lib/mlton/heap/test.sml

   1 (* Copyright (C) 1999-2006 Henry Cejtin, Matthew Fluet, Suresh
   2  *    Jagannathan, and Stephen Weeks.
   3  *
   4  * MLton is released under a BSD-style license.
   5  * See the file MLton-LICENSE for details.
   6  *)
   7
   8 local
   9    structure H = BinaryHeap(structure O = Int
  10                             open Int
  11                             fun inject x = x
  12                             fun project x = x
  13                             val largest = Int.maxInt
  14                             val smallest = Int.minInt)
  15    open H
  16    val h = new[(1, "1"), (2, "2"), (3, "3")]
  17    val _ =
  18       while not(isEmpty h) do
  19          (print(deleteMin h)
  20           ; print "\n")
  21 in
  22 end
  23
  24 structure IntegerHeap = FibonacciHeap(structure Key' = Integer)
  25
  26 open IntegerHeap ;
  27
  28 fun p h = output h Integer.output print
  29
  30 val h = new [(1, 1)] ;
  31
  32 val w = isWellFormed h ;
  33
  34 val _ = p h ;
  35
  36 fun i n = insert h n n ;
  37
  38 val _ = i 2 ;
  39
  40 val _ = i 3 ;
  41
  42 val h = new (ListUtil.reverse (ListUtil.map (ListUtil.fromTo 1 10)
  43                                (fn x => (x, x)))) ;
  44
  45 val _ = p h ;
  46
  47 val w = isWellFormed h ;
  48
  49 val a = min h ;
  50
  51 val a = deleteMin h ;
  52
  53 val b = deleteMin h ;
  54
  55 val c = deleteMin h ;
  56
  57 val l = ListUtil.map (ListUtil.fromTo 1 7) (fn _ => deleteMin h) ;
  58
  59 isEmpty h ;
  60
  61 insert h 100 100 ;
  62
  63 isEmpty h ;
  64
  65 min h ;
  66
  67 ListUtil.foreach (ListUtil.fromTo 1 10) (fn i =>
  68                                          (insert h (11 * i) (11 * i) ;
  69                                           ())) ;
  70
  71 min h ;
  72
  73 deleteMin h ;
  74
  75 isEmpty h ;
  76
  77 ListUtil.foreach (ListUtil.reverse (ListUtil.fromTo 1 1100))
  78 (fn i => (insert h i i ; ())) ;
  79
  80 ListUtil.foreach (ListUtil.fromTo 1 1098) (fn _ => (deleteMin h ; ())) ;
  81
  82
  83 insert h 11 11 ;
  84
  85 val _ = p h ;
  86
  87
  88 val h: int t = new [] ;
  89
  90 val elts = ListUtil.map (ListUtil.fromTo 0 9) (fn x => insert h x x) ;
  91
  92 val _ = p h ;
  93
  94 fun dc i = decreaseKey h (ListUtil.nth elts i)
  95 fun d i = delete h (ListUtil.nth elts i)
  96
  97 val _ = dc 6 ~1 ;
  98
  99    dc 7 0 ;
 100
 101 val a = deleteMin h ;
 102
 103 val _ = d 4 ;