files/practicum/BinTreeTest.icl

   1 module BinTreeTest
   2
   3 /*      Test module BinTree
   4         Voor werken met Gast:
   5                 (*) gebruik Environment 'Gast'
   6                 (*) zet Project Options op 'Basic Values Only' en '2M' Maximum Heap Size
   7 */
   8
   9 import gast
  10 import BinTree
  11
  12 Start
  13                                                         = testn 1000
  14                                                                 (\n -> let n` = abs (n/2) in
  15                                                                    nodes_vs_leaves  n` /\
  16                                                                    leaves_vs_diepte n` /\
  17                                                                    True
  18                                                                 )
  19
  20 nodes_vs_leaves                         :: Int -> Property
  21 nodes_vs_leaves n                       = name "nodes_vs_leaves"
  22                                                           (nodes t == leaves t - 1)
  23 where           t                       = lego_tree n
  24
  25 leaves_vs_diepte                        :: Int -> Property
  26 leaves_vs_diepte n                      = name "leaves_vs_diepte"
  27                                                           (leaves t <= 2^(diepte t))
  28 where           t                       = lego_tree n
  29
  30 //      Function to construct semi-random trees, using those from BinTree:
  31 trees                                           =: [t0,t1,t2,t3,t4,t5,t6,t7]
  32 nr_of_trees                                     =: length trees
  33
  34 lego_tree                                       :: Int -> Tree Int
  35 lego_tree 0                                     = t0
  36 lego_tree n                                     = glue n (trees !! (n rem nr_of_trees)) (lego_tree (n/10))
  37 where
  38         glue                                    :: !Int !(Tree Int) !(Tree Int) -> Tree Int
  39         glue n t Leaf                   = t
  40         glue n t (Node x l r)
  41         | isEven n                              = Node x (glue (n/10) t l) r
  42         | otherwise                             = Node x l (glue (n/10) t r)