Class PaigeTarjan
- java.lang.Object
-
- net.automatalib.util.partitionrefinement.PaigeTarjan
-
public class PaigeTarjan extends Object
An implementation of the Paige/Tarjan partition refinement algorithm.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
Theint
) array(s), to achieve maximal cache efficiency. The layout 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, thePaigeTarjanExtractors
class provides methods for transforming the resulting data structure.
-
-
Nested Class Summary
Nested Classes Modifier and Type Class Description static class
PaigeTarjan.WorklistPolicy
Determines how the worklist is managed, i.e., where newly created blocks are inserted.
-
Field Summary
Fields Modifier and Type Field 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 between0
andnumStates
) 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 theblockData
array.int
posDataLow
The lowest index storing position data in theposData
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 thepredOfsData
array.
-
Constructor Summary
Constructors Constructor Description PaigeTarjan()
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description Iterable<Block>
blockList()
Retrieves anIterable
that provides the iterator returned byblockListIterator()
.Iterator<Block>
blockListIterator()
Retrieves an iterator for iterating over all blocks in the block list.void
canonizeBlocks()
Iterates over the currentblock list
and sets every block'slow
andhigh
pointer to the accumulated sum of its own high pointer and its preceding blocks' high pointers, effectively reducing each block to a single representative padded by its previous range.void
computeCoarsestStablePartition()
Refines the partition until it stabilizes.Block
createBlock()
Creates a new block.Block[]
createBlockForStateMap()
Creates theblockForState
mapping from the blocks in the block list, and the contents of theblockData
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 ablockForState
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.
-
-
-
Field Detail
-
numInputs
public int numInputs
The number of input symbols.
-
numStates
public int numStates
The number of states.
-
blockData
public int[] blockData
The array storing the raw block data, i.e., the states contained in a certain block. It is assumed that the positionsBlock.low
andBlock.high
refer to this array.
-
posData
public int[] posData
The array storing the position data, i.e., for each state, its index in theblockData
array.The layout of this array is assumed to be the following: for the state
i
, where0 <= i <
, the index ofnumStates
i
inblockData
is
.posData
[posDataLow
+ i]
-
posDataLow
public int posDataLow
The lowest index storing position data in theposData
array.
-
predOfsData
public 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. The offsets are assumed to refer to thepredData
array.The layout of this array is assumed to be the following: for state
i
and input symbolj
, where0 <= i <
andnumStates
0 <= j <
, the offset (in thenumInputs
predData
array) of the firstj
-predecessor ofi
is
, and the lastpredOfsData
[predOfsDataLow
+ j*numStates
+ i]j
-predecessor ofi
is
. Note that this requires the indexpredOfsData
[predOfsDataLow
+ j*numStates
+ i + 1] - 1
to be valid, and the contents of thepredOfsDataLow
+numInputs
*numStates
predOfsData
array at this index must be the highest offset of any predecessor plus one.
-
predOfsDataLow
public int predOfsDataLow
The lowest index storing predecessor offset data in thepredOfsData
array.
-
predData
public int[] predData
The array storing the predecessor data, i.e., for each state and input symbol, a list of the respective predecessors.The layout of this array is assumed to be the following: for state
i
and input symbolj
, where0 <= i <
andnumStates
0 <= j <
, thenumInputs
j
-predecessors ofi
are the elements ofpredData
from index
, inclusive, to indexpredOfsData
[predOfsDataLow
+ j*numStates
+ i]
, exclusive.predOfsData
[predOfsDataLow
+ j*numStates
+ i + 1]
-
-
Method Detail
-
setSize
public void setSize(int numStates, int numInputs)
-
setBlockForState
public void setBlockForState(Block[] blockForState)
-
setBlockData
public void setBlockData(int[] blockData)
-
setPosData
public void setPosData(int[] posData, int posDataLow)
-
setPredOfsData
public void setPredOfsData(int[] predOfsData, int predOfsDataLow)
-
setPredData
public void setPredData(int[] predData)
-
removeEmptyBlocks
public void removeEmptyBlocks()
Removes all blocks which are empty from the block list. TheIDs
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.
-
initBlockForStateMap
public void initBlockForStateMap()
Automatically creates ablockForState
mapping, and sets it as the current one.
-
createBlockForStateMap
public Block[] createBlockForStateMap()
Creates theblockForState
mapping from the blocks in the block list, and the contents of theblockData
array.- Returns:
- a
blockForState
mapping consistent with theblockData
-
initWorklist
public void initWorklist(boolean addAll)
Initializes the worklist from the block list. This assumes that the worklist is empty.If
addAll
istrue
, all blocks from the block list will be added to the worklist. Otherwise, all but the largest block will be added.- Parameters:
addAll
- controls if all blocks are added to the worklist, or all but the largest.
-
computeCoarsestStablePartition
public void computeCoarsestStablePartition()
Refines the partition until it stabilizes.
-
createBlock
public Block createBlock()
- Returns:
- a newly created block.
-
canonizeBlocks
public void canonizeBlocks()
Iterates over the currentblock list
and sets every block'slow
andhigh
pointer to the accumulated sum of its own high pointer and its preceding blocks' high pointers, effectively reducing each block to a single representative padded by its previous range.
-
getBlockForState
public Block getBlockForState(int id)
Retrieves the corresponding block for a given state (ID).- Parameters:
id
- the state ID- Returns:
- the block containing the specified state
-
getRepresentative
public int getRepresentative(Block b)
Retrieves a representative state from the given block. This method behaves deterministically.- Parameters:
b
- the block- Returns:
- a representative state in the specified block
-
statesInBlockIterator
public PrimitiveIterator.OfInt statesInBlockIterator(Block b)
Retrieves an iterator for the contents of the given block.- Parameters:
b
- the block- Returns:
- an iterator for the contents of the specified block
-
statesInBlockSpliterator
public Spliterator.OfInt statesInBlockSpliterator(Block b)
Retrieves a spliterator for the contents of the given block.- Parameters:
b
- the block- Returns:
- a spliterator for the contents of the specified block
-
blockListIterator
public Iterator<Block> blockListIterator()
Retrieves an iterator for iterating over all blocks in the block list.- Returns:
- an iterator for iterating over all blocks
-
blockList
public Iterable<Block> blockList()
Retrieves anIterable
that provides the iterator returned byblockListIterator()
.- Returns:
- an
Iterable
for iterating over all blocks
-
getNumBlocks
public int getNumBlocks()
Retrieves the total number of blocks in the block list.- Returns:
- the total number of blocks
-
-