"{ Package: 'stx:libbasic2' }"

SequenceableCollection subclass:#SegmentedOrderedCollection

	instanceVariableNames:'segments maxSegmentSize tally'

	classVariableNames:''

	poolDictionaries:''

	category:'Collections-Sequenceable'

!

!SegmentedOrderedCollection class methodsFor:'documentation'!

documentation

"

    [author:]

        Claus Gittinger

    [see also:]

        Array OrderedCollection BTree 

"

! !

!SegmentedOrderedCollection class methodsFor:'instance creation'!

new

    "return an initialized instance"

    ^ self basicNew initialize.

! !

!SegmentedOrderedCollection methodsFor:'accessing'!

at:index

    |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

    |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

    tally == 0 ifTrue:[^ self emptyCollectionError].

    ^ segments first first

!

last

    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.

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

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

!

removeFirst

    |seg el|

    tally == 0 ifTrue:[

        ^ self emptyCollectionError

    ].

    seg := segments first.

    el := seg removeFirst.

    seg isEmpty ifTrue:[

        segments removeFirst

    ].

    tally := tally - 1.

    ^ el

!

removeFromIndex:startIndex toIndex:endIndex

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

    [true] whileTrue:[

        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.

                    ].

                    tally := tally - (endIndex - startIndex + 1).

                    ^ self.

                ].

                seg removeFromIndex:(startIndex - segStart + 1).        

                seg isEmpty ifTrue:[

                    segments removeAtIndex:segIndex.

                    nextSegIndex := segIndex.    

                ].

                removing := true.

            ].

        ] ifTrue:[

            (endIndex between:segStart and:segEnd) ifTrue:[

                seg removeFromIndex:1 toIndex:(endIndex - segStart + 1).

                seg isEmpty ifTrue:[

                    segments removeAtIndex:segIndex.

                ].

                tally := tally - (endIndex - startIndex + 1).

                ^ self.

            ] ifFalse:[

                "/ remove the whole segment

                segments removeAtIndex:segIndex.

                nextSegIndex := segIndex.

            ]

        ].

        segStart := segEnd + 1.

        segIndex := nextSegIndex.

    ].

    self halt:'should not be here'

!

removeLast

    |seg el|

    tally == 0 ifTrue:[

        ^ self emptyCollectionError

    ].

    seg := segments last.

    el := seg removeLast.

    seg isEmpty ifTrue:[

        segments removeLast

    ].

    tally := tally - 1.

    ^ el

!

splitSegmentAt:segmentIndex

    |seg rightPart|

    seg := segments at:segmentIndex.

    rightPart := OrderedCollection new:20.

    rightPart grow:10.

    rightPart replaceFrom:1 to:10 with:seg startingAt:(seg size - 9).

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

    segments add:rightPart afterIndex:segmentIndex.

! !

!SegmentedOrderedCollection methodsFor:'enumerating'!

do:aBlock

    segments do:[:seg |

        seg do:aBlock

    ].

!

keysAndValuesDo:aBlock

    |idx|

    idx := 1.

    segments do:[:seg |

        seg do:[:each |

            aBlock value:idx value:each.

            idx := idx + 1.

        ]

    ].

! !

!SegmentedOrderedCollection methodsFor:'initialization'!

initialize

    "Invoked when a new instance is created."

    segments := OrderedCollection with:(OrderedCollection new:10).

    maxSegmentSize := 200.

    tally := 0.

! !

!SegmentedOrderedCollection methodsFor:'queries'!

size

    ^ tally

! !

!SegmentedOrderedCollection class methodsFor:'documentation'!

version

!

version_CVS

! !