tests/merge_sort.pcc

   1 ///////////////////////////////////////////////////////////////////////////////
   2 //
   3 //  Test garbage collection by merge sorting a list in reverse sorted
   4 //  order.
   5 //
   6 ///////////////////////////////////////////////////////////////////////////////
   7
   8 #include <iostream.h>
   9 #include <AD/gc/gc.h>
  10
  11 //  A collectable integer list
  12
  13 datatype List :: collectable = #[] | #[ int ... List ];
  14
  15 //  Instantiate the list datatype
  16
  17 instantiate datatype List;
  18
  19 //  Pretty print a list
  20
  21 ostream& operator << (ostream& f, List l)
  22 {  match (l)
  23    {  #[]:             { return f; }
  24    |  #[one]:          { return f << one; }
  25    |  #[one ... rest]: { return f << one << ", " << rest; }
  26    }
  27 }
  28
  29 extern List merge (List, List);
  30 extern List sort  (List);
  31
  32 List merge (List a, List b)
  33 {  match (a) and (b)
  34    {  #[],        b:                   { return b; }
  35    |  a,          #[]:                 { return a; }
  36    |  #[u ... v], #[w ... x] | u <= w: { return #[u ... merge(v,b)]; }
  37    |  #[u ... v], #[w ... x]:          { return #[w ... merge(a,x)]; }
  38    }
  39 }
  40
  41 //  Sort a list
  42
  43 List sort (List l)
  44 {  match (l)
  45    {  #[] || #[_]: { return l; }
  46    |  _:           { List a = #[];
  47                      List b = #[];
  48                      match while (l)
  49                      {  #[x, y ... t]:  { a = #[x...a]; b = #[y...b]; l = t; }
  50                      |  #[x]:           { a = #[x...a]; l = #[]; }
  51                      }
  52                      return merge(sort(a), sort(b));
  53                    }
  54    }
  55 }
  56
  57 //  Create a list from hi to lo in descending order
  58
  59 List range (int hi, int lo)
  60 {  return hi < lo ? #[] : #[hi ... range(hi-1,lo)]; }
  61
  62 //  Sorting the list #[10000, 9999, 9998 ... 1]
  63 //  Use 1 megabyte for heap space.
  64
  65 int main()
  66 {  GC::get_default_gc().set_initial_heap_size(1024*1024);
  67    List l = range(10000,1);
  68    cout << sort(l) << '\n';
  69    GC::get_default_gc().print_statistics(cout);
  70    return 0;
  71 }