basis/heaps/heaps-tests.factor

   1 ! Copyright 2007, 2008 Ryan Murphy, Slava Pestov
   2 ! See http://factorcode.org/license.txt for BSD license.
   3 USING: arrays kernel math namespaces tools.test
   4 heaps heaps.private math.parser random assocs sequences sorting
   5 accessors math.order ;
   6 IN: heaps.tests
   7
   8 [ <min-heap> heap-pop ] must-fail
   9 [ <max-heap> heap-pop ] must-fail
  10
  11 [ t ] [ <min-heap> heap-empty? ] unit-test
  12 [ f ] [ <min-heap> 1 t pick heap-push heap-empty? ] unit-test
  13 [ t ] [ <max-heap> heap-empty? ] unit-test
  14 [ f ] [ <max-heap> 1 t pick heap-push heap-empty? ] unit-test
  15
  16 ! Binary Min Heap
  17 { 1 2 3 4 5 6 } [ 0 left 0 right 1 left 1 right 2 left 2 right ] unit-test
  18 { t } [ t 5 f <entry> t 3 f <entry> T{ min-heap } heap-compare ] unit-test
  19 { f } [ t 5 f <entry> t 3 f <entry> T{ max-heap } heap-compare ] unit-test
  20
  21 [ t 2 ] [ <min-heap> t 300 pick heap-push t 200 pick heap-push t 400 pick heap-push t 3 pick heap-push t 2 pick heap-push heap-pop ] unit-test
  22
  23 [ t 1 ] [ <min-heap> t 300 pick heap-push t 200 pick heap-push t 400 pick heap-push t 3 pick heap-push t 2 pick heap-push t 1 pick heap-push heap-pop ] unit-test
  24
  25 [ t 400 ] [ <max-heap> t 300 pick heap-push t 200 pick heap-push t 400 pick heap-push t 3 pick heap-push t 2 pick heap-push t 1 pick heap-push heap-pop ] unit-test
  26
  27 [ 0 ] [ <max-heap> heap-size ] unit-test
  28 [ 1 ] [ <max-heap> t 1 pick heap-push heap-size ] unit-test
  29
  30 : heap-sort ( alist -- keys )
  31     <min-heap> [ heap-push-all ] keep heap-pop-all ;
  32
  33 : random-alist ( n -- alist )
  34     [
  35         [
  36             32 random-bits dup number>string swap set
  37         ] times
  38     ] H{ } make-assoc ;
  39
  40 : test-heap-sort ( n -- ? )
  41     random-alist dup >alist sort-keys swap heap-sort = ;
  42
  43 14 [
  44     [ t ] swap [ 2^ test-heap-sort ] curry unit-test
  45 ] each
  46
  47 : test-entry-indices ( n -- ? )
  48     random-alist
  49     <min-heap> [ heap-push-all ] keep
  50     data>> dup length swap [ index>> ] map sequence= ;
  51
  52 14 [
  53     [ t ] swap [ 2^ test-entry-indices ] curry unit-test
  54 ] each
  55
  56 : sort-entries ( entries -- entries' )
  57     [ [ key>> ] compare ] sort ;
  58
  59 : delete-test ( n -- ? )
  60     [
  61         random-alist
  62         <min-heap> [ heap-push-all ] keep
  63         dup data>> clone swap
  64     ] keep 3 /i [ 2dup >r delete-random r> heap-delete ] times
  65     data>>
  66     [ [ key>> ] map ] bi@
  67     [ natural-sort ] bi@ ;
  68
  69 11 [
  70     [ t ] swap [ 2^ delete-test sequence= ] curry unit-test
  71 ] each