public class PaigeTarjan extends Object
To ensure maximal performance, this class is designed in a very low-level fashion, exposing most of its internal fields directly. It should only ever be used directly, and its use should be hidden behind a facade such that neither this class nor any of its methods/referenced objects are exposed at an API level.
This class stores most of its internal data in several, or possibly even a single, (mostly int
) array(s),
to achieve maximal cache efficiency. The layout of of these arrays is described in the documentation
of the respective public fields:
PaigeTarjanInitializers
provides methods for initializing this data structure for common
cases (e.g., DFA minimization). Similarly, the PaigeTarjanExtractors
class provides methods for
transforming the resulting data structure.Modifier and Type | Class and Description |
---|---|
static class |
PaigeTarjan.WorklistPolicy
Determines how the worklist is managed, i.e., where newly created blocks are inserted.
|
Modifier and Type | Field and Description |
---|---|
int[] |
blockData
The array storing the raw block data, i.e., the states contained in a certain
block.
|
Block[] |
blockForState
The array mapping states (in the range between
0 and numStates ) to their
containing block. |
int |
numInputs
The number of input symbols.
|
int |
numStates
The number of states.
|
int[] |
posData
The array storing the position data, i.e., for each state, its index in the
blockData array. |
int |
posDataLow
The lowest index storing position data in the
posData array. |
int[] |
predData
The array storing the predecessor data, i.e., for each state and input symbol,
a list of the respective predecessors.
|
int[] |
predOfsData
The array storing the predecessor offset data, i.e., for each state and input symbol,
the delimiting offsets of the respective predecessor list.
|
int |
predOfsDataLow
The lowest index storing predecessor offset data in the
predOfsData array. |
Constructor and Description |
---|
PaigeTarjan() |
Modifier and Type | Method and Description |
---|---|
Iterable<Block> |
blockList()
Retrieves an
Iterable that provides the iterator returned by
blockListIterator() . |
Iterator<Block> |
blockListIterator()
Retrieves an iterator for iterating over all blocks in the block list.
|
void |
computeCoarsestStablePartition()
Refines the partition until it stabilizes.
|
Block |
createBlock()
Creates a new block.
|
Block[] |
createBlockForStateMap()
Creates the
blockForState mapping from the blocks in the block list,
and the contents of the blockData array. |
Block |
getBlockForState(int id)
Retrieves the corresponding block for a given state (ID).
|
int |
getNumBlocks()
Retrieves the total number of blocks in the block list.
|
int |
getRepresentative(Block b)
Retrieves a representative state from the given block.
|
void |
initBlockForStateMap()
Automatically creates a
blockForState mapping, and sets it as the current
one. |
void |
initWorklist(boolean addAll)
Initializes the worklist from the block list.
|
void |
removeEmptyBlocks()
Removes all blocks which are empty from the block list.
|
void |
setBlockData(int[] blockData) |
void |
setBlockForState(Block[] blockForState) |
void |
setPosData(int[] posData,
int posDataLow) |
void |
setPredData(int[] predData) |
void |
setPredOfsData(int[] predOfsData,
int predOfsDataLow) |
void |
setSize(int numStates,
int numInputs) |
void |
setWorklistPolicy(PaigeTarjan.WorklistPolicy policy) |
PrimitiveIterator.OfInt |
statesInBlockIterator(Block b)
Retrieves an iterator for the contents of the given block.
|
Spliterator.OfInt |
statesInBlockSpliterator(Block b)
Retrieves a spliterator for the contents of the given block.
|
public int numInputs
public int numStates
public int[] blockData
Block.low
and Block.high
refer to this array.public int[] posData
blockData
array.
The layout of this array is assumed to be the following: for the state i
,
where 0 <= i <
, the index of numStates
i
in blockData
is
.posData
[posDataLow
+ i]
public int posDataLow
posData
array.public int[] predOfsData
predData
array.
The layout of this array is assumed to be the following: for state i
and input symbol
j
, where 0 <= i <
and
numStates
0 <= j <
, the offset (in the numInputs
predData
array)
of the first j
-predecessor of i
is
, and the
last predOfsData
[predOfsDataLow
+ j*numStates
+ i]j
-predecessor of i
is
.
Note that this requires the index
predOfsData
[predOfsDataLow
+ j*numStates
+ i + 1] - 1
to be valid, and
the contents of the predOfsDataLow
+ numInputs
* numStates
predOfsData
array at this index must be the highest offset of any
predecessor plus one.
public int predOfsDataLow
predOfsData
array.public int[] predData
The layout of this array is assumed to be the following: for state i
and input symbol
j
, where 0 <= i <
and
numStates
0 <= j <
, the numInputs
j
-predecessors of i
are
the elements of predData
from index
, inclusive, to index
predOfsData
[predOfsDataLow
+ j*numStates
+ i]
, exclusive.predOfsData
[predOfsDataLow
+ j*numStates
+ i + 1]
public void setSize(int numStates, int numInputs)
public void setWorklistPolicy(PaigeTarjan.WorklistPolicy policy)
public void setBlockForState(Block[] blockForState)
public void setBlockData(int[] blockData)
public void setPosData(int[] posData, int posDataLow)
public void setPredOfsData(int[] predOfsData, int predOfsDataLow)
public void setPredData(int[] predData)
public void removeEmptyBlocks()
IDs
of the blocks
are adjusted to remain contiguous.
Note that this method does not modify the worklist, i.e., it should only be called when the worklist is empty.
public Block[] createBlockForStateMap()
blockForState
mapping from the blocks in the block list,
and the contents of the blockData
array.blockForState
mapping consistent with the blockData
public void initBlockForStateMap()
blockForState
mapping, and sets it as the current
one.public void initWorklist(boolean addAll)
If addAll
is true
, all blocks from the block list will be added to the
worklist. Otherwise, all but the largest block will be added.
addAll
- controls if all blocks are added to the worklist, or all but the largest.public void computeCoarsestStablePartition()
public Block createBlock()
public Block getBlockForState(int id)
id
- the state IDpublic int getRepresentative(Block b)
b
- the blockpublic Spliterator.OfInt statesInBlockSpliterator(Block b)
b
- the blockpublic PrimitiveIterator.OfInt statesInBlockIterator(Block b)
b
- the blockpublic Iterator<Block> blockListIterator()
public Iterable<Block> blockList()
Iterable
that provides the iterator returned by
blockListIterator()
.Iterable
for iterating over all blockspublic int getNumBlocks()
Copyright © 2015. All rights reserved.