com.devexperts.util

Class ArrayUtil

java.lang.Object

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

Fields

Modifier and Type	Field and Description
static int	MAX_CAPACITY Max allowed array size.
static int	MIN_CAPACITY This is a recommended minimal capacity for arrays.

Method Summary

Modifier and Type	Method and Description
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 implementation 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. While iterating 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.