DEFINITION MODULE splay;
(*
	Title:		Implementation of splay trees
	Last Edit:	Sun Nov 22 13:43:23 1992
	Author:		Johan Persson at my9

	SCCS:		@(#)splay.def       2.1     92/11/22

	Description:	This code implements splay tree as described in 
	                Sleator D. and Tarjan R. "Self adjusting
			binary trees", JACM Vol 32. No 3, 1985, pp 652-
			686.
			
			The implemenation is based on a top down
                        splaying heuristics as described in section 4 of 
			the article.

	Note:		This implementation also supports the operations
			'getRankElement' which finds the element in the tree
			with a given rank in O(lgn) time) and 'getRank', 
			(which returns the rank of a given element)
			To achive this one must store the weight of a node in
			each node (i.e the number of descadents). This
			information must be updated after each operation
			(insert, delete, find). If this is to costly
			(it takes O(n)) the source can be modified to remove
			the call to 'fixRank' in 'insert', 'delete' and
			'find'

*)

  IMPORT splayItem;

  TYPE
     auxFunc = PROCEDURE (splayItem.T);
     T;

  PROCEDURE create(VAR tree:T);
  (* Post: The splay tree tree 'tree' has been created.
  *)
		   
  PROCEDURE destroy(VAR tree:T);
  (* Pre: 'tree' has been created with 'create'
     Post: All dynamic memory previously associated with 'tree'
           have been returned. The 'del' function specified in
	   'create' has been called one time for each datum in the
	   tree. Upon completion 'tree' is no longer a valid tree.
  *) 
  
  PROCEDURE insert(tree:T; item:splayItem.T);
  (* Pre: 'tree' has been created with 'create'
     Post: 'item' has been inserted in 'tree'. If the 'item' already
           exists this operation equals 
	      delete(tree,item);insert(tree,item)
  *)
  
  PROCEDURE delete(tree:T; item:splayItem.T);
  (* Pre: 'tree' has been created with 'create'
     Post: If 'item' exists it has been removed from 'tree'
           otherwise the tree is left untouched
  *)
  
  PROCEDURE find(tree:T; item:splayItem.T; VAR found:splayItem.T):BOOLEAN;
  (* Pre: 'tree' has been created with 'create'
     Post: If 'item' exists in 'tree' 'found' has been assigned
           to the corresponding data in 'tree'.
	   Note: The reason for returning the same item searched
	         for is to make it possible to specify an incomplete
		 search structure and then get the full structure
		 returned.
     Returns: TRUE if 'item' exist, FALSE otherwise
  *)
  
  PROCEDURE nbrElem(tree:T): CARDINAL;
  (* Pre: 'tree' has been created with 'create'
     Returns: The number of elements in 'tree'
  *)
  
  PROCEDURE getRankElement(tree:T; r:CARDINAL; VAR found:splayItem.T): BOOLEAN;
  (* Pre: 'tree' has been created with 'create'
     Post: The 'item' with rank 'r' has been assigned to 'found'
     Returns: TRUE if 'item' exist, FALSE otherwise
  *)
  
  PROCEDURE getRank(tree:T; item:splayItem.T):CARDINAL;
  (* Pre: 'tree' has been created with 'create'
     Returns: The rank of element 'item'. If 'item' wasn't 
              found the routine returns 0 
  *)
  
  PROCEDURE mapIn(tree:T; f:auxFunc);
  (* Pre: 'tree' has been created with 'create'
     Post: The 'f' procedure has been applied to all elements in
           'tree' according to a tree-inorder walk
  *)
  
  PROCEDURE mapPre(tree:T; f:auxFunc);
  (* Pre: 'tree' has been created with 'create'
     Post: The 'f' procedure has been applied to all elements in
           'tree' according to a tree-preorder walk
  *)
  
  PROCEDURE mapPos(tree:T; f:auxFunc); 
  (* Pre: 'tree' has been created with 'create'
     Post: The 'f' procedure has been applied to all elements in
           'tree' according to a tree-preorder walk
  *)

END splay.
