# [Pkg] The Trunk: CollectionsTests-ul.263.mcz

commits at source.squeak.org commits at source.squeak.org
Thu Jun 2 15:59:54 UTC 2016

```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') -----

| heap |
heap := Heap new.
self assert: heap size = 0.
self assert: heap size = 1.
self assert: heap isEmpty not.
self assert: heap first = 3.
self assert: (heap at: 1) = 3.
self assert: heap size = 2.
self assert: heap first = 2.
self assert: (heap at: 2) = 3.
!

+ ----- Method: HeapTest>>testAddAndRemoveFirst (in category 'tests') -----
+
+ 	| 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.
self assert: (heap at: 1) = 3.
self should: [heap at: 2] raise: Error.
self assert: (heap at: 1) = 3.
self assert: (heap at: 2) = 4.

!

+ ----- 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.

+ ----- 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.

+ ----- 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.

+ ----- 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.

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.
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.
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.
+ 	self assert: 5 equals: heap removeFirst.
- 	heap removeFirst.
self assert: heap size = 0.
self should: [heap removeAt: 2] raise: Error.!

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

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

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

```