eXept Software AG Logo

Smalltalk/X Webserver

Documentation of class 'RunArray':

Home

Documentation
www.exept.de
Everywhere
for:
[back]

Class: RunArray


Inheritance:

   Object
   |
   +--Collection
      |
      +--SequenceableCollection
         |
         +--RunArray

Package:
stx:libbasic2
Category:
Collections-Sequenceable
Version:
rev: 1.62 date: 2024/02/16 16:19:10
user: stefan
file: RunArray.st directory: libbasic2
module: stx stc-classLibrary: libbasic2

Description:


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.

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

Class protocol:

instance creation
o  from: aSequencableCollection
return a new runArray, containing the elements from aSequencableCollection

Usage example(s):

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

o  new: count
return a new runArray, containing count elements - all nil

o  new: count withAll: anObject
create a new runArray with count elements, all being anObject

Usage example(s):

     RunArray new:100 withAll:#hello

o  runs: runs values: values
return a new runArray, containing elements defined by pairs from
runs and values

Usage example(s):

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


Instance protocol:

Compatibility-ST80
o  runs
|c|

c := RunArray new.
c add:1 withOccurrences:1000.
c add:2 withOccurrences:1000.
c runs.

o  values
|c|

c := RunArray new.
c add:1 withOccurrences:1000.
c add:2 withOccurrences:1000.
c values.

accessing
o  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).

Usage example(s):

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

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

Usage example(s):

     |c|

     Transcript cr.

     c := RunArray new.
     c add:1; add:1; add:1; add:2; add:2; add:3; add:3; add:4; add:5; yourself.
     Transcript showCR:c.   

     c at:1 put:$a.
     Transcript showCR:c.   
     c.

     c at:3 put:$a.
     Transcript showCR:c.   
     c.

     c at:4 put:$a.   
     Transcript showCR:c.   
     c.

     c at:5 put:$a.   
     Transcript showCR:c.   
     c.

     c at:2 put:$0.   
     Transcript showCR:c.   
     c.

     c at:2 put:$a.   
     Transcript showCR:c.   
     c.

     Transcript showCR:c.   
     Transcript showCR:c runs.   

o  atAllPut: anObject
replace all elements of the collection by the argument, anObject.
Return the receiver.
Notice: This operation modifies the receiver, NOT a copy;
therefore the change may affect all others referencing the receiver.

Usage example(s):

     |c|

     c := RunArray new:20.
     c atAllPut:1.
     Transcript showCR:c.   

adding & removing
o  , aCollection
return a new collection formed from concatenating the receiver with the argument

Usage example(s):

    |a b|
    a := RunArray withAll:#( 10 10 20 20 20 30 30 30 ).
    b := a , (RunArray withAll:#( 40 40 50 50 50 50 60 60 60 60 60)).
    b

Usage example(s):

    |a b|
    a := RunArray withAll:#( 10 10 20 20 20 30 30 30 ).
    b := a ,, (RunArray withAll:#( 40 40 50 50 50 50 60 60 60 60 60)).
    b

o  add: newObject
add newObject at the end.
Returns the object (sigh)

Usage example(s):

     |c|

     c := RunArray new.
     c add:1; add:1; add:1; add:2; add:2; add:3; add:3; add:4; add:5; yourself.

o  add: newObject withOccurrences: n
add newObject n times at the end; returns the object (sigh)

Usage example(s):

     |c|

     c := RunArray new.
     c add:1 withOccurrences:1000; yourself.
     c add:1 withOccurrences:500; yourself.
     c add:2 withOccurrences:1000; yourself.

o  addAll: aCollection
add all elements of the argument, aCollection to the receiver.
Returns the argument, aCollection (sigh).

Usage example(s):

    (RunArray withAll:#(10 10 20 20 20 30 30 30))
       addAll: #(30 40 40 50 50 50);
       yourself

Usage example(s):

    (RunArray withAll:#(10 10 20 20 20 30 30 30))
       addAll:(RunArray withAll:#( 30 30 30 40 40 50 50 50));
       yourself

o  addFirst: newObject
add newObject at the beginning.
Returns the object (sigh)

Usage example(s):

     |c|

     c := RunArray new.
     c add:1; add:1; add:1; 
       add:2; add:2; 
       add:3; add:3; 
       add:4; 
       add:5; 
       addFirst:99;
       yourself.

o  addFirst: newObject withOccurrences: n
add newObject n times at the beginning; returns the object (sigh)

Usage example(s):

     RunArray new
       add:1; add:1; add:1; 
       add:2; add:2; 
       add:3; add:3; 
       add:4; 
       add:5; 
       addFirst:99 withOccurrences:5;
       yourself.

comparing
o  = aCollection
return true, if the argument contains the same elements as the receiver.
Optimized, especially for the common case, that collection is another runArray

Usage example(s):

     'hello' asText sameStringAndEmphasisAs: 'hello' asText
     'hello' asText sameStringAndEmphasisAs: 'hello' asText allBold
     'hello' asText allBold sameStringAndEmphasisAs: 'hello' asText allBold
     'hello1' asText allBold sameStringAndEmphasisAs: 'hello' asText allBold  
     'hello' asText allBold sameStringAndEmphasisAs: 'hello1' asText allBold  
     ('hello' asText allBold , ' ') sameStringAndEmphasisAs: 'hello ' asText allBold  
     ('hello ' asText allBold) sameStringAndEmphasisAs: ('hello' asText allBold , ' ')  
     ('hello' asText allBold , ' ') sameStringAndEmphasisAs: ('hello' asText allBold , ' ')  
     'hello' asRunArray = 'hello' asRunArray 
     'hello1' asRunArray = 'hello' asRunArray 
     'hello' asRunArray = 'hello1' asRunArray 
     'hello' asRunArray = 'hello' asArray      
     'hello1' asRunArray = 'hello' asArray     
     'hello' asRunArray = 'hello1' asArray     

converting
o  asArray
return a new array, containing the receiver's elements.

Usage example(s):

     |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 asArray.
     Transcript showCR:r asRunArray.

o  asOrderedCollection
return a new orderedCollection, containing the receiver's elements.

Usage example(s):

     |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

o  asRunArray
return the receiver itself

copying
o  copyFrom: start to: stop
return a new collection, containing the elements from start to stop

Usage example(s):

     |r|
     r := RunArray withAll:#(1 2 3 3 3 3 4 4 4 5 6 7 7 7 7 7 7 7).
     r copyFrom:1 to:10  

     |r|
     r := RunArray withAll:#(1 2 3 3 3 3 3 3 4 5 6 7 7 7 7 7 7 7).
     r copyFrom:4 to:10       

     |r|
     r := RunArray withAll:#(1 2 3 3 3 3 3 3 4 5 6 7 7 7 7 7 7 7).
     r copyFrom:1 to:20      

copying-private
o  postCopy
(comment from inherited method)
this is for compatibility with ST-80 code, which uses postCopy for
cleanup after copying, while ST/X passes the original in postCopyFrom:
(see there)

enumerating
o  anySatisfy: aBlock
Return true, if aBlock returns true for any of the receiver's elements

Usage example(s):

     #() anySatisfy:[:x | true]    

o  conform: aBlock
return true, if every element conforms to some condition.
I.e. return false, if aBlock returns false for any element;
true otherwise. Returns true for empty receivers.

Usage example(s):

     #() conform:[:x | false]

o  do: aBlock
Evaluate aBlock with each of the receiver's elements as the argument.

o  runsDo: aBlock
Evaluate aBlock with each of the receiver's runs,
passing length and value as arguments.

o  withStartStopAndValueDo: aThreeArgBlock
Evaluate aBlock with each of the receiver's runs, passing
start, end and attributes as arguments.

Usage example(s):

     ('aaa',('bbb' allBold),('ccc' allItalic),'ddd')
        runs 
            withStartStopAndValueDo:[:start :stop :emp |
                Transcript showCR:{start . stop . emp}
            ]

misc ui support
o  inspectorClass
( an extension from the stx:libtool package )
Re-reimplemented so that we don't get an ordered collection inspector
which would get very confused when confronted with a runArray.

printing & storing
o  displayOn: aGCOrStream
Append to aStream an expression which, if evaluated, will generate
an object similar to the receiver.

o  storeOn: aStream
Append to aStream an expression which, if evaluated, will generate
an object similar to the receiver.

private
o  find: oldObject
If I contain oldObject return its index, otherwise create an error
notifier. It will answer with the position of the very first element of
that value.
OBSOLETE: this is a leftover from earlier times; use #indexOf:ifAbsent:

** This is an obsolete interface - do not use it (it may vanish in future versions) **

o  find: oldObject ifAbsent: exceptionBlock
If I contain oldObject return its index, otherwise execute the
exception block. It will answer with the position of the very first
element of that value.
OBSOLETE: this is a leftover from earlier times; use #indexOf:ifAbsent:

** This is an obsolete interface - do not use it (it may vanish in future versions) **

o  getContentsArray

o  runIndexAndStartIndexForIndex: anIndex
given a logical index, find the index of that run and the logical index
of the first item in that run.

o  setElement: newObject occurrences: n
private instance setup

o  setElementsFrom: aCollection
set my elements from aCollection

o  setElementsFromRuns: runs values: values

** This is an obsolete interface - do not use it (it may vanish in future versions) **

o  setRuns: runs setValues: values

private-growing
o  grow: howBig
grow or shrink the receiver to contain howBig elements.
If growing, new slots will be filled (logically) with nil.

Usage example(s):

     |c|

     c := RunArray new.
     c addAll:#(1 2 3 4 4 4 4 5 5 5 1 2 3); yourself.

     c grow:50; yourself.

     c grow:7; yourself.

     c grow:6; yourself.

     c grow:0; yourself.

queries
o  includes: anElement
return true, if the receiver includes an element which is equal
to the argument, anElement; false otherwise.
Redefined to prevent the inherited loop over individual accesses via #at:,
which would be very inefficient.

o  includesIdentical: anElement
return true, if the receiver includes the argument, anElement; false otherwise.
Redefined to prevent the inherited loop over individual accesses via #at:,
which would be very inefficient.

o  isEmpty
Am I empty or not. Returns a boolean

o  size
Answer how many elements the receiver contains.
This is not the number of runs (but the simulated number of elements).

searching
o  findFirst: aBlock ifNone: exceptionalValue
find the index of the first element, for which evaluation of the argument, aBlock
returns true; return its index or 0 if none detected.
Notice, that not all elements are processed here
(the block is only evaluated for each runs first element).

Usage example(s):

     (RunArray new 
        add:1 withOccurrences:100;
        add:2 withOccurrences:100;
        add:3 withOccurrences:100;
        add:4 withOccurrences:100;
        yourself) findFirst:[:el | el == 3] 

o  identityIndexOf: anElement startingAt: start
search for identical anElement, return the index or 0 if not found.
Redefined to prevent a loop over individual accesses via #at:,
which would be very inefficient.

o  indexOf: anElement startingAt: start
search for equal anElement, return the index or 0 if not found.
Redefined to prevent a loop over individual accesses via #at:,
which would be very inefficient.

Usage example(s):

     |r|
     r := RunArray new. 
     r add:1 withOccurrences:100.
     r add:2 withOccurrences:100.
     r add:3 withOccurrences:100.
     r add:4 withOccurrences:100.
     r indexOf:2 startingAt:50.  
     r indexOf:2 startingAt:100.  
     r indexOf:2 startingAt:101.  
     r indexOf:2 startingAt:150.  
     r indexOf:2 startingAt:200.  
     r indexOf:2 startingAt:201.   
     r indexOf:2 startingAt:202.   


Examples:


this eats up a lot of memory ... ... but its relatively fast:
  |coll|

  coll := OrderedCollection new.
  Transcript showCR:(    
      Time millisecondsToRun:[
          100000 timesRepeat:[coll add:'hello'].
          100000 timesRepeat:[coll add:'world'].
      ]
  ).
  coll inspect.
this is very space efficient ... ... (and even slightly faster):
  |coll|

  coll := RunArray new.
  Transcript showCR:(    
      Time millisecondsToRun:[
          100000 timesRepeat:[coll add:'hello'].
          100000 timesRepeat:[coll add:'world'].
      ]
  ).
  coll inspect.
this is very space efficient ... ... AND much faster:
  |coll|

  coll := RunArray new.
  Transcript showCR:(    
      Time millisecondsToRun:[
          coll add:'hello' withOccurrences:100000.
          coll add:'world' withOccurrences:100000.
      ]
  ).
  coll inspect.
single-element runs; this is very space INEFFICIENT (requires twice as much) ... ... and MUCH slower:
  |coll|

  coll := RunArray new.
  Transcript showCR:(    
      Time millisecondsToRun:[
          1 to:1000 do:[:i | coll add:i].
      ]
  ).
compare to:
  |coll|

  coll := OrderedCollection new.
  Transcript showCR:(    
      Time millisecondsToRun:[
          1 to:1000 do:[:i | coll add:i].
      ]
  ).


ST/X 7.7.0.0; WebServer 1.702 at 20f6060372b9.unknown:8081; Mon, 07 Oct 2024 23:08:28 GMT