com.devexperts.util
Class ArrayUtil

java.lang.Object
  extended by com.devexperts.util.ArrayUtil

public class ArrayUtil
extends Object

Helper methods to work with O(1) array-based data structures.

To implement O(1) array of indexed elements use the following pattern of code:

 private static final int MIN_ELEMENT_INDEX = 0; // use 1 to leave elements[0] null
 private Element[] elements = new Element[ArrayUtil.MIN_CAPACITY];
 private int lastElementIndex = MIN_ELEMENT_INDEX;

 void addElement(Element element) {
     lastElementIndex = ArrayUtil.findFreeIndex(elements, lastElementIndex, MIN_ELEMENT_INDEX);
     if (lastElementIndex >= elements.length)
         elements = grow(elements, 0);
     elements[lastElementIndex] = element;
 }
 


Field Summary
static int MAX_CAPACITY
          Max allowed array size.
static int MIN_CAPACITY
          This is a recommended minimal capacity for arrays.
 
Method Summary
static int findFreeIndex(Object[] a, int lastFoundIndex, int minIndex)
          Finds free (non-occupied) index in an array in such a way, that amortized time to allocate an index is O(1).
static boolean[] grow(boolean[] a, int minCapacity)
          Allocates new array with at least double the size of an existing one, preserving all data from an existing array.
static byte[] grow(byte[] a, int minCapacity)
          Allocates new array with at least double the size of an existing one, preserving all data from an existing array.
static char[] grow(char[] a, int minCapacity)
          Allocates new array with at least double the size of an existing one, preserving all data from an existing array.
static int[] grow(int[] a, int minCapacity)
          Allocates new array with at least double the size of an existing one, preserving all data from an existing array.
static long[] grow(long[] a, int minCapacity)
          Allocates new array with at least double the size of an existing one, preserving all data from an existing array.
static
<T> T[]
grow(T[] a, int minCapacity)
          Allocates new array with at least double the size of an existing one, preserving all data from an existing array.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

MIN_CAPACITY

public static final int MIN_CAPACITY
This is a recommended minimal capacity for arrays.

See Also:
Constant Field Values

MAX_CAPACITY

public static final int MAX_CAPACITY
Max allowed array size. For safety, it is equal to Integer.MAX_VALUE minus one million.

See Also:
Constant Field Values
Method Detail

findFreeIndex

public static int findFreeIndex(Object[] a,
                                int lastFoundIndex,
                                int minIndex)
Finds free (non-occupied) index in an array in such a way, that amortized time to allocate an index is O(1). This implementations looks for an index i such that a[i] == null starting from the given lastFreeIndex and then cycles to the beginning of array where it starts from minIndex. On cycle it counts the number of free indices in array. If less than a quarter of indices a free then a.length is returned to indicate that array shall be reallocated to a larger size.

Parameters:
a - the array.
lastFoundIndex - last result of this method. On the first invocation is must be equal to minIndex.
minIndex - Minimal allowed index.
Returns:
an index i, such that i >= minIndex && a[i] == null || i == a.length. The result of a.length indicates that array shall be reallocated with grow(Object[], int) method.

grow

public static <T> T[] grow(T[] a,
                           int minCapacity)
Allocates new array with at least double the size of an existing one, preserving all data from an existing array.

Type Parameters:
T - Type of the array components.
Parameters:
a - the array.
minCapacity - minimal size of the resulting array. Pass 0 if not needed.
Returns:
New array that is at least twice as large as a, has at least MIN_CAPACITY elements, and at least minCapacity elements, with all old elements in their old places.

grow

public static boolean[] grow(boolean[] a,
                             int minCapacity)
Allocates new array with at least double the size of an existing one, preserving all data from an existing array.

Parameters:
a - the array.
minCapacity - minimal size of the resulting array. Pass 0 if not needed.
Returns:
New array that is at least twice as large as a, has at least MIN_CAPACITY elements, and at least minCapacity elements, with all old elements in their old places.

grow

public static byte[] grow(byte[] a,
                          int minCapacity)
Allocates new array with at least double the size of an existing one, preserving all data from an existing array.

Parameters:
a - the array.
minCapacity - minimal size of the resulting array. Pass 0 if not needed.
Returns:
New array that is at least twice as large as a, has at least MIN_CAPACITY elements, and at least minCapacity elements, with all old elements in their old places.

grow

public static char[] grow(char[] a,
                          int minCapacity)
Allocates new array with at least double the size of an existing one, preserving all data from an existing array.

Parameters:
a - the array.
minCapacity - minimal size of the resulting array. Pass 0 if not needed.
Returns:
New array that is at least twice as large as a, has at least MIN_CAPACITY elements, and at least minCapacity elements, with all old elements in their old places.

grow

public static int[] grow(int[] a,
                         int minCapacity)
Allocates new array with at least double the size of an existing one, preserving all data from an existing array.

Parameters:
a - the array.
minCapacity - minimal size of the resulting array. Pass 0 if not needed.
Returns:
New array that is at least twice as large as a, has at least MIN_CAPACITY elements, and at least minCapacity elements, with all old elements in their old places.

grow

public static long[] grow(long[] a,
                          int minCapacity)
Allocates new array with at least double the size of an existing one, preserving all data from an existing array.

Parameters:
a - the array.
minCapacity - minimal size of the resulting array. Pass 0 if not needed.
Returns:
New array that is at least twice as large as a, has at least MIN_CAPACITY elements, and at least minCapacity elements, with all old elements in their old places.


Copyright © 2013 Devexperts. All Rights Reserved.