hg/stx-libbasic: comparison OrderedCollection.st

equal deleted inserted replaced

-:aad4b514271c
+:2d8de035fd7a
 clearContents
 "remove all elements from the collection but keep the contentsArray.
 Useful for huge lists, if the contents will be rebuild soon (using #add:)
 to a size which is similar to the lists current size.
+Destructive: modifies the receiver.
 Returns the receiver."
 "/ clear those references, to give the garbage collector
 "/ a chance ...
 remove:anObject ifAbsent:exceptionBlock
 "remove the first element which is equal to anObject;
 if found, remove and return it;
 if not, return the value from evaluating exceptionBlock.
+Destructive: modifies the receiver.
 Uses equality compare (=) to search for the element."
 |index retVal|
 index := self indexOf:anObject.
 "Modified: 8.2.1997 / 19:17:19 / cg"
 !
 removeAll
 "remove all elements from the collection.
-Returns the receiver."
+Returns the receiver.
+Destructive: modifies the receiver."
 contentsArray size <= 20 ifTrue:[
 "/ reuse the contents array
 contentsArray atAllPut:nil.
 firstIndex := 1.
 removeAllSuchThat:aBlock
 "remove all elements that meet a test criteria as specified in aBlock.
 The argument, aBlock is evaluated for successive elements and all those,
 for which it returns true, are removed.
+Destructive: modifies the receiver.
 Return a collection containing the removed elements.
-Performance hint:
+Performance:
-if a large number of objects is to be removed this way,
+this is an O(N) algorithm.
+If a large number of objects is to be removed this way,
 it may be better to rebuild a new collection via #select:,
 since removing elements out of the middle is somewhat slow
 due to the need to copy over remaining elements within the collection."
 "/ this is a q&d implementation (possibly slow).
-|runIndex removed element sz|
+|removed element dstIndex|
 removed := OrderedCollection new.
-runIndex := 1.
+dstIndex := firstIndex.
-sz := self size.
+firstIndex to: lastIndex do:[:srcIndex |
-[runIndex <= sz] whileTrue:[
+element := contentsArray at:srcIndex.
-element := self at:runIndex.
 (aBlock value:element) ifTrue:[
-removed add:element.
+removed add:element
-self removeAtIndex:runIndex.
-sz := sz - 1.
 ] ifFalse:[
-runIndex := runIndex + 1
+contentsArray at:dstIndex put:element.
-]
+dstIndex := dstIndex + 1.
 ].
+].
+contentsArray from:dstIndex to:lastIndex put:nil.
+lastIndex := dstIndex - 1.
 ^ removed
 "
 |coll|
 coll := OrderedCollection withAll:(1 to:10).
 Transcript showCR:(coll removeAllSuchThat:[:el | el even]).
 Transcript showCR:coll
 "
+"
+|coll1 coll2|
+coll1 := OrderedCollection withAll:(1 to:1000).
+Transcript show:'(1000) - '; showCR:(
+Time millisecondsToRun:[
+100 timesRepeat:[ coll1 copy removeAllSuchThat:[:el | el even] ]
+]).
+coll2 := OrderedCollection withAll:(1 to:10000).
+Transcript show:'(10000) - '; showCR:(
+Time millisecondsToRun:[
+100 timesRepeat:[ coll2 copy removeAllSuchThat:[:el | el even] ]
+]).
+coll2 := OrderedCollection withAll:(1 to:50000).
+Transcript show:'(50000) - '; showCR:(
+Time millisecondsToRun:[
+100 timesRepeat:[ coll2 copy removeAllSuchThat:[:el | el even] ]
+]).
+"
 "Modified: 8.2.1997 / 19:19:00 / cg"
 !
 removeFirst
 "remove the first element from the collection; return the element.
-If there is no element in the receiver collection, raise an error."
+If there is no element in the receiver collection, raise an error.
+Destructive: modifies the receiver"
 |anObject
 fI "{ Class: SmallInteger }" |
 fI := firstIndex.
 "Modified: / 5.2.1999 / 23:22:58 / cg"
 !
 removeFirst:n
 "remove the first n elements from the collection;
-Return a collection containing the removed elements."
+Return a collection containing the removed elements.
+Destructive: modifies the receiver"
 |mySize ret newFirstIndex|
 mySize := self size.
 mySize < n ifTrue:[
 !
 removeFirstIfAbsent:exceptionBlock
 "remove the first element from the collection; return the element.
 If there is no element in the receiver collection, return the value from
-exceptionBlock."
+exceptionBlock.
+Destructive: modifies the receiver"
 |anObject fI "{ Class: SmallInteger }" |
 fI := firstIndex.
 !
 removeFromIndex:startIndex toIndex:stopIndex
 "remove the elements stored under startIndex up to and including
 the elements under stopIndex.
+Destructive: modifies the receiver
 Return the receiver.
 Returning the receiver here is a historic leftover - it may change.
 Please use yourself in a cascade, if you need the receiver's value
 when using this method."
 removeIdentical:anObject ifAbsent:exceptionBlock
 "remove the first element which is identical to anObject;
 if found, remove and return it;
 if not, return the value from evaluating exceptionBlock.
+Destructive: modifies the receiver.
 Uses identity compare (==) to search for the element."
 |index|
 index := contentsArray identityIndexOf:anObject startingAt:firstIndex endingAt:lastIndex.
 "
 "Modified: 8.2.1997 / 18:57:43 / cg"
 !
+removeIndices:aSortedCollectionOfIndices
+"remove all elements stored in any of aSortedCollectionOfIndices,
+which must be sorted and sequenceable.
+Destructive: modifies the receiver.
+Returns a collection of removed elements.
+Performance:
+this is an O(N) algorithm."
+|removed element dstIndex indexIndex nextIndex numIndices|
+removed := OrderedCollection new.
+dstIndex := firstIndex.
+numIndices := aSortedCollectionOfIndices size.
+indexIndex := 1.
+nextIndex := aSortedCollectionOfIndices at:1.
+firstIndex to: lastIndex do:[:srcIndex |
+element := contentsArray at:srcIndex.
+srcIndex == nextIndex ifTrue:[
+removed add:element.
+indexIndex := indexIndex + 1.
+indexIndex > numIndices ifTrue:[
+nextIndex := nil.
+] ifFalse:[
+nextIndex := aSortedCollectionOfIndices at:indexIndex.
+].
+] ifFalse:[
+contentsArray at:dstIndex put:element.
+dstIndex := dstIndex + 1.
+].
+].
+contentsArray from:dstIndex to:lastIndex put:nil.
+lastIndex := dstIndex - 1.
+^ removed
+"
+|coll|
+coll := OrderedCollection withAll:(1 to:10).
+Transcript showCR:(coll removeIndices:#(1 5 7)).
+Transcript showCR:coll
+"
+!
 removeLast
-"remove the last element from the collection; return the element"
+"remove the last element from the collection.
+Return the removed element.
+Destructive: modifies the receiver"
 |anObject
 idx "{ Class: SmallInteger }" |
 idx := lastIndex.
 "Modified: / 12.11.1997 / 17:58:57 / cg"
 !
 removeLast:n
 "remove the last n elements from the receiver collection.
+Destructive: modifies the receiver.
 Return a collection of removed elements."
 |mySize ret|
 mySize := self size.
 ! !
 !OrderedCollection class methodsFor:'documentation'!
 version
-^ '$Header: /cvs/stx/stx/libbasic/OrderedCollection.st,v 1.110 2013-09-14 01:25:37 cg Exp $'
+^ '$Header: /cvs/stx/stx/libbasic/OrderedCollection.st,v 1.111 2014-04-08 12:33:23 cg Exp $'
 ! !

changeset 16304	2d8de035fd7a
parent 15757	f7e84eeeaaa9
child 16305	964f7ffb315d