// splaying, straightforward but not fastest possible
#include <stdio.h>

#define FALSE (0)
#define TRUE (1)

typedef struct node nodetype;
typedef struct node *ref;
struct node
{
int key,count;
ref left,right;
};

ref root;
int probes;
int sp;

enum directions {NONE,LEFT,RIGHT};
typedef enum directions directionsType;
typedef struct stackstruct stacktype;
struct stackstruct
{
ref node;
directionsType direct;
};
stacktype stack[20000];

#define generateRandom(minRange,maxRange) \
  (minRange)+abs(random()) % ((maxRange)-(minRange)+1)

void access(int x,ref *p,int *found)
{
if ((*p)==NULL)
{
  sp--;
  *found=FALSE;
}
else if (x<(*p)->key)
{
  stack[sp].node=(*p);
  sp++;
  stack[sp].direct=LEFT;
  access(x,&((*p)->left),found);
}
else if (x>(*p)->key)
{
  stack[sp].node=(*p);
  sp++;
  stack[sp].direct=RIGHT;
  access(x,&((*p)->right),found);
}
else
{
  stack[sp].node=(*p);
  (*p)->count++;
  (*found)=TRUE;
}
} 

void ll_rotation(ref *p)
{
ref p1;

p1=(*p)->left;
// single LL rotation
(*p)->left=p1->right;
p1->right=(*p);
(*p)=p1;
}

void rr_rotation(ref *p)
{
ref p1;

p1=(*p)->right;
// single RR rotation
(*p)->right=p1->left;
p1->left=(*p);
(*p)=p1;
}

void lr_rotation (ref *p)
{
ref p1,p2;

p1=(*p)->left;
// double LR rotation
p2=p1->right;
p1->right=p2->left;
p2->left=p1;
(*p)->left=p2->right;
p2->right=(*p);
(*p)=p2;
}

void rl_rotation (ref *p)
{
ref p1,p2;

p1=(*p)->right;
// double RL rotation
p2=p1->left;
p1->left=p2->right;
p2->right=p1;
(*p)->right=p2->left;
p2->left=(*p);
(*p)=p2;
}

void splay()
{
while (sp>1)
{
  if (sp==2)
    if (stack[sp].direct==LEFT)
    {
      // ll rotate for zig
      ll_rotation(&root);
      sp=0;
    }
    else
    {
      // rr rotate for zig
      rr_rotation(&root);
      sp=0;
    }
  else if (stack[sp].direct==LEFT)
    if (stack[sp-1].direct==LEFT)
    {
      // two ll rotations for zig-zig
      if (stack[sp-2].direct==LEFT)
      {
        ll_rotation(&(stack[sp-3].node->left));
        ll_rotation(&(stack[sp-3].node->left));
      }
      else if (stack[sp-2].direct==RIGHT)
      {
        ll_rotation(&(stack[sp-3].node->right));
        ll_rotation(&(stack[sp-3].node->right));
      }
      else
      {
        ll_rotation(&root);
        ll_rotation(&root);
      };
      stack[sp-2].node=stack[sp].node;
      sp-=2;
      }
    else
    {
      // rl rotation for zig-zag
      if (stack[sp-2].direct==LEFT)
        rl_rotation(&(stack[sp-3].node->left));
      else if (stack[sp-2].direct==RIGHT)
        rl_rotation(&(stack[sp-3].node->right));
      else
        rl_rotation(&root);
      stack[sp-2].node=stack[sp].node;
      sp-=2;
    }
  else if (stack[sp-1].direct==RIGHT)
  {
    // two rr rotations for zig-zig
    if (stack[sp-2].direct==LEFT)
    {
      rr_rotation(&(stack[sp-3].node->left));
      rr_rotation(&(stack[sp-3].node->left));
    }
    else if (stack[sp-2].direct==RIGHT)
    {
      rr_rotation(&(stack[sp-3].node->right));
      rr_rotation(&(stack[sp-3].node->right));
    }
    else
    {
      rr_rotation(&root);
      rr_rotation(&root);
    }
    stack[sp-2].node=stack[sp].node;
    sp-=2;
  }
  else
  {
    // lr rotation for zig-zag
    if (stack[sp-2].direct==LEFT)
      lr_rotation(&(stack[sp-3].node->left));
    else if (stack[sp-2].direct==RIGHT)
      lr_rotation(&(stack[sp-3].node->right));
    else
      lr_rotation(&root);
    stack[sp-2].node=stack[sp].node;
    sp-=2;
  }
}
}

void insert(int key)
{
int found;
ref left,right,newkey;

sp=1;
stack[sp].direct=NONE;

access(key,&root,&found);
splay();
if (!found)
{
  newkey=(ref) malloc(sizeof(nodetype));
  if (newkey==NULL)
  {
    printf("malloc failed\n");
    exit(0);
  }
  newkey->key=key;
  newkey->count=1;
  if (root==NULL)
  {
    left=NULL;
    right=NULL;
  }
  else if (root->key<key)
  {
    left=root;
    right=root->right;
    left->right=NULL;
  }
  else
  {
    left=root->left;
    right=root;
    right->left=NULL;
  };
  root=newkey;
  root->left=left;
  root->right=right;
}
}

main()
{
int i,key,found;
int num,seed;

printf("enter number of keys & seed\n");
scanf("%d %d",&num,&seed);
srandom(seed);
root=NULL;
/*
for (i=0;i<num;i++)
{
  key=generateRandom(0,99999999);
  insert(key);
}
probes=0;
check(&root,0);
printf("average_probes=%f\n",((float) probes)/num);
*/
for (i=0;i<num;i++)
  insert(i);
while (1)
{
  printf("Enter key\n");
  scanf("%d",&key);
  sp=1;
  stack[sp].direct=NONE;
  access(key,&root,&found);
  if (!found)
  {
    sp=0;
    printf("key not found\n");
  }
  else
    splay();
}
}