001: /*
002: * The JTS Topology Suite is a collection of Java classes that
003: * implement the fundamental operations required to validate a given
004: * geo-spatial data set to a known topological specification.
005: *
006: * Copyright (C) 2001 Vivid Solutions
007: *
008: * This library is free software; you can redistribute it and/or
009: * modify it under the terms of the GNU Lesser General Public
010: * License as published by the Free Software Foundation; either
011: * version 2.1 of the License, or (at your option) any later version.
012: *
013: * This library is distributed in the hope that it will be useful,
014: * but WITHOUT ANY WARRANTY; without even the implied warranty of
015: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
016: * Lesser General Public License for more details.
017: *
018: * You should have received a copy of the GNU Lesser General Public
019: * License along with this library; if not, write to the Free Software
020: * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
021: *
022: * For more information, contact:
023: *
024: * Vivid Solutions
025: * Suite #1A
026: * 2328 Government Street
027: * Victoria BC V8T 5G5
028: * Canada
029: *
030: * (250)385-6040
031: * www.vividsolutions.com
032: */
033: package com.vividsolutions.jts.index.bintree;
034:
035: import com.vividsolutions.jts.util.Assert;
036:
037: /**
038: * A node of a {@link Bintree}.
039: *
040: * @version 1.7
041: */
042: public class Node extends NodeBase {
043: public static Node createNode(Interval itemInterval) {
044: Key key = new Key(itemInterval);
045:
046: //System.out.println("input: " + env + " binaryEnv: " + key.getEnvelope());
047: Node node = new Node(key.getInterval(), key.getLevel());
048: return node;
049: }
050:
051: public static Node createExpanded(Node node, Interval addInterval) {
052: Interval expandInt = new Interval(addInterval);
053: if (node != null)
054: expandInt.expandToInclude(node.interval);
055:
056: Node largerNode = createNode(expandInt);
057: if (node != null)
058: largerNode.insert(node);
059: return largerNode;
060: }
061:
062: private Interval interval;
063: private double centre;
064: private int level;
065:
066: public Node(Interval interval, int level) {
067: this .interval = interval;
068: this .level = level;
069: centre = (interval.getMin() + interval.getMax()) / 2;
070: }
071:
072: public Interval getInterval() {
073: return interval;
074: }
075:
076: protected boolean isSearchMatch(Interval itemInterval) {
077: // System.out.println(itemInterval + " overlaps " + interval + " : "
078: // + itemInterval.overlaps(interval));
079: return itemInterval.overlaps(interval);
080: }
081:
082: /**
083: * Returns the subnode containing the envelope.
084: * Creates the node if
085: * it does not already exist.
086: */
087: public Node getNode(Interval searchInterval) {
088: int subnodeIndex = getSubnodeIndex(searchInterval, centre);
089: // if index is -1 searchEnv is not contained in a subnode
090: if (subnodeIndex != -1) {
091: // create the node if it does not exist
092: Node node = getSubnode(subnodeIndex);
093: // recursively search the found/created node
094: return node.getNode(searchInterval);
095: } else {
096: return this ;
097: }
098: }
099:
100: /**
101: * Returns the smallest <i>existing</i>
102: * node containing the envelope.
103: */
104: public NodeBase find(Interval searchInterval) {
105: int subnodeIndex = getSubnodeIndex(searchInterval, centre);
106: if (subnodeIndex == -1)
107: return this ;
108: if (subnode[subnodeIndex] != null) {
109: // query lies in subnode, so search it
110: Node node = subnode[subnodeIndex];
111: return node.find(searchInterval);
112: }
113: // no existing subnode, so return this one anyway
114: return this ;
115: }
116:
117: void insert(Node node) {
118: Assert.isTrue(interval == null
119: || interval.contains(node.interval));
120: int index = getSubnodeIndex(node.interval, centre);
121: if (node.level == level - 1) {
122: subnode[index] = node;
123: } else {
124: // the node is not a direct child, so make a new child node to contain it
125: // and recursively insert the node
126: Node childNode = createSubnode(index);
127: childNode.insert(node);
128: subnode[index] = childNode;
129: }
130: }
131:
132: /**
133: * get the subnode for the index.
134: * If it doesn't exist, create it
135: */
136: private Node getSubnode(int index) {
137: if (subnode[index] == null) {
138: subnode[index] = createSubnode(index);
139: }
140: return subnode[index];
141: }
142:
143: private Node createSubnode(int index) {
144: // create a new subnode in the appropriate interval
145:
146: double min = 0.0;
147: double max = 0.0;
148:
149: switch (index) {
150: case 0:
151: min = interval.getMin();
152: max = centre;
153: break;
154: case 1:
155: min = centre;
156: max = interval.getMax();
157: break;
158: }
159: Interval subInt = new Interval(min, max);
160: Node node = new Node(subInt, level - 1);
161: return node;
162: }
163:
164: }
|