Class Node

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 org.locationtech.jts.util.Assert;
16
17	/**
18	* A node of a {@link Bintree}.
19	*
20	* @version 1.7
21	*/
22	public class Node
23	extends NodeBase
24	{
25	public static Node createNode(Interval itemInterval)
26	{
27	Key key = new Key(itemInterval);
28
29	//System.out.println("input: " + env + " binaryEnv: " + key.getEnvelope());
30	Node node = new Node(key.getInterval(), key.getLevel());
31	return node;
32	}
33
34	public static Node createExpanded(Node node, Interval addInterval)
35	{
36	Interval expandInt = new Interval(addInterval);
37	if (node != null) expandInt.expandToInclude(node.interval);
38
39	Node largerNode = createNode(expandInt);
40	if (node != null) largerNode.insert(node);
41	return largerNode;
42	}
43
44	private Interval interval;
45	private double centre;
46	private int level;
47
48	public Node(Interval interval, int level)
49	{
50	this.interval = interval;
51	this.level = level;
52	centre = (interval.getMin() + interval.getMax()) / 2;
53	}
54
55	public Interval getInterval() { return interval; }
56
57	protected boolean isSearchMatch(Interval itemInterval)
58	{
59	// System.out.println(itemInterval + " overlaps " + interval + " : "
60	// + itemInterval.overlaps(interval));
61	return itemInterval.overlaps(interval);
62	}
63
64	/**
65	* Returns the subnode containing the envelope.
66	* Creates the node if
67	* it does not already exist.
68	*/
69	public Node getNode(Interval searchInterval)
70	{
71	int subnodeIndex = getSubnodeIndex(searchInterval, centre);
72	// if index is -1 searchEnv is not contained in a subnode
73	if (subnodeIndex != -1) {
74	// create the node if it does not exist
75	Node node = getSubnode(subnodeIndex);
76	// recursively search the found/created node
77	return node.getNode(searchInterval);
78	}
79	else {
80	return this;
81	}
82	}
83
84	/**
85	* Returns the smallest <i>existing</i>
86	* node containing the envelope.
87	*/
88	public NodeBase find(Interval searchInterval)
89	{
90	int subnodeIndex = getSubnodeIndex(searchInterval, centre);
91	if (subnodeIndex == -1)
92	return this;
93	if (subnode[subnodeIndex] != null) {
94	// query lies in subnode, so search it
95	Node node = subnode[subnodeIndex];
96	return node.find(searchInterval);
97	}
98	// no existing subnode, so return this one anyway
99	return this;
100	}
101
102	void insert(Node node)
103	{
104	Assert.isTrue(interval == null \|\| interval.contains(node.interval));
105	int index = getSubnodeIndex(node.interval, centre);
106	if (node.level == level - 1) {
107	subnode[index] = node;
108	}
109	else {
110	// the node is not a direct child, so make a new child node to contain it
111	// and recursively insert the node
112	Node childNode = createSubnode(index);
113	childNode.insert(node);
114	subnode[index] = childNode;
115	}
116	}
117
118	/**
119	* get the subnode for the index.
120	* If it doesn't exist, create it
121	*/
122	private Node getSubnode(int index)
123	{
124	if (subnode[index] == null) {
125	subnode[index] = createSubnode(index);
126	}
127	return subnode[index];
128	}
129
130	private Node createSubnode(int index)
131	{
132	// create a new subnode in the appropriate interval
133
134	double min = 0.0;
135	double max = 0.0;
136
137	switch (index) {
138	case 0:
139	min = interval.getMin();
140	max = centre;
141	break;
142	case 1:
143	min = centre;
144	max = interval.getMax();
145	break;
146	}
147	Interval subInt = new Interval(min, max);
148	Node node = new Node(subInt, level - 1);
149	return node;
150	}
151
152	}
153