home *** CD-ROM | disk | FTP | other *** search
/ ftp.barnyard.co.uk / 2015.02.ftp.barnyard.co.uk.tar / ftp.barnyard.co.uk / cpm / walnut-creek-CDROM / CPM / LANGUAGS / MODULA2 / MTMOD2.LBR / MTPTR.MZD / MTPTR.MOD
Text File  |  2000-06-30  |  3KB  |  104 lines
  1. MODULE MTPtr;
  2.  
  3. (*---------------------------------------------*)
  4. (* Program to measure the speed of:            *)
  5. (*                                             *)
  6. (* 1) Allocating dynamic binary-tree structure *)
  7. (*                                             *)
  8. (* 2) Searching through the binary-tree        *)
  9. (*---------------------------------------------*)
  10.  
  11. FROM InOut IMPORT WriteString, WriteLn, Read, Write;
  12. FROM SYSTEM IMPORT TSIZE;
  13. FROM Storage IMPORT ALLOCATE;
  14. FROM MathLib0 IMPORT sin, entier;
  15.  
  16. CONST SIZE = 1000;
  17.       MainLoopCount = 30;
  18.  
  19. TYPE Ptr =  POINTER TO Node;
  20.  
  21.      Node = RECORD 
  22.               Value : INTEGER;
  23.               Left, Right : Ptr;
  24.             END;
  25.  
  26. VAR Numbers : ARRAY [1..SIZE] OF INTEGER;
  27.     Iter, I : CARDINAL;
  28.     TreeRoot : Ptr;
  29.     Pi : REAL;    
  30.     dummy : CHAR;
  31.  
  32. PROCEDURE Create;
  33. (* Create array using sin() *)
  34. VAR J : CARDINAL;
  35.     Angle, FloatSize, Increment : REAL;
  36.  
  37. BEGIN 
  38.     Angle := 0.0; 
  39.     J := 1; 
  40.     Increment := Pi / 360.0;
  41.     FloatSize := FLOAT(SIZE);
  42.     WHILE J <= SIZE DO 
  43.         Numbers[J] := entier(sin(Angle) * FloatSize);
  44.         Angle := Angle + Increment;
  45.         INC(J);
  46.     END;
  47. END Create;
  48.  
  49. PROCEDURE Insert(VAR Root : Ptr; Item : INTEGER);
  50. (* Insert element in binary-tree *)
  51. BEGIN
  52.     IF Root = NIL THEN 
  53.         ALLOCATE(Root,TSIZE(Node));
  54.         Root^.Value := Item;
  55.         Root^.Left := NIL;
  56.         Root^.Right := NIL
  57.     ELSE 
  58.         WITH Root^ DO
  59.             IF Item < Value THEN Insert(Left,Item)
  60.                             ELSE Insert(Right,Item)
  61.             END;
  62.         END;
  63.     END;
  64. END Insert;
  65.  
  66.  
  67. PROCEDURE Search(VAR Root : Ptr; Target : INTEGER);
  68. (* Recursive procedure to search for Target value *)
  69. BEGIN
  70.     IF Root <> NIL THEN 
  71.         IF Target <> Root^.Value THEN 
  72.             IF Target < Root^.Value THEN 
  73.                 Root := Root^.Left; Search(Root,Target)
  74.             ELSE 
  75.                 Root := Root^.Right; Search(Root,Target)
  76.             END
  77.         END;
  78.     END;
  79. END Search;
  80.  
  81. BEGIN (* MAIN *)
  82.     Pi := 355. / 113.;
  83.     Create;
  84.     WriteString('Created array'); WriteLn;
  85.     (* Building the binary tree *)
  86.     WriteString('Press <CR> to time tree creation '); WriteLn;
  87.     Read(dummy);
  88.     NEW(TreeRoot);
  89.     TreeRoot := NIL;
  90.     FOR I := 1 TO SIZE DO
  91.        Insert(TreeRoot,Numbers[I]);
  92.     END; (* FOR I *)
  93.     WriteLn;
  94.     WriteString('Created Tree'); WriteLn;
  95.     WriteString('Press <CR> to time tree search'); WriteLn;
  96.     Read(dummy); WriteLn;
  97.     FOR Iter := 1 TO MainLoopCount DO
  98.         FOR I := SIZE TO 1 BY -1 DO
  99.             Search(TreeRoot,Numbers[I]);
  100.         END; (* FOR I *)
  101.     END; (* FOR Iter *)
  102.     WriteLn;
  103.     WriteString('DONE'); WriteLn;
  104. END MTPtr.