The Trunk: CollectionsTests-ul.263.mcz

Levente Uzonyi uploaded a new version of CollectionsTests to project The Trunk:
http://source.squeak.org/trunk/CollectionsTests-ul.263.mcz

==================== Summary ====================

Name: CollectionsTests-ul.263
Author: ul
Time: 2 June 2016, 5:49:02.940363 pm
UUID: caaf5382-04e8-47fb-9db3-9b5e97cb3aed
Ancestors: CollectionsTests-mt.262

- added a few more heap tests

=============== Diff against CollectionsTests-mt.262 ===============

Item was changed:
  ----- Method: HeapTest>>heapSortExample (in category 'examples') -----
+ heapSortExample
+ "Sort a random collection of Floats and compare the results with #quicksort and #sort (using the merge-sort algorithm)."
+ "HeapTest new heapSortExample"
+
+ | arrayToSort n rnd array time |
+ Smalltalk garbageCollectMost.
+ n := 50000. "# of elements to sort"
- heapSortExample "HeapTest new heapSortExample"
- "Sort a random collection of Floats and compare the results with
- SortedCollection (using the quick-sort algorithm) and
- ArrayedCollection>>mergeSortFrom:to:by: (using the merge-sort algorithm)."
- | n rnd array  time sorted |
- n := 10000. "# of elements to sort"
  rnd := Random new.
+ array := Array new: n.
+ 1 to: n do: [ :index | array at: index put: rnd next ].
+ arrayToSort := array copy.
- array := (1 to: n) collect:[:i| rnd next].
  "First, the heap version"
+ self deny: arrayToSort isSorted.
+ time := [ (Heap on: arrayToSort) sort ] timeToRun.
+ self assert: arrayToSort isSorted.
+ Transcript cr; show: 'Time for heap-sort: ', time printString,' msecs'.
- time := Time millisecondsToRun:[
- sorted := Heap withAll: array.
- 1 to: n do:[:i| sorted removeFirst].
- ].
- Transcript cr; show:'Time for heap-sort: ', time printString,' msecs'.
  "The quicksort version"
+ arrayToSort copyFrom: array.
+ self deny: arrayToSort isSorted.
+ time := [ arrayToSort quickSort ] timeToRun.
+ self assert: arrayToSort isSorted.
+ Transcript cr; show: 'Time for quick-sort: ', time printString,' msecs'.
- time := Time millisecondsToRun:[
- sorted := SortedCollection withAll: array.
- ].
- Transcript cr; show:'Time for quick-sort: ', time printString,' msecs'.
  "The merge-sort version"
+ arrayToSort copyFrom: array.
+ self deny: arrayToSort isSorted.
+ time := [ arrayToSort sort ] timeToRun.
+ self assert: arrayToSort isSorted.
+ Transcript cr; show: 'Time for merge-sort: ', time printString,' msecs'!
- time := Time millisecondsToRun:[
- array mergeSortFrom: 1 to: array size by: [:v1 :v2| v1 <= v2].
- ].
- Transcript cr; show:'Time for merge-sort: ', time printString,' msecs'.
- !

Item was changed:
+ ----- Method: HeapTest>>test1 (in category 'tests') -----
- ----- Method: HeapTest>>test1 (in category 'testing') -----
  test1
  | data |
 
  "The first element of each array is the sort value, and the second will be updated by the heap with the index of the element within the heap."
  data :=  (1 to: 8) collect: [:i | {i*2. 0}].
 
  "Repeat with different data ordering."
  5 timesRepeat: [ | h |
  h := Heap new sortBlock: [:e1 :e2 | e1 first < e2 first].
  h indexUpdateBlock: [:array :index | array at: 2 put: index].
 
  data shuffled do: [:d | h add: d].
  data do: [:d | self should: (h at: d second) == d].
  ]!

Item was changed:
+ ----- Method: HeapTest>>testAdd (in category 'tests') -----
- ----- Method: HeapTest>>testAdd (in category 'basic tests') -----
  testAdd
  "self run: #testAdd"
 
  | heap |
  heap := Heap new.
  self assert: heap size = 0.
  heap add: 3.
  self assert: heap size = 1.
  self assert: heap isEmpty not.
  self assert: heap first = 3.
  self assert: (heap at: 1) = 3.
  heap add: 2.
  self assert: heap size = 2.
  self assert: heap first = 2.
  self assert: (heap at: 2) = 3.
  !

Item was added:
+ ----- Method: HeapTest>>testAddAndRemoveFirst (in category 'tests') -----
+ testAddAndRemoveFirst
+
+ | random heap validateHeap |
+ random := Random seed: 36rSqueak.
+ heap := Heap sortBlock: [ :a :b | a first >= b first ].
+ heap indexUpdateBlock: [ :element :newIndex | element at: 2 put: newIndex ].
+ validateHeap := [ heap isValidHeap and: [
+ heap do: [ :each | self assert: (heap at: each second) == each ] ] ].
+ validateHeap value.
+ self assert: 0 equals: heap size.
+ self assert: heap isEmpty.
+ 1 to: 100 do: [ :index |
+ heap add: { random next. nil }.
+ self assert: index equals: heap size.
+ validateHeap value ].
+ 1000 timesRepeat: [
+ | first |
+ first := heap removeFirst.
+ heap do: [ :each | self assert: (heap sortBlock value: first value: each) ].
+ heap add: { random next. nil }.
+ validateHeap value ]!

Item was changed:
+ ----- Method: HeapTest>>testAt (in category 'tests') -----
- ----- Method: HeapTest>>testAt (in category 'basic tests') -----
  testAt
  "self run: #testAt"
 
  | heap |
  heap := Heap new.
  heap add: 3.
  self assert: (heap at: 1) = 3.
  self should: [heap at: 2] raise: Error.
  heap add: 4.
  self assert: (heap at: 1) = 3.
  self assert: (heap at: 2) = 4.
 
  !

Item was added:
+ ----- Method: HeapTest>>testAtRaisesErrorWhenIndexIsInvalid (in category 'tests') -----
+ testAtRaisesErrorWhenIndexIsInvalid
+ " self run: #testAtRaisesErrorWhenIndexIsInvalid "
+
+ | heap |
+ heap := Heap new.
+ 1 to: 100 do: [ :index |
+ 1 to: heap size do: [ :each |
+ self assert: ((heap at: each) between: 1 and: heap size) ].
+ self
+ should: [ heap at: 0 ] raise: Error;
+ should: [ heap at: heap size + 1 ] raise: Error.
+ heap add: index ].!

Item was added:
+ ----- Method: HeapTest>>testCompact (in category 'tests') -----
+ testCompact
+ " self run: #testCompact "
+
+ | heap |
+ heap := Heap new.
+ 1 to: 100 do: [ :index |
+ | copy |
+ copy := heap copy.
+ copy compact.
+ self
+ assert: copy = heap;
+ assert: copy capacity <= heap capacity;
+ assert: copy capacity = copy size.
+ heap add: index ].!

Item was added:
+ ----- Method: HeapTest>>testCopy (in category 'tests') -----
+ testCopy
+
+ | heap |
+ heap := Heap new.
+ 1 to: 100 do: [ :index |
+ | copy |
+ copy := heap copy.
+ self
+ assert: copy = heap;
+ assert: heap = copy;
+ deny: copy == heap;
+ assert: copy sortBlock = heap sortBlock;
+ deny: copy array == heap array.
+ heap add: index ].!

Item was added:
+ ----- Method: HeapTest>>testCopyEmpty (in category 'tests') -----
+ testCopyEmpty
+
+ | heap |
+ heap := Heap new.
+ 1 to: 100 do: [ :index |
+ | copy |
+ copy := heap copyEmpty.
+ self
+ assert: copy isHeap;
+ assert: copy isEmpty;
+ assert: copy sortBlock = heap sortBlock.
+ heap add: index ].!

Item was changed:
+ ----- Method: HeapTest>>testDo (in category 'tests') -----
- ----- Method: HeapTest>>testDo (in category 'basic tests') -----
  testDo
  "self run: #testDo"
 
  | heap coll |
  heap := Heap withAll: #(1 3 5).
  coll := OrderedCollection new.
 
  heap do: [:each | coll add: each].
 
  self assert: coll = #(1 3 5) asOrderedCollection.
  !

Item was changed:
+ ----- Method: HeapTest>>testExamples (in category 'tests') -----
- ----- Method: HeapTest>>testExamples (in category 'testing') -----
  testExamples
  self heapExample.
  self heapSortExample.!

Item was changed:
+ ----- Method: HeapTest>>testFirst (in category 'tests') -----
- ----- Method: HeapTest>>testFirst (in category 'basic tests') -----
  testFirst
  "self run: #testFirst"
  | heap |
  heap := Heap new.
  heap add: 5.
  heap add: 12.
  heap add: 1.
  self assert: heap first = 1.
  heap removeFirst.
  self assert: heap first = 5.!

Item was changed:
+ ----- Method: HeapTest>>testHeap (in category 'tests') -----
- ----- Method: HeapTest>>testHeap (in category 'basic tests') -----
  testHeap
  "self run: #testHeap"
 
  | heap |
  heap := Heap new.
  self assert: heap isHeap.
 
  self assert: heap isEmpty.
  heap add: 1.
  self assert: heap isEmpty not
 
  !

Item was changed:
+ ----- Method: HeapTest>>testIfEqualIsTransitive (in category 'tests') -----
- ----- Method: HeapTest>>testIfEqualIsTransitive (in category 'testing') -----
  testIfEqualIsTransitive
  "This is http://bugs.squeak.org/view.php?id=6943"
 
      | anArray heap1 heap2 |
      anArray := #(1 2 3).
      heap1 := Heap withAll: (1 to: 3) sortBlock: [:a :b | a < b].
      heap2 := Heap withAll: (1 to: 3) sortBlock: [:a :b | b > a].
      self
  assert: (heap1 = anArray) & (heap2 = anArray) ==> (heap1 = heap2)
  description: 'Heap equality should be transitive'!

Item was changed:
+ ----- Method: HeapTest>>testRemove (in category 'tests') -----
- ----- Method: HeapTest>>testRemove (in category 'basic tests') -----
  testRemove
  "self run: #testRemove"
 
  | heap |
  heap := Heap new.
  self should: [heap removeFirst] raise: Error.
  heap add: 5.
+ self assert: 5 equals: heap removeFirst.
- heap removeFirst.
  self assert: heap size = 0.
  heap add: 5.
  self should: [heap removeAt: 2] raise: Error.!

Item was added:
+ ----- Method: HeapTest>>testSort (in category 'tests') -----
+ testSort
+
+ self testSortUsing: Heap new.
+ {
+ nil.
+ #<=.
+ [ :a :b | a <= b ].
+ [ :a :b | a >= b ]
+ } do: [ :each | self testSortUsing: (Heap sortBlock: each) ]!

Item was changed:
+ ----- Method: HeapTest>>testSortBlock (in category 'tests') -----
- ----- Method: HeapTest>>testSortBlock (in category 'basic tests') -----
  testSortBlock
  "self run: #testSortBlock"
 
  | heap |
  heap := Heap withAll: #(1 3 5).
  self assert: heap asArray = #(1 3 5).
 
  heap sortBlock: [ :e1 :e2 | e1 >= e2 ].
+ self assert: heap isValidHeap.
  self assert: heap asArray = #(5 3 1)
  !

Item was added:
+ ----- Method: HeapTest>>testSortUsing: (in category 'tests') -----
+ testSortUsing: aHeap
+
+ | random |
+ random := Random seed: 36rSqueak.
+ self assert: aHeap isValidHeap.
+ 1000 timesRepeat: [
+ aHeap add: random next.
+ self assert: aHeap isValidHeap ].
+ self deny: (aHeap asArray isSortedBy: aHeap sortBlock).
+ aHeap sort.
+ self assert: aHeap isValidHeap.
+ self assert: (aHeap asArray isSortedBy: aHeap sortBlock)
+ !

Item was added:
+ ----- Method: HeapTest>>testSortWithIndexUpdateBlock (in category 'tests') -----
+ testSortWithIndexUpdateBlock
+
+ | random heap validateHeap |
+ random := Random seed: 36rSqueak.
+ heap := Heap sortBlock: [ :a :b | a first <= b first ].
+ heap indexUpdateBlock: [ :element :newIndex | element at: 2 put: newIndex ].
+ validateHeap := [
+ heap isHeap
+ and: [ heap isValidHeap
+ and: [ heap do: [ :each | self assert: (heap at: each second) == each ] ] ] ].
+ validateHeap value.
+ 1000 timesRepeat: [
+ heap add: { random next. nil }.
+ validateHeap value ].
+ self deny: (heap asArray isSortedBy: heap sortBlock).
+ heap sort.
+ validateHeap value.
+ self assert: (heap asArray isSortedBy: heap sortBlock)
+ !