/*
                An implementation of top-down splaying
                    D. Sleator <sleator@cs.cmu.edu>
    	                     March 1992

  "Splay trees", or "self-adjusting search trees" are a simple and
  efficient data structure for storing an ordered set.  The data
  structure consists of a binary tree, without parent pointers, and no
  additional fields.  It allows searching, insertion, deletion,
  deletemin, deletemax, splitting, joining, and many other operations,
  all with amortized logarithmic performance.  Since the trees adapt to
  the sequence of requests, their performance on real access patterns is
  typically even better.  Splay trees are described in a number of texts
  and papers [1,2,3,4,5].

  The code here is adapted from simple top-down splay, at the bottom of
  page 669 of [3].  It can be obtained via anonymous ftp from
  spade.pc.cs.cmu.edu in directory /usr/sleator/public.

  The chief modification here is that the splay operation works even if the
  item being splayed is not in the tree, and even if the tree root of the
  tree is NULL.  So the line:

                              t = splay(i, t);

  causes it to search for item with key i in the tree rooted at t.  If it's
  there, it is splayed to the root.  If it isn't there, then the node put
  at the root is the last one before NULL that would have been reached in a
  normal binary search for i.  (It's a neighbor of i in the tree.)  This
  allows many other operations to be easily implemented, as shown below.

  [1] "Fundamentals of data structures in C", Horowitz, Sahni,
       and Anderson-Freed, Computer Science Press, pp 542-547.
  [2] "Data Structures and Their Algorithms", Lewis and Denenberg,
       Harper Collins, 1991, pp 243-251.
  [3] "Self-adjusting Binary Search Trees" Sleator and Tarjan,
       JACM Volume 32, No 3, July 1985, pp 652-686.
  [4] "Data Structure and Algorithm Analysis", Mark Weiss,
       Benjamin Cummins, 1992, pp 119-130.
  [5] "Data Structures, Algorithms, and Performance", Derick Wood,
       Addison-Wesley, 1993, pp 367-375.
*/

#include <stdlib.h>
#include <stdio.h>
#include <assert.h>
#include <string.h>

#include "top-down-splay.h"
/* Here is how sedgewick would have written this.                    */
/* It does the same thing.                                           */
splaytree_node * sedgewickized_splay (splaytree_node * t, char *data) {
	splaytree_node N, *l, *r, *y;
	
	if (t == NULL) return t;
	
	N.left = N.right = NULL;
	l = r = &N;
	
	for (;;) {
		int cmp = strcmp(data, t->data);
		
		if (cmp < 0) {
			if (t->left != NULL && strcmp(data, t->left->data) < 0) {
				y = t->left; t->left = y->right; y->right = t; t = y;
			}
			if (t->left == NULL) break;
			r->left = t; r = t; t = t->left;
		} else if (cmp > 0) {
			if (t->right != NULL && strcmp(data, t->right->data) > 0) {
				y = t->right; t->right = y->left; y->left = t; t = y;
			}
			if (t->right == NULL) break;
			l->right = t; l = t; t = t->right;
		} else break;
	}
	l->right=t->left; r->left=t->right; t->left=N.right; t->right=N.left;
	return t;
}

splaytree *splaytree_init() {
	splaytree *splay;
	
	splay = (splaytree *) malloc (sizeof (splaytree));
	assert(splay);
	
	splay->top = NULL;
	
	return splay;
}

const char *splaytree_insert(splaytree * splt, const char *data) {
	/* Insert i into the tree t, unless it's already there.
	 * Return a pointer to the resulting tree.
	 */
	splaytree_node * splay, *t;
	int cmp;
	
	t = splt->top;
	
	splay = (splaytree_node *) malloc (sizeof (splaytree_node));
	
	if (t == NULL) {
		splay->left = splay->right = NULL;
		
		splt->top = splay;
		splay->data = strdup(data);
		
		return splay->data;
	}
	
	t = sedgewickized_splay(t, data);
	
	cmp = strcmp(data, t->data);
	
	if (cmp < 0) {
		splay->left = t->left;
		splay->right = t;
		t->left = NULL;
		splt->top = splay;
		
		splay->data = strdup(data);
		
		return splay->data;
	} else if (cmp > 0) {
		splay->right = t->right;
		splay->left = t;
		t->right = NULL;
		splt->top = splay;
		
		splay->data = strdup(data);
		
		return splay->data;
	} else { 
		/* We get here if it's already in the tree 
		 * Don't add it again
		 */
		
		free(splay);
		
		splt->top = t;
		
		return t->data;
	}
}

int splaytree_delete(splaytree * splt, const char *data) {
	/* Deletes i from the tree if it's there.               */
	/* Return a pointer to the resulting tree.              */
	splaytree_node * x, *t;
	
	t = splt->top;
	
	if (t == NULL) return -1;
	
	t = sedgewickized_splay(t, data);
	
	if (strcmp(data, t->data) == 0) {               /* found it */
		if (t->left == NULL) {
			x = t->right;
		} else {
			x = sedgewickized_splay(t->left, data);
			x->right = t->right;
		}
		free(t->data);
		free(t);
		
		splt->top = x;
		
		return 1;
	} else {
		splt->top = t;
		return 0;
	}
}

#if 0
void main() {
/* A sample use of these functions.  Start with the empty tree,         */
/* insert some stuff into it, and then delete it                        */
    splaytree_node * root;
    int i;
    root = NULL;              /* the empty tree */
    for (i = 0; i < 1024; i++) {
	root = insert((541*i) & (1023), root);
    }
    for (i = 0; i < 1024; i++) {
	root = delete((541*i) & (1023), root);
    }
    printf("size = %d\n", size);
}
#endif