Nicolas Cellier uploaded a new version of Collections to project The Trunk:
http://source.squeak.org/trunk/Collections-nice.928.mcz
==================== Summary ====================
Name: Collections-nice.928
Author: nice
Time: 3 March 2021, 3:29:05.70662 pm
UUID: ef9658c8-ef7e-a943-8ffc-de7546b29f2f
Ancestors: Collections-nice.927, Collections-nice.634
Merge Collections-nice.634 (Implement replace: in Dictionary)
=============== Diff against Collections-nice.927 ===============
Item was added:
+ ----- Method: Dictionary>>replace: (in category 'enumerating') -----
+ replace: aBlock
+ "Destructively replace the values in this Dictionary by applying aBlock, keeping the same keys.
+ Implementation note: subclasses not storing the key-value pairs as a list of Associations shall refine this method."
+ tally = 0 ifTrue: [ ^self].
+ 1 to: array size do: [ :index |
+ (array at: index) ifNotNil: [ :element |
+ element value: (aBlock value: element value) ] ]!
Item was added:
+ ----- Method: OrderedDictionary>>replace: (in category 'enumerating') -----
+ replace: aBlock
+ "Like super, but iterate in order."
+
+ order from: 1 to: tally do: [:each | each value: (aBlock value: each value)]!
Item was added:
+ ----- Method: WeakKeyDictionary>>replace: (in category 'enumerating') -----
+ replace: aBlock
+ "Like super except that aBlock shouldn't be invoked for any reclaimed (nil) key."
+
+ tally = 0 ifTrue: [ ^self].
+ 1 to: array size do: [ :index |
+ (array at: index) ifNotNil: [ :association |
+ association key ifNotNil: [ :key | "Don't let the key go away."
+ association value: (aBlock value: association value) ] ] ]!
Nicolas Cellier uploaded a new version of Collections to project The Trunk:
http://source.squeak.org/trunk/Collections-nice.634.mcz
==================== Summary ====================
Name: Collections-nice.634
Author: nice
Time: 6 May 2015, 11:08:55.927 pm
UUID: 4d2e458d-25c3-4b58-8df0-858fd2a6e84e
Ancestors: Collections-ul.633
Implement replace: in Dictionary
=============== Diff against Collections-ul.633 ===============
Item was added:
+ ----- Method: Dictionary>>replace: (in category 'enumerating') -----
+ replace: aBlock
+ "Destructively replace the values in this Dictionary by applying aBlock, keeping the same keys.
+ Implementation note: subclasses not storing the key-value pairs as a list of Associations shall refine this method."
+ tally = 0 ifTrue: [ ^self].
+ 1 to: array size do: [ :index |
+ (array at: index) ifNotNil: [ :element |
+ element value: (aBlock value: element value) ] ]!
Item was added:
+ ----- Method: OrderedDictionary>>replace: (in category 'enumerating') -----
+ replace: aBlock
+ "Like super, but iterate in order."
+
+ order from: 1 to: tally do: [:each | each value: (aBlock value: each value)]!
Item was added:
+ ----- Method: WeakKeyDictionary>>replace: (in category 'enumerating') -----
+ replace: aBlock
+ "Like super except that aBlock shouldn't be invoked for any reclaimed (nil) key."
+
+ tally = 0 ifTrue: [ ^self].
+ 1 to: array size do: [ :index |
+ (array at: index) ifNotNil: [ :association |
+ association key ifNotNil: [ :key | "Don't let the key go away."
+ association value: (aBlock value: association value) ] ] ]!
Nicolas Cellier uploaded a new version of Collections to project The Trunk:
http://source.squeak.org/trunk/Collections-nice.927.mcz
==================== Summary ====================
Name: Collections-nice.927
Author: nice
Time: 3 March 2021, 3:10:15.18162 pm
UUID: a5b8a84d-ad99-754f-8960-88c04b17d8d3
Ancestors: Collections-nice.926
Remaster Collections-nice.869 & 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.
- 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.
- prefer replace: to mapValues:, as it is a more generic Collection idiom
Notice that this DOES NOT import one major change of Collections-nice.869:
the enumerating methods like #collect: will continue to iterate on each element, rather than only once per run, so as to preserve side effects.
Thus Collections-nice.869 remains in inbox until larger acceptation occurs.
=============== Diff against Collections-nice.926 ===============
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>>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>>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>>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>>keysAndValuesDo: (in category 'enumerating') -----
+ keysAndValuesDo: aBlock
+ "This is refined for speed"
+
+ | index |
+ index := 0.
+ 1 to: runs size do: [:i |
+ | r v |
+ v := values at: i.
+ r := runs at: i.
+ [( r := r - 1) >= 0]
+ whileTrue: [aBlock value: (index := index + 1) value: v]].!
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 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 := runs copyEmpty.
+ values := values copyEmpty!
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>>withIndexDo: (in category 'enumerating') -----
+ withIndexDo: aBlock
+ "This is refined for speed"
+
+ | index |
+ index := 0.
+ 1 to: runs size do: [:i |
+ | r v |
+ v := values at: i.
+ r := runs at: i.
+ [( r := r - 1) >= 0]
+ whileTrue: [aBlock value: v value: (index := index + 1)]].!
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])
!
Nicolas Cellier uploaded a new version of Collections to project The Trunk:
http://source.squeak.org/trunk/Collections-nice.926.mcz
==================== Summary ====================
Name: Collections-nice.926
Author: nice
Time: 3 March 2021, 10:46:01.17162 am
UUID: bb5d2ec0-d044-c54f-9e8a-5442626c7573
Ancestors: Collections-nice.925
Fix LimitedPrecisionInterval>>collect: it should avoid accumulating increments which also accumulates rounding errors and make collect: behavior diverge from do:.
Rather than modifying Interval>>collect:, implement the specific inexact arithmetic handling in specific subclass.
Do the same with do: and reverseDo:. This enables restoring the legacy Interval enumerations which perform only one operation per loop instead of two.
Do not check rangeIncludes: in indexOf:startingAt:. This is useless foe exact Interval, and now redundant for LimitedPrecisionInterval thanks to more carefull implementation of #size.
=============== Diff against Collections-nice.925 ===============
Item was changed:
----- Method: Interval>>do: (in category 'enumerating') -----
+ do: aBlock
+
+ | aValue |
+ aValue := start.
+ step < 0
+ ifTrue: [[stop <= aValue]
+ whileTrue:
+ [aBlock value: aValue.
+ aValue := aValue + step]]
+ ifFalse: [[stop >= aValue]
+ whileTrue:
+ [aBlock value: aValue.
+ aValue := aValue + step]]!
- do: aBlock
- "Evaluate aBlock for each value of the interval.
- Implementation note: instead of repeatedly incrementing the value
- aValue := aValue + step.
- until stop is reached,
- We prefer to recompute value from start
- aValue := start + (index * step).
- This is better for floating points accuracy, while not degrading Integer and Fraction speed too much.
- Moreover, this is consistent with methods #at: and #size"
-
- | aValue index size |
- index := 0.
- size := self size.
- [index < size]
- whileTrue: [aValue := start + (index * step).
- index := index + 1.
- aBlock value: aValue]!
Item was changed:
----- Method: Interval>>indexOf:startingAt: (in category 'accessing') -----
indexOf: anElement startingAt: startIndex
"startIndex is an positive integer, the collection index where the search is started."
| index |
- (self rangeIncludes: anElement) ifFalse: [ ^0 ].
index := (anElement - start / step) rounded + 1.
(index between: startIndex and: self size) ifFalse: [ ^0 ].
(self at: index) = anElement ifFalse: [ ^0 ].
^index!
Item was changed:
----- Method: Interval>>reverseDo: (in category 'enumerating') -----
reverseDo: aBlock
+ "Evaluate aBlock for each element of my interval, in reverse order."
+ | aValue |
+ aValue := self last.
+ step < 0
+ ifTrue: [[start >= aValue]
+ whileTrue: [aBlock value: aValue.
+ aValue := aValue - step]]
+ ifFalse: [[start <= aValue]
+ whileTrue: [aBlock value: aValue.
+ aValue := aValue - step]]!
- "Evaluate aBlock for each element of my interval, in reverse order.
- Implementation notes: see do: for an explanation on loop detail"
-
- | aValue index |
- index := self size.
- [index > 0]
- whileTrue: [
- index := index - 1.
- aValue := start + (index * step).
- aBlock value: aValue]!
Item was added:
+ ----- Method: LimitedPrecisionInterval>>collect: (in category 'enumerating') -----
+ collect: aBlock
+ "Evaluate aBlock with each of the receiver's elements as the argument.
+ Collect the resulting values into a collection like the receiver. Answer
+ the new collection.
+ Implementation notes: see do: for an explanation on loop detail"
+ | result |
+ result := self species new: self size.
+ 1 to: result size do:
+ [:i |
+ "(self at: i) is inlined here to avoid repeated bound checking"
+ result at: i put: i - 1 * step + start].
+ ^ result!
Item was added:
+ ----- Method: LimitedPrecisionInterval>>do: (in category 'enumerating') -----
+ do: aBlock
+ "Evaluate aBlock for each value of the interval.
+ Implementation note: instead of repeatedly incrementing the value
+ aValue := aValue + step.
+ until stop is reached,
+ We prefer to recompute value from start
+ aValue := start + (index * step).
+ This is better for floating points accuracy, while not degrading Integer and Fraction speed too much.
+ Moreover, this is consistent with methods #at: and #size"
+
+ | aValue index size |
+ index := 0.
+ size := self size.
+ [index < size]
+ whileTrue: [aValue := start + (index * step).
+ index := index + 1.
+ aBlock value: aValue]!
Item was added:
+ ----- Method: LimitedPrecisionInterval>>reverseDo: (in category 'enumerating') -----
+ reverseDo: aBlock
+ "Evaluate aBlock for each element of my interval, in reverse order.
+ Implementation notes: see do: for an explanation on loop detail"
+
+ | aValue index |
+ index := self size.
+ [index > 0]
+ whileTrue: [
+ index := index - 1.
+ aValue := start + (index * step).
+ aBlock value: aValue]!
Nicolas Cellier uploaded a new version of CollectionsTests to project The Trunk:
http://source.squeak.org/trunk/CollectionsTests-nice.352.mcz
==================== Summary ====================
Name: CollectionsTests-nice.352
Author: nice
Time: 3 March 2021, 10:34:45.83962 am
UUID: 8666dc7b-f181-6340-97d4-be3d5a50166d
Ancestors: CollectionsTests-nice.351
Separate the Interval of Float tests into LimitedPrecisionIntervalTest.
Document a few more invalid expectations related to inexact nature of arithmetic on LimitedPrecisionInterval.
=============== Diff against CollectionsTests-nice.351 ===============
Item was removed:
- ----- Method: IntervalTest>>expectedFailures (in category 'failures') -----
- expectedFailures
-
- ^ #(testIntervalOfFloatEqual)!
Item was changed:
----- Method: IntervalTest>>testAsIntervalWithFractionalProgression (in category 'tests') -----
testAsIntervalWithFractionalProgression
self assert: (1 to: 2 by: 1/2) equals: ({1. 3/2. 2} as: Interval).
+ self assert: (1 to: 2 by: 0.2s) equals: ({1. 1.2s. 1.4s. 1.6s. 1.8s. 2} as: Interval).!
- self assert: (1 to: 2 by: 0.2s) equals: ({1. 1.2s. 1.4s. 1.6s. 1.8s. 2} as: Interval).
-
- self should: [#(0.1 0.2 0.3 0.4) as: Interval]
- raise: Error
- description: 'There is no guaranty that Interval of Float can be constructed from individual Float'.
- "Even though, by chance there might be a Float Interval with same elements"
- #(0.1 0.2 0.3 0.4) hasEqualElements: (0.1 to: 0.4 by: 0.1 predecessor)!
Item was added:
+ ----- Method: IntervalTest>>testCollect (in category 'tests') -----
+ testCollect
+ | s i |
+ i := (10 to: 20).
+ s := i collect: [:e | e].
+ self assert: (s hasEqualElements: i)!
Item was removed:
- ----- Method: IntervalTest>>testElementOutOfBound (in category 'tests') -----
- testElementOutOfBound
- self deny: ((1/5 to: 1.2 by: 1) anySatisfy: [:e | e > 1.2]).!
Item was removed:
- ----- Method: IntervalTest>>testIncludesBound (in category 'tests') -----
- testIncludesBound
- "This interval is crafted for including 1.2
- but a careless definition of size might exclude this bound"
- self assert: (((0.3 to: 1.2 by: 0.1) includes: 1.2) ==> [(0.3 to: 1.2 by: 0.1) anySatisfy: [:each | each = 1.2]]).!
Item was removed:
- ----- Method: IntervalTest>>testInclusion (in category 'tests') -----
- testInclusion
- "Non regression test for another bug of fuzzy inclusion"
-
- self deny: ((1.0 to: 3.0 by: 1.0 successor) includes: 3.0) description: 'The last element of this Interval is closed to 2'!
Item was removed:
- ----- Method: IntervalTest>>testInclusionBug6455 (in category 'tests') -----
- testInclusionBug6455
- "This test is about mantis bug http://bugs.squeak.org/view.php?id=6455.
- Well it's not a bug, and not a good feature.
- See testSurprisingFuzzyInclusion for why this feature is not a good idea"
-
- self deny: ((0.2 to: 0.6 by: 0.1) includes: 0.3) description: 'Strict Float equality expecation is too high'.
- self assert: ((0.2 to: 0.6 by: 0.1) includes: 0.3 successor) description: 'it includes a slightly different number'!
Item was removed:
- ----- Method: IntervalTest>>testIndexOfBug6455 (in category 'tests') -----
- testIndexOfBug6455
- "This test is about mantis bug http://bugs.squeak.org/view.php?id=6455
- Well it's not a bug, and not a good feature.
- See testSurprisingFuzzyInclusion for why this feature is not a good idea"
-
- self deny: ((0.2 to: 0.6 by: 0.1) indexOf: 0.3) = 2 description: 'Strict Float equality expecation is too high'.
- self assert: ((0.2 to: 0.6 by: 0.1) indexOf: 0.3 successor) = 2 description: 'it includes a slightly different number'!
Item was removed:
- ----- Method: IntervalTest>>testInfiniteLoopBug6456 (in category 'tests') -----
- testInfiniteLoopBug6456
- "This is a non regression test against mantis bug #6456.
- Some Float interval size was not consistent with do: loop.
- Some Float Interval used to do: infinite loops"
-
- | x interval counter size |
- x := (1.0 timesTwoPower: Float precision). "Note: x+1 = x due to inexact arithmetic"
- interval := x to: x+4.
- size := interval size.
- counter := 0.
- interval do: [:each | self assert: (counter := counter + 1) <= size].!
Item was removed:
- ----- Method: IntervalTest>>testIntervalOfFloatEqual (in category 'tests') -----
- testIntervalOfFloatEqual
- "Interval with Float are weirdos"
-
- | interval1 interval2 interval3 interval4 |
- interval1 := (0 to: 1 by: 1/10).
- interval2 := (0.0 to: 1 by: 1/10).
- self deny: (interval1 = interval2) ==> (interval1 hasEqualElements: interval2)
- description: 'Interval of Float may have different elements from another Interval, even if they pretend to be equal.'.
-
- interval3 := (0.3 to: 0.6 by: 1/10).
- interval4 := (0.3 to: 0.6 by: 0.1).
- self deny: (interval3 hasEqualElements: interval4) ==> (interval3 = interval4)
- description: 'Interval of Float may pretend they differ from another Interval even if they have same elements.'.!
Item was removed:
- ----- Method: IntervalTest>>testIntervalOfFloatLast (in category 'tests') -----
- testIntervalOfFloatLast
- "Some definition of last were problematic for Interval of Float"
-
- | increment upperBound interval |
- self assert: (0.2 to: 0.9 by: 0.1) last = (0.2 to: 0.9 by: 0.1) asArray last
- description: 'the last element cannot reasonably change when converting asArray'.
-
- upperBound := 1.7.
- increment := 0.1.
- self deny: (0 to: upperBound by: increment) last > upperBound
- description: 'the last element cannot reasonably exceed upper bound'.
-
- interval := -0.9999999999999994 to: 1 by: 2.
- self assert: interval last < interval first
- ==> (interval isEmpty or: [interval increment < 0])
- description: 'the last element cannot reasonably deceed(*) lower bound (* be inferior to)'!
Item was removed:
- ----- Method: IntervalTest>>testIntervalOfFloatReversed (in category 'tests') -----
- testIntervalOfFloatReversed
- self assert: (-16.3 to: 20.1 by: 1.3) reversed size
- equals: (-16.3 to: 20.1 by: 1.3) size
- description: 'reversed should preserve the size of a collection'.
- self assert: (0.1 to: 0.9 by: 0.1) reversed asArray
- equals: (0.1 to: 0.9 by: 0.1) asArray reversed
- description: 'reversed should preserve the elements of a collection'.!
Item was changed:
----- Method: IntervalTest>>testPermutationsDo (in category 'tests') -----
testPermutationsDo
| i oc |
+ i := (4 to: 13 by: 3).
- i := (1.234 to: 4.234).
oc := OrderedCollection new.
+ i permutationsDo: [:e | oc add: e copy].
+ self assert: oc size = i size factorial.
+ self assert: oc asSet size = oc size.
+ self assert: (oc allSatisfy: [:e | e sorted hasEqualElements: i]).
- i permutationsDo: [:e | oc add: e].
- self assert: (oc size = i size factorial).
^ oc!
Item was changed:
----- Method: IntervalTest>>testRangeIncludes (in category 'tests') -----
testRangeIncludes
+ self assert: ((1 to: 10) rangeIncludes: 4) description: '4 is within this range'.
+ self assert: ((1 to: 10 by: 2) rangeIncludes: 4) description: 'even if the interval does not include 4'.
+ self deny: ((1 to: 10 by: -1) rangeIncludes: 4) description: 'this range is empty'.
+ self assert: ((10 to: 1 by: -4) rangeIncludes: 4) description: 'the range can be retrograde'.
+ self assert: ((1 to: 10) rangeIncludes: 10) description: 'the range includes the bounds'.
+ self assert: ((1 to: 10 by: 2) rangeIncludes: 10) description: 'even when bound lies past the last element'.
+ #(0 11) do: [:outOfBound |
+ #(-2 -1 2 2) do: [:step |
+ self deny: ((1 to: 10 by: step) includes: outOfBound)]]!
- self
- assert: ((1 to: 10)
- rangeIncludes: 3).
- self
- assert: ((1 to: 10 by: 2)
- rangeIncludes: 3).
- self
- deny: ((1 to: 10)
- rangeIncludes: 0).
- self
- deny: ((1 to: 10)
- rangeIncludes: 11).
- self
- deny: ((1 to: 10 by: 2)
- rangeIncludes: 0).
- self
- deny: ((1 to: 10 by: 2)
- rangeIncludes: 11)!
Item was removed:
- ----- Method: IntervalTest>>testSurprisingFuzzyInclusionBehavior (in category 'tests') -----
- testSurprisingFuzzyInclusionBehavior
- "If ever Interval implement fuzzy inclusion, then we can expect weird logic..."
- self assert: ((0.1 to: 0.9 by: 0.1) includes: 0.3)
- ==> (((0.1 to: 0.9 by: 0.1) occurrencesOf: 0.3) > 0)
- description: 'A Collection that includes something has at least one occurrence of something'.
- self assert: ((0.1 to: 0.9 by: 0.1) lastIndexOf: 0.3)
- >= ((0.1 to: 0.9 by: 0.1) indexOf: 0.3)
- description: 'The last index of an object in a SequenceableCollection should be greater than or equal to the first index'.
- self assert: ((0.1 to: 0.9 by: 0.1) includes: 0.3)
- ==> (((0.1 to: 0.9 by: 0.1) copyWithout: 0.3) size < (0.1 to: 0.9 by: 0.1) size)
- description: 'A Collection should be able to shrink by stripping own elements'.!
Item was added:
+ ClassTestCase subclass: #LimitedPrecisionIntervalTest
+ instanceVariableNames: ''
+ classVariableNames: ''
+ poolDictionaries: ''
+ category: 'CollectionsTests-Sequenceable'!
Item was added:
+ ----- Method: LimitedPrecisionIntervalTest>>assert:is:withinUlp: (in category 'asserting - extensions') -----
+ assert: aFloat is: anotherFloat withinUlp: anInteger
+ ^self assert: (aFloat - anotherFloat) abs <= (aFloat ulp * anInteger)!
Item was added:
+ ----- Method: LimitedPrecisionIntervalTest>>expectedFailures (in category 'failures') -----
+ expectedFailures
+
+ ^ #(testIntervalOfFloatEqual)!
Item was added:
+ ----- Method: LimitedPrecisionIntervalTest>>testAdd (in category 'tests') -----
+ testAdd
+ | floatInterval |
+ floatInterval := (0.3 to: 0.6 by: 0.1).
+ self deny: floatInterval size = (floatInterval + 1) size description: 'there is no guaranty that size is preserved by arithmetic operation'!
Item was added:
+ ----- Method: LimitedPrecisionIntervalTest>>testAsIntervalWithFractionalProgression (in category 'tests') -----
+ testAsIntervalWithFractionalProgression
+ self should: [#(0.1 0.2 0.3 0.4) as: Interval]
+ raise: Error
+ description: 'There is no guaranty that Interval of Float can be constructed from individual Float'.
+ "Even though, by chance there might be a Float Interval with same elements"
+ #(0.1 0.2 0.3 0.4) hasEqualElements: (0.1 to: 0.4 by: 0.1 predecessor)!
Item was added:
+ ----- Method: LimitedPrecisionIntervalTest>>testCollect (in category 'tests') -----
+ testCollect
+ | s i |
+ i := (0.1 to: 1.0 by: 0.1).
+ s := i collect: [:e | e].
+ self assert: (s hasEqualElements: i)!
Item was added:
+ ----- Method: LimitedPrecisionIntervalTest>>testDo (in category 'tests') -----
+ testDo
+ | s i |
+ s := OrderedCollection new.
+ i := (0.1 to: 1.0 by: 0.1).
+ i do: [ :each | s addLast: each].
+ self assert: (s hasEqualElements: i)!
Item was added:
+ ----- Method: LimitedPrecisionIntervalTest>>testElementOutOfBound (in category 'tests') -----
+ testElementOutOfBound
+ "Note: this is a test for correct implementation of size.
+ With super definition of size, an element past the bound could be included"
+
+ self deny: ((1/5 to: 1.2 by: 1) anySatisfy: [:e | e > 1.2]).!
Item was added:
+ ----- Method: LimitedPrecisionIntervalTest>>testIncludesBound (in category 'tests') -----
+ testIncludesBound
+ "This interval is crafted for including 1.2
+ but a careless definition of size might exclude this bound"
+ self assert: (((0.3 to: 1.2 by: 0.1) includes: 1.2) ==> [(0.3 to: 1.2 by: 0.1) anySatisfy: [:each | each = 1.2]]).!
Item was added:
+ ----- Method: LimitedPrecisionIntervalTest>>testInclusion (in category 'tests') -----
+ testInclusion
+ "Non regression test for another bug of fuzzy inclusion"
+
+ self deny: ((1.0 to: 3.0 by: 1.0 successor) includes: 3.0) description: 'The last element of this Interval is closed to 2'!
Item was added:
+ ----- Method: LimitedPrecisionIntervalTest>>testInclusionBug6455 (in category 'tests') -----
+ testInclusionBug6455
+ "This test is about mantis bug http://bugs.squeak.org/view.php?id=6455.
+ Well it's not a bug, and not a good feature.
+ See testSurprisingFuzzyInclusion for why this feature is not a good idea"
+
+ self deny: ((0.2 to: 0.6 by: 0.1) includes: 0.3) description: 'Strict Float equality expecation is too high'.
+ self assert: ((0.2 to: 0.6 by: 0.1) includes: 0.3 successor) description: 'it includes a slightly different number'!
Item was added:
+ ----- Method: LimitedPrecisionIntervalTest>>testIndexOfBug6455 (in category 'tests') -----
+ testIndexOfBug6455
+ "This test is about mantis bug http://bugs.squeak.org/view.php?id=6455
+ Well it's not a bug, and not a good feature.
+ See testSurprisingFuzzyInclusion for why this feature is not a good idea"
+
+ self deny: ((0.2 to: 0.6 by: 0.1) indexOf: 0.3) = 2 description: 'Strict Float equality expecation is too high'.
+ self assert: ((0.2 to: 0.6 by: 0.1) indexOf: 0.3 successor) = 2 description: 'it includes a slightly different number'!
Item was added:
+ ----- Method: LimitedPrecisionIntervalTest>>testInfiniteLoopBug6456 (in category 'tests') -----
+ testInfiniteLoopBug6456
+ "This is a non regression test against mantis bug #6456.
+ Some Float interval size was not consistent with do: loop.
+ Some Float Interval used to do: infinite loops"
+
+ | x interval counter size |
+ x := (1.0 timesTwoPower: Float precision). "Note: x+1 = x due to inexact arithmetic"
+ interval := x to: x+4.
+ size := interval size.
+ counter := 0.
+ interval do: [:each | self assert: (counter := counter + 1) <= size].!
Item was added:
+ ----- Method: LimitedPrecisionIntervalTest>>testIntervalOfFloatEqual (in category 'tests') -----
+ testIntervalOfFloatEqual
+ "Interval with Float are weirdos"
+
+ | interval1 interval2 interval3 interval4 |
+ interval1 := (0 to: 1 by: 1/10).
+ interval2 := (0.0 to: 1 by: 1/10).
+ self deny: (interval1 = interval2) ==> (interval1 hasEqualElements: interval2)
+ description: 'Interval of Float may have different elements from another Interval, even if they pretend to be equal.'.
+
+ interval3 := (0.3 to: 0.6 by: 1/10).
+ interval4 := (0.3 to: 0.6 by: 0.1).
+ self deny: (interval3 hasEqualElements: interval4) ==> (interval3 = interval4)
+ description: 'Interval of Float may pretend they differ from another Interval even if they have same elements.'.!
Item was added:
+ ----- Method: LimitedPrecisionIntervalTest>>testLast (in category 'tests') -----
+ testLast
+ "Some definition of last were problematic for Interval of Float"
+
+ | increment upperBound interval |
+ self assert: (0.2 to: 0.9 by: 0.1) last = (0.2 to: 0.9 by: 0.1) asArray last
+ description: 'the last element cannot reasonably change when converting asArray'.
+
+ upperBound := 1.7.
+ increment := 0.1.
+ self deny: (0 to: upperBound by: increment) last > upperBound
+ description: 'the last element cannot reasonably exceed upper bound'.
+
+ interval := -0.9999999999999994 to: 1 by: 2.
+ self assert: interval last < interval first
+ ==> (interval isEmpty or: [interval increment < 0])
+ description: 'the last element cannot reasonably deceed(*) lower bound (* be inferior to)'!
Item was added:
+ ----- Method: LimitedPrecisionIntervalTest>>testReversed (in category 'tests') -----
+ testReversed
+ self assert: (-16.3 to: 20.1 by: 1.3) reversed size
+ equals: (-16.3 to: 20.1 by: 1.3) size
+ description: 'reversed should preserve the size of a collection'.
+ self assert: (0.1 to: 0.9 by: 0.1) reversed asArray
+ equals: (0.1 to: 0.9 by: 0.1) asArray reversed
+ description: 'reversed should preserve the elements of a collection'.!
Item was added:
+ ----- Method: LimitedPrecisionIntervalTest>>testSum (in category 'tests') -----
+ testSum
+ | floatInterval |
+ floatInterval := 0.1 to: 1.0 by: 0.1.
+ self deny: floatInterval sum = floatInterval asArray sum description: 'do not expect strict Float equality after arithmetic operations'.
+ self assert: floatInterval sum is: floatInterval asArray sum withinUlp: floatInterval size / 2!
Item was added:
+ ----- Method: LimitedPrecisionIntervalTest>>testSurprisingFuzzyInclusionBehavior (in category 'tests') -----
+ testSurprisingFuzzyInclusionBehavior
+ "If ever Interval implement fuzzy inclusion, then we can expect weird logic..."
+ self assert: ((0.1 to: 0.9 by: 0.1) includes: 0.3)
+ ==> (((0.1 to: 0.9 by: 0.1) occurrencesOf: 0.3) > 0)
+ description: 'A Collection that includes something has at least one occurrence of something'.
+ self assert: ((0.1 to: 0.9 by: 0.1) lastIndexOf: 0.3)
+ >= ((0.1 to: 0.9 by: 0.1) indexOf: 0.3)
+ description: 'The last index of an object in a SequenceableCollection should be greater than or equal to the first index'.
+ self assert: ((0.1 to: 0.9 by: 0.1) includes: 0.3)
+ ==> (((0.1 to: 0.9 by: 0.1) copyWithout: 0.3) size < (0.1 to: 0.9 by: 0.1) size)
+ description: 'A Collection should be able to shrink by stripping own elements'.!