/*
 * Time-stamp: <05/11/18 14:02:42 riffraff>
 *
 * $Id: tree.c,v 1.3 2005/11/18 20:03:56 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 */

    /*
     * First, splice out the successor from the tree completely,
     * by moving up its right child into its place.
     */

    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;
    }

    /*
     * Now that the successor has been extricated from the tree,
     * install it in place of the node that we want deleted.
     */

    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;
}

/*
 * Perform a left rotation adjustment on the tree.  The given parent node P
 * and its right child C are rearranged so that the P instead becomes the left
 * child of C.  The left subtree of C is inherited as the new right subtree
 * for P.  The ordering of the keys within the tree is thus preserved.
 */
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;
}

/*
 * This operation is the mirror image of tree_rotate_left.  It is
 * the same procedure, but with left and right interchanged.
 */
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);
}

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 *splaytree_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();

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

PIKE_MODULE_EXIT
{
  free_program(tree_program);
}