triple-ref-trick.a68

     
   1  COMMENT
   2  
   3  @section Synopsis
   4  
   5  The "Algol 68 triple-REF trick" implementation of quicksort.
   6  
   7  Identifier "place" in procedure "insert" has mode REF REF REF NODE. 
   8  This is one of the few practical examples of using a pointer to a 
   9  pointer to a pointer.
  10  
  11  COMMENT
  12  
  13  MODE NODE = STRUCT (REAL v, REF NODE less, more);
  14  REF NODE end = NIL;
  15  REF NODE root := end;
  16  
  17  PROC insert = (REAL v) VOID:
  18       BEGIN REF REF NODE place := root;
  19             WHILE place ISNT end
  20             DO place := (v < v OF place | less OF place | more OF place)
  21             OD;
  22             REF REF NODE (place) := HEAP NODE := (v, end, end)
  23       END;
  24  
  25  PROC print tree = (REF NODE n) VOID:
  26       IF n ISNT NIL
  27       THEN print tree (less OF n);
  28            print ((new line, fixed (v OF n, 10, 4)));
  29            print tree (more OF n)
  30       FI;
  31  
  32  TO 10
  33  DO insert (next random)
  34  OD;
  35  
  36  print tree (root)
     


© 2002-2024 J.M. van der Veer (jmvdveer@xs4all.nl)