--- a/Collection.st	Mon Sep 18 11:05:03 2006 +0200
+++ b/Collection.st	Mon Sep 18 11:05:06 2006 +0200
@@ -2484,6 +2484,102 @@
     ^  nil
 !
 
+largest:n
+    "return the n largest elements"
+
+    |mySize loopAction actionForFirstN actionForRest 
+     nLargest sz_nLargest minInLargest|
+
+    mySize := self size.
+    n > mySize ifTrue:[
+        self notEnoughElementsError
+    ].
+
+    (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 := 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
+        ].
+
+        nLargest := SortedCollection new:n.
+        sz_nLargest := 0.
+        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
+                ].
+            ].
+
+        loopAction := actionForFirstN.
+        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:10000) collect:[:i | Random nextInteger ].
+     t1 := Time millisecondsToRun:[
+        40 timesRepeat:[
+            data asSortedCollection at:3 
+        ]
+     ].
+     t2 := Time millisecondsToRun:[
+        40 timesRepeat:[
+            data largest:3
+        ].
+     ].
+     Transcript show:'asSorted-at -> '; 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."
@@ -2667,6 +2763,39 @@
     "
 !
 
+nthLargest:n
+    "return the n-largest element"
+
+    ^ (self largest:n) first
+
+    "
+     #(10 35 20 45 30 5) nthLargest:1
+     #(10 35 20 45 30 5) nthLargest:2
+     #(10 35 20 45 30 5) nthLargest:3
+     #(10 35 20 45 30 5) nthLargest:5
+     #(10 35 20 45 30 5) nthLargest:6 
+     #(10 35 20 45 30 5) nthLargest:8
+    "
+
+    "
+     |t1 t2 data|
+
+     data := (1 to:10000) collect:[:i | Random nextInteger ].
+     t1 := Time millisecondsToRun:[
+        40 timesRepeat:[
+            data asSortedCollection at:6 
+        ]
+     ].
+     t2 := Time millisecondsToRun:[
+        40 timesRepeat:[
+            data nthLargest:6 
+        ].
+     ].
+     Transcript show:'asSorted-at -> '; show:t1; showCR:'ms'.
+     Transcript show:'nthMost     -> '; show:t2; showCR:'ms'.
+    "
+!
+
 size
     "return the number of elements in the receiver.
      This is usually redefined in subclasses for more performance."
@@ -3002,7 +3131,7 @@
 !Collection class methodsFor:'documentation'!
 
 version
-    ^ '$Header: /cvs/stx/stx/libbasic/Collection.st,v 1.195 2006-09-13 09:19:51 cg Exp $'
+    ^ '$Header: /cvs/stx/stx/libbasic/Collection.st,v 1.196 2006-09-18 09:05:06 cg Exp $'
 ! !
 
 Collection initialize!