Package net.automatalib.util.partitionrefinement

Class Block

java.lang.Object

net.automatalib.util.partitionrefinement.Block

public class Block
extends Object

A block (i.e., partition class) that is maintained during the Paige/Tarjan partition refinement algorithm (see PaigeTarjan).

Like PaigeTarjan, this is a very low-level class that exposes a lot (almost all) of its fields directly. Care should be taken that instances of this class are not returned (in any form) to the API user, but are hidden behind a facade.

Field Summary

Fields

Modifier and Type	Field	Description
int	high	The index of the last element in this block in the PaigeTarjan.blockData array, plus one.
int	id
int	low	The index of the first element in this block in the PaigeTarjan.blockData array.
@Nullable Block	nextBlock
protected @Nullable Block	nextInWorklist
protected @Nullable Block	nextTouched
int	ptr	The current pointer, i.e., the delimiter between elements of this block which were found to belong to a potential subclass of this block, and those that do not or have not been checked.

Constructor Summary

Constructors

Constructor	Description
Block(int low, int high, int id, @Nullable Block next)	Constructor.

Method Summary

Modifier and Type	Method	Description
boolean	isEmpty()	Checks whether this block is empty.
int	size()	Retrieves the size of this block.
@Nullable Block	split(int newId)	Splits this block, if applicable.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

low

public int low

The index of the first element in this block in the PaigeTarjan.blockData array.

ptr

public int ptr

The current pointer, i.e., the delimiter between elements of this block which were found to belong to a potential subclass of this block, and those that do not or have not been checked.

This variable will be maintained such that either ptr == -1, or low <= ptr <= high.

high

public int high

The index of the last element in this block in the PaigeTarjan.blockData array, plus one.

nextBlock

public @Nullable Block nextBlock

id

public int id

nextInWorklist

protected @Nullable Block nextInWorklist

nextTouched

protected @Nullable Block nextTouched

Constructor Detail

Block

public Block(int low,
             int high,
             int id,
             @Nullable Block next)

Constructor. Creates a new block with the specified parameters.

Parameters:

low - the low index of this block's data in the PaigeTarjan.blockData array

high - the high index of this block's data in the PaigeTarjan.blockData array

id - the ID of this block

next - the next block in the block list

Method Detail

size

public int size()

Retrieves the size of this block.

Returns:

the size of this block

isEmpty

public boolean isEmpty()

Checks whether this block is empty.

Returns:

true if this block is empty, false otherwise

split

public @Nullable Block split(int newId)

Splits this block, if applicable. If this block cannot be split, null is returned.

A new block (the split result) is created if both ptr > low and ptr < high. This new block will contain either the elements between low (inclusive) and ptr (exclusive), or between ptr (inclusive) and high (exclusive), depending on whichever range is smaller. This block will be updated to contain the remaining elements.

When this method returns (regardless of whether a new block is created), the ptr field will have been reset to -1.

Preconditions: this.ptr != -1.

Parameters:

newId - the ID of the newly created block, if applicable

Returns:

a block