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