[squeak-dev] Why do Heap re-sort when it removes elements ?

Nicolas Cellier nicolas.cellier.aka.nice at gmail.com
Thu Sep 30 12:16:34 UTC 2010


Hi,
I just saw this:

Heap>>privateRemoveAt: index
	"Remove the element at the given index and make sure the sorting order is okay"
	| removed |
	removed := array at: index.
	array at: index put: (array at: tally).
	array at: tally put: nil.
	tally := tally - 1.
	index > tally ifFalse:[
		"Use #downHeapSingle: since only one element has been removed"
		self downHeapSingle: index].
	^removed

This means that an element removal triggers a new sort phase... (even
a simplified one costs)
I think this could be more efficient:

Heap>>privateRemoveAt: index
	"Remove the element at the given index and make sure the sorting order is okay"
	| removed |
	removed := array at: index.
	tally := tally - 1.
	array replaceFrom: index to: tally with: array startingAt: index + 1.
	array at: tally + 1 put: nil.	
	indexUpdateBlock ifNotNil: [
		index to: tally do: [:i | self updateObjectIndex: i]].
	^removed

Did I miss a good reason justifying to re-sort ?

Nicolas



More information about the Squeak-dev mailing list