org.apache.xml.utils
Class SuballocatedIntVector

java.lang.Object
  org.apache.xml.utils.SuballocatedIntVector

public class SuballocatedIntVector
extends java.lang.Object

A very simple table that stores a list of int. Very similar API to our IntVector class (same API); different internal storage. This version uses an array-of-arrays solution. Read/write access is thus a bit slower than the simple IntVector, and basic storage is a trifle higher due to the top-level array -- but appending is O(1) fast rather than O(N**2) slow, which will swamp those costs in situations where long vectors are being built up. Known issues: Some methods are private because they haven't yet been tested properly. Retrieval performance is critical, since this is used at the core of the DTM model. (Append performance is almost as important.) That's pushing me toward just letting reads from unset indices throw exceptions or return stale data; safer behavior would have performance costs.

Field Summary

protected int	m_blocksize Size of blocks to allocate
protected int[]	m_buildCache "Shortcut" handle to most recently added row of m_map.
protected int	m_buildCacheStartIndex
protected int	m_firstFree Number of ints in array
protected int[][]	m_map Array of arrays of ints
protected int[]	m_map0 "Shortcut" handle to m_map[0].
protected int	m_MASK Bitwise addressing (much faster than div/remainder
protected int	m_numblocks The number of blocks to (over)allocate by
protected int	m_SHIFT Bitwise addressing (much faster than div/remainder
protected static int	NUMBLOCKS_DEFAULT The default number of blocks to (over)allocate by

Constructor Summary

SuballocatedIntVector()
Default constructor.

SuballocatedIntVector(int blocksize)
Construct a IntVector, using the given block size and the default number of blocks (32).

SuballocatedIntVector(int blocksize, int numblocks)
Construct a IntVector, using the given block size and number of blocks.

Method Summary

void	addElement(int value) Append a int onto the vector.
private void	addElements(int numberOfElements) Append several slots onto the vector, but do not set the values.
private void	addElements(int value, int numberOfElements) Append several int values onto the vector.
private boolean	contains(int s) Tell if the table contains the given node.
int	elementAt(int i) Get the nth element.
int[][]	getMap() Return the m_map double array
int[]	getMap0() Return the internal m_map0 array
int	indexOf(int elem) Searches for the first occurence of the given argument, beginning the search at index, and testing for equality using the equals method.
int	indexOf(int elem, int index) Searches for the first occurence of the given argument, beginning the search at index, and testing for equality using the equals method.
private void	insertElementAt(int value, int at) Inserts the specified node in this vector at the specified index.
private int	lastIndexOf(int elem) Searches for the first occurence of the given argument, beginning the search at index, and testing for equality using the equals method.
void	removeAllElements() Wipe it out.
private boolean	removeElement(int s) Removes the first occurrence of the argument from this vector.
private void	removeElementAt(int at) Deletes the component at the specified index.
void	setElementAt(int value, int at) Sets the component at the specified index of this vector to be the specified object.
void	setSize(int sz) Set the length of the list.
int	size() Get the length of the list.

Methods inherited from class java.lang.Object

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

Field Detail

m_blocksize

protected int m_blocksize

Size of blocks to allocate

m_SHIFT

protected int m_SHIFT

Bitwise addressing (much faster than div/remainder

m_MASK

protected int m_MASK

Bitwise addressing (much faster than div/remainder

NUMBLOCKS_DEFAULT

protected static final int NUMBLOCKS_DEFAULT

The default number of blocks to (over)allocate by

See Also:

Constant Field Values

m_numblocks

protected int m_numblocks

The number of blocks to (over)allocate by

m_map

protected int[][] m_map

Array of arrays of ints

m_firstFree

protected int m_firstFree

Number of ints in array

m_map0

protected int[] m_map0

"Shortcut" handle to m_map[0]. Surprisingly helpful for short vectors.

m_buildCache

protected int[] m_buildCache

"Shortcut" handle to most recently added row of m_map. Very helpful during construction.

m_buildCacheStartIndex

protected int m_buildCacheStartIndex

Constructor Detail

SuballocatedIntVector

public SuballocatedIntVector()

Default constructor. Note that the default block size is currently 2K, which may be overkill for small lists and undershootng for large ones.

SuballocatedIntVector

public SuballocatedIntVector(int blocksize,
                             int numblocks)

Construct a IntVector, using the given block size and number of blocks. For efficiency, we will round the requested size off to a power of two.

Parameters:

blocksize - Size of block to allocate

numblocks - Number of blocks to allocate

SuballocatedIntVector

public SuballocatedIntVector(int blocksize)

Construct a IntVector, using the given block size and the default number of blocks (32).

Parameters:

blocksize - Size of block to allocate

Method Detail

size

public int size()

Get the length of the list.

Returns:

length of the list

setSize

public void setSize(int sz)

Set the length of the list. This will only work to truncate the list, and even then it has not been heavily tested and may not be trustworthy.

addElement

public void addElement(int value)

Append a int onto the vector.

Parameters:

value - Int to add to the list

addElements

private void addElements(int value,
                         int numberOfElements)

Append several int values onto the vector.

Parameters:

value - Int to add to the list

addElements

private void addElements(int numberOfElements)

Append several slots onto the vector, but do not set the values. Note: "Not Set" means the value is unspecified.

Parameters:

numberOfElements - Int to add to the list

insertElementAt

private void insertElementAt(int value,
                             int at)

Inserts the specified node in this vector at the specified index. Each component in this vector with an index greater or equal to the specified index is shifted upward to have an index one greater than the value it had previously. Insertion may be an EXPENSIVE operation!

Parameters:

value - Int to insert

at - Index of where to insert

removeAllElements

public void removeAllElements()

Wipe it out. Currently defined as equivalent to setSize(0).

removeElement

private boolean removeElement(int s)

Removes the first occurrence of the argument from this vector. If the object is found in this vector, each component in the vector with an index greater or equal to the object's index is shifted downward to have an index one smaller than the value it had previously.

Parameters:

s - Int to remove from array

Returns:

True if the int was removed, false if it was not found

removeElementAt

private void removeElementAt(int at)

Deletes the component at the specified index. Each component in this vector with an index greater or equal to the specified index is shifted downward to have an index one smaller than the value it had previously.

Parameters:

i - index of where to remove and int

setElementAt

public void setElementAt(int value,
                         int at)

Sets the component at the specified index of this vector to be the specified object. The previous component at that position is discarded. The index must be a value greater than or equal to 0 and less than the current size of the vector.

Parameters:

value - object to set

at - Index of where to set the object

elementAt

public int elementAt(int i)

Get the nth element. This is often at the innermost loop of an application, so performance is critical.

Parameters:

i - index of value to get

Returns:

value at given index. If that value wasn't previously set, the result is undefined for performance reasons. It may throw an exception (see below), may return zero, or (if setSize has previously been used) may return stale data.

Throws:

java.lang.ArrayIndexOutOfBoundsException - if the index was _clearly_ unreasonable (negative, or past the highest block).

java.lang.NullPointerException - if the index points to a block that could have existed (based on the highest index used) but has never had anything set into it. %REVIEW% Could add a catch to create the block in that case, or return 0. Try/Catch is _supposed_ to be nearly free when not thrown to. Do we believe that? Should we have a separate safeElementAt?

contains

private boolean contains(int s)

Tell if the table contains the given node.

Parameters:

s - object to look for

Returns:

true if the object is in the list

indexOf

public int indexOf(int elem,
                   int index)

Searches for the first occurence of the given argument, beginning the search at index, and testing for equality using the equals method.

Parameters:

elem - object to look for

index - Index of where to begin search

Returns:

the index of the first occurrence of the object argument in this vector at position index or later in the vector; returns -1 if the object is not found.

indexOf

public int indexOf(int elem)

Searches for the first occurence of the given argument, beginning the search at index, and testing for equality using the equals method.

Parameters:

elem - object to look for

Returns:

the index of the first occurrence of the object argument in this vector at position index or later in the vector; returns -1 if the object is not found.

lastIndexOf

private int lastIndexOf(int elem)

Searches for the first occurence of the given argument, beginning the search at index, and testing for equality using the equals method.

Parameters:

elem - Object to look for

Returns:

the index of the first occurrence of the object argument in this vector at position index or later in the vector; returns -1 if the object is not found.

getMap0

public final int[] getMap0()

Return the internal m_map0 array

Returns:

the m_map0 array

getMap

public final int[][] getMap()

Return the m_map double array

Returns:

the internal map of array of arrays