--- a/OrderedCollection.st	Fri Apr 04 10:24:43 2014 +0200
+++ b/OrderedCollection.st	Tue Apr 08 14:33:23 2014 +0200
@@ -593,6 +593,7 @@
     "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
@@ -614,6 +615,7 @@
     "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|
@@ -641,7 +643,8 @@
 
 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
@@ -659,32 +662,35 @@
     "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:
-        if a large number of objects is to be removed this way,
+     Performance: 
+        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.
-    sz := self size.
-    [runIndex <= sz] whileTrue:[
-        element := self at:runIndex.
+    dstIndex := firstIndex.
+    firstIndex to: lastIndex do:[:srcIndex |
+        element := contentsArray at:srcIndex.
         (aBlock value:element) ifTrue:[
-            removed add:element.
-            self removeAtIndex:runIndex.
-            sz := sz - 1.
+            removed add:element
         ] ifFalse:[
-            runIndex := runIndex + 1
-        ]
+            contentsArray at:dstIndex put:element.
+            dstIndex := dstIndex + 1.
+        ].
     ].
+    contentsArray from:dstIndex to:lastIndex put:nil.
+    lastIndex := dstIndex - 1.
     ^ removed
 
     "
@@ -694,13 +700,35 @@
      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 }" |
@@ -738,7 +766,8 @@
 
 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|
 
@@ -779,7 +808,8 @@
 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 }" |
 
@@ -827,6 +857,7 @@
 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
@@ -920,6 +951,7 @@
     "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|
@@ -966,8 +998,55 @@
     "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 }" |
@@ -1001,6 +1080,7 @@
 
 removeLast:n
     "remove the last n elements from the receiver collection. 
+     Destructive: modifies the receiver.
      Return a collection of removed elements."
 
     |mySize ret|
@@ -2034,6 +2114,6 @@
 !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 $'
 ! !