tests/insertion_sort.pcc

   1 ///////////////////////////////////////////////////////////////////////////////
   2 //
   3 //  Test garbage collection by insertion 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 //  Insert x into the sorted list l
  30
  31 List insert (int x, List l)
  32 {  match (l)
  33    {  #[]:        { return #[x]; }
  34    |  #[h ... t]: { return h < x ? #[h ... insert(x,t)] : #[x ... l]; }
  35    }
  36 }
  37
  38 //  Sort a list
  39
  40 List sort (List l)
  41 {  match (l)
  42    {  #[] || #[_]: { return l; }
  43    |  #[h ... t]:  { return insert(h,sort(t)); }
  44    }
  45 }
  46
  47 //  Create a list from hi to lo in descending order
  48
  49 List range (int hi, int lo)
  50 {  return hi < lo ? #[] : #[hi ... range(hi-1,lo)]; }
  51
  52 //  Sorting the list #[1000, 999, 998 ... 1]
  53 //  Use 1 megabyte for heap space.
  54
  55 int main()
  56 {  GC::get_default_gc().set_initial_heap_size(1024*1024);
  57    List l = range(1000,1);
  58    cout << sort(l) << '\n';
  59    GC::get_default_gc().print_statistics(cout);
  60    return 0;
  61 }