Interval Trees

Figure 5: The query_iterator class

template<class T, class A = std::allocator<T> > class itree 
{
public:
   class query_iterator : public 
      std::iterator<std::forward_iterator_tag, itree> {
   public:
      ... // constructors and operator*() omitted 

      query_iterator& operator++(void)  // prefix 
      { Increment(); return *this; }  

      query_iterator operator++(int)  // postfix
      { query_iterator it(*this); Increment(); return it; }

      const T* operator->() const { 
         if (cur_node->discrim >= value)
            return (*p_al)[cur_node->start + index]; 
         else
           return (*p_dh)[cur_node->start + index]; 
      }

      bool operator!=(query_iterator& it) const 
      { return !(*this == it); }

      bool operator==(query_iterator& it) const { 
         return (value == it.value) && 
            (cur_node == it.cur_node) && (index == it.index);
      }

   private:
      node*                   cur_node;
      int                     index;
      std::vector<invl_type*> *p_al, *p_dh;
      range_type              value;

      query_iterator(node* cur_node, int index, range_type value,
         std::vector<invl_type*> *p_al, 
         std::vector<invl_type*> *p_dh) 
         : cur_node(cur_node), index(index), value(value), 
           p_al(p_al), p_dh(p_dh) {} // private constructor

      void Increment(void) {
         index++;
         if (index == cur_node->size) {
            if (cur_node->discrim == value) { // finished!
               cur_node = NULL;
               index = 0;
               return;
            }
            else if (cur_node->discrim > value)
               cur_node = cur_node->left;
            else
               cur_node = cur_node->right;
            init_node();
            return;
         }
         if (cur_node->discrim > value) {
            if ((*p_al)[cur_node->start + index]->low() <= value)
               return;
            else
               cur_node = cur_node->left;
         }
         else if (cur_node->discrim < value) {
            if((*p_dh)[cur_node->start + index]->high() >= value)
               return;
            else
               cur_node = cur_node->right;
         }
         else  //(cur_node->discrim == value)
            return;
         init_node();
         return;
      }

      void init_node(void) {
         index = 0;        
         while (cur_node != NULL) {
            if (value < cur_node->discrim) {
               if ((cur_node->size != 0) &&
                   ((*p_al)[cur_node->start]->low() <= value))
                  return;
               else
                  cur_node = cur_node->left;
            }
            else if (value > cur_node->discrim) {
               if ((cur_node->size != 0) && 
                   ((*p_dh)[cur_node->start]->high() >= value))
                  return;
               else
                  cur_node = cur_node->right;
            }
            else //(value == cur_node->discrim)
               return;
         }
      }

      friend itree;  // allow itree to use private constructor
   };    // end of query_iterator definition
   ... // remiander of itree definition omitted
};  // end of itree definition