"{ Package: 'stx:libbasic2' }"

"{ NameSpace: Smalltalk }"

SequenceableCollection subclass:#SegmentedOrderedCollection
	instanceVariableNames:'segments maxSegmentSize tally'
	classVariableNames:''
	poolDictionaries:''
	category:'Collections-Sequenceable'
!

!SegmentedOrderedCollection class methodsFor:'documentation'!

documentation
"
    SegmentedOrderedCollections are intended as a replacement for huge OrderedCollections or Lists.
    They keep their elements in chunks (segments), allowing for fast 
    adding/removing at either end AND relatively fast add/remove inside the collection.
    For huge collections, the performance is much better when adding/removing inner elements.

    However, notice: when only removing at either end only, an OrderedCollection is faster.

    The break-even in performance depends on the number of elements and the usage pattern.
    Consider it with (say) > 10000 elements and many adds/removes from the inside.

    This class was added to support huge selection-in-lists (>100k elements), which are
    constantly changing by adding/removing elements at arbitrary positions.

    Possibly unfinished (may need optimized search and replace).

    [author:]
        Claus Gittinger

    [see also:]
        Array OrderedCollection BTree 
"
! !

!SegmentedOrderedCollection class methodsFor:'instance creation'!

new
    "return an initialized instance"

    ^ self basicNew initialize.
!

new:size
    "return an initialized instance with space for size elements.
     However, be aware that the logical size is 0"

    ^ self basicNew initialize.
! !

!SegmentedOrderedCollection methodsFor:'accessing'!

at:index
    "return the element at index, anInteger"

    |segStart segEnd|

    (index between:1 and:tally) ifFalse:[
        ^ self indexNotIntegerOrOutOfBounds:index
    ].
    segStart := 1.
    segments do:[:seg |
        segEnd := segStart + (seg size - 1).
        (index between:segStart and:segEnd) ifTrue:[
            ^ seg at:(index - segStart + 1).
        ].
        segStart := segEnd + 1.
    ].
    self error:'oops - should not be here'
!

at:index put:newElement
    "set the element at index, to be anInteger.
     Return anObject (sigh)."

    |segStart segEnd|

    (index between:1 and:tally) ifFalse:[
        ^ self indexNotIntegerOrOutOfBounds:index
    ].

    segStart := 1.
    segments do:[:seg |
        segEnd := segStart + (seg size - 1).
        (index between:segStart and:segEnd) ifTrue:[
            ^ seg at:(index - segStart + 1) put:newElement.
        ].
        segStart := segEnd + 1.
    ].
    self error:'oops - should not be here'
!

first
    "return the first element"

    tally == 0 ifTrue:[^ self emptyCollectionError].
    ^ segments first first
!

last
    "return the last element"

    tally == 0 ifTrue:[^ self emptyCollectionError].
    ^ segments last last
! !

!SegmentedOrderedCollection methodsFor:'adding & removing'!

add:anObject
    "add anObject to the end.
     Returns the object (sigh)"

    |seg|

    (seg := segments last) size >= maxSegmentSize ifTrue:[
        self splitSegmentAt:(segments size).
        seg := segments last.
    ].
    seg add:anObject.
    tally := tally + 1.
    self changed:#insert: with:tally.
    ^ anObject.
!

add:anObject beforeIndex:index
    "insert the first argument, anObject into the collection before slot index.
     Return the receiver (sigh - ST-80 compatibility).

     Notice, that this is modifies the receiver NOT a copy."

    |prevSeg segStart|

    index == (tally+1) ifTrue:[
        ^ self add:anObject
    ].
    segStart := 1.
    segments do:[:seg |
        |segEnd|

        segEnd := segStart + (seg size - 1).
        (index between:segStart and:segEnd) ifTrue:[
            index == segStart ifTrue:[
                prevSeg notNil ifTrue:[
                    prevSeg size < seg size ifTrue:[
                        prevSeg add:anObject.
                        tally := tally + 1.
                        ^ anObject
                    ].
                ].
            ].
            seg add:anObject beforeIndex:(index - segStart + 1).
            tally := tally + 1.
            self changed:#insert: with:index.
            ^ anObject
        ].
        segStart := segEnd + 1.
        prevSeg := seg.
    ].
    self error:'oops - should not be here'
!

addFirst:anObject
    "add anObject to the beginning (insert as new first element)."

    |seg|

    (seg := segments first) size >= maxSegmentSize ifTrue:[
        self splitSegmentAt:1.
        seg := segments first.
    ].
    seg addFirst:anObject.
    tally := tally + 1.
    self changed:#insert: with:1
!

removeAll
    "remove all elements from the receiver. Returns the receiver."

    |prevSize|

    prevSize := tally.
    segments := OrderedCollection with:(OrderedCollection new).
    tally := 0.
    self changed:#removeFrom: with:(Array with:1 with:prevSize)

    
    "Modified: / 30-07-2013 / 19:31:05 / cg"
!

removeFirst
    "remove the first element from the collection; return the element.
     If there is no element in the receiver collection, raise an error."

    ^ self removeFirstIfAbsent:[self emptyCollectionError]
!

removeFirstIfAbsent:exceptionBlock
    "remove the first element from the collection; return the element.
     If there is no element in the receiver collection, return the value from
     exceptionBlock.
     Destructive: modifies the receiver"

    |seg el|

    tally == 0 ifTrue:[
        ^ exceptionBlock value
    ].
    seg := segments first.
    el := seg removeFirst.
    seg isEmpty ifTrue:[
        tally == 1 ifTrue:[
            segments := OrderedCollection with:(OrderedCollection new).
        ] ifFalse:[
            segments removeFirst.
        ]    
    ].
    tally := tally - 1.
    self changed:#remove: with:1.
    ^ el
!

removeFromIndex:startIndex toIndex:endIndex
    "remove the elements stored under startIndex up to and including
     the elements under stopIndex.
     Return the receiver.
     Returning the receiver here is a historic leftover - it may change.
     Please use yourself in a cascade, if you need the receiver's value
     when using this method."

    |segStart segEnd removing segIndex nextSegIndex seg|

    (startIndex between:1 and:tally) ifFalse:[
        ^ self indexNotIntegerOrOutOfBounds:startIndex
    ].
    (endIndex between:1 and:tally) ifFalse:[
        ^ self indexNotIntegerOrOutOfBounds:endIndex
    ].

    segStart := 1.
    segIndex := 1.
    removing := false.
    [
        seg := segments at:segIndex.
        nextSegIndex := segIndex + 1.

        segEnd := segStart + (seg size - 1).

        removing ifFalse:[
            "still searching for the segment"
            (startIndex between:segStart and:segEnd) ifTrue:[
                (endIndex between:segStart and:segEnd) ifTrue:[
                    seg removeFromIndex:(startIndex - segStart + 1) toIndex:(endIndex - segStart + 1).
                    seg isEmpty ifTrue:[
                        segments removeAtIndex:segIndex.
                        segments isEmpty ifTrue:[
                            segments := OrderedCollection with:(OrderedCollection new).
                        ]    
                    ].
                    tally := tally - (endIndex - startIndex + 1).
                    self changed:#removeFrom: with:(Array with:startIndex with:endIndex).
                    ^ self.
                ].
                seg removeFromIndex:(startIndex - segStart + 1).        
                seg isEmpty ifTrue:[
                    segments removeAtIndex:segIndex.
                    segments isEmpty ifTrue:[
                        segments := OrderedCollection with:(OrderedCollection new).
                    ].    
                    nextSegIndex := segIndex.    
                ].
                removing := true.
            ].
        ] ifTrue:[
            (endIndex between:segStart and:segEnd) ifTrue:[
                seg removeFromIndex:1 toIndex:(endIndex - segStart + 1).
                seg isEmpty ifTrue:[
                    segments removeAtIndex:segIndex.
                    segments isEmpty ifTrue:[
                        segments := OrderedCollection with:(OrderedCollection new).
                    ]    
                ].
                tally := tally - (endIndex - startIndex + 1).
                self changed:#removeFrom: with:(Array with:startIndex with:endIndex).
                ^ self.
            ] ifFalse:[
                "/ remove the whole segment
                segments removeAtIndex:segIndex.
                segments isEmpty ifTrue:[
                    segments := OrderedCollection with:(OrderedCollection new).
                ].    
                nextSegIndex := segIndex.
            ]
        ].
        segStart := segEnd + 1.
        segIndex := nextSegIndex.
    ] loop.
!

removeLast
    "remove the last element from the collection; return the element"

    |seg el|

    tally == 0 ifTrue:[
        ^ self emptyCollectionError
    ].
    seg := segments last.
    el := seg removeLast.
    seg isEmpty ifTrue:[
        tally == 1 ifTrue:[
            segments := OrderedCollection with:(OrderedCollection new).
        ] ifFalse:[
            segments removeLast.
        ]    
    ].
    tally := tally - 1.
    self changed:#remove: with:(1 + tally).
    ^ el
! !

!SegmentedOrderedCollection methodsFor:'enumerating'!

do:aBlock
    "evaluate the argument, aBlock for every element in the collection."

    segments do:[:seg |
        seg do:aBlock
    ].
!

keysAndValuesDo:aBlock
    "evaluate the argument, aBlock for every element in the collection,
     passing both index and element as arguments."

    |idx|

    idx := 1.
    segments do:[:seg |
        seg do:[:each |
            aBlock value:idx value:each.
            idx := idx + 1.
        ]
    ].
! !

!SegmentedOrderedCollection methodsFor:'grow & shrink'!

grow:newSize
    "adjust the logical size to newSize"

    |numExtraSegments segStart segEnd segIndex seg|

    newSize == 0 ifTrue:[
        segments := OrderedCollection with:(OrderedCollection new).
        tally := 0.
        ^ self
    ].

    newSize < tally ifTrue:[
        "/ shrinking
        segStart := 1.
        segIndex := 1.
        [
            seg := segments at:segIndex.
            segEnd := segStart + (seg size - 1).
            (newSize between:segStart and:segEnd) ifTrue:[
                (segments at:segIndex) removeFromIndex:(newSize - segStart + 1 + 1).
                segments removeFromIndex:segIndex+1.
                tally := newSize.
                ^ self
            ].
            segStart := segEnd + 1.
            segIndex := segIndex + 1.
        ] loop.
        "/ not reached
    ].

    "/ growing
    numExtraSegments := (newSize - tally) // maxSegmentSize + 1.
    numExtraSegments timesRepeat:[
        segments add:((OrderedCollection new:maxSegmentSize) grow:maxSegmentSize)
    ].
    tally := newSize
! !

!SegmentedOrderedCollection methodsFor:'initialization'!

initialize
    "Invoked when a new instance is created."

    segments := OrderedCollection with:(OrderedCollection new).
    maxSegmentSize := 200.
    tally := 0.

    "Modified: / 30-07-2013 / 19:31:12 / cg"
! !

!SegmentedOrderedCollection methodsFor:'private'!

splitSegmentAt:segmentIndex
    |seg segSize rightPart|

    seg := segments at:segmentIndex.
    segSize := seg size.
    
    rightPart := OrderedCollection new:20.
    rightPart grow:10.
    rightPart replaceFrom:1 to:10 with:seg startingAt:(segSize - 9).

    seg removeFromIndex:(segSize - 9) toIndex:segSize.

    segments add:rightPart afterIndex:segmentIndex.
! !

!SegmentedOrderedCollection methodsFor:'queries'!

isFixedSize
    "return true if the receiver cannot grow"

    ^ false
!

size
    "return the number of elements in the collection"

    ^ tally
! !

!SegmentedOrderedCollection class methodsFor:'documentation'!

version
    ^ '$Header$'
!

version_CVS
    ^ '$Header$'
! !