public class Block extends Object
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.
Modifier and Type | Field and 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. |
Block |
nextBlock |
protected Block |
nextInWorklist |
protected Block |
nextTouched |
int |
ptr
The current pointer, i.e., the delimiter between elements of this block which were found to
belong to a potential sub-class of this block, and those that do not or have not been checked.
|
Constructor and Description |
---|
Block(int low,
int high,
int id,
Block next)
Constructor.
|
Modifier and Type | Method and Description |
---|---|
boolean |
isEmpty()
Checks whether this block is empty.
|
int |
size()
Retrieves the size of this block.
|
Block |
split(int newId)
Splits this block, if applicable.
|
public int low
PaigeTarjan.blockData
array.public int ptr
public int high
PaigeTarjan.blockData
array,
plus one.protected Block nextInWorklist
protected Block nextTouched
public Block nextBlock
public int id
public Block(int low, int high, int id, Block next)
low
- the low index of this block's data in the PaigeTarjan.blockData
arrayhigh
- the high index of this block's data in the PaigeTarjan.blockData
arrayid
- the ID of this blocknext
- the next block in the block listpublic int size()
public boolean isEmpty()
true
if this block is empty, false
otherwisepublic Block split(int newId)
null
is returned.
A new block (the split result) is created if both
and ptr
> low
. This new block will contain either the elements
between ptr
< high
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
.
newId
- the ID of the newly created block, if applicableCopyright © 2015. All rights reserved.