Interval Trees

Figure 3: The interval tree template class itree

#ifndef ITREE_H_
#define ITREE_H_
#include <vector>
#include <set>
#include <assert.h>
#include <algorithm>
#include <iterator>

template<class T, class A = std::allocator<T> > class itree 
{
public:
   typedef T                                 invl_type;
   typedef T::range_type                     range_type;
   typedef std::vector<invl_type, A>         invl_vec;

   typedef invl_vec::iterator                iterator;
   typedef invl_vec::const_iterator          const_iterator;
   // other types derived from invl_vec omitted
   ...

private:
   typedef struct node_tag       // Interval tree nodes
   {
      range_type      discrim;  // discriminant
      int             start;    // starting offset in AL and DH
      int             size;     // number of entris in AL and DH
      struct node_tag *left;    // left subtree
      struct node_tag *right;   // right subtree
   } node;

public:
   ... // query iterator definition omitted
   ... // functions forwarded to std::vector omitted
   // Interval tree specific functionality follows

   itree() : root(NULL) {}
   ~itree() { deconstruct(); }

   void deconstruct(void) // reverts initialization mode
   { delete_tree(root);  root = NULL; }

   void delete_tree(node *cur_node) {  // delete nodes in tree
      if (cur_node != NULL) {
         delete_tree(cur_node->left);    // left tree 
                                         //  recursively
         delete_tree(cur_node->right);   // right tree 
                                         //  recursively
         delete cur_node;
     }
   }

   bool constructed() const { return root != NULL; }

   // build the interval tree structure and
   // put the container into query mode
   itree const& construct(void) {
      std::vector<range_type> values;
      std::vector<bool>       flags(invls.size(), false);
      int                     num_al_dh = 0;

      extract_values(values);   
      al.resize(invls.size());
      dh.resize(invls.size());
      root = construct_tree(values, flags, num_al_dh, 0, 
                            values.size() - 1);
      return *this;
   }
   ... // extract_values function definition omitted
   // recursively construct the tree
   node* 
   construct_tree(const std::vector<range_type>& values, 
      std::vector<bool>& flags, int& num_al_dh,
      int start, int end) {
      int         discrim_pos;
      range_type  discrim;
      int         list_start, list_size;
      node        *root, *left, *right;
      bool        continue_left = false;
      bool        continue_right = false;

      root = left = right = NULL;
      if (start > end)
         return root;
      discrim_pos = (start + end) / 2;
      discrim = values[discrim_pos];
 
      list_start = num_al_dh;
      list_size = 0;
      for (int i = 0; i < invls.size(); i++) {
         if (flags[i])
            continue;

         if ((invls[i].low() <= discrim) && 
             (invls[i].high() >= discrim)) {

            al[num_al_dh] = &(invls[i]);
            dh[num_al_dh] = &(invls[i]);

            num_al_dh++;
            list_size++;
            flags[i] = true;
         }

         if ((invls[i].low() < discrim) && 
             (invls[i].high() < discrim))
            continue_left = true;

          if ((invls[i].low() > discrim) && 
              (invls[i].high() > discrim))

            continue_right = true;
      }

      // see if left and/or right subtree needs to be built
      if (continue_left && (start <= (discrim_pos - 1)))
         left = construct_tree(values, flags, num_al_dh, start, 
                   discrim_pos - 1);

      if (continue_right && ((discrim_pos + 1) <= end))
         right = construct_tree(values, flags, num_al_dh, 
                    discrim_pos + 1, end);

      // this node is needed only if thre are entries in the 
      // AL/DH list or the left or right subtree exists.
      if ((list_size > 0) || (left != NULL) || (right != NULL)) {
         std::sort(&(al[list_start]), 
            &(al[list_start + list_size]), comp_for_al);
         std::sort(&(dh[list_start]), 
            &(dh[list_start + list_size]), comp_for_dh);

         root = new node;
         root->left = left;
         root->right = right;
         root->discrim = discrim;
         root->start = list_start;
         root->size = list_size;
      }
      return root;
   }

   ... // comparison functions for sorting AL and DL omitted

   query_iterator qbegin(range_type x) { 
      assert(constructed());
      query_iterator it(root, 0, x, &al, &dh); 
      it.init_node(); return it; 
   }

   query_iterator qend(range_type x) { 
      assert(constructed());
      query_iterator  it(NULL, 0, x, NULL, NULL); 
      return it; 
   }

private:
   invl_vec                invls;  // vector of intervals
   std::vector<invl_type*> al, dh; // vectors of interval ptrs
   node                    *root;  // Interval tree root node
};
#endif    // ITREE_H_