--- a/Collection.st Tue Feb 04 21:09:59 2014 +0100
+++ b/Collection.st Wed Apr 01 10:20:10 2015 +0100
@@ -1,3 +1,5 @@
+"{ Encoding: utf8 }"
+
"
COPYRIGHT (c) 1989 by Claus Gittinger
All Rights Reserved
@@ -11,10 +13,12 @@
"
"{ Package: 'stx:libbasic' }"
+"{ NameSpace: Smalltalk }"
+
Object subclass:#Collection
instanceVariableNames:''
classVariableNames:'InvalidKeySignal EmptyCollectionSignal ValueNotFoundSignal
- NotEnoughElementsSignal RecursiveCollectionStoreStringSignal'
+ NotEnoughElementsSignal'
poolDictionaries:''
category:'Collections-Abstract'
!
@@ -39,9 +43,9 @@
"
Abstract superclass for all collections.
This abstract class provides functionality common to all collections,
- without knowing how the concrete class implements things. Thus, all
- methods found here depend on some basic mechanisms to be defined in the
- concrete class.
+ without knowing how the concrete class implements things.
+ Thus, all methods found here depend on some basic mechanisms
+ to be defined in the concrete class.
These basic methods are usually defined as #subclassResponsibility here.
Some methods are also redefined for better performance.
@@ -49,15 +53,21 @@
do: - enumerate elements
they should implement one of the following set of access messages:
- keyed collections:
+ For keyed collections:
at:ifAbsent: - fetching an element
at: - fetching an element
at:put: - storing an element
- unkeyed collections:
+ For unkeyed collections:
add: - add an element
remove:ifAbsent: - remove an element
+ Given that the above is implemented in a concrete subclass,
+ Collection provides protocol for enumeration, searching and others.
+ However, for performance reasons, many of them are also redefined in
+ concrete subclasses, as some can be implemented much faster if implementation
+ details are known (for example, searching can be done faster if it is known that
+ elements are sorted or accessable by a key).
[author:]
Claus Gittinger
@@ -144,6 +154,13 @@
"
!
+newWithSize:n
+ "return a new collection which really provides space for n elements.
+ Kludges around the stupid definition of OrderedCollection>>new:"
+
+ ^ self new:n
+!
+
with:anObject
"return a new Collection with one element:anObject"
@@ -244,10 +261,11 @@
!
withSize:n
- "return a new collection which really provides space for n elements.
+ "obsolete: please use newWithSize:, for its better name
+ Return a new collection which really provides space for n elements.
Kludges around the stupid definition of OrderedCollection>>new:"
- ^ self new:n
+ ^ self newWithSize:n
! !
!Collection class methodsFor:'Compatibility-Squeak'!
@@ -256,7 +274,7 @@
"return a new collection which really provides space for n elements.
Kludges around the stupid definition of OrderedCollection>>new:"
- ^ self withSize:n
+ ^ self newWithSize:n
! !
@@ -301,13 +319,6 @@
"Created: / 09-01-2011 / 10:37:15 / cg"
! !
-!Collection class methodsFor:'misc ui support'!
-
-iconInBrowserSymbol
- <resource: #programImage>
-
- ^ #containerClassBrowserIcon
-! !
!Collection class methodsFor:'queries'!
@@ -417,7 +428,7 @@
gather:aBlock
"return an Array,
- containing all elements as returned from applying aBlock to each element if the receiver,
+ containing all elements as returned from applying aBlock to each element of the receiver,
where the block returns a collection of to-be-added elements.
This could also be called: collectAllAsArray:"
@@ -430,7 +441,7 @@
gather:aBlock as:aClass
"return an instance of the collection-class aClass,
- containing all elements as returned from applying aBlock to each element if the receiver.
+ containing all elements as returned from applying aBlock to each element of the receiver.
where the block returns a collection of to-be-added elements.
This could also be called: collectAll:as:"
@@ -466,6 +477,18 @@
"
!
+ifEmpty:alternativeValue
+ "return the receiver if not empty, alternativeValue otherwise"
+
+ ^ self size ~~ 0 ifTrue:[self] ifFalse:[alternativeValue value]
+
+ "
+ 'foo' ifEmpty: 'bar'
+ '' ifEmpty: 'bar'
+ '' ifEmpty: [ Time now printString ]
+ "
+!
+
ifEmpty:ifEmptyValue ifNotEmpty:ifNotEmptyValue
|action|
@@ -503,32 +526,6 @@
^ self intersect:aCollection
"Created: / 22-10-2008 / 21:29:27 / cg"
-!
-
-withIndexCollect:aTwoArgBlock
- "same as keysAndValuesCollect:, but with argument order reversed"
-
- |newCollection|
-
- newCollection := OrderedCollection new.
- self keysAndValuesDo:[:key :value |
- newCollection add:(aTwoArgBlock value:value value:key)
- ].
- ^ newCollection
-
- "
- #(one two three) withIndexCollect:[:sym :num | (num->sym)]
- #(10 20 30) withIndexCollect:[:n :i | n*i ]
- "
-!
-
-withIndexDo:aTwoArgBlock
- "evaluate the argument, aBlock for every element in the collection,
- passing both element and index as arguments."
-
- ^ self keysAndValuesDo:[:key :index |
- aTwoArgBlock value:index value:key
- ].
! !
@@ -536,10 +533,19 @@
anElement
"return any element from the collection,
- report an error if there is none"
+ report an error if there is none.
+ Use this to fetch the some element from a collection which is non-indexed or which
+ has a non-numeric index. I.e. if someone gets an arbitrary collection which might be either indexable
+ or not, anElement is a save way to access some element without a need to check for a proper key."
self do: [:each | ^ each].
self emptyCollectionError.
+
+ "
+ #() anElement -> Error
+ #(1 2 3) anElement -> 1
+ #(1 2 3) asSet anElement -> one of them (undefined, which one)
+ "
!
at:aKey ifNilOrAbsentPut:valueBlock
@@ -629,9 +635,11 @@
first:n
"return the n first elements of the collection.
- Raises an error if there are not enough elements in the receiver.
+ No longer raises an error if there are not enough elements;
+ instead, returns what is there.
+
For unordered collections, this simply returns the first
- n elements when enumerating them
+ n elements when enumerating them.
(Warning: the contents of the returned collection is not deterministic in this case).
This should be redefined in subclasses."
@@ -648,13 +656,18 @@
^ coll
].
].
-
- "error if collection has not enough elements"
- ^ self notEnoughElementsError
+ "/ OLD:
+ "/ "error if collection has not enough elements"
+ "/ ^ self notEnoughElementsError
+ "/ NEW:
+ "/ return what we have - no error if not enough elements
+ ^ coll.
"
#(1 2 3 4 5) first:3
#(1 2 3 4 5) asSet first:3
+ #(1 2 3) first:5
+ #(1 2 3) asSet first:5
"
"Modified (format): / 29-09-2011 / 10:16:49 / cg"
@@ -730,7 +743,8 @@
last:n
"return the n last elements of the collection.
- Raises an error if there are not enough elements in the receiver.
+ No longer raises an error if there are not enough elements;
+ instead, returns what is there.
For unordered collections, this simply returns the last
n elements when enumerating them
(Warning: the contents of the returned collection is not deterministic in this case).
@@ -751,16 +765,19 @@
coll add:e.
].
- remain ~~ 0 ifTrue:[
- "error if collection has not enough elements"
- ^ self notEnoughElementsError
- ].
+ "/ OLD:
+ "/ remain ~~ 0 ifTrue:[
+ "/ "error if collection has not enough elements"
+ "/ ^ self notEnoughElementsError
+ "/ ].
^ coll
"
#(1 2 3 4 5) last:3
#(1 2 3 4 5 6 7 8 9 0) asSet last:3
'hello world' last:5
+ 'hello' last:10
+ 'hello' asSet last:10
"
"Modified (format): / 29-09-2011 / 10:16:22 / cg"
@@ -778,21 +795,11 @@
"Created: 6.2.1996 / 15:27:49 / cg"
!
-median
- "Return the middle element, or as close as we can get."
-
- ^ self asSortedCollection median
-
- "
- #(10 35 20 45 30 5) median
- "
-!
-
nth:n
"return the nth element of the collection.
For unordered collections, this simply returns the nth
element when enumerating them.
- This should be redefined in subclasses."
+ This should be redefined in subclasses which can accecss fast by numeric index (aka Array-like things)."
|count|
@@ -1017,6 +1024,13 @@
"Modified: 12.4.1996 / 13:31:12 / cg"
!
+clearContents
+ "remove all elements from the receiver. Returns the receiver.
+ Subclasses may redefine this to keep the container."
+
+ self removeAll.
+!
+
contents:aCollection
"set my contents from aCollection
- this may be redefined in a concrete subclass for more performance"
@@ -1535,14 +1549,29 @@
^ anArray
!
+asArrayOfType:arrayClass
+ "return a new instance of arrayClass with the collection's elements"
+
+ |anIntegerArray
+ index "{ Class: SmallInteger }" |
+
+ anIntegerArray := arrayClass new:(self size).
+ index := 1.
+ self do:[:each |
+ anIntegerArray at:index put:each.
+ index := index + 1
+ ].
+ ^ anIntegerArray
+!
+
asBag
- "return a new Bag with the receiver collections elements"
+ "return a new Bag with the receiver collection's elements"
^ self addAllTo:(Bag new)
!
asByteArray
- "return a new ByteArray with the collections elements
+ "return a new ByteArray with the collection's elements
(which must convert to 8bit integers in the range 0..255)."
^ self asIntegerArray:ByteArray
@@ -1561,7 +1590,8 @@
"return a Dictionary with the receiver collection's elements,
using the original keys of the receiver as dictionary key.
Notice: this is redefined in Dictionary, where it returns the receiver.
- Use asNewDictionary, if you intent to modify the returned collection."
+ Use asNewDictionary, if you intent to modify the returned collection.
+ See associationsAsDictionary if you already have a collection of associations"
|d|
@@ -1575,10 +1605,10 @@
!
asDoubleArray
- "return a new DoubleArray with the collections elements
+ "return a new DoubleArray with the collection's elements
(which must convert to 64bit floats)."
- ^ self asIntegerArray:DoubleArray
+ ^ self asArrayOfType:DoubleArray
!
asFlatOrderedCollection
@@ -1605,14 +1635,21 @@
!
asFloatArray
- "return a new FloatArray with the collections elements
+ "return a new FloatArray with the collection's elements
(which must convert to 32bit floats)."
- ^ self asIntegerArray:FloatArray
+ ^ self asArrayOfType:FloatArray
+!
+
+asHalfFloatArray
+ "return a new HalfFloatArray with the collection's elements
+ (which must convert to 16bit half-floats)."
+
+ ^ self asArrayOfType:HalfFloatArray
!
asIdentitySet
- "return a new IdentitySet with the receiver collections elements"
+ "return a new IdentitySet with the receiver collection's elements"
^ self addAllTo:(IdentitySet new:self size)
!
@@ -1639,8 +1676,19 @@
^ anIntegerArray
!
+asKeysAndValues
+ "return a Dictionary with the receiver's associations as key->value pairs
+ using each element's key as dictionary key and value as dictionary value."
+
+ ^ Dictionary withAssociations:self
+
+ "
+ { 10->'ten' . 20->'twenty' . 30->'thirty'} asKeysAndValues
+ "
+!
+
asList
- "return a new List with the receiver collections elements"
+ "return a new List with the receiver collection's elements"
^ self addAllTo:(List new:self size)
@@ -1648,12 +1696,18 @@
!
asLongIntegerArray
- "return a new LongIntegerArray with the collections elements
+ "return a new LongIntegerArray with the collection's elements
(which must convert to 64bit integers in the range 0..16rFFFFFFFFFFFFFFFF)."
^ self asIntegerArray:LongIntegerArray
!
+asMutableCollection
+ "return myself"
+
+ ^ self
+!
+
asNewArray
"return a new Array with the receiver collection's elements.
This method ensures that the returned collection is a new one, not
@@ -1726,7 +1780,7 @@
!
asRunArray
- "return a new RunArray with the collections elements"
+ "return a new RunArray with the collection's elements"
^ RunArray from:self.
@@ -1792,8 +1846,22 @@
"Created: / 07-10-2011 / 13:14:01 / cg"
!
+asSignedLongIntegerArray
+ "return a new LongIntegerArray with the collection's elements
+ (which must convert to 64bit integers in the range -16r8000000000000000..16r7FFFFFFFFFFFFFFF)."
+
+ ^ self asIntegerArray:SignedLongIntegerArray
+!
+
+asSignedWordArray
+ "return a new WordArray with the collection's elements
+ (which must convert to 16bit integers in the range -0x8000..16r7FFF)."
+
+ ^ self asIntegerArray:SignedWordArray
+!
+
asSortedCollection
- "return a new SortedCollection with the receiver collections elements"
+ "return a new SortedCollection with the receiver collection's elements"
|aSortedCollection|
@@ -1803,7 +1871,7 @@
!
asSortedCollection:sortBlock
- "return a new SortedCollection with the receiver collections elements,
+ "return a new SortedCollection with the receiver collection's elements,
using sortBlock for comparing"
|aSortedCollection|
@@ -1923,7 +1991,7 @@
!
asUnicodeString
- "return a String with the collections elements
+ "return a String with the collection's elements
(which must convert to characters)"
|aString
@@ -1943,19 +2011,10 @@
!
asWordArray
- "return a new WordArray with the collections elements
+ "return a new WordArray with the collection's elements
(which must convert to integers in the range 0..16rFFFF)."
- |aWordArray
- index "{ Class: SmallInteger }" |
-
- aWordArray := WordArray new:(self size).
- index := 1.
- self do:[:each |
- aWordArray at:index put:each asInteger.
- index := index + 1
- ].
- ^ aWordArray
+ ^ self asIntegerArray:WordArray
!
associationsAsDictionary
@@ -2267,6 +2326,29 @@
"
!
+collect:collectBlock thenDetect:detectBlock ifNone:exceptionalValue
+ "first apply collectBlock to each element, then pass the result to
+ detectBlock.
+ Return the first element from collectBlock for which detectBlock evaluates to true.
+ If none does, return the value of exceptionalValue, which is usually a block.
+ Returns the same as if two separate collect:+detect:ifNone: messages were sent,
+ but avoids the creation of intermediate collections, so this is nicer for
+ big collections."
+
+ self do:[:each |
+ |rslt|
+
+ rslt := collectBlock value:each.
+ (detectBlock value:rslt) ifTrue:[^ rslt].
+ ].
+ ^ exceptionalValue value
+
+ "
+ ( #(1 2 3 4) collect:[:e | e squared] ) detect:[:e| e odd] ifNone:0
+ #(1 2 3 4) collect:[:e | e squared] thenDetect:[:e| e odd] ifNone:0
+ "
+!
+
collect:collectBlock thenDo:aBlock
"combination of collect followed by do.
Avoids the creation of intermediate garbage"
@@ -2388,6 +2470,27 @@
"
!
+collectWithIndex:aTwoArgBlock
+ "for each element in the receiver and a running index,
+ evaluate the argument, aTwoArgBlock.
+ Return a new collection with the results"
+
+ |newCollection runIndex|
+
+ newCollection := self species new.
+ runIndex := 1.
+ self do:[:element |
+ newCollection add:(aTwoArgBlock value:element value:runIndex).
+ runIndex := runIndex + 1.
+ ].
+ ^ newCollection
+
+ "
+ #(1 2 3 4) collectWithIndex:[:n :i | n * 2 + i]
+ #(1 2 3 4) collectWithIndex:[:n :i | i -> (n * 2)]
+ "
+!
+
count:aBlock
"count elements, for which aBlock returns true.
Return the sum."
@@ -2417,15 +2520,17 @@
"
#(1 2 3 4) detect:[:n | n odd]
#(2 4 6 8) detect:[:n | n odd]
- "
-!
-
-detect:generatorBlock forWhich:testBlock ifNone:exceptionBlock
+
+ #(1 2 3 4) detect: #odd
+ #(2 4 6 8) detect: #odd
+ "
+!
+
+detect:generatorBlock forWhich:testBlock ifNone:exceptionValue
"evaluate generatorBlock for each element in the receiver until
testBlock returns true for it;
in this case return the value from generatorBlock, which caused the true evaluation.
- If none of the test evaluations returns true, return the result of the
- evaluation of the exceptionBlock"
+ If none of the test evaluations returns true, return the value from exceptionValue"
self do:[:each |
|val|
@@ -2433,7 +2538,7 @@
val := generatorBlock value:each.
(testBlock value:val) ifTrue:[^ val].
].
- ^ exceptionBlock value
+ ^ exceptionValue value
"
#(2 3 4) detect:[:n | n squared] forWhich:[:nsq | nsq odd] ifNone:['sorry']
@@ -2446,17 +2551,16 @@
"
!
-detect:aOneArgBlock ifNone:exceptionBlock
+detect:aOneArgBlock ifNone:exceptionValue
"evaluate the argument, aBlock for each element in the receiver until
the block returns true; in this case return the element which caused
the true evaluation.
- If none of the evaluations returns true, return the result of the
- evaluation of the exceptionBlock"
+ If none of the evaluations returns true, return the value from exceptionValue"
self do:[:each |
(aOneArgBlock value:each) ifTrue:[^ each].
].
- ^ exceptionBlock value
+ ^ exceptionValue value
"
#(1 2 3 4) detect:[:n | n odd] ifNone:['sorry']
@@ -2514,17 +2618,16 @@
"
!
-detectLast:aBlock ifNone:exceptionBlock
+detectLast:aBlock ifNone:exceptionValue
"evaluate the argument, aBlock for each element in the receiver until
the block returns true; in this case return the element which caused
the true evaluation. The elements are processed in reverse order.
- If none of the evaluations returns true, return the result of the
- evaluation of the exceptionBlock"
+ If none of the evaluations returns true, return the value from exceptionValue"
self reverseDo:[:each |
(aBlock value:each) ifTrue:[^ each].
].
- ^ exceptionBlock value
+ ^ exceptionValue value
"
#(1 2 3 4) detectLast:[:n | n odd] ifNone:['sorry']
@@ -2535,44 +2638,57 @@
detectMax: aBlock
"Evaluate aBlock with each of the receiver's elements as the argument.
Answer the element for which aBlock evaluates to the highest magnitude.
- If collection empty, return nil. This method might also be called elect:."
+ If the receiver collection is empty, return nil.
+ This method might also be called elect:."
| maxElement maxValue |
- self do: [:each | | val |
- maxValue == nil
- ifFalse: [
- (val := aBlock value: each) > maxValue ifTrue: [
- maxElement := each.
- maxValue := val]]
- ifTrue: ["first element"
- maxElement := each.
- maxValue := aBlock value: each].
- "Note that there is no way to get the first element that works
- for all kinds of Collections. Must test every one."].
+
+ self do: [:each |
+ | val |
+
+ val := aBlock value: each.
+ "Note that there is no way to get the first element that works
+ for all kinds of Collections.
+ Must test every one (maxValue is nil for the first element)."
+ (maxValue == nil or:[val > maxValue]) ifTrue: [
+ maxElement := each.
+ maxValue := val
+ ]
+ ].
^ maxElement
+ "
+ #(1 -1 5 -17 10 -8 5) detectMax: #abs
+ "
+
"Created: / 20-08-2011 / 21:34:49 / cg"
!
detectMin: aBlock
"Evaluate aBlock with each of the receiver's elements as the argument.
Answer the element for which aBlock evaluates to the lowest number.
- If collection empty, return nil."
+ If the receiver collection is empty, return nil."
| minElement minValue |
- self do: [:each | | val |
- minValue == nil
- ifFalse: [
- (val := aBlock value: each) < minValue ifTrue: [
- minElement := each.
- minValue := val]]
- ifTrue: ["first element"
- minElement := each.
- minValue := aBlock value: each].
- "Note that there is no way to get the first element that works
- for all kinds of Collections. Must test every one."].
+
+ self do: [:each |
+ | val |
+
+ val := aBlock value: each.
+ "Note that there is no way to get the first element that works
+ for all kinds of Collections.
+ Must test every one (maxValue is nil for the first element)."
+ (minValue == nil or:[val < minValue]) ifTrue: [
+ minElement := each.
+ minValue := val
+ ]
+ ].
^ minElement
+ "
+ #(1 -1 5 -17 10 -8 5) detectMin: #abs
+ "
+
"Created: / 20-08-2011 / 21:35:13 / cg"
!
@@ -2735,9 +2851,94 @@
"Modified (format): / 29-02-2012 / 11:50:02 / cg"
!
+doWithIndex:aBlock
+ "Squeak/V'Age compatibility;
+ like keysAndValuesDo:, but passes the index as second argument.
+ Same as withIndexDo:, due to parallel evolution of different Smalltalk dialects"
+
+ self keysAndValuesDo:[:index :el | aBlock value:el value:index].
+
+ "Created: / 17-10-1997 / 12:33:10 / cg"
+!
+
+flatDetect:aBlock
+ "for each element of the collection, if it's a scalar, evaluate aBlock for it;
+ otherwise, recursively invoke flatDetect: on the collection.
+ Return the first element for which aBlock evaluates to true.
+ Thus implementing a depth-first search.
+ Raises an error, if no element is found"
+
+ ^ self flatDetect:aBlock ifNone:[self errorNotFound]
+
+ "
+ #(
+ (1 2 3)
+ 4 5
+ (6)
+ 7
+ (8 (9 10) 11 12 (13 (14 (15) 16)))) flatDetect:[:el | el>5]
+ "
+!
+
+flatDetect:aBlock ifNone:exceptionValue
+ "for each element of the collection, if it's a scalar, evaluate aBlock for it;
+ otherwise, recursively invoke flatDetect: on the collection.
+ Return the first element for which aBlock evaluates to true.
+ Thus implementing a depth-first search.
+ Return the value from exceptionValue if none found"
+
+ self do:[:each |
+ |result|
+
+ (each isNonByteCollection) ifTrue:[
+ each flatDo:[:el | (aBlock value:el) ifTrue:[^ el]].
+ ] ifFalse:[
+ (aBlock value:each) ifTrue:[^ each].
+ ].
+ ].
+ ^ exceptionValue value.
+
+ "
+ #(
+ (1 2 3)
+ 4 5
+ (6)
+ 7
+ ( 8
+ (9 10)
+ 11
+ 12
+ ( 13
+ ( 14
+ (15)
+ 16)
+ )
+ )
+ ) flatDetect:[:el | el<0] ifNone:#none
+ "
+ "
+ #(
+ (1 2 3)
+ 4 5
+ (6)
+ 7
+ ( 8
+ (9 10)
+ 11
+ 12
+ ( 13
+ ( 14
+ (15)
+ 16)
+ )
+ )
+ ) flatDetect:[:el | el>15] ifNone:#none
+ "
+!
+
flatDo:aBlock
- "for each element of the collection, if its a scalar, evaluate aBlock for it;
- otherwise, recursively invoke flatDo on the collection.
+ "for each element of the collection, if it's a scalar, evaluate aBlock for it;
+ otherwise, recursively invoke flatDo: on the collection.
Thus implementing a depth-first enumeration"
self do:[:each |
@@ -2754,7 +2955,8 @@
4 5
(6)
7
- (8 (9 10) 11 12 (13 (14 (15) 16)))) flatDo:[:el | Transcript showCR:el]
+ (8 (9 10) 11 12 (13 (14 (15) 16)))
+ ) flatDo:[:el | Transcript showCR:el]
"
"Modified: / 22-01-2011 / 09:12:22 / cg"
@@ -2823,6 +3025,31 @@
"Modified: 23.4.1996 / 13:47:06 / cg"
!
+injectAndCollect:thisValue into:binaryBlock
+ "starting with thisValue for value, pass this value and each element
+ to binaryBlock, replacing value with the result returned from the block
+ in the next iteration.
+ Collect all results and return them all.
+
+ See also: #fold: #reduce:"
+
+ |coll nextValue|
+
+ coll := self species new.
+ nextValue := thisValue.
+ self do: [:each | nextValue := binaryBlock value:nextValue value:each. coll add:nextValue].
+ ^ coll
+
+ "sum up the elements of a collection:
+
+ #(1 2 3 4) inject:0 into:[:accu :element | accu + element]
+ (1 to:10) inject:0 into:[:accu :element | accu + element]
+
+ same, getting all partial sums:
+ (1 to:10) injectAndCollect:0 into:[:accu :element | accu + element]
+ "
+!
+
keysAndValuesCollect:aBlock
"for each key-value pair in the receiver, evaluate the argument, aBlock
and return a collection with the results.
@@ -2908,6 +3135,7 @@
"
#(1 2 3 4) map:#negated
+ #(1 2 3 4) collect:#negated
"
"Modified (comment): / 29-02-2012 / 11:53:51 / cg"
@@ -3155,16 +3383,16 @@
"Created: / 07-08-2010 / 16:26:15 / cg"
!
-select:aBlock ifNone:exceptionBlock
+select:aBlock ifNone:exceptionValue
"try a new collection with all elements from the receiver, for which
the argument aBlock evaluates to true. If none of the elements passes
- the check of aBlock, return the result of evaluating exceptionBlock.
+ the check of aBlock, return the value from exceptionValue.
See also: #removeAllFoundIn: and #removeAllSuchThat:"
|newCollection|
newCollection := self select:aBlock.
- newCollection isEmpty ifTrue:[^ exceptionBlock value].
+ newCollection isEmpty ifTrue:[^ exceptionValue value].
^ newCollection
"
@@ -3356,6 +3584,25 @@
"
!
+with:aCollection conform:aTwoArgBlock
+ "evaluate the argument, aBlock for successive elements from
+ each the receiver and the argument, aCollection.
+ Return true, if the block returns true for all of these pairs.
+ This method fails if neither the receiver nor aCollection is
+ a sequenceable collection (i.e. implements numeric key access)."
+
+ self with:aCollection do:[:a :b |
+ (aTwoArgBlock value:a value:b) ifFalse:[^ false].
+ ].
+ ^ true.
+
+ "
+ (1 to:3) with:#(1 2 3 4) conform:[:a :b | a = b] --- raises an error
+ (1 to:3) with:#(1 22 3) conform:[:a :b | a = b]
+ (1 to:3) with:#(1 2 3) conform:[:a :b | a = b]
+ "
+!
+
with:aCollection contains:aTwoArgBlock
"evaluate the argument, aBlock for successive elements from
each the receiver and the argument, aCollection.
@@ -3496,6 +3743,33 @@
"Modified: / 30-06-2011 / 17:39:47 / cg"
"Created: / 18-03-2012 / 15:15:04 / cg"
+!
+
+withIndexCollect:aTwoArgBlock
+ "same as keysAndValuesCollect:, but with argument order reversed"
+
+ |newCollection|
+
+ newCollection := OrderedCollection new.
+ self keysAndValuesDo:[:key :value |
+ newCollection add:(aTwoArgBlock value:value value:key)
+ ].
+ ^ newCollection
+
+ "
+ #(one two three) withIndexCollect:[:sym :num | (num->sym)]
+ #(10 20 30) withIndexCollect:[:n :i | n*i ]
+ "
+!
+
+withIndexDo:aTwoArgBlock
+ "evaluate the argument, aBlock for every element in the collection,
+ passing both element and index as arguments.
+ Same as doWithIndex:, due to parallel evolution of different Smalltalk dialects"
+
+ ^ self keysAndValuesDo:[:key :index |
+ aTwoArgBlock value:index value:key
+ ].
! !
!Collection methodsFor:'enumerating-tests'!
@@ -3587,11 +3861,7 @@
!Collection methodsFor:'error handling'!
emptyCheck
- "check if the receiver is empty; report an error if so.
-
- CAVEAT: Set redefines #emptySet with a different meaning,
- so calling this for a Set or a Dictionary does not show the
- expected behaviour!!"
+ "check if the receiver is empty; report an error if so"
self isEmpty ifTrue:[
^ self emptyCollectionError.
@@ -3641,6 +3911,11 @@
creator := Method allSubInstances
detect:[:aMethod | (aMethod referencesGlobal:self)]
ifNone:nil.
+ creator isNil ifTrue:[
+ creator := Method allSubInstances
+ detect:[:aMethod | (aMethod literalsDetect:[:l | l == self] ifNone:nil) notNil]
+ ifNone:nil.
+ ].
creator notNil ifTrue:[
msg := ' (' , creator whoString , ')'
].
@@ -3726,7 +4001,7 @@
"/ what a kludge - Dolphin and Squeak mean: printOn: a stream;
"/ ST/X (and some old ST80's) mean: draw-yourself on a GC.
- (aGCOrStream isStream and:[aGCOrStream ~~ Transcript]) ifFalse:[
+ (aGCOrStream isStream) ifFalse:[
^ super displayOn:aGCOrStream
].
@@ -3941,126 +4216,199 @@
!Collection methodsFor:'queries'!
-arithmeticMean
- "arithmetic mean value of all elements in the collection"
-
- ^ self sum / self size
-
- "
- TestCase assert:( { 1. 2. 3. 4 } arithmeticMean = 2.5).
- TestCase assert:( { 13. 23. 12. 44. 55 } arithmeticMean closeTo: 29.4).
- TestCase assert:( { 13. 23. 12. 44. 55 } standardDeviation closeTo: 19.2431).
- "
-
- "Created: / 13-04-2011 / 16:52:32 / cg"
-!
-
-average
- "average value of all elements in the collection"
-
- ^ self arithmeticMean
-
- "
- TestCase assert:( { 1. 2. 3. 4 } average = 2.5).
- "
-
- "Created: / 18-03-2011 / 10:31:04 / cg"
- "Modified: / 13-04-2011 / 17:09:21 / cg"
-!
-
defaultElement
^ nil
!
-geometricMean
- "geometric mean value of all elements in the collection"
-
- ^ self product raisedTo:(1/self size)
-
- "
- TestCase assert:( { 1. 2. 3. 4. } geometricMean closeTo: 2.21336).
- TestCase assert:( { 1. 2. 3. 4. 5 } geometricMean closeTo: 2.60517).
- TestCase assert:( { 13. 23. 12. 44. 55 } geometricMean closeTo: 24.41932).
- "
-
- "Created: / 13-04-2011 / 16:53:44 / cg"
-!
-
-largest:n
- "return the n largest elements"
-
- |mySize loopAction actionForFirstN actionForRest
- nLargest sz_nLargest minInLargest|
+isReadOnly
+ ^ false
+!
+
+isWritable
+ ^ self isReadOnly not
+!
+
+size
+ "return the number of elements in the receiver.
+ This is usually redefined in subclasses for more performance."
+
+ |count "{ Class: SmallInteger }" |
+
+ count := 0.
+ self do:[:element |
+ count := count + 1
+ ].
+ ^ count
+!
+
+speciesForAdding
+ "like species, but redefined for collections which cannot grow easily.
+ Used by functions which create a growing collection (see collect:with:, for example)"
+
+ ^ self species
+! !
+
+!Collection methodsFor:'searching'!
+
+findFirst:aBlock
+ "find the index of the first element, for which evaluation of the argument, aBlock
+ returns true; return its index or 0 if none detected.
+ This is much like #detect, however, here an INDEX is returned,
+ while #detect returns the element."
+
+ ^ self findFirst:aBlock ifNone:0
+
+ "
+ #(1 2 3 4 5 6) findFirst:[:x | (x >= 3)]
+ #(1 2 3 4 5 6) findFirst:[:x | (x >= 3) and:[x even]]
+ #(1 2 3 4 5 6) findFirst:[:x | (x >= 8)]
+ 'one.two.three' findFirst:[:c | (c == $.)]
+ '__one.two.three' findFirst:[:c | (c ~= $_)]
+ 'one.two.three' findFirst:[:c | (c ~= $_)]
+ "
+
+ "Modified: / 21.10.1998 / 18:48:10 / cg"
+!
+
+findFirst:aBlock ifNone:exceptionValue
+ "find the index of the first element, for which evaluation of the argument, aBlock returns true;
+ return its index or the value from exceptionValue if none detected.
+ This is much like #detect:ifNone:, however, here an INDEX is returned,
+ while #detect:ifNone: returns the element."
+
+ self subclassResponsibility
+
+ "
+ #(1 2 3 4 5 6) findFirst:[:x | (x >= 3)] ifNone:99
+ #(1 2 3 4 5 6) findFirst:[:x | (x >= 9)] ifNone:99
+ "
+!
+
+findLast:aBlock
+ "find the last element, for which evaluation of the argument, aBlock returns true.
+ Return its index or 0 if none detected."
+
+ ^ self findLast:aBlock ifNone:0
+
+ "
+ #(1 99 3 99 5 6) findLast:[:x | (x == 99)]
+ 'one.two.three' findLast:[:c | (c == $.)]
+ "
+!
+
+findLast:aBlock ifNone:exceptionValue
+ "find the index of the last element, for which evaluation of the argument, aBlock returns true.
+ Return its index or the value from exceptionValue if none detected."
+
+ self subclassResponsibility
+
+ "
+ #(1 2 3 4 5 6) findLast:[:x | (x >= 3)] ifNone:99
+ #(1 2 3 4 5 6) findLast:[:x | (x >= 9)] ifNone:99
+ "
+!
+
+keysOfLargest:n
+ "return the keys (aka indices) of the n largest elements, key of largest last.
+ Raises an exception, if the receiver does not contain at least n elements"
+
+ |mySize loopAction actionForFirstN nLargest minInLargest |
mySize := self size.
n > mySize ifTrue:[
self notEnoughElementsError
].
+ "/ for big collections, it seems to be better to sort only once
+ "/ (many individual insert operations into a sortedCollection are expensive)
+ "/ Consider using a tree-oriented collection if this becomes a problem
(n < 50) ifTrue:[
- n == 1 ifTrue:[ ^ Array with:self max ].
+ n == 1 ifTrue:[
+ |max kMax|
+
+ loopAction := [:k :el |
+ max := el. kMax := k.
+ loopAction :=
+ [:k :el |
+ el > max ifTrue:[
+ max := el. kMax := k
+ ].
+ ]
+ ].
+ self keysAndValuesDo:[:k :el | loopAction value:k value:el ].
+ kMax isNil ifTrue:[ self notEnoughElementsError ].
+ ^ Array with:kMax.
+ ].
n == 2 ifTrue:[
- |l1 l2|
-
- loopAction := [:el | l1 := el.
- loopAction :=
- [:el |
- el > l1 ifTrue:[
- l2 := l1. l1 := el
- ] ifFalse:[
- l2 := el
+ |max1 kMax1 max2 kMax2|
+
+ loopAction := [:k :el |
+ max1 := el. kMax1 := k.
+ loopAction :=
+ [:k :el |
+ el > max1 ifTrue:[
+ max2 := max1. kMax2 := kMax1.
+ max1 := el. kMax1 := k
+ ] ifFalse:[
+ max2 := el. kMax2 := k
+ ].
+ loopAction :=
+ [:k :el |
+ el > max2 ifTrue:[
+ el > max1 ifTrue:[
+ max2 := max1. max1 := el.
+ kMax2 := kMax1. kMax1 := k.
+ ] ifFalse:[
+ max2 := el.
+ kMax2 := k.
+ ].
].
- loopAction := actionForRest
]
+ ]
].
- actionForRest := [:el |
- el > l2 ifTrue:[
- el > l1 ifTrue:[
- l2 := l1. l1 := el
- ] ifFalse:[
- l2 := el
- ].
- ].
- ].
-
- self do:[:el | loopAction value:el ].
- ^ Array with:l2 with:l1
+
+ self keysAndValuesDo:[:k :el | loopAction value:k value:el ].
+ kMax2 isNil ifTrue:[ self notEnoughElementsError ].
+ ^ Array with:kMax2 with:kMax1
].
nLargest := SortedCollection new:n.
- sz_nLargest := 0.
+ nLargest setSortBlock:[:a :b | a key < b key].
+
actionForFirstN :=
- [:el |
- nLargest add:el.
- sz_nLargest := sz_nLargest + 1.
- sz_nLargest == n ifTrue:[
- loopAction := actionForRest.
- minInLargest := nLargest min.
- ].
- ].
- actionForRest :=
- [:el |
- el > minInLargest ifTrue:[
- nLargest removeFirst.
- nLargest add:el.
- minInLargest := nLargest min
+ [:k :el |
+ nLargest add:(el -> k).
+ nLargest size == n ifTrue:[
+ minInLargest := nLargest min key.
+ loopAction :=
+ [:k :el |
+ el > minInLargest ifTrue:[
+ nLargest removeFirst.
+ nLargest add:(el -> k).
+ minInLargest := nLargest min key
+ ].
+ ]
].
].
loopAction := actionForFirstN.
- self do:[:el | loopAction value:el ].
- ^ nLargest
+ self keysAndValuesDo:[:k :el | loopAction value:k value:el ].
+ ^ nLargest collect:[:a | a value].
].
- ^ self asSortedCollection copyTo:n
-
- "
- #(10 35 20 45 30 5) largest:1
- #(10 35 20 45 30 5) largest:2
- #(10 35 20 45 30 5) largest:3
- #(10 35 20 45 30 5) largest:5
- #(10 35 20 45 30 5) largest:6
- #(10 35 20 45 30 5) largest:8
+ ^ (self keys asNewOrderedCollection
+ sortWith:self asNewOrderedCollection)
+ copyFrom:(self size-n+1)
+
+ "
+ #(10 35 20 45 30 5) keysOfLargest:1
+ #(10 35 20 45 30 5) keysOfLargest:2
+ #(10 35 20 45 30 5) largest:2
+ #(10 35 20 45 30 5) keysOfLargest:3
+ #(10 35 20 45 30 5) keysOfLargest:5
+ #(10 35 20 45 30 5) keysOfLargest:6
+ #(10 35 20 45 30 5) keysOfLargest:8
+ (1 to: 1000) asArray shuffled keysOfLargest:51
"
"
@@ -4074,7 +4422,7 @@
].
t2 := Time millisecondsToRun:[
40 timesRepeat:[
- data largest:3
+ data keysOfLargest:3
].
].
Transcript show:'asSorted-at -> '; show:t1; showCR:'ms'.
@@ -4082,6 +4430,226 @@
"
!
+keysOfSmallest:n
+ "return the keys (aka indices) of the n smallest elements, key of largest last.
+ Raises an exception, if the receiver does not contain at least n elements"
+
+ |mySize loopAction actionForFirstN nSmallest maxInSmallest |
+
+ mySize := self size.
+ n > mySize ifTrue:[
+ self notEnoughElementsError
+ ].
+
+ "/ for big collections, it seems to be better to sort only once
+ "/ (many individual insert operations into a sortedCollection are expensive)
+ "/ Consider using a tree-oriented collection if this becomes a problem
+ (n < 50) ifTrue:[
+ n == 1 ifTrue:[
+ |min kMin|
+
+ loopAction := [:k :el |
+ min := el. kMin := k.
+ loopAction :=
+ [:k :el |
+ el < min ifTrue:[
+ min := el. kMin := k
+ ].
+ ]
+ ].
+ self keysAndValuesDo:[:k :el | loopAction value:k value:el ].
+ kMin isNil ifTrue:[ self notEnoughElementsError ].
+ ^ Array with:kMin.
+ ].
+ n == 2 ifTrue:[
+ |min1 kMin1 min2 kMin2|
+
+ loopAction := [:k :el |
+ min1 := el. kMin1 := k.
+ loopAction :=
+ [:k :el |
+ el < min1 ifTrue:[
+ min2 := min1. kMin2 := kMin1.
+ min1 := el. kMin1 := k
+ ] ifFalse:[
+ min2 := el. kMin2 := k
+ ].
+ loopAction :=
+ [:k :el |
+ el < min2 ifTrue:[
+ el < min1 ifTrue:[
+ min2 := min1. min1 := el.
+ kMin2 := kMin1. kMin1 := k.
+ ] ifFalse:[
+ min2 := el.
+ kMin2 := k.
+ ].
+ ].
+ ]
+ ]
+ ].
+
+ self keysAndValuesDo:[:k :el | loopAction value:k value:el ].
+ kMin2 isNil ifTrue:[ self notEnoughElementsError ].
+ ^ Array with:kMin1 with:kMin2
+ ].
+
+ nSmallest := SortedCollection new:n.
+ nSmallest setSortBlock:[:a :b | a key < b key].
+
+ actionForFirstN :=
+ [:k :el |
+ nSmallest add:(el -> k).
+ nSmallest size == n ifTrue:[
+ maxInSmallest := nSmallest max key.
+ loopAction :=
+ [:k :el |
+ el < maxInSmallest ifTrue:[
+ nSmallest removeLast.
+ nSmallest add:(el -> k).
+ maxInSmallest := nSmallest max key
+ ].
+ ]
+ ].
+ ].
+
+ loopAction := actionForFirstN.
+ self keysAndValuesDo:[:k :el | loopAction value:k value:el ].
+ ^ nSmallest collect:[:a | a value].
+ ].
+
+ ^ (self keys asNewOrderedCollection
+ sortWith:self asNewOrderedCollection)
+ copyTo:n
+
+ "
+ #(10 35 20 45 30 5) keysOfSmallest:1
+ #(10 35 20 45 30 5) keysOfSmallest:2
+ #(10 35 20 45 30 5) smallest:2
+ #(10 35 20 45 30 5) keysOfSmallest:3
+ #(10 35 20 45 30 5) keysOfSmallest:5
+ #(10 35 20 45 30 5) keysOfSmallest:6
+ #(10 35 20 45 30 5) keysOfSmallest:8
+ (1 to: 1000) asArray shuffled keysOfSmallest:51
+ "
+
+ "
+ |t1 t2 data|
+
+ data := (1 to:10000) collect:[:i | Random nextInteger ].
+ t1 := Time millisecondsToRun:[
+ 40 timesRepeat:[
+ data asSortedCollection at:3
+ ]
+ ].
+ t2 := Time millisecondsToRun:[
+ 40 timesRepeat:[
+ data keysOfSmallest:3
+ ].
+ ].
+ Transcript show:'asSorted-at -> '; show:t1; showCR:'ms'.
+ Transcript show:'largest -> '; show:t2; showCR:'ms'.
+ "
+!
+
+largest:n
+ "return a collection containing the n largest elements, largest last.
+ Raises an exception, if the receiver does not contain at least n elements"
+
+ |mySize loopAction nLargest sz_nLargest minInLargest|
+
+ mySize := self size.
+ n > mySize ifTrue:[
+ self notEnoughElementsError
+ ].
+
+ "/ for big collections, it seems to be better to sort only once
+ "/ (many individual insert operations into a sortedCollection are expensive)
+ "/ Consider using a tree-oriented collection if this becomes a problem
+ (n < 50) ifTrue:[
+ n == 1 ifTrue:[ ^ Array with:self max ].
+ n == 2 ifTrue:[
+ |l1 l2|
+
+ loopAction := [:el |
+ l1 := el.
+ loopAction :=
+ [:el |
+ el > l1 ifTrue:[
+ l2 := l1. l1 := el
+ ] ifFalse:[
+ l2 := el
+ ].
+ loopAction :=
+ [:el |
+ el > l2 ifTrue:[
+ el > l1 ifTrue:[
+ l2 := l1. l1 := el
+ ] ifFalse:[
+ l2 := el
+ ].
+ ].
+ ].
+ ]
+ ].
+
+ self do:[:el | loopAction value:el ].
+ ^ Array with:l2 with:l1
+ ].
+
+ nLargest := SortedCollection new:n.
+ sz_nLargest := 0.
+ loopAction :=
+ [:el |
+ nLargest add:el.
+ sz_nLargest := sz_nLargest + 1.
+ sz_nLargest == n ifTrue:[
+ loopAction :=
+ [:el |
+ el > minInLargest ifTrue:[
+ nLargest removeFirst.
+ nLargest add:el.
+ minInLargest := nLargest min
+ ].
+ ].
+ minInLargest := nLargest min.
+ ].
+ ].
+
+ self do:[:el | loopAction value:el ].
+ ^ nLargest
+ ].
+
+ ^ self asSortedCollection copyTo:n
+
+ "
+ #(10 35 20 45 30 5) largest:1
+ #(10 35 20 45 30 5) largest:2
+ #(10 35 20 45 30 5) largest:3
+ #(10 35 20 45 30 5) largest:5
+ #(10 35 20 45 30 5) largest:6
+ #(10 35 20 45 30 5) largest:8
+ "
+
+ "
+ |t1 t2 data|
+
+ data := (1 to:100000) collect:[:i | Random nextInteger ].
+ t1 := Time millisecondsToRun:[
+ 40 timesRepeat:[
+ data asSortedCollection copyLast:2
+ ]
+ ].
+ t2 := Time millisecondsToRun:[
+ 40 timesRepeat:[
+ data largest:2
+ ].
+ ].
+ Transcript show:'asSorted -> '; show:t1; showCR:'ms'.
+ Transcript show:'largest -> '; show:t2; showCR:'ms'.
+ "
+!
+
longestCommonPrefix
"return the longest common prefix of my elements.
Typically used with string collections."
@@ -4367,46 +4935,105 @@
"
!
-size
- "return the number of elements in the receiver.
- This is usually redefined in subclasses for more performance."
-
- |count "{ Class: SmallInteger }" |
-
- count := 0.
- self do:[:element |
- count := count + 1
+smallest:n
+ "return the n smallest elements"
+
+ |mySize loopAction actionForFirstN actionForRest
+ nSmallest sz_nSmallest maxInSmallest|
+
+ mySize := self size.
+ n > mySize ifTrue:[
+ self notEnoughElementsError
].
- ^ count
-!
-
-speciesForAdding
- "like species, but redefined for collections which cannot grow easily.
- Used by functions which create a growing collection (see collect:with:, for example)"
-
- ^ self species
-! !
-
-!Collection methodsFor:'searching'!
-
-findFirst:aBlock
- "find the index of the first element, for which evaluation of the argument, aBlock
- returns true; return its index or 0 if none detected.
- This is much like #detect, however, here an INDEX is returned,
- while #detect returns the element."
-
- ^ self findFirst:aBlock ifNone:0
-
- "
- #(1 2 3 4 5 6) findFirst:[:x | (x >= 3)]
- #(1 2 3 4 5 6) findFirst:[:x | (x >= 3) and:[x even]]
- #(1 2 3 4 5 6) findFirst:[:x | (x >= 8)]
- 'one.two.three' findFirst:[:c | (c == $.)]
- '__one.two.three' findFirst:[:c | (c ~= $_)]
- 'one.two.three' findFirst:[:c | (c ~= $_)]
- "
-
- "Modified: / 21.10.1998 / 18:48:10 / cg"
+
+ "/ for big collections, it seems to be better to sort only once
+ "/ (many individual insert operations into a sortedCollection are expensive)
+ "/ Consider using a tree-oriented collection if this becomes a problem
+ (n < 50) ifTrue:[
+ n == 1 ifTrue:[ ^ Array with:self min ].
+ n == 2 ifTrue:[
+ |l1 l2|
+
+ loopAction := [:el | l1 := el.
+ loopAction :=
+ [:el |
+ el < l1 ifTrue:[
+ l2 := l1. l1 := el
+ ] ifFalse:[
+ l2 := el
+ ].
+ loopAction := actionForRest
+ ]
+ ].
+ actionForRest := [:el |
+ el < l2 ifTrue:[
+ el < l1 ifTrue:[
+ l2 := l1. l1 := el
+ ] ifFalse:[
+ l2 := el
+ ].
+ ].
+ ].
+
+ self do:[:el | loopAction value:el ].
+ ^ Array with:l1 with:l2
+ ].
+
+ nSmallest := SortedCollection new:n.
+ sz_nSmallest := 0.
+ actionForFirstN :=
+ [:el |
+ nSmallest add:el.
+ sz_nSmallest := sz_nSmallest + 1.
+ sz_nSmallest == n ifTrue:[
+ loopAction := actionForRest.
+ maxInSmallest := nSmallest max.
+ ].
+ ].
+ actionForRest :=
+ [:el |
+ el < maxInSmallest ifTrue:[
+ nSmallest removeLast.
+ nSmallest add:el.
+ maxInSmallest := nSmallest max
+ ].
+ ].
+
+ loopAction := actionForFirstN.
+ self do:[:el | loopAction value:el ].
+ ^ nSmallest
+ ].
+
+ ^ self asSortedCollection copyFrom:(self size - n + 1)
+
+ "
+ #(10 35 20 45 30 5) smallest:1
+ #(10 35 20 45 30 5) smallest:2
+ #(10 35 20 45 30 5) smallest:3
+ #(10 35 20 45 30 5) smallest:5
+ #(10 35 20 45 30 5) smallest:6
+ (1 to:10000) asArray shuffled smallest:10
+ (1 to:10000) asArray shuffled largest:10
+ #(10 35 20 45 30 5) smallest:8
+ "
+
+ "
+ |t1 t2 data|
+
+ data := (1 to:10000) collect:[:i | Random nextInteger ].
+ t1 := Time millisecondsToRun:[
+ 40 timesRepeat:[
+ data asSortedCollection at:3
+ ]
+ ].
+ t2 := Time millisecondsToRun:[
+ 40 timesRepeat:[
+ data smallest:3
+ ].
+ ].
+ Transcript show:'asSorted-at -> '; show:t1; showCR:'ms'.
+ Transcript show:'smallest -> '; show:t2; showCR:'ms'.
+ "
! !
!Collection methodsFor:'set operations'!
@@ -4510,19 +5137,57 @@
!Collection methodsFor:'sorting & reordering'!
+sortedBy:aBlock
+ "Create a copy that is sorted. Sort criteria is the block that accepts two arguments.
+ When the block returns true, the first arg goes first ([:a :b | a > b] sorts in descending order)."
+
+ ^ (self asNewOrderedCollection sort: aBlock)
+
+ "Modified: / 22-10-2008 / 21:25:07 / cg"
+!
+
+sortedBySelector:aSelector
+ "return a new collection containing my elements sorted based on the value of what aSelector returns when sent to my
+ elements. Sorting by a selector is so common, that it's worth a separate utility"
+
+ ^ self sortedBy:[:a :b | (a perform:aSelector) < (b perform:aSelector)]
+
+ "
+ |a b|
+
+ a := #(123 25235 12 13423423 234234).
+ b := a sortedBySelector:#abs
+ "
+!
+
topologicalSort
"Sort a partial ordered collection.
The receiver consists of tupels defining a partial order.
Use the algorithm by R. E. Tarjan from 1972.
Answer an OrderedCollection containing the sorted items"
+ ^ self topologicalSortStable: false
+
+ "Modified: / 05-06-2014 / 12:22:14 / Jan Vrany <jan.vrany@fit.cvut.cz>"
+!
+
+topologicalSortStable: sortStable
+ "Sort a partial ordered collection.
+ The receiver consists of tupels defining a partial order.
+ Use the algorithm by R. E. Tarjan from 1972.
+ Answer an OrderedCollection containing the sorted items.
+
+ If sortStable is true, try to make order stable among
+ multiple invocations. If false, stability is not guaranteed.
+ "
+
|graph roots sorted count|
"create a graph.
For each node there is an entry containing the number of references
and a list of arcs to other nodes"
- graph := Dictionary new.
+ graph := sortStable ifTrue:[ OrderedDictionary new ] ifFalse:[ Dictionary new ].
self do:[:eachTuple|
|node1|
@@ -4616,10 +5281,63 @@
Array with:eachClass superclass with:eachClass
]) topologicalSort
"
+
+ "Modified: / 05-06-2014 / 12:21:55 / Jan Vrany <jan.vrany@fit.cvut.cz>"
! !
!Collection methodsFor:'statistical functions'!
+arithmeticMean
+ "arithmetic mean value of all elements in the collection"
+
+ ^ self sum / self size
+
+ "
+ TestCase assert:( { 1. 2. 3. 4 } arithmeticMean = 2.5).
+ TestCase assert:( { 13. 23. 12. 44. 55 } arithmeticMean closeTo: 29.4).
+ TestCase assert:( { 13. 23. 12. 44. 55 } standardDeviation closeTo: 19.2431).
+ "
+
+ "Created: / 13-04-2011 / 16:52:32 / cg"
+!
+
+average
+ "average value of all elements in the collection"
+
+ ^ self arithmeticMean
+
+ "
+ TestCase assert:( { 1. 2. 3. 4 } average = 2.5).
+ "
+
+ "Created: / 18-03-2011 / 10:31:04 / cg"
+ "Modified: / 13-04-2011 / 17:09:21 / cg"
+!
+
+geometricMean
+ "geometric mean value of all elements in the collection"
+
+ ^ self product raisedTo:(1/self size)
+
+ "
+ TestCase assert:( { 1. 2. 3. 4. } geometricMean closeTo: 2.21336).
+ TestCase assert:( { 1. 2. 3. 4. 5 } geometricMean closeTo: 2.60517).
+ TestCase assert:( { 13. 23. 12. 44. 55 } geometricMean closeTo: 24.41932).
+ "
+
+ "Created: / 13-04-2011 / 16:53:44 / cg"
+!
+
+median
+ "Return the middle element, or as close as we can get."
+
+ ^ self asSortedCollection median
+
+ "
+ #(10 35 20 45 30 5) median
+ "
+!
+
standardDeviation
"standard deviation value of all elements in the collection,
which is the complete set and not a sample."
@@ -4752,18 +5470,31 @@
"Modified: / 13-10-2006 / 12:54:50 / cg"
!
-includesAny:aCollection
+includesAny:searchCollection
"return true, if the the receiver includes any elements of
the argument, aCollection; false if it includes none.
- Notice: this method has O^2(N) runtime behavior and may be
- slow for big receivers/args.
- Think about using a Set or Dictionary.
- Some speedup is also possible, by arranging highly
- probable elements towards the beginning of aCollection,
- to avoid useless searches."
-
- aCollection do:[:element |
- (self includes:element) ifTrue:[^ true].
+ Notice:
+ this method has O^2(N) runtime behavior and may be
+ slow for big receivers/args.
+ Think about using a Set or Dictionary.
+ Some speedup is also possible, by arranging highly
+ probable elements towards the beginning of aCollection,
+ to avoid useless searches.
+
+ Also: I am not sure, if (and if so, at which breakeven),
+ it is better to reverse the loops, and walk over the receiver's
+ elements once, walking over the searched elements in the inner loop.
+ If the receiver is large, caching effects will definitely favour this.
+ "
+
+ self size < searchCollection size ifTrue:[
+ self do:[:existingElement |
+ (searchCollection includes:existingElement) ifTrue:[^ true].
+ ].
+ ] ifFalse:[
+ searchCollection do:[:searchedElement |
+ (self includes:searchedElement) ifTrue:[^ true].
+ ].
].
^ false
@@ -4772,6 +5503,34 @@
#('hello' 'there' 'world') includesAny:#('hello' 'world')
#(1 2 3 4 5 6 7) includesAny:#(7 8 9)
#(1 2 3 4 5 6 7) includesAny:#(8 9 10)
+
+ |coll|
+ coll := (1 to:10000) asOrderedCollection.
+ Time millisecondsToRun:[
+ 100000 timesRepeat:[ coll includesAny:#(500 600) ]
+ ].
+
+ |coll|
+ coll := (1 to:10000) asOrderedCollection.
+ Time millisecondsToRun:[
+ 100000 timesRepeat:[ coll includesAny:#(-1 -10) ]
+ ].
+
+ Notice: it is redefined for string search in a subclass:
+
+ |coll|
+ coll := String new:10000 withAll:$a.
+ coll at:500 put:$b.
+ Time millisecondsToRun:[
+ 100000 timesRepeat:[ coll includesAny:'bc' ]
+ ].
+
+ |coll|
+ coll := String new:10000 withAll:$a.
+ Time millisecondsToRun:[
+ 100000 timesRepeat:[ coll includesAny:'bc' ]
+ ].
+
"
!
@@ -4979,18 +5738,20 @@
!Collection methodsFor:'visiting'!
acceptVisitor:aVisitor with:aParameter
+ "dispatch for visitor pattern; send #visitCollection:with: to aVisitor"
^ aVisitor visitCollection:self with:aParameter
! !
+
!Collection class methodsFor:'documentation'!
version
- ^ '$Header: /cvs/stx/stx/libbasic/Collection.st,v 1.319 2013-12-06 14:41:05 stefan Exp $'
+ ^ '$Header: /cvs/stx/stx/libbasic/Collection.st,v 1.361 2015-03-28 09:01:50 cg Exp $'
!
version_CVS
- ^ '$Header: /cvs/stx/stx/libbasic/Collection.st,v 1.319 2013-12-06 14:41:05 stefan Exp $'
+ ^ '$Header: /cvs/stx/stx/libbasic/Collection.st,v 1.361 2015-03-28 09:01:50 cg Exp $'
! !