The Inbox: Collections-nice.869.mcz

> Nicolas Cellier uploaded a new version of Collections to project The
> Inbox:
> http://source.squeak.org/inbox/Collections-nice.869.mcz
>
> ==================== Summary ====================
>
> Name: Collections-nice.869
> Author: nice
> Time: 31 December 2019, 11:14:43.388306 pm
> UUID: e5a9bef5-16d3-4d8a-bf08-040d30e4e907
> Ancestors: Collections-nice.868
>
> Remaster Collections-nice.464: opimize RunArray
>
> This should not be noticeable for Text, but as a general library, it's
> important for any other potential use.
>
> Among those optimizations, notice one important change: some of the
> enumerating methods like #collect: won't iterate on each element, but only
> once per run. Be aware that providing blocks with side effects like (i :=
> i + 1) might lead to different behavior than ordinary ArrayedCollection.
>
> Move RunArray off ArrayedCollection which serves nothing to such subclass.
>
> Add the ability to remove: since it already has the hability to addFirst:
> and addLast:
>
> Fix a few missing lastIndex cache flush, and advertise about the necessity
> to do it in class comment.
>
> Deprecate mapValues: to the profit of replace:.
>
> =============== Diff against Collections-nice.868 ===============
>
> Item was changed:
> + SequenceableCollection subclass: #RunArray
> - ArrayedCollection subclass: #RunArray
>   instanceVariableNames: 'runs values lastIndex lastRun lastOffset'
>   classVariableNames: ''
>   poolDictionaries: ''
>   category: 'Collections-Arrayed'!
>  
> + !RunArray commentStamp: 'nice 12/30/2019 00:57' prior: 0!
> - !RunArray commentStamp: '
> <historical>
> ' prior: 0!
>   My instances provide space-efficient storage of data which tends to be
> constant over long runs of the possible indices. Essentially repeated
> values are stored singly and then associated with a "run" length that
> denotes the number of consecutive occurrences of the value.
>  
>   My two important variables are
>   runs An array of how many elements are in each run
>   values An array of what the value is over those elements
>  
>   The variables lastIndex, lastRun and lastOffset cache the last access
>   so that streaming through RunArrays is not an N-squared process.
> + Beware: methods modifying the RunArray contents should reset the
> lastIndex cache to nil.
>  
>   Many complexities of access can be bypassed by using the method
>   RunArray withStartStopAndValueDo:!
>
> Item was changed:
>   ----- Method: RunArray class>>newFrom: (in category 'instance creation')
> -----
>   newFrom: aCollection
>   "Answer an instance of me containing the same elements as aCollection."
>  
>   | newCollection |
>   newCollection := self new.
> + newCollection fillFrom: aCollection with: [:each | each].
> - aCollection do: [:x | newCollection addLast: x].
>   ^newCollection
>  
>   " RunArray newFrom: {1. 2. 2. 3}
>   {1. $a. $a. 3} as: RunArray
>   ({1. $a. $a. 3} as: RunArray) values
>   "!
>
> Item was added:
> + ----- Method: RunArray>>allSatisfy: (in category 'enumerating') -----
> + allSatisfy: aBlock
> + "Only evaluate once per run"
> +
> + ^values allSatisfy: aBlock!
>
> Item was added:
> + ----- Method: RunArray>>anySatisfy: (in category 'enumerating') -----
> + anySatisfy: aBlock
> + "Only evaluate once per run"
> +
> + ^values anySatisfy: aBlock!
>
> Item was added:
> + ----- Method: RunArray>>asBag (in category 'converting') -----
> + asBag
> + | aBag |
> + aBag := Bag new: values size.
> + self runsAndValuesDo: [:run :value |
> + aBag add: value withOccurrences: run].
> + ^aBag!
>
> Item was added:
> + ----- Method: RunArray>>asSet (in category 'converting') -----
> + asSet
> + ^values asSet!
>
> Item was changed:
> + ----- Method: RunArray>>coalesce (in category 'private') -----
> - ----- Method: RunArray>>coalesce (in category 'adding') -----
>   coalesce
> + "Coalesce theRuns and theValues if ever the values have adjacent equal
> objects"
> +
> + | lastLength lastValue mustCoalesce coalescedRuns coalescedValued
> runIndex |
> + mustCoalesce := false.
> + runIndex := 0.
> + lastLength := 0.
> + lastValue := Object new.
> + runs with: values do: [:run :value |
> + (lastValue = value or: [run = 0])
> + ifTrue:
> + [mustCoalesce
> + ifFalse:
> + [coalescedRuns := (Array new: runs size) writeStream.
> + coalescedValued := (Array new: values size) writeStream.
> + coalescedRuns next: runIndex putAll: runs startingAt: 1.
> + coalescedValued next: runIndex putAll: values startingAt: 1.
> + mustCoalesce := true].
> + lastLength := lastLength + run]
> + ifFalse:
> + [lastLength > 0
> + ifTrue:
> + [mustCoalesce
> + ifTrue:
> + [coalescedRuns nextPut: lastLength.
> + coalescedValued nextPut: lastValue].
> + runIndex := runIndex + 1].
> + lastLength := run.
> + lastValue := value]].
> + mustCoalesce
> + ifTrue:
> + [lastLength > 0
> + ifTrue:
> + [coalescedRuns nextPut: lastLength.
> + coalescedValued nextPut: lastValue].
> + self setRuns: coalescedRuns contents setValues: coalescedValued
> contents]!
> - "Try to combine adjacent runs"
> - | ind |
> - ind := 2.
> - [ind > values size] whileFalse: [
> - (values at: ind-1) = (values at: ind)
> - ifFalse: [ind := ind + 1]
> - ifTrue: ["two are the same, combine them"
> - values := values copyReplaceFrom: ind to: ind with: #().
> - runs at: ind-1 put: (runs at: ind-1) + (runs at: ind).
> - runs := runs copyReplaceFrom: ind to: ind with: #().
> - "self error: 'needed to combine runs' "]].
> - !
>
> Item was added:
> + ----- Method: RunArray>>collect: (in category 'enumerating') -----
> + collect: aBlock
> + "Beware, the block will be evaluated only once per group of values."
> + ^(self class runs: runs copy values: (values collect: aBlock))
> coalesce!
>
> Item was added:
> + ----- Method: RunArray>>copyUpThrough: (in category 'copying') -----
> + copyUpThrough: value
> + "Optimized"
> +
> + | newSize newValues newRuns |
> + newSize := values indexOf: value startingAt: 1.
> + newSize = 0 ifTrue: [^self copy].
> + newRuns := runs copyFrom: 1 to: newSize.
> + newRuns at: newSize put: 1.
> + newValues := values copyFrom: 1 to: newSize.
> + ^ self class
> + runs: newRuns
> + values: newValues!
>
> Item was added:
> + ----- Method: RunArray>>copyUpTo: (in category 'copying') -----
> + copyUpTo: anElement
> + "Optimized"
> +
> + | newValues |
> + newValues := values copyUpTo: anElement.
> + ^ self class
> + runs: (runs copyFrom: 1 to: newValues size)
> + values: newValues!
>
> Item was added:
> + ----- Method: RunArray>>copyUpToLast: (in category 'copying') -----
> + copyUpToLast: value
> + "Optimized"
> +
> + | newSize run newRuns newValues |
> + newSize := values lastIndexOf: value startingAt: values size.
> + newSize = 0 ifTrue: [^self copy].
> + run := runs at: newSize.
> + run > 1
> + ifTrue:
> + [newRuns := runs copyFrom: 1 to: newSize.
> + newRuns at: newSize put: run - 1]
> + ifFalse:
> + [newSize := newSize - 1.
> + newRuns := runs copyFrom: 1 to: newSize].
> + newValues := values copyFrom: 1 to: newSize.
> + ^ self class
> + runs: newRuns
> + values: newValues!
>
> Item was added:
> + ----- Method: RunArray>>count: (in category 'enumerating') -----
> + count: aBlock
> + "Beware, the block will be evaluated only once per group of values."
> + | count |
> + count := 0.
> + self runsAndValuesDo: [:run :value |
> + (aBlock value: value)
> + ifTrue:
> + [count := count + run]].
> + ^count!
>
> Item was added:
> + ----- Method: RunArray>>detect:ifNone: (in category 'enumerating') -----
> + detect: aBlock ifNone: exceptionBlock
> + "Only evaluate once per run"
> +
> + ^values detect: aBlock ifNone: exceptionBlock !
>
> Item was added:
> + ----- Method: RunArray>>detectMax: (in category 'enumerating') -----
> + detectMax: aBlock
> + "Only evaluate once per run"
> +
> + ^values detectMax: aBlock!
>
> Item was added:
> + ----- Method: RunArray>>detectMin: (in category 'enumerating') -----
> + detectMin: aBlock
> + "Only evaluate once per run"
> +
> + ^values detectMin: aBlock!
>
> Item was added:
> + ----- Method: RunArray>>detectSum: (in category 'enumerating') -----
> + detectSum: aBlock
> + "Only loop on runs"
> + | sum |
> + sum := 0.
> + self runsAndValuesDo: [:run :value |
> + sum := (aBlock value: value) * run + sum].  
> + ^ sum!
>
> Item was added:
> + ----- Method: RunArray>>do: (in category 'enumerating') -----
> + do: aBlock
> + "This is refined for speed"
> +
> + 1 to: runs size do: [:i |
> + | r v |
> + v := values at: i.
> + r := runs at: i.
> + [( r := r - 1) >= 0]
> + whileTrue: [aBlock value: v]].!
>
> Item was added:
> + ----- Method: RunArray>>fillFrom:with: (in category 'private') -----
> + fillFrom: aCollection with: aBlock
> + "Evaluate aBlock with each of aCollections's elements as the argument.  
> + Collect the resulting values into self. Answer self."
> +
> + | newRuns newValues lastLength lastValue |
> + newRuns := (Array new: aCollection size) writeStream.
> + newValues := (Array new: aCollection size) writeStream.
> + lastLength := 0.
> + lastValue := Object new.
> + lastIndex := nil.  "flush access cache"
> + aCollection do: [:each |
> + | value |
> + value := aBlock value: each.
> + lastValue = value
> + ifTrue: [lastLength := lastLength + 1]
> + ifFalse:
> + [lastLength > 0
> + ifTrue:
> + [newRuns nextPut: lastLength.
> + newValues nextPut: lastValue].
> + lastLength := 1.
> + lastValue := value]].
> + lastLength > 0
> + ifTrue:
> + [newRuns nextPut: lastLength.
> + newValues nextPut: lastValue].
> + self setRuns: newRuns contents setValues: newValues contents!
>
> Item was added:
> + ----- Method: RunArray>>findFirst: (in category 'enumerating') -----
> + findFirst: aBlock
> + | index |
> + index := 1.
> + self runsAndValuesDo: [ :run :value |
> + (aBlock value: value) ifTrue: [^index].
> + index := index + run].
> + ^0!
>
> Item was added:
> + ----- Method: RunArray>>findLast: (in category 'enumerating') -----
> + findLast: aBlock
> + | index |
> + index := values size + 1.
> + [(index := index - 1) >= 1] whileTrue:
> + [(aBlock value: (values at: index)) ifTrue: [^(1 to: index) detectSum:
> [:i | runs at: i]]].
> + ^0!
>
> Item was added:
> + ----- Method: RunArray>>includes: (in category 'testing') -----
> + includes: anObject
> + "Answer whether anObject is one of the receiver's elements."
> +
> + ^values includes: anObject!
>
> Item was added:
> + ----- Method: RunArray>>indexOf:startingAt: (in category 'accessing')
> -----
> + indexOf: anElement startingAt: start
> + "Answer the index of the first occurence of anElement after start
> + within the receiver. If the receiver does not contain anElement,
> + answer 0."
> +
> + | index |
> + index := 1.
> + self runsAndValuesDo: [ :run :value |
> + (index >= start and: [value = anElement]) ifTrue: [^index].
> + index := index + run].
> + ^0!
>
> Item was added:
> + ----- Method: RunArray>>indexOfAnyOf:startingAt: (in category
> 'accessing') -----
> + indexOfAnyOf: aCollection startingAt: start
> + "Answer the index of the first occurence of any element included in
> aCollection after start within the receiver.
> + If the receiver does not contain anElement, answer zero, which is an
> invalid index."
> +
> + | index |
> + index := 1.
> + self runsAndValuesDo: [ :run :value |
> + (index >= start and: [aCollection includes: value]) ifTrue: [^index].
> + index := index + run].
> + ^0!
>
> Item was added:
> + ----- Method: RunArray>>isSorted (in category 'testing') -----
> + isSorted
> + ^values isSorted!
>
> Item was added:
> + ----- Method: RunArray>>isSortedBy: (in category 'testing') -----
> + isSortedBy: aBlock
> + ^values isSortedBy: aBlock!
>
> Item was added:
> + ----- Method: RunArray>>lastIndexOf:startingAt: (in category
> 'accessing') -----
> + lastIndexOf: anElement startingAt: lastIndex
> + "Answer the index of the last occurence of anElement within the  
> + receiver. If the receiver does not contain anElement, answer 0."
> +
> + | lastValueIndex |
> + lastValueIndex := values lastIndexOf: anElement startingAt: values
> size.
> + [lastValueIndex > 0] whileTrue:
> + [| i index |
> + i := index := 0.
> + [index <= lastIndex and: [(i := i + 1) <= lastValueIndex]]
> + whileTrue: [index := index + (runs at: i)].
> + index <= lastIndex ifTrue: [^index].
> + index - (runs at: lastValueIndex) < lastIndex ifTrue: [^lastIndex].
> + lastValueIndex := values lastIndexOf: anElement startingAt:
> lastValueIndex - 1].
> + ^0!
>
> Item was added:
> + ----- Method: RunArray>>lastIndexOfAnyOf:startingAt: (in category
> 'accessing') -----
> + lastIndexOfAnyOf: aCollection startingAt: lastIndex
> + "Answer the index of the last occurence of any element of aCollection
> + within the receiver. If the receiver does not contain any of those
> + elements, answer 0"
> +
> + | lastValueIndex |
> + lastValueIndex := values lastIndexOfAnyOf: aCollection startingAt:
> values size.
> + [lastValueIndex > 0] whileTrue:
> + [| i index |
> + i := index := 0.
> + [index <= lastIndex and: [(i := i + 1) <= lastValueIndex]]
> + whileTrue: [index := index + (runs at: i)].
> + index <= lastIndex ifTrue: [^index].
> + index - (runs at: lastValueIndex) < lastIndex ifTrue: [^lastIndex].
> + lastValueIndex := values lastIndexOfAnyOf: aCollection startingAt:
> lastValueIndex - 1].
> + ^0!
>
> Item was removed:
> - ----- Method: RunArray>>mapValues: (in category 'private') -----
> - mapValues: mapBlock
> - "NOTE: only meaningful to an entire set of runs"
> -
> - values := values collect: mapBlock!
>
> Item was added:
> + ----- Method: RunArray>>noneSatisfy: (in category 'enumerating') -----
> + noneSatisfy: aBlock
> + "Only evaluate once per run"
> +
> + ^values noneSatisfy: aBlock!
>
> Item was changed:
> + ----- Method: RunArray>>rangeOf:startingAt: (in category 'accessing')
> -----
> - ----- Method: RunArray>>rangeOf:startingAt: (in category 'adding') -----
>   rangeOf: attr startingAt: startPos
>   "Answer an interval that gives the range of attr at index position
> startPos. An empty interval with start value startPos is returned when the
> attribute attr is not present at position startPos.  self size > 0 is
> assumed, it is the responsibility of the caller to test for emptiness of
> self.
>   Note that an attribute may span several adjancent runs. "
>  
>   self at: startPos
>   setRunOffsetAndValue:
>               [:run :offset :value |
>                  ^(value includes: attr)
>                     ifFalse: [startPos to: startPos - 1]
>                     ifTrue:
>                       [ | firstRelevantPosition lastRelevantPosition
> idxOfCandidateRun |
>                        lastRelevantPosition := startPos - offset + (runs
> at: run) - 1.
>                        firstRelevantPosition := startPos - offset.
>                        idxOfCandidateRun := run + 1.
>                        [idxOfCandidateRun <= runs size
>                                and: [(values at: idxOfCandidateRun)
> includes: attr]]
>                           whileTrue:
>                             [lastRelevantPosition := lastRelevantPosition
> + (runs at: idxOfCandidateRun).
>                              idxOfCandidateRun := idxOfCandidateRun + 1].
>                        idxOfCandidateRun := run - 1.
>                        [idxOfCandidateRun >= 1
>                                and: [(values at: idxOfCandidateRun)
> includes: attr]]
>                           whileTrue:
>                             [firstRelevantPosition :=
> firstRelevantPosition - (runs at: idxOfCandidateRun).
>                              idxOfCandidateRun := idxOfCandidateRun - 1].
>    
>                       firstRelevantPosition to: lastRelevantPosition]
>    ]!
>
> Item was added:
> + ----- Method: RunArray>>remove:ifAbsent: (in category 'removing') -----
> + remove: anObject ifAbsent: exceptionBlock
> + | index mustCoalesce run |
> + lastIndex := nil.  "flush access cache"
> + index := values indexOf: anObject ifAbsent: [^exceptionBlock value].
> + (run := runs at: index) > 1
> + ifTrue: [runs at: index put: run - 1]
> + ifFalse:
> + [mustCoalesce := index > 1 and: [index < values size and: [(values
> at: index - 1) = (values at: index + 1)]].
> + runs := runs copyWithoutIndex: index.
> + values := values copyWithoutIndex: index.
> + mustCoalesce
> + ifTrue:
> + [runs at: index - 1 put: (runs at: index - 1) + (runs at: index).
> + runs := runs copyWithoutIndex: index.
> + values := values copyWithoutIndex: index]].
> + ^anObject!
>
> Item was added:
> + ----- Method: RunArray>>removeAll (in category 'removing') -----
> + removeAll
> + lastIndex := nil.  "flush access cache"
> + runs := Array new.
> + values := Array new!
>
> Item was added:
> + ----- Method: RunArray>>replace: (in category 'enumerating') -----
> + replace: aBlock
> + "destructively replace the values in this RunArray with the ones
> transformed by aBlock."
> + lastIndex := nil.  "flush access cache"
> + values := values replace: aBlock.
> + self coalesce!
>
> Item was added:
> + ----- Method: RunArray>>reverseDo: (in category 'enumerating') -----
> + reverseDo: aBlock
> + "This is refined for speed"
> +
> + | i |
> + i := runs size.
> + [i > 0]
> + whileTrue:
> + [ | r v |
> + v := values at: i.
> + r := runs at: i.
> + i := i - 1.
> + [( r := r - 1) >= 0]
> + whileTrue: [aBlock value: v]].!
>
> Item was added:
> + ----- Method: RunArray>>select: (in category 'enumerating') -----
> + select: aBlock
> + "Beware, the block will be evaluated only once per group of values."
> + | newRuns newValues |
> + newRuns := (Array new: runs size) writeStream.
> + newValues := (Array new: values size) writeStream.
> + self runsAndValuesDo: [:run :value |
> + (aBlock value: value)
> + ifTrue:
> + [newRuns nextPut: run.
> + newValues nextPut: value]].
> + ^(self class runs: newRuns contents values: newValues contents)
> coalesce!
>
> Item was changed:
>   ----- Method: SequenceableCollection>>lastIndexOf:startingAt: (in
> category 'accessing') -----
>   lastIndexOf: anElement startingAt: lastIndex
>   "Answer the index of the last occurence of anElement within the  
> + receiver. If the receiver does not contain anElement, answer 0."
> - receiver. If the receiver does not contain anElement, answer the
> - result of evaluating the argument, exceptionBlock."
>  
>   lastIndex to: 1 by: -1 do: [ :index |
>   (self at: index) = anElement ifTrue: [ ^index ] ].
>   ^0!
>
> Item was changed:
>   ----- Method: Text>>addAttribute:from:to: (in category 'emphasis') -----
>   addAttribute: att from: start to: stop
>   "Set the attribute for characters in the interval start to stop."
>   runs :=  runs copyReplaceFrom: start to: stop
>   with: ((runs copyFrom: start to: stop)
> + replace:
> - mapValues:
>   [:attributes | Text addAttribute: att toArray: attributes])
>   !
>
> Item was changed:
>   ----- Method: Text>>removeAttribute:from:to: (in category 'emphasis')
> -----
>   removeAttribute: att from: start to: stop
>   "Remove the attribute over the interval start to stop."
>   runs :=  runs copyReplaceFrom: start to: stop
>   with: ((runs copyFrom: start to: stop)
> + replace:
> - mapValues:
>   [:attributes | attributes copyWithout: att])
>   !