rbtqueue.cpp

Go to the documentation of this file.

// red black tree
/* Derived from
http://ciips.ee.uwa.edu.au/~morris/Year2/PLDS210/niemann/s_man.htm
Sorting and Searching Algorithms:
A Cookbook
by
Thomas Niemann
*/
/* The original c code is enclosed in #if 0 and the original functions
are given the class name RBTQueue (which is defined as TQueue)
whereas my own analogous class methods to the old TQueue have the same name
*/

/* red-black tree */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdarg.h>


#if 0
typedef int T;                  /* type of item to be stored */
#else
typedef double T;
#endif

#define compLT(a,b) (a < b)
#define compEQ(a,b) (a == b)

#if 0
/* Red-Black tree description */
typedef enum { BLACK, RED } nodeColor;
#endif

#if 0
typedef struct Node_ {
    struct Node_ *left;         /* left child */
    struct Node_ *right;        /* right child */
    struct Node_ *parent;       /* parent */
    nodeColor color;            /* node color (BLACK, RED) */
    T data;                     /* data stored in node */
} Node;
#else
#define left left_
#define right right_
#define parent parent_
#define Node TQItem
#define data t_
#define color red_
#define BLACK false
#define RED true
#define root root_
#endif

#if 0
#define NIL &sentinel           /* all leafs are sentinels */
Node sentinel = { NIL, NIL, 0, BLACK, 0};
Node *root = NIL;               /* root of Red-Black tree */

#else

#undef NIL
#define NIL sentinel
static TQItem* sentinel;
#endif

TQItem::TQItem() {
    left_ = NIL;
    right_ = NIL;
    parent_ = nil;
}

TQItem::~TQItem() {
    assert(this != NIL);
}

static void deleteitem(TQItem* i) {
    assert(i != NIL);
    if (i->left_ && i->left != NIL) {
        deleteitem(i->left_);
    }
    if (i->right_ && i->right != NIL) {
        deleteitem(i->right_);
    }
    i->left_ = nil;
    i->right_ = nil;
    tpool_->free(i);
}

bool TQItem::check() {
#if DOCHECK
#endif
    return true;
}

static void prnt(const TQItem* b, int level) {
    int i;
    for (i=0; i < level; ++i) {
        Printf("    ");
    }
//  printf("%g %c %d\n", b->t_, b->data_?'x':'o', b->red_);
    Printf("%g %c %d Q=%p D=%p\n", b->t_, b->data_?'x':'o', b->red_, b, b->data_);
}

static void chk(TQItem* b, int level) {
    if (!b->check()) {
        hoc_execerror("chk failed", errmess_);
    }
}

void TQItem::t_iterate(void (*f)(const TQItem*, int), int level) {
    if (left_ && left_ != NIL) {
        left_->t_iterate(f, level+1);
    }
    f(this, level);
    if (right_ && right_ != NIL) {
        right_->t_iterate(f, level+1);
    }
}
        
TQueue::TQueue() {
    if (!sentinel) {
        sentinel = new TQItem();
        sentinel->red_ = BLACK;
        sentinel->t_ = 0.;
        sentinel->data_ = nil;
        sentinel->left_ = NIL;
        sentinel->right_ = NIL;
    }
    if (!tpool_) {
        tpool_ = new TQItemPool(1000);
    }
    root_ = NIL;
    least_ = NIL;

#if COLLECT_TQueue_STATISTICS
    nmove = ninsert = nrem = nleast = nbal = ncmplxrem = 0;
    nfastmove = ncompare = nleastsrch = nfind = nfindsrch = 0;
#endif
}

TQueue::~TQueue() {
    if (root_ != NIL) {
        deleteitem(root_);
        
    }
}
    
void TQueue::print() {
    if (root_!= NIL) {
        root_->t_iterate(prnt, 0);
    }
}

void TQueue::forall_callback(void(*f)(const TQItem*, int)) {
    if (root_ != NIL ) {
        root_->t_iterate(f, 0);
    }
}

void TQueue::check(const char* mes) {
#if DOCHECK
    errmess_ = mes;
    if (root_ != NIL) {
        root_->t_iterate(chk, 0);
    }
    errmess_ = nil;
#endif
}

double TQueue::least_t() {
    TQItem* b = least();
    if (b) {
        return b->t_;
    }else{
        return 1e15;
    }
}

TQItem* TQueue::least() {
    STAT(nleast)
#if !FAST_LEAST || DOCHECK
    TQItem* b;
    b = root_;
    if (b != NIL) for (; b->left_ != NIL; b = b->left_) {
        STAT(nleastsrch)
    }
#if DOCHECK
    assert(least_ == b);
#else
    least_ = b;
#endif
#endif
    return least_ != NIL ? least_ : nil ;

}

void TQueue::new_least() {
    assert(least_ != NIL);
    assert(least_->left_ == NIL);
    TQItem* b = least_->right_;
    if (b != NIL) {
        for (;b->left_ != NIL; b = b->left_) {;}
        least_ = b;
    }else{
        b = least_->parent_;
        if (b && b != NIL) {
            assert(b->left_ == least_);
            least_ = b;
        }else{
            least_ = NIL;
        }
    }
}

void TQueue::move_least(double tnew) {
    TQItem* b = least();
    if (b) {
        move(b, tnew);
    }
}

void TQueue::move(TQItem* i, double tnew) {
PSTART(1)
    STAT(nmove)
    // the long way
    deleteNode(i);
    insertNode(tnew, i);
PSTOP(1)
}

void TQueue::statistics() {
#if COLLECT_TQueue_STATISTICS
    Printf("insertions=%lu  moves=%lu fastmoves=%lu removals=%lu calls to least=%lu\n", ninsert, nmove, nfastmove, nrem, nleast);
    Printf("calls to find=%lu balances=%lu complex removals=%lu\n", nfind, nbal, ncmplxrem);
    Printf("comparisons=%lu leastsearch=%lu findsearch=%lu\n", ncompare, nleastsrch, nfindsrch);
#else
    Printf("Turn on COLLECT_TQueue_STATISTICS_ in tqueue.h\n");
#endif
}

void RBTQueue::rotateLeft(Node *x) {

   /**************************
    *  rotate node x to left *
    **************************/

    Node *y = x->right;

    /* establish x->right link */
    x->right = y->left;
    if (y->left != NIL) y->left->parent = x;

    /* establish y->parent link */
    if (y != NIL) y->parent = x->parent;
    if (x->parent) {
        if (x == x->parent->left)
            x->parent->left = y;
        else
            x->parent->right = y;
    } else {
        root = y;
    }

    /* link x and y */
    y->left = x;
    if (x != NIL) x->parent = y;
}

void RBTQueue::rotateRight(Node *x) {

   /****************************
    *  rotate node x to right  *
    ****************************/

    Node *y = x->left;

    /* establish x->left link */
    x->left = y->right;
    if (y->right != NIL) y->right->parent = x;

    /* establish y->parent link */
    if (y != NIL) y->parent = x->parent;
    if (x->parent) {
        if (x == x->parent->right)
            x->parent->right = y;
        else
            x->parent->left = y;
    } else {
        root = y;
    }

    /* link x and y */
    y->right = x;
    if (x != NIL) x->parent = y;
}

void RBTQueue::insertFixup(Node *x) {

   /*************************************
    *  maintain Red-Black tree balance  *
    *  after inserting node x           *
    *************************************/

    /* check Red-Black properties */
    while (x != root && x->parent->color == RED) {
        /* we have a violation */
        if (x->parent == x->parent->parent->left) {
            Node *y = x->parent->parent->right;
            if (y->color == RED) {

                /* uncle is RED */
                x->parent->color = BLACK;
                y->color = BLACK;
                x->parent->parent->color = RED;
                x = x->parent->parent;
            } else {

                /* uncle is BLACK */
                if (x == x->parent->right) {
                    /* make x a left child */
                    x = x->parent;
                    rotateLeft(x);
                }

                /* recolor and rotate */
                x->parent->color = BLACK;
                x->parent->parent->color = RED;
                rotateRight(x->parent->parent);
            }
        } else {

            /* mirror image of above code */
            Node *y = x->parent->parent->left;
            if (y->color == RED) {

                /* uncle is RED */
                x->parent->color = BLACK;
                y->color = BLACK;
                x->parent->parent->color = RED;
                x = x->parent->parent;
            } else {

                /* uncle is BLACK */
                if (x == x->parent->left) {
                    x = x->parent;
                    rotateRight(x);
                }
                x->parent->color = BLACK;
                x->parent->parent->color = RED;
                rotateLeft(x->parent->parent);
            }
        }
    }
    root->color = BLACK;
}

Node* RBTQueue::insert(double t, void* d) {
    TQItem* i = tpool_->alloc();
    i->data_ = d;
    insertNode(t, i);
    return i;
}

void RBTQueue::insertNode(T data, Node* x) {
//printf("%p::insertNode %g\n", this, data);
    Node *current, *parent;

#if FAST_LEAST
    STAT(ncompare)
    if (data < least_t()) {
        least_ = x;
    }
#endif

   /***********************************************
    *  allocate node for data and insert in tree  *
    ***********************************************/

    /* find where node belongs */
    STAT(ninsert)
    current = root;
    parent = 0;
    while (current != NIL) {
#if 0
        if (compEQ(data, current->data)) return (current);
#endif
        parent = current;
        current = compLT(data, current->data) ?
            current->left : current->right;
    }

    /* setup new node */
#if 0
    if ((x = malloc (sizeof(*x))) == 0) {
        printf ("insufficient memory (insertNode)\n");
        exit(1);
    }
#endif
    x->data = data;
    x->parent = parent;
    x->left = NIL;
    x->right = NIL;
    x->color = RED;

    /* insert node in tree */
    if(parent) {
        if(compLT(data, parent->data))
            parent->left = x;
        else
            parent->right = x;
    } else {
        root = x;
    }

    insertFixup(x);
}

void RBTQueue::deleteFixup(Node *x) {

   /*************************************
    *  maintain Red-Black tree balance  *
    *  after deleting node x            *
    *************************************/

    while (x != root && x->color == BLACK) {
        if (x == x->parent->left) {
            Node *w = x->parent->right;
            if (w->color == RED) {
                w->color = BLACK;
                x->parent->color = RED;
                rotateLeft (x->parent);
                w = x->parent->right;
            }
            if (w->left->color == BLACK && w->right->color == BLACK) {
                w->color = RED;
                x = x->parent;
            } else {
                if (w->right->color == BLACK) {
                    w->left->color = BLACK;
                    w->color = RED;
                    rotateRight (w);
                    w = x->parent->right;
                }
                w->color = x->parent->color;
                x->parent->color = BLACK;
                w->right->color = BLACK;
                rotateLeft (x->parent);
                x = root;
            }
        } else {
            Node *w = x->parent->left;
            if (w->color == RED) {
                w->color = BLACK;
                x->parent->color = RED;
                rotateRight (x->parent);
                w = x->parent->left;
            }
            if (w->right->color == BLACK && w->left->color == BLACK) {
                w->color = RED;
                x = x->parent;
            } else {
                if (w->left->color == BLACK) {
                    w->right->color = BLACK;
                    w->color = RED;
                    rotateLeft (w);
                    w = x->parent->left;
                }
                w->color = x->parent->color;
                x->parent->color = BLACK;
                w->left->color = BLACK;
                rotateRight (x->parent);
                x = root;
            }
        }
    }
    x->color = BLACK;
}

void RBTQueue::remove(Node* z) {
    if (z && z != NIL) {
        deleteNode(z);
        tpool_->free(z);
    }
}

void RBTQueue::deleteNode(Node *z) {
//printf("%p::deleteNode %g\n", this, z->t_);
    Node *x, *y;

    STAT(nrem)
   /*****************************
    *  delete node z from tree  *
    *****************************/

    if (z == NIL) return;

#if FAST_LEAST
    if (least_ == z) {
        new_least();
    }
#endif

    if (z->left == NIL || z->right == NIL) {
        /* y has a NIL node as a child */
        y = z;
    } else {
        /* find tree successor with a NIL node as a child */
        y = z->right;
        while (y->left != NIL) y = y->left;
    }

    /* x is y's only child */
    if (y->left != NIL)
        x = y->left;
    else
        x = y->right;

    /* remove y from the parent chain */
    x->parent = y->parent;
    if (y->parent)
        if (y == y->parent->left)
            y->parent->left = x;
        else
            y->parent->right = x;
    else
        root = x;

#if 0
    // inadequate. does not preserve association between data and Node*
    if (y != z) z->data = y->data;
#endif

    if (y->color == BLACK)
        deleteFixup (x);

#if 0
    free (y);
#else
    //we need to preserve the association between data and Node*
    if (y != z) {
        y->red_ = z->red_;
        y->parent_ = z->parent_;
        y->left_ = z->left_;
        y->right_ = z->right_;
        if (z->left_ != NIL) { z->left_->parent_ = y; }
        if (z->right_ != NIL) { z->right_->parent_ = y; }
        if (z->parent && z->parent_ != NIL) {
            if (z->parent_->left_ == z) {
                z->parent_->left_ = y;
            }else{
                z->parent_->right_ = y;
            }
        }
    }
#endif
}

Node* RBTQueue::find(T data) {

    STAT(nfind);
   /*******************************
    *  find node containing data  *
    *******************************/

    Node *current = root;
    while(current != NIL)
    STAT(nfindsrch)
    STAT(ncompare)
        if(compEQ(data, current->data))
            return (current);
        else
            current = compLT (data, current->data) ?
                current->left : current->right;
    return(0);
}