SparseClusterArray (JPF API)

java.lang.Object
- gov.nasa.jpf.util.SparseClusterArray<E>

All Implemented Interfaces:

Iterable<E>
```
public class SparseClusterArray<E>
extends Object
implements Iterable<E>
```
A generic sparse reference array that assumes clusters, and more frequent intra-cluster access. This is motivated by looking for a more suitable ADT to model a heap address space, where reference values consist of segment/offset pairs, we have reasonably dense and very dynamic population inside of well separated segment clusters, and intra-cluster access is more likely than inter-cluster access. An especially important feature is to be able to iterate efficiently over set/unset elements in index intervals (cluster sizes). The result should find a compromise between the fast element access & iteration of a simple, dense array, and the efficient memory storage of a HashMap (if only it could avoid box objects). <2do> so far, we are totally ignorant of population constraints

Nested Class Summary

Nested Classes
Modifier and Type	Class and Description
`protected static class`	`SparseClusterArray.Chunk`
`protected static class`	`SparseClusterArray.ChunkNode`
`protected class`	`SparseClusterArray.ElementIndexIterator`
`protected class`	`SparseClusterArray.ElementIterator<T>`
`static class`	`SparseClusterArray.Entry<E>`
`protected static class`	`SparseClusterArray.Node` this corresponds to a toplevel cluster (e.g.
`protected static class`	`SparseClusterArray.Root`
`static class`	`SparseClusterArray.Snapshot<T,E>`

Field Summary

Fields
Modifier and Type	Field and Description
`protected static int`	`BM_ENTRIES`
`protected SparseClusterArray.Entry`	`changes`
`protected static int`	`CHUNK_BASEMASK`
`static int`	`CHUNK_BITS`
`static int`	`CHUNK_SIZE`
`protected static int`	`ELEM_MASK`
`protected SparseClusterArray.Chunk`	`head`
`protected SparseClusterArray.Chunk`	`lastChunk`
`protected static int`	`MAX_BM_INDEX`
`static int`	`MAX_CLUSTER_ENTRIES`
`static int`	`MAX_CLUSTERS`
`static int`	`N_ELEM`
`static int`	`N_SEG`
`protected int`	`nSet`
`protected SparseClusterArray.Root`	`root`
`static int`	`S1`
`static int`	`S2`
`static int`	`S3`
`static int`	`SEG_BITS`
`protected static int`	`SEG_MASK`
`protected boolean`	`trackChanges`

Constructor Summary

Constructors
Modifier	Constructor and Description
	`SparseClusterArray()`
`protected`	`SparseClusterArray(SparseClusterArray base)` be careful, this should only be used to get old stored elements during a Snapshot restore

Method Summary

Methods
Modifier and Type	Method and Description
`int`	`cardinality()`
`void`	`clear()`
`SparseClusterArray<E>`	`deepCopy(Cloner<E> elementCloner)` deep copy we need to do this depth first, right-to-left, to maintain the Chunk list ordering.
`int`	`firstNullIndex(int i, int length)` find first null element within given range [i, i+length[
`E`	`get(int i)`
`SparseClusterArray.Entry<E>`	`getChanges()`
`IndexIterator`	`getElementIndexIterator()`
`IndexIterator`	`getElementIndexIterator(int fromIndex)`
`<T> SparseClusterArray.Snapshot<E,T>`	`getSnapshot(Transformer<E,T> transformer)` create a snapshot that can be used to restore a certain state of our array This is more suitable than cloning in case the array is very sparse, or the elements contain a lot of transient data we don't want to store
`boolean`	`isTrackingChanges()`
`Iterator<E>`	`iterator()`
`int`	`numberOfChunks()`
`int`	`numberOfElements()`
`protected <T> void`	`populateSnapshot(SparseClusterArray.Snapshot<E,T> snap, Transformer<E,T> transformer)`
`void`	`resetChanges()`
`<T> void`	`restore(SparseClusterArray.Snapshot<E,T> snap, Transformer<T,E> transformer)`
`void`	`revertChanges(SparseClusterArray.Entry<E> changes)`
`void`	`set(int i, E e)`
`void`	`stopTrackingChanges()`
`String`	`toString()`
`void`	`trackChanges()`

Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Field Detail

CHUNK_BITS
```
public static final int CHUNK_BITS
```
See Also:
Constant Field Values

CHUNK_SIZE
```
public static final int CHUNK_SIZE
```
See Also:
Constant Field Values

N_ELEM
```
public static final int N_ELEM
```
See Also:
Constant Field Values

ELEM_MASK
```
protected static final int ELEM_MASK
```
See Also:
Constant Field Values

BM_ENTRIES
```
protected static final int BM_ENTRIES
```
See Also:
Constant Field Values

MAX_BM_INDEX
```
protected static final int MAX_BM_INDEX
```
See Also:
Constant Field Values

SEG_BITS
```
public static final int SEG_BITS
```
See Also:
Constant Field Values

N_SEG
```
public static final int N_SEG
```
See Also:
Constant Field Values

SEG_MASK
```
protected static final int SEG_MASK
```
See Also:
Constant Field Values

S1
```
public static final int S1
```
See Also:
Constant Field Values

S2
```
public static final int S2
```
See Also:
Constant Field Values

S3
```
public static final int S3
```
See Also:
Constant Field Values

CHUNK_BASEMASK
```
protected static final int CHUNK_BASEMASK
```
See Also:
Constant Field Values

MAX_CLUSTERS
```
public static final int MAX_CLUSTERS
```
See Also:
Constant Field Values

MAX_CLUSTER_ENTRIES
```
public static final int MAX_CLUSTER_ENTRIES
```
See Also:
Constant Field Values

root
```
protected SparseClusterArray.Root root
```

lastChunk

protected SparseClusterArray.Chunk lastChunk

head

protected SparseClusterArray.Chunk head

nSet
```
protected int nSet
```

trackChanges
```
protected boolean trackChanges
```

changes

protected SparseClusterArray.Entry changes

Constructor Detail
- SparseClusterArray
```
public SparseClusterArray()
```
- SparseClusterArray
```
protected SparseClusterArray(SparseClusterArray base)
```
  be careful, this should only be used to get old stored elements during a Snapshot restore

Method Detail

get
```
public E get(int i)
```

set
```
public void set(int i,
       E e)
```

firstNullIndex
```
public int firstNullIndex(int i,
                 int length)
```
find first null element within given range [i, i+length[

Returns:
-1 if there is none

deepCopy
```
public SparseClusterArray<E> deepCopy(Cloner<E> elementCloner)
```
deep copy we need to do this depth first, right-to-left, to maintain the Chunk list ordering. We also compact during cloning, i.e. remove empty chunks and ChunkNodes/Nodes w/o descendants

getSnapshot
```
public <T> SparseClusterArray.Snapshot<E,T> getSnapshot(Transformer<E,T> transformer)
```
create a snapshot that can be used to restore a certain state of our array This is more suitable than cloning in case the array is very sparse, or the elements contain a lot of transient data we don't want to store

populateSnapshot

protected <T> void populateSnapshot(SparseClusterArray.Snapshot<E,T> snap,
                        Transformer<E,T> transformer)

restore

public <T> void restore(SparseClusterArray.Snapshot<E,T> snap,
               Transformer<T,E> transformer)

clear
```
public void clear()
```

trackChanges
```
public void trackChanges()
```

stopTrackingChanges
```
public void stopTrackingChanges()
```

isTrackingChanges
```
public boolean isTrackingChanges()
```

getChanges

public SparseClusterArray.Entry<E> getChanges()

resetChanges
```
public void resetChanges()
```

revertChanges

public void revertChanges(SparseClusterArray.Entry<E> changes)

toString
```
public String toString()
```
Overrides:

toString in class Object

numberOfElements
```
public int numberOfElements()
```

numberOfChunks
```
public int numberOfChunks()
```

getElementIndexIterator

public IndexIterator getElementIndexIterator()

getElementIndexIterator

public IndexIterator getElementIndexIterator(int fromIndex)

iterator
```
public Iterator<E> iterator()
```
Specified by:

iterator in interface Iterable<E>

cardinality
```
public int cardinality()
```

Class SparseClusterArray<E>

Nested Class Summary

Field Summary

Constructor Summary

Method Summary

Methods inherited from class java.lang.Object

Field Detail

CHUNK_BITS

CHUNK_SIZE

N_ELEM

ELEM_MASK

BM_ENTRIES

MAX_BM_INDEX

SEG_BITS

N_SEG

SEG_MASK

S1

S2

S3

CHUNK_BASEMASK

MAX_CLUSTERS

MAX_CLUSTER_ENTRIES

root

lastChunk

head

nSet

trackChanges

changes

Constructor Detail

SparseClusterArray

SparseClusterArray

Method Detail

get

set

firstNullIndex

deepCopy

getSnapshot

populateSnapshot

restore

clear

trackChanges

stopTrackingChanges

isTrackingChanges

getChanges

resetChanges

revertChanges

toString

numberOfElements

numberOfChunks

getElementIndexIterator

getElementIndexIterator

iterator

cardinality