diff -r 8a87aeffa1c0 -r 2b891872f0af RunArray.st --- 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 $' ! !