home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1994 October / usenetsourcesnewsgroupsinfomagicoctober1994disk2.iso / misc / volume35 / m2-splay22 / part01 / splay.def < prev    next >
Text File  |  1993-01-20  |  4KB  |  112 lines
  1. DEFINITION MODULE splay;
  2. (*
  3.     Title:        Implementation of splay trees
  4.     Last Edit:    Mon Dec 21 13:20:31 1992
  5.     Author:        Johan Persson at my16
  6.  
  7.     SCCS:        @(#)splay.def       2.2     92/12/21
  8.  
  9.     Description:    This code implements splay tree as described in 
  10.                     Sleator D. and Tarjan R. "Self adjusting
  11.             binary trees", JACM Vol 32. No 3, 1985, pp 652-
  12.             686.
  13.             
  14.             The implemenation is based on a top down
  15.                         splaying heuristics as described in section 4 of 
  16.             the article.
  17.  
  18.     Note:        This implementation also supports the operations
  19.             'getRankElement' which finds the element in the tree
  20.             with a given rank in O(lgn) time) and 'getRank', 
  21.             (which returns the rank of a given element)
  22.             To achive this one must store the weight of a node in
  23.             each node (i.e the number of descadents). The
  24.             update of this information after each basic 
  25.             operation takes O(lgn) time.
  26.             
  27.             To maintain this weight it's necessary to use a
  28.             stack, since the size of the stack is 
  29.             specified at compile time this may cause a checked 
  30.             run time error if the bounds of this stack is 
  31.                 violated. 
  32. *)
  33.  
  34.   IMPORT splayItem;
  35.  
  36.   TYPE
  37.      auxFunc = PROCEDURE (splayItem.T);
  38.      T;
  39.  
  40.   PROCEDURE create(VAR tree:T);
  41.   (* Post: The splay tree tree 'tree' has been created.
  42.   *)
  43.            
  44.   PROCEDURE destroy(VAR tree:T);
  45.   (* Pre: 'tree' has been created with 'create'
  46.      Post: All dynamic memory previously associated with 'tree'
  47.            have been returned. The 'del' function specified in
  48.        'create' has been called one time for each datum in the
  49.        tree. Upon completion 'tree' is no longer a valid tree.
  50.   *) 
  51.   
  52.   PROCEDURE insert(tree:T; item:splayItem.T);
  53.   (* Pre: 'tree' has been created with 'create'
  54.      Post: 'item' has been inserted in 'tree'. If the 'item' already
  55.            exists this operation equals 
  56.           delete(tree,item);insert(tree,item)
  57.   *)
  58.   
  59.   PROCEDURE delete(tree:T; item:splayItem.T);
  60.   (* Pre: 'tree' has been created with 'create'
  61.      Post: If 'item' exists it has been removed from 'tree'
  62.            otherwise the tree is left untouched
  63.   *)
  64.   
  65.   PROCEDURE find(tree:T; item:splayItem.T; VAR found:splayItem.T):BOOLEAN;
  66.   (* Pre: 'tree' has been created with 'create'
  67.      Post: If 'item' exists in 'tree' 'found' has been assigned
  68.            to the corresponding data in 'tree'.
  69.        Note: The reason for returning the same item searched
  70.              for is to make it possible to specify an incomplete
  71.          search structure and then get the full structure
  72.          returned.
  73.      Returns: TRUE if 'item' exist, FALSE otherwise
  74.   *)
  75.   
  76.   PROCEDURE nbrElem(tree:T): CARDINAL;
  77.   (* Pre: 'tree' has been created with 'create'
  78.      Returns: The number of elements in 'tree'
  79.   *)
  80.   
  81.   PROCEDURE getRankElement(tree:T; r:CARDINAL; VAR found:splayItem.T): BOOLEAN;
  82.   (* Pre: 'tree' has been created with 'create'
  83.      Post: The 'item' with rank 'r' has been assigned to 'found'
  84.      Returns: TRUE if 'item' exist, FALSE otherwise
  85.   *)
  86.   
  87.   PROCEDURE getRank(tree:T; item:splayItem.T):CARDINAL;
  88.   (* Pre: 'tree' has been created with 'create'
  89.      Returns: The rank of element 'item'. If 'item' wasn't 
  90.               found the routine returns 0 
  91.   *)
  92.   
  93.   PROCEDURE mapIn(tree:T; f:auxFunc);
  94.   (* Pre: 'tree' has been created with 'create'
  95.      Post: The 'f' procedure has been applied to all elements in
  96.            'tree' according to a tree-inorder walk
  97.   *)
  98.   
  99.   PROCEDURE mapPre(tree:T; f:auxFunc);
  100.   (* Pre: 'tree' has been created with 'create'
  101.      Post: The 'f' procedure has been applied to all elements in
  102.            'tree' according to a tree-preorder walk
  103.   *)
  104.   
  105.   PROCEDURE mapPos(tree:T; f:auxFunc); 
  106.   (* Pre: 'tree' has been created with 'create'
  107.      Post: The 'f' procedure has been applied to all elements in
  108.            'tree' according to a tree-preorder walk
  109.   *)
  110.  
  111. END splay.
  112.