home *** CD-ROM | disk | FTP | other *** search
/ Aminet 18 / aminetcdnumber181997.iso / Aminet / dev / m2 / CycloneModules.lha / OOModules / txt / trees.mod < prev   
Text File  |  1996-05-17  |  4KB  |  204 lines
  1. IMPLEMENTATION MODULE Trees;
  2.  
  3. (* Copyright (C) 1996 by Marcel Timmermans *)
  4.  
  5. (* A example of a tree object *)
  6.  
  7. FROM SYSTEM IMPORT ADR,ADDRESS,BYTE,CAST;
  8. IMPORT H:Heap;
  9.  
  10.  
  11. PROCEDURE TTree.Compare(d:ADDRESS;node:NodePtr):INTEGER;
  12. BEGIN
  13.  RETURN 0;
  14. END TTree.Compare;
  15.  
  16. PROCEDURE TTree.FindComp(d:ADDRESS;node:NodePtr):INTEGER;
  17. BEGIN
  18.  RETURN Compare(d,node);
  19. END TTree.FindComp;
  20.  
  21. PROCEDURE TTree.DoProc(d:ADDRESS);
  22. BEGIN
  23. (*  Empty procedure *)
  24. END TTree.DoProc;
  25.  
  26. PROCEDURE TTree.NewItem(d:ADDRESS):NodePtr;
  27. VAR node:NodePtr;
  28. BEGIN
  29. (* io.WriteString('NewItem\n');*)
  30.  H.Allocate(node,SIZE(Node));
  31.  IF node#NIL THEN
  32.   WITH node^ DO
  33.    left:=NIL; right:=NIL; data:=d;
  34.   END;
  35.  END;
  36.  RETURN node;
  37. END TTree.NewItem;
  38.  
  39. PROCEDURE TTree.Remove(n:NodePtr):ADDRESS;
  40. VAR d:ADDRESS;
  41. BEGIN
  42.  d:=NIL;
  43.  IF n#NIL THEN
  44.   d:=n^.data;
  45.   H.Deallocate(n);
  46.  END;
  47.  RETURN d;
  48. END TTree.Remove;
  49.  
  50. PROCEDURE TTree.Insert(n:NodePtr;d:ADDRESS):NodePtr;
  51. BEGIN
  52. (* io.WriteString('Insert\n');*)
  53.  LOOP
  54.   IF n=NIL THEN EXIT; END;
  55.   IF (Compare(d,n)<0) THEN (* Element smaller *)
  56.     IF n^.left=NIL THEN
  57.        n^.left:=NewItem(d);
  58.        EXIT;
  59.     ELSE
  60.       n:=n^.left;
  61.     END;
  62.   ELSE
  63.     IF n^.right=NIL THEN
  64.       n^.right:=NewItem(d);
  65.       EXIT;
  66.     ELSE
  67.       n:=n^.right;
  68.     END;
  69.   END;
  70.  END;
  71.  RETURN n;
  72. END TTree.Insert;
  73.  
  74. PROCEDURE TTree.Find(n:NodePtr;d:ADDRESS):NodePtr;
  75. VAR s:INTEGER;
  76. BEGIN
  77.  s:=-1;
  78.  WHILE (n#NIL) & (s#cmpEqual) DO
  79.   s:=FindComp(d,n);
  80.   IF s=cmpLess THEN n:=n^.left;
  81.   ELSIF s=cmpMore THEN n:=n^.right;
  82.   ELSE s:=cmpEqual; END;
  83.  END;
  84.  RETURN n;
  85. END TTree.Find;
  86.  
  87. PROCEDURE TTree.Min(tree:NodePtr):NodePtr;
  88. BEGIN
  89.   WHILE (tree^.left#NIL) DO tree:=tree^.left; END;
  90.   RETURN tree;
  91. END TTree.Min;
  92.  
  93. PROCEDURE TTree.FindPred(head:NodePtr; d:ADDRESS; VAR Left:BOOLEAN):NodePtr;
  94. BEGIN
  95.  LOOP
  96.   IF head=NIL THEN 
  97.      EXIT; 
  98.   ELSIF (head^.left#NIL) & (Compare(d,head^.left)=cmpEqual) THEN
  99.      Left:=TRUE;
  100.      EXIT;
  101.   ELSIF (head^.right#NIL) & (Compare(d,head^.right)=cmpEqual) THEN
  102.      Left:=FALSE;
  103.      EXIT;
  104.   ELSIF (Compare(d,head)=cmpLess) THEN
  105.      head:=head^.left;
  106.   ELSIF (Compare(d,head)=cmpMore) THEN
  107.      head:=head^.right;
  108.   END;    
  109.  END;
  110.  RETURN head;
  111. END TTree.FindPred;
  112.  
  113. PROCEDURE TTree.Delete(n,del:NodePtr):NodePtr;
  114. VAR 
  115.  pred,new:NodePtr;
  116.  Left:BOOLEAN;
  117.  temp:POINTER TO NodePtr;
  118. BEGIN
  119.  IF (del#NIL) & (n#NIL) THEN
  120.    pred:=FindPred(n,del^.data,Left);
  121.    IF Left & (pred#NIL) THEN
  122.      temp:=ADR(pred^.left);
  123.    ELSIF (pred#NIL) THEN
  124.      temp:=ADR(pred^.right);
  125.    END;
  126.  
  127.    IF del^.left=NIL THEN
  128.      IF (pred#NIL) THEN 
  129.        temp^:=del^.right;
  130.      ELSE
  131.        n:=del^.right;
  132.      END;
  133.    ELSIF del^.right=NIL THEN
  134.      IF (pred#NIL) THEN
  135.        temp^:=del^.left;
  136.      ELSE
  137.        n:=del^.left;
  138.      END;
  139.    ELSE
  140.      (*io.WriteString('New delete\n');*)
  141.      new:=Min(del^.right);
  142.      n:=Self^.Delete(n,new);
  143.      IF (pred#NIL) THEN
  144.        temp^:=new;
  145.      ELSE
  146.       n:=new;
  147.      END;
  148.      new^.left:=del^.left;
  149.      new^.right:=del^.right;
  150.    END;
  151.  END;
  152.  RETURN n;
  153. END TTree.Delete;
  154.  
  155. PROCEDURE TTree.CountElements():LONGINT; 
  156.   PROCEDURE CntElements(n:NodePtr):LONGINT;
  157.   BEGIN
  158.    IF n=NIL THEN 
  159.      RETURN 0; 
  160.    ELSE 
  161.      RETURN CntElements(n^.left)+CntElements(n^.right)+1;
  162.    END;
  163.   END CntElements; 
  164. BEGIN
  165.  RETURN CntElements(root);
  166. END TTree.CountElements;
  167.  
  168. PROCEDURE TTree.WalkTree(t:NodePtr);
  169.  
  170.   PROCEDURE WlkTree(n:NodePtr);
  171.   BEGIN
  172.    IF (n^.left#NIL) THEN WlkTree(n^.left); END;
  173.    Self^.DoProc(n^.data);
  174.    IF (n^.right#NIL) THEN WlkTree(n^.right); END;
  175.   END WlkTree;
  176.  
  177. BEGIN
  178.  IF t#NIL THEN WlkTree(t); END;
  179. END TTree.WalkTree;
  180.  
  181. PROCEDURE TTree.FreeData(d:ADDRESS);
  182. BEGIN
  183.  (* emtpy method for freeing memory of the data *)
  184. END TTree.FreeData;
  185.  
  186. PROCEDURE TTree.DestroyTree(VAR t:NodePtr);
  187. VAR temp:NodePtr;
  188.  
  189.  PROCEDURE DelTree(n:NodePtr);
  190.  BEGIN
  191.   IF (n^.left#NIL) THEN DelTree(n^.left); END;
  192.   Self^.FreeData(n^.data);
  193.   temp:=n^.right;
  194.   H.Deallocate(n);
  195.   IF temp#NIL THEN DelTree(temp); END;
  196.  END DelTree;
  197.  
  198. BEGIN
  199.  IF t#NIL THEN DelTree(t); t:=NIL; END;
  200. END TTree.DestroyTree;
  201.  
  202. BEGIN
  203. END Trees.
  204.