Odielib: Artifact [822483fd55]

Artifact 822483fd556b93ba17510c8bbe1a6c5c40d3946b:

File cmodules/btree/tree.tcl — part of check-in [f705581d68] at 2016-03-15 20:59:32 on branch trunk — Rewrote the btree utility as a dynamic C module Fixes to practcl. Practcl now attempts to deploy the "load" function from within the project's tcl bootloader Tweaks to allow the script generated by a library's [package ifneeded] method to be evaluated properly within an amalgamated pkgIndex.tcl file, where the value of $dir changes constantly. Added a practcl bootstrap to the end of project.rc.in (user: tne size: 13755)
##
## This file implements an in-memory balanced binary tree.  This code
## was originally brought in to implement an efficient priority queue
## for the Dijkstra's shortest path algorithm in crewroute.c.
##
## This file contains code imported into READI from another project.
## The text of the original header comment follows:
##
##
## A package of routines for handling balanced binary trees.
## Copyright (c) 1990 by D. Richard Hipp
##

my code public-structure {
typedef struct Tree Tree;
/* A complete binary tree is defined by an instance of the following
** structure
*/
struct Tree {
  int (*xCompare)(const void*, const void*); /* Comparison function */
  void *(*xCopy)(const void*);               /* Key copy function, or NULL */
  void (*xFree)(void*);                      /* Key delete function */
  struct TreeElem *top;                      /* The top-most node of the tree */
};

/* Each node in the binary tree is represented by a single instance
** of the following structure
*/
typedef struct TreeElem TreeElem;
struct TreeElem {
  void *data;             /* Pointer to the user's data */
  void *key;              /* The key associated with this element */
  TreeElem *left;         /* Left daughter */
  TreeElem *right;        /* Right daughter */
  int weight;             /* Weight of this node */
};
}

my c_function {void TreeInit(Tree *tree, int (*xCompare)(const void*, const void*),void *(*xCopy)(const void*),void (*xFree)(void*))} {
/* Turn bulk memory into a Tree structure
  Tree *tree,                                 Tree object to initialize
  int (*xCompare)(const void*, const void*),  Comparison function
  void *(*xCopy)(const void*),                Key copy function or NULL 
  void (*xFree)(void*)                        Key delete function or NULL
*/
  tree->xCompare = xCompare;
  tree->xCopy = xCopy;
  tree->xFree = xFree;
  tree->top = 0;
}

my c_function {int TreeCount(Tree *pTree)} {
  /* Return the number of elements in the tree. */
  if( pTree && pTree->top ){
    return pTree->top->weight;
  }else{
    return 0;
  }
}

my c_function {static void TreeClearNode(TreeElem *p, void (*xFree)(void*))} {
  /* Delete a single node of the binary tree and all of its children */
  if( p==0 ) return;
  if( p->left ) TreeClearNode(p->left, xFree);
  if( p->right ) TreeClearNode(p->right, xFree);
  if( xFree ){
    xFree(p->key);
  }
  Tcl_Free((char *)p);
}

my c_function {void TreeClear(Tree *tree)} {
  /* Remove all nodes from a tree */
  if( tree->top ){
    TreeClearNode(tree->top, tree->xFree);
  }
  tree->top = 0;
}

my c_function {void *TreeFind(Tree *tree, const void *key)} {
/* Find the element of the tree (if any) whose key matches "key".
** Return a pointer to the data for that element.  If no match
** is found, return NULL.
*/
  TreeElem *p;

  p = tree->top;
  while( p ){
    int c = tree->xCompare(p->key, key);
    if( c==0 ){
      return p->data;
    }else if( c<0 ){
      p = p->right;
    }else{
      p = p->left;
    }
  }
  return 0;
}

my c_function {int TreeRank(Tree *tree, const void *key)} {
  /* If the node with key "key" is the left-most element of the tree, 
  ** return 0.  If it is the second to the left, return 1.  And so
  ** forth.
  **
  ** If there is no node in the tree with the key "key", then return
  ** the number that would have been returned if such a node were
  ** inserted.
  */
  TreeElem *p;
  int rank = 0;

  p = tree->top;
  while( p ){
    int c = tree->xCompare(p->key, key);
    if( c==0 ){
      rank += p->left ? p->left->weight: 0;
      break;
    }else if( c<0 ){
      rank += (p->left ? p->left->weight: 0) + 1;
      p = p->right;
    }else{
      p = p->left;
    }
  }
  return rank;
}

my c_function {static TreeElem *TreeFindNthElem(Tree *tree, int n)} {
  /* Return a pointer to the N-th element of a tree.  (The left-most
  ** element is number 0, the next is number 1 and so forth.)
  */
  TreeElem *p;

  p = tree->top;
  while( p ){
    int c = p->left ? p->left->weight : 0;
    if( n==c ){
      return p;
    }else if( n>c ){
      n -= c+1;
      p = p->right;
    }else{
      p = p->left;
    }
  }
  return 0;
}

my c_function {void *TreeData(Tree *tree, int n)} {
  /* Return the data associated with the N-th element of the tree.  Return
  ** NULL if there is no N-th element.
  */
  TreeElem *p = TreeFindNthElem(tree,n);
  return p ? p->data : 0;
}

my c_function {const void *TreeKey(Tree *tree, int n)} {
  /* Return the key associated with the N-th element of the tree.  Return
  ** NULL if there is no N-th element.
  */
  TreeElem *p = TreeFindNthElem(tree,n);
  if( p ){
    return p->key;
  }else{
    return 0;
  }
}

my c_function {static void TreeBalance(TreeElem **ppElem)} {
  /*
  ** Definitions:
  ** WEIGHT
  **   The weight of a node is the total number of children for the node
  **   plus 1.  Leaf nodes have a weight of 1.  The root node has a weight
  **   which equals the number of nodes in the tree.
  **
  ** BALANCE
  **   A node is balanced if the weight of the one child is not more than
  **   twice the weight of the other child.
  */

  /* The following routine rebalances the tree rooted at *ppElem after
  ** the insertion or deletion of a single ancestor.
  */
  TreeElem *n;     /* Pointer to self */
  int l,r;         /* Weight of left and right daughters */
  int a,b;         /* Weights of various nodes */

  if( ppElem==0 || (n=*ppElem)==0 ) return;
  l = n->left ? n->left->weight: 0;
  r = n->right ? n->right->weight: 0;
  if( l>r*2 ){    /* Too heavy on the left side */
    TreeElem *nl;     /* Pointer to left daughter */
    TreeElem *nr;     /* Pointer to right daughter */
    int ll, lr;       /* Weight of left daughter's left and right daughter */
    nl = n->left;
    ll = nl->left ? nl->left->weight: 0;
    lr = nl->right ? nl->right->weight: 0;
    if( ll>lr || nl->right==0 ){
      /*
      ** Convert from:  n     to:  nl
      **               / \        /  \
      **              nl  c      a    n
      **             /  \            / \
      **            a    b          b   c
      */
      n->left = nl->right;
      nl->right = n;
      n->weight = a = r + lr + 1;
      nl->weight = a + ll + 1;
      *ppElem = nl;
    }else{
      /*
      ** Convert from:  n        to:  nr
      **               / \           /  \
      **             nl   d        nl    n
      **            /  \          / \   / \
      **           a    nr       a   b c   d
      **               /  \
      **              b    c
      */
      int lrl, lrr;    /* Weight of Great-granddaughter nodes */
      nr = nl->right;
      lrl = nr->left ? nr->left->weight: 0;
      lrr = nr->right ? nr->right->weight: 0;
      nl->right = nr->left;
      nr->left = nl;
      n->left = nr->right;
      nr->right = n;
      n->weight = a = lrr + r + 1;
      nl->weight = b = ll + lrl + 1;
      nr->weight = a + b + 1;
      *ppElem = nr;
    }
  }else if( r>l*2 ){/* Too deep on the right side */
    TreeElem *nl;     /* Pointer to left daughter */
    TreeElem *nr;     /* Pointer to right daughter */
    int rl, rr;       /* Weight of right daughter's left and right daughter */
    nr = n->right;
    rl = nr->left ? nr->left->weight: 0;
    rr = nr->right ? nr->right->weight: 0;
    if( rr>rl || nr->left==0 ){
      /*
      ** Convert from:  n         to:  nr
      **               / \            /  \
      **              a   nr         n    c 
      **                 /  \       / \
      **                b    c     a   b
      */
      n->right = nr->left;
      nr->left = n;
      n->weight = a = l + rl + 1;
      nr->weight = a + rr + 1;
      *ppElem = nr;
    }else{
      /*
      ** Convert from:  n         to:  nl
      **               / \            /  \
      **              a   nr         n    nr
      **                 /  \       / \   / \
      **               nl    d     a   b c   d
      **              /  \
      **             b    c
      */
      int rll,rlr;    /* Weights of great-granddaughter nodes */
      nl = nr->left;
      rll = nl->left ? nl->left->weight: 0;
      rlr = nl->right ? nl->right->weight: 0;
      nr->left = nl->right;
      nl->right = nr;
      n->right = nl->left;
      nl->left = n;
      n->weight = a = l + rll + 1;
      nr->weight = b = rr + rlr + 1;
      nl->weight = a + b + 1;
      *ppElem = nl;
    }
  }else{ /* Node is already balanced.  Just recompute its weight. */
    n->weight = l + r + 1;
  }
}

my c_function {static void *TreeInsertElement(Tree *pTree, void *key, void *data)} {
  /*
  Tree *pTree,              The root of the tree
  void *key,                Insert data at this key
  void *data                Data to be inserted
  */
  /* This routine either changes the data on an existing node in the tree,
  ** or inserts a new node.  "key" identifies the node.  If the data on
  ** an existing node is changed, then the function returns the old data.
  ** If a new node is created, NULL is returned.
  */
  TreeElem *n;
  void *old = 0;
  TreeElem **h[100];  /* Sufficient for a tree with up to 4.0E+17 nodes */
  int level = 0;


  h[0] = &pTree->top;
  level = 1;
  n = pTree->top;
  while( n ){
    int c;
    c = pTree->xCompare(key, n->key);
    if( c<0 ){
      h[level++] = &(n->left);
      n = n->left;
    }else if( c>0 ){
      h[level++] = &(n->right);
      n = n->right;
    }else{
      old = n->data;
      n->data = data;                /* Replace data in an existing node */
      break;
    }
  }
  if( n==0 ){                     /* Insert a leaf node */
    level--;
    n = *h[level] = (TreeElem *)Tcl_Alloc( sizeof(TreeElem) );
    if( n==0 ){
      return data;
    }
    n->data = data;
    if( pTree->xCopy ){
      n->key = pTree->xCopy(key);
    }else{
      n->key = key;
    }
    n->left = n->right = 0;
    while( level>=0 ) TreeBalance(h[level--]);
  }
  return old;
}

my c_function {static TreeElem *TreeDeleteNthElem(TreeElem **ppTop, int N)} {
  /* Unlink the N-th node of the tree and return a pointer to that
  ** node.  (The left-most node is 0, the next node to the right is
  ** 1 and so forth.)
  */
  TreeElem *p;        /* For walking the tree */
  int level = 0;      /* Depth of the blancing stack */
  TreeElem **h[100];  /* Balance stack.  100 is sufficient for balancing
                      ** a tree with up to 4.0E+17 nodes */

  h[0] = ppTop;
  level = 1;
  p = *ppTop;
  while( p ){
    int w;
    w = (p->left ? p->left->weight: 0);
    if( N>w ){
      h[level++] = &(p->right);
      p = p->right;
      N -= w+1;
    }else if( N<w ){
      h[level++] = &(p->left);
      p = p->left;
    }else{
      break;
    }
  }
  if( p ){
    level--;
    if( p->left==0 ){
      *h[level] = p->right;
      level--;
    }else if( p->right==0 ){
      *h[level] = p->left;
      level--;
    }else{
      TreeElem *x;
      x = TreeDeleteNthElem(&(p->right),0);
      x->right = p->right;
      x->left = p->left;
      *h[level] = x;
    }
    while( level>=0 ) TreeBalance(h[level--]);
  }
  return p;
}

my c_function {static TreeElem *TreeDeleteElem(Tree *tree, const void *key)} {
  /* Unlink the node of the tree corresponding to key and return a pointer 
  ** to that node.
  */
  TreeElem *p;        /* For walking the tree */
  int level = 0;      /* Depth of the blancing stack */
  TreeElem **h[100];  /* Balance stack.  100 is sufficient for balancing
                      ** a tree with up to 4.0E+17 nodes */

  h[0] = &tree->top;
  level = 1;
  p = tree->top;
  while( p ){
    int w;
    w = tree->xCompare(p->key, key);
    if( w<0 ){
      h[level++] = &(p->right);
      p = p->right;
    }else if( w>0 ){
      h[level++] = &(p->left);
      p = p->left;
    }else{
      break;
    }
  }
  if( p ){
    level--;
    if( p->left==0 ){
      *h[level] = p->right;
      level--;
    }else if( p->right==0 ){
      *h[level] = p->left;
      level--;
    }else{
      TreeElem *x;
      x = TreeDeleteNthElem(&(p->right),0);
      x->right = p->right;
      x->left = p->left;
      *h[level] = x;
    }
    while( level>=0 ) TreeBalance(h[level--]);
  }
  return p;
}

my c_function {void *TreeInsert(Tree *tree, void *key, void *data)} {
  /* Insert new data into a node of the tree.  The node is identified
  ** by "key".
  **
  ** If the new data is NULL, then node is deleted.
  **
  ** If the node aready exists, the new data overwrites the old and
  ** the old data is returned.  If the node doesn't already exist, then
  ** a new node is created and the function returns NULL.
  */

  void *old;
  if( data==0 ){
    TreeElem *elem = TreeDeleteElem(tree, key);
    if( elem ){
      if( tree->xFree ){
        tree->xFree(elem->key);
      }
      old = elem->data;
      Tcl_Free((char *)elem);
    }else{
      old = 0;
    }
  }else{
    old = TreeInsertElement(tree,key,data);
  }
  return old;
}

my c_function {void *TreeChangeNth(Tree *tree, int n, void *data)} {
  /* Change the data on the n-th node of the tree.  The old data
  ** is returned.
  **
  ** If data==NULL, then the n-th node of the tree is deleted.  (The
  ** data associated with that node is still returned.)
  **
  ** If the value N is out-of-bounds, then no new node is created.
  ** Instead, the "data" parameter is returned.
  */
  void *old;
  if( data==0 ){
    TreeElem *elem = TreeDeleteNthElem(&tree->top,n);
    if( elem ){
      if( tree->xFree ){
        tree->xFree(elem->key);
      }
      old = elem->data;
      Tcl_Free((char *)elem);
    }else{
      old = 0;
    }
  }else{
    TreeElem *elem = TreeFindNthElem(tree,n);
    if( elem ){
      old = elem->data;
      elem->data = data;
    }else{
      old = data;
    }
  }
  return old;
}