// Algoritmiek - Programming Assignment 3 - 07-05-2001 - Matthijs van Duin
// btree.h

#ifndef __btree_H__
#define __btree_H__

#include "autoref.h"
#include <iostream.h>


// note: code template classes can't really be put in a separate file
// which is why all code is in here too. (like <iostream> etc)


// ========== Comperator class ========== //
// default mechanism for comparing stuff

template<class type>
class Comperator {
public:
   static bool GT (type a, type b) { return a > b; }
   static bool LT (type a, type b) { return a < b; }
   static bool EQ (type a, type b) { return a == b; }
   static bool NE (type a, type b) { return a != b; }
};


// ========== BTree class ========== //

// forward declaration of BTree
template<class KT, class DT, class cmp> class BTree;

// A node in the B-tree
template<class KT, class DT, class cmp = Comperator<KT> >
class BTreeNode : public RefCounted {
friend class BTree<KT, DT, cmp>;
public:
   const char *ClassName() const { return "BTreeNode"; }
   
   typedef BTreeNode node;
   typedef AutoRef<node> ptr;
   
   // data accessors
   DT&  Data()   { return data; }
   KT   Key()    { return key; }
   ptr  Left()   { return left; }
   ptr  Right()  { return right; }
   
   // setting left/right must be carefully monitored, but clearing is always ok
   void ClearLeft()  { left = NULL; }
   void ClearRight() { right = NULL; }
   void ClearBoth()  { left = right = NULL; }
   
   // simple recursive functions
   ptr Leftmost()  { return left ? left->Leftmost() : ptr(&me); }
   ptr Rightmost() { return right ? right->Rightmost() : ptr(&me); }
   ptr FlatLeft()  { return left ? left->Rightmost() : ptr(NULL); }
   ptr FlatRight() { return right ? right->Leftmost() : ptr(NULL); }
   
   // lots of ways to compare stuff using standard operators
   friend bool operator == (node& x, node& y) { return cmp::EQ(x.key, y.key); }
   friend bool operator != (node& x, node& y) { return cmp::NE(x.key, y.key); }
   friend bool operator <  (node& x, node& y) { return cmp::LT(x.key, y.key); }
   friend bool operator >  (node& x, node& y) { return cmp::GT(x.key, y.key); }
   
   friend bool operator == (node& x, KT y) { return cmp::EQ(x.key, y); }
   friend bool operator != (node& x, KT y) { return cmp::NE(x.key, y); }
   friend bool operator <  (node& x, KT y) { return cmp::LT(x.key, y); }
   friend bool operator >  (node& x, KT y) { return cmp::GT(x.key, y); }
   
   friend bool operator == (KT x, node& y) { return cmp::EQ(x, y.key); }
   friend bool operator != (KT x, node& y) { return cmp::NE(x, y.key); }
   friend bool operator <  (KT x, node& y) { return cmp::LT(x, y.key); }
   friend bool operator >  (KT x, node& y) { return cmp::GT(x, y.key); }
   
   // constructors
   explicit BTreeNode(KT k) : key(k) {}
   BTreeNode() {}
   BTreeNode(KT k, DT d) : key(k), data(d) {}
   
private:
   KT    key;
   DT    data;
   ptr   left, right;
   
   // low-level find/add/delete/trace/edit/whatever primitive
   template<class W> ptr Edit(KT key, W& obj, bool (W::*proc)(ptr&));
   
   // recursive functions for walks over the tree
   template<class W> ptr WalkUp(W& obj, bool (W::*proc)(ptr));
   template<class W> ptr WalkDown(W& obj, bool (W::*proc)(ptr));
};

// The B-tree itself
template<class KT, class DT, class cmp = Comperator<KT> >
class BTree : public RefCounted {
public:
   const char *ClassName() const { return "BTree"; }
   
   typedef AutoRef<BTree> ptr;
   typedef BTreeNode<KT, DT, cmp> node;
   typedef typename node::ptr nodeptr;
   
   // high-level access
   nodeptr Find(KT key);
   nodeptr Add(typename node::ptr item);
   nodeptr Remove(KT key);       // remove node and children
   nodeptr RemoveShift(KT key);  // remove node and shift child into its place
   void RemoveUp(KT key);        // remove nodes greater than key
   
   // various walks over the tree
   template<class W> nodeptr WalkUp(W& obj, bool (W::*proc)(nodeptr));
   template<class W> nodeptr WalkDown(W& obj, bool (W::*proc)(nodeptr));
   template<class W> void Lindstrom(W& obj, void (W::*proc)(nodeptr));
   
   nodeptr Root() { return root; }
   
protected:
   // low-level find/add/delete/trace/edit/whatever primitive
   template<class W> nodeptr Edit(KT key, W& obj, bool (W::*proc)(nodeptr&));
   
private:
   nodeptr   root;
   
   // helper classes for editing the tree.
   
   // NoHelper doesn't help in any way, except by doing nothing.
   class NoHelper {
   public:
      bool proc(nodeptr&) { return false; }
   };
   
   // AddHelper adds the node at an empty spot
   class AddHelper {
   public:
      nodeptr add;
      AddHelper(nodeptr node) : add(node) {}
      bool proc(nodeptr& node) { return !node && (node = add); }
   };
   
   // RemoveHelper removes the node specified
   class RemoveHelper {
   public:
      KT key;
      nodeptr found;
      RemoveHelper(KT k) : key(k) {}
      bool proc(nodeptr& node)  {
         if (node && *node == key) {
            found = node;
            node = NULL;
            return true;
         }
         return false;
      }
   };
   
   // RemoveShiftHelper removes the node specified and shifts one child into
   // its place. (if node has two children, leaves one attached to the node)
   class RemoveShiftHelper {
   public:
      KT key;
      nodeptr found;
      RemoveShiftHelper(KT k) : key(k) {}
      bool proc(nodeptr& node)  {
         if (node && *node == key) {
            found = node;
            if (node->Left())
               node = node->Left(), found->ClearLeft();
            else if (node->Right())
               node = node->Right(), found->ClearRight();
            else
               node = NULL;
            return true;
         }
         return false;
      }
   };
   
   // RemoveUpHelper removes all nodes greater than specified key
   class RemoveUpHelper {
   public:
      KT key;
      RemoveUpHelper(KT k) : key(k) {}
      bool proc(nodeptr& node)  {
         Tracer tracer("BTree::RemoveUpHelper::proc");
         if (node) {
            if (*node == key)
               return node->ClearRight(), true;
            else if (*node > key)
               return node = node->Left(), proc(node);
         }
         return false;
      }
   };
};


// ======= BTreeNode recursive functions ======= //

// universal multi-purpose generic recursive subtree editing function:
// searches towards specified key, does a callback to obj.*proc for
// each node, including the NULL at the end if node isn't found.
template<class KT, class DT, class cmp> template<class W> typename BTreeNode<KT,
DT, cmp>::ptr BTreeNode<KT, DT, cmp>::Edit(KT key, W& obj, bool (W::*proc)(
typename BTreeNode<KT, DT, cmp>::ptr&)) {
   Tracer tracer("BTreeNode::Edit");
   if (me == key)
      return &me;
   else if (me > key)
      return (obj.*proc)(left) || !left ? left : left->Edit(key, obj, proc);
   else
      return (obj.*proc)(right) || !right ? right : right->Edit(key, obj, proc);
}

// Walks through the subtree, visiting the nodes in incremental order.
// Calls obj.*proc for each node visited.
template<class KT, class DT, class cmp> template<class W> typename BTreeNode<KT,
DT, cmp>::ptr BTreeNode<KT, DT, cmp>::WalkUp(W& obj, bool (W::*proc)(typename
BTreeNode<KT, DT, cmp>::ptr)) {
   Tracer tracer("BTreeNode::WalkUp");
   ptr temp;
   if (left && (temp = left->WalkUp(obj, proc)))
      return temp;
   if ((obj.*proc)(&me))
      return &me;
   if (right && (temp = right->WalkUp(obj, proc)))
      return temp;
   return NULL;
}

// Walks through the subtree, visiting the nodes in decremental order.
// Calls obj.*proc for each node visited.
template<class KT, class DT, class cmp> template<class W> typename BTreeNode<KT,
DT, cmp>::ptr BTreeNode<KT, DT, cmp>::WalkDown(W& obj, bool (W::*proc)(typename
BTreeNode<KT, DT, cmp>::ptr)) {
   Tracer tracer("BTreeNode::WalkDown");
   ptr temp;
   if (right && (temp = right->WalkUp(obj, proc)))
      return temp;
   if ((obj.*proc)(&me))
      return &me;
   if (left && (temp = left->WalkUp(obj, proc)))
      return temp;
   return NULL;
}


// ======= BTree high-level access functions ======= //

// Find node with specified key, returns NULL if not found.
template<class KT, class DT, class cmp> typename BTreeNode<KT, DT, cmp>::ptr
BTree<KT, DT, cmp>::Find(KT key) {
   Tracer tracer("BTree::Find");
   NoHelper helper;
   return Edit(key, helper, &NoHelper::proc);
}

// Add specified node and return it. If tree already contains a node with the
// same key, it is returned instead.
template<class KT, class DT, class cmp> typename BTreeNode<KT, DT, cmp>::ptr
BTree<KT, DT, cmp>::Add(typename BTreeNode<KT, DT, cmp>::ptr node) {
   Tracer tracer("BTree::Add");
   AddHelper helper(node);
   return Edit(node->Key(), helper, &AddHelper::proc);
}

// Remove node with specified key from the tree and returns it, with its
// descendents still attached. Returns NULL if the node is not found.
template<class KT, class DT, class cmp> typename BTreeNode<KT, DT, cmp>::ptr
BTree<KT, DT, cmp>::Remove(KT key) {
   Tracer tracer("BTree::Remove");
   RemoveHelper helper(key);
   Edit(key, helper, &RemoveHelper::proc);
   return helper.found;
}

// Remove node with specified key from the tree and returns it. If the removed
// node has one child, it is shifted up, replacing the removed node. If it has
// two children, the left one is shifted up and the right one remains attached
// to the removed node.
template<class KT, class DT, class cmp> typename BTreeNode<KT, DT, cmp>::ptr
BTree<KT, DT, cmp>::RemoveShift(KT key) {
   Tracer tracer("BTree::RemoveShift");
   RemoveShiftHelper helper(key);
   Edit(key, helper, &RemoveShiftHelper::proc);
   return helper.found;
}

// Remove all nodes greater than specified key.
template<class KT, class DT, class cmp> void BTree<KT, DT, cmp>::RemoveUp(KT
key) {
   Tracer tracer("BTree::RemoveUp");
   RemoveUpHelper helper(key);
   Edit(key, helper, &RemoveUpHelper::proc);
}


// ======= BTree iteration functions ======= //

// Walks through the tree, visiting the nodes in incremental order.
// Calls obj.*proc for each node visited.
template<class KT, class DT, class cmp> template<class W> typename BTreeNode<KT,
DT, cmp>::ptr BTree<KT, DT, cmp>::WalkUp(W& obj, bool (W::*proc)(typename
BTreeNode<KT, DT, cmp>::ptr)) {
   Tracer tracer("BTree::WalkUp");
   if (root)
      return root->WalkUp(obj, proc);
   return NULL;
}

// Walks through the tree, visiting the nodes in incremental order.
// Calls obj.*proc for each node visited.
template<class KT, class DT, class cmp> template<class W> typename BTreeNode<KT,
DT, cmp>::ptr BTree<KT, DT, cmp>::WalkDown(W& obj, bool (W::*proc)(typename
BTreeNode<KT, DT, cmp>::ptr)) {
   Tracer tracer("BTree::WalkDown");
   if (root)
      return root->WalkDown(obj, proc);
   return NULL;
}

// universal multi-purpose generic recursive tree editing function:
// searches towards specified key, does a callback to obj.*proc for each node,
// including the NULL at the end if node isn't found.
template<class KT, class DT, class cmp> template<class W> typename BTreeNode<KT,
DT, cmp>::ptr BTree<KT, DT, cmp>::Edit(KT key, W& obj, bool (W::*proc)(typename
BTreeNode<KT, DT, cmp>::ptr&)) {
   Tracer tracer("BTree::Edit");
   return ((obj.*proc)(root) || !root) ? root : root->Edit(key, obj, proc);
}

// Walks through the tree using the Lindstrom algormitm.
// Calls obj.*proc for each node visited.
template<class KT, class DT, class cmp> template<class W> void BTree<KT, DT,
cmp>::Lindstrom(W& obj, void (W::*proc)(typename BTreeNode<KT, DT, cmp>::ptr)) {
   Tracer tracer("BTree::Lindstrom");
   register nodeptr head = new node;
   register nodeptr p = root, q = head, tmp;
   
   if (!p)  // no tree to walk
      return;
   
   do {
      if (p)
         tmp = p->left, p->left = p->right, p->right = q, q = p, p = tmp;
      else
         tmp = p, p = q->left, q->left = q->right, q->right = tmp;
      
      (obj.*proc)(q);
      
   } while (p != head);
}

#endif // __btree_H__