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) + !