Quad Tree

QuadTree.h

//
//  QuadTree.h
//
//  Created by Sid on 24/01/14.
//  Copyright (c) 2014 whackylabs. All rights reserved.
//

#ifndef QuadTree_h
#define QuadTree_h

//#define ENABLE_FRAGMENTED_HEAP

#if defined (ENABLE_FRAGMENTED_HEAP)
template <typename T>
struct QuadNode {
  
  QuadNode(const T &v) :
  value(v)
  {
    for (int i = 0; i < 4; ++i) {
      neighbors[i] = NULL;
    }
  }
  
  static QuadNode<T> *Create(const T&v)
  {
    return new QuadNode<T>(v);
  }
  
  ~QuadNode()
  {
    for (int i = 0; i < 4; ++i) {
      if (neighbors[i]) {
        delete neighbors[i];
      }
    }
  }
  
  T value;
  QuadNode<T> *neighbors[4]; /* pointer to four quadrants */
};

#else 

template <typename T>
struct QuadNode {

  void Clear()
  {
    for (int i = 0; i < 4; ++i) {
      neighbors[i] = NULL;
    }
  }

  void Init(const T &v)
  {
    value = v;
    for (int i = 0; i < 4; ++i) {
      neighbors[i] = NULL;
    }
  }
  
  T value;
  QuadNode<T> *neighbors[4]; /* pointer to four quadrants */
};

template <typename T>
class QuadNodeAllocator {
public:
  
  QuadNodeAllocator() :
  nodes(new QuadNode<T>[1000000]), /* maximum nodes possible */
  node_index(0)
  {}

  ~QuadNodeAllocator()
  {
    delete [] nodes;
  }
  
  /* Clear all the nodes data and reset node_index to 0 */
  void Reset()
  {
    while (node_index) {
      nodes[--node_index].Clear();
    }
    assert(node_index == 0);
  }

  /* Return an address to next available node */
  QuadNode<T> *Create(const T &v)
  {
    assert(node_index < 1000000);
    
    QuadNode<T> *p = &nodes[node_index++];
    p->Init(v);
    return p;
  }
  
private:
  QuadNode<T> *nodes;
  unsigned int node_index;
};

/* Allocate memory for all nodes at start up
 * and reuse them till the app quits.
 */
template <typename T>
QuadNodeAllocator<T> &QuadNodeAllocatorInstance()
{
  static QuadNodeAllocator<T> q_allocator;
  return q_allocator;
}
#endif

/** QuadTree 
 * T is the type of the data
 * QF is a functor that should return a value as:
 * range (0, 3) which is the quadrant number where the new node should be inserted
 *      +y
 *    1 | 0
 * +x --+-- -x
 *    2 | 3
 *      -y
 *
 * or -1 for duplicate value or where insertion is not possible
 *
 * A typical implementation should be like:
 *
 * template <typename T> struct PointQuadrant {
 *  PointQuadrant(const Point<T> &b) :
 *  two(b)
 *  {}
 *
 *  int operator()(Point<T> &one)
 *  {
 *   if (one == two) {
 *    return -1;
 *   }
 *
 *   if (two.x < one.x) {
 *    return (two.y < one.y) ? 3 : 0;
 *   }
 *   return (two.y < one.y) ? 2 : 1;
 *  }
 *
 *   Point<T> two;
 * };
 *
 */
template <typename T, typename QF>
class QuadTree {
public:
  QuadTree() : root(NULL)
  {}
  
  ~QuadTree()
  {
#if defined (ENABLE_FRAGMENTED_HEAP)

    if (root) {
      delete root;
    }
    
#else
    QuadNodeAllocatorInstance<T>().Reset();
#endif
    root = NULL;
  }
  
  bool Insert(const T &val) {
#if defined (ENABLE_FRAGMENTED_HEAP)
    QuadNode<T> *node = QuadNode<T>::Create(val);
#else
    QuadNode<T> *node = QuadNodeAllocatorInstance<T>().Create(val);
#endif
    if (!root) {
      root = node;
      return true;
    }
    
    QF qf(node->value);
    
    QuadNode<T> *curr = root;
    int q = -1;
    while ((q = qf(curr->value)) >= 0) {
      QuadNode<T> *next = curr->neighbors[q];
      if (!next) {
        curr->neighbors[q] = node;
        return true;
      } else {
        curr = next;
      }
    }
    
    return false;
  }
  
private:
  QuadNode<T> *root;
};


#endif