/*
 * Time-stamp: <05/11/21 08:34:24 riffraff>
 *
 * $Id: splay.c,v 1.1 2005/11/21 15:34:18 riffraff Exp riffraff $
 */

#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)

extern struct anode sentinel;

static void double_right(struct anode *child,
			 struct anode *parent,
			 struct anode *g) {
  tree_rotate_right(parent,g);
  tree_rotate_right(child,parent);
}

static void double_left(struct anode *child,
			struct anode *parent,
			struct anode *g) {
  tree_rotate_left(parent,g);
  tree_rotate_left(child,parent);
}

static void right_left(struct anode *child,
		       struct anode *parent,
		       struct anode *g) {
  tree_rotate_right(child,parent);
  tree_rotate_left(child,g);
}

static void left_right(struct anode *child,
		       struct anode *parent,
		       struct anode *g) {
  tree_rotate_left(child,parent);
  tree_rotate_right(child,g);
}

static void splay_node(struct anode *node) {
  struct anode *root,*parent;

  root=THIS->root->left;
  parent=node->parent;

  if (parent->left==node) {
    if (parent==root) {
      tree_rotate_right(node,parent);
    } else {
      struct anode *g=parent->parent;

      if (g->left==parent) {
	double_right(node,parent,g);
      } else {
	if (g->right!=parent) {
	  fputs("splay_node:  g->right!=parent\n",stderr);
	}
	right_left(node,parent,g);
      }
    }
  } else {
    if (parent->right!=node) {
      fputs("splay_node:  parent->right!=node\n",stderr);
    }

    if (parent==root) {
      tree_rotate_left(node,parent);
    } else {
      struct anode *g=parent->parent;

      if (g->right==parent) {
	double_left(node,parent,g);
      } else {
	if (g->left!=parent) {
	  fputs("splay_node:  g->left!=parent\n",stderr);
	}
	left_right(node,parent,g);
      }
    }
  }
}

static void real_low_splay_insert(struct anode *node) {
  while (node!=THIS->root->left)
    splay_node(node);
}

static struct anode *low_splay_insert(struct svalue *key,
			     struct svalue *val) {
  struct anode *n;

  n=low_tree_insert(key,val);
  if (n==NULL)
    return NULL;
  real_low_splay_insert(n);
  return n;
}

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

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

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

static void real_low_splay_remove(struct anode *n) {
  struct anode *dummy;

  low_tree_delete(n,&dummy,&dummy);
}

static struct anode *low_splay_remove(struct svalue *key) {
  struct anode *n;

  n=low_tree_find(key);
  if (n==NULL)
    return NULL;
  real_low_splay_remove(n);
  return n;
}

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

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

void splay_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);
  if (n==NULL) {
    push_undefined();
    return;
  }
  push_svalue(n->key);
  push_svalue(n->val);
  f_aggregate(2);
  while (n!=THIS->root->left)
    splay_node(n);
}

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

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

extern struct program *tree_program;

struct program *create_splay_program() {
  start_new_program();
  low_inherit(tree_program,0,0,0,0,0);

  ADD_FUNCTION("create",splay_create,tFunc(tOr(tVoid,tFunc(tMixed tMixed,tInt)),tVoid),ID_STATIC);
  ADD_FUNCTION("insert",splay_insert,tFunc(tMixed tOr(tMixed,tVoid),tOr(tObj,tInt)),0);
  ADD_FUNCTION("remove",splay_remove,tFunc(tMixed,tArray),0);
  ADD_FUNCTION("find",splay_find,tFunc(tMixed,tArray),0);

  return end_program();
}