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.
SortColl.st
changeset 607 a9a526c51233
parent 530 07d0bce293c9
child 629 2ceefe9b5a19 
--- a/SortColl.st	Thu Nov 23 02:19:14 1995 +0100
+++ b/SortColl.st	Thu Nov 23 02:21:27 1995 +0100
@@ -33,10 +33,6 @@
 "
 !
 
-version
-    ^ '$Header: /cvs/stx/stx/libbasic/Attic/SortColl.st,v 1.21 1995-11-11 15:27:30 cg Exp $'
-!
-
 documentation
 "
     I keep my elements sorted. The sort order is defined by a sortblock,
@@ -48,6 +44,10 @@
     while [:a :b | a > b] defines descening order.
     The default sortBlock for SortedCollections is the first one.
 "
+!
+
+version
+    ^ '$Header: /cvs/stx/stx/libbasic/Attic/SortColl.st,v 1.22 1995-11-23 01:20:20 cg Exp $'
 ! !
 
 !SortedCollection class methodsFor:'initialization'!
@@ -91,34 +91,28 @@
     "
 ! !
 
-!SortedCollection methodsFor:'copying'!
-
-copyEmpty:size
-    "return a copy of the receiver with no elements, but
-     the same size. This method has been be redefined to
-     preserve the sortBlock."
-
-    ^ (self species new:size) sortBlock:sortBlock
-! !
-
 !SortedCollection methodsFor:'adding & removing'!
 
-addFirst:anObject
-    "catch this - its not allowed for sortedCollections"
+add:anObject
+    "add the argument, anObject at the proper place in the
+     receiver. Returns the argument, anObject."
 
-    self shouldNotImplement
-!
+    |index|
 
-addLast:anObject
-    "catch this - its not allowed for sortedCollections"
+    lastIndex < firstIndex "i.e. self size == 0" ifTrue:[
+	super add:anObject
+    ] ifFalse:[
+	index := self indexForInserting:anObject. 
+	self makeRoomAtIndex:index.
+	contentsArray at:index put:anObject
+    ].
+    ^ anObject
 
-    self shouldNotImplement
-!
-
-at:index put:anObject
-    "catch this - its not allowed for sortedCollections"
-
-    self shouldNotImplement
+    "
+     |c| #(7 3 9 10 99) asSortedCollection add:5; yourself    
+     #(7 3 9 10 99) asSortedCollection add:1; yourself        
+     #(7 3 9 10 99) asSortedCollection add:1000; yourself     
+    "
 !
 
 add:newObject after:oldObject
@@ -175,30 +169,46 @@
     "
 !
 
-add:anObject
-    "add the argument, anObject at the proper place in the
-     receiver. Returns the argument, anObject."
+addFirst:anObject
+    "catch this - its not allowed for sortedCollections"
+
+    self shouldNotImplement
+!
 
-    |index|
+addLast:anObject
+    "catch this - its not allowed for sortedCollections"
+
+    self shouldNotImplement
+!
 
-    lastIndex < firstIndex "i.e. self size == 0" ifTrue:[
-	super add:anObject
-    ] ifFalse:[
-	index := self indexForInserting:anObject. 
-	self makeRoomAtIndex:index.
-	contentsArray at:index put:anObject
+at:index put:anObject
+    "catch this - its not allowed for sortedCollections"
+
+    self shouldNotImplement
+! !
+
+!SortedCollection methodsFor:'converting'!
+
+asSortedCollection
+    "return the receiver as a sorted collection"
+
+    "could be an instance of a subclass..."
+    self class == SortedCollection ifTrue:[
+	^ self
     ].
-    ^ anObject
-
-    "
-     |c| #(7 3 9 10 99) asSortedCollection add:5; yourself    
-     #(7 3 9 10 99) asSortedCollection add:1; yourself        
-     #(7 3 9 10 99) asSortedCollection add:1000; yourself     
-    "
+    ^ super asSortedCollection
 ! !
 
 !SortedCollection methodsFor:'copying'!
 
+copyEmpty:size
+    "return a copy of the receiver with no elements, but
+     the same size. This method has been be redefined to
+     preserve the sortBlock."
+
+    ^ (self species new:size) sortBlock:sortBlock
+!
+
 postCopyFrom:anOriginal
     "sent after a copy or when a new collection species has been created.
      The new collection should have the same sortBlock as the original."
@@ -214,18 +224,6 @@
     "
 ! !
 
-!SortedCollection methodsFor:'converting'!
-
-asSortedCollection
-    "return the receiver as a sorted collection"
-
-    "could be an instance of a subclass..."
-    self class == SortedCollection ifTrue:[
-	^ self
-    ].
-    ^ super asSortedCollection
-! !
-
 !SortedCollection methodsFor:'enumerating'!
 
 collect:aBlock
@@ -246,6 +244,163 @@
     ^ newCollection
 ! !
 
+!SortedCollection methodsFor:'instance protocol'!
+
+sortBlock
+    "return the block used for sorting"
+
+    ^ sortBlock
+!
+
+sortBlock:aSortBlock
+    "change the sort criteria for a sorted collection, resort the elements of 
+    the collection, and return the receiver. The argument, aSortBlock must
+    be a two-argument block which returns true if its arg1 has to come before
+    its arg2 in the collection."
+
+    sortBlock := aSortBlock.
+    lastIndex > firstIndex ifTrue:[
+	contentsArray quickSortFrom:firstIndex to:lastIndex sortBlock:aSortBlock
+    ]
+
+    "
+     #(9 8 7 6 5 4 3) asSortedCollection
+     #(9 8 7 6 5 4 3) asSortedCollection sortBlock:[:a : b | a < b]
+     #(9 8 7 6 5 4 3) asSortedCollection sortBlock:[:a : b | a > b]
+     #($f $G $z $Y $o $H) asSortedCollection
+     #($f $G $z $Y $o $H) asSortedCollection sortBlock:[:a : b | a asUppercase < b asUppercase]
+    "
+! !
+
+!SortedCollection methodsFor:'private'!
+
+indexForInserting:anObject
+    "search the index at which to insert anObject. Can also be used
+     to search for an existing element by checking if the element at
+     the returned index is the one we look for.
+     The returned index is a physical one, for accessing contentsArray."
+
+    |low    "{ Class: SmallInteger}"
+     high   "{ Class: SmallInteger}"
+     middle "{ Class: SmallInteger}"
+     element|
+
+    "
+     we can of course use a binary search - since the elements are
+     sorted
+    "
+    low := firstIndex.
+    high := lastIndex.
+    [low <= high] whileTrue:[
+	middle := (low + high) // 2.
+	element := contentsArray at:middle.
+	(sortBlock value:element value:anObject) ifTrue:[
+	    "middleelement is smaller than object"
+	    low := middle + 1
+	] ifFalse:[
+	    high := middle - 1
+	]
+    ].
+    ^ low
+
+    "
+     #(1 2 3 4 7 99 1313 981989 898989898) asSortedCollection indexForInserting:50      
+     #(1.0 2.0 3 4 7 49.0 51.0 99 1313 981989 898989898) asSortedCollection indexForInserting:50 
+    "
+
+!
+
+setSortBlock: aSortBlock
+    "set the sortblock without resorting - private only"
+
+    sortBlock := aSortBlock
+! !
+
+!SortedCollection methodsFor:'searching'!
+
+after:anObject
+    "return the element after the argument, anObject; or nil if there is none.
+     If anObject is contained multiple times in the collection, return the
+     the first element which is non-equal to anObject.
+     If the receiver does not contain anObject, report an error"
+
+    ^ self after:anObject ifAbsent:[self errorValueNotFound:anObject]
+
+    "
+     #(7 3 9 10 99) asSortedCollection after:50
+     #(7 3 9 10 99) asSortedCollection after:1 
+     #(7 3 9 10 99) asSortedCollection after:10
+     #(7 3 9 10 99) asSortedCollection after:7 
+     #(7 3 9 10 99) asSortedCollection after:99 
+     #(7 10 3 10 9 10 10 99) asSortedCollection after:9  
+     #(7 10 3 10 9 10 10 99) asSortedCollection after:10 
+    "
+!
+
+after:anObject ifAbsent:exceptionBlock
+    "return the element after the argument, anObject; or nil if there is none.
+     If anObject is contained multiple times in the collection, return the
+     the first element which is non-equal to anObject.
+     If the receiver does not contain anObject, return the result from evaluating
+     exceptionBlock."
+
+    |index      "{ Class: SmallInteger }"|
+
+    index := self indexForInserting:anObject.
+    ((index < firstIndex) 
+     or:[(contentsArray at:index) ~= anObject]) ifTrue:[^ exceptionBlock value].
+
+    "skip multiple occurences of the same ..."
+
+    [(index <= lastIndex) and:[(contentsArray at:index) = anObject]] whileTrue:[
+	index := index + 1
+    ].
+    (index > lastIndex) ifTrue:[^ nil].
+    ^ contentsArray at:index
+!
+
+before:anObject
+    "return the element before the argument, anObject; or nil if there is none.
+     If the receiver does not contain anObject, report an error"
+
+    ^ self before:anObject ifAbsent:[self errorValueNotFound:anObject]
+
+    "
+     #(7 3 9 10 99) asSortedCollection before:50
+     #(7 3 9 10 99) asSortedCollection before:1 
+     #(7 3 9 10 99) asSortedCollection before:1000 
+     #(7 3 9 10 99) asSortedCollection before:10
+     #(7 3 9 10 99) asSortedCollection before:7 
+     #(7 3 9 10 99) asSortedCollection before:99 
+     #(7 10 3 10 9 10 10 99) asSortedCollection before:9
+     #(7 10 3 10 9 10 10 99) asSortedCollection before:10
+    "
+!
+
+before:anObject ifAbsent:exceptionBlock
+    "return the element before the argument, anObject; or nil if there is none.
+     If the receiver does not contain anObject, return the result from evaluating
+     exceptionBlock."
+
+    |index      "{ Class: SmallInteger }"|
+
+    index := self indexForInserting:anObject.
+    ((index <= firstIndex) 
+     or:[(contentsArray at:index) ~= anObject]) ifTrue:[^ exceptionBlock value].
+
+    ^ contentsArray at:index - 1
+
+    "
+     #(7 3 9 10 99) asSortedCollection before:50
+     #(7 3 9 10 99) asSortedCollection before:1 
+     #(7 3 9 10 99) asSortedCollection before:10  
+     #(7 3 9 10 99) asSortedCollection before:7   
+     #(7 3 9 10 99) asSortedCollection before:99   
+     #(7 10 3 10 9 10 10 99) asSortedCollection before:9  
+     #(7 10 3 10 9 10 10 99) asSortedCollection before:10   
+    "
+! !
+
 !SortedCollection methodsFor:'testing'!
 
 includes:anObject
@@ -290,159 +445,4 @@
     "
 ! !
 
-!SortedCollection methodsFor:'searching'!
-
-before:anObject
-    "return the element before the argument, anObject; or nil if there is none.
-     If the receiver does not contain anObject, report an error"
-
-    ^ self before:anObject ifAbsent:[self errorValueNotFound:anObject]
-
-    "
-     #(7 3 9 10 99) asSortedCollection before:50
-     #(7 3 9 10 99) asSortedCollection before:1 
-     #(7 3 9 10 99) asSortedCollection before:1000 
-     #(7 3 9 10 99) asSortedCollection before:10
-     #(7 3 9 10 99) asSortedCollection before:7 
-     #(7 3 9 10 99) asSortedCollection before:99 
-     #(7 10 3 10 9 10 10 99) asSortedCollection before:9
-     #(7 10 3 10 9 10 10 99) asSortedCollection before:10
-    "
-!
-
-before:anObject ifAbsent:exceptionBlock
-    "return the element before the argument, anObject; or nil if there is none.
-     If the receiver does not contain anObject, return the result from evaluating
-     exceptionBlock."
-
-    |index      "{ Class: SmallInteger }"|
-
-    index := self indexForInserting:anObject.
-    ((index <= firstIndex) 
-     or:[(contentsArray at:index) ~= anObject]) ifTrue:[^ exceptionBlock value].
-
-    ^ contentsArray at:index - 1
-
-    "
-     #(7 3 9 10 99) asSortedCollection before:50
-     #(7 3 9 10 99) asSortedCollection before:1 
-     #(7 3 9 10 99) asSortedCollection before:10  
-     #(7 3 9 10 99) asSortedCollection before:7   
-     #(7 3 9 10 99) asSortedCollection before:99   
-     #(7 10 3 10 9 10 10 99) asSortedCollection before:9  
-     #(7 10 3 10 9 10 10 99) asSortedCollection before:10   
-    "
-!
-
-after:anObject
-    "return the element after the argument, anObject; or nil if there is none.
-     If anObject is contained multiple times in the collection, return the
-     the first element which is non-equal to anObject.
-     If the receiver does not contain anObject, report an error"
-
-    ^ self after:anObject ifAbsent:[self errorValueNotFound:anObject]
-
-    "
-     #(7 3 9 10 99) asSortedCollection after:50
-     #(7 3 9 10 99) asSortedCollection after:1 
-     #(7 3 9 10 99) asSortedCollection after:10
-     #(7 3 9 10 99) asSortedCollection after:7 
-     #(7 3 9 10 99) asSortedCollection after:99 
-     #(7 10 3 10 9 10 10 99) asSortedCollection after:9  
-     #(7 10 3 10 9 10 10 99) asSortedCollection after:10 
-    "
-!
-
-after:anObject ifAbsent:exceptionBlock
-    "return the element after the argument, anObject; or nil if there is none.
-     If anObject is contained multiple times in the collection, return the
-     the first element which is non-equal to anObject.
-     If the receiver does not contain anObject, return the result from evaluating
-     exceptionBlock."
-
-    |index      "{ Class: SmallInteger }"|
-
-    index := self indexForInserting:anObject.
-    ((index < firstIndex) 
-     or:[(contentsArray at:index) ~= anObject]) ifTrue:[^ exceptionBlock value].
-
-    "skip multiple occurences of the same ..."
-
-    [(index <= lastIndex) and:[(contentsArray at:index) = anObject]] whileTrue:[
-	index := index + 1
-    ].
-    (index > lastIndex) ifTrue:[^ nil].
-    ^ contentsArray at:index
-! !
-
-!SortedCollection methodsFor:'instance protocol'!
-
-sortBlock
-    "return the block used for sorting"
-
-    ^ sortBlock
-!
-
-sortBlock:aSortBlock
-    "change the sort criteria for a sorted collection, resort the elements of 
-    the collection, and return the receiver. The argument, aSortBlock must
-    be a two-argument block which returns true if its arg1 has to come before
-    its arg2 in the collection."
-
-    sortBlock := aSortBlock.
-    lastIndex > firstIndex ifTrue:[
-	contentsArray quickSortFrom:firstIndex to:lastIndex sortBlock:aSortBlock
-    ]
-
-    "
-     #(9 8 7 6 5 4 3) asSortedCollection
-     #(9 8 7 6 5 4 3) asSortedCollection sortBlock:[:a : b | a < b]
-     #(9 8 7 6 5 4 3) asSortedCollection sortBlock:[:a : b | a > b]
-     #($f $G $z $Y $o $H) asSortedCollection
-     #($f $G $z $Y $o $H) asSortedCollection sortBlock:[:a : b | a asUppercase < b asUppercase]
-    "
-! !
-
-!SortedCollection methodsFor:'private'!
-
-setSortBlock: aSortBlock
-    "set the sortblock without resorting - private only"
-
-    sortBlock := aSortBlock
-!
-
-indexForInserting:anObject
-    "search the index at which to insert anObject. Can also be used
-     to search for an existing element by checking if the element at
-     the returned index is the one we look for.
-     The returned index is a physical one, for accessing contentsArray."
-
-    |low    "{ Class: SmallInteger}"
-     high   "{ Class: SmallInteger}"
-     middle "{ Class: SmallInteger}"
-     element|
-
-    "
-     we can of course use a binary search - since the elements are
-     sorted
-    "
-    low := firstIndex.
-    high := lastIndex.
-    [low <= high] whileTrue:[
-	middle := (low + high) // 2.
-	element := contentsArray at:middle.
-	(sortBlock value:element value:anObject) ifTrue:[
-	    "middleelement is smaller than object"
-	    low := middle + 1
-	] ifFalse:[
-	    high := middle - 1
-	]
-    ].
-    ^ low
-
-    "
-     #(1 2 3 4 7 99 1313 981989 898989898) asSortedCollection indexForInserting:50      
-     #(1.0 2.0 3 4 7 49.0 51.0 99 1313 981989 898989898) asSortedCollection indexForInserting:50 
-    "
-
-! !
+SortedCollection initialize!
hg/stx-libbasic