org.exist.numbering
Class DLNBase

java.lang.Object
  org.exist.numbering.DLNBase

All Implemented Interfaces:

java.lang.Comparable

Direct Known Subclasses:

DLN

public class DLNBase

extends java.lang.Object

implements java.lang.Comparable

Base class representing a node id in the form of a dynamic level number (DLN). See DLN. DLNBase handles the efficient binary encoding of node ids. Level values are stored consecutively, using a fixed prefix free encoding. The number of units to be used for encoding a single level value is dynamically adjusted. We start with one unit and use its n - 1 lower bits. If the number exceeds the lower bits, we add another unit and set the highest bit to 1. This process is repeated for larger numbers. As a result, the first 1 bits of a level id indicate the number of fixed-size units used for encoding a level id. We thus don't need separator bits between the units themselves.

Author:

wolf

Field Summary

protected int	bitIndex
protected byte[]	bits
static int	BITS_PER_UNIT The default number of bits used per fixed size unit.
protected static int[]	PER_COMPONENT_SIZE Lists the maximum number that can be encoded by a given number of units.
protected static int	UNIT_SHIFT

Constructor Summary

	DLNBase()
protected	DLNBase(byte[] data, int nbits)
	DLNBase(DLNBase dln)
	DLNBase(int units, byte[] data, int startOffset)
	DLNBase(VariableByteInput is)

Method Summary

void	addLevelId(int levelId) Adds a new level to the node id, using levelId as initial value.
protected static int	bitWidth(int units) Calculates the number of bits available in a bit set that uses the given number of units.
int	compareTo(DLNBase other)
int	compareTo(java.lang.Object obj)
java.lang.String	debug()
int	getLevelCount() Returns the number of level in this id, which corresponds to the depth at which the node occurs within the node tree.
int	getLevelId(int startBit) Returns the id starting at offset.
int[]	getLevelIds() Return all level ids converted to int.
protected static int	getUnitsRequired(int levelId) Calculates the minimum number of units that would be required to properly encode the given integer.
void	incrementLevelId() Increments the last level id by one.
protected int	lastLevelOffset() Find the last level in the id and return its offset.
void	serialize(byte[] data, int offset)
protected void	setCurrentLevelId(int levelId) Set the level id for the last level that has been written.
void	setLevelId(int offset, int levelId) Set the level id which starts at offset to the given id value.
int	size() Returns the size of this id by counting the bits used to encode it.
boolean	startsWith(DLNBase other)
java.lang.String	toBitString()
java.lang.String	toString()
byte	units() Returns the number of units currently used to encode the id.

Methods inherited from class java.lang.Object

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

Field Detail

BITS_PER_UNIT

public static final int BITS_PER_UNIT

The default number of bits used per fixed size unit.

See Also:

Constant Field Values

PER_COMPONENT_SIZE

protected static final int[] PER_COMPONENT_SIZE

Lists the maximum number that can be encoded by a given number of units. PER_COMPONENT_SIZE[0] corresponds to 1 unit used, PER_COMPONENT_SIZE[1] to 2 units, and so on. With BITS_PER_UNIT = 4, the largest number to be encoded by 1 unit is 7, for 2 units it's 71, for 3 units 583 ...

UNIT_SHIFT

protected static final int UNIT_SHIFT

See Also:

Constant Field Values

bits

protected byte[] bits

bitIndex

protected int bitIndex

Constructor Detail

DLNBase

public DLNBase()

DLNBase

public DLNBase(DLNBase dln)

DLNBase

public DLNBase(int units,
               byte[] data,
               int startOffset)

DLNBase

protected DLNBase(byte[] data,
                  int nbits)

DLNBase

public DLNBase(VariableByteInput is)
        throws java.io.IOException

Method Detail

setLevelId

public void setLevelId(int offset,
                       int levelId)

Set the level id which starts at offset to the given id value.

Parameters:

offset -

levelId -

addLevelId

public void addLevelId(int levelId)

Adds a new level to the node id, using levelId as initial value.

Parameters:

levelId - initial value

incrementLevelId

public void incrementLevelId()

Increments the last level id by one.

setCurrentLevelId

protected void setCurrentLevelId(int levelId)

Set the level id for the last level that has been written. The data array will be resized automatically if the bit set is too small to encode the id.

Parameters:

levelId -

getLevelId

public int getLevelId(int startBit)

Returns the id starting at offset.

Parameters:

startBit -

Returns:

the level id

units

public byte units()

Returns the number of units currently used to encode the id. The size of a single unit is given by BITS_PER_UNIT.

Returns:

the number of units

size

public int size()

Returns the size of this id by counting the bits used to encode it.

Returns:

the size in bits

getLevelCount

public int getLevelCount()

Returns the number of level in this id, which corresponds to the depth at which the node occurs within the node tree.

Returns:

the number of levels in this id

getLevelIds

public int[] getLevelIds()

Return all level ids converted to int.

Returns:

all level ids in this node id.

lastLevelOffset

protected int lastLevelOffset()

Find the last level in the id and return its offset.

Returns:

start-offset of the last level id.

startsWith

public boolean startsWith(DLNBase other)

bitWidth

protected static int bitWidth(int units)

Calculates the number of bits available in a bit set that uses the given number of units. These are the bits that can be actually used for the id, not including the trailing address bits.

Parameters:

units -

Returns:

number of bits available

getUnitsRequired

protected static int getUnitsRequired(int levelId)

Calculates the minimum number of units that would be required to properly encode the given integer.

Parameters:

levelId - the integer to encode in the level id

Returns:

number of units required

serialize

public void serialize(byte[] data,
                      int offset)

compareTo

public int compareTo(DLNBase other)

compareTo

public int compareTo(java.lang.Object obj)

Specified by:

compareTo in interface java.lang.Comparable

debug

public java.lang.String debug()

toString

public java.lang.String toString()

toBitString

public java.lang.String toBitString()