--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/SortColl.st Fri Jul 16 11:39:45 1993 +0200
@@ -0,0 +1,234 @@
+"
+ COPYRIGHT (c) 1993 by Claus Gittinger
+ All Rights Reserved
+
+ This software is furnished under a license and may be used
+ only in accordance with the terms of that license and with the
+ inclusion of the above copyright notice. This software may not
+ be provided or otherwise made available to, or used by, any
+ other person. No title to or ownership of the software is
+ hereby transferred.
+"
+
+OrderedCollection subclass:#SortedCollection
+ instanceVariableNames:'sortBlock'
+ classVariableNames:'DefaultSortBlock'
+ poolDictionaries:''
+ category:'Collections-Ordered'
+!
+
+SortedCollection comment:'
+
+COPYRIGHT (c) 1993 by Claus Gittinger
+ All Rights Reserved
+
+I keep my elements sorted. The sort order is defined by a sortblock,
+which is a two-argument block which, when given two elements of the
+collection, returns true if the element given as first arg has to
+come before the element given as second arg.
+Thus a sortBlock of [:a :b | a < b] defines ascending sort-order,
+while [:a :b | a > b] defines descening order.
+
+%W% %E%
+'!
+
+!SortedCollection class methodsFor:'initialization'!
+
+initialize
+ DefaultSortBlock := [:a :b | a < b ]
+
+ "SortedCollection initialize"
+! !
+
+!SortedCollection class methodsFor:'instance creation'!
+
+new
+ ^ super new setSortBlock:DefaultSortBlock
+!
+
+new:size
+ ^ (super new:size) setSortBlock:DefaultSortBlock
+!
+
+sortBlock:aBlock
+ ^ super new setSortBlock:aBlock
+! !
+
+!SortedCollection methodsFor:'adding & removing'!
+
+addFirst:anObject
+ self shouldNotImplement
+!
+
+addLast:anObject
+ self shouldNotImplement
+!
+
+at:index put:anObject
+ self shouldNotImplement
+!
+
+add:newObject after:oldObject
+ self shouldNotImplement
+!
+
+add:newObject before:oldObject
+ self shouldNotImplement
+!
+
+addAll:aCollection
+ "add all elements of the argument, aCollection to the
+ receiver"
+
+ |mySize "{ Class: SmallInteger }"
+ otherSize "{ Class: SmallInteger }"
+ dstIndex "{ Class: SmallInteger }"
+ newSize newContents|
+
+ "if aCollection is bigger than a threshhold, its faster
+ to add all and resort - question: what is a good treshhold ?"
+
+ mySize := self size.
+ otherSize := aCollection size.
+ ((mySize == 0) or:[otherSize > 5]) ifTrue:[
+ newSize := mySize + otherSize.
+ newContents := Array new:newSize.
+ newContents replaceFrom:1 to:mySize with:contentsArray startingAt:1.
+ (aCollection isKindOf:SequenceableCollection) ifTrue:[
+ "maybe we can do it in one big move"
+ newContents replaceFrom:(mySize + 1) to:newSize with:aCollection startingAt:1.
+ ] ifFalse:[
+ dstIndex := mySize + 1.
+ aCollection do:[:element |
+ newContents at:dstIndex put:element.
+ dstIndex := dstIndex + 1
+ ]
+ ].
+ firstIndex := 1.
+ lastIndex := newSize.
+ contentsArray := newContents.
+ contentsArray sort:sortBlock.
+ ^ self
+ ].
+ super addAll:aCollection
+
+ "#(7 3 9 10 99) asSortedCollection addAll:#(77 0 1 16 5)"
+!
+
+add:anObject
+ "add the argument, anObject at the proper place in the
+ receiver"
+
+ |sz index|
+
+ sz := self size.
+ sz == 0 ifTrue:[
+ super addLast:anObject
+ ] ifFalse:[
+ index := self findIndexFor:anObject.
+ self makeRoomAtIndex:index.
+ contentsArray at:index put:anObject
+ ].
+ ^ anObject
+! !
+
+!SortedCollection methodsFor:'testing'!
+
+includes:anObject
+ "return true, if the argument, anObject is in the collection.
+ (can reduce the number of compares since we are sorted)"
+
+ |index|
+
+ index := self findIndexFor:anObject.
+ ^ (index <= self size) and:[(contentsArray at:index) = anObject]
+!
+
+occurrencesOf:anObject
+ "return how many times the argument, anObject is in the collection.
+ (can reduce the number of compares since we are sorted)"
+
+ |index "{ Class: SmallInteger }"
+ mySize "{ Class: SmallInteger }"
+ tally "{ Class: SmallInteger }" |
+
+ index := self findIndexFor:anObject.
+ mySize := self size.
+ index > mySize ifTrue:[^ 0].
+ tally := 0.
+ [(index <= mySize) and:[(contentsArray at:index) = anObject]] whileTrue:[
+ tally := tally + 1.
+ index := index + 1
+ ].
+ ^ tally
+! !
+
+!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]"
+ "#($f $G $z $Y $o $H) asSortedCollectionSortedCollection"
+ "#($f $G $z $Y $o $H) asSortedCollection sortBlock:[:a : b | a asUppercase < b asUppercase]"
+! !
+
+!SortedCollection methodsFor:'enumerating'!
+
+collect: aBlock
+ | newOrderedCollection |
+ newOrderedCollection := OrderedCollection new.
+ self do: [ :element | newOrderedCollection add: (aBlock value: element) ].
+ ^newOrderedCollection
+! !
+
+!SortedCollection methodsFor:'private'!
+
+setSortBlock: aSortBlock
+ "set the sortblock without resorting - private only"
+
+ sortBlock := aSortBlock
+!
+
+findIndexFor: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."
+
+ |low "{ Class: SmallInteger}"
+ high "{ Class: SmallInteger}"
+ middle "{ Class: SmallInteger}"
+ element|
+
+ low := firstIndex.
+ high := lastIndex.
+ [low <= high] whileTrue:[
+ middle := (low + high) // 2.
+ element := super 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"
+
+! !