Doc Classic

Class Root

  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.index.quadtree.IntervalSize;
 16 import org.locationtech.jts.util.Assert;
 17  
 18 /**
 19  * The root node of a single {@link Bintree}.
 20  * It is centred at the origin,
 21  * and does not have a defined extent.
 22  *
 23  * @version 1.7
 24  */
 25 public class Root
 26   extends NodeBase
 27 {
 28  
 29   // the singleton root node is centred at the origin.
 30   private static final double origin = 0.0;
 31  
 32   public Root()
 33   {
 34   }
 35  
 36   /**
 37    * Insert an item into the tree this is the root of.
 38    */
 39   public void insert(Interval itemInterval, Object item)
 40   {
 41     int index = getSubnodeIndex(itemInterval, origin);
 42     // if index is -1, itemEnv must contain the origin.
 43     if (index == -1) {
 44       add(item);
 45       return;
 46     }
 47     /**
 48      * the item must be contained in one interval, so insert it into the
 49      * tree for that interval (which may not yet exist)
 50      */
 51     Node node = subnode[index];
 52     /**
 53      *  If the subnode doesn't exist or this item is not contained in it,
 54      *  have to expand the tree upward to contain the item.
 55      */
 56  
 57     if (node == null || ! node.getInterval().contains(itemInterval)) {
 58        Node largerNode = Node.createExpanded(node, itemInterval);
 59        subnode[index] = largerNode;
 60     }
 61     /**
 62      * At this point we have a subnode which exists and must contain
 63      * contains the env for the item.  Insert the item into the tree.
 64      */
 65     insertContained(subnode[index], itemInterval, item);
 66 //System.out.println("depth = " + root.depth() + " size = " + root.size());
 67   }
 68  
 69   /**
 70    * insert an item which is known to be contained in the tree rooted at
 71    * the given Node.  Lower levels of the tree will be created
 72    * if necessary to hold the item.
 73    */
 74   private void insertContained(Node tree, Interval itemInterval, Object item)
 75   {
 76     Assert.isTrue(tree.getInterval().contains(itemInterval));
 77    /**
 78     * Do NOT create a new node for zero-area intervals - this would lead
 79     * to infinite recursion. Instead, use a heuristic of simply returning
 80     * the smallest existing node containing the query
 81     */
 82     boolean isZeroArea = IntervalSize.isZeroWidth(itemInterval.getMin(), itemInterval.getMax());
 83     NodeBase node;
 84     if (isZeroArea)
 85       node = tree.find(itemInterval);
 86     else
 87       node = tree.getNode(itemInterval);
 88     node.add(item);
 89   }
 90  
 91   /**
 92    * The root node matches all searches
 93    */
 94   protected boolean isSearchMatch(Interval interval)
 95   {
 96     return true;
 97   }
 98  
 99  
100 }
101