"

 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,

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.

The default sortBlock for SortedCollections is the first one.

'!

!SortedCollection class methodsFor:'initialization'!

initialize

    DefaultSortBlock := [:a :b | a < b ]

    "SortedCollection initialize"

! !

!SortedCollection class methodsFor:'instance creation'!

new

    "return a new sortedCollection, the sorting is done using

     a compare for a > b, in ascending order"

    ^ super new setSortBlock:DefaultSortBlock

!

new:size

    "return a new sortedCollection with preallocated size.

     The sorting is done using a compare for a > b, in ascending order"

    ^ (super new:size) setSortBlock:DefaultSortBlock

!

sortBlock:aBlock

    "set the sort-block"

    ^ super new setSortBlock:aBlock

! !

!SortedCollection methodsFor:'adding & removing'!

addFirst:anObject

    "catch this - its not allowed for sortedCollections"

    self shouldNotImplement

!

addLast:anObject

    "catch this - its not allowed for sortedCollections"

    self shouldNotImplement

!

at:index put:anObject

    "catch this - its not allowed for sortedCollections"

    self shouldNotImplement

!

add:newObject after:oldObject

    "catch this - its not allowed for sortedCollections"

    self shouldNotImplement

!

add:newObject before:oldObject

    "catch this - its not allowed for sortedCollections"

    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. Returns the argument, anObject."

    |index|

    lastIndex < firstIndex "i.e. self size == 0" ifTrue:[

        super add:anObject

    ] ifFalse:[

        index := self findIndexFor:anObject. 

        self makeRoomAtIndex:index.

        contentsArray at:index put:anObject

    ].

    ^ anObject

! !

!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:'testing'!

includes:anObject

    "return true, if the argument, anObject is in the collection.

     Redefined, since due to beeing sorted, the inclusion check can

     be done with log-n compares i.e. much faster."

    |index "{ Class: SmallInteger }"|

    index := self findIndexFor:anObject.

    ((index < firstIndex) or:[index > lastIndex]) ifTrue:[^ false].

    ^ (contentsArray at:index) = anObject

    "#(7 3 9 10 99) asSortedCollection includes:50"

    "#(7 3 9 10 99) asSortedCollection includes:10"

!

occurrencesOf:anObject

    "return how many times the argument, anObject is in the collection.

     Redefined, since due to beeing sorted, the range of checked objects

     can be limited i.e. it can be done much faster."

    |index      "{ Class: SmallInteger }"

     tally      "{ Class: SmallInteger }" |

    index := self findIndexFor:anObject.

    ((index < firstIndex) or:[index > lastIndex]) ifTrue:[^ 0].

    tally := 0.

    [(index <= lastIndex) and:[(contentsArray at:index) = anObject]] whileTrue:[

        tally := tally + 1.

        index := index + 1

    ].

    ^ tally

    "#(7 3 9 10 99) asSortedCollection occurrencesOf:50"

    "#(7 3 9 10 99) asSortedCollection occurrencesOf:10"

    "#(7 10 3 10 9 10 10 99) asSortedCollection occurrencesOf:10"

! !

!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

!

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.

     The returned index is a physical one, for accessing contentsArray."

    |low    "{ Class: SmallInteger}"

     high   "{ Class: SmallInteger}"

     middle "{ Class: SmallInteger}"

     element|

    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 findIndexFor:50"

! !