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.index.quadtree.IntervalSize;
036: import com.vividsolutions.jts.util.Assert;
037:
038: /**
039: * The root node of a single {@link Bintree}.
040: * It is centred at the origin,
041: * and does not have a defined extent.
042: *
043: * @version 1.7
044: */
045: public class Root extends NodeBase {
046:
047: // the singleton root node is centred at the origin.
048: private static final double origin = 0.0;
049:
050: public Root() {
051: }
052:
053: /**
054: * Insert an item into the tree this is the root of.
055: */
056: public void insert(Interval itemInterval, Object item) {
057: int index = getSubnodeIndex(itemInterval, origin);
058: // if index is -1, itemEnv must contain the origin.
059: if (index == -1) {
060: add(item);
061: return;
062: }
063: /**
064: * the item must be contained in one interval, so insert it into the
065: * tree for that interval (which may not yet exist)
066: */
067: Node node = subnode[index];
068: /**
069: * If the subnode doesn't exist or this item is not contained in it,
070: * have to expand the tree upward to contain the item.
071: */
072:
073: if (node == null || !node.getInterval().contains(itemInterval)) {
074: Node largerNode = Node.createExpanded(node, itemInterval);
075: subnode[index] = largerNode;
076: }
077: /**
078: * At this point we have a subnode which exists and must contain
079: * contains the env for the item. Insert the item into the tree.
080: */
081: insertContained(subnode[index], itemInterval, item);
082: //System.out.println("depth = " + root.depth() + " size = " + root.size());
083: }
084:
085: /**
086: * insert an item which is known to be contained in the tree rooted at
087: * the given Node. Lower levels of the tree will be created
088: * if necessary to hold the item.
089: */
090: private void insertContained(Node tree, Interval itemInterval,
091: Object item) {
092: Assert.isTrue(tree.getInterval().contains(itemInterval));
093: /**
094: * Do NOT create a new node for zero-area intervals - this would lead
095: * to infinite recursion. Instead, use a heuristic of simply returning
096: * the smallest existing node containing the query
097: */
098: boolean isZeroArea = IntervalSize.isZeroWidth(itemInterval
099: .getMin(), itemInterval.getMax());
100: NodeBase node;
101: if (isZeroArea)
102: node = tree.find(itemInterval);
103: else
104: node = tree.getNode(itemInterval);
105: node.add(item);
106: }
107:
108: /**
109: * The root node matches all searches
110: */
111: protected boolean isSearchMatch(Interval interval) {
112: return true;
113: }
114:
115: }
|