Logo Search packages:      
Sourcecode: ncc version File versions  Download package

inttree.C

/******************************************************************************

      The Integer Tree

      We want to store things whos comparison key is an integer value.

      Whether a node is less or more compared to another node will be
      just a matter of the n-th bit of the integer, where n the current
      depth. For example the Least Significant Bit will be used to
      specify less (0) or more (1) for the comparison with the root node.

      Each integer therefore carries its tree path (0 - go less, 1 - go more)

      For any possible order of the nodes the tree will NEVER exceed the
      depth of 33 (for 32-bit integers).

      Even though it could be unbalanced, its logarithmic unbalance.
      We will always be able to find something in less than 32 steps.
            O(32)=O(1) < O(log(n)) < O(n) < O(n^2) < O(\infty)

      Moverover, if the numbers are in a range 0..2^n the depth will
      always be <= n+1. For a database with 65536 ID-elements, finds will
      be a matter of 17 steps.

      In order to remove an element from the tree any node can replace
      the node to be removed as long as:
            - It is below it
            - It is a terminal node
      Because it has the same path and no other node's postition is
      changed in the tree.

******************************************************************************/
/**************************************************************************
 Copyright (C) 2000, 2001, 2002 Stelios Xanthakis
**************************************************************************/

#include <stdio.h>

#include "inttree.h"

unsigned int intTree::Query;
intNode **intTree::FoundSlot;

intTree::intTree ()
{
      cnt = 0;
      root = NULL;
      FoundSlot = NULL;
}

intNode::~intNode ()
{
      if (less) delete less;
      if (more) delete more;
}

intNode *intTree::intFind (unsigned int q)
{
      Query = q;

      intNode *n;

      if (!(n = root)) {
            FoundSlot = &root;
            return NULL;
      }

      FoundSlot = NULL;

      for (unsigned int bt = 1; bt; bt *= 2) {
            if (n->Key == q) return n;
            if (q & bt)
                  if (n->less) n = n->less;
                  else {
                        FoundSlot = &n->less;
                        return NULL;
                  }
            else
                  if (n->more) n = n->more;
                  else {
                        FoundSlot = &n->more;
                        return NULL;
                  }
      }

      fprintf (stderr, "intTree FUBAR. Segmentation Fault. sorry\n");
      return NULL;
}

intNode::intNode (intTree *i)
{
      if (i->FoundSlot) addself (i);

      less = more = NULL;
}

void intNode::addself (intTree *i)
{
      *i->FoundSlot = this;
      ++i->cnt;
      i->FoundSlot = NULL;
      Key = i->Query;
}

void intNode::intRemove (intTree *i)
{
      unsigned int isroot, bt = 0;
      intNode *n = i->root;

      if (!(isroot = n == this))
            for (bt = 1; bt; bt *= 2)
                  if (Key & bt)     // avoid braces like hell
                        if (n->less != this) n = n->less;
                        else break;
                  else        // yes but why?
                        if (n->more != this) n = n->more;
                        else break;

      if (!less && !more)
            if (isroot) i->root = NULL;
            else
                  if (Key & bt) n->less = NULL;
                  else n->more = NULL;
      else {
            intNode *r = this, *rp = NULL;
            while (r->more || r->less) {
                  rp = r;
                  r = (r->more) ? r->more : r->less;
            }
            if (isroot) i->root = r;
            else
                  if (Key & bt) n->less = r;
                  else n->more = r;
            if (rp->more == r) rp->more = NULL;
            else rp->less = NULL;
            r->more = more;
            r->less = less;
      }

      i->cnt--;
      less = more = NULL;
}

Generated by  Doxygen 1.6.0   Back to index