Class Bintree

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.bintree;
14
15	import java.util.ArrayList;
16	import java.util.Collection;
17	import java.util.Iterator;
18	import java.util.List;
19
20
21	/**
22	* An <code>BinTree</code> (or "Binary Interval Tree")
23	* is a 1-dimensional version of a quadtree.
24	* It indexes 1-dimensional intervals (which may
25	* be the projection of 2-D objects on an axis).
26	* It supports range searching
27	* (where the range may be a single point).
28	* This structure is dynamic -
29	* new items can be added at any time,
30	* and it will support deletion of items
31	* (although this is not currently implemented).
32	* <p>
33	* This implementation does not require specifying the extent of the inserted
34	* items beforehand. It will automatically expand to accommodate any extent
35	* of dataset.
36	* <p>
37	* The bintree structure is used to provide a primary filter
38	* for interval queries. The query() method returns a list of
39	* all objects which <i>may</i> intersect the query interval.
40	* Note that it may return objects which do not in fact intersect.
41	* A secondary filter is required to test for exact intersection.
42	* Of course, this secondary filter may consist of other tests besides
43	* intersection, such as testing other kinds of spatial relationships.
44	* <p>
45	* This index is different to the Interval Tree of Edelsbrunner
46	* or the Segment Tree of Bentley.
47	*
48	* @version 1.7
49	*/
50	public class Bintree
51	{
52	/**
53	* Ensure that the Interval for the inserted item has non-zero extents.
54	* Use the current minExtent to pad it, if necessary
55	*/
56	public static Interval ensureExtent(Interval itemInterval, double minExtent)
57	{
58	double min = itemInterval.getMin();
59	double max = itemInterval.getMax();
60	// has a non-zero extent
61	if (min != max) return itemInterval;
62
63	// pad extent
64	if (min == max) {
65	min = min - minExtent / 2.0;
66	max = min + minExtent / 2.0;
67	}
68	return new Interval(min, max);
69	}
70
71	private Root root;
72	/**
73	* Statistics
74	*
75	* minExtent is the minimum extent of all items
76	* inserted into the tree so far. It is used as a heuristic value
77	* to construct non-zero extents for features with zero extent.
78	* Start with a non-zero extent, in case the first feature inserted has
79	* a zero extent in both directions. This value may be non-optimal, but
80	* only one feature will be inserted with this value.
81	**/
82	private double minExtent = 1.0;
83
84	public Bintree()
85	{
86	root = new Root();
87	}
88
89	public int depth()
90	{
91	if (root != null) return root.depth();
92	return 0;
93	}
94	public int size()
95	{
96	if (root != null) return root.size();
97	return 0;
98	}
99	/**
100	* Compute the total number of nodes in the tree
101	*
102	* @return the number of nodes in the tree
103	*/
104	public int nodeSize()
105	{
106	if (root != null) return root.nodeSize();
107	return 0;
108	}
109
110	public void insert(Interval itemInterval, Object item)
111	{
112	collectStats(itemInterval);
113	Interval insertInterval = ensureExtent(itemInterval, minExtent);
114	//int oldSize = size();
115	root.insert(insertInterval, item);
116	/* DEBUG
117	int newSize = size();
118	System.out.println("BinTree: size = " + newSize + " node size = " + nodeSize());
119	if (newSize <= oldSize) {
120	System.out.println("Lost item!");
121	root.insert(insertInterval, item);
122	System.out.println("reinsertion size = " + size());
123	}
124	*/
125	}
126
127	/**
128	* Removes a single item from the tree.
129	*
130	* @param itemEnv the Envelope of the item to be removed
131	* @param item the item to remove
132	* @return <code>true</code> if the item was found (and thus removed)
133	*/
134	public boolean remove(Interval itemInterval, Object item)
135	{
136	Interval insertInterval = ensureExtent(itemInterval, minExtent);
137	return root.remove(insertInterval, item);
138	}
139
140	public Iterator iterator()
141	{
142	List foundItems = new ArrayList();
143	root.addAllItems(foundItems);
144	return foundItems.iterator();
145	}
146
147	public List query(double x)
148	{
149	return query(new Interval(x, x));
150	}
151
152	/**
153	* Queries the tree to find all candidate items which
154	* may overlap the query interval.
155	* If the query interval is <tt>null</tt>, all items in the tree are found.
156	*
157	* min and max may be the same value
158	*/
159	public List query(Interval interval)
160	{
161	/**
162	* the items that are matched are all items in intervals
163	* which overlap the query interval
164	*/
165	List foundItems = new ArrayList();
166	query(interval, foundItems);
167	return foundItems;
168	}
169
170	/**
171	* Adds items in the tree which potentially overlap the query interval
172	* to the given collection.
173	* If the query interval is <tt>null</tt>, add all items in the tree.
174	*
175	* @param interval a query interval, or null
176	* @param resultItems the candidate items found
177	*/
178	public void query(Interval interval, Collection foundItems)
179	{
180	root.addAllItemsFromOverlapping(interval, foundItems);
181	}
182
183	private void collectStats(Interval interval)
184	{
185	double del = interval.getWidth();
186	if (del < minExtent && del > 0.0)
187	minExtent = del;
188	}
189
190	}
191