[Pkg] The Trunk: Collections-ul.748.mcz

commits at source.squeak.org commits at source.squeak.org
Sun Apr 23 18:20:04 UTC 2017


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

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

Name: Collections-ul.748
Author: ul
Time: 23 April 2017, 6:01:07.769449 pm
UUID: 834a2107-7087-42e3-a165-edc40a9f65f7
Ancestors: Collections-pre.747, Collections-ul.743

- merged with Collections-ul.743
- ArrayedCollection >> #mergeSortFrom:to:by: signals errors instead of assertion failures and uses #shallowCopy instead of #clone
- optimized Heap >> #removeFirst and SequenceCollection >> #beginsWith:

=============== Diff against Collections-pre.747 ===============

Item was changed:
  ----- Method: ArrayedCollection>>mergeSortFrom:to:by: (in category 'sorting') -----
  mergeSortFrom: startIndex to: stopIndex by: aBlock
  	"Sort the given range of indices using the mergesort algorithm.
  	Mergesort is a worst-case O(N log N) sorting algorithm that usually
  	does only half as many comparisons as heapsort or quicksort."
  
  	"Details: recursively split the range to be sorted into two halves,
  	mergesort each half, then merge the two halves together. An extra 
  	copy of the data is used as temporary storage and successive merge 
  	phases copy data back and forth between the receiver and this copy.
  	The recursion is set up so that the final merge is performed into the
  	receiver, resulting in the receiver being completely sorted."
  
+ 	| size |
+ 	(size := self size) <= 1 ifTrue: [^ self].  "nothing to do"
- 	self size <= 1 ifTrue: [^ self].  "nothing to do"
  	startIndex = stopIndex ifTrue: [^ self].
+ 	1 <= startIndex ifFalse: [ self errorSubscriptBounds: startIndex ].
+ 	stopIndex <= size ifFalse: [ self errorSubscriptBounds: stopIndex ].
+ 	startIndex < stopIndex ifFalse: [ self errorSubscriptBounds: startIndex ].
- 	self assert: [startIndex >= 1 and: [startIndex < stopIndex]]. "bad start index"
- 	self assert: [stopIndex <= self size]. "bad stop index"
  	self
  		mergeSortFrom: startIndex
  		to: stopIndex 
+ 		src: self shallowCopy
- 		src: self clone 
  		dst: self 
  		by: aBlock!

Item was changed:
+ NonPointersOrderedCollection subclass: #FloatCollection
- OrderedCollection subclass: #FloatCollection
  	instanceVariableNames: ''
  	classVariableNames: ''
  	poolDictionaries: ''
  	category: 'Collections-Sequenceable'!
  
  !FloatCollection commentStamp: 'cmm 1/28/2013 19:49' prior: 0!
  FloatCollctions store 32bit IEEE floating point numbers.!

Item was changed:
+ ----- Method: FloatCollection class>>arrayType (in category 'private') -----
- ----- Method: FloatCollection class>>arrayType (in category 'overriding') -----
  arrayType
  	^ FloatArray!

Item was removed:
- ----- Method: FloatCollection>>addLast: (in category 'adding') -----
- addLast: aFloat
- 	aFloat isNumber ifFalse: [ self error: 'This collection can only store Floats.' ].
- 	^ super addLast: aFloat!

Item was changed:
+ ----- Method: FloatCollection>>asFloatArray (in category 'converting') -----
- ----- Method: FloatCollection>>asFloatArray (in category 'adding') -----
  asFloatArray
  	"Optimized version"
  
  	^array copyFrom: firstIndex to: lastIndex!

Item was changed:
  ----- Method: Heap>>removeFirst (in category 'removing') -----
  removeFirst
+ 	"Remove the root element and make sure the sorting order is okay. Optimized version for the most common use case."
+ 
+ 	| removed |
+ 	tally = 0 ifTrue: [ self errorSubscriptBounds: 1 ].
+ 	removed := array at: 1.
+ 	array 
+ 		at: 1 put: (array at: tally);
+ 		at: tally put: nil.
+ 	(tally := tally - 1) > 1 ifTrue: [
+ 		"Root node has at least one child."
+ 		self downHeapSingle: 1 ].
+ 	^removed!
- 	"Remove the first element from the receiver"
- 	^self removeAt: 1!

Item was added:
+ OrderedCollection subclass: #NonPointersOrderedCollection
+ 	instanceVariableNames: ''
+ 	classVariableNames: ''
+ 	poolDictionaries: ''
+ 	category: 'Collections-Sequenceable'!
+ 
+ !NonPointersOrderedCollection commentStamp: 'ul 3/26/2017 21:38' prior: 0!
+ I am an OrderedCollection with an internal array holding non-pointers objects. This has the advantage that the array is never subject of garbage collection. But I can only hold objects of a given type defined by my class-side #arrayType method, which is the only method they have to implement.!

Item was added:
+ ----- Method: NonPointersOrderedCollection class>>arrayType (in category 'private') -----
+ arrayType
+ 	"This method must return a non-pointers array class."
+ 
+ 	self subclassResponsibility!

Item was added:
+ ----- Method: NonPointersOrderedCollection>>makeRoomAtFirst (in category 'private') -----
+ makeRoomAtFirst
+ 	"Same as super without trying to store nil in the emptied slots of array."
+ 	
+ 	| tally newFirstIndex newLastIndex capacity |
+ 	tally := self size.
+ 	capacity := array size.
+ 	tally * 2 >= capacity ifTrue: [ ^self growAtFirst ].
+ 	tally = 0 ifTrue: [ ^self resetTo: capacity + 1 ].
+ 	newFirstIndex := capacity // 2 + 1.
+ 	newLastIndex := newFirstIndex - firstIndex + lastIndex.
+ 	0 to: tally - 1 do: [ :offset |
+ 		array at: newLastIndex - offset put: (array at: lastIndex - offset) ].
+ 	firstIndex := newFirstIndex.
+ 	lastIndex := newLastIndex!

Item was added:
+ ----- Method: NonPointersOrderedCollection>>makeRoomAtLast (in category 'private') -----
+ makeRoomAtLast
+ 	"Same as super without trying to store nil in the emptied slots of array."
+ 	
+ 	| tally newFirstIndex newLastIndex |
+ 	tally := self size.
+ 	tally * 2 >= lastIndex ifTrue: [ ^self growAtLast ].
+ 	tally = 0 ifTrue: [ ^self resetTo: 1 ].
+ 	newLastIndex := lastIndex // 2.
+ 	newFirstIndex := newLastIndex - lastIndex + firstIndex.
+ 	array 
+ 		replaceFrom: newFirstIndex
+ 		to: newLastIndex
+ 		with: array
+ 		startingAt: firstIndex.
+ 	firstIndex := newFirstIndex.
+ 	lastIndex := newLastIndex!

Item was added:
+ ----- Method: NonPointersOrderedCollection>>removeAllSuchThat: (in category 'removing') -----
+ removeAllSuchThat: aBlock 
+ 	"Same as super without trying to store nil in the emptied slots of array."
+ 
+ 	| n |
+ 	n := firstIndex.
+ 	firstIndex to: lastIndex do: [ :index |
+ 		| element |
+ 		(aBlock value: (element := array at: index)) ifFalse: [
+ 			array at: n put: element.
+ 			n := n + 1 ] ].
+ 	lastIndex := n - 1!

Item was added:
+ ----- Method: NonPointersOrderedCollection>>removeFirst (in category 'removing') -----
+ removeFirst
+ 	"Same as super without trying to store nil in the emptied slot of array."
+ 
+ 	| firstObject |
+ 	firstIndex > lastIndex ifTrue: [ self errorEmptyCollection ].
+ 	firstObject := array at: firstIndex.
+ 	firstIndex := firstIndex + 1.
+ 	^firstObject!

Item was added:
+ ----- Method: NonPointersOrderedCollection>>removeFirst: (in category 'removing') -----
+ removeFirst: n 
+ 	"Same as super without trying to store nil in the emptied slots of array."
+ 
+ 	| lastIndexToRemove result |
+ 	n < 1 ifTrue: [ self errorNoSuchElement ].
+ 	lastIndex < (lastIndexToRemove := firstIndex + n - 1) ifTrue: [ self errorNotEnoughElements ].
+ 	result := array copyFrom: firstIndex to: lastIndexToRemove.
+ 	firstIndex := lastIndexToRemove + 1.
+ 	^result!

Item was added:
+ ----- Method: NonPointersOrderedCollection>>removeIndex: (in category 'private') -----
+ removeIndex: removedIndex
+  	"Same as super without trying to store nil in the emptied slot of array."
+ 
+ 	array 
+ 		replaceFrom: removedIndex 
+ 		to: lastIndex - 1 
+ 		with: array 
+ 		startingAt: removedIndex + 1.
+ 	lastIndex := lastIndex - 1.!

Item was added:
+ ----- Method: NonPointersOrderedCollection>>removeLast (in category 'removing') -----
+ removeLast
+ 	"Same as super without trying to store nil in the emptied slot of array."
+ 	
+ 	| lastObject |
+ 	firstIndex > lastIndex ifTrue: [ self errorEmptyCollection ].
+ 	lastObject := array at: lastIndex.
+ 	lastIndex := lastIndex - 1.
+ 	^ lastObject!

Item was added:
+ ----- Method: NonPointersOrderedCollection>>removeLast: (in category 'removing') -----
+ removeLast: n
+ 	"Same as super without trying to store nil in the emptied slots of array."
+ 
+ 	| firstIndexToRemove result |
+ 	n < 1 ifTrue: [ self errorNoSuchElement ].
+ 	(firstIndexToRemove := lastIndex - n + 1) < firstIndex ifTrue: [ self errorNotEnoughElements ].
+ 	result := array copyFrom: firstIndexToRemove to: lastIndex.
+ 	lastIndex := firstIndexToRemove - 1.
+ 	^result!

Item was changed:
  ----- Method: OrderedCollection>>collect: (in category 'enumerating') -----
  collect: aBlock 
+ 	"Evaluate aBlock with each of my elements as the argument.
+ 	Collect the resulting values into an OrderedCollection."
- 	"Evaluate aBlock with each of my elements as the argument. Collect the 
- 	resulting values into a collection that is like me. Answer the new 
- 	collection. Override superclass in order to use addLast:, not at:put:."
  
  	| newCollection |
+ 	newCollection := OrderedCollection new: self size.
- 	newCollection := self species new: self size.
  	firstIndex to: lastIndex do:
  		[:index |
  		newCollection addLast: (aBlock value: (array at: index))].
  	^ newCollection!

Item was changed:
  ----- Method: OrderedCollection>>collect:from:to: (in category 'enumerating') -----
  collect: aBlock from: fromIndex to: toIndex
+ 	"Evaluate aBlock with each of my elements as the argument between fromIndex and toIndex.
+ 	Collect the resulting values into an OrderedCollection."
+ 
+ 	| result offset |
+ 	offset := firstIndex - 1.
+ 	(fromIndex < 1 or:[toIndex + offset > lastIndex])
- 	"Override superclass in order to use addLast:, not at:put:."
- 	| result |
- 	(fromIndex < 1 or:[toIndex + firstIndex - 1 > lastIndex])
  		ifTrue: [^self errorNoSuchElement].
+ 	result := OrderedCollection new: toIndex - fromIndex + 1.
+ 	fromIndex + offset to: toIndex + offset do:
- 	result := self species new: toIndex - fromIndex + 1.
- 	firstIndex + fromIndex - 1 to: firstIndex + toIndex - 1 do:
  		[:index | result addLast: (aBlock value: (array at: index))].
  	^ result
  !

Item was changed:
  ----- Method: OrderedCollection>>with:collect: (in category 'enumerating') -----
  with: otherCollection collect: twoArgBlock 
  	"Collect and return the result of evaluating twoArgBlock with 
  	corresponding elements from this collection and otherCollection."
  
  	| result offset size |
  	(size := self size) = otherCollection size ifFalse: [ self error: 'otherCollection must be the same size' ].
+ 	result := OrderedCollection new: size.
- 	result := self species new: size.
  	offset := 1 - firstIndex.
  	firstIndex to: lastIndex do: [ :index |
  		result addLast: (
  			twoArgBlock 
  				value: (array at: index)
  				value: (otherCollection at: index + offset)) ].
  	^result!

Item was changed:
  ----- Method: OrderedCollection>>withIndexCollect: (in category 'enumerating') -----
  withIndexCollect: elementAndIndexBlock 
  	"Just like with:collect: except that the iteration index supplies the second argument to the block. Override superclass in order to use addLast:, not at:put:."
  
  	| newCollection offset |
+ 	newCollection := OrderedCollection new: self size.
- 	newCollection := self species new: self size.
  	offset := 1 - firstIndex.
  	firstIndex to: lastIndex do:
  		[:index |
  		newCollection addLast: (elementAndIndexBlock
  			value: (array at: index)
  			value: index + offset) ].
  	^ newCollection!

Item was changed:
  ----- Method: SequenceableCollection>>beginsWith: (in category 'testing') -----
  beginsWith: sequence
  	"Answer true if the receiver starts with the argument collection."
  	
  	| sequenceSize |
+ 	((sequenceSize := sequence size) = 0 or: [ self size < sequenceSize ]) ifTrue: [ ^false ].
- 	((sequenceSize := sequence size) = 0 or: [ self size < sequence size ]) ifTrue: [ ^false ].
  	1 to: sequenceSize do: [ :index |
  		(sequence at: index) = (self at: index) ifFalse: [ ^false ] ].
  	^true!

Item was removed:
- ----- Method: SortedCollection>>collect: (in category 'enumerating') -----
- collect: aBlock 
- 	"Evaluate aBlock with each of my elements as the argument. Collect the 
- 	resulting values into an OrderedCollection. Answer the new collection. 
- 	Override the superclass in order to produce an OrderedCollection instead
- 	of a SortedCollection."
- 
- 	| newCollection | 
- 	newCollection := OrderedCollection new: self size.
- 	self do: [:each | newCollection addLast: (aBlock value: each)].
- 	^ newCollection!

Item was changed:
+ ----- Method: WeakOrderedCollection class>>arrayType (in category 'private') -----
- ----- Method: WeakOrderedCollection class>>arrayType (in category 'as yet unclassified') -----
  arrayType
  	^ WeakArray!



More information about the Packages mailing list