org.apache.xml.utils
Class SuballocatedByteVector

java.lang.Object
  extended byorg.apache.xml.utils.SuballocatedByteVector

public class SuballocatedByteVector
extends Object

A very simple table that stores a list of byte. 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. If an element has not been set (because we skipped it), its value will initially be 0. Shortening the vector does not clear old storage; if you then skip values and setElementAt a higher index again, you may see old data reappear in the truncated-and-restored section. Doing anything else would have performance costs.


Field Summary
protected  int m_blocksize
          Size of blocks to allocate
protected  int m_firstFree
          Number of bytes in array
protected  byte[][] m_map
          Array of arrays of bytes
protected  byte[] m_map0
          "Shortcut" handle to m_map[0]
protected  int m_numblocks
          Number of blocks to (over)allocate by
 
Constructor Summary
SuballocatedByteVector()
          Default constructor.
SuballocatedByteVector(int blocksize)
          Construct a ByteVector, using the given block size.
SuballocatedByteVector(int blocksize, int increaseSize)
          Construct a ByteVector, using the given block size.
 
Method Summary
 void addElement(byte value)
          Append a byte onto the vector.
private  void addElements(byte value, int numberOfElements)
          Append several byte values onto the vector.
private  void addElements(int numberOfElements)
          Append several slots onto the vector, but do not set the values.
private  boolean contains(byte s)
          Tell if the table contains the given node.
 byte elementAt(int i)
          Get the nth element.
 int indexOf(byte 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(byte 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(byte value, int at)
          Inserts the specified node in this vector at the specified index.
private  int lastIndexOf(byte 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(byte 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(byte value, int at)
          Sets the component at the specified index of this vector to be the specified object.
private  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_numblocks

protected int m_numblocks
Number of blocks to (over)allocate by


m_map

protected byte[][] m_map
Array of arrays of bytes


m_firstFree

protected int m_firstFree
Number of bytes in array


m_map0

protected byte[] m_map0
"Shortcut" handle to m_map[0]

Constructor Detail

SuballocatedByteVector

public SuballocatedByteVector()
Default constructor. Note that the default block size is very small, for small lists.


SuballocatedByteVector

public SuballocatedByteVector(int blocksize)
Construct a ByteVector, using the given block size.

Parameters:
blocksize - Size of block to allocate

SuballocatedByteVector

public SuballocatedByteVector(int blocksize,
                              int increaseSize)
Construct a ByteVector, using the given block size.

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

private void setSize(int sz)
Set the length of the list.

Returns:
length of the list

addElement

public void addElement(byte value)
Append a byte onto the vector.

Parameters:
value - Byte to add to the list

addElements

private void addElements(byte value,
                         int numberOfElements)
Append several byte values onto the vector.

Parameters:
value - Byte 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.


insertElementAt

private void insertElementAt(byte 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 - Byte to insert
at - Index of where to insert

removeAllElements

public void removeAllElements()
Wipe it out.


removeElement

private boolean removeElement(byte 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 - Byte to remove from array
Returns:
True if the byte 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:
at - index of where to remove a byte

setElementAt

public void setElementAt(byte 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.


elementAt

public byte 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.

contains

private boolean contains(byte 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(byte 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(byte 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(byte 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.