Package org.ddogleg.struct

Class BigDogArrayBase<Array>

java.lang.Object
org.ddogleg.struct.BigDogArrayBase<Array>
Direct Known Subclasses:
BigDogArray, BigDogArray_B, BigDogArray_F32, BigDogArray_F64, BigDogArray_I32, BigDogArray_I64, BigDogArray_I8
public abstract class BigDogArrayBase<Array> extends Object
A growable array that is composed of internal blocks. This is intended to reduce overhead when growing a very large array. Contrast this with DogArray for which its entire internal array needs to be copied when growing. While more complex and in some classes slightly slower, the approach employed here is much more memory and speed efficient while growing. See BigDogGrowth for a description of different growth strategies. When operations are used which add/append to the end of the array then extra room is typically added, if a grow strategy is employed. This is done to avoid excessive amount of memory copy operations.

  • Field Details

    • DEFAULT_BLOCK_SIZE

      public static final int DEFAULT_BLOCK_SIZE
      Default block size. It's assumed that this is used in fairly large arrays.
      See Also:

    • blocks

      protected final FastArray<Array> blocks
      Storage for blocks. Note that the size is always the number of elements with non-null values.

    • blockSize

      protected final int blockSize
      Number of elements in a full block

    • size

      public int size
      Number of elements in the array being used. Know what you're doing before modifying.

    • growth

      protected final BigDogGrowth growth
      Approach used for growth. See enum for a description

    • generatorArray

      public final BigDogArrayBase.NewArray<Array> generatorArray

    • initializeArray

      public final BigDogArrayBase.AssignNewArrayElements<Array> initializeArray

  • Constructor Details

  • Method Details

    • isIndexOutOfBounds

      public boolean isIndexOutOfBounds(int index)
      Returns true if the specified array index is outside the allowed value range

    • reset

      public void reset()
      Sets the array size to zero. No memory is freed.

    • reserve

      public void reserve(int desiredSize)
      Ensures that the internal data can store up to this number of elements before needing to allocate more memory. No extra data is added and this function is only recommended when the array has a known max size.

    • allocate

      protected void allocate(int desiredSize, boolean saveValues, boolean addExtra)
      Allocate more memory so that an array of the specified desiredSize can be stored. Optionally copy old values into new arrays when growing
      Parameters:
      desiredSize - New size of internal array, not just a single block.
      saveValues - If old values should be copied.
      addExtra - If using a grow strategy, is this a case where it should add extra elements or do the exact request?

    • resize

      public void resize(int desiredSize)
      Either increased or decreases the array size. If it's increased then the new elements will be filled with undefined values, depending on their previous state.
      Parameters:
      desiredSize - (Input) New array size

    • append

      public void append(Array array, int offset, int length)
      Adds the input array to the end of this array.
      Parameters:
      array - (Input) Array which is to be copied
      offset - (Input) First element in the array which is to be copied
      length - (Input) Number of elements which are to be copied

    • removeTail

      public void removeTail()
      Shrinks the array by one

    • removeSwap

      public abstract void removeSwap(int index)
      Removes an element in O(1) time by swapping the specified index with the last index and resizing to size -1.

    • setArray

      public void setArray(long location, Array array, int offset, int length)
      Copies the passed in array into this array at the specified location
      Parameters:
      location - (Input) First element that the array is to be inserted at
      array - (Input) Array which is to be copied in
      offset - (Input) Offset inside of array that it should be copied from
      length - (Input) Number of elements in array to copy

    • processByBlock

      public void processByBlock(int idx0, int idx1, BigDogArrayBase.FunctionEachRange<Array> op)
      Passes in array elements to the operator one block at a time. What's given to the operator is the first index in the block it should process, the last (exclusive) index in the block, and the number of elements offset from the original range requested.
      Parameters:
      idx0 - (Input) First index, inclusive.
      idx1 - (Input) Last index, exclusive.
      op - The operator which processes the values

    • getDesiredBlocks

      protected final int getDesiredBlocks(int desiredSize)
      Returns the number of blocks needed to store an array of the specified size

    • isValidStructure

      public boolean isValidStructure()
      Performs an internal check to make sure all data structures and values are internally consistent. Used for debugging and paranoia.

    • getTotalAllocation

      public int getTotalAllocation()
      Returns the number of elements which have been allocated. This array size has to be less than or equal to this number\

    • blockArrayLength

      protected int blockArrayLength(int block)

    • setInitialBlockSize

      public void setInitialBlockSize(int initialBlockSize)
      Assigns a new initial block size. The value is adjusted to ensure that it is valid. Can't be larger than a block or less than 1.

    • arrayLength

      protected abstract int arrayLength(Array array)