Levente Uzonyi uploaded a new version of Collections to project The Inbox:
http://source.squeak.org/inbox/Collections-ul.812.mcz

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

Name: Collections-ul.812
Author: ul
Time: 5 December 2018, 7:11:14.545451 pm
UUID: b76e2bfa-1510-4380-8ce6-421c08623ce6
Ancestors: Collections-eem.811

Simple OrderedSet based on OrderedDictionary's implementation, but the order instance variable is an OrderedCollection, which simplifies a few things and makes #removeFirst and #removeLast O(1) (amortized).

=============== Diff against Collections-eem.811 ===============

Item was added:
+ Set subclass: #OrderedSet
+ 	instanceVariableNames: 'order'
+ 	classVariableNames: ''
+ 	poolDictionaries: ''
+ 	category: 'Collections-Sequenceable'!
+ 
+ !OrderedSet commentStamp: 'ul 12/4/2018 23:48' prior: 0!
+ I am an ordered set. I have an additional index (called 'order') to keep track of the insertion order of my objects.
+ 
+ Access and insertion time is not affected by the additional index.
+ 
+ Removal takes O(n) time in general, but it is O(1) to remove the first and last elements via #removeFirst and #removeLast, respectively.!

Item was added:
+ ----- Method: OrderedSet>>atIndex: (in category 'accessing') -----
+ atIndex: integer
+ 
+ 	^order at: integer!

Item was added:
+ ----- Method: OrderedSet>>atIndex:ifAbsent: (in category 'accessing') -----
+ atIndex: integer ifAbsent: exceptionBlock
+ 	"As we are sequenceable, provide index-based access."
+ 
+ 	^order at: integer ifAbsent: exceptionBlock!

Item was added:
+ ----- Method: OrderedSet>>atNewIndex:put: (in category 'private') -----
+ atNewIndex: index put: setElement
+ 
+ 	super atNewIndex: index put: setElement.
+ 	order addLast: setElement enclosedSetElement
+ 	!

Item was added:
+ ----- Method: OrderedSet>>copyFrom:to: (in category 'copying') -----
+ copyFrom: startIndex to: endIndex 
+ 	"Answer a copy of the receiver that contains elements from position
+ 	startIndex to endIndex."
+ 
+ 	^ self shallowCopy postCopyFrom: startIndex to: endIndex!

Item was added:
+ ----- Method: OrderedSet>>do: (in category 'enumerating') -----
+ do: aBlock
+ 	"Iterate over the order instead of the internal array."
+ 
+ 	order do: aBlock!

Item was added:
+ ----- Method: OrderedSet>>eighth (in category 'accessing') -----
+ eighth
+ 
+ 	^order eighth!

Item was added:
+ ----- Method: OrderedSet>>fifth (in category 'accessing') -----
+ fifth
+ 
+ 	^order fifth!

Item was added:
+ ----- Method: OrderedSet>>first (in category 'accessing') -----
+ first
+ 	"Answer the first element of the receiver"
+ 
+ 	^order first!

Item was added:
+ ----- Method: OrderedSet>>first: (in category 'accessing') -----
+ first: n
+ 	"Answer the first n elements of the receiver.
+ 	Raise an error if there are not enough elements."
+ 
+ 	^ self copyFrom: 1 to: n!

Item was added:
+ ----- Method: OrderedSet>>fourth (in category 'accessing') -----
+ fourth
+ 
+ 	^order fourth!

Item was added:
+ ----- Method: OrderedSet>>initialize: (in category 'private') -----
+ initialize: n
+ 
+ 	super initialize: n.
+ 	order := OrderedCollection new: n!

Item was added:
+ ----- Method: OrderedSet>>isSorted (in category 'sorting') -----
+ isSorted
+ 	"Return true if the receiver is sorted by #<=."
+ 	
+ 	^order isSorted!

Item was added:
+ ----- Method: OrderedSet>>last (in category 'accessing') -----
+ last
+ 	"Answer the last element of the receiver"
+ 
+ 	^order last!

Item was added:
+ ----- Method: OrderedSet>>last: (in category 'accessing') -----
+ last: n
+ 	"Answer the last n elements of the receiver.  
+ 	Raise an error if there are not enough elements."
+ 
+ 	^ self copyFrom: tally - n + 1 to: tally!

Item was added:
+ ----- Method: OrderedSet>>ninth (in category 'accessing') -----
+ ninth
+ 	"Answer the ninth element of the receiver.
+ 	Raise an error if there are not enough elements."
+ 
+ 	^ self atIndex: 9!

Item was added:
+ ----- Method: OrderedSet>>postCopy (in category 'copying') -----
+ postCopy
+ 
+ 	super postCopy.
+ 	order := order copy!

Item was added:
+ ----- Method: OrderedSet>>postCopyFrom:to: (in category 'copying') -----
+ postCopyFrom: startIndex to: endIndex
+ 	"Adapted from SequenceableCollection and OrderedCollection."
+ 
+ 	tally := endIndex - startIndex + 1.
+ 	array := self class arrayType
+ 		new: (self class goodPrimeAtLeast: tally * 4 // 3). "fill up to ~75%"
+ 	order := order copyFrom: startIndex to: endIndex.
+ 	order do: [ :element | "TODO: do we need #enclosedSetElement?"
+ 		array at: (self scanFor: element) put: element].
+ 
+ 	!

Item was added:
+ ----- Method: OrderedSet>>remove:ifAbsent: (in category 'removing') -----
+ remove: anObject ifAbsent: aBlock
+ 
+ 	^order remove: (super remove: anObject ifAbsent: [ ^aBlock value ])!

Item was added:
+ ----- Method: OrderedSet>>removeFirst (in category 'removing') -----
+ removeFirst
+ 
+ 	^super remove: order removeFirst ifAbsent: nil!

Item was added:
+ ----- Method: OrderedSet>>removeLast (in category 'removing') -----
+ removeLast
+ 
+ 	^super remove: order removeLast ifAbsent: nil!

Item was added:
+ ----- Method: OrderedSet>>second (in category 'accessing') -----
+ second
+ 
+ 	^order second!

Item was added:
+ ----- Method: OrderedSet>>seventh (in category 'accessing') -----
+ seventh
+ 
+ 	^order seventh!

Item was added:
+ ----- Method: OrderedSet>>sixth (in category 'accessing') -----
+ sixth
+ 
+ 	^order sixth!

Item was added:
+ ----- Method: OrderedSet>>sort (in category 'sorting') -----
+ sort
+ 
+ 	self sort: nil!

Item was added:
+ ----- Method: OrderedSet>>sort: (in category 'sorting') -----
+ sort: aSortBlock
+ 	"Like in OrderedCollection, sort the associations according to the sort block."
+ 
+ 	tally <= 1 ifTrue: [ ^self ].
+ 	order sort: aSortBlock!

Item was added:
+ ----- Method: OrderedSet>>sorted: (in category 'sorting') -----
+ sorted: aSortBlockOrNil
+ 
+ 	^ self copy sort: aSortBlockOrNil!

Item was added:
+ ----- Method: OrderedSet>>third (in category 'accessing') -----
+ third
+ 
+ 	^order third!