src/index/bintree/Node.cpp

   1 /**********************************************************************
   2  * $Id$
   3  *
   4  * GEOS - Geometry Engine Open Source
   5  * http://geos.refractions.net
   6  *
   7  * Copyright (C) 2006 Refractions Research Inc.
   8  * Copyright (C) 2001-2002 Vivid Solutions Inc.
   9  *
  10  * This is free software; you can redistribute and/or modify it under
  11  * the terms of the GNU Lesser General Public Licence as published
  12  * by the Free Software Foundation.
  13  * See the COPYING file for more information.
  14  *
  15  **********************************************************************/
  16
  17 #include <cstddef>
  18 #include <cassert>
  19
  20 #include <geos/index/bintree/Node.h>
  21 #include <geos/index/bintree/Key.h>
  22 #include <geos/index/bintree/Interval.h>
  23
  24 namespace geos {
  25 namespace index { // geos.index
  26 namespace bintree { // geos.index.bintree
  27
  28 Node*
  29 Node::createNode(Interval *itemInterval)
  30 {
  31         Key *key=new Key(itemInterval);
  32         //System.out.println("input: " + env + "  binaryEnv: " + key.getEnvelope());
  33         Node* node=new Node(new Interval(key->getInterval()),key->getLevel());
  34         delete key;
  35         return node;
  36 }
  37
  38 Node*
  39 Node::createExpanded(Node *node,Interval *addInterval)
  40 {
  41         Interval *expandInt=new Interval(addInterval);
  42         if (node!=NULL) expandInt->expandToInclude(node->interval);
  43         Node *largerNode=createNode(expandInt);
  44         if (node!=NULL) largerNode->insert(node);
  45         delete expandInt;
  46         return largerNode;
  47 }
  48
  49 Node::Node(Interval *newInterval,int newLevel)
  50 {
  51         interval=newInterval;
  52         level=newLevel;
  53         centre=(interval->getMin()+interval->getMax())/2;
  54 }
  55
  56 Node::~Node()
  57 {
  58         delete interval;
  59 }
  60
  61 Interval*
  62 Node::getInterval()
  63 {
  64         return interval;
  65 }
  66
  67 bool
  68 Node::isSearchMatch(Interval *itemInterval)
  69 {
  70         return itemInterval->overlaps(interval);
  71 }
  72
  73 /**
  74  * Returns the subnode containing the envelope.
  75  * Creates the node if
  76  * it does not already exist.
  77  */
  78 Node*
  79 Node::getNode(Interval *searchInterval)
  80 {
  81         int subnodeIndex=getSubnodeIndex(searchInterval,centre);
  82         // if index is -1 searchEnv is not contained in a subnode
  83         if (subnodeIndex!=-1) {
  84                 // create the node if it does not exist
  85                 Node* node=getSubnode(subnodeIndex);
  86                 // recursively search the found/created node
  87                 return node->getNode(searchInterval);
  88         } else {
  89                 return this;
  90         }
  91 }
  92
  93 /**
  94  * Returns the smallest <i>existing</i>
  95  * node containing the envelope.
  96  */
  97 NodeBase*
  98 Node::find(Interval *searchInterval)
  99 {
 100         int subnodeIndex=getSubnodeIndex(searchInterval,centre);
 101         if (subnodeIndex==-1)
 102                 return this;
 103         if (subnode[subnodeIndex]!=NULL) {
 104                 // query lies in subnode, so search it
 105                 Node *node=subnode[subnodeIndex];
 106                 return node->find(searchInterval);
 107         }
 108         // no existing subnode, so return this one anyway
 109         return this;
 110 }
 111
 112 void
 113 Node::insert(Node *node)
 114 {
 115         assert(interval==NULL || interval->contains(node->interval));
 116         int index=getSubnodeIndex(node->interval,centre);
 117         assert(index >= 0);
 118         if (node->level==level-1) {
 119                 subnode[index]=node;
 120         } else {
 121                 // the node is not a direct child, so make a new child node to contain it
 122                 // and recursively insert the node
 123                 Node* childNode=createSubnode(index);
 124                 childNode->insert(node);
 125                 subnode[index]=childNode;
 126         }
 127 }
 128
 129 /**
 130  * get the subnode for the index.
 131  * If it doesn't exist, create it
 132  */
 133 Node*
 134 Node::getSubnode(int index)
 135 {
 136         if (subnode[index]==NULL) {
 137                 subnode[index]=createSubnode(index);
 138         }
 139         return subnode[index];
 140 }
 141
 142 Node*
 143 Node::createSubnode(int index)
 144 {
 145         // create a new subnode in the appropriate interval
 146         double min=0.0;
 147         double max=0.0;
 148         switch (index) {
 149                 case 0:
 150                         min=interval->getMin();
 151                         max=centre;
 152                         break;
 153                 case 1:
 154                         min=centre;
 155                         max=interval->getMax();
 156                         break;
 157         }
 158         Interval* subInt=new Interval(min,max);
 159         Node *node=new Node(subInt,level-1);
 160         return node;
 161 }
 162
 163 } // namespace geos.index.bintree
 164 } // namespace geos.index
 165 } // namespace geos
 166
 167 /**********************************************************************
 168  * $Log$
 169  * Revision 1.3  2006/03/22 16:01:33  strk
 170  * indexBintree.h header split, classes renamed to match JTS
 171  *
 172  **********************************************************************/
 173