extra/trees/splay/splay-tests.factor

   1 ! Copyright (c) 2005 Mackenzie Straight.
   2 ! See http://factorcode.org/license.txt for BSD license.
   3 USING: assocs fry grouping kernel math random sequences sets
   4 tools.test trees.splay ;
   5 IN: trees.splay.tests
   6
   7 : randomize-numeric-splay-tree ( splay-tree -- )
   8     100 <iota> [ drop 100 random of drop ] with each ;
   9
  10 : make-numeric-splay-tree ( n -- splay-tree )
  11     <iota> <splay> [ '[ dup _ set-at ] each ] keep ;
  12
  13 { t } [
  14     100 make-numeric-splay-tree dup randomize-numeric-splay-tree
  15     [ drop ] { } assoc>map [ < ] monotonic?
  16 ] unit-test
  17
  18 { 10 } [ 10 make-numeric-splay-tree keys length ] unit-test
  19 { 10 } [ 10 make-numeric-splay-tree values length ] unit-test
  20
  21 { f } [ <splay> f 4 pick set-at 4 of ] unit-test
  22
  23 ! Ensure that f can be a value
  24 { t } [ <splay> f 4 pick set-at 4 swap key? ] unit-test
  25
  26 {
  27     { { 1 "a" } { 2 "b" } { 3 "c" } { 4 "d" } { 5 "e" } { 6 "f" } }
  28 } [
  29     {
  30         { 4 "d" } { 5 "e" } { 6 "f" }
  31         { 1 "a" } { 2 "b" } { 3 "c" }
  32     } >splay >alist
  33 ] unit-test
  34
  35 { 0 } [
  36     100 <iota> [ dup zip >splay ] keep
  37     [ over delete-at ] each assoc-size
  38 ] unit-test
  39
  40 : test-tree ( -- tree )
  41     SPLAY{
  42         { 7 "seven" }
  43         { 9 "nine" }
  44         { 4 "four" }
  45         { 4 "replaced four" }
  46         { 7 "replaced seven" }
  47     } clone ;
  48
  49 ! test assoc-size
  50 { 3 } [ test-tree assoc-size ] unit-test
  51 { 2 } [ test-tree 9 over delete-at assoc-size ] unit-test
  52
  53 ! Test that converting trees doesn't give linked lists
  54 {
  55     SPLAY{ { 1 1 } { 3 3 } { 2 2 } }
  56 } [ SPLAY{ { 1 1 } { 3 3 } { 2 2 } } >splay ] unit-test