"

 This class is not covered by or part of the ST/X licence.

 COPYRIGHT.

 The above file is a Manchester Goodie protected by copyright.

 These conditions are imposed on the whole Goodie, and on any significant

 part of it which is separately transmitted or stored:

	* You must ensure that every copy includes this notice, and that

	  source and author(s) of the material are acknowledged.

	* These conditions must be imposed on anyone who receives a copy.

	* The material shall not be used for commercial gain without the prior

	  written consent of the author(s).

 Further information on the copyright conditions may be obtained by

 sending electronic mail:

	To: goodies-lib@cs.man.ac.uk

	Subject: copyright

 or by writing to The Smalltalk Goodies Library Manager, Dept of

 Computer Science, The University, Manchester M13 9PL, UK

 (C) Copyright 1993 University of Manchester

 For more information about the Manchester Goodies Library (from which 

 this file was distributed) send e-mail:

	To: goodies-lib@cs.man.ac.uk

	Subject: help 

"

"{ Package: 'stx:libbasic2' }"

SequenceableCollection subclass:#RunArray

	instanceVariableNames:'contentsArray'

	classVariableNames:''

	poolDictionaries:''

	category:'Collections-Sequenceable'

!

RunArray comment:'This implements an ordered collection which uses runs to minimise the amount

 of data that it holds. Basically it should be used if you know that an ordered

 collections is giong to contain a lot of runs of eactly the same data. Implemented

 to allow simultation playback, since the ordered collctions which that generates

 are so big that the complier falls over, though most of it is extremely repetetive.

 This should be totally abstracted. The user should not be a ble to see the difference

 between an ordered collection and a ComrpessedOrderedCollection.  This has a

 lot in common with RunArray, and the two should probably share implementation.

 but I could not do some of the things I wanted with the RunArray code, so this

 is all done on its own.

	Some of this could be made faster by adding a cache of the start and finish

 indices of each run, but since I envisage that most additions etc. will be to

 and from the end those are not included. In addition I have implemented the

 bare essentials of this for what I need it for - i.e. add to the end and take

!RunArray class methodsFor:'documentation'!

copyright

"

 This class is not covered by or part of the ST/X licence.

 COPYRIGHT.

 The above file is a Manchester Goodie protected by copyright.

 These conditions are imposed on the whole Goodie, and on any significant

 part of it which is separately transmitted or stored:

	* You must ensure that every copy includes this notice, and that

	  source and author(s) of the material are acknowledged.

	* These conditions must be imposed on anyone who receives a copy.

	* The material shall not be used for commercial gain without the prior

	  written consent of the author(s).

 Further information on the copyright conditions may be obtained by

 sending electronic mail:

	To: goodies-lib@cs.man.ac.uk

	Subject: copyright

 or by writing to The Smalltalk Goodies Library Manager, Dept of

 Computer Science, The University, Manchester M13 9PL, UK

 (C) Copyright 1993 University of Manchester

 For more information about the Manchester Goodies Library (from which 

 this file was distributed) send e-mail:

	To: goodies-lib@cs.man.ac.uk

	Subject: help 

"

!

documentation

"

    This implements an array which uses runs to minimise the amount

    of data that it physically holds. 

    A run consists of a count/object pair, which (when the collection

    is accessed), is treated as if the object was contained count-times 

    in the runArray.

    Basically it can be used if you know that your collection is 

    going to contain a lot of runs of exactly the same data. 

    RunArrays are used by the Text class to keep character attributes

    (which we expect to remain constant for longer character ranges).

    [notice:]

        there is ONLY a space saving if there are really runs 

        (i.e. multiple elements which compare same).

        The break-even is when runs have an average size of 2 elements,

        if average runs are shorter, other collections (i.e. Array or

        OrderedCollection) are more compact.

        Also note, that indexed access (i.e. #at: / #at:put:) may be

        very inefficient (as opposed to enumeration, which is reasonably

        fast).

        The reason is that for indexed access the runs have to be walked.

        When storing into a runArray, runs may have to be splitted or merged,

        depending on where the store is done (within a run).

        This may lead to a resize operation.

        You have been warned.

    [instance variables:]

        contentsArray    <Array>         contains the runs, consisting of

                                         alternating length/value entries.

    [implementation note:]

        structure-wise, it would have been more intuitive, to keep

        instances of Run objects (as done in CompressedOrderedCollection)

        instead of alternating length/values in the `runs' collection.

        However, doing this means that lots of additional memory is required,

        since for every run, another object (consisting of 12bytes header)

        would be needed.

        Here, we choose the more space efficient way - after all, space saving

        is the only reason this class was built for.

    [author:]

        Claus Gittinger

    [see also:]

        Array OrderedCollection CompressedOrderedCollection

"

!

examples

"

  this eats up a lot of memory ...

  ... but its relatively fast:

                                                                        [exBegin]

    |coll|

    coll := OrderedCollection new.

    Transcript showCR:(    

        Time millisecondsToRun:[

            100000 timesRepeat:[coll add:'hello'].

            100000 timesRepeat:[coll add:'world'].

        ]

    ).

    coll inspect.

                                                                        [exEnd]

  this is very space efficient ...

  ... (and even slightly faster):

                                                                        [exBegin]

    |coll|

    coll := RunArray new.

    Transcript showCR:(    

        Time millisecondsToRun:[

            100000 timesRepeat:[coll add:'hello'].

            100000 timesRepeat:[coll add:'world'].

        ]

    ).

    coll inspect.

                                                                        [exEnd]

  this is very space efficient ...

  ... AND much faster:

                                                                        [exBegin]

    |coll|

    coll := RunArray new.

    Transcript showCR:(    

        Time millisecondsToRun:[

            coll add:'hello' withOccurrences:100000.

            coll add:'world' withOccurrences:100000.

        ]

    ).

    coll inspect.

                                                                        [exEnd]

  single-element runs;

  this is very space INEFFICIENT (requires twice as much) ...

  ... and MUCH slower:

                                                                        [exBegin]

    |coll|

    coll := RunArray new.

    Transcript showCR:(    

        Time millisecondsToRun:[

            1 to:1000 do:[:i | coll add:i].

        ]

    ).

                                                                        [exEnd]

  compare to:

                                                                        [exBegin]

    |coll|

    coll := OrderedCollection new.

    Transcript showCR:(    

        Time millisecondsToRun:[

            1 to:1000 do:[:i | coll add:i].

        ]

    ).

                                                                        [exEnd]

"

! !

!RunArray class methodsFor:'instance creation'!

from:aSequencableCollection

    "return a new runArray, containing the elements from aSequencableCollection"

    ^ self basicNew setElementsFrom:aSequencableCollection

    "

     RunArray from:#(1 2 3 3 3 4 5 5 6 6 6 6 6 6)

    "

    "Created: / 7.4.1998 / 09:12:45 / cg"

    "Modified: / 7.4.1998 / 09:15:53 / cg"

!

new:count

    "return a new runArray, containing count elements - all nil"

    ^ self basicNew setElement:nil occurrences:count

    "Modified: / 30.10.1997 / 14:36:05 / cg"

!

new:count withAll:anObject

    "create a new runArray with count elements, all being anObject"

    ^ self basicNew setElement:anObject occurrences:count

    "

     RunArray new:100 withAll:#hello

    "

    "Modified: / 30.10.1997 / 14:36:38 / cg"

!

runs:runs values:values

    "return a new runArray, containing elements defined by pairs from

     runs and values"

    ^ self basicNew setElementsFromRuns:runs values:values

    "

     RunArray runs:#(2 3 4) values:#($a $b $c)

    "

! !

!RunArray methodsFor:'accessing'!

at:index 

    "Answer the element at index. 

     at: is used by a knowledgeable client to access an existing element 

     This is a pretty dumb thing to do to a runArray and it is 

     not at all efficient (think of that as a discouragement)."

    |position "{ Class: SmallInteger }"

     nRuns    "{ Class: SmallInteger }"|

    (index > 0) ifTrue:[

        position := 1.

        nRuns := contentsArray size.

        1 to:nRuns by:2 do:[:runIndex |

            |runLen|

            runLen := contentsArray at:runIndex.

            index >= position ifTrue:[

                index < (position + runLen) ifTrue:[

                    ^ contentsArray at:(runIndex + 1)

                ].

            ].

            position := position + runLen

        ]

    ].

    ^ self subscriptBoundsError:index

    "

     |c|

     c := RunArray new.

     c add:1; add:1; add:1; add:2; add:2; add:3; add:3; add:4; add:5.

     c at:1. 

     c at:2. 

     c at:3. 

     c at:4.  

     c at:5. 

     c at:6. 

     c at:7. 

     c at:8.  

     c at:9.  

     c at:10.  

    "

    "Modified: 18.5.1996 / 14:54:52 / cg"

!

at:index put:anObject 

    "Put anObject at element index anInteger.      

     at:put: can not be used to append, front or back, to a runArray.      

     It is used by a knowledgeable client to replace an element. 

     This is a pretty dumb thing to do to a runArray and it is 

     very inefficient, since we have to check if runs are to be merged or

     splitted."

    |runSz runIndex runOffset len l1 l2 prevIdx nextIdx

     val newRuns prevLen prevVal nextLen nextVal idx|

    runSz := contentsArray size.

    runIndex := nil.

    (index > 0) ifTrue:[

        runOffset := 1.

        idx := 1.

        [runIndex isNil and:[idx < runSz]] whileTrue:[

            len := contentsArray at:idx.

            nextIdx := runOffset + len.

            index >= runOffset ifTrue:[

                index < nextIdx ifTrue:[

                    runIndex := idx.

                    nextIdx := runOffset. "/ dont advance

                ].

            ].

            runOffset := nextIdx.

            idx := idx + 2.

        ]

    ].

    runIndex isNil ifTrue:[

        ^ self subscriptBoundsError:index

    ].

    val := contentsArray at:(runIndex + 1).

    "/ easiest: value there is the same ...

    val = anObject ifTrue:[

        ^ anObject

    ].

    "/ if the length is 1, this is an island ...

    "/ ... which is either easy, or requires a merge.

    len := contentsArray at:runIndex.

    len = 1 ifTrue:[

        "/ check if it can be merged into the next or previous run

        runIndex > 1 ifTrue:[

            prevIdx := runIndex - 2.

            prevVal := contentsArray at:(prevIdx + 1).

            prevVal = anObject ifTrue:[

                "/ can merge it into previous

                prevLen := contentsArray at:prevIdx.

                "/ check if merge into next is also possible (filling an island)

                runIndex < (runSz - 1) ifTrue:[

                    nextIdx := runIndex + 2.

                    nextVal := contentsArray at:(nextIdx + 1).

                    nextVal = anObject ifTrue:[

                        "/ can merge with both.

                        nextLen := contentsArray at:nextIdx.

                        contentsArray at:prevIdx put:prevLen+nextLen+1.

                        runSz := (runSz - 4).

                        newRuns := Array new:runSz.

                        newRuns replaceFrom:1 to:(prevIdx + 1) with:contentsArray startingAt:1.

                        newRuns replaceFrom:runIndex to:runSz with:contentsArray startingAt:nextIdx+2.

                        contentsArray := newRuns.

                        ^ anObject

                    ]

                ].

                contentsArray at:prevIdx put:prevLen+1.

                runSz := (runSz - 2).

                newRuns := Array new:runSz.

                newRuns replaceFrom:1 to:(runIndex - 1) with:contentsArray startingAt:1.

                newRuns replaceFrom:runIndex to:runSz with:contentsArray startingAt:runIndex+2.

                contentsArray := newRuns.

                ^ anObject

            ].

        ].

        "/ check if merge into next is possible

        runIndex < (runSz-1) ifTrue:[

            nextIdx := runIndex + 2.

            nextVal := contentsArray at:nextIdx+1.

            nextVal = anObject ifTrue:[

                nextLen := contentsArray at:nextIdx.

                contentsArray at:nextIdx put:nextLen + 1.

                runSz := (runSz - 2).

                newRuns := Array new:runSz.

                newRuns replaceFrom:1 to:(runIndex - 1) with:contentsArray startingAt:1.

                newRuns replaceFrom:runIndex to:runSz with:contentsArray startingAt:nextIdx.

                contentsArray := newRuns.

                ^ anObject

            ].

        ].

        "/ no merge; island remains

        contentsArray at:(runIndex+1) put:anObject.

        ^ anObject

    ].

    runOffset == index ifTrue:[

        "/ at the beginning of that run ...

        "/ check if its better added to the previous run ...

        runIndex > 1 ifTrue:[

            prevIdx := runIndex - 2.

            prevVal := contentsArray at:prevIdx+1.

            prevVal = anObject ifTrue:[

                prevLen := contentsArray at:prevIdx.

                contentsArray at:prevIdx put:prevLen + 1.

                contentsArray at:runIndex put:len - 1.

                ^ anObject.

            ].

        ].

        "/ must cut off 1 & insert a new run before ..

        contentsArray at:runIndex put:len - 1.

        runSz := (runSz + 2).

        newRuns := Array new:runSz.

        newRuns replaceFrom:1 to:(runIndex - 1) with:contentsArray startingAt:1.

        newRuns replaceFrom:runIndex+2 to:runSz with:contentsArray startingAt:runIndex.

        contentsArray := newRuns.

        contentsArray at:runIndex   put:1.

        contentsArray at:runIndex+1 put:anObject.

        ^ anObject

    ].

    (runOffset + len - 1) == index ifTrue:[

        "/ at the end ...

        "/ check if its better added to the next run ...

        runIndex < (runSz-1) ifTrue:[

            nextIdx := runIndex + 2.

            nextVal := contentsArray at:nextIdx+1.

            nextVal = anObject ifTrue:[

                nextLen := contentsArray at:nextIdx.

                contentsArray at:nextIdx put:nextLen + 1.

                contentsArray at:runIndex put:len - 1.

                ^ anObject.

            ].

        ].

        "/ must cut off 1 & insert a new run after ..

        contentsArray at:runIndex put:len - 1.

        runSz := (runSz + 2).

        newRuns := Array new:runSz.

        newRuns replaceFrom:1 to:(runIndex + 1) with:contentsArray startingAt:1.

        newRuns replaceFrom:runIndex+4 to:runSz with:contentsArray startingAt:runIndex+2.

        contentsArray := newRuns.

        contentsArray at:runIndex+2 put:1.

        contentsArray at:runIndex+2+1 put:anObject.

        ^ anObject

    ].

    "/ hardest - split run into two, insert new run in-between

    runSz := (runSz + 4).

    newRuns := Array new:runSz.

    runIndex > 1 ifTrue:[

        newRuns replaceFrom:1 to:runIndex-1 with:contentsArray.

    ].

    newRuns replaceFrom:runIndex+6 to:runSz with:contentsArray startingAt:runIndex+2.

    l2 := len - (index - runOffset).

    l1 := len - l2.

    l2 := l2 - 1.

    newRuns at:runIndex   put:l1.

    newRuns at:runIndex+1 put:val.

    newRuns at:runIndex+4 put:l2.

    newRuns at:runIndex+5 put:val.