--- a/RunArray.st Sat May 11 13:27:54 1996 +0200
+++ b/RunArray.st Sat May 11 13:35:58 1996 +0200
@@ -28,7 +28,7 @@
SequenceableCollection subclass:#RunArray
- instanceVariableNames:'runs'
+ instanceVariableNames:'contentsArray'
classVariableNames:''
poolDictionaries:''
category:'Collections-Sequenceable'
@@ -197,7 +197,7 @@
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 }"
@@ -205,14 +205,14 @@
(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
@@ -237,30 +237,29 @@
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,
- and as you can see, the implementation is awful - still if you will
- insist on using this what can you expect. Basically this just copies
- itself up to the start point then adds the required element then
- copies the rest of itself"
+ 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 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:[
@@ -276,7 +275,7 @@
^ self errorInvalidKey:index
].
- val := runs at:(runIndex + 1).
+ val := contentsArray at:(runIndex + 1).
"/ easiest: value there is the same ...
@@ -287,45 +286,45 @@
"/ 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:runIndex to:runSz with:runs startingAt:nextIdx+2.
- runs := newRuns.
+ newRuns replaceFrom:1 to:(prevIdx + 1) with:contentsArray startingAt:1.
+ newRuns replaceFrom:runIndex to:runSz with:contentsArray startingAt:nextIdx+2.
+ 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:runIndex to:runSz with:runs startingAt:runIndex+2.
- runs := newRuns.
+ newRuns replaceFrom:1 to:(runIndex - 1) with:contentsArray startingAt:1.
+ newRuns replaceFrom:runIndex to:runSz with:contentsArray startingAt:runIndex+2.
+ contentsArray := newRuns.
^ anObject
].
@@ -335,23 +334,23 @@
runIndex < runSz ifTrue:[
nextIdx := runIndex + 2.
- nextVal := runs at:nextIdx+1.
+ nextVal := contentsArray at:nextIdx+1.
nextVal = anObject ifTrue:[
- nextLen := runs at:nextIdx.
- runs at:nextIdx put:nextLen + 1.
+ nextLen := contentsArray at:nextIdx.
+ 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:runIndex to:runSz with:runs startingAt:nextIdx.
- runs := newRuns.
+ 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
- runs at:(runIndex+1) put:anObject.
+ contentsArray at:(runIndex+1) put:anObject.
^ anObject
].
@@ -362,27 +361,27 @@
runIndex > 1 ifTrue:[
prevIdx := runIndex - 2.
- prevVal := runs at:prevIdx+1.
+ prevVal := contentsArray at:prevIdx+1.
prevVal = anObject ifTrue:[
- prevLen := runs at:prevIdx.
- runs at:prevIdx put:prevLen + 1.
- runs at:runIndex put:len - 1.
+ 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 ..
- 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:runIndex+2 to:runSz with:runs startingAt:runIndex.
- runs := newRuns.
+ newRuns replaceFrom:1 to:(runIndex - 1) with:contentsArray startingAt:1.
+ newRuns replaceFrom:runIndex+2 to:runSz with:contentsArray startingAt:runIndex.
+ contentsArray := newRuns.
- runs at:runIndex put:1.
- runs at:runIndex+1 put:anObject.
+ contentsArray at:runIndex put:1.
+ contentsArray at:runIndex+1 put:anObject.
^ anObject
].
@@ -393,27 +392,27 @@
runIndex < runSz ifTrue:[
nextIdx := runIndex + 2.
- nextVal := runs at:nextIdx+1.
+ nextVal := contentsArray at:nextIdx+1.
nextVal = anObject ifTrue:[
- nextLen := runs at:nextIdx.
- runs at:nextIdx put:nextLen + 1.
- runs at:runIndex put:len - 1.
+ 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 ..
- 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:runIndex+4 to:runSz with:runs startingAt:runIndex+2.
- runs := newRuns.
+ newRuns replaceFrom:1 to:(runIndex + 1) with:contentsArray startingAt:1.
+ newRuns replaceFrom:runIndex+4 to:runSz with:contentsArray startingAt:runIndex+2.
+ contentsArray := newRuns.
- runs at:runIndex+2 put:1.
- runs at:runIndex+2+1 put:anObject.
+ contentsArray at:runIndex+2 put:1.
+ contentsArray at:runIndex+2+1 put:anObject.
^ anObject
].
@@ -423,9 +422,9 @@
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.
@@ -441,7 +440,7 @@
newRuns at:runIndex+2 put:1.
newRuns at:runIndex+3 put:anObject.
- runs := newRuns.
+ contentsArray := newRuns.
^ anObject
"
@@ -480,21 +479,24 @@
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'!
@@ -519,24 +521,24 @@
|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
@@ -548,12 +550,12 @@
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|
@@ -562,22 +564,22 @@
howBig == sz ifTrue:[^ self].
howBig == 0 ifTrue:[
- runs := nil.
+ contentsArray := nil.
^ self.
].
- runs isNil ifTrue:[
- runs := Array with:howBig with:nil.
+ contentsArray isNil ifTrue:[
+ 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
].
@@ -590,10 +592,10 @@
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).
- runs at:runIndex put:(howBig - runOffset + 1)
+ contentsArray := contentsArray copyFrom:1 to:(runIndex+1).
+ contentsArray at:runIndex put:(howBig - runOffset + 1)
].
"
@@ -611,21 +613,33 @@
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.
- newCollection addAll:self.
+ contentsArray isNil ifTrue:[^ OrderedCollection new].
+
+ 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'!
@@ -634,13 +648,13 @@
"Evaluate aBlock with each of the receiver's elements as the
argument. "
- runs notNil ifTrue:[
- runs pairWiseDo:[:len :val |
+ contentsArray notNil ifTrue:[
+ 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'!
@@ -650,8 +664,8 @@
an object similar to the receiver."
aStream nextPutAll: '(RunArray new'.
- runs notNil ifTrue:[
- runs pairWiseDo:[:len :val |
+ contentsArray notNil ifTrue:[
+ contentsArray pairWiseDo:[:len :val |
aStream nextPutAll: ' add:'; nextPutAll:val storeString.
len == 1 ifFalse:[
aStream nextPutAll:' withCount:'; nextPutAll:len printString.
@@ -674,6 +688,8 @@
RunArray new storeString
"
+
+ "Modified: 11.5.1996 / 13:35:08 / cg"
! !
!RunArray methodsFor:'private'!
@@ -713,8 +729,8 @@
|position|
position := 1.
- runs notNil ifTrue:[
- runs pairWiseDo:[:len :val |
+ contentsArray notNil ifTrue:[
+ contentsArray pairWiseDo:[:len :val |
val = oldObject ifTrue:[
^ position
].
@@ -723,13 +739,15 @@
].
^ 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
@@ -739,11 +757,11 @@
|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:[
@@ -756,15 +774,7 @@
^ #(0 0)
"Created: 10.5.1996 / 17:12:28 / cg"
- "Modified: 10.5.1996 / 17:13:42 / 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"
+ "Modified: 11.5.1996 / 13:35:21 / cg"
! !
!RunArray methodsFor:'user interface'!
@@ -781,5 +791,5 @@
!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 $'
! !