diff -r 7a9ab63a6757 -r a9a526c51233 SortColl.st --- 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!