1 collections define: #Sequence &parents: {Collection. Mapping}.
2 "Sequences are Mappings from a range of Integers starting from 0 to a final
3 Integer, in a sequence, to arbitrary objects. The last address will be one
6 "Mapping compatibility methods."
8 _@Sequence size [0]. "metadata traits barrier"
10 s@(Sequence traits) acceptsKey: n@(Integer traits)
11 [n isPositive /\ [n < s size]].
13 _@(Sequence traits) acceptsKey: _
16 s@(Sequence traits) keySet
17 "Answers the keys of a Sequence as a Range; will not work until Range is
20 s isEmpty ifTrue: [#{}] ifFalse: [0 below: s size]
23 s@(Sequence traits) keysDo: block
24 "Iterate over just the indices in the Sequence."
26 0 below: s size do: [| :index | block apply*, index]
29 s@(Sequence traits) keysAndValuesDo: block
31 s doWithIndex: [| :each :index | block apply*, index, each]
34 "Some commonly useful idioms."
36 c@(Sequence traits) first [c at: 0].
37 c@(Sequence traits) second [c at: 1].
38 c@(Sequence traits) third [c at: 2].
39 c@(Sequence traits) fourth [c at: 3].
40 c@(Sequence traits) fifth [c at: 4].
41 c@(Sequence traits) sixth [c at: 5].
42 c@(Sequence traits) seventh [c at: 6].
43 c@(Sequence traits) eighth [c at: 7].
44 c@(Sequence traits) ninth [c at: 8].
45 c@(Sequence traits) tenth [c at: 9].
47 c@(Sequence traits) indexFirst [0].
48 c@(Sequence traits) indexLast [c size - 1].
49 "The index of the last element, not to be confused with lastIndex for
50 ExtensibleArray which indexes into its internal Array."
51 c@(Sequence traits) last [c at: c indexLast].
52 c@(Sequence traits) indexMiddle [c size // 2].
54 c@(Sequence traits) middle
55 "Answer the element at the median index."
56 [c at: c indexMiddle].
58 s@(Sequence traits) newWith: obj
59 [(s new &capacity: 1) `>> [at: s indexFirst put: obj. ]].
61 s@(Sequence traits) newWithAll: c@(Collection traits)
63 result := s newSizeOf: c.
65 c do: [| :each | result at: index put: each. index += 1].
69 s@(Sequence traits) newWithAll: c@(Sequence traits)
71 (s new &capacity: c size `cache) `>> [replaceFrom: 0 below: c size with: c. ]
74 s1@(Sequence traits) as: s2@(Sequence traits)
79 s@(Sequence traits) as: ea@(ExtensibleCollection traits)
81 (ea newSizeOf: s) `>> [addAll: s. ]
84 assoc@(Association traits) as: s@(Sequence traits)
85 [{assoc key. assoc value}].
87 s@(Sequence traits) as: assoc@(Association traits)
90 ifTrue: [s first -> s second]
91 ifFalse: [error: 'Invalid conversion - the input Sequence is not a pair.']
94 s@(Sequence traits) new* [| *rest | rest as: s].
96 s@(Sequence traits) length
97 "For Sequences, length is a property we expect - it's the size of it."
100 c@(Sequence traits) arrayType
101 "A generic protocol for returning a suitable Array prototype for holding the
102 Sequence's objects. TODO: This is an internal, messy kind of detail that
103 should be fixed with some parametrization on elementType."
106 c@(Sequence traits) after: obj ifAbsent: block
111 [| :index | index = c indexLast ifFalse: [c at: index + 1]]
114 c@(Sequence traits) after: obj
116 c after: obj ifAbsent: [Nil]
119 c@(Sequence traits) allButFirst: n
122 ifTrue: [c copyFrom: n to: c indexLast]
126 c@(Sequence traits) allButFirst
131 c@(Sequence traits) allButLast: n
134 ifTrue: [c copyFrom: 0 to: c size - n - 1]
138 c@(Sequence traits) allButLast
143 c@(Sequence traits) anyOne
148 c@(Sequence traits) acceptsKey: n@(Integer traits)
149 "Note that this method is a temporal query: it answers about the 'now'."
151 n >= 0 /\ [n < c size]
154 _@(Sequence traits) acceptsKey: _@(Root traits)
155 "Sequenceables are keyed by integers as indices only."
158 c@(Sequence traits) includesKey: index
159 "A specialized version for sequences"
161 index >= 0 /\ [index < c size]
164 c@(Sequence traits) at: index ifAbsent: block
166 (c includesKey: index)
167 ifTrue: [c at: index]
171 c@(Sequence traits) atAll: d@(Collection traits)
172 "Returns a new Sequence of the elements corresponding to the indexes in the
175 d collect: #(c at: _) `er into: (c newSizeOf: d)
178 c@(Sequence traits) atAll: d@(Sequence traits)
179 "Returns a new Sequence of the elements corresponding to the indexes in the
182 (result := c newSizeOf: d) keysDo:
184 result at: index put: (c at: (d at: index))].
188 c@(Sequence traits) atAll: d put: obj
189 "Replace the element at each index with the corresponding value of the
192 d do: #(c at: _ put: obj) `er.
196 c@(Sequence traits) atAll: indices@(Sequence traits) put: values
197 "Replace the element at each index with the corresponding value of the
200 indices with: values do: #(c at: _ put: _) `er.
204 c@(Sequence traits) atAllPut: obj
205 "Replace all elements with the given one."
207 c infect: [| :_ | obj]
210 s@(Sequence traits) clear
211 "Set all elements to be the default/clear marker (usually Nil)."
213 s atAllPut: s defaultElement
216 c@(Sequence traits) = d@(Sequence traits)
217 "Tests for equality with the simple == and size-checks first, then iterating
218 through the elements in a linear scan =-comparison."
221 \/ [c size `cache = d size
222 /\ [0 below: c size do:
223 [| :index | (c at: index) = (d at: index) ifFalse: [^ False]].
227 c@(Sequence traits) hash
229 c inject: c traits identityHash into: [| :hash :each | (hash + each hash) hashMultiply]
232 c@(Sequence traits) atPin: index
233 "Return the indexed element, coercing index to the collection's range."
235 c isEmpty ifFalse: [c at: (index min: c indexLast max: 0)]
238 c@(Sequence traits) atWrap: index
239 "Return the indexed element, wrapping the index around until it's in range."
241 c at: index \\ c size
244 c@(Sequence traits) atWrap: index put: obj
245 "Set the indexed element, wrapping the index around until it's in range."
247 c at: index \\ c size put: obj
250 c@(Sequence traits) before: obj ifAbsent: block
255 [| :index | index isZero ifTrue: [Nil] ifFalse: [c at: index - 1]]
258 c@(Sequence traits) before: obj
260 c before: obj ifAbsent: [Nil]
263 c@(Sequence traits) first: n
264 "Answer the first N elements or the Sequence itself if it is smaller."
266 c copyFrom: 0 to: (n min: c size) - 1
269 c@(Sequence traits) identityIndexOf: obj ifAbsent: block
271 0 below: c size do: [| :index |
272 (c at: index) == obj ifTrue: [^ index]].
276 c@(Sequence traits) identityIndexOf: obj
278 c identityIndexOf: obj ifAbsent: [Nil]
281 c@(Sequence traits) indexOf: obj startingAt: start ifAbsent: block
282 "Returns the first occurrence of an element equal to the given object from
283 the start-point. Execute and return the block's value if nothing is found."
285 start below: c size do: [| :index |
286 (c at: index) = obj ifTrue: [^ index]].
290 c@(Sequence traits) indexOf: obj startingAt: start
292 c indexOf: obj startingAt: start ifAbsent: [Nil]
295 c@(Sequence traits) indexOf: obj ifAbsent: block
297 c indexOf: obj startingAt: 0 ifAbsent: block
300 c@(Sequence traits) indexOf: obj
302 c indexOf: obj ifAbsent: [Nil]
305 c@(Sequence traits) indicesOfAllSatisfying: block
306 "Answer all positions of the occurrence of elements satisfying the block within
307 the Sequence in the order that they occur."
309 result := ExtensibleArray new.
311 [(position := c indexOfFirstSatisfying: block startingAt: position) isNil]
312 whileFalse: [result addLast: position. position += 1].
316 c@(Sequence traits) indicesOf: obj
317 "Answer all positions of the occurrence of the given element within the
318 Sequence in the order that they occur."
319 [c indicesOfAllSatisfying: #(= obj) `er].
321 c@(Sequence traits) includes: obj
322 "Defined using indexOf: since Sequence is not hashed. Of course, this takes
323 O(n) time in worst cases (most of them, when the element isn't found."
325 (c indexOf: obj) isNotNil
328 c@(Sequence traits) indexOfSubSeq: subSeq startingAt: start ifAbsent: block
331 [subSeq isEmpty] -> [block do].
332 [subSeq size = 1] -> [c indexOf: subSeq first startingAt: start ifAbsent: block]
335 first := subSeq first.
336 start upTo: c size - subSeq size do: [| :startIndex |
337 (c at: startIndex) = first ifTrue:
339 [(c at: startIndex + index) = (subSeq at: index)]
340 whileTrue: [(index += 1) = subSeq size ifTrue: [^ startIndex]]]].
344 c@(Sequence traits) indexOfSubSeq: subSeq startingAt: start
346 c indexOfSubSeq: subSeq startingAt: start ifAbsent: [Nil]
349 c@(Sequence traits) indexOfSubSeq: subSeq
351 c indexOfSubSeq: subSeq startingAt: 0
354 c@(Sequence traits) includesSubSeq: subSeq
356 (c indexOfSubSeq: subSeq) isNotNil
359 c@(Sequence traits) last: n
360 "Answer the last N elements in the Sequence or itself if smaller."
362 c copyFrom: (0 max: c size - n)
365 c@(Sequence traits) lastIndexOf: obj startingAt: start ifAbsent: block
366 "Answer the last index where an element equal to the object is found
367 preceding the start index, executing the block if none."
369 start downTo: 0 do: [| :index | (c at: index) = obj ifTrue: [^ index]].
373 c@(Sequence traits) lastIndexOf: obj ifAbsent: block
375 c lastIndexOf: obj startingAt: c indexLast ifAbsent: block
378 c@(Sequence traits) lastIndexOf: obj
379 "The last index where the object is found or Nil if none."
381 c lastIndexOf: obj startingAt: c indexLast ifAbsent: [Nil]
384 s@(Sequence traits) firstIndexOf: delims@(Collection traits) startingAt: start
385 "Answer the first occurrence of an object in the delimiters, starting at
386 start, returning size on failure."
389 do: [| :index | delims do:
390 [| :obj | obj = (s at: index) ifTrue: [^ index]]].
394 s@(Sequence traits) lastIndexOf: delims@(Collection traits) startingAt: start
395 "Answer the last occurrence of an object in the delimiters, starting at
396 start, returning -1 on failure."
399 do: [| :index | delims do:
400 [| :obj | obj = (s at: index) ifTrue: [^ index]]].
404 c@(Sequence traits) replaceAll: obj with: newOne
405 "Replace all elements equal to the given object with the replacement given."
407 index := c indexOf: obj startingAt: 0.
409 whileFalse: [c at: index put: newOne.
410 index := c indexOf: obj startingAt: index].
413 c@(Sequence traits) replaceFrom: start below: end with: replacement startingAt: repStart
415 c replaceFrom: start to: end - 1 with: replacement startingAt: repStart
418 c@(Sequence traits) replaceFrom: start below: end with: replacement &startingAt: repStart
420 c replaceFrom: start to: end - 1 with: replacement startingAt: (repStart ifNil: [0])
423 c@(Sequence traits) replaceFrom: start to: end with: replacement &startingAt: repStart
425 c replaceFrom: start to: end with: replacement startingAt: (repStart ifNil: [0])
428 c@(Sequence traits) replaceFrom: start to: end with: replacement startingAt: repStart
429 "This destructively modifies the Sequence in a batch operation. It takes care
430 to stay within the range of indices specified and can start from a specified
431 index in the replacement source."
433 repOff := repStart - start.
434 c == replacement /\ [start > repStart]
435 ifTrue: [end downTo: start do:
436 [| :index | c at: index put: (replacement at: repOff + index)]]
437 ifFalse: [start upTo: end do:
438 [| :index | c at: index put: (replacement at: repOff + index)]].
441 c@(Sequence traits) replaceFrom: start with: replacement
442 "Destructively modify the Sequence, beginning at start, with all the elements
443 of the replacement that will fit."
445 c replaceFrom: start to: start + replacement indexLast with: replacement
448 c@(Sequence traits) swap: index1 with: index2
449 "Swaps the objects stored at the given indices."
452 c at: index1 put: (c at: index2).
453 c at: index2 put: obj.
456 c@(Sequence traits) ; d@(Sequence traits)
457 "Concatenates the two Sequences, answering the result."
459 result := c newSize: c size `cache + d size.
460 result replaceFrom: 0 to: c indexLast with: c.
461 result replaceFrom: c size to: result indexLast with: d.
465 c@(Sequence traits) concatenateAll: seq &separator: delim
466 "Answer a new Sequence the result of concatenating the first argument with
467 all of those in the second, interspersed with elements of the specified
468 delimiter Sequence (or nothing when not given)."
469 [| result targetIndex |
471 delim `defaultsTo: #{}.
472 result := c new &capacity:
473 (seq inject: c size into:
474 [| :accum :each | accum + each size])
475 + (seq size - (c isEmpty ifTrue: [1] ifFalse: [0]) * delim size).
478 [result replaceFrom: targetIndex below: c size with: c.
480 result replaceFrom: targetIndex below: targetIndex + delim size with: delim.
481 targetIndex += delim size].
484 eachSize := each size.
485 result replaceFrom: targetIndex below: targetIndex + eachSize with: each.
486 targetIndex += eachSize]
488 [result replaceFrom: targetIndex below: targetIndex + delim size with: delim.
489 targetIndex += delim size].
493 c@(Sequence traits) ;* seq &separator: delim
494 [c concatenateAll: seq &separator: delim].
496 c@(Sequence traits) concatenatedTimes: n
497 "Answer a Sequence the result of concatenating N copies of the original together."
499 result := c new &capacity: c size * n.
500 0 below: result capacity by: c size do:
504 result at: index + srcIndex put: each]].
508 c@(Sequence traits) copyAfter: obj
509 "Answer a similar Sequence of all but the elements before the first matching
512 c allButFirst: (c indexOf: obj ifAbsent: [^ c traits new]) + 1
515 c@(Sequence traits) copyAfterLast: obj
516 "Answer a similar Sequence of all but the elements before the last matching
519 c allButFirst: (c lastIndexOf: obj ifAbsent: [^ c traits new]) + 1
522 c@(Sequence traits) copyFrom: start below: end
524 c copyFrom: start to: end - 1
527 c@(Sequence traits) copyFrom: start to: end
528 "Answer a similar Sequence with the elements from the start to the end
531 end < start \/ [c isEmpty]
533 ifFalse: [(c new &capacity: (newSize: end - start + 1))
534 replaceFrom: 0 to: newSize - 1 with: c startingAt: start]
537 c@(Sequence traits) copyFrom: start
538 [c copyFrom: start to: c indexLast].
540 c@(Sequence traits) copyReplaceFrom: start to: end with: d
541 "Copy with replacement, except if end < start, then this is instead an
542 insertion. start = 0 and end = -1 inserts at the beginning; start = size
544 [| result resultSize endReplace |
545 resultSize := c size + d size `cache - (end - start + 1).
546 endReplace := start - 1 + d size.
547 result := c new &capacity: resultSize.
549 [result replaceFrom: 0 to: start - 1 with: c].
550 start <= endReplace ifTrue:
551 [result replaceFrom: start to: endReplace with: d].
552 endReplace < resultSize ifTrue:
553 [result replaceFrom: endReplace + 1 to: resultSize - 1 with: c startingAt: end + 1].
557 c@(Sequence traits) copyReplaceAll: seq with: replacement
558 "Answer a copy with any occurrences of the (sub)sequence replaced with the
560 [| start result currentIndex end |
563 [(currentIndex := result indexOfSubSeq: seq startingAt: start) isNotNil]
565 [end := currentIndex + seq indexLast.
566 result := result copyReplaceFrom: currentIndex to: end with: replacement.
567 start := currentIndex + replacement size].
571 c@(Sequence traits) copyReplace: element with: obj
572 "Answer a copy with any occurrences of the element replaced with the given
575 result := c newSameSize.
578 result at: index put: (each = element ifTrue: [obj] ifFalse: [each])].
582 c@(Sequence traits) copyUpTo: obj
584 c first: (c indexOf: obj ifAbsent: [^ c copy])
587 c@(Sequence traits) copyUpToLast: obj
589 c first: (c lastIndexOf: obj ifAbsent: [^ c copy])
592 c@(Sequence traits) copyWith: obj
593 "Non-destructively append an object."
595 (c new &capacity: (cs := c size) + 1) `>>
596 [replaceFrom: 0 below: cs with: c.
600 c@(Sequence traits) copyWith: obj at: index
601 "Non-destructively insert an object at a specified index."
603 (c new &capacity: (cs := c size) + 1) `>>
604 [replaceFrom: 0 below: index with: c.
606 replaceFrom: index + 1 to: cs with: c startingAt: index. ]
609 c@(Sequence traits) copyWithoutFirst
614 c@(Sequence traits) copyWithoutAt: index
616 (c new &capacity: (ns := c indexLast)) `>>
617 [replaceFrom: 0 to: index - 1 with: c.
618 replaceFrom: index to: ns - 1 with: c startingAt: index + 1. ]
621 s@(Sequence traits) indexPast: obj startingAt: start
622 "Answer the index of the character within s, starting at start,
623 that does NOT match obj. If s does not contain obj, answer size."
626 do: [| :index | obj = (s at: index) ifFalse: [^ index]].
630 s@(Sequence traits) indexPastAll: delims startingAt: start
631 "Answer the index of the character within the receiver, starting at start,
632 that does NOT match one of the delimiters. If the receiver does not
633 contain any of the delimiters, answer size. Assumes the delimiters to
634 be a non-empty string."
636 start below: s size do:
638 delims detect: [| :c | c = (s at: index)]
643 s@(Sequence traits) indexOfAny: delims startingAt: start
644 "Answer the index of the first element in s, starting at start,
645 that matches any of the delimiters. If s does not contain any of
646 the delimiters, answer s size."
648 start below: s size do:
651 [| :delim | delim = (s at: index) ifTrue: [^ index]]].
655 s@(Sequence traits) splitWith: obj &count: count &includeEmpty: empties
656 "Divides the Sequence up into subsequences as delimited by the given element."
657 "NOTE: This has a forward reference to ExtensibleArray."
658 [| subSeqs keyStart keyEnd |
659 empties `defaultsTo: False.
660 subSeqs := ExtensibleArray new.
661 keyEnd := s indexOf: obj startingAt: 0 ifAbsent: [s size].
662 empties \/ [keyEnd > 0] ifTrue: [subSeqs add: (s copyFrom: 0 to: keyEnd - 1)].
663 [keyEnd < s size] whileTrue:
664 [count isNotNil /\ [subSeqs size >= count] ifTrue:
665 [subSeqs add: (s copyFrom: keyEnd to: s indexLast).
667 keyStart := (s indexOf: obj startingAt: keyEnd ifAbsent: [keyEnd]) + 1.
668 keyEnd := s indexOf: obj startingAt: keyStart ifAbsent: [s size].
669 (keyStart < keyEnd) \/ [empties /\ [keyStart <= keyEnd]] ifTrue:
670 [subSeqs add: (s copyFrom: keyStart to: keyEnd - 1)]].
674 s@(Sequence traits) splitWithAny: delims@(Sequence traits) &count: count
675 "Answer the Sequence of substrings resulting from splitting the string with
676 the given delimiting characters."
677 [| subSeqs keyStart keyEnd |
678 subSeqs := ExtensibleArray new.
680 [keyEnd < s size] whileTrue:
681 [count isNotNil /\ [subSeqs size >= count]
682 ifTrue: [subSeqs add: (s copyFrom: keyEnd to: s indexLast).
684 keyStart := s indexPastAll: delims startingAt: keyEnd.
685 keyEnd := s indexOfAny: delims startingAt: keyStart.
687 ifTrue: [subSeqs add:
688 (s copyFrom: keyStart to: keyEnd - 1)]].
692 c@(Sequence traits) copy
693 "An abstract Sequence copy."
695 c copyFrom: 0 to: c indexLast
698 s@(Sequence traits) copySize: n
699 "Create a new Sequence of the same type and given size, filling in the values
700 with repetitions of the source's contents throughout its length."
703 result := s new &capacity: n.
704 result keysDo: [| :index | result at: index put: (s at: index // s size)].
708 c@(Sequence traits) choose: k of: n into: workingArray do: block
709 "Execute the block on all the combinations of size k out of the sequence.
710 This uses a single array as an iterator object which should not be modified
715 [k isZero] -> [block apply*, workingArray]
717 [workingArray at: k - 1 put: (c at: n - 1).
718 c choose: k - 1 of: n - 1 into: workingArray do: block.
719 c choose: k of: n - 1 into: workingArray do: block. ]
722 c@(Sequence traits) choose: n do: block
723 "Execute the block on all the combinations of size N out of the sequence.
724 This uses a single array as an iterator object which should not be modified
727 c choose: n of: c size into: (Array newSize: n) do: block
730 c@(Sequence traits) collect: block
732 c collectWithIndex: [| :each :_ | block apply*, each] into: c newSameSize
735 c@(Sequence traits) collect: block from: start to: end
737 end < start \/ [c isEmpty]
740 [result := c new &capacity: end - start + 1.
742 result keysDo: [| :index | result at: index put: (block apply*, (c at: j)). j += 1].
746 c@(Sequence traits) collectWithIndex: binBlock
747 "binBlock should take :element and :index."
749 c collectWithIndex: binBlock into: c newSameSize
752 c@(Sequence traits) do: block
755 [0 below: c size do: [| :index | block apply*, (c at: index)]].
758 c@(Sequence traits) pairsDo: block
759 "Apply the block to each distinct pair of sequential elements. The Sequence
760 must have an even size."
762 (c size rem: 2) isZero
763 ifTrue: [0 below: c size by: 2 do:
764 [| :index | block apply*, (c at: index), (c at: index + 1)]]
765 ifFalse: [error: 'This collection has an odd number of elements'].
768 c@(Sequence traits) chainPairsDo: block
769 "Apply the block to each distinct pair of sequential elements in a
770 next-last pairing so that each element is an argument twice, once in each
771 position (except the first and last elements, of course)."
773 c indexFirst below: c indexLast do:
774 [| :index | block apply*, (c at: index), (c at: index + 1)].
777 c@(Sequence traits) do: block separatedBy: sepBlock
778 "Run the separator block between applying the block to each element."
781 [block apply*, c first.
782 1 below: c size do: [| :index | sepBlock do. block apply*, (c at: index)]].
785 c@(Sequence traits) doWithIndex: block separatedBy: sepBlock
786 "Run the separator block between applying the block to each element."
789 [block apply*, c first, 0.
790 1 below: c size do: [| :index | sepBlock do. block apply*, (c at: index), index]].
793 c@(Sequence traits) from: start to: end do: block
795 (start between: c indexFirst and: end) /\ [end <= c indexLast] ifTrue:
796 [start to: end do: [| :index | block apply*, (c at: index)]].
799 c@(Sequence traits) allButFirst: n do: block
800 "Apply the block to all elements but the first N in the Sequence."
802 c from: n to: c indexLast do: block
805 c@(Sequence traits) allButFirstDo: block
807 c allButFirst: 1 do: block
810 c@(Sequence traits) allButLast: n do: block
811 "Apply the block to all but the last N members of the Sequence."
813 n >= c size ifTrue: [^ Nil].
814 c from: 0 to: c indexLast - n do: block
817 c@(Sequence traits) allButLastDo: block
819 c allButLast: 1 do: block
822 c@(Sequence traits) doWithIndex: binBlock
823 "binBlock takes :each object and its :index."
827 [| :index | binBlock apply*, (c at: index), index]].
830 c@(Sequence traits) collectWithIndex: binBlock into: seq@(Sequence traits)
831 "Runs doWithIndex: on binBlock, collecting results implicitly into the other
832 Sequence at the same locations as the arguments, and returning that result."
835 [| :each :index | seq at: index put: (binBlock apply*, each, index)].
839 c@(Sequence traits) do: block every: step
840 "Invoke the block on every n'th argument."
842 c do: block every: step startingAt: 0
845 c@(Sequence traits) do: block every: step startingAt: start
846 "Invoke the block on every n'th argument, starting at a particular index."
850 steps := (c size - start) // step.
852 [block apply*, (c at: index). index += step]].
855 c@(Sequence traits) do: block inGroupsOf: arity
856 "Send the elements of the target to the block in the number of its arity. If
857 fewer than that are remaining, abort and return."
859 c do: block inGroupsOf: arity startingAt: 0
862 c@(Sequence traits) do: block inGroupsOf: arity startingAt: start
863 "Send the elements of the target to the block in the number of its arity,
864 beginning with a given index. If fewer than that are remaining, abort and
868 steps := (c size - start) // arity.
870 block applyTo: (c copyFrom: index to: index + arity - 1).
874 c@(Sequence traits) indexOfFirstSatisfying: block startingAt: start
875 "Find the index of the first occurrence of an object satisfying the block
876 starting at the given index."
878 start below: c size do: [| :index |
879 (block apply*, (c at: index)) ifTrue: [^ index]].
882 c@(Sequence traits) indexOfFirstSatisfying: block
883 "Find the index of the first occurrence of an object satisfying the block."
885 c indexOfFirstSatisfying: block startingAt: 0
888 c@(Sequence traits) indexOfLastSatisfying: block before: end
889 "Find the index of the last occurrence of an object satisfying the block
890 before the given index."
892 end - 1 downTo: 0 do: [| :index |
893 (block apply*, (c at: index)) ifTrue: [^ index]].
896 c@(Sequence traits) indexOfLastSatisfying: block
897 "Find the index of the last occurrence of an object satisfying the block."
899 c indexOfLastSatisfying: block before: c size
902 c@(Sequence traits) firstSatisfying: block startingAt: start
903 "Answer the first occurrence of an object satisfying the block."
904 [c at: ((c indexOfFirstSatisfying: block startingAt: start) ifNil: [^ Nil])].
906 c@(Sequence traits) firstSatisfying: block
907 "Answer the first occurrence of an object satisfying the block."
908 [c at: ((c indexOfFirstSatisfying: block) ifNil: [^ Nil])].
910 c@(Sequence traits) lastSatisfying: block before: end
911 "Answer the last occurrence of an object satisfying the block."
912 [c at: ((c indexOfLastSatisfying: block before: end) ifNil: [^ Nil])].
914 c@(Sequence traits) lastSatisfying: block
915 "Answer the last occurrence of an object satisfying the block."
916 [c at: ((c indexOfLastSatisfying: block) ifNil: [^ Nil])].
918 c@(Sequence traits) reverseDoWithIndex: block
919 "The reverse performance of doWithIndex: of course."
921 c indexLast downTo: 0 do: [| :index | block apply*, (c at: index), index].
924 c@(Sequence traits) reverseDo: block
925 "The reverse performance of do:."
927 c indexLast downTo: 0 do: [| :index | block apply*, (c at: index)].
930 c@(Sequence traits) reverseWith: d do: block
931 "The reverse performance of with:do:."
933 1 to: (c size `cache min: d size `cache) do:
935 block apply*, (c at: c size - index), (d at: d size - index)].
938 c@(Sequence traits) shiftFrom: index by: steps count: items
939 "Shifts 'count:' elements from index by the specified amount, positive
940 indicating right-ward. Overwritten elements are shifted back-ward."
943 elems := c copyFrom: index below: index + items.
944 steps isNegative ifTrue:
945 [steps := steps abs. index += items - 1. items := items negated].
947 c at: index put: (c at: index + items).
948 index += items sign].
949 items isNegative ifTrue: [index += items + 1].
950 c replaceFrom: index with: elems
953 c@(Sequence traits) shiftFrom: index by: steps
954 "See shiftFrom:by:count:"
956 c shiftFrom: index by: steps count: 1
959 c@(Sequence traits) rotate ×: count
960 "Rotate all elements in the Sequence in-place by the specified amount, positive
961 indicating right-ward (increasing indices of elements until wrapped around)."
963 count `defaultsTo: 1.
964 count := count mod: c size.
966 ifTrue: [index := c size - count. steps := count - c size]
967 ifFalse: [index := 0. steps := c size + count].
968 c shiftFrom: index by: steps count: count
971 c@(Sequence traits) rotated ×: count
972 "Answer a new Sequence of the same size with the elements rotated by the
973 specified amount, positive indicating right-ward (increasing indices of
974 elements until wrapped around)."
976 count `defaultsTo: 1.
977 c size isZero \/ count isZero
980 [count := count mod: c size.
981 index := c size - count mod: c size.
983 [replaceFrom: 0 with: (c sliceFrom: index).
984 replaceFrom: c size - index with: c. ]]
987 c@(Sequence traits) mapSelect: block
988 [c mapSelect: block into: c newSameSize].
990 c@(Sequence traits) with: d@(Sequence traits) collect: binBlock
991 "Collect the result from applying the block to as many pairs of elements from
992 each Sequence as possible."
994 result := c new &capacity: (c size min: d size).
995 result keysDo: [| :index |
996 result at: index put: (binBlock apply*, (c at: index), (d at: index))].
1000 c@(Sequence traits) with: d@(Sequence traits) do: binBlock
1001 "Apply the block to as many pairs of elements from each Sequence as possible."
1003 0 below: (c size min: d size) do: [| :index |
1004 binBlock apply*, (c at: index), (d at: index)].
1007 c@(Sequence traits) gather: binBlock &initial: init
1017 [| :each | result := binBlock apply*, result, each]]
1020 c do: [| :each | result := binBlock apply*, result, each]].
1024 c@(Sequence traits) reverseGather: binBlock &initial: init
1033 c reverseAllButLastDo:
1034 [| :each | result := binBlock apply*, result, each]]
1037 c reverseDo: [| :each | result := binBlock apply*, result, each]].
1041 c@(Sequence traits) reduce: binBlock ifEmpty: emptyBlock
1042 "Reduce works like inject except that the first element of the collection is
1043 used as the injected element for the rest of the collection.
1044 e.g. #{1. 2. 3 .4} reduce: [| :a :b | a + b] returns a sum of the elements."
1047 ifTrue: [emptyBlock do]
1048 ifFalse: [| result |
1051 [| :each | result := binBlock apply*, result, each].
1055 c@(Sequence traits) reverseAllButLastDo: block
1056 "allButLastDo: in reversed order"
1058 c indexLast - 1 downTo: c indexFirst do:
1059 [| :index | block apply*, (c at: index)].
1062 c@(Sequence traits) reverseReduce: binBlock ifEmpty: emptyBlock
1063 "Like foldr in Haskell or Sequence reversed reduce:ifEmpty:"
1066 ifTrue: [emptyBlock do]
1070 c reverseAllButLastDo:
1071 [| :each | result := binBlock apply*, result, each].
1075 c@(Sequence traits) reverseReduce: binBlock
1076 "Like foldr in Haskell or Sequence reversed reduce:"
1078 c reverseReduce: binBlock ifEmpty: []
1081 prefix@(Sequence traits) isPrefixOf: seq@(Sequence traits)
1082 "Answer whether the first elements of the Sequence match the potential prefix
1083 Sequence's elements in order."
1085 prefix size <= seq size
1086 /\ [prefix doWithIndex: [| :each :index |
1087 each = (seq at: index) ifFalse: [^ False]].
1091 suffix@(Sequence traits) isSuffixOf: seq@(Sequence traits)
1092 "Answer whether the last elements of the Sequence match the potential suffix
1093 Sequence's elements in order."
1095 seq size >= suffix size /\
1097 seqIndex := seq indexLast.
1098 suffix reverseDoWithIndex:
1100 each = (seq at: seqIndex) ifFalse: [^ False].
1105 c@(Sequence traits) reverse
1106 "Reverse the element order of the Sequence in place."
1108 0 to: c indexLast `cache // 2 do:
1109 [| :index | c swap: index with: c indexLast - index].
1113 c@(Sequence traits) reversed
1114 "Answer a new Sequence with the element order reversed."
1116 result := c new &capacity: c size `cache.
1118 c keysDo: [| :destIdx | result at: destIdx put: (c at: (srcIdx -= 1))].
1122 a@(Sequence traits) isSortedBy: block
1123 "Whether the elements in the Sequence are arranged in order by the block
1126 a isEmpty ifTrue: [^ True].
1128 1 below: a size do: [| :index |
1130 (block apply*, lastObj, obj) ifFalse: [^ False].
1135 s@(Sequence traits) sortFrom: start to: end by: block
1136 "Perform a quick-sort within the start/end bounds using the sort block."
1138 start >= end ifTrue: [^ s].
1141 pivot := s at: start.
1144 [[low <= high /\ [block apply*, (s at: low), pivot]]
1145 whileTrue: [low += 1].
1146 [low <= high /\ [block apply*, pivot, (s at: high)]]
1147 whileTrue: [high -= 1].
1149 ifTrue: [s swap: low with: high]].
1153 [s swap: start with: low.
1154 s sortFrom: start to: low - 1 by: block].
1157 [s sortFrom: low + 1 to: end by: block].
1161 a@(Sequence traits) destructiveSortBy: block
1162 "Sort the elements by a binary block comparison. Perform a quick-sort by
1163 default. The sense of the block is that it should return the equivalent of
1164 <=: whether the first element not greater than the second."
1166 a sortFrom: 0 to: a indexLast by: block
1169 a@(Sequence traits) destructiveSort &comparison: block
1170 "The default comparison given to sort the Sequence's elements is <=."
1172 a destructiveSortBy: (block ifNil: [#<=`er])
1175 s@(Sequence traits) stableSortFrom: start to: end by: block
1176 "Perform a stable sort (using merge-sort algorithm) within the
1177 start/end bounds using the sort block."
1178 [| middle scopy i1 i2 val1 val2 out |
1179 s size <= 1 ifTrue: [^ s].
1180 end > s size ifTrue: [end := s size].
1181 start >= end ifTrue: [^ s].
1182 middle := (start + end) // 2.
1184 scopy stableSortFrom: start to: middle by: block.
1185 scopy stableSortFrom: middle + 1 to: end by: block.
1188 val1 := scopy at: i1.
1189 val2 := scopy at: i2.
1191 [(i1 <= middle) /\ [i2 <= end]] whileTrue:
1192 [(block apply*, val1, val2)
1193 ifTrue: [s at: (out += 1) put: val1.
1194 val1 := scopy at: (i1 := i1 + 1)]
1195 ifFalse: [s at: (out += 1) put: val2.
1197 i2 <= end ifTrue: [val2 := scopy at: i2]]].
1199 ifTrue: [s replaceFrom: out + 1 to: end with: scopy startingAt: i1]
1200 ifFalse: [s replaceFrom: out + 1 to: end with: scopy startingAt: i2]
1203 s@(Sequence traits) destructiveStableSortBy: block
1205 s stableSortFrom: 0 to: s indexLast by: block
1208 s@(Sequence traits) destructiveStableSort &comparison: block
1210 s destructiveStableSortBy: (block ifNil: [#<=`er])
1213 s@(Sequence traits) sortBy: sortBlock attributeBlock: slowBlock
1214 "This applies the 'Schwartzian Transform', suitable for when a sort needs
1215 to be performed by comparing the values of an expensive calculation on the
1216 values. By caching the results of the calculation using Associations,
1217 the use of the block is limited to O(N). An intermediate Sequence is
1220 ((s collect: [| :each | each -> (slowBlock apply*, each)])
1221 destructiveSortBy: [| :a :b | sortBlock apply*, a value, b value])
1225 x caseOf: cases@(Sequence traits) otherwise: block
1226 "A Sequence of Associations between Objects and Blocks is used as a control
1227 structure. Matching against the first argument causes the respective block
1228 to be evaluated and its result returned. If none match, an alternative block
1229 is provided which then is evaluated for an answer."
1231 cases do: [| :assoc | assoc key = x ifTrue: [^ assoc value do]].
1235 x caseOf: cases@(Sequence traits)
1236 "Executes the case-switching logic with a null alternative block."
1237 [x caseOf: cases otherwise: []].
1239 x conditions: conds@(Sequence traits) otherwise: block
1240 "A Sequence of Associations between Blocks is used as a control structure.
1241 Each key is evaluated and if it answers True, the associated block is evaluated
1242 and its answer passed along, and evaluation stops. If none are true, an
1243 alternative block is provided which then is evaluated for an answer."
1245 conds do: [| :assoc | assoc key do ifTrue: [^ assoc value do]].
1249 x conditions: conds@(Sequence traits)
1250 "Executes the condition-switching logic with a null alternative block."
1251 [x conditions: conds otherwise: []].
1253 c@(Sequence traits) collect: block into: seq@(Sequence traits)
1254 "Specialized to handle sequences which are not Extensible. This returns a
1255 result of applying the block to each element, which may not be the given
1256 Sequence if it was not of the right size."
1258 c collectWithIndex: [| :each :_ | block apply*, each]
1259 into: (seq capacity = c size ifTrue: [seq] ifFalse: [seq newSizeOf: c])
1262 s@(Sequence traits) splitIntoSize: n
1263 "Answers the result of splitting the sequence into n-sized sequences.
1264 If size of the sequence is not divisible by n, the last element will be
1268 [n <= 0] -> [error: 'Split size must be positive.'].
1269 [n >= s size] -> [{s copy}]
1271 [| subSeqs sepIndex |
1272 subSeqs := (Array newSize: s size // n + 1) writer.
1274 [sepIndex < (s size - (s size mod: n))]
1275 whileTrue: [subSeqs nextPut: (s copyFrom: sepIndex to: sepIndex + n - 1).
1277 sepIndex = s size "There are extra elements; a remainder to be added."
1278 ifFalse: [subSeqs nextPut: (s copyFrom: sepIndex to: s indexLast)].
1282 x@(Sequence traits) beginsWith: y@(Sequence traits)
1283 "Answer whether the sequence begins with another sequence."
1286 [x with: y do: [| :each1 :each2 | each1 = each2 ifFalse: [^ False]]. True]
1289 x@(Sequence traits) endsWith: y@(Sequence traits)
1290 "Answer whether the sequence ends with another sequence."
1293 [x reverseWith: y do: [| :each1 :each2 | each1 = each2 ifFalse: [^ False]]. True]
1296 x@(Sequence traits) truncateTo: limit paddedBy: padElement &onRight: onRight
1299 ifTrue: [(onRight `defaultsTo: False)
1300 ifTrue: [x ; (padElement repeatedTimes: limit - x size)]
1301 ifFalse: [x new ; (padElement repeatedTimes: limit - x size) ; x]]
1302 ifFalse: [x sliceUpTo: limit]
1305 x@(Sequence traits) truncateTo: limit
1306 "Return a new Sequence no longer than the limit or the sequence itself if it is
1307 shorter than the limit."
1310 ifTrue: [x sliceUpTo: limit]