Class NodeBase

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.List;
18
19
20
21	/**
22	* The base class for nodes in a {@link Bintree}.
23	*
24	* @version 1.7
25	*/
26	public abstract class NodeBase {
27
28	/**
29	* Returns the index of the subnode that wholely contains the given interval.
30	* If none does, returns -1.
31	*/
32	public static int getSubnodeIndex(Interval interval, double centre)
33	{
34	int subnodeIndex = -1;
35	if (interval.min >= centre) subnodeIndex = 1;
36	if (interval.max <= centre) subnodeIndex = 0;
37	return subnodeIndex;
38	}
39
40	protected List items = new ArrayList();
41
42	/**
43	* subnodes are numbered as follows:
44	*
45	* 0 \| 1
46	*/
47	protected Node[] subnode = new Node[2];
48
49	public NodeBase() {
50	}
51
52	public List getItems() { return items; }
53
54	public void add(Object item)
55	{
56	items.add(item);
57	}
58	public List addAllItems(List items)
59	{
60	items.addAll(this.items);
61	for (int i = 0; i < 2; i++) {
62	if (subnode[i] != null) {
63	subnode[i].addAllItems(items);
64	}
65	}
66	return items;
67	}
68	protected abstract boolean isSearchMatch(Interval interval);
69
70	/**
71	* Adds items in the tree which potentially overlap the query interval
72	* to the given collection.
73	* If the query interval is <tt>null</tt>, add all items in the tree.
74	*
75	* @param interval a query interval, or null
76	* @param resultItems the candidate items found
77	*/
78	public void addAllItemsFromOverlapping(Interval interval, Collection resultItems)
79	{
80	if (interval != null && ! isSearchMatch(interval))
81	return;
82
83	// some of these may not actually overlap - this is allowed by the bintree contract
84	resultItems.addAll(items);
85
86	if (subnode[0] != null) subnode[0].addAllItemsFromOverlapping(interval, resultItems);
87	if (subnode[1] != null) subnode[1].addAllItemsFromOverlapping(interval, resultItems);
88	}
89
90	/**
91	* Removes a single item from this subtree.
92	*
93	* @param itemInterval the envelope containing the item
94	* @param item the item to remove
95	* @return <code>true</code> if the item was found and removed
96	*/
97	public boolean remove(Interval itemInterval, Object item)
98	{
99	// use interval to restrict nodes scanned
100	if (! isSearchMatch(itemInterval))
101	return false;
102
103	boolean found = false;
104	for (int i = 0; i < 2; i++) {
105	if (subnode[i] != null) {
106	found = subnode[i].remove(itemInterval, item);
107	if (found) {
108	// trim subtree if empty
109	if (subnode[i].isPrunable())
110	subnode[i] = null;
111	break;
112	}
113	}
114	}
115	// if item was found lower down, don't need to search for it here
116	if (found) return found;
117	// otherwise, try and remove the item from the list of items in this node
118	found = items.remove(item);
119	return found;
120	}
121
122	public boolean isPrunable()
123	{
124	return ! (hasChildren() \|\| hasItems());
125	}
126
127	public boolean hasChildren()
128	{
129	for (int i = 0; i < 2; i++) {
130	if (subnode[i] != null)
131	return true;
132	}
133	return false;
134	}
135
136	public boolean hasItems() { return ! items.isEmpty(); }
137
138	int depth()
139	{
140	int maxSubDepth = 0;
141	for (int i = 0; i < 2; i++) {
142	if (subnode[i] != null) {
143	int sqd = subnode[i].depth();
144	if (sqd > maxSubDepth)
145	maxSubDepth = sqd;
146	}
147	}
148	return maxSubDepth + 1;
149	}
150
151	int size()
152	{
153	int subSize = 0;
154	for (int i = 0; i < 2; i++) {
155	if (subnode[i] != null) {
156	subSize += subnode[i].size();
157	}
158	}
159	return subSize + items.size();
160	}
161
162	int nodeSize()
163	{
164	int subSize = 0;
165	for (int i = 0; i < 2; i++) {
166	if (subnode[i] != null) {
167	subSize += subnode[i].nodeSize();
168	}
169	}
170	return subSize + 1;
171	}
172
173	}
174