|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Objectcom.devexperts.util.ArrayUtil
public class ArrayUtil
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
|
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 |
---|
public static final int MIN_CAPACITY
public static final int MAX_CAPACITY
Integer.MAX_VALUE
minus one million.
Method Detail |
---|
public static int findFreeIndex(Object[] a, int lastFoundIndex, int minIndex)
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.
a
- the array.lastFoundIndex
- last result of this method.
On the first invocation is must be equal to minIndex
.minIndex
- Minimal allowed 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.public static <T> T[] grow(T[] a, int minCapacity)
T
- Type of the array components.a
- the array.minCapacity
- minimal size of the resulting array. Pass 0 if not needed.
a
,
has at least MIN_CAPACITY
elements, and at least
minCapacity
elements, with all old elements in their old places.public static boolean[] grow(boolean[] a, int minCapacity)
a
- the array.minCapacity
- minimal size of the resulting array. Pass 0 if not needed.
a
,
has at least MIN_CAPACITY
elements, and at least
minCapacity
elements, with all old elements in their old places.public static byte[] grow(byte[] a, int minCapacity)
a
- the array.minCapacity
- minimal size of the resulting array. Pass 0 if not needed.
a
,
has at least MIN_CAPACITY
elements, and at least
minCapacity
elements, with all old elements in their old places.public static char[] grow(char[] a, int minCapacity)
a
- the array.minCapacity
- minimal size of the resulting array. Pass 0 if not needed.
a
,
has at least MIN_CAPACITY
elements, and at least
minCapacity
elements, with all old elements in their old places.public static int[] grow(int[] a, int minCapacity)
a
- the array.minCapacity
- minimal size of the resulting array. Pass 0 if not needed.
a
,
has at least MIN_CAPACITY
elements, and at least
minCapacity
elements, with all old elements in their old places.public static long[] grow(long[] a, int minCapacity)
a
- the array.minCapacity
- minimal size of the resulting array. Pass 0 if not needed.
a
,
has at least MIN_CAPACITY
elements, and at least
minCapacity
elements, with all old elements in their old places.
|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |