Mercurial Mercurial > hg > stx-libbasic / diff
summary | shortlog | changelog | graph | tags | bookmarks | branches | files | changeset | file | latest | revisions | annotate | diff | comparison | raw | help
Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
SequenceableCollection.st
changeset 2069 f6183117f922
parent 1673 eea933dbf42d
child 2165 9ef030343739 
--- a/SequenceableCollection.st	Sun Jan 05 15:51:02 1997 +0100
+++ b/SequenceableCollection.st	Sun Jan 05 18:15:27 1997 +0100
@@ -17,7 +17,7 @@
 	category:'Collections-Abstract'
 !
 
-!SequenceableCollection  class methodsFor:'documentation'!
+!SequenceableCollection class methodsFor:'documentation'!
 
 copyright
 "
@@ -61,7 +61,7 @@
 "
 ! !
 
-!SequenceableCollection  class methodsFor:'instance creation'!
+!SequenceableCollection class methodsFor:'instance creation'!
 
 new:size withAll:element
     "return a new collection of size, where all elements are
@@ -1815,6 +1815,146 @@
     "
 ! !
 
+!SequenceableCollection methodsFor:'private sorting helpers'!
+
+quickSortFrom:inBegin to:inEnd
+    "actual quicksort worker for sort-message"
+
+    |begin   "{ Class: SmallInteger }"
+     end     "{ Class: SmallInteger }"
+     b       "{ Class: SmallInteger }"
+     e       "{ Class: SmallInteger }"
+     middleElement temp1 temp2 |
+
+    begin := inBegin.   "/ this also does a type-check
+    end := inEnd.
+
+    b := begin.
+    e := end.
+    middleElement := self at:((b + e) // 2).
+
+    [b < e] whileTrue:[
+	[b < end and:[(self at:b) < middleElement]] whileTrue:[b := b + 1].
+	[e > begin and:[middleElement < (self at:e)]] whileTrue:[e := e - 1].
+
+	(b <= e) ifTrue:[
+	    (b == e) ifFalse:[
+		temp1 := self at:b. temp2 := self at:e. 
+		self at:b put:temp2. self at:e put:temp1
+	    ].
+	    b := b + 1.
+	    e := e - 1
+	]
+    ].
+    (begin < e) ifTrue:[self quickSortFrom:begin to:e].
+    (b < end) ifTrue:[self quickSortFrom:b to:end]
+!
+
+quickSortFrom:inBegin to:inEnd sortBlock:sortBlock
+    "actual quicksort worker for sort:-message"
+
+    |begin   "{ Class: SmallInteger }"
+     end     "{ Class: SmallInteger }"
+     b       "{ Class: SmallInteger }"
+     e       "{ Class: SmallInteger }"
+     middleElement temp1 temp2 |
+
+    begin := inBegin.   "/ this also does a type-check
+    end := inEnd.
+
+    b := begin.
+    e := end.
+    middleElement := self at:((b + e) // 2).
+
+    [b < e] whileTrue:[
+	[b < end and:[sortBlock value:(self at:b) value:middleElement]] whileTrue:[b := b + 1].
+	[e > begin and:[sortBlock value:middleElement value:(self at:e)]] whileTrue:[e := e - 1].
+
+	(b <= e) ifTrue:[
+	    (b == e) ifFalse:[
+		temp1 := self at:b. temp2 := self at:e. 
+		self at:b put:temp2. self at:e put:temp1
+	    ].
+	    b := b + 1.
+	    e := e - 1
+	]
+    ].
+    (begin < e) ifTrue:[self quickSortFrom:begin to:e sortBlock:sortBlock].
+    (b < end) ifTrue:[self quickSortFrom:b to:end sortBlock:sortBlock]
+!
+
+quickSortFrom:inBegin to:inEnd sortBlock:sortBlock with:aCollection
+    "actual quicksort worker for sort:with:-message"
+
+    |begin   "{ Class: SmallInteger }"
+     end     "{ Class: SmallInteger }"
+     b       "{ Class: SmallInteger }"
+     e       "{ Class: SmallInteger }"
+     middleElement temp1 temp2 |
+
+    begin := inBegin.   "/ this also does a type-check
+    end := inEnd.
+
+    b := begin.
+    e := end.
+    middleElement := self at:((b + e) // 2).
+
+    [b < e] whileTrue:[
+        [b < end and:[sortBlock value:(self at:b) value:middleElement]] whileTrue:[b := b + 1].
+        [e > begin and:[sortBlock value:middleElement value:(self at:e)]] whileTrue:[e := e - 1].
+
+        (b <= e) ifTrue:[
+            (b == e) ifFalse:[
+                temp1 := self at:b. temp2 := self at:e. 
+                self at:b put:temp2. self at:e put:temp1.
+                temp1 := aCollection at:b. temp2 := aCollection at:e. 
+                aCollection at:b put:temp2. aCollection at:e put:temp1
+            ].
+            b := b + 1.
+            e := e - 1
+        ]
+    ].
+    (begin < e) ifTrue:[self quickSortFrom:begin to:e sortBlock:sortBlock with:aCollection].
+    (b < end) ifTrue:[self quickSortFrom:b to:end sortBlock:sortBlock with:aCollection]
+
+    "Modified: 5.1.1997 / 18:12:36 / cg"
+!
+
+quickSortFrom:inBegin to:inEnd with:aCollection
+    "actual quicksort worker for sortWith-message"
+
+    |begin   "{ Class: SmallInteger }"
+     end     "{ Class: SmallInteger }"
+     b       "{ Class: SmallInteger }"
+     e       "{ Class: SmallInteger }"
+     middleElement temp1 temp2 |
+
+    begin := inBegin.   "/ this also does a type-check
+    end := inEnd.
+
+    b := begin.
+    e := end.
+    middleElement := self at:((b + e) // 2).
+
+    [b < e] whileTrue:[
+	[b < end and:[(self at:b) < middleElement]] whileTrue:[b := b + 1].
+	[e > begin and:[middleElement < (self at:e)]] whileTrue:[e := e - 1].
+
+	(b <= e) ifTrue:[
+	    (b == e) ifFalse:[
+		temp1 := self at:b. temp2 := self at:e. 
+		self at:b put:temp2. self at:e put:temp1.
+		temp1 := aCollection at:b. temp2 := aCollection at:e. 
+		aCollection at:b put:temp2. aCollection at:e put:temp1
+	    ].
+	    b := b + 1.
+	    e := e - 1
+	]
+    ].
+    (begin < e) ifTrue:[self quickSortFrom:begin to:e with:aCollection].
+    (b < end) ifTrue:[self quickSortFrom:b to:end with:aCollection]
+! !
+
 !SequenceableCollection methodsFor:'queries'!
 
 firstIndex
@@ -2500,142 +2640,6 @@
 
 !SequenceableCollection methodsFor:'sorting & reordering'!
 
-quickSortFrom:inBegin to:inEnd
-    "actual quicksort worker for sort-message"
-
-    |begin   "{ Class: SmallInteger }"
-     end     "{ Class: SmallInteger }"
-     b       "{ Class: SmallInteger }"
-     e       "{ Class: SmallInteger }"
-     middleElement temp1 temp2 |
-
-    begin := inBegin.   "/ this also does a type-check
-    end := inEnd.
-
-    b := begin.
-    e := end.
-    middleElement := self at:((b + e) // 2).
-
-    [b < e] whileTrue:[
-	[b < end and:[(self at:b) < middleElement]] whileTrue:[b := b + 1].
-	[e > begin and:[middleElement < (self at:e)]] whileTrue:[e := e - 1].
-
-	(b <= e) ifTrue:[
-	    (b == e) ifFalse:[
-		temp1 := self at:b. temp2 := self at:e. 
-		self at:b put:temp2. self at:e put:temp1
-	    ].
-	    b := b + 1.
-	    e := e - 1
-	]
-    ].
-    (begin < e) ifTrue:[self quickSortFrom:begin to:e].
-    (b < end) ifTrue:[self quickSortFrom:b to:end]
-!
-
-quickSortFrom:inBegin to:inEnd sortBlock:sortBlock
-    "actual quicksort worker for sort:-message"
-
-    |begin   "{ Class: SmallInteger }"
-     end     "{ Class: SmallInteger }"
-     b       "{ Class: SmallInteger }"
-     e       "{ Class: SmallInteger }"
-     middleElement temp1 temp2 |
-
-    begin := inBegin.   "/ this also does a type-check
-    end := inEnd.
-
-    b := begin.
-    e := end.
-    middleElement := self at:((b + e) // 2).
-
-    [b < e] whileTrue:[
-	[b < end and:[sortBlock value:(self at:b) value:middleElement]] whileTrue:[b := b + 1].
-	[e > begin and:[sortBlock value:middleElement value:(self at:e)]] whileTrue:[e := e - 1].
-
-	(b <= e) ifTrue:[
-	    (b == e) ifFalse:[
-		temp1 := self at:b. temp2 := self at:e. 
-		self at:b put:temp2. self at:e put:temp1
-	    ].
-	    b := b + 1.
-	    e := e - 1
-	]
-    ].
-    (begin < e) ifTrue:[self quickSortFrom:begin to:e sortBlock:sortBlock].
-    (b < end) ifTrue:[self quickSortFrom:b to:end sortBlock:sortBlock]
-!
-
-quickSortFrom:inBegin to:inEnd sortBlock:sortBlock with:aCollection
-    "actual quicksort worker for sort:with:-message"
-
-    |begin   "{ Class: SmallInteger }"
-     end     "{ Class: SmallInteger }"
-     b       "{ Class: SmallInteger }"
-     e       "{ Class: SmallInteger }"
-     middleElement temp1 temp2 |
-
-    begin := inBegin.   "/ this also does a type-check
-    end := inEnd.
-
-    b := begin.
-    e := end.
-    middleElement := self at:((b + e) // 2).
-
-    [b < e] whileTrue:[
-	[b < end and:[sortBlock value:(self at:b) value:middleElement]] whileTrue:[b := b + 1].
-	[e > begin and:[sortBlock value:middleElement value:(self at:e)]] whileTrue:[e := e - 1].
-
-	(b <= e) ifTrue:[
-	    (b == e) ifFalse:[
-		temp1 := self at:b. temp2 := self at:e. 
-		self at:b put:temp2. self at:e put:temp1.
-		temp1 := aCollection at:b. temp2 := aCollection at:e. 
-		aCollection at:b put:temp2. aCollection at:e put:temp1
-	    ].
-	    b := b + 1.
-	    e := e - 1
-	]
-    ].
-    (begin < e) ifTrue:[self quickSortFrom:begin to:e sortBlock:sortBlock with:aCollection].
-    (b < end) ifTrue:[self quickSortFrom:b to:end sortBlock:sortBlock with:aCollection]
-!
-
-quickSortFrom:inBegin to:inEnd with:aCollection
-    "actual quicksort worker for sortWith-message"
-
-    |begin   "{ Class: SmallInteger }"
-     end     "{ Class: SmallInteger }"
-     b       "{ Class: SmallInteger }"
-     e       "{ Class: SmallInteger }"
-     middleElement temp1 temp2 |
-
-    begin := inBegin.   "/ this also does a type-check
-    end := inEnd.
-
-    b := begin.
-    e := end.
-    middleElement := self at:((b + e) // 2).
-
-    [b < e] whileTrue:[
-	[b < end and:[(self at:b) < middleElement]] whileTrue:[b := b + 1].
-	[e > begin and:[middleElement < (self at:e)]] whileTrue:[e := e - 1].
-
-	(b <= e) ifTrue:[
-	    (b == e) ifFalse:[
-		temp1 := self at:b. temp2 := self at:e. 
-		self at:b put:temp2. self at:e put:temp1.
-		temp1 := aCollection at:b. temp2 := aCollection at:e. 
-		aCollection at:b put:temp2. aCollection at:e put:temp1
-	    ].
-	    b := b + 1.
-	    e := e - 1
-	]
-    ].
-    (begin < e) ifTrue:[self quickSortFrom:begin to:e with:aCollection].
-    (b < end) ifTrue:[self quickSortFrom:b to:end with:aCollection]
-!
-
 reverse
     "reverse the order of the elements inplace"
 
@@ -2661,7 +2665,7 @@
 
 sort
     "sort the collection inplace. The elements are compared using
-     > and < i.e. they should offer a magnitude-like protocol.
+     '<' i.e. they should offer a magnitude-like protocol.
      The implementation uses the quicksort algorithm, which may not be
      the best possible for all situations."
 
@@ -2669,7 +2673,7 @@
 
     stop := self size.
     (stop > 1) ifTrue:[
-	self quickSortFrom:1 to:stop
+        self quickSortFrom:1 to:stop
     ]
 
     "
@@ -2682,6 +2686,8 @@
      data reverse. 
      'reverse ' print. (Time millisecondsToRun:[data sort]) printNL.
     "
+
+    "Modified: 5.1.1997 / 17:51:03 / cg"
 !
 
 sort:sortBlock
@@ -2692,25 +2698,29 @@
 
     stop := self size.
     (stop > 1) ifTrue:[
-	self quickSortFrom:1 to:stop sortBlock:sortBlock
+        self quickSortFrom:1 to:stop sortBlock:sortBlock
     ]
 
     "
-     #(1 16 7 98 3 19 4 0) sort:[:a :b | a < b]
-     #(1 16 7 98 3 19 4 0) sort:[:a :b | a > b]
+     #(1 16 7 98 3 19 4 0) sort:[:a :b | a < b] 
+     #(1 16 7 98 3 19 4 0) sort:[:a :b | a > b] 
+     #(1 -1 16 -16 7 -7 98 -98) sort:[:a :b | a < b] 
+     #(1 -1 16 -16 7 -7 98 -98) sort:[:a :b | a abs < b abs] 
     "
+
+    "Modified: 5.1.1997 / 17:52:27 / cg"
 !
 
 sort:sortBlock with:aCollection
     "sort the collection inplace using the 2-arg block sortBlock
      for comparison. Also reorder the elements in aCollection.
-     Use, when you have a key collection to sort some other collection with."
+     Use this, when you have a key collection to sort some other collection with."
 
     |stop|
 
     stop := self size.
     (stop > 1) ifTrue:[
-	self quickSortFrom:1 to:stop sortBlock:sortBlock with:aCollection
+        self quickSortFrom:1 to:stop sortBlock:sortBlock with:aCollection
     ]
 
     "
@@ -2721,17 +2731,20 @@
      c1 printNL.
      c2 printNL
     "
+
+    "Modified: 5.1.1997 / 17:52:45 / cg"
 !
 
 sortWith:aCollection
-    "sort the receiver collection inplace, also sort aCollection with it.
-     Use, when you have a key collection to sort another collection with."
+    "sort the receiver collection inplace, using '<' to compare elements.
+     Also, the elements of aCollection are reordered with it.
+     Use this, when you have a key collection to sort another collection with."
 
     |stop|
 
     stop := self size.
     (stop > 1) ifTrue:[
-	self quickSortFrom:1 to:stop with:aCollection
+        self quickSortFrom:1 to:stop with:aCollection
     ]
 
     "
@@ -2742,6 +2755,8 @@
      c1 printNL.
      c2 printNL
     "
+
+    "Modified: 5.1.1997 / 17:53:26 / cg"
 !
 
 topologicalSort:sortBlock
@@ -2802,8 +2817,8 @@
     "
 ! !
 
-!SequenceableCollection  class methodsFor:'documentation'!
+!SequenceableCollection class methodsFor:'documentation'!
 
 version
-    ^ '$Header: /cvs/stx/stx/libbasic/SequenceableCollection.st,v 1.69 1996-09-22 15:36:11 cg Exp $'
+    ^ '$Header: /cvs/stx/stx/libbasic/SequenceableCollection.st,v 1.70 1997-01-05 17:15:27 cg Exp $'
 ! !
hg/stx-libbasic