hg/stx-libbasic2: comparison RunArray.st

equal deleted inserted replaced

-:8a87aeffa1c0
+:2b891872f0af
 "
 SequenceableCollection subclass:#RunArray
-	instanceVariableNames:'runs'
+	instanceVariableNames:'contentsArray'
 	classVariableNames:''
 	poolDictionaries:''
 	category:'Collections-Sequenceable'
 !
 !RunArray methodsFor:'accessing'!
 at:anInteger
 "Answer the element at index anInteger.
 at: is used by a knowledgeable client to access an existing element
-This is a pretty dumb thing to do a compressed collection and it is
+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 }"|
 (anInteger > 0) ifTrue:[
 position := 1.
-nRuns := runs size.
+nRuns := contentsArray size.
 1 to:nRuns by:2 do:[:runIndex |
 |runLen|
-runLen := runs at:runIndex.
+runLen := contentsArray at:runIndex.
 anInteger >= position ifTrue:[
 anInteger < (position + runLen) ifTrue:[
-^ runs at:(runIndex + 1)
+^ contentsArray at:(runIndex + 1)
 ].
 ].
 position := position + runLen
 ]
 ].
 c at:8.
 c at:9.
 c at:10.
 "
-"Modified: 10.5.1996 / 16:59:03 / cg"
+"Modified: 11.5.1996 / 13:33:50 / cg"
 !
 at:index put:anObject
 "Put anObject at element index anInteger.
 at:put: can not be used to append, front or back, to an ordered
 collection;  it is used by a knowledgeable client to replace an
-element. It doesn't make a lot of sense for a compressed collection,
+element.
-and as you can see, the implementation is awful - still if you will
+This is a pretty dumb thing to do to a runArray and it is
-insist on using this what can you expect. Basically this just copies
+very inefficient, since we have to check if runs are to be merged or
-itself up to the start point then adds the required element then
+splitted."
-copies the rest of itself"
 |runSz runIndex runOffset len l1 l2 prevIdx nextIdx
 val newRuns newValues prevLen prevVal nextLen nextVal idx|
-runSz := runs size.
+runSz := contentsArray size.
 runIndex := nil.
 (index > 0) ifTrue:[
 runOffset := 1.
 idx := 1.
 [runIndex isNil and:[idx < runSz]] whileTrue:[
-len := runs at:idx.
+len := contentsArray at:idx.
 nextIdx := runOffset + len.
 index >= runOffset ifTrue:[
 index < nextIdx ifTrue:[
 runIndex := idx.
 nextIdx := runOffset. "/ dont advance
 ].
 runIndex isNil ifTrue:[
 ^ self errorInvalidKey:index
 ].
-val := runs at:(runIndex + 1).
+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 := runs at:runIndex.
+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 := runs at:(prevIdx + 1).
+prevVal := contentsArray at:(prevIdx + 1).
 prevVal = anObject ifTrue:[
 "/ can merge it into previous
-prevLen := runs at:prevIdx.
+prevLen := contentsArray at:prevIdx.
 "/ check if merge into next is also possible (filling an island)
 runIndex < (runSz - 1) ifTrue:[
 nextIdx := runIndex + 2.
-nextVal := runs at:(nextIdx + 1).
+nextVal := contentsArray at:(nextIdx + 1).
 nextVal = anObject ifTrue:[
 "/ can merge with both.
-nextLen := runs at:nextIdx.
+nextLen := contentsArray at:nextIdx.
-runs at:prevIdx put:prevLen+nextLen+1.
+contentsArray at:prevIdx put:prevLen+nextLen+1.
 runSz := (runSz - 4).
 newRuns := Array new:runSz.
-newRuns replaceFrom:1 to:(prevIdx + 1) with:runs startingAt:1.
+newRuns replaceFrom:1 to:(prevIdx + 1) with:contentsArray startingAt:1.
-newRuns replaceFrom:runIndex to:runSz with:runs startingAt:nextIdx+2.
+newRuns replaceFrom:runIndex to:runSz with:contentsArray startingAt:nextIdx+2.
-runs := newRuns.
+contentsArray := newRuns.
 ^ anObject
 ]
 ].
-runs at:prevIdx put:prevLen+1.
+contentsArray at:prevIdx put:prevLen+1.
 runSz := (runSz - 2).
 newRuns := Array new:runSz.
-newRuns replaceFrom:1 to:(runIndex - 1) with:runs startingAt:1.
+newRuns replaceFrom:1 to:(runIndex - 1) with:contentsArray startingAt:1.
-newRuns replaceFrom:runIndex to:runSz with:runs startingAt:runIndex+2.
+newRuns replaceFrom:runIndex to:runSz with:contentsArray startingAt:runIndex+2.
-runs := newRuns.
+contentsArray := newRuns.
 ^ anObject
 ].
 ].
 "/ check if merge into next is possible
 runIndex < runSz ifTrue:[
 nextIdx := runIndex + 2.
-nextVal := runs at:nextIdx+1.
+nextVal := contentsArray at:nextIdx+1.
 nextVal = anObject ifTrue:[
-nextLen := runs at:nextIdx.
+nextLen := contentsArray at:nextIdx.
-runs at:nextIdx put:nextLen + 1.
+contentsArray at:nextIdx put:nextLen + 1.
 runSz := (runSz - 2).
 newRuns := Array new:runSz.
-newRuns replaceFrom:1 to:(runIndex - 1) with:runs startingAt:1.
+newRuns replaceFrom:1 to:(runIndex - 1) with:contentsArray startingAt:1.
-newRuns replaceFrom:runIndex to:runSz with:runs startingAt:nextIdx.
+newRuns replaceFrom:runIndex to:runSz with:contentsArray startingAt:nextIdx.
-runs := newRuns.
+contentsArray := newRuns.
 ^ anObject
 ].
 ].
 "/ no merge; island remains
-runs at:(runIndex+1) put:anObject.
+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 := runs at:prevIdx+1.
+prevVal := contentsArray at:prevIdx+1.
 prevVal = anObject ifTrue:[
-prevLen := runs at:prevIdx.
+prevLen := contentsArray at:prevIdx.
-runs at:prevIdx put:prevLen + 1.
+contentsArray at:prevIdx put:prevLen + 1.
-runs at:runIndex put:len - 1.
+contentsArray at:runIndex put:len - 1.
 ^ anObject.
 ].
 ].
 "/ must cut off 1 & insert a new run before ..
-runs at:runIndex put:len - 1.
+contentsArray at:runIndex put:len - 1.
 runSz := (runSz + 2).
 newRuns := Array new:runSz.
-newRuns replaceFrom:1 to:(runIndex - 1) with:runs startingAt:1.
+newRuns replaceFrom:1 to:(runIndex - 1) with:contentsArray startingAt:1.
-newRuns replaceFrom:runIndex+2 to:runSz with:runs startingAt:runIndex.
+newRuns replaceFrom:runIndex+2 to:runSz with:contentsArray startingAt:runIndex.
-runs := newRuns.
+contentsArray := newRuns.
-runs at:runIndex   put:1.
+contentsArray at:runIndex   put:1.
-runs at:runIndex+1 put:anObject.
+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 ifTrue:[
 nextIdx := runIndex + 2.
-nextVal := runs at:nextIdx+1.
+nextVal := contentsArray at:nextIdx+1.
 nextVal = anObject ifTrue:[
-nextLen := runs at:nextIdx.
+nextLen := contentsArray at:nextIdx.
-runs at:nextIdx put:nextLen + 1.
+contentsArray at:nextIdx put:nextLen + 1.
-runs at:runIndex put:len - 1.
+contentsArray at:runIndex put:len - 1.
 ^ anObject.
 ].
 ].
 "/ must cut off 1 & insert a new run after ..
-runs at:runIndex put:len - 1.
+contentsArray at:runIndex put:len - 1.
 runSz := (runSz + 2).
 newRuns := Array new:runSz.
-newRuns replaceFrom:1 to:(runIndex + 1) with:runs startingAt:1.
+newRuns replaceFrom:1 to:(runIndex + 1) with:contentsArray startingAt:1.
-newRuns replaceFrom:runIndex+4 to:runSz with:runs startingAt:runIndex+2.
+newRuns replaceFrom:runIndex+4 to:runSz with:contentsArray startingAt:runIndex+2.
-runs := newRuns.
+contentsArray := newRuns.
-runs at:runIndex+2 put:1.
+contentsArray at:runIndex+2 put:1.
-runs at:runIndex+2+1 put:anObject.
+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:runs.
+newRuns replaceFrom:1 to:runIndex-1 with:contentsArray.
 ].
-newRuns replaceFrom:runIndex+6 to:(runSz+4) with:runs startingAt:runIndex+2.
+newRuns replaceFrom:runIndex+6 to:(runSz+4) with:contentsArray startingAt:runIndex+2.
 l2 := len - (index - runOffset).
 l1 := len - l2.
 l2 := l2 - 1.
 "/ insert
 newRuns at:runIndex+2 put:1.
 newRuns at:runIndex+3 put:anObject.
-runs := newRuns.
+contentsArray := newRuns.
 ^ anObject
 "
 |c|
 c.
 Transcript showCr:c.
 "
-"Modified: 11.5.1996 / 08:41:49 / cg"
+"Modified: 11.5.1996 / 13:34:21 / cg"
 !
 size
-"Answer how many elements the receiver contains."
+"Answer how many elements the receiver contains.
+Thsi is not the number of runs (but the simulated number of elements)."
 |n     "{ Class: SmallInteger }"
 runSz "{ Class: SmallInteger }"|
 n := 0.
-runSz := runs size.
+runSz := contentsArray size.
 1 to:runSz by:2 do:[:i |
-n := n + (runs at:i)
+n := n + (contentsArray at:i)
 ].
 ^ n
+"Modified: 11.5.1996 / 13:34:27 / cg"
 ! !
 !RunArray methodsFor:'adding'!
 add:newObject
 add:newObject withOccurrences:n
 "add newObject n times at the end; returns the object (sigh)"
 |lastIdx runSz newRuns|
-runs notNil ifTrue:[
+contentsArray notNil ifTrue:[
 "/ check for merge
-runSz := runs size.
+runSz := contentsArray size.
-(runs at:runSz) = newObject ifTrue:[
+(contentsArray at:runSz) = newObject ifTrue:[
 lastIdx := runSz - 1.
-runs at:lastIdx put:(runs at:lastIdx) + n.
+contentsArray at:lastIdx put:(contentsArray at:lastIdx) + n.
 ^ newObject
 ].
 newRuns := Array new:(runSz + 2).
-newRuns replaceFrom:1 to:runSz with:runs.
+newRuns replaceFrom:1 to:runSz with:contentsArray.
 newRuns at:runSz+1 put:n.
 newRuns at:runSz+2 put:newObject.
-runs := newRuns.
+contentsArray := newRuns.
 ] ifFalse:[
-runs := Array with:n with:newObject.
+contentsArray := Array with:n with:newObject.
 ].
 ^ newObject
 "
 |c|
 c := RunArray new.
 c add:1 withOccurrences:1000; yourself.
 c add:2 withOccurrences:1000; yourself.
 "
-"Modified: 10.5.1996 / 18:29:56 / cg"
+"Modified: 11.5.1996 / 13:34:37 / cg"
 !
 grow:howBig
 "grow or shrink the receiver to contain howBig elements.
-If growing, new slots will be filled with nil."
+If growing, new slots will be filled (logically) with nil."
 |sz info runIndex runOffset runSz newRuns|
 sz := self size.
 howBig == sz ifTrue:[^ self].
 howBig == 0 ifTrue:[
-runs := nil.
+contentsArray := nil.
 ^ self.
 ].
-runs isNil ifTrue:[
+contentsArray isNil ifTrue:[
-runs := Array with:howBig with:nil.
+contentsArray := Array with:howBig with:nil.
 ^ self
 ].
-runSz := runs size.
+runSz := contentsArray size.
 howBig > sz ifTrue:[
 newRuns := Array new:(runSz + 2).
-newRuns replaceFrom:1 to:runSz with:runs startingAt:1.
+newRuns replaceFrom:1 to:runSz with:contentsArray startingAt:1.
 newRuns at:(runSz+1) put:(howBig - sz).
-runs := newRuns.
+contentsArray := newRuns.
 ^ self
 ].
 "/ shrinking; possibly cut of a run
 runOffset := info at:2.
 howBig == (runOffset - 1) ifTrue:[
 "/ we are lucky - new size is up-to previous run
-runs := runs copyFrom:1 to:runIndex-1.
+contentsArray := contentsArray copyFrom:1 to:runIndex-1.
 ] ifFalse:[
-runs := runs copyFrom:1 to:(runIndex+1).
+contentsArray := contentsArray copyFrom:1 to:(runIndex+1).
-runs at:runIndex put:(howBig - runOffset + 1)
+contentsArray at:runIndex put:(howBig - runOffset + 1)
 ].
 "
 |c|
 c grow:6; yourself.
 c grow:0; yourself.
 "
-"Modified: 10.5.1996 / 18:11:54 / cg"
+"Modified: 11.5.1996 / 13:34:53 / cg"
 ! !
 !RunArray methodsFor:'converting'!
 asOrderedCollection
-"Uncompress this collection."
+"return a new orderedCollection, containing the receivers elements."
 |newCollection|
-newCollection := OrderedCollection new.
+contentsArray isNil ifTrue:[^ OrderedCollection new].
-newCollection addAll:self.
+newCollection := OrderedCollection new:(self size).
+contentsArray pairWiseDo:[:len :value |
+newCollection add:value withOccurrences:len
+].
 ^ newCollection
-"Modified: 10.5.1996 / 13:31:49 / cg"
+"
+|r|
+r := RunArray withAll:#(1 2 3 3 3 3 4 4 4 5 6 7 7 7 7 7 7 7).
+Transcript showCr:r.
+Transcript showCr:r asOrderedCollection
+"
+"Modified: 11.5.1996 / 13:34:59 / cg"
 ! !
 !RunArray methodsFor:'enumerating'!
 do:aBlock
 "Evaluate aBlock with each of the receiver's elements as the
 argument. "
-runs notNil ifTrue:[
+contentsArray notNil ifTrue:[
-runs pairWiseDo:[:len :val |
+contentsArray pairWiseDo:[:len :val |
 len timesRepeat: [aBlock value:val]
 ]
 ]
-"Modified: 10.5.1996 / 16:56:01 / cg"
+"Modified: 11.5.1996 / 13:35:03 / cg"
 ! !
 !RunArray methodsFor:'printing'!
 storeOn:aStream
 "Append to aStream an expression which, if evaluated, will generate
 an object similar to the receiver."
 aStream nextPutAll: '(RunArray new'.
-runs notNil ifTrue:[
+contentsArray notNil ifTrue:[
-runs pairWiseDo:[:len :val |
+contentsArray pairWiseDo:[:len :val |
 aStream nextPutAll: ' add:'; nextPutAll:val storeString.
 len == 1 ifFalse:[
 aStream nextPutAll:' withCount:'; nextPutAll:len printString.
 ].
 aStream nextPutAll:';'
 add:5;
 yourself) storeString
 RunArray new storeString
 "
+"Modified: 11.5.1996 / 13:35:08 / cg"
 ! !
 !RunArray methodsFor:'private'!
 find:oldObject
 element of that value."
 |position|
 position := 1.
-runs notNil ifTrue:[
+contentsArray notNil ifTrue:[
-runs pairWiseDo:[:len :val |
+contentsArray pairWiseDo:[:len :val |
 val = oldObject ifTrue:[
 ^ position
 ].
 position := position + len.
 ].
 ].
 ^ exceptionBlock value
-"Modified: 10.5.1996 / 13:54:25 / cg"
+"Modified: 11.5.1996 / 13:35:14 / cg"
 !
 isEmpty
 "Am I empty or not. Returns a boolean"
-^ runs notNil
+^ contentsArray notNil
+"Modified: 11.5.1996 / 13:35:17 / cg"
 !
 runIndexAndStartIndexForIndex:anIndex
 "given a logical index, find the index of that run and the logical index
 of the first item in that run."
 |position nRuns "{ Class: SmallInteger }"|
 position := 1.
-nRuns := runs size.
+nRuns := contentsArray size.
 1 to:nRuns by:2 do:[:runIndex |
 |runLen runLast|
-runLen := runs at:runIndex.
+runLen := contentsArray at:runIndex.
 anIndex >= position ifTrue:[
 runLast := position + runLen - 1.
 anIndex <= runLast ifTrue:[
 ^ Array with:runIndex with:position
 ].
 ].
 ^ #(0 0)
 "Created: 10.5.1996 / 17:12:28 / cg"
-"Modified: 10.5.1996 / 17:13:42 / cg"
+"Modified: 11.5.1996 / 13:35:21 / cg"
-!
-runIndexForIndex:anIndex
-"given a logical index, find the index of that run"
-^ (self runIndexAndStartIndexForIndex:anIndex) at:1
-"Modified: 10.5.1996 / 17:13:45 / cg"
 ! !
 !RunArray methodsFor:'user interface'!
 inspect
 ! !
 !RunArray class methodsFor:'documentation'!
 version
-^ '$Header: /cvs/stx/stx/libbasic2/RunArray.st,v 1.2 1996-05-11 11:27:54 cg Exp $'
+^ '$Header: /cvs/stx/stx/libbasic2/RunArray.st,v 1.3 1996-05-11 11:35:58 cg Exp $'
 ! !

changeset 299	2b891872f0af
parent 298	8a87aeffa1c0
child 300	4855b70c63b6