// Written by Nic Roets. This code is in the public domain.
#ifndef ARTREE_H_INCLUDED
#define ARTREE_H_INCLUDED

#define ARTREE_VERSION_MAJOR 0
#define ARTREE_VERSION_MINOR 1

template <class t> struct arnode {
  arnode<t> *parent, *left, *right;
  struct {
    int branchsize : 31;
    int red : 1;
  } s;
  t node;
};

template <class t> struct artree {
  arnode<t> *root;
  
  artree<t>(void) : root(NULL) {}
  
  void InsertBefore (arnode<t> *me, arnode<t> *_new);

  void Remove (arnode<t> *old);
  
  int Next (arnode<t> **ptr);
  /* TRUE if another element was found */
  
  int Search (arnode<t> **ptr, int referenceMinusPtr);
  /* 0: not done, 1: it does not exist, but it's neighbours has been found
     2: it has been found */
  
  arnode<t> &operator[](int i);
};

#define ArtreeSearch(tree,condition) ({ typeof (tree.root) x = tree.root; \
  while (x && !tree.Search (&x, condition)) {} x; })
/* If not found, returns the position where it should be inserted */

#define ArtreeFind(tree,condition) ({ typeof (tree.root) x = tree.root; \
  int _done; while (x && !(_done = tree.Search (&x, condition))) {} \
    _done == 2 ? x : NULL; })
/* If not found, returns NULL */

#endif