--- a/Assoc.st Thu Nov 23 02:19:14 1995 +0100
+++ b/Assoc.st Thu Nov 23 02:21:27 1995 +0100
@@ -11,10 +11,10 @@
"
LookupKey subclass:#Association
- instanceVariableNames:'value'
- classVariableNames:''
- poolDictionaries:''
- category:'Collections-Support'
+ instanceVariableNames:'value'
+ classVariableNames:''
+ poolDictionaries:''
+ category:'Collections-Support'
!
!Association class methodsFor:'documentation'!
@@ -33,10 +33,6 @@
"
!
-version
- ^ '$Header: /cvs/stx/stx/libbasic/Attic/Assoc.st,v 1.13 1995-11-11 14:26:43 cg Exp $'
-!
-
documentation
"
Associations are a key-value pair; conceptionally, they are the elements of
@@ -49,6 +45,10 @@
key <Object> the key (inherited)
value <Object> the value
"
+!
+
+version
+ ^ '$Header: /cvs/stx/stx/libbasic/Attic/Assoc.st,v 1.14 1995-11-23 01:21:08 cg Exp $'
! !
!Association class methodsFor:'instance creation'!
@@ -61,6 +61,14 @@
!Association methodsFor:'accessing'!
+key:aKey value:aValue
+ "set both the key and value of the receiver.
+ Return the receiver"
+
+ key := aKey.
+ value := aValue
+!
+
value
"return the value of the association"
@@ -72,14 +80,6 @@
Return the receiver"
value := anObject
-!
-
-key:aKey value:aValue
- "set both the key and value of the receiver.
- Return the receiver"
-
- key := aKey.
- value := aValue
! !
!Association methodsFor:'comparing'!
@@ -106,6 +106,14 @@
!Association methodsFor:'printing & storing'!
+displayString
+ "return a string containing a printable representation
+ of the receiver for displaying - redefined to use display string on
+ the components for nicer look"
+
+ ^ key displayString , '->' , value displayString
+!
+
printOn:aStream
"return a string containing a printable representation
of the receiver"
@@ -113,12 +121,5 @@
key printOn:aStream.
aStream nextPutAll:'->'.
value printOn:aStream
-!
+! !
-displayString
- "return a string containing a printable representation
- of the receiver for displaying - redefined to use display string on
- the components for nicer look"
-
- ^ key displayString , '->' , value displayString
-! !
--- a/Association.st Thu Nov 23 02:19:14 1995 +0100
+++ b/Association.st Thu Nov 23 02:21:27 1995 +0100
@@ -11,10 +11,10 @@
"
LookupKey subclass:#Association
- instanceVariableNames:'value'
- classVariableNames:''
- poolDictionaries:''
- category:'Collections-Support'
+ instanceVariableNames:'value'
+ classVariableNames:''
+ poolDictionaries:''
+ category:'Collections-Support'
!
!Association class methodsFor:'documentation'!
@@ -33,10 +33,6 @@
"
!
-version
- ^ '$Header: /cvs/stx/stx/libbasic/Association.st,v 1.13 1995-11-11 14:26:43 cg Exp $'
-!
-
documentation
"
Associations are a key-value pair; conceptionally, they are the elements of
@@ -49,6 +45,10 @@
key <Object> the key (inherited)
value <Object> the value
"
+!
+
+version
+ ^ '$Header: /cvs/stx/stx/libbasic/Association.st,v 1.14 1995-11-23 01:21:08 cg Exp $'
! !
!Association class methodsFor:'instance creation'!
@@ -61,6 +61,14 @@
!Association methodsFor:'accessing'!
+key:aKey value:aValue
+ "set both the key and value of the receiver.
+ Return the receiver"
+
+ key := aKey.
+ value := aValue
+!
+
value
"return the value of the association"
@@ -72,14 +80,6 @@
Return the receiver"
value := anObject
-!
-
-key:aKey value:aValue
- "set both the key and value of the receiver.
- Return the receiver"
-
- key := aKey.
- value := aValue
! !
!Association methodsFor:'comparing'!
@@ -106,6 +106,14 @@
!Association methodsFor:'printing & storing'!
+displayString
+ "return a string containing a printable representation
+ of the receiver for displaying - redefined to use display string on
+ the components for nicer look"
+
+ ^ key displayString , '->' , value displayString
+!
+
printOn:aStream
"return a string containing a printable representation
of the receiver"
@@ -113,12 +121,5 @@
key printOn:aStream.
aStream nextPutAll:'->'.
value printOn:aStream
-!
+! !
-displayString
- "return a string containing a printable representation
- of the receiver for displaying - redefined to use display string on
- the components for nicer look"
-
- ^ key displayString , '->' , value displayString
-! !
--- a/Link.st Thu Nov 23 02:19:14 1995 +0100
+++ b/Link.st Thu Nov 23 02:21:27 1995 +0100
@@ -11,10 +11,10 @@
"
Object subclass:#Link
- instanceVariableNames:'nextLink'
- classVariableNames:''
- poolDictionaries:''
- category:'Collections-Support'
+ instanceVariableNames:'nextLink'
+ classVariableNames:''
+ poolDictionaries:''
+ category:'Collections-Support'
!
!Link class methodsFor:'documentation'!
@@ -33,10 +33,6 @@
"
!
-version
- ^ '$Header: /cvs/stx/stx/libbasic/Link.st,v 1.9 1995-11-11 15:23:51 cg Exp $'
-!
-
documentation
"
this class provides the basic functionality for Link-nodes.
@@ -44,6 +40,10 @@
something, just the link-chain.
For more usability look at ValueLink or other subclasses.
"
+!
+
+version
+ ^ '$Header: /cvs/stx/stx/libbasic/Link.st,v 1.10 1995-11-23 01:21:19 cg Exp $'
! !
!Link methodsFor:'accessing'!
@@ -59,3 +59,4 @@
nextLink := aLink
! !
+
--- a/LookupKey.st Thu Nov 23 02:19:14 1995 +0100
+++ b/LookupKey.st Thu Nov 23 02:21:27 1995 +0100
@@ -11,10 +11,10 @@
"
Magnitude subclass:#LookupKey
- instanceVariableNames:'key'
- classVariableNames:''
- poolDictionaries:''
- category:'Collections-Support'
+ instanceVariableNames:'key'
+ classVariableNames:''
+ poolDictionaries:''
+ category:'Collections-Support'
!
!LookupKey class methodsFor:'documentation'!
@@ -33,10 +33,6 @@
"
!
-version
- ^ '$Header: /cvs/stx/stx/libbasic/LookupKey.st,v 1.4 1995-11-11 15:23:54 cg Exp $'
-!
-
documentation
"
LookupKey has been extracted from Association for ST-80 compatibility.
@@ -46,6 +42,10 @@
key <Object> the key
"
+!
+
+version
+ ^ '$Header: /cvs/stx/stx/libbasic/LookupKey.st,v 1.5 1995-11-23 01:21:27 cg Exp $'
! !
!LookupKey class methodsFor:'instance creation'!
@@ -73,6 +73,13 @@
!LookupKey methodsFor:'comparing'!
+< aKey
+ "return true, if the receivers KEY is less
+ than the arguments key. The argument must be a kind of lookupKey"
+
+ ^ key < aKey key
+!
+
= aLookupKey
"return true if the receiver equals the argument.
Notice, that in contrast to the less/greater compares,
@@ -81,40 +88,34 @@
^ (self species == aLookupKey species) and:[key = aLookupKey key]
!
+> aKey
+ "return true, if the receivers KEY is greater
+ than the arguments key. The argument must be a kind of lookupKey"
+
+ ^ key > aKey key
+!
+
hash
"return an integer useful for hashing on the receiver;
redefined since = is redefined here."
^ key hash
-!
-
-< aKey
- "return true, if the receivers KEY is less
- than the arguments key. The argument must be a kind of lookupKey"
-
- ^ key < aKey key
-!
-
-> aKey
- "return true, if the receivers KEY is greater
- than the arguments key. The argument must be a kind of lookupKey"
-
- ^ key > aKey key
! !
!LookupKey methodsFor:'printing & storing'!
-printOn:aStream
- "return a string containing a printable representation
- of the receiver"
-
- key printOn:aStream.
-!
-
displayString
"return a string containing a printable representation
of the receiver for displaying - redefined to use display string on
the components for nicer look"
^ self class name , '(' , key displayString , ')'
+!
+
+printOn:aStream
+ "return a string containing a printable representation
+ of the receiver"
+
+ key printOn:aStream.
! !
+
--- 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!
--- a/SortedCollection.st Thu Nov 23 02:19:14 1995 +0100
+++ b/SortedCollection.st Thu Nov 23 02:21:27 1995 +0100
@@ -33,10 +33,6 @@
"
!
-version
- ^ '$Header: /cvs/stx/stx/libbasic/SortedCollection.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/SortedCollection.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!