isort.h isort.cc

isort.h

#ifndef BTREEH

#define BTREEH


// binary tree class
class Btree
{
   public:
       // insert a pointer associated with a key into the list
       class BtNode *Insert(int key, void *iptr);
       // delete a node
       class BtNode *Delete(class BtNode *bt);
       // total number of nodes
       int  NData();
       // init list class
       Btree();
       ~Btree();

       void Loop1();
       bool Loop2();
       void Loop3();
       void *LoopVar();
#define BTFOR(x) for((x)->Loop1();(x)->Loop2();(x)->Loop3())
       // example:
       // Btree bt(2, false);
       // BTFOR(&bt)
       // {
       //     someclass *p = (someclass *)(bt.LoopVar());
       // }

       // root of bi-tree, head/tail of sorted pointer string, current loop var
       class BtNode *Root, *Head, *Tail, *loop, *loopnext;
   private:
       int nnodes;
};

// node class for binary tree
class BtNode
{
   public:
       void *ptr; // pointer to some object associated with the key
       BtNode *left, *right; // NULL at Init
       BtNode *next, *prev; //for simple string, value sorted list
       BtNode **pparent, *parent;
       int nLeft; // number of nodes uder left
       int rank;  // rank sorted by key

       //Init
       int key;
       BtNode(int key0, void *iptr);

       //Deinit
       ~BtNode();
};

#endif

isort.cc

#include "isort.h"
#include <stdio.h>
#include <stdlib.h>

// create new node
BtNode::BtNode(int key0, void *iptr)
{
   left=right=NULL;
   next=prev=NULL;
   pparent = NULL;
   parent = NULL;
   ptr = iptr;
   key = key0;
   nLeft = 0;
}

BtNode::~BtNode()
{
}


// Init tree  
Btree::Btree()
{
   nnodes=0;
   Root = Head = Tail = loop = loopnext = NULL;
}

// free all
Btree::~Btree()
{
   nnodes=0;
   Root = Head = Tail = loop = loopnext = NULL;
}

BtNode *Btree::Insert(int key0, void *iptr)
{
   // Place to add leaf
   BtNode **p = &Root;
   BtNode *parent = NULL;

   int rank = 0;

   while(*p != NULL)
   {
       parent = *p;
       if (key0 <= parent->key)
       {
	   //printf("Insert: Now[%d] vs %d going left\n", parent->key, key0);
	   p = &(parent->left);
	   parent->nLeft++;
       }
       else
       {
	   //printf("Insert: Now[%d] vs %d going right\n", parent->key, key0);
	   p = &(parent->right);
	   rank += 1+parent->nLeft;
       }
   }
   //printf("Insert: Loop end\n");

   BtNode *n = new BtNode(key0, iptr);
   n->rank = rank;
   n->pparent = p;
   n->parent = parent;
   *p = n;
   if (parent == NULL)
   {
       Head = Tail = n;
       n->prev = n->next = NULL;
   }
   else if(parent->left == n)
   {
       n->prev = parent->prev;
       n->next = parent;
       parent->prev = n;
       if(n->prev) n->prev->next = n;
       if (parent == Head) Head = n;
   }
   else if(parent->right == n)
   {
       n->next = parent->next;
       n->prev = parent;
       parent->next = n;
       if(n->next) n->next->prev = n;
       if (parent == Tail) Tail = n;
   }
   else
   {
       printf("#error left/right\n");
       exit(1);
   }
   return n;
}

BtNode *Btree::Delete(BtNode *node)
{
   BtNode **pp = node->pparent;

   //simple case
   if (node->left == NULL || node->right == NULL)
   {
       nnodes--;
       // deal simple string ptr
       if (Head == node) Head = node->next;
       if (Tail == node) Tail = node->prev;
       if (node->next) node->next->prev = node->prev;
       if (node->prev) node->prev->next = node->next;
 
	// update nLeft;
	BtNode *p = node->parent;
	BtNode *n = node;
	while(p!=NULL)
	{
	    if(p->left == n) p->nLeft--;
	    n = p;
	    p = p->parent;
	}

       //deal tree ptr
       if (node->left == NULL)
       {
           *pp = node->right;
	   if(node->right)
	   {
	       node->right->pparent =pp;
	       node->right->parent = node->parent;
	   }
       }
       else
       {
           *pp = node->left;
	   if(node->left)
	   {
	       node->left->pparent =pp;
	       node->left->parent = node->parent;
	   }
       }

       //avoid recurse
        node->left=node->right=NULL;

        delete node;
	return NULL;
   }
   else
   {
       // leftmost child of right subtree)
       // Node has two children - get max of right subtree
       BtNode *tmp = node->next;
       if(tmp->left != NULL && tmp->right !=NULL)
       {
	   exit(1);
       }
       // copy contents
       node->key = tmp->key;
       node->ptr = tmp->ptr;

       // don't touch left/right/next/prev
       Delete(tmp); //(tmp->left==NULL case will be done)

       // tree content changed. notify user affected node
       return node;
   }
}

int  Btree::NData()
{
    return nnodes;
}

void Btree::Loop1()
{
    loop = Head;
    if (loop == NULL) return;
    loopnext = loop->next;
}

bool Btree::Loop2()
{
    if (!loop) return false;
    return true;
}

void Btree::Loop3()
{
    loop = loopnext;
    if (loop) loopnext = loop->next;
}

void *Btree::LoopVar()
{
    return loop->ptr;
}