Class SortedPackedIntervalRTree

1	/*
2	* Copyright (c) 2016 Vivid Solutions.
3	*
4	* All rights reserved. This program and the accompanying materials
5	* are made available under the terms of the Eclipse Public License 2.0
6	* and Eclipse Distribution License v. 1.0 which accompanies this distribution.
7	* The Eclipse Public License is available at http://www.eclipse.org/legal/epl-v20.html
8	* and the Eclipse Distribution License is available at
9	*
10	* http://www.eclipse.org/org/documents/edl-v10.php.
11	*/
12	package org.locationtech.jts.index.intervalrtree;
13
14	import java.util.ArrayList;
15	import java.util.Collections;
16	import java.util.List;
17
18	import org.locationtech.jts.geom.Coordinate;
19	import org.locationtech.jts.index.ItemVisitor;
20	import org.locationtech.jts.io.WKTWriter;
21
22
23	/**
24	* A static index on a set of 1-dimensional intervals,
25	* using an R-Tree packed based on the order of the interval midpoints.
26	* It supports range searching,
27	* where the range is an interval of the real line (which may be a single point).
28	* A common use is to index 1-dimensional intervals which
29	* are the projection of 2-D objects onto an axis of the coordinate system.
30	* <p>
31	* This index structure is <i>static</i>
32	* - items cannot be added or removed once the first query has been made.
33	* The advantage of this characteristic is that the index performance
34	* can be optimized based on a fixed set of items.
35	*
36	* @author Martin Davis
37	*/
38	public class SortedPackedIntervalRTree
39	{
40	private List leaves = new ArrayList();
41
42	/**
43	* If root is null that indicates
44	* that the tree has not yet been built,
45	* OR nothing has been added to the tree.
46	* In both cases, the tree is still open for insertions.
47	*/
48	private IntervalRTreeNode root = null;
49
50	public SortedPackedIntervalRTree()
51	{
52
53	}
54
55	/**
56	* Adds an item to the index which is associated with the given interval
57	*
58	* @param min the lower bound of the item interval
59	* @param max the upper bound of the item interval
60	* @param item the item to insert
61	*
62	* @throws IllegalStateException if the index has already been queried
63	*/
64	public void insert(double min, double max, Object item)
65	{
66	if (root != null)
67	throw new IllegalStateException("Index cannot be added to once it has been queried");
68	leaves.add(new IntervalRTreeLeafNode(min, max, item));
69	}
70
71	private void init()
72	{
73	// already built
74	if (root != null) return;
75
76	/**
77	* if leaves is empty then nothing has been inserted.
78	* In this case it is safe to leave the tree in an open state
79	*/
80	if (leaves.size() == 0) return;
81
82	buildRoot();
83	}
84
85	private synchronized void buildRoot()
86	{
87	if (root != null) return;
88	root = buildTree();
89	}
90
91	private IntervalRTreeNode buildTree()
92	{
93
94	// sort the leaf nodes
95	Collections.sort(leaves, new IntervalRTreeNode.NodeComparator());
96
97	// now group nodes into blocks of two and build tree up recursively
98	List src = leaves;
99	List temp = null;
100	List dest = new ArrayList();
101
102	while (true) {
103	buildLevel(src, dest);
104	if (dest.size() == 1)
105	return (IntervalRTreeNode) dest.get(0);
106
107	temp = src;
108	src = dest;
109	dest = temp;
110	}
111	}
112
113	private int level = 0;
114
115	private void buildLevel(List src, List dest)
116	{
117	level++;
118	dest.clear();
119	for (int i = 0; i < src.size(); i += 2) {
120	IntervalRTreeNode n1 = (IntervalRTreeNode) src.get(i);
121	IntervalRTreeNode n2 = (i + 1 < src.size())
122	? (IntervalRTreeNode) src.get(i) : null;
123	if (n2 == null) {
124	dest.add(n1);
125	} else {
126	IntervalRTreeNode node = new IntervalRTreeBranchNode(
127	(IntervalRTreeNode) src.get(i),
128	(IntervalRTreeNode) src.get(i + 1));
129	// printNode(node);
130	// System.out.println(node);
131	dest.add(node);
132	}
133	}
134	}
135
136	private void printNode(IntervalRTreeNode node)
137	{
138	System.out.println(WKTWriter.toLineString(new Coordinate(node.min, level), new Coordinate(node.max, level)));
139	}
140
141	/**
142	* Search for intervals in the index which intersect the given closed interval
143	* and apply the visitor to them.
144	*
145	* @param min the lower bound of the query interval
146	* @param max the upper bound of the query interval
147	* @param visitor the visitor to pass any matched items to
148	*/
149	public void query(double min, double max, ItemVisitor visitor)
150	{
151	init();
152
153	// if root is null tree must be empty
154	if (root == null)
155	return;
156
157	root.query(min, max, visitor);
158	}
159
160	}
161