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) |
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 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 void initBlockForStateMap()
blockForState
mapping, and sets it as the current one.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 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 PrimitiveIterator.OfInt statesInBlockIterator(Block b)
b
- the blockpublic Spliterator.OfInt statesInBlockSpliterator(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 © 2020. All rights reserved.