"

 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.

"

"{ Package: 'stx:libbasic' }"

OrderedCollection subclass:#SortedCollection

	instanceVariableNames:'sortBlock'

	classVariableNames:'DefaultSortBlock'

	poolDictionaries:''

	category:'Collections-Sequenceable'

!

!SortedCollection class methodsFor:'documentation'!

copyright

"

 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.

"

!

documentation

"

    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,

    should return true if the element given as first arg has to come before the

    element given as second arg.

    Equal elements may occur multiple times.

    SortedCollection uses quickSort to resort and a binary search when adding/removing elements.

    Because insertion/removal may require that remaining elements have to

    be shifted within the container, adding many individual elements may be done faster

    by creating a completely new collection from the unsorted elements.

    (see examples)

    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.

    Compatibility Warning:

        VW seems to use a default sortBlock which compares a<=b, wheras ST/X uses a<b.

        That means, that elements which are compared MUST understand #< in ST/X

        while the minumum protocol is #<= in VW.

        This may be changed in a future release of ST/X

        (it is not yet, to not confuse existing applications ...

         ... be aware, that the sortBlock has an effect on a few algorithms

         found here; especially #indexForInserting is critical.)

    [author:]

        Claus Gittinger

"

!

examples

"

    when many elements are to be added, it may be better to add them

    all en-bloeque instead of individually.

    The reason is that for each individual #add:, the contents has to be

    shifted, to create an empty slot for the new element.

    timing example:

        |o rnd|

        o := SortedCollection new.

        rnd := Random new.

        10000 timesRepeat:[

            o add:rnd next.

        ]

    takes 1365 ms on a P5 (admitted: this is a fast machine ;-)

    Times are a'changing: 

        Just came around 2005: on my 1.5Ghz laptop, this now takes 260ms...

        an another comment 2008: on a 1.8Ghz laptop, it takes now 105ms...

    In contrast:

        |o rnd|

        o := OrderedCollection new.

        rnd := Random new.

        10000 timesRepeat:[

            o add:rnd next.

        ].

        o := o asSortedCollection

    takes 383 ms on the same machine.

        2005: on my 1.5Ghz laptop, this now takes 100ms

        2008: on a 1.8Ghz laptop, this now takes 47ms

    If you already have a big sortedCollection at hand, adding multiple

    items may be better done with #addAll:, which resorts all elements, if

    the number of added items is more than some threshold number.

    However, the break-even point where bulk-adding is faster depends

    on the machine ... (and ST/X version ;-).

  adding elements in order:

    |c|

    Time millisecondsToRun:[

        10 timesRepeat:[

            |c|

            c := SortedCollection new.

            (1 to:100000) do:[:e | c add:e].

        ]

    ].    

    (5.4.1: 2031 2187)

    (5.4.3: 484 516)

    |c|

    c := SortedCollection new.

    (1 to:100000) do:[:e | c add:e].

    self assert:(c asBag = (1 to:100000) asBag).

  adding elements in reverse order:

    Time millisecondsToRun:[

        10 timesRepeat:[

            |c|

            c := SortedCollection new.

            (1 to:100000) reverseDo:[:e | c add:e].

        ]

    ].        

    (5.4.1: 201969)

    (5.4.3: 1609 1766)

    |c|

    c := SortedCollection new.

    (1 to:100000) reverseDo:[:e | c add:e].

    self assert:(c asBag = (1 to:100000) asBag).

  adding elements in random order:

    |toAdd|

    toAdd := (1 to:100000) asOrderedCollection randomShuffle.

    Time millisecondsToRun:[

        10 timesRepeat:[

            |c|

            c := SortedCollection new.

            toAdd do:[:e | c add:e].

        ]

    ].

    (5.4.1: 108484)

    (5.4.3: 75734)

    |c|

    c := SortedCollection new.

    (1 to:100000) asOrderedCollection randomShuffle do:[:e | c add:e].

    self assert:(c asBag = (1 to:100000) asBag).

"

! !

!SortedCollection class methodsFor:'initialization'!

initialize

    "setup the default sortBlock.

    "/ only do this once at early startup

    DefaultSortBlock isNil ifTrue:[

    ]

    "

     SortedCollection initialize

    "

    "Modified: 12.4.1996 / 12:29:27 / cg"

! !

!SortedCollection class methodsFor:'instance creation'!

forStrings

    "this is supposed to return a sortedCollection, which sorts using

     the current locales collating sequence. For now, simply use a

     normal string compare.

     This will change"

    ^ self new

    "Modified: 13.9.1997 / 10:18:58 / cg"

    "Created: 13.9.1997 / 10:41:54 / cg"

!

forStrings:size

    "this is supposed to return a sortedCollection, which sorts using

     the current locales collating sequence. For now, simply use a

     normal string compare.

     This will change"

    ^ self new:size

    "Modified: 13.9.1997 / 10:18:58 / cg"

!

new

    "return a new sortedCollection, the sorting is done using

     a compare for a < b, in ascending order"

    ^ super new setSortBlock:DefaultSortBlock

    "Modified: 12.4.1996 / 12:28:18 / cg"

!

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

    "Modified: 12.4.1996 / 12:28:22 / cg"

!

sortBlock:aBlock

    "return a new sortedCollection, whe the sort order is defined

     by aBlock.

     This must be a two-argument block which returns true if its arg1 has to come before

     its arg2 in the collection."

    ^ super new setSortBlock:aBlock

    "default:

     |s|

     s := SortedCollection new.

     s add:15; add:99; add:3; add:-29; add:17; add:-6.

     Transcript showCR:s

    "

    "sorting by absolute values:

     |s|

     s := SortedCollection sortBlock:[:a :b | a abs < b abs].

     s add:15; add:99; add:3; add:29; add:17; add:-6.

     Transcript showCR:s

    "

    "default again:

     |s|

     s := SortedCollection new.

     s add:'foo'; add:'Bar'; add:'baz'; add:'hello'; add:'world'; add:'Wow'.

     Transcript showCR:s

    "

    "sorting strings caseless:

     |s|

     s := SortedCollection sortBlock:[:a :b | a asLowercase < b asLowercase].

     s add:'foo'; add:'Bar'; add:'baz'; add:'hello'; add:'world'; add:'Wow'.

     Transcript showCR:s

    "

    "Modified: 12.4.1996 / 12:26:28 / cg"

!

withAll:aCollection sortBlock:aBlock

    "initialize from aCollection and set the sort-block"

    ^ (self sortBlock:aBlock) addAll:aCollection; yourself

    "

     SortedCollection withAll:#(1 2 3 4 5 6 7 8 9 0)

		      sortBlock:[:a :b | a > b]

    "

    "default:

     |s|

     s := SortedCollection withAll:#(15 99 3 29 17 -6).

     Transcript showCR:s

    "

    "sorting by absolute values:

     |s|

     s := SortedCollection withAll:#(15 99 3 29 17 -6) sortBlock:[:a :b | a abs < b abs].

     Transcript showCR:s

    "

    "default again:

     |s|

     s := SortedCollection withAll:#('foo' 'Bar' 'baz' 'hello' 'world' 'Wow').

     Transcript showCR:s

    "

    "sorting strings caseless:

     |s|

     s := SortedCollection withAll:#('foo' 'Bar' 'baz' 'hello' 'world' 'Wow') sortBlock:[:a :b | a asLowercase < b asLowercase].

     Transcript showCR:s

    "

    "Modified: 12.4.1996 / 12:28:09 / cg"

! !

!SortedCollection class methodsFor:'Compatibility-Dolphin'!

sortBlock:aBlock withAll:aCollection

    ^ self withAll:aCollection sortBlock:aBlock

! !

!SortedCollection class methodsFor:'helpers'!

binarySearch:aSortedArray for:anObject

    "search for an existing element; return true if found.

     by checking if the element at the returned index is the one we look for.

     Uses a binarySearch since we can depend on the elements being on sorted order.

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

     This is only to be used for arrays which are known to be sorted."

    |idx|

    idx := self

        binarySearch:aSortedArray 

        forIndexOf:anObject.

    ^ idx <= aSortedArray size

    and:[ (aSortedArray at:idx) = anObject ].

    "

     SortedCollection

        binarySearch:#(1 2 3 4 7 99 1313 981989 898989898) 

        for:898989898    

    "

!

binarySearch:aSortedArray forIndexOf: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.

     Uses a binarySearch since we can depend on the elements being on sorted order.

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

     This is only to be used for arrays which are known to be sorted."

    ^ self

        binarySearch:aSortedArray 

        from:1 to:(aSortedArray size)

        forIndexOf:anObject 

        usingSortBlock:[:a :b | a < b ]

    "

     SortedCollection

        binarySearch:#(1 2 3 4 7 99 1313 981989 898989898) 

        from:1 to:9

        forIndexOf:99

        usingSortBlock:[:a :b | a < b ]

    "

    "Modified: 12.4.1996 / 13:22:03 / cg"

!

binarySearch:aSortedArray from:firstIndex to:lastIndex forIndexOf:anObject usingSortBlock:sortBlock

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

     Uses a binarySearch since we can depend on the elements being on sorted order.

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

     This is only to be used for arrays which are known to be sorted."

    |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] whileFalse:[

        middle := (low + high) // 2.

        element := aSortedArray at:middle.

        (sortBlock value:element value:anObject) ifTrue:[

            "middleelement is smaller than object"

            low := middle + 1

        ] ifFalse:[

            high := middle - 1

        ]

    ].

    ^ low

    "

     SortedCollection

        binarySearch:#(1 2 3 4 7 99 1313 981989 898989898) 

        from:1 to:9

        forIndexOf:99

        usingSortBlock:[:a :b | a < b ]

    "

    "Modified: 12.4.1996 / 13:22:03 / cg"

! !

!SortedCollection methodsFor:'accessing'!

largest:n

    "return the n largest elements"

    sortBlock == DefaultSortBlock ifTrue:[

        ^ self copyFrom:(self size-n+1)

    ].

    ^ super largest:n

    "

     #(10 35 20 45 30 5) asSortedCollection largest:3 

    "

!

max

    "Return the largest element."

    sortBlock == DefaultSortBlock ifTrue:[

        ^ self last

    ].

    ^ super max

    "

     #(10 35 20 45 30 5) asSortedCollection max 

    "

!

median

    "Return the middle element, or as close as we can get."

    ^ self at:(self size + 1 // 2)

    "

     #(10 35 20 45 30 5) asSortedCollection median

     #(10 35 20 45 30 5) median

    "

!

min

    "Return the smallest element."

    sortBlock == DefaultSortBlock ifTrue:[

        ^ self first

    ].

    ^ super min

    "

     #(10 35 20 45 30 5) asSortedCollection min

    "

! !

!SortedCollection methodsFor:'adding & removing'!

add:anObject

    "add the argument, anObject at the proper place in the receiver. 

     Returns the argument, anObject (sigh)."

    |index lastElement|

    "/

    "/ cg: the original code was simply:

    "/

    "/  index := self indexForInserting:anObject.

    "/  index := self makeRoomAtIndex:index.

    "/  contentsArray basicAt:index put:anObject.

    "/

    "/  which was nice and simple to understand.

    "/ However, the code below is 5 times faster, if elements are added in an already ordered fashion,

    "/ which often happens.

    "/ so we allow the code to be a bit more complicated...

    (lastIndex < firstIndex "i.e. self size == 0"