Class AbstractSTRtree

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
16	import java.io.Serializable;
17	import java.util.ArrayList;
18	import java.util.Collection;
19	import java.util.Collections;
20	import java.util.Comparator;
21	import java.util.Iterator;
22	import java.util.List;
23
24	import org.locationtech.jts.index.ItemVisitor;
25	import org.locationtech.jts.util.Assert;
26
27	/**
28	* Base class for STRtree and SIRtree. STR-packed R-trees are described in:
29	* P. Rigaux, Michel Scholl and Agnes Voisard. <i>Spatial Databases With
30	* Application To GIS.</i> Morgan Kaufmann, San Francisco, 2002.
31	* <p>
32	* This implementation is based on {@link Boundable}s rather than {@link AbstractNode}s,
33	* because the STR algorithm operates on both nodes and
34	* data, both of which are treated as Boundables.
35	* <p>
36	* This class is thread-safe. Building the tree is synchronized,
37	* and querying is stateless.
38	*
39	* @see STRtree
40	* @see SIRtree
41	*
42	* @version 1.7
43	*/
44	public abstract class AbstractSTRtree implements Serializable {
45
46	/**
47	*
48	*/
49	private static final long serialVersionUID = -3886435814360241337L;
50
51	/**
52	* A test for intersection between two bounds, necessary because subclasses
53	* of AbstractSTRtree have different implementations of bounds.
54	*/
55	protected static interface IntersectsOp {
56	/**
57	* For STRtrees, the bounds will be Envelopes; for SIRtrees, Intervals;
58	* for other subclasses of AbstractSTRtree, some other class.
59	* @param aBounds the bounds of one spatial object
60	* @param bBounds the bounds of another spatial object
61	* @return whether the two bounds intersect
62	*/
63	boolean intersects(Object aBounds, Object bBounds);
64	}
65
66	protected AbstractNode root;
67
68	private boolean built = false;
69	/**
70	* Set to <tt>null</tt> when index is built, to avoid retaining memory.
71	*/
72	private ArrayList itemBoundables = new ArrayList();
73
74	private int nodeCapacity;
75
76	private static final int DEFAULT_NODE_CAPACITY = 10;
77
78	/**
79	* Constructs an AbstractSTRtree with the
80	* default node capacity.
81	*/
82	public AbstractSTRtree() {
83	this(DEFAULT_NODE_CAPACITY);
84	}
85
86	/**
87	* Constructs an AbstractSTRtree with the specified maximum number of child
88	* nodes that a node may have
89	*
90	* @param nodeCapacity the maximum number of child nodes in a node
91	*/
92	public AbstractSTRtree(int nodeCapacity) {
93	Assert.isTrue(nodeCapacity > 1, "Node capacity must be greater than 1");
94	this.nodeCapacity = nodeCapacity;
95	}
96
97	/**
98	* Creates parent nodes, grandparent nodes, and so forth up to the root
99	* node, for the data that has been inserted into the tree. Can only be
100	* called once, and thus can be called only after all of the data has been
101	* inserted into the tree.
102	*/
103	public synchronized void build() {
104	if (built) return;
105	root = itemBoundables.isEmpty()
106	? createNode(0)
107	: createHigherLevels(itemBoundables, -1);
108	// the item list is no longer needed
109	itemBoundables = null;
110	built = true;
111	}
112
113	protected abstract AbstractNode createNode(int level);
114
115	/**
116	* Sorts the childBoundables then divides them into groups of size M, where
117	* M is the node capacity.
118	*/
119	protected List createParentBoundables(List childBoundables, int newLevel) {
120	Assert.isTrue(!childBoundables.isEmpty());
121	ArrayList parentBoundables = new ArrayList();
122	parentBoundables.add(createNode(newLevel));
123	ArrayList sortedChildBoundables = new ArrayList(childBoundables);
124	Collections.sort(sortedChildBoundables, getComparator());
125	for (Iterator i = sortedChildBoundables.iterator(); i.hasNext(); ) {
126	Boundable childBoundable = (Boundable) i.next();
127	if (lastNode(parentBoundables).getChildBoundables().size() == getNodeCapacity()) {
128	parentBoundables.add(createNode(newLevel));
129	}
130	lastNode(parentBoundables).addChildBoundable(childBoundable);
131	}
132	return parentBoundables;
133	}
134
135	protected AbstractNode lastNode(List nodes) {
136	return (AbstractNode) nodes.get(nodes.size() - 1);
137	}
138
139	protected static int compareDoubles(double a, double b) {
140	return a > b ? 1
141	: a < b ? -1
142	: 0;
143	}
144
145	/**
146	* Creates the levels higher than the given level
147	*
148	* @param boundablesOfALevel
149	* the level to build on
150	* @param level
151	* the level of the Boundables, or -1 if the boundables are item
152	* boundables (that is, below level 0)
153	* @return the root, which may be a ParentNode or a LeafNode
154	*/
155	private AbstractNode createHigherLevels(List boundablesOfALevel, int level) {
156	Assert.isTrue(!boundablesOfALevel.isEmpty());
157	List parentBoundables = createParentBoundables(boundablesOfALevel, level + 1);
158	if (parentBoundables.size() == 1) {
159	return (AbstractNode) parentBoundables.get(0);
160	}
161	return createHigherLevels(parentBoundables, level + 1);
162	}
163
164	/**
165	* Gets the root node of the tree.
166	*
167	* @return the root node
168	*/
169	public AbstractNode getRoot()
170	{
171	build();
172	return root;
173	}
174
175	/**
176	* Returns the maximum number of child nodes that a node may have.
177	*
178	* @return the node capacity
179	*/
180	public int getNodeCapacity() { return nodeCapacity; }
181
182	/**
183	* Tests whether the index contains any items.
184	* This method does not build the index,
185	* so items can still be inserted after it has been called.
186	*
187	* @return true if the index does not contain any items
188	*/
189	public boolean isEmpty()
190	{
191	if (! built) return itemBoundables.isEmpty();
192	return root.isEmpty();
193	}
194
195	protected int size() {
196	if (isEmpty()) {
197	return 0;
198	}
199	build();
200	return size(root);
201	}
202
203	protected int size(AbstractNode node)
204	{
205	int size = 0;
206	for (Iterator i = node.getChildBoundables().iterator(); i.hasNext(); ) {
207	Boundable childBoundable = (Boundable) i.next();
208	if (childBoundable instanceof AbstractNode) {
209	size += size((AbstractNode) childBoundable);
210	}
211	else if (childBoundable instanceof ItemBoundable) {
212	size += 1;
213	}
214	}
215	return size;
216	}
217
218	protected int depth() {
219	if (isEmpty()) {
220	return 0;
221	}
222	build();
223	return depth(root);
224	}
225
226	protected int depth(AbstractNode node)
227	{
228	int maxChildDepth = 0;
229	for (Iterator i = node.getChildBoundables().iterator(); i.hasNext(); ) {
230	Boundable childBoundable = (Boundable) i.next();
231	if (childBoundable instanceof AbstractNode) {
232	int childDepth = depth((AbstractNode) childBoundable);
233	if (childDepth > maxChildDepth)
234	maxChildDepth = childDepth;
235	}
236	}
237	return maxChildDepth + 1;
238	}
239
240
241	protected void insert(Object bounds, Object item) {
242	Assert.isTrue(!built, "Cannot insert items into an STR packed R-tree after it has been built.");
243	itemBoundables.add(new ItemBoundable(bounds, item));
244	}
245
246	/**
247	* Also builds the tree, if necessary.
248	*/
249	protected List query(Object searchBounds) {
250	build();
251	ArrayList matches = new ArrayList();
252	if (isEmpty()) {
253	//Assert.isTrue(root.getBounds() == null);
254	return matches;
255	}
256	if (getIntersectsOp().intersects(root.getBounds(), searchBounds)) {
257	queryInternal(searchBounds, root, matches);
258	}
259	return matches;
260	}
261
262	/**
263	* Also builds the tree, if necessary.
264	*/
265	protected void query(Object searchBounds, ItemVisitor visitor) {
266	build();
267	if (isEmpty()) {
268	// nothing in tree, so return
269	//Assert.isTrue(root.getBounds() == null);
270	return;
271	}
272	if (getIntersectsOp().intersects(root.getBounds(), searchBounds)) {
273	queryInternal(searchBounds, root, visitor);
274	}
275	}
276
277	/**
278	* @return a test for intersection between two bounds, necessary because subclasses
279	* of AbstractSTRtree have different implementations of bounds.
280	* @see IntersectsOp
281	*/
282	protected abstract IntersectsOp getIntersectsOp();
283
284	private void queryInternal(Object searchBounds, AbstractNode node, List matches) {
285	List childBoundables = node.getChildBoundables();
286	for (int i = 0; i < childBoundables.size(); i++) {
287	Boundable childBoundable = (Boundable) childBoundables.get(i);
288	if (! getIntersectsOp().intersects(childBoundable.getBounds(), searchBounds)) {
289	continue;
290	}
291	if (childBoundable instanceof AbstractNode) {
292	queryInternal(searchBounds, (AbstractNode) childBoundable, matches);
293	}
294	else if (childBoundable instanceof ItemBoundable) {
295	matches.add(((ItemBoundable)childBoundable).getItem());
296	}
297	else {
298	Assert.shouldNeverReachHere();
299	}
300	}
301	}
302
303	private void queryInternal(Object searchBounds, AbstractNode node, ItemVisitor visitor) {
304	List childBoundables = node.getChildBoundables();
305	for (int i = 0; i < childBoundables.size(); i++) {
306	Boundable childBoundable = (Boundable) childBoundables.get(i);
307	if (! getIntersectsOp().intersects(childBoundable.getBounds(), searchBounds)) {
308	continue;
309	}
310	if (childBoundable instanceof AbstractNode) {
311	queryInternal(searchBounds, (AbstractNode) childBoundable, visitor);
312	}
313	else if (childBoundable instanceof ItemBoundable) {
314	visitor.visitItem(((ItemBoundable)childBoundable).getItem());
315	}
316	else {
317	Assert.shouldNeverReachHere();
318	}
319	}
320	}
321
322	/**
323	* Gets a tree structure (as a nested list)
324	* corresponding to the structure of the items and nodes in this tree.
325	* <p>
326	* The returned {@link List}s contain either {@link Object} items,
327	* or Lists which correspond to subtrees of the tree
328	* Subtrees which do not contain any items are not included.
329	* <p>
330	* Builds the tree if necessary.
331	*
332	* @return a List of items and/or Lists
333	*/
334	public List itemsTree()
335	{
336	build();
337
338	List valuesTree = itemsTree(root);
339	if (valuesTree == null)
340	return new ArrayList();
341	return valuesTree;
342	}
343
344	private List itemsTree(AbstractNode node)
345	{
346	List valuesTreeForNode = new ArrayList();
347	for (Iterator i = node.getChildBoundables().iterator(); i.hasNext(); ) {
348	Boundable childBoundable = (Boundable) i.next();
349	if (childBoundable instanceof AbstractNode) {
350	List valuesTreeForChild = itemsTree((AbstractNode) childBoundable);
351	// only add if not null (which indicates an item somewhere in this tree
352	if (valuesTreeForChild != null)
353	valuesTreeForNode.add(valuesTreeForChild);
354	}
355	else if (childBoundable instanceof ItemBoundable) {
356	valuesTreeForNode.add(((ItemBoundable)childBoundable).getItem());
357	}
358	else {
359	Assert.shouldNeverReachHere();
360	}
361	}
362	if (valuesTreeForNode.size() <= 0)
363	return null;
364	return valuesTreeForNode;
365	}
366
367	/**
368	* Removes an item from the tree.
369	* (Builds the tree, if necessary.)
370	*/
371	protected boolean remove(Object searchBounds, Object item) {
372	build();
373	if (getIntersectsOp().intersects(root.getBounds(), searchBounds)) {
374	return remove(searchBounds, root, item);
375	}
376	return false;
377	}
378
379	private boolean removeItem(AbstractNode node, Object item)
380	{
381	Boundable childToRemove = null;
382	for (Iterator i = node.getChildBoundables().iterator(); i.hasNext(); ) {
383	Boundable childBoundable = (Boundable) i.next();
384	if (childBoundable instanceof ItemBoundable) {
385	if ( ((ItemBoundable) childBoundable).getItem() == item)
386	childToRemove = childBoundable;
387	}
388	}
389	if (childToRemove != null) {
390	node.getChildBoundables().remove(childToRemove);
391	return true;
392	}
393	return false;
394	}
395
396	private boolean remove(Object searchBounds, AbstractNode node, Object item) {
397	// first try removing item from this node
398	boolean found = removeItem(node, item);
399	if (found)
400	return true;
401
402	AbstractNode childToPrune = null;
403	// next try removing item from lower nodes
404	for (Iterator i = node.getChildBoundables().iterator(); i.hasNext(); ) {
405	Boundable childBoundable = (Boundable) i.next();
406	if (!getIntersectsOp().intersects(childBoundable.getBounds(), searchBounds)) {
407	continue;
408	}
409	if (childBoundable instanceof AbstractNode) {
410	found = remove(searchBounds, (AbstractNode) childBoundable, item);
411	// if found, record child for pruning and exit
412	if (found) {
413	childToPrune = (AbstractNode) childBoundable;
414	break;
415	}
416	}
417	}
418	// prune child if possible
419	if (childToPrune != null) {
420	if (childToPrune.getChildBoundables().isEmpty()) {
421	node.getChildBoundables().remove(childToPrune);
422	}
423	}
424	return found;
425	}
426
427	protected List boundablesAtLevel(int level) {
428	ArrayList boundables = new ArrayList();
429	boundablesAtLevel(level, root, boundables);
430	return boundables;
431	}
432
433	/**
434	* @param level -1 to get items
435	*/
436	private void boundablesAtLevel(int level, AbstractNode top, Collection boundables) {
437	Assert.isTrue(level > -2);
438	if (top.getLevel() == level) {
439	boundables.add(top);
440	return;
441	}
442	for (Iterator i = top.getChildBoundables().iterator(); i.hasNext(); ) {
443	Boundable boundable = (Boundable) i.next();
444	if (boundable instanceof AbstractNode) {
445	boundablesAtLevel(level, (AbstractNode)boundable, boundables);
446	}
447	else {
448	Assert.isTrue(boundable instanceof ItemBoundable);
449	if (level == -1) { boundables.add(boundable); }
450	}
451	}
452	return;
453	}
454
455	protected abstract Comparator getComparator();
456
457	}
458