"
 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"

! !