" Smalltalk/SortedCollection.st					-*- Smalltalk -*- "

SortedCollection : OrderedCollection ( sortBlock )

SortedCollection new: size
[
    self := super new: size.
    sortBlock := nil.
]

SortedCollection sortBlock: binaryBlock
[
    " Make the binaryBlock define the ordering relation for the
      elements of the receiver. "
    sortBlock := binaryBlock.
    self notEmpty ifTrue: [self reSort].
]

SortedCollection addFirst: anObject		[ ^self shouldNotImplement ]
SortedCollection addLast: anObject		[ ^self shouldNotImplement ]
SortedCollection insert: anObject before: index	[ ^self shouldNotImplement ]

SortedCollection add: newObject
[
    ^super insert: newObject before: (self indexForInserting: newObject)
]

SortedCollection indexForInserting: newObject
[
    | index low high |
    low := firstIndex.
    high := lastIndex - 1.
    sortBlock isNil
	ifTrue:
	  [ [low > high]
	        whileFalse:
	          [ index := high + low // 2.
                    (array at: index) <= newObject
                        ifTrue: [low := index + 1]
                        ifFalse: [high := index - 1] ] ]
	ifFalse:
	  [ [ low > high ]
	        whileFalse:
	          [ index := high + low // 2.
                    (sortBlock value: (array at: index) value: newObject)
                        ifTrue: [low := index + 1]
                        ifFalse: [high := index - 1] ] ].
    ^low
]

" ---------------------------------------------------------------- "

Collection asSortedCollection: binarySortBlock
[
    " Answer a SortedCollection whose elements are the elements of the
      receiver.  The sort order is defined by binarySortBlock. "
    ^(SortedCollection new: self size)
        sortBlock: binarySortBlock;
        addAll: self;
        yourself
]

Collection asSortedCollection
[
    ^self asSortedCollection: nil
]