Package org.loboevolution.apache.xml.utils

Class SuballocatedIntVector

java.lang.Object
org.loboevolution.apache.xml.utils.SuballocatedIntVector
public class SuballocatedIntVector extends 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

    Fields
    Modifier and Type
    Field
    Description
    protected final 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 final int[]
    m_map0
    "Shortcut" handle to m_map[0].
    protected final int
    m_MASK
     
    protected final int
    m_numblocks
    The number of blocks to (over)allocate by
    protected int
    m_SHIFT
    Bitwise addressing (much faster than div/remainder
    protected static final int
    NUMBLOCKS_DEFAULT
    The default number of blocks to (over)allocate by

  • Constructor Summary

    Constructors
    Constructor
    Description
    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

    Modifier and Type
    Method
    Description
    void
    addElement(int value)
    Append a int onto the vector.
    int
    elementAt(int i)
    Get the nth element.
    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.
    void
    setElementAt(int value, int at)
    Sets the component at the specified index of this vector to be the specified object.
    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 Details

    • m_blocksize

      protected final int m_blocksize
      Size of blocks to allocate

    • m_SHIFT

      protected int m_SHIFT
      Bitwise addressing (much faster than div/remainder

    • m_MASK

      protected final int m_MASK

    • NUMBLOCKS_DEFAULT

      protected static final int NUMBLOCKS_DEFAULT
      The default number of blocks to (over)allocate by
      See Also:

    • m_numblocks

      protected final 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 final 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 Details

    • 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 Details

    • size

      public int size()
      Get the length of the list.
      Returns:
      length of the list

    • addElement

      public void addElement(int value)
      Append a int onto the vector.
      Parameters:
      value - Int to add to the list

    • 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:
      ArrayIndexOutOfBoundsException - if the index was _clearly_ unreasonable (negative, or past the highest block).
      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?

    • 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.