The Inbox: Collections-ul.812.mcz

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!