home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / alt / sources / 2600 / splay.def < prev    next >
Encoding:
Modula Definition  |  1992-11-21  |  3.7 KB  |  110 lines
  1. DEFINITION MODULE splay;
  2. (*
  3.     Title:        Implementation of splay trees
  4.     Last Edit:    Sun Nov 22 13:43:23 1992
  5.     Author:        Johan Persson at my9
  6.  
  7.     SCCS:        @(#)splay.def       2.1     92/11/22
  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). This
  24.             information must be updated after each operation
  25.             (insert, delete, find). If this is to costly
  26.             (it takes O(n)) the source can be modified to remove
  27.             the call to 'fixRank' in 'insert', 'delete' and
  28.             'find'
  29.  
  30. *)
  31.  
  32.   IMPORT splayItem;
  33.  
  34.   TYPE
  35.      auxFunc = PROCEDURE (splayItem.T);
  36.      T;
  37.  
  38.   PROCEDURE create(VAR tree:T);
  39.   (* Post: The splay tree tree 'tree' has been created.
  40.   *)
  41.            
  42.   PROCEDURE destroy(VAR tree:T);
  43.   (* Pre: 'tree' has been created with 'create'
  44.      Post: All dynamic memory previously associated with 'tree'
  45.            have been returned. The 'del' function specified in
  46.        'create' has been called one time for each datum in the
  47.        tree. Upon completion 'tree' is no longer a valid tree.
  48.   *) 
  49.   
  50.   PROCEDURE insert(tree:T; item:splayItem.T);
  51.   (* Pre: 'tree' has been created with 'create'
  52.      Post: 'item' has been inserted in 'tree'. If the 'item' already
  53.            exists this operation equals 
  54.           delete(tree,item);insert(tree,item)
  55.   *)
  56.   
  57.   PROCEDURE delete(tree:T; item:splayItem.T);
  58.   (* Pre: 'tree' has been created with 'create'
  59.      Post: If 'item' exists it has been removed from 'tree'
  60.            otherwise the tree is left untouched
  61.   *)
  62.   
  63.   PROCEDURE find(tree:T; item:splayItem.T; VAR found:splayItem.T):BOOLEAN;
  64.   (* Pre: 'tree' has been created with 'create'
  65.      Post: If 'item' exists in 'tree' 'found' has been assigned
  66.            to the corresponding data in 'tree'.
  67.        Note: The reason for returning the same item searched
  68.              for is to make it possible to specify an incomplete
  69.          search structure and then get the full structure
  70.          returned.
  71.      Returns: TRUE if 'item' exist, FALSE otherwise
  72.   *)
  73.   
  74.   PROCEDURE nbrElem(tree:T): CARDINAL;
  75.   (* Pre: 'tree' has been created with 'create'
  76.      Returns: The number of elements in 'tree'
  77.   *)
  78.   
  79.   PROCEDURE getRankElement(tree:T; r:CARDINAL; VAR found:splayItem.T): BOOLEAN;
  80.   (* Pre: 'tree' has been created with 'create'
  81.      Post: The 'item' with rank 'r' has been assigned to 'found'
  82.      Returns: TRUE if 'item' exist, FALSE otherwise
  83.   *)
  84.   
  85.   PROCEDURE getRank(tree:T; item:splayItem.T):CARDINAL;
  86.   (* Pre: 'tree' has been created with 'create'
  87.      Returns: The rank of element 'item'. If 'item' wasn't 
  88.               found the routine returns 0 
  89.   *)
  90.   
  91.   PROCEDURE mapIn(tree:T; f:auxFunc);
  92.   (* Pre: 'tree' has been created with 'create'
  93.      Post: The 'f' procedure has been applied to all elements in
  94.            'tree' according to a tree-inorder walk
  95.   *)
  96.   
  97.   PROCEDURE mapPre(tree:T; f:auxFunc);
  98.   (* Pre: 'tree' has been created with 'create'
  99.      Post: The 'f' procedure has been applied to all elements in
  100.            'tree' according to a tree-preorder walk
  101.   *)
  102.   
  103.   PROCEDURE mapPos(tree:T; f:auxFunc); 
  104.   (* Pre: 'tree' has been created with 'create'
  105.      Post: The 'f' procedure has been applied to all elements in
  106.            'tree' according to a tree-preorder walk
  107.   *)
  108.  
  109. END splay.
  110.