home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1994 January / usenetsourcesnewsgroupsinfomagicjanuary1994.iso / sources / misc / volume35 / m2-splay22 / part01 / splay.mod < prev    next >
Text File  |  1993-01-20  |  16KB  |  588 lines
  1. IMPLEMENTATION MODULE splay;
  2. (*
  3.     Title:        Implementation of splay trees
  4.     Last Edit:    Mon Dec 21 13:20:38 1992
  5.     Author:        Johan Persson at my16
  6.  
  7.     SCCS:        @(#)splay.mod       2.2     92/12/21    
  8.     
  9.         
  10.     Description:    This code implements splay tree as described in 
  11.                     Sleator D. and Tarjan R. "Self adjusting
  12.             binary trees", JACM Vol 32. No 3, 1985, pp 652-
  13.             686.
  14.             
  15.             The implemenation is based on a top down
  16.                         splaying heuristics as described in section 4 of 
  17.             the article.
  18.  
  19.     Note:        This implementation also supports the operations
  20.             'getRankElement' which finds the element in the tree
  21.             with a given rank in O(lgn) time) and 'getRank', 
  22.             (which returns the rank of a given element)
  23.             To achive this one must store the weight of a node in
  24.             each node (i.e the number of descadents). The
  25.             update of this information after each basic 
  26.             operation takes O(lgn) time.
  27.  
  28.             To maintain this weight it's necessary to use a
  29.             stack, since the size of the stack is 
  30.             specified at compile time this may cause a checked 
  31.             run time error if the bounds of this stack is 
  32.                 violated. 
  33.  
  34.             See 'splay.def' for a complete description
  35.             of all procedures.
  36. *)
  37.  
  38.   IMPORT SYSTEM,Storage,splayItem,error; 
  39.    
  40.   TYPE
  41.      T = POINTER TO head;
  42.      Tree = POINTER TO treeNode;
  43.      treeNode = RECORD
  44.            l,r:Tree;          (* left and right links   *)
  45.            data:splayItem.T;      (* stored item            *)
  46.            weight:CARDINAL;      (* number of nodes in subtrees *)
  47.         END (* record *);         
  48.         
  49.      cmpFunc = PROCEDURE (splayItem.T, splayItem.T) : CARDINAL;
  50.     
  51.      head = RECORD
  52.             t : Tree;
  53.           nbr : CARDINAL;   
  54.         END (* record *);
  55.         
  56.     CONST 
  57.       stackSize =  10000;
  58.               
  59.     VAR 
  60.          ls : ARRAY [0..stackSize] OF Tree;
  61.          rs : ARRAY [0..stackSize] OF Tree;
  62.      lp,rp : CARDINAL;
  63.  
  64.  
  65.     PROCEDURE create(VAR tree:T);
  66.        BEGIN (* create *)
  67.          Storage.ALLOCATE(tree,SIZE(head));
  68.      tree^.t := NIL;
  69.      tree^.nbr := 0;
  70.        END create;
  71.  
  72.  
  73.   PROCEDURE destroy(VAR tree:T);
  74.      PROCEDURE des(t:Tree);
  75.        BEGIN (* des *)
  76.      IF t # NIL THEN 
  77.         des(t^.l);
  78.         des(t^.r);
  79.         splayItem.destroy(t^.data);
  80.         Storage.DEALLOCATE(t,SIZE(treeNode));
  81.      END (* if *);
  82.        END des;
  83.      BEGIN (* destroy *)
  84.        des(tree^.t); 
  85.        Storage.DEALLOCATE(tree,SIZE(head));
  86.        tree := NIL;
  87.      END destroy;
  88.   
  89.    PROCEDURE nbrElem(tree:T): CARDINAL; 
  90.       BEGIN
  91.          RETURN tree^.nbr;
  92.       END nbrElem;
  93.      
  94. (* *)
  95.   PROCEDURE insert(tree:T; item:splayItem.T);
  96.      VAR n,nn,l,r,node:Tree;
  97.          i:CARDINAL;
  98.      BEGIN (* insert *)
  99.        Storage.ALLOCATE(node,SIZE(treeNode));
  100.        node^.data := item; 
  101.        n := tree^.t;
  102.        lp:=0;rp:=0;ls[0]:=NIL;rs[0]:=NIL;
  103.        tree^.t := node;
  104.        IF n = NIL THEN
  105.             node^.l:=NIL; node^.r:=NIL;
  106.        ELSE 
  107.             l:=node; r:=node;
  108.      ls[0]:=l; rs[0]:=r;
  109.      LOOP 
  110.        IF l#ls[lp] THEN INC(lp);
  111.          IF lp>stackSize THEN error.raise("Internal error splay(insert):\n");HALT;
  112.          ELSE ls[lp]:=l; END;
  113.        END;
  114.        IF r#rs[rp] THEN INC(rp); 
  115.          IF rp>stackSize THEN error.raise("Internal error splay(insert):\n");HALT;
  116.          ELSE rs[rp]:=r; END;
  117.        END;
  118.      
  119.        IF splayItem.cmp(item,n^.data) < 0 THEN 
  120.          nn := n^.l;
  121.          IF nn=NIL THEN r^.l := n; l^.r := NIL; EXIT;
  122.          ELSIF splayItem.cmp(item,nn^.data) >= 0 THEN 
  123.            r^.l := n; r := n; 
  124.            l^.r := nn; l := nn;
  125.            n := nn^.r;
  126.            IF n=NIL THEN r^.l:=NIL; EXIT; END;
  127.          ELSE (* item < data *)
  128.            n^.l := nn^.r;
  129.            r^.l := nn;
  130.            nn^.r := n;
  131.            r := nn;
  132.            n := nn^.l;
  133.            IF n = NIL THEN l^.r := NIL; EXIT; END;
  134.          END (* if *);
  135.        ELSE (* item >= data *)   
  136.          nn := n^.r;
  137.          IF nn=NIL THEN l^.r := n; r^.l := NIL; EXIT;
  138.          ELSIF splayItem.cmp(item,nn^.data) < 0 THEN 
  139.            l^.r := n; l := n; 
  140.            r^.l := nn; r:=nn;
  141.            n := nn^.l;
  142.            IF n=NIL THEN l^.r:=NIL; EXIT; END;
  143.          ELSE (* item >= data *)
  144.            n^.r := nn^.l;
  145.            l^.r := nn;
  146.            nn^.l := n;
  147.            l := nn;
  148.            n := nn^.r;
  149.            IF n=NIL THEN r^.l := NIL; EXIT; END;
  150.          END (* if *)
  151.        END (* if *);
  152.      END (* loop *);
  153.      IF l#ls[lp] THEN INC(lp); ls[lp]:=l; END;
  154.      IF r#rs[rp] THEN INC(rp); rs[rp]:=r; END; 
  155.      (*
  156.      ** Now, walk back up the left AND right built tree, i.e all nodes
  157.      ** that are smaller (and bigger) than the node searched for, 
  158.      ** and update all weights. This is done using an explicit stack ls
  159.      ** and lr.
  160.      *) 
  161.      FOR i := lp TO 0 BY -1 DO
  162.         n:=ls[i]; n^.weight:=1;
  163.         nn:=n^.l;
  164.         IF nn#NIL THEN 
  165.            nn^.weight:=1;           
  166.            IF nn^.l#NIL THEN nn^.weight:=nn^.weight+nn^.l^.weight; END;
  167.            IF nn^.r#NIL THEN nn^.weight:=nn^.weight+nn^.r^.weight; END;
  168.            n^.weight:=n^.weight+nn^.weight; 
  169.         END;
  170.         nn:=n^.r;
  171.         IF nn#NIL THEN n^.weight:=n^.weight+nn^.weight; END;
  172.      END (* for *);
  173.      
  174.      FOR i := rp TO 0 BY -1 DO
  175.         n:=rs[i]; n^.weight:=1;
  176.         nn:=n^.r;
  177.         IF nn#NIL THEN 
  178.            nn^.weight:=1;
  179.            IF nn^.l#NIL THEN nn^.weight:=nn^.weight+nn^.l^.weight; END;
  180.            IF nn^.r#NIL THEN nn^.weight:=nn^.weight+nn^.r^.weight; END;
  181.            n^.weight:=n^.weight+nn^.weight; 
  182.         END;
  183.         nn:=n^.l;
  184.         IF nn#NIL THEN n^.weight:=n^.weight+nn^.weight; END;
  185.      END (* for *); 
  186.      
  187.      nn := node^.r;
  188.      node^.r := node^.l;
  189.      node^.l := nn;
  190.        END (* if empty tree*);
  191.        INC(tree^.nbr);
  192.      END insert;
  193.  
  194. (*   *)
  195.  
  196.   PROCEDURE delete(tree:T; item:splayItem.T);
  197.      VAR l,r,nnn,nn,n,pnn:Tree;
  198.          left,right:treeNode;
  199.          fFound:BOOLEAN;
  200.      i:CARDINAL;
  201.      PROCEDURE replace(VAR p:Tree; n:Tree);
  202.         VAR r,pr:Tree;
  203.         BEGIN (* replace *)
  204.            r:=n^.l;
  205.        IF r=NIL THEN p:=n^.r;
  206.        ELSE 
  207.           IF r^.r=NIL THEN p:=r; p^.r:=n^.r;
  208.           ELSE 
  209.              WHILE r^.r#NIL DO DEC(r^.weight); pr:=r; r:=r^.r; END;
  210.              pr^.r:=r^.l;
  211.              r^.l:=n^.l; r^.r:=n^.r;
  212.              p:=r;
  213.           END;
  214.        END (* if *);
  215.        splayItem.destroy(n^.data);
  216.        Storage.DEALLOCATE(n,SIZE(treeNode));
  217.        DEC(tree^.nbr);
  218.         END replace;
  219.       PROCEDURE fixWeight(n:Tree);
  220.     VAR nn:Tree;   
  221.     BEGIN (* fixWeight *)
  222.         n^.weight:=1;
  223.         nn:=n^.r;
  224.         IF nn#NIL THEN 
  225.            nn^.weight:=1;
  226.            IF nn^.l#NIL THEN INC(nn^.weight,nn^.l^.weight); END;
  227.            IF nn^.r#NIL THEN INC(nn^.weight,nn^.r^.weight); END;
  228.            INC(n^.weight,nn^.weight);
  229.         END;
  230.         nn:=n^.l;
  231.         IF nn#NIL THEN 
  232.            nn^.weight:=1;
  233.            IF nn^.l#NIL THEN INC(nn^.weight,nn^.l^.weight); END;
  234.            IF nn^.r#NIL THEN INC(nn^.weight,nn^.r^.weight); END;
  235.            INC(n^.weight,nn^.weight); 
  236.         END;
  237.     END fixWeight;
  238.     
  239.      BEGIN (* delete *) 
  240.         l:=SYSTEM.ADR(left); r:=SYSTEM.ADR(right);
  241.     l^.l:=NIL; l^.r:=NIL;
  242.     r^.l:=NIL; r^.r:=NIL;
  243.         lp:=0;rp:=0;ls[0]:=l;rs[0]:=r;
  244.         n := tree^.t;
  245.     IF n=NIL THEN RETURN;
  246.     ELSIF splayItem.cmp(n^.data,item)=0 THEN replace(tree^.t,n);
  247.     ELSE
  248.        LOOP
  249.           IF l#ls[lp] THEN INC(lp);
  250.             IF lp>stackSize THEN error.raise("Internal error splay(delete):\n");HALT;
  251.             ELSE ls[lp]:=l; END;
  252.           END;
  253.           IF r#rs[rp] THEN INC(rp); 
  254.             IF rp>stackSize THEN error.raise("Internal error/delete):\n");HALT;
  255.             ELSE rs[rp]:=r; END;
  256.           END;
  257.        
  258.           IF splayItem.cmp(item,n^.data)<0 THEN
  259.              nn:=n^.l;
  260.          IF nn=NIL THEN EXIT;
  261.          ELSE 
  262.             IF splayItem.cmp(item,nn^.data)=0 THEN 
  263.                replace(n^.l,nn);
  264.                EXIT;  
  265.             ELSIF splayItem.cmp(item,nn^.data)<0 THEN 
  266.                nnn:=nn^.l;
  267.                IF nnn#NIL THEN
  268.                      IF splayItem.cmp(item,nnn^.data)=0 THEN
  269.                  replace(nn^.l,nnn);
  270.                  r^.l:=n; r:=n; n:=nn;
  271.                  EXIT;
  272.               ELSE (* case III *) 
  273.                  n^.l:=nn^.r;
  274.                  r^.l:=nn; r:=nn; 
  275.                  nn^.r:=n;
  276.                  n:=nnn;
  277.               END (* if *);
  278.                ELSE (* nnn=NIL *)
  279.                      r^.l:=n; r:=n; n:=nn;
  280.               EXIT;
  281.                END (* if nnn#NIL *);
  282.             ELSE (* item > n^.data *)
  283.                nnn:=nn^.r;
  284.                IF nnn#NIL THEN
  285.                   IF splayItem.cmp(item,nnn^.data)=0 THEN
  286.                  replace(nn^.r,nnn);
  287.                  r^.l:=n; r:=n; n:=nn;
  288.                  EXIT;
  289.               ELSE (* case V *)
  290.                  l^.r:=nn; l:=nn;
  291.                  r^.l:=n; r:=n;
  292.                  n:=nnn;
  293.               END (* if *);
  294.                ELSE (* nnn=NIL *)
  295.               r^.l:=n; r:=n; n:=nn;
  296.               EXIT;
  297.                END (* if nnn#NIL *);
  298.             END (* if *);
  299.          END (* if nn#NIL  *);
  300.           ELSE (* item>n^.data *)
  301.                nn:=n^.r;
  302.          IF nn=NIL THEN EXIT;
  303.          ELSE 
  304.             IF splayItem.cmp(item,nn^.data)=0 THEN 
  305.                replace(n^.r,nn);
  306.                EXIT;  
  307.             ELSIF splayItem.cmp(item,nn^.data)>0 THEN 
  308.                nnn:=nn^.r;
  309.                IF nnn#NIL THEN
  310.                      IF splayItem.cmp(item,nnn^.data)=0 THEN
  311.                  replace(nn^.r,nnn);
  312.                  l^.r:=n; l:=n; n:=nn;
  313.                  EXIT;
  314.               ELSE (* case IV *)
  315.                  n^.r:=nn^.l;
  316.                  l^.r:=nn; l:=nn;
  317.                  nn^.l:=n;
  318.                  n:=nnn;
  319.               END (* if *);
  320.                ELSE (* nnn=NIL *)
  321.               l^.r:=n; l:=n; n:=nn;
  322.               EXIT;
  323.                END (* if nnn#NIL *);
  324.             ELSE (* item < n^.data *)
  325.                nnn:=nn^.l;
  326.                IF nnn#NIL THEN
  327.                   IF splayItem.cmp(item,nnn^.data)=0 THEN
  328.                  replace(nn^.l,nnn);
  329.                  l^.r:=n; l:=n; n:=nn;
  330.                  EXIT;
  331.               ELSE (* case VI *)
  332.                  l^.r:=n; l:=n;
  333.                  r^.l:=nn; r:=nn;
  334.                  n:=nnn;
  335.               END (* if *);
  336.                ELSE (* nnn=NIL *)
  337.               l^.r:=n; l:=n; n:=nn;
  338.               EXIT;
  339.                END (* if nnn#NIL *);
  340.             END (* if *);
  341.          END (* if nn#nil *);
  342.           END (* if *);
  343.        END (* loop *);
  344.        IF l#ls[lp] THEN INC(lp); ls[lp]:=l; END;
  345.        IF r#rs[rp] THEN INC(rp); rs[rp]:=r; END; 
  346.        l^.r:=n^.l; r^.l:=n^.r; 
  347.        n^.l:=left.r; n^.r:=right.l;
  348.        tree^.t:=n;
  349.      (*
  350.      ** Now, walk back up the left AND right built tree, i.e all nodes
  351.      ** that are smaller (and bigger) than the node searched for, 
  352.      ** and update all weights. This is done using an explicit stack ls
  353.      ** and lr.
  354.      *) 
  355.           
  356.        FOR i := lp TO 1 BY -1 DO
  357.          fixWeight(ls[i]);
  358.        END (* for *);
  359.        FOR i := rp TO 1 BY -1 DO
  360.          fixWeight(rs[i]);
  361.        END (* for *); 
  362.     END;
  363.     IF tree^.t#NIL THEN fixWeight(tree^.t); END;
  364.      END delete;
  365.  
  366.  
  367. (*   *)
  368.   PROCEDURE find(tree:T; item:splayItem.T;VAR found:splayItem.T): BOOLEAN;
  369.      VAR l,r,nnn,nn,n:Tree;
  370.          left,right:treeNode;
  371.          fFound : BOOLEAN;
  372.      i:CARDINAL;
  373.      BEGIN (* find *)
  374.         l:=SYSTEM.ADR(left); r:=SYSTEM.ADR(right);
  375.     l^.l:=NIL; l^.r:=NIL;
  376.     r^.l:=NIL; r^.r:=NIL;
  377.     
  378.     fFound:=FALSE;
  379.         n := tree^.t;
  380.     lp:=0;rp:=0;ls[0]:=l;rs[0]:=r;
  381.     IF n=NIL THEN RETURN FALSE;
  382.     ELSIF splayItem.cmp(n^.data,item)=0 THEN
  383.        found:=n^.data; 
  384.        RETURN TRUE;
  385.     ELSE
  386.        LOOP
  387.           IF l#ls[lp] THEN INC(lp);
  388.             IF lp>stackSize THEN error.raise("Internal error splay(find):\n");HALT;
  389.             ELSE ls[lp]:=l; END;
  390.           END;
  391.           IF r#rs[rp] THEN INC(rp); 
  392.             IF rp>stackSize THEN error.raise("Internal error splay(find):\n");HALT;
  393.             ELSE rs[rp]:=r; END;
  394.           END;
  395.        
  396.           IF splayItem.cmp(item,n^.data)=0 THEN
  397.              found:=n^.data; fFound:=TRUE;
  398.          EXIT;
  399.           ELSIF splayItem.cmp(item,n^.data)<0 THEN
  400.              nn:=n^.l;
  401.          IF nn=NIL THEN EXIT;
  402.          ELSE 
  403.             IF splayItem.cmp(item,nn^.data)=0 THEN  (* case I   *)
  404.                r^.l:=n; r:=n; n:=nn;
  405.                found:=n^.data; fFound:=TRUE;
  406.                EXIT;  
  407.             ELSIF splayItem.cmp(item,nn^.data)<0 THEN 
  408.                nnn:=nn^.l;
  409.                IF nnn#NIL THEN                  (* case III *)
  410.               n^.l:=nn^.r;
  411.               r^.l:=nn; r:=nn; 
  412.               nn^.r:=n; n:=nnn;
  413.                ELSE (* nnn=NIL *)
  414.                      r^.l:=n; r:=n; n:=nn;
  415.               EXIT;
  416.                END (* if nnn#NIL *);
  417.             ELSE (* item > nn^.data *)
  418.                nnn:=nn^.r;
  419.                IF nnn#NIL THEN                  (* case V   *)
  420.               l^.r:=nn; l:=nn;
  421.               r^.l:=n; r:=n; n:=nnn;
  422.                ELSE (* nnn=NIL *)
  423.               r^.l:=n; r:=n; n:=nn;
  424.               EXIT;
  425.                END (* if nnn#NIL *);
  426.             END (* if *);
  427.          END (* if nn#NIL  *);
  428.           ELSE (* item>n^.data *)
  429.                nn:=n^.r;
  430.          IF nn=NIL THEN EXIT;
  431.          ELSE 
  432.             IF splayItem.cmp(item,nn^.data)=0 THEN  (* case II  *)
  433.                l^.r:=n; l:=n; n:=nn;
  434.                found:=n^.data; fFound:=TRUE;
  435.                EXIT;  
  436.             ELSIF splayItem.cmp(item,nn^.data)>0 THEN 
  437.                nnn:=nn^.r;
  438.                IF nnn#NIL THEN                  (* case IV  *)
  439.               n^.r:=nn^.l;
  440.               l^.r:=nn; l:=nn;
  441.               nn^.l:=n; n:=nnn;
  442.                ELSE (* nnn=NIL *)
  443.               l^.r:=n; l:=n; n:=nn;
  444.               EXIT;
  445.                END (* if nnn#NIL *);
  446.             ELSE (* item < nn^.data *)
  447.                nnn:=nn^.l;
  448.                IF nnn#NIL THEN                  (* case VI  *)
  449.               l^.r:=n; l:=n;
  450.               r^.l:=nn; r:=nn; n:=nnn;
  451.                ELSE (* nnn=NIL *)
  452.               l^.r:=n; l:=n; n:=nn;
  453.               EXIT;
  454.                END (* if nnn#NIL *);
  455.             END (* if cmp(...) *);
  456.          END (* if nn=nil *);
  457.           END (* if cmp(...) *);
  458.        END (* loop *);
  459.        IF l#ls[lp] THEN INC(lp); ls[lp]:=l; END;
  460.        IF r#rs[rp] THEN INC(rp); rs[rp]:=r; END; 
  461.        
  462.        r^.l:=n^.r; l^.r:=n^.l; 
  463.        n^.l:=left.r; n^.r:=right.l; 
  464.        tree^.t:=n;
  465.      (*
  466.      ** Now, walk back up the left AND right built tree, i.e all nodes
  467.      ** that are smaller (and bigger) than the node searched for, 
  468.      ** and update all weights. This is done using an explicit stack ls
  469.      ** and lr.
  470.      *) 
  471.        
  472.        FOR i := lp TO 0 BY -1 DO
  473.         n:=ls[i]; n^.weight:=1;
  474.         nn:=n^.l;
  475.         IF nn#NIL THEN 
  476.            nn^.weight:=1;           
  477.            IF nn^.l#NIL THEN nn^.weight:=nn^.weight+nn^.l^.weight; END;
  478.            IF nn^.r#NIL THEN nn^.weight:=nn^.weight+nn^.r^.weight; END;
  479.            n^.weight:=n^.weight+nn^.weight; 
  480.         END;
  481.         nn:=n^.r;
  482.         IF nn#NIL THEN n^.weight:=n^.weight+nn^.weight; END; 
  483.        END (* for *);
  484.      
  485.        FOR i := rp TO 0 BY -1 DO
  486.          n:=rs[i]; n^.weight:=1;
  487.          nn:=n^.r;
  488.          IF nn#NIL THEN 
  489.            nn^.weight:=1;
  490.            IF nn^.l#NIL THEN nn^.weight:=nn^.weight+nn^.l^.weight; END;
  491.            IF nn^.r#NIL THEN nn^.weight:=nn^.weight+nn^.r^.weight; END;
  492.            n^.weight:=n^.weight+nn^.weight; 
  493.          END;
  494.          nn:=n^.l;
  495.          IF nn#NIL THEN n^.weight:=n^.weight+nn^.weight; END;
  496.        END (* for *); 
  497.     END;
  498.     RETURN fFound;      
  499.      END find;
  500.   
  501.  
  502.   PROCEDURE getRank(tree:T; item:splayItem.T): CARDINAL;
  503.      VAR t,p:Tree;rank:CARDINAL;
  504.      BEGIN (* getRank *)
  505.        t:=tree^.t;
  506.        p:=NIL;
  507.        rank:=1;
  508.        LOOP 
  509.          IF t = NIL THEN
  510.            RETURN 0;
  511.          ELSE 
  512.            IF splayItem.cmp(t^.data,item)=0 THEN 
  513.                IF t^.l # NIL THEN 
  514.                   RETURN rank+t^.l^.weight;
  515.                ELSE
  516.                   RETURN rank;
  517.                END;
  518.            ELSIF splayItem.cmp(t^.data,item) > 0  THEN 
  519.                p:=t;
  520.                t := t^.l;
  521.            ELSE
  522.                IF t^.l#NIL THEN  
  523.                   rank:=rank+t^.l^.weight+1;
  524.                ELSE 
  525.                   INC(rank);
  526.                END;
  527.                p:=t;
  528.                t := t^.r
  529.            END;
  530.          END (* if *);
  531.        END (* loop *);
  532.      END getRank;
  533.  
  534.   
  535.    PROCEDURE getRankElement(tree:T; r:CARDINAL; VAR found:splayItem.T):BOOLEAN;
  536.       VAR n:Tree;rank,weight:CARDINAL;
  537.       BEGIN (* getRankElement *)
  538.          n:=tree^.t;
  539.      rank:=0;
  540.      WHILE n#NIL DO
  541.        IF n^.l#NIL THEN weight:=n^.l^.weight+1;
  542.        ELSE weight:=1; END; 
  543.        IF r=rank+weight THEN
  544.          found:=n^.data;
  545.          RETURN TRUE;
  546.        ELSIF r<rank+weight THEN
  547.          n:=n^.l;
  548.        ELSE
  549.          rank:=rank+weight;
  550.          n:=n^.r; 
  551.        END (* if *);
  552.      END;
  553.      RETURN FALSE;
  554.       END getRankElement;
  555.       
  556.  
  557.   PROCEDURE mapIn(tree:T; f:auxFunc);
  558.      PROCEDURE mI(t:Tree);
  559.     BEGIN (* mI *)
  560.       IF t # NIL THEN mI(t^.l); f(t^.data); mI(t^.r); END;
  561.     END mI;
  562.      BEGIN (* mapIn *)
  563.        mI(tree^.t); 
  564.      END mapIn;
  565.  
  566.  
  567.   PROCEDURE mapPre(tree:T; f:auxFunc);
  568.      PROCEDURE mPr(t:Tree);
  569.     BEGIN (* mPr *)
  570.       IF t # NIL THEN f(t^.data); mPr(t^.l); mPr(t^.r); END;
  571.     END mPr;
  572.      BEGIN (* mapPre *)
  573.        mPr(tree^.t); 
  574.      END mapPre;
  575.  
  576.  
  577.   PROCEDURE mapPos(tree:T; f:auxFunc);
  578.      PROCEDURE mPo(t:Tree);
  579.     BEGIN (* mPo *)
  580.       IF t # NIL THEN mPo(t^.l); mPo(t^.r); f(t^.data); END;
  581.     END mPo;
  582.      BEGIN (* mapPos *)
  583.        mPo(tree^.t); 
  584.      END mapPos;
  585.  
  586. END splay.
  587.  
  588.