Class SIRtree

1
2	/*
3	* Copyright (c) 2016 Vivid Solutions.
4	*
5	* All rights reserved. This program and the accompanying materials
6	* are made available under the terms of the Eclipse Public License 2.0
7	* and Eclipse Distribution License v. 1.0 which accompanies this distribution.
8	* The Eclipse Public License is available at http://www.eclipse.org/legal/epl-v20.html
9	* and the Eclipse Distribution License is available at
10	*
11	* http://www.eclipse.org/org/documents/edl-v10.php.
12	*/
13	package org.locationtech.jts.index.strtree;
14
15	import java.util.Comparator;
16	import java.util.Iterator;
17	import java.util.List;
18
19	/**
20	* One-dimensional version of an STR-packed R-tree. SIR stands for
21	* "Sort-Interval-Recursive". STR-packed R-trees are described in:
22	* P. Rigaux, Michel Scholl and Agnes Voisard. Spatial Databases With
23	* Application To GIS. Morgan Kaufmann, San Francisco, 2002.
24	* <p>
25	* This class is thread-safe. Building the tree is synchronized,
26	* and querying is stateless.
27	*
28	* @see STRtree
29	*
30	* @version 1.7
31	*/
32	public class SIRtree extends AbstractSTRtree {
33
34	private Comparator comparator = new Comparator() {
35	public int compare(Object o1, Object o2) {
36	return compareDoubles(
37	((Interval)((Boundable)o1).getBounds()).getCentre(),
38	((Interval)((Boundable)o2).getBounds()).getCentre());
39	}
40	};
41
42	private IntersectsOp intersectsOp = new IntersectsOp() {
43	public boolean intersects(Object aBounds, Object bBounds) {
44	return ((Interval)aBounds).intersects((Interval)bBounds);
45	}
46	};
47
48	/**
49	* Constructs an SIRtree with the default node capacity.
50	*/
51	public SIRtree() { this(10); }
52
53	/**
54	* Constructs an SIRtree with the given maximum number of child nodes that
55	* a node may have
56	*/
57	public SIRtree(int nodeCapacity) {
58	super(nodeCapacity);
59	}
60
61	protected AbstractNode createNode(int level) {
62	return new AbstractNode(level) {
63	protected Object computeBounds() {
64	Interval bounds = null;
65	for (Iterator i = getChildBoundables().iterator(); i.hasNext(); ) {
66	Boundable childBoundable = (Boundable) i.next();
67	if (bounds == null) {
68	bounds = new Interval((Interval)childBoundable.getBounds());
69	}
70	else {
71	bounds.expandToInclude((Interval)childBoundable.getBounds());
72	}
73	}
74	return bounds;
75	}
76	};
77	}
78
79	/**
80	* Inserts an item having the given bounds into the tree.
81	*/
82	public void insert(double x1, double x2, Object item) {
83	super.insert(new Interval(Math.min(x1, x2), Math.max(x1, x2)), item);
84	}
85
86	/**
87	* Returns items whose bounds intersect the given value.
88	*/
89	public List query(double x) {
90	return query(x, x);
91	}
92
93	/**
94	* Returns items whose bounds intersect the given bounds.
95	* @param x1 possibly equal to x2
96	*/
97	public List query(double x1, double x2) {
98	return super.query(new Interval(Math.min(x1, x2), Math.max(x1, x2)));
99	}
100
101	protected IntersectsOp getIntersectsOp() {
102	return intersectsOp;
103	}
104
105	protected Comparator getComparator() {
106	return comparator;
107	}
108
109	}
110