src/index/bintree/Bintree.cpp

   1 /**********************************************************************
   2  *
   3  * GEOS - Geometry Engine Open Source
   4  * http://geos.osgeo.org
   5  *
   6  * Copyright (C) 2006 Refractions Research Inc.
   7  * Copyright (C) 2001-2002 Vivid Solutions Inc.
   8  *
   9  * This is free software; you can redistribute and/or modify it under
  10  * the terms of the GNU Lesser General Public Licence as published
  11  * by the Free Software Foundation.
  12  * See the COPYING file for more information.
  13  *
  14  **********************************************************************/
  15
  16 #include <cstddef>
  17 #include <geos/index/bintree/Bintree.h>
  18 #include <geos/index/bintree/Root.h>
  19 #include <geos/index/bintree/Interval.h>
  20 #include <vector>
  21
  22 namespace geos {
  23 namespace index { // geos.index
  24 namespace bintree { // geos.index.bintree
  25
  26 using namespace std;
  27
  28 Interval*
  29 Bintree::ensureExtent(const Interval* itemInterval, double minExtent)
  30 {
  31         double min = itemInterval->getMin();
  32         double max = itemInterval->getMax();
  33         // has a non-zero extent
  34         if (min != max)
  35         {
  36                 // GEOS forces a copy here to be predictable wrt
  37                 // memory management. May change in the future.
  38                 return new Interval(*itemInterval);
  39         }
  40
  41         // pad extent
  42         if (min==max)
  43         {
  44                 min = min-minExtent/2.0;
  45                 max = min+minExtent/2.0;
  46         }
  47
  48         return new Interval(min, max);
  49 }
  50
  51
  52
  53 Bintree::Bintree()
  54 {
  55         minExtent=1.0;
  56         root=new Root();
  57 }
  58
  59 Bintree::~Bintree()
  60 {
  61         for (unsigned int i=0; i<newIntervals.size(); i++)
  62                 delete newIntervals[i];
  63         delete root;
  64 }
  65
  66 int
  67 Bintree::depth()
  68 {
  69         if (root!=NULL) return root->depth();
  70         return 0;
  71 }
  72
  73 int
  74 Bintree::size()
  75 {
  76         if (root!=NULL) return root->size();
  77         return 0;
  78 }
  79
  80 /**
  81  * Compute the total number of nodes in the tree
  82  *
  83  * @return the number of nodes in the tree
  84  */
  85 int
  86 Bintree::nodeSize()
  87 {
  88         if (root!=NULL) return root->nodeSize();
  89         return 0;
  90 }
  91
  92 void
  93 Bintree::insert(Interval *itemInterval,void* item)
  94 {
  95         collectStats(itemInterval);
  96         Interval *insertInterval=ensureExtent(itemInterval,minExtent);
  97         if ( insertInterval != itemInterval )
  98                 newIntervals.push_back(insertInterval);
  99         //int oldSize=size();
 100         root->insert(insertInterval,item);
 101
 102         /* GEOS_DEBUG
 103         int newSize=size();
 104         System.out.println("BinTree: size="+newSize+"   node size="+nodeSize());
 105         if (newSize <= oldSize) {
 106         System.out.println("Lost item!");
 107         root.insert(insertInterval, item);
 108         System.out.println("reinsertion size="+size());
 109         }
 110         */
 111 }
 112
 113 vector<void*>* Bintree::iterator() {
 114         vector<void*>* foundItems=new vector<void*>();
 115         root->addAllItems(foundItems);
 116         return foundItems;
 117 }
 118
 119 vector<void*>* Bintree::query(double x) {
 120         return query(new Interval(x, x));
 121 }
 122
 123 /**
 124 * min and max may be the same value
 125 */
 126 vector<void*>* Bintree::query(Interval *interval) {
 127         /**
 128         * the items that are matched are all items in intervals
 129         * which overlap the query interval
 130         */
 131         vector<void*>* foundItems=new vector<void*>();
 132         query(interval,foundItems);
 133         return foundItems;
 134 }
 135
 136 void
 137 Bintree::query(Interval *interval,vector<void*> *foundItems)
 138 {
 139         root->addAllItemsFromOverlapping(interval,foundItems);
 140 }
 141
 142 void
 143 Bintree::collectStats(Interval *interval)
 144 {
 145         double del=interval->getWidth();
 146         if (del<minExtent && del>0.0)
 147                 minExtent=del;
 148 }
 149
 150 } // namespace geos.index.bintree
 151 } // namespace geos.index
 152 } // namespace geos
 153
 154 /**********************************************************************
 155  * $Log$
 156  * Revision 1.13  2006/03/22 16:01:33  strk
 157  * indexBintree.h header split, classes renamed to match JTS
 158  *
 159  **********************************************************************/
 160