Home modules.gotpike.org
Username: Password: [Create Account]
[Forgot Password?]

Modules

ADT
Database
GTK2
GUI
IP
PiJAX
Public
Sql
Stdio
Subversion
System
Tools
Xosd
lua
v4l2
wx

Recent Changes

Public.Parser.XML2 1.50
Public.ZeroMQ 1.1
Public.Template.Mustache 1.0
Public.Protocols.XMPP 1.4
Sql.Provider.jdbc 1.0

Popular Downloads

Public.Parser.JSON2 1.0
Public.Parser.JSON 0.2
GTK2 2.23
Public.Web.FCGI 1.8
Public.Parser.XML2 1.48


Module Information
ADT.Tree
Viewing contents of ADT_Tree-1.2/tree.c

/*
 * Time-stamp: <05/11/21 09:32:53 riffraff>
 *
 * $Id: tree.c,v 1.4 2005/11/21 15:34:03 riffraff Exp $
 */

#include "global.h"
#include "module.h"
#include "interpret.h"
#include "svalue.h"
#include "stralloc.h"
#include "array.h"
#include "pike_macros.h"
#include "program.h"
#include "object.h"
#include "pike_types.h"
#include "pike_error.h"
#include "builtin_functions.h"
#include "opcodes.h"
#include "module_support.h"
#include "operators.h"
#include "mapping.h"

#include "tree.h"

#undef THIS
#define THIS ((struct atable *)(Pike_fp->current_storage))
#define THIS_PROGRAM (Pike_fp->context.prog)
#define RETURN_THIS() do{ ref_push_object(Pike_fp->current_object); }while(0)

struct anode sentinel;

void tree_sizeof(INT32 args) {
  pop_n_elems(args);
  push_int(THIS->count);
}

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

struct anode *low_tree_insert(struct svalue *key, struct svalue *val) {
  struct anode *where,*parent,*node;
  int res=-1;

  where=THIS->root->left;
  parent=where->parent;
  
  node=create_node();
  assign_svalue_no_free(node->key,key);
  assign_svalue_no_free(node->val,val?val:key);
  
  while (where!=&sentinel) {
    parent=where;
    res=compare_svalue(key,where->key);
    if (res==0) { /* duplicate */
      destroy_node(node);
      return NULL;
    }
    if (res<0)
      where=where->left;
    else
      where=where->right;
  }

  /* where==&sentinel */
  if (res<0)
    parent->left=node;
  else
    parent->right=node;
  node->parent=parent;
  node->left=&sentinel;
  node->right=&sentinel;
  THIS->count++;
  THIS->gen++;
  return node;
}

void low_tree_remove(struct anode *node) {
  struct anode *s,*c;
  low_tree_delete(node,&s,&c);
}

void low_tree_delete(struct anode *node,
		 struct anode **pswap,
		 struct anode **pchild) {
  struct anode *child,*delparent,*next,*nextparent;

  delparent=node->parent;
  next=node;

  if (node->left!=&sentinel && node->right!=&sentinel) {
    next=find_next(node);
    nextparent=next->parent;

    if (next==&sentinel) {
      fputs("low_tree_delete:  next==NULL\n",stderr);
      return;
    }
    if (next->parent==&sentinel) {
      fputs("low_tree_delete:  next->parent==NULL\n",stderr);
      return;
    }
    if (next->left!=&sentinel) {
      fputs("low_tree_delete:  next->left!=NULL\n",stderr);
      return;
    }
    /* next!=NULL && next->parent!=NULL && next->left==NULL */


    child=next->right;
    child->parent=nextparent;

    if (nextparent->left==next) {
      nextparent->left=child;
    } else {
      if (nextparent->right!=next) {
	fputs("low_tree_delete:  nextparent->right!=next\n",stderr);
	return;
      }
      /* nextparent->right==next */
      nextparent->right=child;
    }

    next->parent=delparent;
    next->left=node->left;
    next->right=node->right;
    next->left->parent=next;
    next->right->parent=next;

    if (delparent->left==node) {
      delparent->left=next;
    } else {
      if (delparent->right!=node) {
	fputs("low_tree_delete:  delparent->right!=node\n",stderr);
	return;
      }
      /* delparent->right==node */
      delparent->right=next;
    }
  } else {
    if (node==&sentinel) {
      fputs("low_tree_delete:  node==NULL\n",stderr);
      return;
    }

    if (!(node->left==&sentinel || node->right==&sentinel)) {
      fputs("low_tree_delete:  !(node->left==NULL || node->right==NULL)\n",stderr);
      return;
    }
    
    /* node!=NULL */
    /* node->left==NULL && node->right==NULL */

    child=(node->left!=&sentinel)?node->left:node->right;

    child->parent=delparent=node->parent;

    if (node==delparent->left) {
      delparent->left=child;
    } else {
      if (node!=delparent->right) {
	fputs("low_tree_delete:  node!=delparent->right\n",stderr);
	return;
      }
      /* node==delparent->right */
      delparent->right=child;
    }
  }
  node->parent=node->left=node->right=NULL;

  THIS->count--;
  THIS->gen--;

  *pswap=next;
  *pchild=child;
}

struct anode *low_tree_find(struct svalue *key) {
  struct anode *root,*saved;
  int res;

  root=THIS->root->left;

  while (root!=&sentinel) {
    res=compare_svalue(key,root->key);
    if (res<0)
      root=root->left;
    else if (res>0)
      root=root->right;
    else {
      if (!THIS->dup) /* no dupes, return match */
	return root;
      else { /* could be dupes, find leftmost one */
	do {
	  saved=root;
	  root=root->left;
	  while (root!=&sentinel && compare_svalue(key,root->key))
	    root=root->right;
	} while (root!=&sentinel);
	return saved;
      }
    }
  }
  return NULL;
}

struct anode *low_tree_lower_bound(struct svalue *key) {
  struct anode *root,*tent;

  root=THIS->root->left;
  tent=NULL;

  while (root!=&sentinel) {
    int res=compare_svalue(key,root->key);

    if (res>0) {
      root=root->right;
    } else if (res<0) {
      tent=root;
      root=root->left;
    } else {
      if (!THIS->dup) {
	return root;
      } else {
	tent=root;
	root=root->left;
      }
    }
  }
  return tent;
}

struct anode *low_tree_upper_bound(struct svalue *key) {
  struct anode *root,*tent;

  root=THIS->root->left;
  tent=NULL;

  while (root!=&sentinel) {
    int res=compare_svalue(key,root->key);

    if (res<0) {
      root=root->left;
    } else if (res>0) {
      tent=root;
      root=root->right;
    } else {
      if (!THIS->dup) {
	return root;
      } else {
	tent=root;
	root=root->right;
      }
    }
  }
  return tent;
}

void tree_rotate_left(struct anode *child, struct anode *parent) {
  struct anode *leftgc,*g;

  if (parent->right!=child) {
    fputs("tree_rotate_left:  parent->right!=child\n",stderr);
    return;
  }

  parent->right=leftgc=child->left;
  leftgc->parent=parent;

  child->parent=g=parent->parent;

  if (parent==g->left) {
    g->left=child;
  } else {
    if (parent!=g->right) {
      fputs("tree_rotate_left:  parent!=g->right\n",stderr);
      return;
    }
    g->right=child;
  }

  child->left=parent;
  parent->parent=child;
}

void tree_rotate_right(struct anode *child, struct anode *parent) {
  struct anode *rgc,*g;

  if (parent->left!=child) {
    fputs("tree_rotate_right:  parent->left!=child\n",stderr);
    return;
  }

  parent->left=rgc=child->right;
  rgc->parent=parent;

  child->parent=g=parent->parent;

  if (parent==g->right) {
    g->right=child;
  } else {
    if (parent!=g->left) {
      fputs("tree_rotate_right:  parent!=g->left\n",stderr);
    }
    /* parent==g->left */
    g->left=child;
  }

  child->right=parent;
  parent->parent=child;
}

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

void tree_clear(INT32 args) {
  pop_n_elems(args);
  while (THIS->count) {
    struct anode *n;
    n=find_first(THIS->root->left);
    low_tree_remove(n);
    destroy_node(n);
  }
}

void tree_destroy(INT32 args) {
  tree_clear(args);
  free_svalue(&THIS->comp_func);
  /*  free(THIS->root->left); */
}

void tree_create(INT32 args) {
  struct svalue *cb=NULL;

  get_all_args("create",args,".%*",&cb);
  low_tree_create(cb);
  THIS->type=TREE_BIN;
  pop_n_elems(args);
}

void low_describe_tree(struct anode *a, int type) {
  if (a==&sentinel)
    return;

#define DESCRIBE() if (a->key) {		\
    struct pike_string *s;			\
    s=tree_describe_type(a->key);		\
    push_string(s);				\
    s=tree_describe_type(a->val);		\
    push_string(s);				\
    f_aggregate(2);				\
  }

#define push_stuff() {				\
    push_svalue(a->key);			\
    push_svalue(a->val);			\
    f_aggregate(2);				\
  }

  if (type==TREE_PREORDER)
    push_stuff();
  low_describe_tree(a->left,type);
  if (type==TREE_INORDER)
    push_stuff();
  low_describe_tree(a->right,type);
  if (type==TREE_POSTORDER)
    push_stuff();
}

void tree_cast(INT32 args) {
  char *type;

  get_all_args("cast",args,"%s",&type);
  if (!strcmp(type,"array")) {
    pop_n_elems(args);
    low_describe_tree(THIS->root->left,0);
    f_aggregate(THIS->count);
  } else {
    push_undefined();
  }
}

void tree_insert(INT32 args) {
  struct svalue *key,*val;
  struct anode *n;
  struct anode *res;

  val=NULL;
  get_all_args("insert",args,"%*.%*",&key,&val);
  if (key==NULL) {
    pop_n_elems(args);
    RETURN_THIS();
    return;
  }

  res=low_tree_insert(key,val);
  pop_n_elems(args);
  if (res==NULL && THIS->abend)
    Pike_error("Key already exists.\n");
  RETURN_THIS();
}

void tree_find(INT32 args) {
  struct svalue *key;
  struct anode *n;

  get_all_args("find",args,"%*",&key);
  if (key==NULL) {
    pop_n_elems(args);
    push_undefined();
    return;
  }
  n=low_tree_find(key);
  pop_n_elems(args);
  if (n)
    push_svalue(n->val);
  else
    push_undefined();
}

void tree_remove(INT32 args) {
  struct svalue *key=NULL;
  struct anode *n;

  get_all_args("remove",args,"%*",&key);
  if (key==NULL) {
    push_undefined();
    return;
  }
  n=low_tree_find(key);
  if (n==NULL) {
    push_undefined();
    return;
  }
  low_tree_remove(n);
  pop_n_elems(args);
  push_svalue(n->key);
  push_svalue(n->val);
  f_aggregate(2);
}

void tree_first(INT32 args) {
  struct anode *n;

  pop_n_elems(args);
  n=find_first(THIS->root->left);
  if (n) {
    push_svalue(n->key);
    push_svalue(n->val);
    f_aggregate(2);
  } else
    push_undefined();
}

void tree_next(INT32 args) {
  struct anode *n;
  struct svalue *key;

  get_all_args("next",args,"%*",&key);
  if (key==NULL) {
    push_undefined();
    return;
  }
  n=low_tree_find(key);
  pop_n_elems(args);
  if (n==NULL) {
    push_undefined();
    return;
  }
  n=find_next(n);
  if (n) {
    push_svalue(n->key);
    push_svalue(n->val);
    f_aggregate(2);
  } else
    push_undefined();
}

void tree_last(INT32 args) {
  struct anode *n;

  pop_n_elems(args);
  n=find_last(THIS->root->left);
  if (n) {
    push_svalue(n->key);
    push_svalue(n->val);
    f_aggregate(2);
  } else
    push_undefined();
}

void tree_prev(INT32 args) {
  struct anode *n;
  struct svalue *key;

  get_all_args("prev",args,"%*",&key);
  if (key==NULL) {
    push_undefined();
    return;
  }
  n=low_tree_find(key);
  pop_n_elems(args);
  if (n==NULL) {
    push_undefined();
    return;
  }
  n=find_prev(n);
  if (n) {
    push_svalue(n->key);
    push_svalue(n->val);
    f_aggregate(2);
  } else
    push_undefined();
}

void tree_init() {
  sentinel.key=sentinel.val=NULL;
}

struct program *tree_program;
struct program *rbtree_program;
struct program *avltree_program;
struct program *splay_program;

PIKE_MODULE_INIT
{
  start_new_program();
  ADD_STORAGE(struct atable);

  ADD_FUNCTION("create",tree_create,tFunc(tOr(tVoid,tFunc(tMixed tMixed,tInt)),tVoid),ID_STATIC);
  ADD_FUNCTION("_sizeof",tree_sizeof,tFunc(tVoid,tInt),0);
  ADD_FUNCTION("cast",tree_cast,tFunc(tString,tMixed),0);
  ADD_FUNCTION("insert",tree_insert,tFunc(tMixed tOr(tMixed,tVoid),tOr(tObj,tInt)),0);
  ADD_FUNCTION("find",tree_find,tFunc(tMixed,tOr(tMixed,tVoid)),0);
  ADD_FUNCTION("remove",tree_remove,tFunc(tMixed,tArray),0);
  ADD_FUNCTION("first",tree_first,tFunc(tVoid,tArray),0);
  ADD_FUNCTION("last",tree_last,tFunc(tVoid,tArray),0);
  ADD_FUNCTION("next",tree_next,tFunc(tMixed,tArray),0);
  ADD_FUNCTION("prev",tree_prev,tFunc(tMixed,tArray),0);
  ADD_FUNCTION("clear",tree_clear,tFunc(tVoid,tObj),0);
  ADD_FUNCTION("destroy",tree_destroy,tFunc(tVoid,tVoid),ID_STATIC);

  tree_program=end_program();

  add_integer_constant("INORDER",TREE_INORDER,0);
  add_integer_constant("PREORDER",TREE_PREORDER,0);
  add_integer_constant("POSTORDER",TREE_POSTORDER,0);

  rbtree_program=create_rbtree_program();
  splay_program=create_splay_program();

  add_program_constant("Tree",tree_program,0);
  add_program_constant("RedBlack",rbtree_program,0);
  add_program_constant("Splay",splay_program,0);
  /*  set_init_callback(tree_init); */
}

PIKE_MODULE_EXIT
{
  free_program(splay_program);
  free_program(rbtree_program);
  free_program(tree_program);
}


gotpike.org | Copyright © 2004 - 2019 | Pike is a trademark of Department of Computer and Information Science, Linköping University