tests/skiplist.slate

   1
   2 UnitTests addPrototype: #SkipList derivedFrom: {TestCase}.
   3
   4 tc@(UnitTests SkipList traits) isEmpty
   5 [
   6   sl ::= SkipList new.
   7   tc assert: sl isEmpty description: 'new SkipList states that it is empty'.
   8 ].
   9
  10 tc@(UnitTests SkipList traits) size
  11 [
  12   sl ::= SkipList new.
  13   tc assert: sl size = 0 description: 'empty SkipList has non-zero size'.
  14 ].
  15
  16 tc@(UnitTests SkipList traits) newPointerLength
  17 [
  18   sl ::= SkipList new.
  19   sum ::= 0.
  20   10 timesRepeat: [sum += sl newPointerLength].
  21   tc assert: (sum between: 15 and: 25) description:
  22     'pointerlength average is incorrect'.
  23 ].
  24
  25 tc@(UnitTests SkipList traits) forward
  26 [
  27   sln ::= SkipList Node clone.
  28   sln pointers: (sln pointers newSize: 5).
  29   0 upTo: 4 do: [| :i | sln pointers at: i put: i].
  30   0 upTo: 4 do: [| :i |
  31     tc assert: (sln forward: i) = i description: 'forward answers wrong value'.].
  32 ].
  33
  34 tc@(UnitTests SkipList traits) add
  35 [
  36   sl ::= SkipList new.
  37   sl add: 2.
  38   tc assert: (sl size) = 1 description: 'added one item but size is not one'.
  39   sl add: 5.
  40   tc assert: (sl size) = 2 description: 'could not add item at last place'.
  41   sl add: 1.
  42   tc assert: (sl size) = 3 description: 'added as first does not increase size'.
  43 ].
  44
  45 tc@(UnitTests SkipList traits) includes
  46 [
  47   sl ::= SkipList new.
  48   sl add: 2.
  49   tc assert: (sl includes: 2) description: 'first added object is not included'.
  50   sl add: 5.
  51   tc assert: (sl includes: 5) description: 'second added object is not included'.
  52   sl add: 1.
  53   tc assert: (sl includes: 1) description: 'added as first not included'.
  54   sl add: 3.
  55   tc assert: (sl includes: 3) description: 'inserted not included'.
  56   tc assert: (sl includes: 4) not description: 'includes unadded object'.
  57 ].
  58
  59 tc@(UnitTests SkipList traits) remove
  60 [
  61   sl ::= SkipList new.
  62   sl add: 4.
  63   sl remove: 4.
  64   tc assert: sl isEmpty description: 'not empty after add-remove'.
  65   0 upTo: 10 do: [| :i | sl add: i].
  66   tc assert: (sl size) = 11 description: 'pre-test check'.
  67   sl remove: 3.
  68   tc assert: (sl size) = 10 description: 'remove does not decrease size'.
  69   tc assert: (sl includes: 3) not description: 'found after removal'.
  70 ].
  71
  72 tc@(UnitTests SkipList traits) do
  73 [| sum counter |
  74   sl ::= SkipList new.
  75   0 upTo: 9 do: [| :i | sl add: i].
  76   sum := 0.
  77   sl do: [| :obj | obj < 5 ifTrue: [sum += obj]].
  78   tc assert: sum = 10 description: 'do on first elements failed'.
  79   sum := 0.
  80   sl do: [| :obj | obj > 4 ifTrue: [sum += obj]].
  81   tc assert: sum = 35 description: 'do on last elements failed'.
  82   sum := 0.
  83   counter := 0.
  84   sl do: [| :obj |
  85     obj < 5 /\ [counter < 5]
  86       ifTrue: [sum += obj. counter += 1]].
  87   tc assert: sum = 10 description: 'summed incorrect elements'.
  88 ].
  89
  90 tc@(UnitTests SkipList traits) reverseDoAndSequence
  91 "Test reverseDo and sequence of elements."
  92 [| sum counter |
  93   sl ::= SkipList new.
  94   0 upTo: 9 do: [| :i | sl add: i].
  95   sum := 0.
  96   counter := 0.
  97   sl reverseDo: [| :obj |
  98     counter < 5 ifTrue: [
  99       counter += 1.
 100       obj < 8 ifTrue: [sum += obj]]].
 101   tc assert: sum = 18 description: 'reverse do on selected from first half failed'.
 102   sum := 0.
 103   counter := 0.
 104   sl reverseDo: [| :obj |
 105     counter < 8 ifTrue: [
 106       counter += 1.
 107       obj < 5 ifTrue: [sum += obj]]].
 108   tc assert: sum = 9 description: 'reverse do on selection failed'.
 109 ].
 110
 111 tc@(UnitTests SkipList traits) addIfPresent
 112 [
 113   sl ::= SkipList new.
 114   0 upTo: 9 do: [| :i | sl add: i].
 115   counter := 0.
 116   0 upTo: 9 do: [| :i | sl add: i ifPresent: [counter += 1]].
 117   tc assert: counter = 10 description: 'added object when present'.
 118 ].
 119
 120 tc@(UnitTests SkipList traits) removeIfAbsent
 121 [| counter |
 122   sl ::= SkipList new.
 123   counter := 0.
 124   0 upTo: 9 do: [| :i |
 125     sl remove: i ifAbsent: [
 126       counter += 1.
 127       sl add: i]].
 128   0 upTo: 9 do: [| :i | sl remove: i ifAbsent: [counter -= 1]].
 129   tc assert: counter = 10 description: 'removing absent object?'.
 130 ].
 131
 132 tc@(UnitTests SkipList traits) suite
 133 [tc suiteForSelectors: {
 134   #size.
 135   #newPointerLength.
 136   #isEmpty.
 137   #forward.
 138   #add.
 139   #includes.
 140   #remove.
 141   #do.
 142   #reverseDoAndSequence.
 143   #addIfPresent.
 144   #removeIfAbsent.
 145 }].