1 collections define: #InternallyOrderedSequence &parents: {ExtensibleSequence}.
2 "An extensible Sequence whose elements order is determined by a constraint
3 rather than manipulable by a public protocol."
4 "TODO: Factor out an immutable Sequence type."
6 sc@(InternallyOrderedSequence traits) at: index put: obj
7 "TODO? Just call add:."
8 [sc shouldNotImplement].
10 collections define: #SortedArray &parents: {ExtensibleArray. InternallyOrderedSequence}
11 &slots: {#sortBlock -> #<= `er }.
12 "A SortedArray is a Sequence which is Extensible, but which however maintains
13 an order determined by a sorting block, therefore making indexed modification
16 c@(Collection traits) sort
17 "TODO: this scales up poorly."
18 [(SortedArray newSizeOf: c) `>> [addAll: c. ]].
20 c@(Collection traits) sortBy: block
21 "TODO: this scales up poorly."
22 [(SortedArray newSizeOf: c) `>> [sortBlock: block. addAll: c. ]].
24 sc@(SortedArray traits) sort [sc].
26 sc@(SortedArray traits) newSortedBy: block
27 [sc new `>> [sortBlock: block. ]].
29 sc@(SortedArray traits) shouldArrange: x before: y
30 [sc sortBlock apply*, x, y].
32 sc@(SortedArray traits) min
33 [sc isEmpty ifFalse: [sc first]].
35 sc@(SortedArray traits) max
36 [sc isEmpty ifFalse: [sc last]].
38 sc@(SortedArray traits) median
39 [sc at: sc size + 1 // 2].
41 sc@(SortedArray traits) sortViolation
42 [error: 'Sort order violation.'].
44 sc@(SortedArray traits) at: index insert: obj
46 (sc indexForInserting: obj) = index
48 ifFalse: [sc sortViolation]
51 sc@(SortedArray traits) add: obj
52 "Use the unsafe #at:insert: call to avoid a double #indexForInserting:
53 calculation which would be expensive."
54 [#at:insert: sendTo: {sc. sc indexForInserting: obj. obj}
55 through: {ExtensibleArray. Nil. Nil}
58 sc@(SortedArray traits) addLast: obj
62 ifFalse: [(sc shouldArrange: sc last before: obj)
64 ifFalse: [sc sortViolation]]
67 sc@(SortedArray traits) addFirst: obj
71 ifFalse: [(sc shouldArrange: obj before: sc first)
73 ifFalse: [sc sortViolation]]
76 sc@(SortedArray traits) addAll: c
77 "If the number of elements to add is great enough, add the elements unsafely,
78 and then sort. Otherwise, add each in turn."
80 c size > (sc size // 3)
81 ifTrue: [c do: [| :each | #addLast: sendTo: {sc. each}
82 through: {ExtensibleArray. Nil}].
84 ifFalse: [c do: #(sc add: _) `er].
88 sc@(SortedArray traits) = sc2@(SortedArray traits)
90 sc sortBlock = sc2 sortBlock /\ [resend]
93 sc@(SortedArray traits) copy
94 "Make a new SortedArray with the same sortBlock. Since we know the order
95 will not change, use the minimally-checking addLast: method vice addAll:."
97 result ::= sc newSameSize.
98 sc do: #(result addLast: _) `er.
102 sc@(SortedArray traits) copyWith: obj
103 "Non-destructively append, but don't use addLast: as ExtensibleArray does."
105 sc copy `>> [add: obj. ]
108 sc@(SortedArray traits) copyFrom: start to: end
109 "Copy the range into a new SortedArray which keeps the same sortBlock."
111 end < start \/ [sc isEmpty]
112 ifTrue: [result := sc new]
114 [result := sc new &capacity: end - start + 1.
115 start to: end do: [| :index | result addLast: (sc at: index)]].
119 sc@(SortedArray traits) reversed
120 [resend `>> [sortBlock := sc sortBlock converse. ]].
122 sc@(SortedArray traits) collect: block
123 "Override in order to return an ExtensibleArray instead of a SortedArray."
125 result ::= ExtensibleArray newSizeOf: sc.
126 sc do: [| :each | result addLast: (block applyWith: each)].
130 sc@(SortedArray traits) indexOf: obj startingAt: start ifAbsent: block
131 "Subdivides the SortedArray into segments by comparing mid-elements with
132 the object, narrowing until the object is found, or running the block if it
135 low := sc firstIndex + start.
136 high := sc lastIndex.
137 [index := high + low // 2. low > high]
139 [(sc contents at: index) = obj
141 (sc shouldArrange: (sc contents at: index) before: obj)
142 ifTrue: [low := index + 1]
143 ifFalse: [high := index - 1]].
147 sc@(SortedArray traits) includes: obj
148 "Overridden because the sort order makes a faster implementation possible."
150 (sc indexOf: obj ifAbsent: [^ False]) isPositive
153 sc@(SortedArray traits) indexForInserting: obj
154 "This returns the index where the object should be inserted to preserve sort
157 low := sc firstIndex.
158 high := sc lastIndex.
159 [index := high + low // 2. low > high]
160 whileFalse: [(sc shouldArrange: (sc contents at: index) before: obj)
161 ifTrue: [low := index + 1] ifFalse: [high := index - 1]].
165 sc@(SortedArray traits) replaceNextLargerWith: obj
166 "Find the place at which obj would normally be inserted into the Sequence.
167 If that place is already occupied by obj, just return Nil. If the place
168 does not exist (i.e., it is off the end of the collection), add it to the
169 end, otherwise replace the element at that point with obj. This returns the
170 destination index in any normal case. This operation does preserve the
173 (index ::= sc indexForInserting: obj) > sc indexLast
174 ifTrue: [sc addLast: obj. sc indexLast]
175 ifFalse: [(sc at: index) = obj ifFalse:
176 [sc contents at: index + sc firstIndex put: obj. index]]
179 sc@(SortedArray traits) reSort
181 sc contents sortFrom: sc firstIndex to: sc lastIndex by: sc sortBlock.