1                 : /*
       2                 :  * $Id: KDTree.h 5866 2005-10-25 21:13:32Z dfs $
       3                 :  *
       4                 :  * Copyright 2003-2005 Daniel F. Savarese
       5                 :  * Copyright 2005 Savarese Software Research
       6                 :  *
       7                 :  * Licensed under the Apache License, Version 2.0 (the "License");
       8                 :  * you may not use this file except in compliance with the License.
       9                 :  * You may obtain a copy of the License at
      10                 :  *
      11                 :  *     https://www.savarese.com/software/ApacheLicense-2.0
      12                 :  *
      13                 :  * Unless required by applicable law or agreed to in writing, software
      14                 :  * distributed under the License is distributed on an "AS IS" BASIS,
      15                 :  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
      16                 :  * See the License for the specific language governing permissions and
      17                 :  * limitations under the License.
      18                 :  */
      19                 : 
      20                 : #ifndef __SAVA_SPATIAL_KDTREE_DETAIL_H
      21                 : #define __SAVA_SPATIAL_KDTREE_DETAIL_H
      22                 : 
      23                 : #include <cstring>
      24                 : #include <iterator>
      25                 : #include <stack>
      26                 : 
      27                 : #include <libsava/packages.h>
      28                 : 
      29                 : __BEGIN_PACKAGE_SAVA_SPATIAL
      30                 : 
      31                 : namespace detail {
      32                 : 
      33                 :   template<typename TreeTraits>
      34                 :   class KDTreeNode {
      35                 :   public:
      36                 :     // Convention we use is that values < discriminator are in low
      37                 :     // subtree and those >= are in high subtree.
      38                 :     enum Child { ChildLow = 0, ChildHigh = 1 };
      39                 :     typedef Child child_type;
      40                 : 
      41                 :     typedef TreeTraits traits;
      42                 :     typedef typename traits::key_type key_type;
      43                 :     typedef typename traits::mapped_type mapped_type;
      44                 :     typedef typename traits::value_type value_type;
      45                 :     typedef typename traits::pointer pointer;
      46                 :     typedef typename traits::const_pointer const_pointer;
      47                 :     typedef typename traits::reference reference;
      48                 :     typedef typename traits::const_reference const_reference;
      49                 :     typedef typename traits::discriminator_type discriminator_type;
      50                 :     typedef typename traits::node_type node_type;
      51                 : 
      52                 :   private:
      53                 :     static const unsigned int NumChildren = 2;
      54                 : 
      55                 :     discriminator_type _discriminator;
      56                 :     value_type _pair;
      57                 :     node_type *_children[NumChildren];
      58                 : 
      59                 :   public:
      60                 : 
      61                 :     KDTreeNode(const discriminator_type discriminator,
      62          294914 :                const key_type & point, const mapped_type & value) :
      63          294914 :       _discriminator(discriminator), _pair(point,value)
      64                 :     {
      65          294914 :       std::memset(_children, 0, sizeof(_children));
      66                 :     }
      67                 : 
      68          294914 :     ~KDTreeNode() {
      69          294914 :       delete _children[ChildLow];
      70          294914 :       delete _children[ChildHigh];
      71                 :     }
      72                 : 
      73        10788077 :     discriminator_type & discriminator() {
      74        10788077 :       return _discriminator;
      75                 :     }
      76                 : 
      77        34679732 :     const key_type & point() const {
      78        34679732 :       return _pair.first;
      79                 :     }
      80                 : 
      81          294926 :     mapped_type & value() {
      82          294926 :       return _pair.second;
      83                 :     }
      84                 : 
      85                 :     const mapped_type & value() const {
      86                 :       return _pair.second;
      87                 :     }
      88                 : 
      89          229382 :     reference pair() {
      90          229382 :       return _pair;
      91                 :     }
      92                 : 
      93                 :     const_reference pair() const {
      94                 :       return _pair;
      95                 :     }
      96                 : 
      97        15771317 :     node_type* & child(const Child child) {
      98        15771317 :       return _children[child];
      99                 :     }
     100                 :   };
     101                 : 
     102                 :   template<typename TreeTraits>
     103                 :   class KDTreeRangeSearchIterator :
     104                 :     public
     105                 :     std::iterator<std::forward_iterator_tag,typename TreeTraits::value_type>
     106          229434 :   {
     107                 :   public:
     108                 :     typedef TreeTraits traits;
     109                 :     typedef typename traits::node_type node_type;
     110                 :     typedef typename traits::key_type key_type;
     111                 :     typedef typename traits::value_type value_type;
     112                 :     typedef typename traits::pointer pointer;
     113                 :     typedef typename traits::reference reference;
     114                 :     typedef typename traits::discriminator_type discriminator_type;
     115                 : 
     116                 :   private:
     117                 :     friend class traits::const_iterator;
     118                 :     friend class traits::tree_type;
     119                 : 
     120                 :     node_type *_node;
     121                 :     key_type _lower, _upper;
     122                 :     std::stack<node_type *> _stack;
     123                 :     discriminator_type _discriminator;
     124                 : 
     125           32776 :     void advance() {
     126           65552 :       while(!_stack.empty()) {
     127           32774 :         node_type *node = _stack.top();
     128           32774 :         _stack.pop();
     129                 : 
     130           32774 :         _discriminator = node->discriminator();
     131                 : 
     132                 :         // <= instead of < because values >= are in right subtree.
     133           32774 :         if(node->point()[_discriminator] <= _upper[_discriminator] &&
     134                 :            node->child(node_type::ChildHigh) != 0)
     135           16413 :           _stack.push(node->child(node_type::ChildHigh));
     136                 : 
     137                 :         // Push left subtree last so that it will be searched first
     138           32774 :         if(node->point()[_discriminator] > _lower[_discriminator] &&
     139                 :            node->child(node_type::ChildLow) != 0)
     140           16353 :           _stack.push(node->child(node_type::ChildLow));
     141                 : 
     142           32774 :         if(isContained(node->point(), _lower, _upper)) {
     143           32774 :           _node = node;
     144           32774 :           return;
     145                 :         }
     146                 :       }
     147               2 :       _node = 0;
     148                 :     }
     149                 : 
     150          131074 :     void advanceToLower() {
     151         2168660 :       while(!_stack.empty()) {
     152         2037586 :         node_type *node = _stack.top();
     153         2037586 :         _stack.pop();
     154                 : 
     155         2037586 :         _discriminator = node->discriminator();
     156                 : 
     157                 :         // <= instead of < because values >= are in right subtree.
     158         2037586 :         if(node->point()[_discriminator] <= _upper[_discriminator] &&
     159                 :            node->child(node_type::ChildHigh) != 0)
     160         1900229 :           _stack.push(node->child(node_type::ChildHigh));
     161                 : 
     162                 :         // Push left subtree last so that it will be searched first.
     163         2037586 :         if(node->point()[_discriminator] > _lower[_discriminator] &&
     164                 :            node->child(node_type::ChildLow) != 0)
     165          914244 :           _stack.push(node->child(node_type::ChildLow));
     166                 : 
     167         2037586 :         if(node->point() == _lower) {
     168          131074 :           _node = node;
     169          131074 :           return;
     170                 :         }
     171                 :       }
     172               0 :       _node = 0;
     173                 :     }
     174                 : 
     175                 :   public:
     176                 :     // For now, we rely on default assignment operator and for
     177                 :     // const_iterator the default copy constructor.  They are
     178                 :     // unacceptable only if Discriminator or Point types allocate and
     179                 :     // destroy memory referenced by pointers, which for now we forbid.
     180                 : 
     181           32804 :     KDTreeRangeSearchIterator() :
     182           32804 :       _node(0), _lower(), _upper(), _stack(), _discriminator()
     183           32804 :     { }
     184                 : 
     185                 :     // Copy constructor to allow const_iterator to be created from iterator
     186           32772 :     KDTreeRangeSearchIterator(const typename traits::iterator & rsi) :
     187                 :       _node(rsi._node), _lower(rsi._lower), _upper(rsi._upper),
     188           32772 :       _stack(rsi._stack), _discriminator(rsi._discriminator)
     189                 :       { }
     190                 : 
     191                 :     KDTreeRangeSearchIterator(const key_type & lower, const key_type & upper,
     192          131086 :                               node_type* const root, bool find = false) :
     193          131086 :       _node(root), _lower(lower), _upper(upper), _stack(), _discriminator()
     194                 :     {
     195          131086 :       if(_node != 0) {
     196          131082 :         _stack.push(_node);
     197          131082 :         if(!find)
     198               8 :           advance();
     199                 :         else
     200          131074 :           advanceToLower();
     201                 :       }
     202                 :     }
     203                 : 
     204                 :     bool endOfRange() const {
     205                 :       return (_node == 0);
     206                 :     }
     207                 : 
     208           65536 :     reference operator*() {
     209           65536 :       return _node->pair();
     210                 :     }
     211                 : 
     212          163846 :     pointer operator->() {
     213          163846 :       return &(_node->pair());
     214                 :     }
     215                 : 
     216           32768 :     KDTreeRangeSearchIterator & operator++() {
     217           32768 :       advance();
     218           32768 :       return *this;
     219                 :     }
     220                 : 
     221                 :     KDTreeRangeSearchIterator operator++(int) {
     222                 :       KDTreeRangeSearchIterator old(*this);
     223                 :       advance();
     224                 :       return old;
     225                 :     }
     226                 : 
     227               4 :     bool operator==(const KDTreeRangeSearchIterator & rsi) const {
     228               4 :       return (_node == rsi._node);
     229                 :     }
     230                 : 
     231           98308 :     bool operator!=(const KDTreeRangeSearchIterator & rsi) const {
     232           98308 :       return (_node != rsi._node);
     233                 :     }
     234                 :   };
     235                 : 
     236                 : }
     237                 : 
     238                 : __END_PACKAGE_SAVA_SPATIAL
     239                 : 
     240                 : #endif