Java/Collections Data Structure/Auto Growth Array
Содержание
- 1 Adds all the elements of the given arrays into a new array.
- 2 Append the given Object to the given array
- 3 ArrayList of boolean primitives
- 4 ArrayList of byte primitives
- 5 ArrayList of char primitives
- 6 ArrayList of double primitives
- 7 ArrayList of float primitives
- 8 ArrayList of int primitives
- 9 ArrayList of long primitives
- 10 ArrayList of short primitives
- 11 A two dimensional Vector
- 12 Auto Size Array
- 13 A variable length Double Array: expanding and contracting its internal storage array as elements are added and removed.
- 14 Dynamic Int Array
- 15 Dynamic Long Array
- 16 Extensible vector of bytes
- 17 Fast Array
- 18 Growable int[]
- 19 Growable String array with type specific access methods.
- 20 Int Array
- 21 Int Array List
- 22 Int Vector
- 23 Int Vector (from java-objects-database)
- 24 Lazy List creation based on ArrayList
- 25 Long Vector
- 26 Simple object pool
- 27 Your own auto-growth Array
Adds all the elements of the given arrays into a new array.
<source lang="java">
/* Copyright 2004 The Apache Software Foundation
* * Licensed under the Apache License, Version 2.0 (the "License"); * you may not use this file except in compliance with the License. * You may obtain a copy of the License at * * http://www.apache.org/licenses/LICENSE-2.0 * * Unless required by applicable law or agreed to in writing, software * distributed under the License is distributed on an "AS IS" BASIS, * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. * See the License for the specific language governing permissions and * limitations under the License. */
import java.lang.reflect.Array;
/**
*Operations on arrays, primitive arrays (like int[]) and
* primitive wrapper arrays (like Integer[]).
**
This class tries to handle null input gracefully.
* An exception will not be thrown for a null
* array input. However, an Object array that contains a null
* element may throw an exception. Each method documents its behaviour.
* * @author Stephen Colebourne * @author Moritz Petersen * @author * @author Maarten Coene * @since 2.0 * @version $Id: ArrayUtils.java 632503 2008-03-01 00:21:52Z ggregory $ */
public class Main {
/***
Adds all the elements of the given arrays into a new array.
*The new array contains all of the element of array1 followed
* by all of the elements array2. When an array is returned, it is always
* a new array.
**
* ArrayUtils.addAll(null, null) = null * ArrayUtils.addAll(array1, null) = cloned copy of array1 * ArrayUtils.addAll(null, array2) = cloned copy of array2 * ArrayUtils.addAll([], []) = [] * ArrayUtils.addAll([null], [null]) = [null, null] * ArrayUtils.addAll(["a", "b", "c"], ["1", "2", "3"]) = ["a", "b", "c", "1", "2", "3"] *
* * @param array1 the first array whose elements are added to the new array, may be*null* @param array2 the second array whose elements are added to the new array, may benull* @return The new array,nullifnullarray inputs. * The type of the new array is the type of the first array. * @since 2.1 */ public static Object[] addAll(Object[] array1, Object[] array2) { if (array1 == null) { return clone(array2); } else if (array2 == null) { return clone(array1); } Object[] joinedArray = (Object[]) Array.newInstance(array1.getClass().getComponentType(), array1.length + array2.length); System.arraycopy(array1, 0, joinedArray, 0, array1.length); System.arraycopy(array2, 0, joinedArray, array1.length, array2.length); return joinedArray; } /**
Shallow clones an array returning a typecast result and handling
* null.
**
The objects in the array are not cloned, thus there is no special * handling for multi-dimensional arrays.
**
This method returns null for a null input array.
* * @param array the array to shallow clone, may benull* @return the cloned array,nullifnullinput */ public static Object[] clone(Object[] array) { if (array == null) { return null; } return (Object[]) array.clone(); }
}
</source>
Append the given Object to the given array
<source lang="java">
import java.lang.reflect.Array; import java.util.Arrays; /*
* Copyright 2002-2007 the original author or authors. * * Licensed under the Apache License, Version 2.0 (the "License"); * you may not use this file except in compliance with the License. * You may obtain a copy of the License at * * http://www.apache.org/licenses/LICENSE-2.0 * * Unless required by applicable law or agreed to in writing, software * distributed under the License is distributed on an "AS IS" BASIS, * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. * See the License for the specific language governing permissions and * limitations under the License. */
//Revised from springframework /**
* Miscellaneous object utility methods. Mainly for internal use within the * framework; consider Jakarta"s Commons Lang for a more comprehensive suite * of object utilities. * * @author Juergen Hoeller * @author Keith Donald * @author Rod Johnson * @author Rob Harrop * @author Alex Ruiz * @since 19.03.2004 * @see org.apache.rumons.lang.ObjectUtils */
abstract class ObjectUtils {
private static final int INITIAL_HASH = 7;
private static final int MULTIPLIER = 31;
private static final String EMPTY_STRING = "";
private static final String NULL_STRING = "null";
private static final String ARRAY_START = "{";
private static final String ARRAY_END = "}";
private static final String EMPTY_ARRAY = ARRAY_START + ARRAY_END;
private static final String ARRAY_ELEMENT_SEPARATOR = ", ";
/**
* Return whether the given array is empty: that is, null
* or of zero length.
* @param array the array to check
* @return whether the given array is empty
*/
public static boolean isEmpty(Object[] array) {
return (array == null || array.length == 0);
}
/**
* Append the given Object to the given array, returning a new array
* consisting of the input array contents plus the given Object.
* @param array the array to append to (can be null)
* @param obj the Object to append
* @return the new array (of the same component type; never null)
*/
public static Object[] addObjectToArray(Object[] array, Object obj) {
Class compType = Object.class;
if (array != null) {
compType = array.getClass().getComponentType();
}
else if (obj != null) {
compType = obj.getClass();
}
int newArrLength = (array != null ? array.length + 1 : 1);
Object[] newArr = (Object[]) Array.newInstance(compType, newArrLength);
if (array != null) {
System.arraycopy(array, 0, newArr, 0, array.length);
}
newArr[newArr.length - 1] = obj;
return newArr;
}
/**
* Convert the given array (which may be a primitive array) to an
* object array (if necessary of primitive wrapper objects).
* A null source value will be converted to an
* empty Object array.
* @param source the (potentially primitive) array
* @return the corresponding object array (never null)
* @throws IllegalArgumentException if the parameter is not an array
*/
public static Object[] toObjectArray(Object source) {
if (source instanceof Object[]) {
return (Object[]) source;
}
if (source == null) {
return new Object[0];
}
if (!source.getClass().isArray()) {
throw new IllegalArgumentException("Source is not an array: " + source);
}
int length = Array.getLength(source);
if (length == 0) {
return new Object[0];
}
Class wrapperType = Array.get(source, 0).getClass();
Object[] newArray = (Object[]) Array.newInstance(wrapperType, length);
for (int i = 0; i < length; i++) {
newArray[i] = Array.get(source, i);
}
return newArray;
}
}
</source>
ArrayList of boolean primitives
<source lang="java">
// Copyright (c) 2003-2009, Jodd Team (jodd.org). All Rights Reserved.
import java.io.ObjectInputStream; import java.io.ObjectOutputStream; import java.io.Serializable; import java.io.IOException; /**
* ArrayList of boolean primitives. */
public class BooleanArrayList implements Serializable {
private boolean[] array;
private int size;
public static int initialCapacity = 10;
/**
* Constructs an empty list with an initial capacity.
*/
public BooleanArrayList() {
this(initialCapacity);
}
/**
* Constructs an empty list with the specified initial capacity.
*/
public BooleanArrayList(int initialCapacity) {
if (initialCapacity < 0) {
throw new IllegalArgumentException("Capacity can"t be negative: " + initialCapacity);
}
array = new boolean[initialCapacity];
size = 0;
}
/**
* Constructs a list containing the elements of the specified array.
* The list instance has an initial capacity of 110% the size of the specified array.
*/
public BooleanArrayList(boolean[] data) {
array = new boolean[(int) (data.length * 1.1) + 1];
size = data.length;
System.arraycopy(data, 0, array, 0, size);
}
// ---------------------------------------------------------------- conversion
/**
* Returns an array containing all of the elements in this list in the correct order.
*/
public boolean[] toArray() {
boolean[] result = new boolean[size];
System.arraycopy(array, 0, result, 0, size);
return result;
}
// ---------------------------------------------------------------- methods
/**
* Returns the element at the specified position in this list.
*/
public boolean get(int index) {
checkRange(index);
return array[index];
}
/**
* Returns the number of elements in this list.
*/
public int size() {
return size;
}
/**
* Removes the element at the specified position in this list.
* Shifts any subsequent elements to the left (subtracts
* one from their indices).
*
* @param index the index of the element to remove
* @return the value of the element that was removed
* @throws UnsupportedOperationException when this operation is not
* supported
* @throws IndexOutOfBoundsException if the specified index is out of range
*/
public boolean remove(int index) {
checkRange(index);
boolean oldval = array[index];
int numtomove = size - index - 1;
if (numtomove > 0) {
System.arraycopy(array, index + 1, array, index, numtomove);
}
size--;
return oldval;
}
/**
* Removes from this list all of the elements whose index is between fromIndex,
* inclusive and toIndex, exclusive. Shifts any succeeding elements to the left (reduces their index).
*/
public void removeRange(int fromIndex, int toIndex) {
checkRange(fromIndex);
checkRange(toIndex);
if (fromIndex >= toIndex) {
return;
}
int numtomove = size - toIndex;
if (numtomove > 0) {
System.arraycopy(array, toIndex, array, fromIndex, numtomove);
}
size -= (toIndex - fromIndex);
}
/**
* Replaces the element at the specified position in this list with the specified element.
*
* @param index the index of the element to change
* @param element the value to be stored at the specified position
* @return the value previously stored at the specified position
*/
public boolean set(int index, boolean element) {
checkRange(index);
boolean oldval = array[index];
array[index] = element;
return oldval;
}
/**
* Appends the specified element to the end of this list.
*/
public void add(boolean element) {
ensureCapacity(size + 1);
array[size++] = element;
}
/**
* Inserts the specified element at the specified position in this list.
* Shifts the element currently at that position (if any) and any subsequent
* elements to the right (adds one to their indices).
*
* @param index the index at which to insert the element
* @param element the value to insert
*/
public void add(int index, boolean element) {
checkRangeIncludingEndpoint(index);
ensureCapacity(size + 1);
int numtomove = size - index;
System.arraycopy(array, index, array, index + 1, numtomove);
array[index] = element;
size++;
}
/**
* Appends all of the elements in the specified array to the end of this list.
*/
public void addAll(boolean[] data) {
int dataLen = data.length;
if (dataLen == 0) {
return;
}
int newcap = size + (int) (dataLen * 1.1) + 1;
ensureCapacity(newcap);
System.arraycopy(data, 0, array, size, dataLen);
size += dataLen;
}
/**
* Appends all of the elements in the specified array at the specified position in this list.
*/
public void addAll(int index, boolean[] data) {
int dataLen = data.length;
if (dataLen == 0) {
return;
}
int newcap = size + (int) (dataLen * 1.1) + 1;
ensureCapacity(newcap);
System.arraycopy(array, index, array, index + dataLen, size - index);
System.arraycopy(data, 0, array, index, dataLen);
size += dataLen;
}
/**
* Removes all of the elements from this list.
* The list will be empty after this call returns.
*/
public void clear() {
size = 0;
}
// ---------------------------------------------------------------- search
/**
* Returns true if this list contains the specified element.
*/
public boolean contains(boolean data) {
for (int i = 0; i < size; i++) {
if (array[i] == data) {
return true;
}
}
return false;
}
/**
* Searches for the first occurence of the given argument.
*/
public int indexOf(boolean data) {
for (int i = 0; i < size; i++) {
if (array[i] == data) {
return i;
}
}
return -1;
}
/**
* Returns the index of the last occurrence of the specified object in this list.
*/
public int lastIndexOf(boolean data) {
for (int i = size - 1; i >= 0; i--) {
if (array[i] == data) {
return i;
}
}
return -1;
}
/**
* Tests if this list has no elements.
*/
public boolean isEmpty() {
return size == 0;
}
// ---------------------------------------------------------------- capacity
/**
* Increases the capacity of this ArrayList instance, if necessary,
* to ensure that it can hold at least the number of elements specified by
* the minimum capacity argument.
*/
public void ensureCapacity(int mincap) {
if (mincap > array.length) {
int newcap = ((array.length * 3) >> 1) + 1;
boolean[] olddata = array;
array = new boolean[newcap < mincap ? mincap : newcap];
System.arraycopy(olddata, 0, array, 0, size);
}
}
/**
* Trims the capacity of this instance to be the list"s current size.
* An application can use this operation to minimize the storage of some instance.
*/
public void trimToSize() {
if (size < array.length) {
boolean[] olddata = array;
array = new boolean[size];
System.arraycopy(olddata, 0, array, 0, size);
}
}
// ---------------------------------------------------------------- serializable
private void writeObject(ObjectOutputStream out) throws IOException {
out.defaultWriteObject();
out.writeInt(array.length);
for (int i = 0; i < size; i++) {
out.writeBoolean(array[i]);
}
}
private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException {
in.defaultReadObject();
array = new boolean[in.readInt()];
for (int i = 0; i < size; i++) {
array[i] = in.readBoolean();
}
}
// ---------------------------------------------------------------- privates
private void checkRange(int index) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException("Index should be at least 0 and less than " + size + ", found " + index);
}
}
private void checkRangeIncludingEndpoint(int index) {
if (index < 0 || index > size) {
throw new IndexOutOfBoundsException("Index should be at least 0 and at most " + size + ", found " + index);
}
}
}
</source>
ArrayList of byte primitives
<source lang="java">
// Copyright (c) 2003-2009, Jodd Team (jodd.org). All Rights Reserved.
import java.io.ObjectInputStream; import java.io.ObjectOutputStream; import java.io.Serializable; import java.io.IOException; /**
* ArrayList of byte primitives. */
public class ByteArrayList implements Serializable {
private byte[] array;
private int size;
public static int initialCapacity = 10;
/**
* Constructs an empty list with an initial capacity.
*/
public ByteArrayList() {
this(initialCapacity);
}
/**
* Constructs an empty list with the specified initial capacity.
*/
public ByteArrayList(int initialCapacity) {
if (initialCapacity < 0) {
throw new IllegalArgumentException("Capacity can"t be negative: " + initialCapacity);
}
array = new byte[initialCapacity];
size = 0;
}
/**
* Constructs a list containing the elements of the specified array.
* The list instance has an initial capacity of 110% the size of the specified array.
*/
public ByteArrayList(byte[] data) {
array = new byte[(int) (data.length * 1.1) + 1];
size = data.length;
System.arraycopy(data, 0, array, 0, size);
}
// ---------------------------------------------------------------- conversion
/**
* Returns an array containing all of the elements in this list in the correct order.
*/
public byte[] toArray() {
byte[] result = new byte[size];
System.arraycopy(array, 0, result, 0, size);
return result;
}
// ---------------------------------------------------------------- methods
/**
* Returns the element at the specified position in this list.
*/
public byte get(int index) {
checkRange(index);
return array[index];
}
/**
* Returns the number of elements in this list.
*/
public int size() {
return size;
}
/**
* Removes the element at the specified position in this list.
* Shifts any subsequent elements to the left (subtracts
* one from their indices).
*
* @param index the index of the element to remove
* @return the value of the element that was removed
* @throws UnsupportedOperationException when this operation is not
* supported
* @throws IndexOutOfBoundsException if the specified index is out of range
*/
public byte remove(int index) {
checkRange(index);
byte oldval = array[index];
int numtomove = size - index - 1;
if (numtomove > 0) {
System.arraycopy(array, index + 1, array, index, numtomove);
}
size--;
return oldval;
}
/**
* Removes from this list all of the elements whose index is between fromIndex,
* inclusive and toIndex, exclusive. Shifts any succeeding elements to the left (reduces their index).
*/
public void removeRange(int fromIndex, int toIndex) {
checkRange(fromIndex);
checkRange(toIndex);
if (fromIndex >= toIndex) {
return;
}
int numtomove = size - toIndex;
if (numtomove > 0) {
System.arraycopy(array, toIndex, array, fromIndex, numtomove);
}
size -= (toIndex - fromIndex);
}
/**
* Replaces the element at the specified position in this list with the specified element.
*
* @param index the index of the element to change
* @param element the value to be stored at the specified position
* @return the value previously stored at the specified position
*/
public byte set(int index, byte element) {
checkRange(index);
byte oldval = array[index];
array[index] = element;
return oldval;
}
/**
* Appends the specified element to the end of this list.
*/
public void add(byte element) {
ensureCapacity(size + 1);
array[size++] = element;
}
/**
* Inserts the specified element at the specified position in this list.
* Shifts the element currently at that position (if any) and any subsequent
* elements to the right (adds one to their indices).
*
* @param index the index at which to insert the element
* @param element the value to insert
*/
public void add(int index, byte element) {
checkRangeIncludingEndpoint(index);
ensureCapacity(size + 1);
int numtomove = size - index;
System.arraycopy(array, index, array, index + 1, numtomove);
array[index] = element;
size++;
}
/**
* Appends all of the elements in the specified array to the end of this list.
*/
public void addAll(byte[] data) {
int dataLen = data.length;
if (dataLen == 0) {
return;
}
int newcap = size + (int) (dataLen * 1.1) + 1;
ensureCapacity(newcap);
System.arraycopy(data, 0, array, size, dataLen);
size += dataLen;
}
/**
* Appends all of the elements in the specified array at the specified position in this list.
*/
public void addAll(int index, byte[] data) {
int dataLen = data.length;
if (dataLen == 0) {
return;
}
int newcap = size + (int) (dataLen * 1.1) + 1;
ensureCapacity(newcap);
System.arraycopy(array, index, array, index + dataLen, size - index);
System.arraycopy(data, 0, array, index, dataLen);
size += dataLen;
}
/**
* Removes all of the elements from this list.
* The list will be empty after this call returns.
*/
public void clear() {
size = 0;
}
// ---------------------------------------------------------------- search
/**
* Returns true if this list contains the specified element.
*/
public boolean contains(byte data) {
for (int i = 0; i < size; i++) {
if (array[i] == data) {
return true;
}
}
return false;
}
/**
* Searches for the first occurence of the given argument.
*/
public int indexOf(byte data) {
for (int i = 0; i < size; i++) {
if (array[i] == data) {
return i;
}
}
return -1;
}
/**
* Returns the index of the last occurrence of the specified object in this list.
*/
public int lastIndexOf(byte data) {
for (int i = size - 1; i >= 0; i--) {
if (array[i] == data) {
return i;
}
}
return -1;
}
/**
* Tests if this list has no elements.
*/
public boolean isEmpty() {
return size == 0;
}
// ---------------------------------------------------------------- capacity
/**
* Increases the capacity of this ArrayList instance, if necessary,
* to ensure that it can hold at least the number of elements specified by
* the minimum capacity argument.
*/
public void ensureCapacity(int mincap) {
if (mincap > array.length) {
int newcap = ((array.length * 3) >> 1) + 1;
byte[] olddata = array;
array = new byte[newcap < mincap ? mincap : newcap];
System.arraycopy(olddata, 0, array, 0, size);
}
}
/**
* Trims the capacity of this instance to be the list"s current size.
* An application can use this operation to minimize the storage of some instance.
*/
public void trimToSize() {
if (size < array.length) {
byte[] olddata = array;
array = new byte[size];
System.arraycopy(olddata, 0, array, 0, size);
}
}
// ---------------------------------------------------------------- serializable
private void writeObject(ObjectOutputStream out) throws IOException {
out.defaultWriteObject();
out.writeInt(array.length);
for (int i = 0; i < size; i++) {
out.writeByte(array[i]);
}
}
private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException {
in.defaultReadObject();
array = new byte[in.readInt()];
for (int i = 0; i < size; i++) {
array[i] = in.readByte();
}
}
// ---------------------------------------------------------------- privates
private void checkRange(int index) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException("Index should be at least 0 and less than " + size + ", found " + index);
}
}
private void checkRangeIncludingEndpoint(int index) {
if (index < 0 || index > size) {
throw new IndexOutOfBoundsException("Index should be at least 0 and at most " + size + ", found " + index);
}
}
}
</source>
ArrayList of char primitives
<source lang="java">
// Copyright (c) 2003-2009, Jodd Team (jodd.org). All Rights Reserved.
import java.io.ObjectInputStream; import java.io.ObjectOutputStream; import java.io.Serializable; import java.io.IOException; /**
* ArrayList of char primitives. */
public class CharArrayList implements Serializable {
private char[] array;
private int size;
public static int initialCapacity = 10;
/**
* Constructs an empty list with an initial capacity.
*/
public CharArrayList() {
this(initialCapacity);
}
/**
* Constructs an empty list with the specified initial capacity.
*/
public CharArrayList(int initialCapacity) {
if (initialCapacity < 0) {
throw new IllegalArgumentException("Capacity can"t be negative: " + initialCapacity);
}
array = new char[initialCapacity];
size = 0;
}
/**
* Constructs a list containing the elements of the specified array.
* The list instance has an initial capacity of 110% the size of the specified array.
*/
public CharArrayList(char[] data) {
array = new char[(int) (data.length * 1.1) + 1];
size = data.length;
System.arraycopy(data, 0, array, 0, size);
}
// ---------------------------------------------------------------- conversion
/**
* Returns an array containing all of the elements in this list in the correct order.
*/
public char[] toArray() {
char[] result = new char[size];
System.arraycopy(array, 0, result, 0, size);
return result;
}
// ---------------------------------------------------------------- methods
/**
* Returns the element at the specified position in this list.
*/
public char get(int index) {
checkRange(index);
return array[index];
}
/**
* Returns the number of elements in this list.
*/
public int size() {
return size;
}
/**
* Removes the element at the specified position in this list.
* Shifts any subsequent elements to the left (subtracts
* one from their indices).
*
* @param index the index of the element to remove
* @return the value of the element that was removed
* @throws UnsupportedOperationException when this operation is not
* supported
* @throws IndexOutOfBoundsException if the specified index is out of range
*/
public char remove(int index) {
checkRange(index);
char oldval = array[index];
int numtomove = size - index - 1;
if (numtomove > 0) {
System.arraycopy(array, index + 1, array, index, numtomove);
}
size--;
return oldval;
}
/**
* Removes from this list all of the elements whose index is between fromIndex,
* inclusive and toIndex, exclusive. Shifts any succeeding elements to the left (reduces their index).
*/
public void removeRange(int fromIndex, int toIndex) {
checkRange(fromIndex);
checkRange(toIndex);
if (fromIndex >= toIndex) {
return;
}
int numtomove = size - toIndex;
if (numtomove > 0) {
System.arraycopy(array, toIndex, array, fromIndex, numtomove);
}
size -= (toIndex - fromIndex);
}
/**
* Replaces the element at the specified position in this list with the specified element.
*
* @param index the index of the element to change
* @param element the value to be stored at the specified position
* @return the value previously stored at the specified position
*/
public char set(int index, char element) {
checkRange(index);
char oldval = array[index];
array[index] = element;
return oldval;
}
/**
* Appends the specified element to the end of this list.
*/
public void add(char element) {
ensureCapacity(size + 1);
array[size++] = element;
}
/**
* Inserts the specified element at the specified position in this list.
* Shifts the element currently at that position (if any) and any subsequent
* elements to the right (adds one to their indices).
*
* @param index the index at which to insert the element
* @param element the value to insert
*/
public void add(int index, char element) {
checkRangeIncludingEndpoint(index);
ensureCapacity(size + 1);
int numtomove = size - index;
System.arraycopy(array, index, array, index + 1, numtomove);
array[index] = element;
size++;
}
/**
* Appends all of the elements in the specified array to the end of this list.
*/
public void addAll(char[] data) {
int dataLen = data.length;
if (dataLen == 0) {
return;
}
int newcap = size + (int) (dataLen * 1.1) + 1;
ensureCapacity(newcap);
System.arraycopy(data, 0, array, size, dataLen);
size += dataLen;
}
/**
* Appends all of the elements in the specified array at the specified position in this list.
*/
public void addAll(int index, char[] data) {
int dataLen = data.length;
if (dataLen == 0) {
return;
}
int newcap = size + (int) (dataLen * 1.1) + 1;
ensureCapacity(newcap);
System.arraycopy(array, index, array, index + dataLen, size - index);
System.arraycopy(data, 0, array, index, dataLen);
size += dataLen;
}
/**
* Removes all of the elements from this list.
* The list will be empty after this call returns.
*/
public void clear() {
size = 0;
}
// ---------------------------------------------------------------- search
/**
* Returns true if this list contains the specified element.
*/
public boolean contains(char data) {
for (int i = 0; i < size; i++) {
if (array[i] == data) {
return true;
}
}
return false;
}
/**
* Searches for the first occurence of the given argument.
*/
public int indexOf(char data) {
for (int i = 0; i < size; i++) {
if (array[i] == data) {
return i;
}
}
return -1;
}
/**
* Returns the index of the last occurrence of the specified object in this list.
*/
public int lastIndexOf(char data) {
for (int i = size - 1; i >= 0; i--) {
if (array[i] == data) {
return i;
}
}
return -1;
}
/**
* Tests if this list has no elements.
*/
public boolean isEmpty() {
return size == 0;
}
// ---------------------------------------------------------------- capacity
/**
* Increases the capacity of this ArrayList instance, if necessary,
* to ensure that it can hold at least the number of elements specified by
* the minimum capacity argument.
*/
public void ensureCapacity(int mincap) {
if (mincap > array.length) {
int newcap = ((array.length * 3) >> 1) + 1;
char[] olddata = array;
array = new char[newcap < mincap ? mincap : newcap];
System.arraycopy(olddata, 0, array, 0, size);
}
}
/**
* Trims the capacity of this instance to be the list"s current size.
* An application can use this operation to minimize the storage of some instance.
*/
public void trimToSize() {
if (size < array.length) {
char[] olddata = array;
array = new char[size];
System.arraycopy(olddata, 0, array, 0, size);
}
}
// ---------------------------------------------------------------- serializable
private void writeObject(ObjectOutputStream out) throws IOException {
out.defaultWriteObject();
out.writeInt(array.length);
for (int i = 0; i < size; i++) {
out.writeChar(array[i]);
}
}
private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException {
in.defaultReadObject();
array = new char[in.readInt()];
for (int i = 0; i < size; i++) {
array[i] = in.readChar();
}
}
// ---------------------------------------------------------------- privates
private void checkRange(int index) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException("Index should be at least 0 and less than " + size + ", found " + index);
}
}
private void checkRangeIncludingEndpoint(int index) {
if (index < 0 || index > size) {
throw new IndexOutOfBoundsException("Index should be at least 0 and at most " + size + ", found " + index);
}
}
}
</source>
ArrayList of double primitives
<source lang="java">
// Copyright (c) 2003-2009, Jodd Team (jodd.org). All Rights Reserved.
import java.io.ObjectInputStream; import java.io.ObjectOutputStream; import java.io.Serializable; import java.io.IOException; /**
* ArrayList of double primitives. */
public class DoubleArrayList implements Serializable {
private double[] array;
private int size;
public static int initialCapacity = 10;
/**
* Constructs an empty list with an initial capacity.
*/
public DoubleArrayList() {
this(initialCapacity);
}
/**
* Constructs an empty list with the specified initial capacity.
*/
public DoubleArrayList(int initialCapacity) {
if (initialCapacity < 0) {
throw new IllegalArgumentException("Capacity can"t be negative: " + initialCapacity);
}
array = new double[initialCapacity];
size = 0;
}
/**
* Constructs a list containing the elements of the specified array.
* The list instance has an initial capacity of 110% the size of the specified array.
*/
public DoubleArrayList(double[] data) {
array = new double[(int) (data.length * 1.1) + 1];
size = data.length;
System.arraycopy(data, 0, array, 0, size);
}
// ---------------------------------------------------------------- conversion
/**
* Returns an array containing all of the elements in this list in the correct order.
*/
public double[] toArray() {
double[] result = new double[size];
System.arraycopy(array, 0, result, 0, size);
return result;
}
// ---------------------------------------------------------------- methods
/**
* Returns the element at the specified position in this list.
*/
public double get(int index) {
checkRange(index);
return array[index];
}
/**
* Returns the number of elements in this list.
*/
public int size() {
return size;
}
/**
* Removes the element at the specified position in this list.
* Shifts any subsequent elements to the left (subtracts
* one from their indices).
*
* @param index the index of the element to remove
* @return the value of the element that was removed
* @throws UnsupportedOperationException when this operation is not
* supported
* @throws IndexOutOfBoundsException if the specified index is out of range
*/
public double remove(int index) {
checkRange(index);
double oldval = array[index];
int numtomove = size - index - 1;
if (numtomove > 0) {
System.arraycopy(array, index + 1, array, index, numtomove);
}
size--;
return oldval;
}
/**
* Removes from this list all of the elements whose index is between fromIndex,
* inclusive and toIndex, exclusive. Shifts any succeeding elements to the left (reduces their index).
*/
public void removeRange(int fromIndex, int toIndex) {
checkRange(fromIndex);
checkRange(toIndex);
if (fromIndex >= toIndex) {
return;
}
int numtomove = size - toIndex;
if (numtomove > 0) {
System.arraycopy(array, toIndex, array, fromIndex, numtomove);
}
size -= (toIndex - fromIndex);
}
/**
* Replaces the element at the specified position in this list with the specified element.
*
* @param index the index of the element to change
* @param element the value to be stored at the specified position
* @return the value previously stored at the specified position
*/
public double set(int index, double element) {
checkRange(index);
double oldval = array[index];
array[index] = element;
return oldval;
}
/**
* Appends the specified element to the end of this list.
*/
public void add(double element) {
ensureCapacity(size + 1);
array[size++] = element;
}
/**
* Inserts the specified element at the specified position in this list.
* Shifts the element currently at that position (if any) and any subsequent
* elements to the right (adds one to their indices).
*
* @param index the index at which to insert the element
* @param element the value to insert
*/
public void add(int index, double element) {
checkRangeIncludingEndpoint(index);
ensureCapacity(size + 1);
int numtomove = size - index;
System.arraycopy(array, index, array, index + 1, numtomove);
array[index] = element;
size++;
}
/**
* Appends all of the elements in the specified array to the end of this list.
*/
public void addAll(double[] data) {
int dataLen = data.length;
if (dataLen == 0) {
return;
}
int newcap = size + (int) (dataLen * 1.1) + 1;
ensureCapacity(newcap);
System.arraycopy(data, 0, array, size, dataLen);
size += dataLen;
}
/**
* Appends all of the elements in the specified array at the specified position in this list.
*/
public void addAll(int index, double[] data) {
int dataLen = data.length;
if (dataLen == 0) {
return;
}
int newcap = size + (int) (dataLen * 1.1) + 1;
ensureCapacity(newcap);
System.arraycopy(array, index, array, index + dataLen, size - index);
System.arraycopy(data, 0, array, index, dataLen);
size += dataLen;
}
/**
* Removes all of the elements from this list.
* The list will be empty after this call returns.
*/
public void clear() {
size = 0;
}
// ---------------------------------------------------------------- search
/**
* Returns true if this list contains the specified element.
*/
public boolean contains(double data, double delta) {
for (int i = 0; i < size; i++) {
if (Math.abs(array[i] - data) <= delta) {
return true;
}
}
return false;
}
/**
* Searches for the first occurence of the given argument.
*/
public int indexOf(double data, double delta) {
for (int i = 0; i < size; i++) {
if (Math.abs(array[i] - data) <= delta) {
return i;
}
}
return -1;
}
/**
* Returns the index of the last occurrence of the specified object in this list.
*/
public int lastIndexOf(double data, double delta) {
for (int i = size - 1; i >= 0; i--) {
if (Math.abs(array[i] - data) <= delta) {
return i;
}
}
return -1;
}
/**
* Tests if this list has no elements.
*/
public boolean isEmpty() {
return size == 0;
}
// ---------------------------------------------------------------- capacity
/**
* Increases the capacity of this ArrayList instance, if necessary,
* to ensure that it can hold at least the number of elements specified by
* the minimum capacity argument.
*/
public void ensureCapacity(int mincap) {
if (mincap > array.length) {
int newcap = ((array.length * 3) >> 1) + 1;
double[] olddata = array;
array = new double[newcap < mincap ? mincap : newcap];
System.arraycopy(olddata, 0, array, 0, size);
}
}
/**
* Trims the capacity of this instance to be the list"s current size.
* An application can use this operation to minimize the storage of some instance.
*/
public void trimToSize() {
if (size < array.length) {
double[] olddata = array;
array = new double[size];
System.arraycopy(olddata, 0, array, 0, size);
}
}
// ---------------------------------------------------------------- serializable
private void writeObject(ObjectOutputStream out) throws IOException {
out.defaultWriteObject();
out.writeInt(array.length);
for (int i = 0; i < size; i++) {
out.writeDouble(array[i]);
}
}
private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException {
in.defaultReadObject();
array = new double[in.readInt()];
for (int i = 0; i < size; i++) {
array[i] = in.readDouble();
}
}
// ---------------------------------------------------------------- privates
private void checkRange(int index) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException("Index should be at least 0 and less than " + size + ", found " + index);
}
}
private void checkRangeIncludingEndpoint(int index) {
if (index < 0 || index > size) {
throw new IndexOutOfBoundsException("Index should be at least 0 and at most " + size + ", found " + index);
}
}
}
</source>
ArrayList of float primitives
<source lang="java">
// Copyright (c) 2003-2009, Jodd Team (jodd.org). All Rights Reserved.
import java.io.ObjectInputStream; import java.io.ObjectOutputStream; import java.io.Serializable; import java.io.IOException; /**
* ArrayList of float primitives. */
public class FloatArrayList implements Serializable {
private float[] array;
private int size;
public static int initialCapacity = 10;
/**
* Constructs an empty list with an initial capacity.
*/
public FloatArrayList() {
this(initialCapacity);
}
/**
* Constructs an empty list with the specified initial capacity.
*/
public FloatArrayList(int initialCapacity) {
if (initialCapacity < 0) {
throw new IllegalArgumentException("Capacity can"t be negative: " + initialCapacity);
}
array = new float[initialCapacity];
size = 0;
}
/**
* Constructs a list containing the elements of the specified array.
* The list instance has an initial capacity of 110% the size of the specified array.
*/
public FloatArrayList(float[] data) {
array = new float[(int) (data.length * 1.1) + 1];
size = data.length;
System.arraycopy(data, 0, array, 0, size);
}
// ---------------------------------------------------------------- conversion
/**
* Returns an array containing all of the elements in this list in the correct order.
*/
public float[] toArray() {
float[] result = new float[size];
System.arraycopy(array, 0, result, 0, size);
return result;
}
// ---------------------------------------------------------------- methods
/**
* Returns the element at the specified position in this list.
*/
public float get(int index) {
checkRange(index);
return array[index];
}
/**
* Returns the number of elements in this list.
*/
public int size() {
return size;
}
/**
* Removes the element at the specified position in this list.
* Shifts any subsequent elements to the left (subtracts
* one from their indices).
*
* @param index the index of the element to remove
* @return the value of the element that was removed
* @throws UnsupportedOperationException when this operation is not
* supported
* @throws IndexOutOfBoundsException if the specified index is out of range
*/
public float remove(int index) {
checkRange(index);
float oldval = array[index];
int numtomove = size - index - 1;
if (numtomove > 0) {
System.arraycopy(array, index + 1, array, index, numtomove);
}
size--;
return oldval;
}
/**
* Removes from this list all of the elements whose index is between fromIndex,
* inclusive and toIndex, exclusive. Shifts any succeeding elements to the left (reduces their index).
*/
public void removeRange(int fromIndex, int toIndex) {
checkRange(fromIndex);
checkRange(toIndex);
if (fromIndex >= toIndex) {
return;
}
int numtomove = size - toIndex;
if (numtomove > 0) {
System.arraycopy(array, toIndex, array, fromIndex, numtomove);
}
size -= (toIndex - fromIndex);
}
/**
* Replaces the element at the specified position in this list with the specified element.
*
* @param index the index of the element to change
* @param element the value to be stored at the specified position
* @return the value previously stored at the specified position
*/
public float set(int index, float element) {
checkRange(index);
float oldval = array[index];
array[index] = element;
return oldval;
}
/**
* Appends the specified element to the end of this list.
*/
public void add(float element) {
ensureCapacity(size + 1);
array[size++] = element;
}
/**
* Inserts the specified element at the specified position in this list.
* Shifts the element currently at that position (if any) and any subsequent
* elements to the right (adds one to their indices).
*
* @param index the index at which to insert the element
* @param element the value to insert
*/
public void add(int index, float element) {
checkRangeIncludingEndpoint(index);
ensureCapacity(size + 1);
int numtomove = size - index;
System.arraycopy(array, index, array, index + 1, numtomove);
array[index] = element;
size++;
}
/**
* Appends all of the elements in the specified array to the end of this list.
*/
public void addAll(float[] data) {
int dataLen = data.length;
if (dataLen == 0) {
return;
}
int newcap = size + (int) (dataLen * 1.1) + 1;
ensureCapacity(newcap);
System.arraycopy(data, 0, array, size, dataLen);
size += dataLen;
}
/**
* Appends all of the elements in the specified array at the specified position in this list.
*/
public void addAll(int index, float[] data) {
int dataLen = data.length;
if (dataLen == 0) {
return;
}
int newcap = size + (int) (dataLen * 1.1) + 1;
ensureCapacity(newcap);
System.arraycopy(array, index, array, index + dataLen, size - index);
System.arraycopy(data, 0, array, index, dataLen);
size += dataLen;
}
/**
* Removes all of the elements from this list.
* The list will be empty after this call returns.
*/
public void clear() {
size = 0;
}
// ---------------------------------------------------------------- search
/**
* Returns true if this list contains the specified element.
*/
public boolean contains(float data, float delta) {
for (int i = 0; i < size; i++) {
if (Math.abs(array[i] - data) <= delta) {
return true;
}
}
return false;
}
/**
* Searches for the first occurence of the given argument.
*/
public int indexOf(float data, float delta) {
for (int i = 0; i < size; i++) {
if (Math.abs(array[i] - data) <= delta) {
return i;
}
}
return -1;
}
/**
* Returns the index of the last occurrence of the specified object in this list.
*/
public int lastIndexOf(float data, float delta) {
for (int i = size - 1; i >= 0; i--) {
if (Math.abs(array[i] - data) <= delta) {
return i;
}
}
return -1;
}
/**
* Tests if this list has no elements.
*/
public boolean isEmpty() {
return size == 0;
}
// ---------------------------------------------------------------- capacity
/**
* Increases the capacity of this ArrayList instance, if necessary,
* to ensure that it can hold at least the number of elements specified by
* the minimum capacity argument.
*/
public void ensureCapacity(int mincap) {
if (mincap > array.length) {
int newcap = ((array.length * 3) >> 1) + 1;
float[] olddata = array;
array = new float[newcap < mincap ? mincap : newcap];
System.arraycopy(olddata, 0, array, 0, size);
}
}
/**
* Trims the capacity of this instance to be the list"s current size.
* An application can use this operation to minimize the storage of some instance.
*/
public void trimToSize() {
if (size < array.length) {
float[] olddata = array;
array = new float[size];
System.arraycopy(olddata, 0, array, 0, size);
}
}
// ---------------------------------------------------------------- serializable
private void writeObject(ObjectOutputStream out) throws IOException {
out.defaultWriteObject();
out.writeInt(array.length);
for (int i = 0; i < size; i++) {
out.writeFloat(array[i]);
}
}
private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException {
in.defaultReadObject();
array = new float[in.readInt()];
for (int i = 0; i < size; i++) {
array[i] = in.readFloat();
}
}
// ---------------------------------------------------------------- privates
private void checkRange(int index) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException("Index should be at least 0 and less than " + size + ", found " + index);
}
}
private void checkRangeIncludingEndpoint(int index) {
if (index < 0 || index > size) {
throw new IndexOutOfBoundsException("Index should be at least 0 and at most " + size + ", found " + index);
}
}
}
</source>
ArrayList of int primitives
<source lang="java">
// Copyright (c) 2003-2009, Jodd Team (jodd.org). All Rights Reserved.
import java.io.ObjectInputStream; import java.io.ObjectOutputStream; import java.io.Serializable; import java.io.IOException; /**
* ArrayList of int primitives. */
public class IntArrayList implements Serializable {
private int[] array;
private int size;
public static int initialCapacity = 10;
/**
* Constructs an empty list with an initial capacity.
*/
public IntArrayList() {
this(initialCapacity);
}
/**
* Constructs an empty list with the specified initial capacity.
*/
public IntArrayList(int initialCapacity) {
if (initialCapacity < 0) {
throw new IllegalArgumentException("Capacity can"t be negative: " + initialCapacity);
}
array = new int[initialCapacity];
size = 0;
}
/**
* Constructs a list containing the elements of the specified array.
* The list instance has an initial capacity of 110% the size of the specified array.
*/
public IntArrayList(int[] data) {
array = new int[(int) (data.length * 1.1) + 1];
size = data.length;
System.arraycopy(data, 0, array, 0, size);
}
// ---------------------------------------------------------------- conversion
/**
* Returns an array containing all of the elements in this list in the correct order.
*/
public int[] toArray() {
int[] result = new int[size];
System.arraycopy(array, 0, result, 0, size);
return result;
}
// ---------------------------------------------------------------- methods
/**
* Returns the element at the specified position in this list.
*/
public int get(int index) {
checkRange(index);
return array[index];
}
/**
* Returns the number of elements in this list.
*/
public int size() {
return size;
}
/**
* Removes the element at the specified position in this list.
* Shifts any subsequent elements to the left (subtracts
* one from their indices).
*
* @param index the index of the element to remove
* @return the value of the element that was removed
* @throws UnsupportedOperationException when this operation is not
* supported
* @throws IndexOutOfBoundsException if the specified index is out of range
*/
public int remove(int index) {
checkRange(index);
int oldval = array[index];
int numtomove = size - index - 1;
if (numtomove > 0) {
System.arraycopy(array, index + 1, array, index, numtomove);
}
size--;
return oldval;
}
/**
* Removes from this list all of the elements whose index is between fromIndex,
* inclusive and toIndex, exclusive. Shifts any succeeding elements to the left (reduces their index).
*/
public void removeRange(int fromIndex, int toIndex) {
checkRange(fromIndex);
checkRange(toIndex);
if (fromIndex >= toIndex) {
return;
}
int numtomove = size - toIndex;
if (numtomove > 0) {
System.arraycopy(array, toIndex, array, fromIndex, numtomove);
}
size -= (toIndex - fromIndex);
}
/**
* Replaces the element at the specified position in this list with the specified element.
*
* @param index the index of the element to change
* @param element the value to be stored at the specified position
* @return the value previously stored at the specified position
*/
public int set(int index, int element) {
checkRange(index);
int oldval = array[index];
array[index] = element;
return oldval;
}
/**
* Appends the specified element to the end of this list.
*/
public void add(int element) {
ensureCapacity(size + 1);
array[size++] = element;
}
/**
* Inserts the specified element at the specified position in this list.
* Shifts the element currently at that position (if any) and any subsequent
* elements to the right (adds one to their indices).
*
* @param index the index at which to insert the element
* @param element the value to insert
*/
public void add(int index, int element) {
checkRangeIncludingEndpoint(index);
ensureCapacity(size + 1);
int numtomove = size - index;
System.arraycopy(array, index, array, index + 1, numtomove);
array[index] = element;
size++;
}
/**
* Appends all of the elements in the specified array to the end of this list.
*/
public void addAll(int[] data) {
int dataLen = data.length;
if (dataLen == 0) {
return;
}
int newcap = size + (int) (dataLen * 1.1) + 1;
ensureCapacity(newcap);
System.arraycopy(data, 0, array, size, dataLen);
size += dataLen;
}
/**
* Appends all of the elements in the specified array at the specified position in this list.
*/
public void addAll(int index, int[] data) {
int dataLen = data.length;
if (dataLen == 0) {
return;
}
int newcap = size + (int) (dataLen * 1.1) + 1;
ensureCapacity(newcap);
System.arraycopy(array, index, array, index + dataLen, size - index);
System.arraycopy(data, 0, array, index, dataLen);
size += dataLen;
}
/**
* Removes all of the elements from this list.
* The list will be empty after this call returns.
*/
public void clear() {
size = 0;
}
// ---------------------------------------------------------------- search
/**
* Returns true if this list contains the specified element.
*/
public boolean contains(int data) {
for (int i = 0; i < size; i++) {
if (array[i] == data) {
return true;
}
}
return false;
}
/**
* Searches for the first occurence of the given argument.
*/
public int indexOf(int data) {
for (int i = 0; i < size; i++) {
if (array[i] == data) {
return i;
}
}
return -1;
}
/**
* Returns the index of the last occurrence of the specified object in this list.
*/
public int lastIndexOf(int data) {
for (int i = size - 1; i >= 0; i--) {
if (array[i] == data) {
return i;
}
}
return -1;
}
/**
* Tests if this list has no elements.
*/
public boolean isEmpty() {
return size == 0;
}
// ---------------------------------------------------------------- capacity
/**
* Increases the capacity of this ArrayList instance, if necessary,
* to ensure that it can hold at least the number of elements specified by
* the minimum capacity argument.
*/
public void ensureCapacity(int mincap) {
if (mincap > array.length) {
int newcap = ((array.length * 3) >> 1) + 1;
int[] olddata = array;
array = new int[newcap < mincap ? mincap : newcap];
System.arraycopy(olddata, 0, array, 0, size);
}
}
/**
* Trims the capacity of this instance to be the list"s current size.
* An application can use this operation to minimize the storage of some instance.
*/
public void trimToSize() {
if (size < array.length) {
int[] olddata = array;
array = new int[size];
System.arraycopy(olddata, 0, array, 0, size);
}
}
// ---------------------------------------------------------------- serializable
private void writeObject(ObjectOutputStream out) throws IOException {
out.defaultWriteObject();
out.writeInt(array.length);
for (int i = 0; i < size; i++) {
out.writeInt(array[i]);
}
}
private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException {
in.defaultReadObject();
array = new int[in.readInt()];
for (int i = 0; i < size; i++) {
array[i] = in.readInt();
}
}
// ---------------------------------------------------------------- privates
private void checkRange(int index) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException("Index should be at least 0 and less than " + size + ", found " + index);
}
}
private void checkRangeIncludingEndpoint(int index) {
if (index < 0 || index > size) {
throw new IndexOutOfBoundsException("Index should be at least 0 and at most " + size + ", found " + index);
}
}
}
</source>
ArrayList of long primitives
<source lang="java">
// Copyright (c) 2003-2009, Jodd Team (jodd.org). All Rights Reserved.
import java.io.ObjectInputStream; import java.io.ObjectOutputStream; import java.io.Serializable; import java.io.IOException; /**
* ArrayList of long primitives. */
public class LongArrayList implements Serializable {
private long[] array;
private int size;
public static int initialCapacity = 10;
/**
* Constructs an empty list with an initial capacity.
*/
public LongArrayList() {
this(initialCapacity);
}
/**
* Constructs an empty list with the specified initial capacity.
*/
public LongArrayList(int initialCapacity) {
if (initialCapacity < 0) {
throw new IllegalArgumentException("Capacity can"t be negative: " + initialCapacity);
}
array = new long[initialCapacity];
size = 0;
}
/**
* Constructs a list containing the elements of the specified array.
* The list instance has an initial capacity of 110% the size of the specified array.
*/
public LongArrayList(long[] data) {
array = new long[(int) (data.length * 1.1) + 1];
size = data.length;
System.arraycopy(data, 0, array, 0, size);
}
// ---------------------------------------------------------------- conversion
/**
* Returns an array containing all of the elements in this list in the correct order.
*/
public long[] toArray() {
long[] result = new long[size];
System.arraycopy(array, 0, result, 0, size);
return result;
}
// ---------------------------------------------------------------- methods
/**
* Returns the element at the specified position in this list.
*/
public long get(int index) {
checkRange(index);
return array[index];
}
/**
* Returns the number of elements in this list.
*/
public int size() {
return size;
}
/**
* Removes the element at the specified position in this list.
* Shifts any subsequent elements to the left (subtracts
* one from their indices).
*
* @param index the index of the element to remove
* @return the value of the element that was removed
* @throws UnsupportedOperationException when this operation is not
* supported
* @throws IndexOutOfBoundsException if the specified index is out of range
*/
public long remove(int index) {
checkRange(index);
long oldval = array[index];
int numtomove = size - index - 1;
if (numtomove > 0) {
System.arraycopy(array, index + 1, array, index, numtomove);
}
size--;
return oldval;
}
/**
* Removes from this list all of the elements whose index is between fromIndex,
* inclusive and toIndex, exclusive. Shifts any succeeding elements to the left (reduces their index).
*/
public void removeRange(int fromIndex, int toIndex) {
checkRange(fromIndex);
checkRange(toIndex);
if (fromIndex >= toIndex) {
return;
}
int numtomove = size - toIndex;
if (numtomove > 0) {
System.arraycopy(array, toIndex, array, fromIndex, numtomove);
}
size -= (toIndex - fromIndex);
}
/**
* Replaces the element at the specified position in this list with the specified element.
*
* @param index the index of the element to change
* @param element the value to be stored at the specified position
* @return the value previously stored at the specified position
*/
public long set(int index, long element) {
checkRange(index);
long oldval = array[index];
array[index] = element;
return oldval;
}
/**
* Appends the specified element to the end of this list.
*/
public void add(long element) {
ensureCapacity(size + 1);
array[size++] = element;
}
/**
* Inserts the specified element at the specified position in this list.
* Shifts the element currently at that position (if any) and any subsequent
* elements to the right (adds one to their indices).
*
* @param index the index at which to insert the element
* @param element the value to insert
*/
public void add(int index, long element) {
checkRangeIncludingEndpoint(index);
ensureCapacity(size + 1);
int numtomove = size - index;
System.arraycopy(array, index, array, index + 1, numtomove);
array[index] = element;
size++;
}
/**
* Appends all of the elements in the specified array to the end of this list.
*/
public void addAll(long[] data) {
int dataLen = data.length;
if (dataLen == 0) {
return;
}
int newcap = size + (int) (dataLen * 1.1) + 1;
ensureCapacity(newcap);
System.arraycopy(data, 0, array, size, dataLen);
size += dataLen;
}
/**
* Appends all of the elements in the specified array at the specified position in this list.
*/
public void addAll(int index, long[] data) {
int dataLen = data.length;
if (dataLen == 0) {
return;
}
int newcap = size + (int) (dataLen * 1.1) + 1;
ensureCapacity(newcap);
System.arraycopy(array, index, array, index + dataLen, size - index);
System.arraycopy(data, 0, array, index, dataLen);
size += dataLen;
}
/**
* Removes all of the elements from this list.
* The list will be empty after this call returns.
*/
public void clear() {
size = 0;
}
// ---------------------------------------------------------------- search
/**
* Returns true if this list contains the specified element.
*/
public boolean contains(long data) {
for (int i = 0; i < size; i++) {
if (array[i] == data) {
return true;
}
}
return false;
}
/**
* Searches for the first occurence of the given argument.
*/
public int indexOf(long data) {
for (int i = 0; i < size; i++) {
if (array[i] == data) {
return i;
}
}
return -1;
}
/**
* Returns the index of the last occurrence of the specified object in this list.
*/
public int lastIndexOf(long data) {
for (int i = size - 1; i >= 0; i--) {
if (array[i] == data) {
return i;
}
}
return -1;
}
/**
* Tests if this list has no elements.
*/
public boolean isEmpty() {
return size == 0;
}
// ---------------------------------------------------------------- capacity
/**
* Increases the capacity of this ArrayList instance, if necessary,
* to ensure that it can hold at least the number of elements specified by
* the minimum capacity argument.
*/
public void ensureCapacity(int mincap) {
if (mincap > array.length) {
int newcap = ((array.length * 3) >> 1) + 1;
long[] olddata = array;
array = new long[newcap < mincap ? mincap : newcap];
System.arraycopy(olddata, 0, array, 0, size);
}
}
/**
* Trims the capacity of this instance to be the list"s current size.
* An application can use this operation to minimize the storage of some instance.
*/
public void trimToSize() {
if (size < array.length) {
long[] olddata = array;
array = new long[size];
System.arraycopy(olddata, 0, array, 0, size);
}
}
// ---------------------------------------------------------------- serializable
private void writeObject(ObjectOutputStream out) throws IOException {
out.defaultWriteObject();
out.writeInt(array.length);
for (int i = 0; i < size; i++) {
out.writeLong(array[i]);
}
}
private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException {
in.defaultReadObject();
array = new long[in.readInt()];
for (int i = 0; i < size; i++) {
array[i] = in.readLong();
}
}
// ---------------------------------------------------------------- privates
private void checkRange(int index) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException("Index should be at least 0 and less than " + size + ", found " + index);
}
}
private void checkRangeIncludingEndpoint(int index) {
if (index < 0 || index > size) {
throw new IndexOutOfBoundsException("Index should be at least 0 and at most " + size + ", found " + index);
}
}
}
</source>
ArrayList of short primitives
<source lang="java">
// Copyright (c) 2003-2009, Jodd Team (jodd.org). All Rights Reserved.
import java.io.ObjectInputStream; import java.io.ObjectOutputStream; import java.io.Serializable; import java.io.IOException; /**
* ArrayList of short primitives. */
public class ShortArrayList implements Serializable {
private short[] array;
private int size;
public static int initialCapacity = 10;
/**
* Constructs an empty list with an initial capacity.
*/
public ShortArrayList() {
this(initialCapacity);
}
/**
* Constructs an empty list with the specified initial capacity.
*/
public ShortArrayList(int initialCapacity) {
if (initialCapacity < 0) {
throw new IllegalArgumentException("Capacity can"t be negative: " + initialCapacity);
}
array = new short[initialCapacity];
size = 0;
}
/**
* Constructs a list containing the elements of the specified array.
* The list instance has an initial capacity of 110% the size of the specified array.
*/
public ShortArrayList(short[] data) {
array = new short[(int) (data.length * 1.1) + 1];
size = data.length;
System.arraycopy(data, 0, array, 0, size);
}
// ---------------------------------------------------------------- conversion
/**
* Returns an array containing all of the elements in this list in the correct order.
*/
public short[] toArray() {
short[] result = new short[size];
System.arraycopy(array, 0, result, 0, size);
return result;
}
// ---------------------------------------------------------------- methods
/**
* Returns the element at the specified position in this list.
*/
public short get(int index) {
checkRange(index);
return array[index];
}
/**
* Returns the number of elements in this list.
*/
public int size() {
return size;
}
/**
* Removes the element at the specified position in this list.
* Shifts any subsequent elements to the left (subtracts
* one from their indices).
*
* @param index the index of the element to remove
* @return the value of the element that was removed
* @throws UnsupportedOperationException when this operation is not
* supported
* @throws IndexOutOfBoundsException if the specified index is out of range
*/
public short remove(int index) {
checkRange(index);
short oldval = array[index];
int numtomove = size - index - 1;
if (numtomove > 0) {
System.arraycopy(array, index + 1, array, index, numtomove);
}
size--;
return oldval;
}
/**
* Removes from this list all of the elements whose index is between fromIndex,
* inclusive and toIndex, exclusive. Shifts any succeeding elements to the left (reduces their index).
*/
public void removeRange(int fromIndex, int toIndex) {
checkRange(fromIndex);
checkRange(toIndex);
if (fromIndex >= toIndex) {
return;
}
int numtomove = size - toIndex;
if (numtomove > 0) {
System.arraycopy(array, toIndex, array, fromIndex, numtomove);
}
size -= (toIndex - fromIndex);
}
/**
* Replaces the element at the specified position in this list with the specified element.
*
* @param index the index of the element to change
* @param element the value to be stored at the specified position
* @return the value previously stored at the specified position
*/
public short set(int index, short element) {
checkRange(index);
short oldval = array[index];
array[index] = element;
return oldval;
}
/**
* Appends the specified element to the end of this list.
*/
public void add(short element) {
ensureCapacity(size + 1);
array[size++] = element;
}
/**
* Inserts the specified element at the specified position in this list.
* Shifts the element currently at that position (if any) and any subsequent
* elements to the right (adds one to their indices).
*
* @param index the index at which to insert the element
* @param element the value to insert
*/
public void add(int index, short element) {
checkRangeIncludingEndpoint(index);
ensureCapacity(size + 1);
int numtomove = size - index;
System.arraycopy(array, index, array, index + 1, numtomove);
array[index] = element;
size++;
}
/**
* Appends all of the elements in the specified array to the end of this list.
*/
public void addAll(short[] data) {
int dataLen = data.length;
if (dataLen == 0) {
return;
}
int newcap = size + (int) (dataLen * 1.1) + 1;
ensureCapacity(newcap);
System.arraycopy(data, 0, array, size, dataLen);
size += dataLen;
}
/**
* Appends all of the elements in the specified array at the specified position in this list.
*/
public void addAll(int index, short[] data) {
int dataLen = data.length;
if (dataLen == 0) {
return;
}
int newcap = size + (int) (dataLen * 1.1) + 1;
ensureCapacity(newcap);
System.arraycopy(array, index, array, index + dataLen, size - index);
System.arraycopy(data, 0, array, index, dataLen);
size += dataLen;
}
/**
* Removes all of the elements from this list.
* The list will be empty after this call returns.
*/
public void clear() {
size = 0;
}
// ---------------------------------------------------------------- search
/**
* Returns true if this list contains the specified element.
*/
public boolean contains(short data) {
for (int i = 0; i < size; i++) {
if (array[i] == data) {
return true;
}
}
return false;
}
/**
* Searches for the first occurence of the given argument.
*/
public int indexOf(short data) {
for (int i = 0; i < size; i++) {
if (array[i] == data) {
return i;
}
}
return -1;
}
/**
* Returns the index of the last occurrence of the specified object in this list.
*/
public int lastIndexOf(short data) {
for (int i = size - 1; i >= 0; i--) {
if (array[i] == data) {
return i;
}
}
return -1;
}
/**
* Tests if this list has no elements.
*/
public boolean isEmpty() {
return size == 0;
}
// ---------------------------------------------------------------- capacity
/**
* Increases the capacity of this ArrayList instance, if necessary,
* to ensure that it can hold at least the number of elements specified by
* the minimum capacity argument.
*/
public void ensureCapacity(int mincap) {
if (mincap > array.length) {
int newcap = ((array.length * 3) >> 1) + 1;
short[] olddata = array;
array = new short[newcap < mincap ? mincap : newcap];
System.arraycopy(olddata, 0, array, 0, size);
}
}
/**
* Trims the capacity of this instance to be the list"s current size.
* An application can use this operation to minimize the storage of some instance.
*/
public void trimToSize() {
if (size < array.length) {
short[] olddata = array;
array = new short[size];
System.arraycopy(olddata, 0, array, 0, size);
}
}
// ---------------------------------------------------------------- serializable
private void writeObject(ObjectOutputStream out) throws IOException {
out.defaultWriteObject();
out.writeInt(array.length);
for (int i = 0; i < size; i++) {
out.writeShort(array[i]);
}
}
private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException {
in.defaultReadObject();
array = new short[in.readInt()];
for (int i = 0; i < size; i++) {
array[i] = in.readShort();
}
}
// ---------------------------------------------------------------- privates
private void checkRange(int index) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException("Index should be at least 0 and less than " + size + ", found " + index);
}
}
private void checkRangeIncludingEndpoint(int index) {
if (index < 0 || index > size) {
throw new IndexOutOfBoundsException("Index should be at least 0 and at most " + size + ", found " + index);
}
}
}
</source>
A two dimensional Vector
<source lang="java">
//** Copyright Statement *************************************************** //The Salmon Open Framework for Internet Applications (SOFIA) // Copyright (C) 1999 - 2002, Salmon LLC // // This program is free software; you can redistribute it and/or // modify it under the terms of the GNU General Public License version 2 // as published by the Free Software Foundation; // // This program is distributed in the hope that it will be useful, // but WITHOUT ANY WARRANTY; without even the implied warranty of // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the // GNU General Public License for more details. // // You should have received a copy of the GNU General Public License // along with this program; if not, write to the Free Software // Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. // // For more information please visit http://www.salmonllc.ru //** End Copyright Statement ***************************************************
///////////////////////// //$Archive: /JADE/SourceCode/com/salmonllc/util/Vector2D.java $ //$Author: Dan $ //$Revision: 15 $ //$Modtime: 10/30/02 2:59p $ ///////////////////////// import java.util.*; /**
* This class is a two dimensional Vector. It contains rows and columns that can expand as necessary. */
public class Vector2D implements java.io.Serializable {
Vector _rows = new Vector(); int _columnCapacity = 5; int _columnCount; int _columnSize; int _rowSize;
/**
* Constructs an empty 2 Dimensional vector. */
public Vector2D() {
super();
} /**
* This method adds a specified number of columns to the vector * @param The Number of colums to add. */
public void addColumns(int noColumns) {
if ((noColumns + _columnCount) >= _columnCapacity)
{
_columnCapacity = noColumns + _columnCount + _columnCapacity;
}
for (int i = 0; i < _rows.size(); i++)
{
Object[] tgt = new Object[_columnCapacity];
Object[] src = (Object[]) _rows.elementAt(i);
System.arraycopy(src, 0, tgt, 0, _columnCount);
_rows.setElementAt(tgt, i);
}
_columnCount += noColumns;
} /**
* This method adds a specified number of rows to the vector * @param The Number of rows to add. */
public void addRows(int noRows) {
for (int i = 0; i < noRows; i++)
{
Object[] o = new Object[_columnCapacity];
_rows.addElement(o);
}
} /**
* This method returns the object at row and column.. */
public Object elementAt(int index) {
if (index < 0 || index >= size()) return null; int row = index / _columnCount; int column = index % _columnCount; Object[] o = (Object[]) _rows.elementAt(row); return o[column];
} /**
* This method returns the object at row and column.. */
public Object elementAt(int row, int column) {
if (row < 0 || row >= _rows.size()) return null; else if (column < 0 || column >= _columnCount) return null; Object[] o = (Object[]) _rows.elementAt(row); return o[column];
} public void exportData(boolean includeHeaders, java.io.PrintWriter p) {
StringBuffer work = new StringBuffer(); Object data = null; //work.append("
");
work.append("ROW_NUM");
work.append(" | ");
for (int i = 0; i < getColumnCount(); i++)
{
work.append("");
work.append("COL_" + i);
work.append(" | ");
}
work.append("
|---|---|
| ROW_" + rows); work.append(" | "); for (int cols = 0; cols < getColumnCount(); cols++) { work.append("");
data = elementAt(rows, cols);
if (data == null)
{
work.append(" ");
}
else
{
work.append(data.toString());
}
work.append(" | ");
}
work.append("
p.println(work.toString()); p.flush();
} /**
* This method returns the number of columns in the 2D Vector */
public int getColumnCount() {
return _columnCount;
} /**
* This method returns the number of columns that are occupied with data in the 2D Vector */
public int getColumnSize() {
return _columnSize + 1;
} /**
* This method returns the number of columns in the 2DVector */
public int getRowCount() {
return _rows.size();
} /**
* This method returns the number of rows that are occupied with data in the 2D Vector */
public int getRowSize() {
return _rowSize + 1;
} /**
* This method returns the index of the item at row and column or -1 if the element doesn"t exist. */
public int indexAt(int row, int column) {
if (row < 0 || row >= _rows.size()) return -1; else if (column < 0 || column >= _columnCount) return -1; return (row * _columnCount) + column;
} /**
* This method inserts a row immediately before the specified row */
public void insertRow(int row) {
if (row < 0) return; Object[] o = new Object[_columnCapacity]; if (row > _rows.size()) _rows.addElement(o); else _rows.insertElementAt(o,row);
} /**
* This method inserts a row immediately before the specified row */
public void removeAll() {
_rows.removeAllElements(); _columnCapacity = 5; _columnCount = 0; _columnSize = 0; _rowSize = 0;
} /**
* This method removes a row from the 2DVector * @param row The row to remove. */
public void removeRow(int row) {
if (row < 0 || row > _rows.size()) return; _rows.removeElementAt(row); _rowSize = _rowSize - 1;
} /**
* This method sets the value of a cell in the 2D Vector * @param row The row position * @param column The row position * @param in The object to set. */
public void setElementAt(int row, int column, Object in) {
if (row < 0 || row >= _rows.size())
return;
else
if (column < 0 || column >= _columnCount)
return;
Object[] o = (Object[]) _rows.elementAt(row);
o[column] = in;
// this is to get only the occupied rows and columns
if (_rowSize < row)
_rowSize = row;
if (_columnSize < column)
_columnSize = column;
} /**
* This method sets the value of a cell in the 2D Vector * @param in The object to set. * @param index The position to put it at */
public void setElementAt(int index,Object in){
if (index < 0 || index >= size()) return; int row = index / _columnCount; int column = index % _columnCount; Object[] o = (Object[]) _rows.elementAt(row); o[column] = in; // this is to get only the occupied rows and columns if (_rowSize < row) _rowSize = row; if (_columnSize < column) _columnSize = column;
} /**
* This method was created in VisualAge. * @return int */
public int size() {
return (_rows.size() * _columnCount);
} /**
* Returns a string representation of the 2D vector. */
public String toString() {
StringBuffer work = new StringBuffer();
Object data = null;
boolean commaFlag = false;
for (int rows = 0; rows < getRowCount(); rows++)
{
work.append("[");
for (int cols = 0; cols < getColumnCount(); cols++)
{
if (commaFlag == true)
{
work.append(",");
}
data = elementAt(rows, cols);
if (data == null)
{
work.append("NULL");
}
else
{
work.append(data.toString());
}
commaFlag = true;
}
work.append("]\n");
commaFlag = false;
}
return work.toString();
} }
</source>
Auto Size Array
<source lang="java">
/*
Copyright 2007 Robert C. Ilardi Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at http://www.apache.org/licenses/LICENSE-2.0 Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License. */
import java.io.Serializable; import java.util.ArrayList; /**
* @author rilardi */
public class AutoSizeArray implements Serializable {
private ArrayList<IndexedItem> items;
public AutoSizeArray() {
items = new ArrayList<IndexedItem>();
}
public int findMaxIndex() {
int maxIndex = 0;
IndexedItem iItem;
for (int i = 0; i < items.size(); i++) {
iItem = (IndexedItem) items.get(i);
if (iItem.getIndex() > maxIndex) {
maxIndex = iItem.getIndex();
}
}
return maxIndex;
}
public Object get(int index) {
IndexedItem iItem = null;
for (int i = 0; i < items.size(); i++) {
iItem = (IndexedItem) items.get(i);
if (iItem.getIndex() == index) {
break;
}
else {
iItem = null;
}
}
return (iItem != null ? iItem.getItem() : null);
}
public void store(int index, Serializable item) {
IndexedItem iItem;
if (index >= 0) {
iItem = new IndexedItem();
iItem.setIndex(index);
iItem.setItem(item);
items.add(iItem);
}
}
public Object[] getObjectArray() {
Object[] arr = null;
IndexedItem iItem;
int maxIndex;
maxIndex = findMaxIndex();
arr = new Object[maxIndex + 1];
for (int i = 0; i < arr.length && i < items.size(); i++) {
iItem = (IndexedItem) items.get(i);
arr[iItem.getIndex()] = iItem.getItem();
}
return arr;
}
public String[] getStringArray() {
String[] arr = null;
IndexedItem iItem;
int maxIndex;
Object obj;
maxIndex = findMaxIndex();
arr = new String[maxIndex + 1];
for (int i = 0; i < arr.length && i < items.size(); i++) {
iItem = (IndexedItem) items.get(i);
obj = iItem.getItem();
if (obj != null) {
arr[iItem.getIndex()] = obj.toString();
}
}
return arr;
}
public int size() {
return items.size();
}
public Object remove(int index) {
IndexedItem iItem = null;
for (int i = 0; i < items.size(); i++) {
iItem = (IndexedItem) items.get(i);
if (iItem.getIndex() == index) {
items.remove(i);
break;
}
else {
iItem = null;
}
}
return (iItem != null ? iItem.getItem() : null);
}
public void clear() {
items.clear();
}
} /* Copyright 2007 Robert C. Ilardi Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at http://www.apache.org/licenses/LICENSE-2.0 Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License.
- /
/**
- @author rilardi
- /
class IndexedItem implements Serializable {
private int index;
private Serializable item;
public IndexedItem() {}
/**
* @return Returns the index.
*/
public int getIndex() {
return index;
}
/**
* @param index The index to set.
*/
public void setIndex(int index) {
this.index = index;
}
/**
* @return Returns the item.
*/
public Object getItem() {
return item;
}
/**
* @param item The item to set.
*/
public void setItem(Serializable item) {
this.item = item;
}
}
</source>
A variable length Double Array: expanding and contracting its internal storage array as elements are added and removed.
<source lang="java">
/*
* Licensed to the Apache Software Foundation (ASF) under one or more * contributor license agreements. See the NOTICE file distributed with * this work for additional information regarding copyright ownership. * The ASF licenses this file to You under the Apache License, Version 2.0 * (the "License"); you may not use this file except in compliance with * the License. You may obtain a copy of the License at * * http://www.apache.org/licenses/LICENSE-2.0 * * Unless required by applicable law or agreed to in writing, software * distributed under the License is distributed on an "AS IS" BASIS, * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. * See the License for the specific language governing permissions and * limitations under the License. */
import java.io.Serializable; /**
* <p>
* A variable length {@link DoubleArray} implementation that automatically
* handles expanding and contracting its internal storage array as elements are
* added and removed.
*
*
* The internal storage array starts with capacity determined by the
* initialCapacity property, which can be set by the constructor.
* The default initial capacity is 16. Adding elements using
* {@link #addElement(double)} appends elements to the end of the array. When
* there are no open entries at the end of the internal storage array, the array
* is expanded. The size of the expanded array depends on the
* expansionMode and expansionFactor properties.
* The expansionMode determines whether the size of the array is
* multiplied by the expansionFactor (MULTIPLICATIVE_MODE) or if
* the expansion is additive (ADDITIVE_MODE -- expansionFactor
* storage locations added). The default expansionMode is
* MULTIPLICATIVE_MODE and the default expansionFactor is 2.0.
*
* The {@link #addElementRolling(double)} method adds a new element to the end
* of the internal storage array and adjusts the "usable window" of the internal
* array forward by one position (effectively making what was the second element
* the first, and so on). Repeated activations of this method (or activation of
* {@link #discardFrontElements(int)}) will effectively orphan the storage
* locations at the beginning of the internal storage array. To reclaim this
* storage, each time one of these methods is activated, the size of the
* internal storage array is compared to the number of addressable elements (the
* numElements property) and if the difference is too large, the
* internal array is contracted to size numElements + 1. The
* determination of when the internal storage array is "too large" depends on
* the expansionMode and contractionFactor
* properties. If the expansionMode is
* MULTIPLICATIVE_MODE, contraction is triggered when the ratio
* between storage array length and numElements exceeds
* contractionFactor. If the expansionMode is
* ADDITIVE_MODE, the number of excess storage locations is
* compared to contractionFactor.
*
* To avoid cycles of expansions and contractions, the
* expansionFactor must not exceed the
* contractionFactor. Constructors and mutators for both of these
* properties enforce this requirement, throwing IllegalArgumentException if it
* is violated.
*
* * @version $Revision: 618057 $ $Date: 2008-02-03 11:58:54 -0700 (Sun, 03 Feb * 2008) $ */
public class ResizableDoubleArray implements Serializable {
/** Serializable version identifier */ private static final long serialVersionUID = -3485529955529426875L; /** additive expansion mode */ public static final int ADDITIVE_MODE = 1; /** multiplicative expansion mode */ public static final int MULTIPLICATIVE_MODE = 0; /** * The contraction criteria determines when the internal array will be * contracted to fit the number of elements contained in the element array + * 1. */ protected float contractionCriteria = 2.5f; /** * The expansion factor of the array. When the array needs to be expanded, the * new array size will be*internalArray.length * expansionFactor* ifexpansionModeis set to MULTIPLICATIVE_MODE, or *internalArray.length + expansionFactorif *expansionModeis set to ADDITIVE_MODE. */ protected float expansionFactor = 2.0f; /** * Determines whether array expansion byexpansionFactoris * additive or multiplicative. */ protected int expansionMode = MULTIPLICATIVE_MODE; /** * The initial capacity of the array. Initial capacity is not exposed as a * property as it is only meaningful when passed to a constructor. */ protected int initialCapacity = 16; /** * The internal storage array. */ protected double[] internalArray; /** * The number of addressable elements in the array. Note that this has nothing * to do with the length of the internal storage array. */ protected int numElements = 0; /** * The position of the first addressable element in the internal storage * array. The addressable elements in the array are* internalArray[startIndex],...,internalArray[startIndex + numElements -1] **/ protected int startIndex = 0; /** * Create a ResizableArray with default properties.
-
*
initialCapacity = 16
* expansionMode = MULTIPLICATIVE_MODE
* expansionFactor = 2.5
* contractionFactor = 2.0
*
*/
public ResizableDoubleArray() {
internalArray = new double[initialCapacity];
}
/**
* Create a ResizableArray with the specified initial capacity. Other
* properties take default values:
* -
*
expansionMode = MULTIPLICATIVE_MODE
* expansionFactor = 2.5
* contractionFactor = 2.0
*
*
* @param initialCapacity
* The initial size of the internal storage array
* @throws IllegalArgumentException
* if initialCapacity is not > 0
*/
public ResizableDoubleArray(int initialCapacity) {
setInitialCapacity(initialCapacity);
internalArray = new double[this.initialCapacity];
}
/**
* * Create a ResizableArray with the specified initial capacity and expansion * factor. The remaining properties take default values: *
-
*
expansionMode = MULTIPLICATIVE_MODE
* contractionFactor = 0.5 + expansionFactor
*
* Throws IllegalArgumentException if the following conditions are not met: *
-
*
initialCapacity > 0
* expansionFactor > 1
*
*
* @param initialCapacity
* The initial size of the internal storage array
* @param expansionFactor
* the array will be expanded based on this parameter
* @throws IllegalArgumentException
* if parameters are not valid
*/
public ResizableDoubleArray(int initialCapacity, float expansionFactor) {
this.expansionFactor = expansionFactor;
setInitialCapacity(initialCapacity);
internalArray = new double[initialCapacity];
setContractionCriteria(expansionFactor + 0.5f);
}
/**
*
* Create a ResizableArray with the specified initialCapacity,
* expansionFactor, and contractionCriteria. The expansionMode
* will default to MULTIPLICATIVE_MODE.
*
* Throws IllegalArgumentException if the following conditions are not met: *
-
*
initialCapacity > 0
* expansionFactor > 1
* contractionFactor >= expansionFactor
*
*
* @param initialCapacity
* The initial size of the internal storage array
* @param expansionFactor
* the array will be expanded based on this parameter
* @param contractionCriteria
* The contraction Criteria.
* @throws IllegalArgumentException
* if parameters are not valid
*/
public ResizableDoubleArray(int initialCapacity, float expansionFactor, float contractionCriteria) {
this.expansionFactor = expansionFactor;
setContractionCriteria(contractionCriteria);
setInitialCapacity(initialCapacity);
internalArray = new double[initialCapacity];
}
/**
* * Create a ResizableArray with the specified properties. *
** Throws IllegalArgumentException if the following conditions are not met: *
-
*
initialCapacity > 0
* expansionFactor > 1
* contractionFactor >= expansionFactor
* expansionMode in {MULTIPLICATIVE_MODE, ADDITIVE_MODE}*
*
*
* @param initialCapacity
* the initial size of the internal storage array
* @param expansionFactor
* the array will be expanded based on this parameter
* @param contractionCriteria
* the contraction Criteria
* @param expansionMode
* the expansion mode
* @throws IllegalArgumentException
* if parameters are not valid
*/
public ResizableDoubleArray(int initialCapacity, float expansionFactor,
float contractionCriteria, int expansionMode) {
this.expansionFactor = expansionFactor;
setContractionCriteria(contractionCriteria);
setInitialCapacity(initialCapacity);
setExpansionMode(expansionMode);
internalArray = new double[initialCapacity];
}
/**
* Adds an element to the end of this expandable array.
*
* @param value
* to be added to end of array
*/
public synchronized void addElement(double value) {
numElements++;
if ((startIndex + numElements) > internalArray.length) {
expand();
}
internalArray[startIndex + (numElements - 1)] = value;
if (shouldContract()) {
contract();
}
}
/**
* * Adds an element to the end of the array and removes the first element in * the array. Returns the discarded first element. The effect is similar to a * push operation in a FIFO queue. *
** Example: If the array contains the elements 1, 2, 3, 4 (in that order) and * addElementRolling(5) is invoked, the result is an array containing the * entries 2, 3, 4, 5 and the value returned is 1. *
*
* @param value
* the value to be added to the array
* @return the value which has been discarded or "pushed" out of the array by
* this rolling insert
*/
public synchronized double addElementRolling(double value) {
double discarded = internalArray[startIndex];
if ((startIndex + (numElements + 1)) > internalArray.length) {
expand();
}
// Increment the start index
startIndex += 1;
// Add the new value
internalArray[startIndex + (numElements - 1)] = value;
// Check the contraction criteria
if (shouldContract()) {
contract();
}
return discarded;
}
/**
* Checks the expansion factor and the contraction criteria and throws an
* IllegalArgumentException if the contractionCriteria is less than the
* expansionCriteria
*
* @param expansionFactor
* factor to be checked
* @param contractionCritera
* critera to be checked
* @throws IllegalArgumentException
* if the contractionCriteria is less than the expansionCriteria.
*/
protected void checkContractExpand(float contractionCritera, float expansionFactor) {
if (contractionCritera < expansionFactor) {
String msg = "Contraction criteria can never be smaller than "
+ "the expansion factor. This would lead to a never "
+ "ending loop of expansion and contraction as a newly "
+ "expanded internal storage array would immediately "
+ "satisfy the criteria for contraction";
throw new IllegalArgumentException(msg);
}
if (contractionCriteria <= 1.0) {
String msg = "The contraction criteria must be a number larger "
+ "than one. If the contractionCriteria is less than or "
+ "equal to one an endless loop of contraction and "
+ "expansion would ensue as an internalArray.length "
+ "== numElements would satisfy the contraction criteria";
throw new IllegalArgumentException(msg);
}
if (expansionFactor <= 1.0) {
String msg = "The expansion factor must be a number greater than 1.0";
throw new IllegalArgumentException(msg);
}
}
/**
* Clear the array, reset the size to the initialCapacity and the number of
* elements to zero.
*/
public synchronized void clear() {
numElements = 0;
internalArray = new double[initialCapacity];
}
/**
* Contracts the storage array to the (size of the element set) + 1 - to avoid
* a zero length array. This function also resets the startIndex to zero.
*/
public synchronized void contract() {
double[] tempArray = new double[numElements + 1];
// Copy and swap - copy only the element array from the src array.
System.arraycopy(internalArray, startIndex, tempArray, 0, numElements);
internalArray = tempArray;
// Reset the start index to zero
startIndex = 0;
}
/**
* Discards the i<code> initial elements of the array. For example,
* if the array contains the elements 1,2,3,4, invoking
* <code>discardFrontElements(2) will cause the first two elements
* to be discarded, leaving 3,4 in the array. Throws illegalArgumentException
* if i exceeds numElements.
*
* @param i the number of elements to discard from the front of the array
* @throws IllegalArgumentException if i is greater than numElements.
*/
public synchronized void discardFrontElements(int i) {
if (i > numElements) {
String msg = "Cannot discard more elements than are" + "contained in this array.";
throw new IllegalArgumentException(msg);
} else if (i < 0) {
String msg = "Cannot discard a negative number of elements.";
throw new IllegalArgumentException(msg);
} else {
// "Subtract" this number of discarded from numElements
numElements -= i;
startIndex += i;
}
if (shouldContract()) {
contract();
}
}
/**
* Expands the internal storage array using the expansion factor.
*
* if expansionMode is set to MULTIPLICATIVE_MODE, the new
* array size will be internalArray.length * expansionFactor.
* If expansionMode is set to ADDITIVE_MODE, the length after
* expansion will be internalArray.length + expansionFactor
*
*/
protected synchronized void expand() {
// notice the use of Math.ceil(), this gaurantees that we will always
// have an array of at least currentSize + 1. Assume that the
// current initial capacity is 1 and the expansion factor
// is 1.000000000000000001. The newly calculated size will be
// rounded up to 2 after the multiplication is performed.
int newSize = 0;
if (expansionMode == MULTIPLICATIVE_MODE) {
newSize = (int) Math.ceil(internalArray.length * expansionFactor);
} else {
newSize = internalArray.length + Math.round(expansionFactor);
}
double[] tempArray = new double[newSize];
// Copy and swap
System.arraycopy(internalArray, 0, tempArray, 0, internalArray.length);
internalArray = tempArray;
}
/**
* Expands the internal storage array to the specified size.
*
* @param size
* Size of the new internal storage array
*/
private synchronized void expandTo(int size) {
double[] tempArray = new double[size];
// Copy and swap
System.arraycopy(internalArray, 0, tempArray, 0, internalArray.length);
internalArray = tempArray;
}
/**
* The contraction criteria defines when the internal array will contract to
* store only the number of elements in the element array. If the
* expansionMode is MULTIPLICATIVE_MODE,
* contraction is triggered when the ratio between storage array length and
* numElements exceeds contractionFactor. If
* the expansionMode is ADDITIVE_MODE, the
* number of excess storage locations is compared to
* contractionFactor.
*
* @return the contraction criteria used to reclaim memory.
*/
public float getContractionCriteria() {
return contractionCriteria;
}
/**
* Returns the element at the specified index
*
* @param index
* index to fetch a value from
* @return value stored at the specified index
* @throws ArrayIndexOutOfBoundsException
* if index is less than zero or is greater than
* getNumElements() - 1.
*/
public synchronized double getElement(int index) {
if (index >= numElements) {
String msg = "The index specified: " + index
+ " is larger than the current number of elements";
throw new ArrayIndexOutOfBoundsException(msg);
} else if (index >= 0) {
return internalArray[startIndex + index];
} else {
String msg = "Elements cannot be retrieved from a negative array index";
throw new ArrayIndexOutOfBoundsException(msg);
}
}
/**
* Returns a double array containing the elements of this
* ResizableArray. This method returns a copy, not a reference
* to the underlying array, so that changes made to the returned array have no
* effect on this ResizableArray.
*
* @return the double array.
*/
public synchronized double[] getElements() {
double[] elementArray = new double[numElements];
System.arraycopy(internalArray, startIndex, elementArray, 0, numElements);
return elementArray;
}
/**
* The expansion factor controls the size of a new aray when an array needs to
* be expanded. The expansionMode determines whether the size
* of the array is multiplied by the expansionFactor
* (MULTIPLICATIVE_MODE) or if the expansion is additive (ADDITIVE_MODE --
* expansionFactor storage locations added). The default
* expansionMode is MULTIPLICATIVE_MODE and the default
* expansionFactor is 2.0.
*
* @return the expansion factor of this expandable double array
*/
public float getExpansionFactor() {
return expansionFactor;
}
/**
* The expansionMode determines whether the internal storage
* array grows additively (ADDITIVE_MODE) or multiplicatively
* (MULTIPLICATIVE_MODE) when it is expanded.
*
* @return Returns the expansionMode.
*/
public int getExpansionMode() {
return expansionMode;
}
/**
* Notice the package scope on this method. This method is simply here for the
* JUnit test, it allows us check if the expansion is working properly after a
* number of expansions. This is not meant to be a part of the public
* interface of this class.
*
* @return the length of the internal storage array.
*/
synchronized int getInternalLength() {
return (internalArray.length);
}
/**
* Returns the number of elements currently in the array. Please note that
* this is different from the length of the internal storage array.
*
* @return number of elements
*/
public synchronized int getNumElements() {
return (numElements);
}
/**
* Returns the internal storage array. Note that this method returns a
* reference to the internal storage array, not a copy, and to correctly
* address elements of the array, the startIndex is required
* (available via the {@link #start} method). This method should only be used
* in cases where copying the internal array is not practical. The
* {@link #getElements} method should be used in all other cases.
*
*
* @return the internal storage array used by this object
*/
public synchronized double[] getValues() {
return (internalArray);
}
/**
* Sets the contraction criteria for this ExpandContractDoubleArray.
*
* @param contractionCriteria
* contraction criteria
*/
public void setContractionCriteria(float contractionCriteria) {
checkContractExpand(contractionCriteria, getExpansionFactor());
this.contractionCriteria = contractionCriteria;
}
/**
* Sets the element at the specified index. If the specified index is greater
* than getNumElements() - 1, the numElements
* property is increased to index +1 and additional storage is
* allocated (if necessary) for the new element and all (uninitialized)
* elements between the new element and the previous end of the array).
*
* @param index
* index to store a value in
* @param value
* value to store at the specified index
* @throws ArrayIndexOutOfBoundsException
* if index is less than zero.
*/
public synchronized void setElement(int index, double value) {
if (index < 0) {
String msg = "Cannot set an element at a negative index";
throw new ArrayIndexOutOfBoundsException(msg);
}
if (index + 1 > numElements) {
numElements = index + 1;
}
if ((startIndex + index) >= internalArray.length) {
expandTo(startIndex + (index + 1));
}
internalArray[startIndex + index] = value;
}
/**
* Sets the expansionFactor. Throws IllegalArgumentException if the the
* following conditions are not met:
* -
*
expansionFactor > 1
* contractionFactor >= expansionFactor
*
*
* @param expansionFactor
* the new expansion factor value.
* @throws IllegalArgumentException
* if expansionFactor is <= 1 or greater than contractionFactor
*/
public void setExpansionFactor(float expansionFactor) {
checkContractExpand(getContractionCriteria(), expansionFactor);
// The check above verifies that the expansion factor is > 1.0;
this.expansionFactor = expansionFactor;
}
/**
* Sets the expansionMode. The specified value must be one of
* ADDITIVE_MODE, MULTIPLICATIVE_MODE.
*
* @param expansionMode
* The expansionMode to set.
* @throws IllegalArgumentException
* if the specified mode value is not valid
*/
public void setExpansionMode(int expansionMode) {
if (expansionMode != MULTIPLICATIVE_MODE && expansionMode != ADDITIVE_MODE) {
throw new IllegalArgumentException("Illegal expansionMode setting.");
}
this.expansionMode = expansionMode;
}
/**
* Sets the initial capacity. Should only be invoked by constructors.
*
* @param initialCapacity
* of the array
* @throws IllegalArgumentException
* if initialCapacity is not positive.
*/
protected void setInitialCapacity(int initialCapacity) {
if (initialCapacity > 0) {
synchronized (this) {
this.initialCapacity = initialCapacity;
}
} else {
String msg = "The initial capacity supplied: " + initialCapacity
+ "must be a positive integer";
throw new IllegalArgumentException(msg);
}
}
/**
* This function allows you to control the number of elements contained in
* this array, and can be used to "throw out" the last n values in an array.
* This function will also expand the internal array as needed.
*
* @param i
* a new number of elements
* @throws IllegalArgumentException
* if i is negative.
*/
public synchronized void setNumElements(int i) {
// If index is negative thrown an error
if (i < 0) {
String msg = "Number of elements must be zero or a positive " + "integer";
throw new IllegalArgumentException(msg);
}
// Test the new num elements, check to see if the array needs to be
// expanded to accomodate this new number of elements
if ((startIndex + i) > internalArray.length) {
expandTo(startIndex + i);
}
// Set the new number of elements to new value
numElements = i;
}
/**
* Returns true if the internal storage array has too many unused storage
* positions.
*
* @return true if array satisfies the contraction criteria
*/
private synchronized boolean shouldContract() {
if (expansionMode == MULTIPLICATIVE_MODE) {
return (internalArray.length / ((float) numElements)) > contractionCriteria;
} else {
return (internalArray.length - numElements) > contractionCriteria;
}
}
/**
* Returns the starting index of the internal array. The starting index is the
* position of the first addressable element in the internal storage array.
* The addressable elements in the array are
* internalArray[startIndex],...,internalArray[startIndex + numElements -1]
*
*
* @return starting index
*/
public synchronized int start() {
return startIndex;
}
}
</source>
Dynamic Int Array
<source lang="java">
/* Copyright (C) 2007 Mobixess Inc. http://www.java-objects-database.ru This file is part of the JODB (Java Objects Database) open source project. JODB is free software; you can redistribute it and/or modify it under the terms of version 2 of the GNU General Public License as published by the Free Software Foundation. JODB is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with this program; if not, write to the Free Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
- /
public class DynamicIntArray {
final static int DEFAULT_CHUNK_SIZE = 256; final static int DEFAULT_CHUNKS = 16; private int _chunkSize; private int[][] _data; private int _length;
public DynamicIntArray() {
this(DEFAULT_CHUNK_SIZE);
}
public DynamicIntArray(int chunkSize) {
_chunkSize = chunkSize;
_data = new int[DEFAULT_CHUNKS][];
}
public boolean isEmpty() {
return (_length == 0);
}
private void ensureCapacity(int index) {
if (index >= _length) {
int i = index / _chunkSize;
if (i >= _data.length) {
// grow by 50%
int new_size = (i * 3) / 2 + 1;
int[][] newChunk = new int[new_size][];
System.arraycopy(_data, 0, newChunk, 0, _data.length);
_data = newChunk;
}
_length = index + 1;
}
}
public int get(int index) {
if (index >= _length) {
throw new IndexOutOfBoundsException("Index " + index
+ " is outside of 0.." + (_length - 1));
}
int i = index / _chunkSize;
int j = index % _chunkSize;
if (_data[i] == null) {
return 0;
} else {
return _data[i][j];
}
}
public void set(int index, int value) {
int i = index / _chunkSize;
int j = index % _chunkSize;
ensureCapacity(index);
if (_data[i] == null) {
_data[i] = new int[_chunkSize];
}
_data[i][j] = value;
}
public int size() {
return _length;
}
public String toString() {
int i;
StringBuffer sb = new StringBuffer(_length * 4);
sb.append("{");
int l = _length - 1;
for (i = 0; i < l; i++) {
sb.append(get(i));
sb.append(",");
}
sb.append(get(i));
sb.append("}");
return sb.toString();
}
}
</source>
Dynamic Long Array
<source lang="java">
/* Copyright (C) 2007 Mobixess Inc. http://www.java-objects-database.ru This file is part of the JODB (Java Objects Database) open source project. JODB is free software; you can redistribute it and/or modify it under the terms of version 2 of the GNU General Public License as published by the Free Software Foundation. JODB is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with this program; if not, write to the Free Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
- /
public class DynamicLongArray {
final static int DEFAULT_CHUNK_SIZE = 256; final static int DEFAULT_CHUNKS = 16; private int _chunkSize; private long[][] _data; private int _length;
public DynamicLongArray() {
this(DEFAULT_CHUNK_SIZE);
}
public DynamicLongArray(int chunkSize) {
_chunkSize = chunkSize;
_data = new long[DEFAULT_CHUNKS][];
}
public boolean isEmpty() {
return (_length == 0);
}
private void ensureCapacity(int index) {
if (index >= _length) {
int i = index / _chunkSize;
if (i >= _data.length) {
// grow by 50%
int new_size = (i * 3) / 2 + 1;
long[][] newChunk = new long[new_size][];
System.arraycopy(_data, 0, newChunk, 0, _data.length);
_data = newChunk;
}
_length = index + 1;
}
}
public long get(int index) {
if (index >= _length) {
throw new IndexOutOfBoundsException("Index " + index
+ " is outside of 0.." + (_length - 1));
}
int i = index / _chunkSize;
int j = index % _chunkSize;
if (_data[i] == null) {
return 0;
} else {
return _data[i][j];
}
}
public void set(int index, long value) {
int i = index / _chunkSize;
int j = index % _chunkSize;
ensureCapacity(index);
if (_data[i] == null) {
_data[i] = new long[_chunkSize];
}
_data[i][j] = value;
}
public int size() {
return _length;
}
public String toString() {
int i;
StringBuffer sb = new StringBuffer(_length * 4);
sb.append("{");
int l = _length - 1;
for (i = 0; i < l; i++) {
sb.append(get(i));
sb.append(",");
}
sb.append(get(i));
sb.append("}");
return sb.toString();
}
}
</source>
Extensible vector of bytes
<source lang="java">
/***
* ASM: a very small and fast Java bytecode manipulation framework * Copyright (c) 2000-2005 INRIA, France Telecom * All rights reserved. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions * are met: * 1. Redistributions of source code must retain the above copyright * notice, this list of conditions and the following disclaimer. * 2. Redistributions in binary form must reproduce the above copyright * notice, this list of conditions and the following disclaimer in the * documentation and/or other materials provided with the distribution. * 3. Neither the name of the copyright holders nor the names of its * contributors may be used to endorse or promote products derived from * this software without specific prior written permission. * * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF * THE POSSIBILITY OF SUCH DAMAGE. */
/**
* A dynamically extensible vector of bytes. This class is roughly equivalent to * a DataOutputStream on top of a ByteArrayOutputStream, but is more efficient. * * @author Eric Bruneton */
public class ByteVector {
/**
* The content of this vector.
*/
byte[] data;
/**
* Actual number of bytes in this vector.
*/
int length;
/**
* Constructs a new {@link ByteVector ByteVector} with a default initial
* size.
*/
public ByteVector() {
data = new byte[64];
}
/**
* Constructs a new {@link ByteVector ByteVector} with the given initial
* size.
*
* @param initialSize the initial size of the byte vector to be constructed.
*/
public ByteVector(final int initialSize) {
data = new byte[initialSize];
}
/**
* Puts a byte into this byte vector. The byte vector is automatically
* enlarged if necessary.
*
* @param b a byte.
* @return this byte vector.
*/
public ByteVector putByte(final int b) {
int length = this.length;
if (length + 1 > data.length) {
enlarge(1);
}
data[length++] = (byte) b;
this.length = length;
return this;
}
/**
* Puts two bytes into this byte vector. The byte vector is automatically
* enlarged if necessary.
*
* @param b1 a byte.
* @param b2 another byte.
* @return this byte vector.
*/
ByteVector put11(final int b1, final int b2) {
int length = this.length;
if (length + 2 > data.length) {
enlarge(2);
}
byte[] data = this.data;
data[length++] = (byte) b1;
data[length++] = (byte) b2;
this.length = length;
return this;
}
/**
* Puts a short into this byte vector. The byte vector is automatically
* enlarged if necessary.
*
* @param s a short.
* @return this byte vector.
*/
public ByteVector putShort(final int s) {
int length = this.length;
if (length + 2 > data.length) {
enlarge(2);
}
byte[] data = this.data;
data[length++] = (byte) (s >>> 8);
data[length++] = (byte) s;
this.length = length;
return this;
}
/**
* Puts a byte and a short into this byte vector. The byte vector is
* automatically enlarged if necessary.
*
* @param b a byte.
* @param s a short.
* @return this byte vector.
*/
ByteVector put12(final int b, final int s) {
int length = this.length;
if (length + 3 > data.length) {
enlarge(3);
}
byte[] data = this.data;
data[length++] = (byte) b;
data[length++] = (byte) (s >>> 8);
data[length++] = (byte) s;
this.length = length;
return this;
}
/**
* Puts an int into this byte vector. The byte vector is automatically
* enlarged if necessary.
*
* @param i an int.
* @return this byte vector.
*/
public ByteVector putInt(final int i) {
int length = this.length;
if (length + 4 > data.length) {
enlarge(4);
}
byte[] data = this.data;
data[length++] = (byte) (i >>> 24);
data[length++] = (byte) (i >>> 16);
data[length++] = (byte) (i >>> 8);
data[length++] = (byte) i;
this.length = length;
return this;
}
/**
* Puts a long into this byte vector. The byte vector is automatically
* enlarged if necessary.
*
* @param l a long.
* @return this byte vector.
*/
public ByteVector putLong(final long l) {
int length = this.length;
if (length + 8 > data.length) {
enlarge(8);
}
byte[] data = this.data;
int i = (int) (l >>> 32);
data[length++] = (byte) (i >>> 24);
data[length++] = (byte) (i >>> 16);
data[length++] = (byte) (i >>> 8);
data[length++] = (byte) i;
i = (int) l;
data[length++] = (byte) (i >>> 24);
data[length++] = (byte) (i >>> 16);
data[length++] = (byte) (i >>> 8);
data[length++] = (byte) i;
this.length = length;
return this;
}
/**
* Puts an UTF8 string into this byte vector. The byte vector is
* automatically enlarged if necessary.
*
* @param s a String.
* @return this byte vector.
*/
public ByteVector putUTF8(final String s) {
int charLength = s.length();
if (length + 2 + charLength > data.length) {
enlarge(2 + charLength);
}
int len = length;
byte[] data = this.data;
// optimistic algorithm: instead of computing the byte length and then
// serializing the string (which requires two loops), we assume the byte
// length is equal to char length (which is the most frequent case), and
// we start serializing the string right away. During the serialization,
// if we find that this assumption is wrong, we continue with the
// general method.
data[len++] = (byte) (charLength >>> 8);
data[len++] = (byte) (charLength);
for (int i = 0; i < charLength; ++i) {
char c = s.charAt(i);
if (c >= "\001" && c <= "\177") {
data[len++] = (byte) c;
} else {
int byteLength = i;
for (int j = i; j < charLength; ++j) {
c = s.charAt(j);
if (c >= "\001" && c <= "\177") {
byteLength++;
} else if (c > "\u07FF") {
byteLength += 3;
} else {
byteLength += 2;
}
}
data[length] = (byte) (byteLength >>> 8);
data[length + 1] = (byte) (byteLength);
if (length + 2 + byteLength > data.length) {
length = len;
enlarge(2 + byteLength);
data = this.data;
}
for (int j = i; j < charLength; ++j) {
c = s.charAt(j);
if (c >= "\001" && c <= "\177") {
data[len++] = (byte) c;
} else if (c > "\u07FF") {
data[len++] = (byte) (0xE0 | c >> 12 & 0xF);
data[len++] = (byte) (0x80 | c >> 6 & 0x3F);
data[len++] = (byte) (0x80 | c & 0x3F);
} else {
data[len++] = (byte) (0xC0 | c >> 6 & 0x1F);
data[len++] = (byte) (0x80 | c & 0x3F);
}
}
break;
}
}
length = len;
return this;
}
/**
* Puts an array of bytes into this byte vector. The byte vector is
* automatically enlarged if necessary.
*
* @param b an array of bytes. May be null to put len
* null bytes into this byte vector.
* @param off index of the fist byte of b that must be copied.
* @param len number of bytes of b that must be copied.
* @return this byte vector.
*/
public ByteVector putByteArray(final byte[] b, final int off, final int len)
{
if (length + len > data.length) {
enlarge(len);
}
if (b != null) {
System.arraycopy(b, off, data, length, len);
}
length += len;
return this;
}
/**
* Enlarge this byte vector so that it can receive n more bytes.
*
* @param size number of additional bytes that this byte vector should be
* able to receive.
*/
private void enlarge(final int size) {
int length1 = 2 * data.length;
int length2 = length + size;
byte[] newData = new byte[length1 > length2 ? length1 : length2];
System.arraycopy(data, 0, newData, 0, length);
data = newData;
}
}
</source>
Fast Array
<source lang="java">
/*
* Copyright 2003-2007 the original author or authors. * * Licensed under the Apache License, Version 2.0 (the "License"); * you may not use this file except in compliance with the License. * You may obtain a copy of the License at * * http://www.apache.org/licenses/LICENSE-2.0 * * Unless required by applicable law or agreed to in writing, software * distributed under the License is distributed on an "AS IS" BASIS, * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. * See the License for the specific language governing permissions and * limitations under the License. */
import java.util.AbstractList; import java.util.Collection; import java.util.List; public class FastArray implements Cloneable {
private Object[] data;
public int size;
public static final FastArray EMPTY_LIST = new FastArray(0);
public FastArray(int initialCapacity) {
data = new Object[initialCapacity];
}
public FastArray() {
this (8);
}
public FastArray(Collection c) {
this (c.toArray());
}
public FastArray(Object[] objects) {
data = objects;
size = objects.length;
}
public Object get(int index) {
return data [index];
}
public void add(Object o) {
if (size == data.length) {
Object [] newData = new Object[size == 0 ? 8 : size*2];
System.arraycopy(data, 0, newData, 0, size);
data = newData;
}
data [size++] = o;
}
public void set(int index, Object o) {
data [index] = o;
}
public int size() {
return size;
}
public void clear() {
data = new Object[data.length];
size = 0;
}
public void addAll(FastArray newData) {
addAll(newData.data, newData.size);
}
public void addAll(Object [] newData, int size) {
if (size == 0)
return;
final int newSize = this.size + size;
if (newSize > data.length) {
Object nd [] = new Object [newSize];
System.arraycopy(data, 0, nd, 0, this.size);
data = nd;
}
System.arraycopy(newData, 0, data, this.size, size);
this.size = newSize;
}
public FastArray copy() {
final Object[] newData = new Object[size];
System.arraycopy(data, 0, newData, 0, size);
return new FastArray(newData);
}
public boolean isEmpty() {
return size == 0;
}
public void addAll(List coll) {
final Object[] newData = coll.toArray();
addAll(newData, newData.length);
}
public void remove(int index) {
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(data, index+1, data, index, numMoved);
data[--size] = null;
}
public List toList () {
return new AbstractList() {
public Object get(int index) {
return FastArray.this.get(index);
}
public int size() {
return size;
}
};
}
public Object[] getArray() {
return data;
}
public String toString() {
if (size() == 0) return "[]";
return toList().toString();
}
}
</source>
Growable int[]
<source lang="java">
/*
* Copyright (c) 1998 - 2005 Versant Corporation * All rights reserved. This program and the accompanying materials * are made available under the terms of the Eclipse Public License v1.0 * which accompanies this distribution, and is available at * http://www.eclipse.org/legal/epl-v10.html * * Contributors: * Versant Corporation - initial API and implementation */
/**
* Growable int[]. This is based com.sosnoski.util.array.IntArray from * Sosnoski Software Solutions, Inc. */
public final class IntArray {
private int[] buf;
private int size;
public IntArray() {
this(64);
}
public IntArray(int capacity) {
buf = new int[capacity];
}
public int size() {
return size;
}
private void ensureCapacity(int len) {
if (size + len > buf.length) {
int n = buf.length * 3 / 2 + 1;
if (size + len > n) {
n = size + len;
}
int[] a = new int[n];
System.arraycopy(buf, 0, a, 0, size);
buf = a;
}
}
public void add(int v) {
ensureCapacity(size + 1);
buf[size++] = v;
}
/**
* Add a value at a specified index in the array.
*/
public void add(int index, int value) {
ensureCapacity(size + 1);
if (index == size) {
buf[size++] = value;
} else {
System.arraycopy(buf, index, buf, index + 1, size - index);
buf[index] = value;
}
}
/**
* Constructs and returns a simple array containing the same data as held
* in this growable array.
*/
public int[] toArray() {
int[] a = new int[size];
System.arraycopy(buf, 0, a, 0, size);
return a;
}
public void clear() {
size = 0;
}
/**
* Retrieve the value present at an index position in the array.
*/
public int get(int index) {
return buf[index];
}
}
</source>
Growable String array with type specific access methods.
<source lang="java">
/* Copyright (c) 2000-2008, Dennis M. Sosnoski. All rights reserved. Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met:
* Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer. * Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer in the documentation and/or other materials provided with the distribution. * Neither the name of JiBX nor the names of its contributors may be used to endorse or promote products derived from this software without specific prior written permission.
THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
- /
import java.lang.reflect.Array; /**
* Growable String array with type specific access methods. This
* implementation is unsynchronized in order to provide the best possible
* performance for typical usage scenarios, so explicit synchronization must
* be implemented by a wrapper class or directly by the application in cases
* where instances are modified in a multithreaded environment.
*
* @author Dennis M. Sosnoski
*/
public class StringArray {
/** Default initial array size. */
public static final int DEFAULT_SIZE = 8;
/** Size of the current array. */
private int m_countLimit;
/** The number of values currently present in the array. */
private int m_countPresent;
/** Maximum size increment for growing array. */
private int m_maximumGrowth;
/** The underlying array used for storing the data. */
private String[] m_baseArray;
/**
* Constructor with full specification.
*
* @param size number of String values initially allowed in
* array
* @param growth maximum size increment for growing array
*/
public StringArray(int size, int growth) {
String[] array = new String[size];
m_countLimit = size;
m_maximumGrowth = growth;
m_baseArray = array;
}
/**
* Constructor with initial size specified.
*
* @param size number of String values initially allowed in
* array
*/
public StringArray(int size) {
this(size, Integer.MAX_VALUE);
}
/**
* Default constructor.
*/
public StringArray() {
this(DEFAULT_SIZE);
}
/**
* Copy (clone) constructor.
*
* @param base instance being copied
*/
public StringArray(StringArray base) {
this(base.m_countLimit, base.m_maximumGrowth);
System.arraycopy(base.m_baseArray, 0, m_baseArray, 0,
base.m_countPresent);
m_countPresent = base.m_countPresent;
}
/**
* Copy data after array resize. This just copies the entire contents of the
* old array to the start of the new array. It should be overridden in cases
* where data needs to be rearranged in the array after a resize.
*
* @param base original array containing data
* @param grown resized array for data
*/
private void resizeCopy(Object base, Object grown) {
System.arraycopy(base, 0, grown, 0, Array.getLength(base));
}
/**
* Discards values for a range of indices in the array. Clears references to
* removed values.
*
* @param from index of first value to be discarded
* @param to index past last value to be discarded
*/
private void discardValues(int from, int to) {
for (int i = from; i < to; i++) {
m_baseArray[i] = null;
}
}
/**
* Increase the size of the array to at least a specified size. The array
* will normally be at least doubled in size, but if a maximum size
* increment was specified in the constructor and the value is less than
* the current size of the array, the maximum increment will be used
* instead. If the requested size requires more than the default growth,
* the requested size overrides the normal growth and determines the size
* of the replacement array.
*
* @param required new minimum size required
*/
private void growArray(int required) {
int size = Math.max(required,
m_countLimit + Math.min(m_countLimit, m_maximumGrowth));
String[] grown = new String[size];
resizeCopy(m_baseArray, grown);
m_countLimit = size;
m_baseArray = grown;
}
/**
* Ensure that the array has the capacity for at least the specified
* number of values.
*
* @param min minimum capacity to be guaranteed
*/
public final void ensureCapacity(int min) {
if (min > m_countLimit) {
growArray(min);
}
}
/**
* Overwrite an existing value in the array.
*
* @param index position of value to be overwritten
* @param value value to be added
*/
public void set(int index, String value) {
if (index < m_countPresent) {
m_baseArray[index] = value;
} else {
throw new IllegalArgumentException("Index value out of range");
}
}
/**
* Add a value at the end of the array.
*
* @param value value to be added
*/
public void add(String value) {
int index = getAddIndex();
m_baseArray[index] = value;
}
/**
* Add an array of values at the end of the array.
*
* @param values values to be added
*/
public void addAll(String[] values) {
ensureCapacity(m_countPresent+values.length);
for (int i = 0; i < values.length; i++) {
m_baseArray[m_countPresent++] = values[i];
}
}
/**
* Remove some number of values from the end of the array.
*
* @param count number of values to be removed
* @exception ArrayIndexOutOfBoundsException on attempt to remove more than
* the count present
*/
public void remove(int count) {
int start = m_countPresent - count;
if (start >= 0) {
discardValues(start, m_countPresent);
m_countPresent = start;
} else {
throw new ArrayIndexOutOfBoundsException
("Attempt to remove too many values from array");
}
}
/**
* Get a value from the array.
*
* @param index index of value to be returned
* @return value from stack
* @exception ArrayIndexOutOfBoundsException on attempt to access outside
* valid range
*/
public String get(int index) {
if (m_countPresent > index) {
return m_baseArray[index];
} else {
throw new ArrayIndexOutOfBoundsException
("Attempt to access past end of array");
}
}
/**
* Constructs and returns a simple array containing the same data as held
* in this array.
*
* @return array containing a copy of the data
*/
public String[] toArray() {
String[] copy = new String[m_countPresent];
System.arraycopy(m_baseArray, 0, copy, 0, m_countPresent);
return copy;
}
/**
* Duplicates the object with the generic call.
*
* @return a copy of the object
*/
public Object clone() {
return new StringArray(this);
}
/**
* Gets the array offset for appending a value to those in the array. If the
* underlying array is full, it is grown by the appropriate size increment
* so that the index value returned is always valid for the array in use by
* the time of the return.
*
* @return index position for added element
*/
private int getAddIndex() {
int index = m_countPresent++;
if (m_countPresent > m_countLimit) {
growArray(m_countPresent);
}
return index;
}
/**
* Get the number of values currently present in the array.
*
* @return count of values present
*/
public int size() {
return m_countPresent;
}
/**
* Check if array is empty.
*
* @return true if array empty, false if not
*/
public boolean isEmpty() {
return m_countPresent == 0;
}
/**
* Set the array to the empty state.
*/
public void clear() {
discardValues(0, m_countPresent);
m_countPresent = 0;
}
}
</source>
Int Array
<source lang="java">
/*
* Copyright (c) 2002-2008 "Neo Technology," * Network Engine for Objects in Lund AB [1] * * This file is part of Neo4j. * * Neo4j is free software: you can redistribute it and/or modify * it under the terms of the GNU Affero General Public License as * published by the Free Software Foundation, either version 3 of the * License, or (at your option) any later version. * * This program is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * GNU Affero General Public License for more details. * * You should have received a copy of the GNU Affero General Public License * along with this program. If not, see <http://www.gnu.org/licenses/>. */
import java.util.HashSet; import java.util.Set; public class IntArray {
private int[] rels;
private int arrayCount = 0;
public IntArray()
{
rels = new int[2];
}
public IntArray( int initialCapacity )
{
rels = new int[ initialCapacity ];
}
public IntArray( int[] array )
{
rels = array;
arrayCount = array.length;
}
public void add( int id )
{
if ( arrayCount == rels.length )
{
int newRels[] = new int[rels.length * 2];
System.arraycopy( rels, 0, newRels, 0, rels.length );
rels = newRels;
}
rels[arrayCount++] = id;
}
public void addAll( IntArray array )
{
if ( array == null )
{
return;
}
if ( array.length() + arrayCount > rels.length )
{
int newSize = rels.length * 2;
while ( array.length() + arrayCount > newSize )
{
newSize = newSize * 2;
}
int newRels[] = new int[newSize];
System.arraycopy( rels, 0, newRels, 0, arrayCount );
rels = newRels;
}
System.arraycopy( array.getArray(), 0, rels, arrayCount,
array.length() );
arrayCount += array.length();
}
public int length()
{
return arrayCount;
}
public int[] getArray()
{
return rels;
}
public int get( int i )
{
assert i >= 0 && i < arrayCount;
return rels[i];
}
public static IntArray composeNew( IntArray src, IntArray add,
IntArray remove )
{
if ( remove == null )
{
if ( src == null )
{
return add;
}
if ( add != null )
{
IntArray newArray = new IntArray( add.length() + src.length() );
newArray.addAll( src );
newArray.addAll( add );
return newArray;
}
return src;
}
else
{
if ( src == null && add == null )
{
return null;
}
int newLength = 0;
if ( add != null )
{
newLength += add.length();
}
if ( src != null )
{
newLength += src.length();
}
IntArray newArray = new IntArray( newLength );
Set<Integer> set = new HashSet<Integer>( remove.length() + 1,
1.0f );
for ( int i = 0; i < remove.length(); i++ )
{
set.add( remove.get( i ) );
}
newArray.addAll( src );
for ( int i = 0; i < newArray.length(); i++ )
{
int value = newArray.get( i );
if ( set.contains( value ) )
{
boolean swapSuccessful = false;
for ( int j = newArray.length() - 1; j >= i + 1; j--)
{
int backValue = newArray.get( j );
newArray.arrayCount--;
if ( !set.contains( backValue) )
{
newArray.getArray()[i] = backValue;
swapSuccessful = true;
break;
}
}
if ( !swapSuccessful ) // all elements from pos in remove
{
newArray.arrayCount--;
}
}
}
if ( add != null )
{
for ( int i = 0; i < add.length(); i++ )
{
int value = add.get( i );
if ( !set.contains( value ) )
{
newArray.add( value );
}
}
}
return newArray;
}
}
/* public static IntArray composeNew( IntArray src, IntArray add,
IntArray remove )
{
if ( remove == null )
{
if ( src == null )
{
return add;
}
if ( add != null )
{
IntArray newArray = new IntArray( add.length() + src.length() );
newArray.addAll( src );
newArray.addAll( add );
return newArray;
}
return src;
}
else
{
if ( src == null )
{
return null;
}
// TODO: merge add and remove array then append add array to result
int[] newArray = new int[src.length()];
int[] srcArray = src.getArray();
int[] removeArray = remove.getArray();
assert removeArray.length <= srcArray.length;
System.arraycopy( srcArray, 0, newArray, 0, src.length() );
Arrays.sort( newArray );
Arrays.sort( removeArray );
int newArraySize = newArray.length;
int startSearchFrom = 0;
int checkTo = removeArray.length; // can decrease if we swap
for ( int i = 0; i < checkTo; i++ )
{
int index = binarySearch( newArray, startSearchFrom,
newArraySize, removeArray[i] );
if ( index >= 0 )
{
// next search can start from here
startSearchFrom = index + 1;
// find element we can swap with
for ( int j = newArraySize - 1; j >= startSearchFrom; j-- )
{
int swapValue = newArray[j];
int rIndex = binarySearch( removeArray, i, checkTo,
swapValue );
newArraySize--;
// ok last element in newArray ==
// last element in removeArray
if ( rIndex > 0 )
{
checkTo--;
// continue with second last to see if that is
// swapable
}
else // we swap with this element
{
newArray[index] = newArray[j];
break;
}
}
}
}
IntArray newIntArray = new IntArray( newArray );
newIntArray.arrayCount = newArraySize;
return newIntArray;
}
}
private static int binarySearch( int[] array, int startOffset,
int endOffset, int value )
{
int pIndex = startOffset + ( endOffset - startOffset ) / 2;
int valueFound = array[pIndex];
if ( valueFound == value )
{
return pIndex;
}
if ( pIndex == startOffset ) // search exhausted
{
return -1;
}
if ( value < valueFound )
{
return binarySearch( array, startOffset, pIndex, value );
}
else
{
return binarySearch( array, pIndex, endOffset, value );
}
}*/
}
</source>
Int Array List
<source lang="java">
/*
* Copyright 2004 (C) TJDO. * All rights reserved. * * This software is distributed under the terms of the TJDO License version 1.0. * See the terms of the TJDO License in the documentation provided with this software. * * $Id: IntArrayList.java,v 1.1 2004/01/18 03:01:07 jackknifebarber Exp $ */
import java.util.Arrays;
/**
* A variation on the standard ArrayList class that efficiently handles arrays * of integers. * Using this class rather than ArrayList avoids the need to "box" each * element in an instance of java.lang.Integer. * It is useful where performance is important. * * @author * @version $Revision: 1.1 $ */
public class IntArrayList implements Cloneable {
private int[] elements; private int size = 0;
/**
* Constructs an empty list with an initial capacity of ten.
*/
public IntArrayList()
{
this(10);
}
/**
* Constructs an empty list with the specified initial capacity.
*
* @param initialCapacity
* The initial capacity of the list.
*
* @exception IllegalArgumentException
* If the specified initial capacity is negative.
*/
public IntArrayList(int initialCapacity)
{
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal capacity: "+ initialCapacity);
elements = new int[initialCapacity];
}
/**
* Constructs a list containing the elements of the specified array.
* The IntArrayList instance has an initial capacity of 110% the
* size of the specified collection.
*
* @param initialContents
* The array whose elements are to be placed into this list.
*/
public IntArrayList(int[] initialContents)
{
size = initialContents.length;
elements = new int[(int)Math.min((size * 11L)/10, Integer.MAX_VALUE)];
System.arraycopy(initialContents, 0, elements, 0, size);
}
/**
* Trims the capacity of this IntArrayList instance to be the
* list"s current size.
* An application can use this operation to minimize the storage of an
* IntArrayList instance.
*/
public void trimToSize()
{
if (size < elements.length)
{
int[] newelems = new int[size];
System.arraycopy(elements, 0, newelems, 0, size);
elements = newelems;
}
}
/**
* Increases the capacity of this IntArrayList instance, if
* necessary, to ensure that it can hold at least the number of elements
* specified by the minimum capacity argument.
*
* @param minCapacity
* The desired minimum capacity.
*/
public void ensureCapacity(int minCapacity)
{
int oldCapacity = elements.length;
if (minCapacity > oldCapacity)
{
int[] newelems = new int[(int)Math.min((oldCapacity * 3L)/2, Integer.MAX_VALUE)];
System.arraycopy(elements, 0, newelems, 0, size);
elements = newelems;
}
}
/**
* Returns the number of elements in this list.
*
* @return The number of elements in this list.
*/
public int size()
{
return size;
}
/**
* Tests if this list has no elements.
*
* @return true if this list has no elements;
* false otherwise.
*/
public boolean isEmpty()
{
return size == 0;
}
/**
* Returns true if this list contains the specified element.
*
* @param elem element whose presence in this List is to be tested.
*
* @return true if the specified element is present;
* false otherwise.
*/
public boolean contains(int elem)
{
return indexOf(elem) >= 0;
}
/**
* Searches for the first occurence of the given argument.
*
* @param elem
* An integer to search for.
*
* @return The index of the first occurrence of the argument in this
* list; returns -1 if the value is not found.
*/
public int indexOf(int elem)
{
for (int i = 0; i < size; ++i)
{
if (elements[i] == elem)
return i;
}
return -1;
}
/**
* Returns the index of the last occurrence of the specified integer in
* this list.
*
* @param elem
* The desired element.
*
* @return The index of the last occurrence of the specified integer in
* this list; returns -1 if the value is not found.
*/
public int lastIndexOf(int elem)
{
for (int i = size - 1; i >= 0; --i)
{
if (elements[i] == elem)
return i;
}
return -1;
}
/**
* Returns a copy of this IntArrayList instance.
*
* @return A clone of this ArrayList instance.
*/
public Object clone()
{
try
{
IntArrayList l = (IntArrayList)super.clone();
l.elements = new int[size];
System.arraycopy(elements, 0, l.elements, 0, size);
return l;
}
catch (CloneNotSupportedException e)
{
/* Should never happen since we are Cloneable. */
throw new InternalError();
}
}
/**
* Returns an array containing all of the elements in this list.
*
* @return An array containing all of the elements in this list.
*/
public int[] toArray()
{
int[] result = new int[size];
System.arraycopy(elements, 0, result, 0, size);
return result;
}
/**
* Check if the given index is in range.
* If not, throw an appropriate runtime exception.
*/
private void rangeCheck(int index)
{
if (index < 0 || index >= size)
throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
}
/**
* Returns the element at the specified position in this list.
*
* @param index
* Index of element to return.
*
* @return
* The element at the specified position in this list.
*
* @exception IndexOutOfBoundsException
* If index is out of range (index < 0 || index >= size()).
*/
public int get(int index)
{
rangeCheck(index);
return elements[index];
}
/**
* Replaces the element at the specified position in this list with
* the specified element.
*
* @param index
* Index of element to replace.
* @param element
* Element to be stored at the specified position.
*
* @return
* The element previously at the specified position.
*
* @exception IndexOutOfBoundsException
* If index is out of range (index < 0 || index >= size()).
*/
public int set(int index, int element)
{
rangeCheck(index);
int oldValue = elements[index];
elements[index] = element;
return oldValue;
}
/**
* Appends the specified element to the end of this list.
*
* @param element
* Element to be appended to this list.
*/
public void add(int element)
{
ensureCapacity(size + 1);
elements[size++] = element;
}
/**
* Inserts the specified element at the specified position in this
* list.
* Shifts the element currently at that position (if any) and any subsequent
* elements to the right (adds one to their indices).
*
* @param index
* Index at which the specified element is to be inserted.
* @param element
* Element to be inserted.
*
* @exception IndexOutOfBoundsException
* If index is out of range (index < 0 || index > size()).
*/
public void add(int index, int element)
{
if (index < 0 || index > size)
throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
ensureCapacity(size + 1);
System.arraycopy(elements, index, elements, index + 1, size - index);
elements[index] = element;
++size;
}
/**
* Removes the element at the specified position in this list.
* Shifts any subsequent elements to the left (subtracts one from their
* indices).
*
* @param index
* The index of the element to removed.
*
* @return
* The element that was removed from the list.
*
* @exception IndexOutOfBoundsException
* If index is out of range (index < 0 || index >= size()).
*/
public int remove(int index)
{
rangeCheck(index);
int oldValue = elements[index];
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elements, index + 1, elements, index, numMoved);
--size;
return oldValue;
}
/**
* Removes all of the elements from this list.
* The list will be empty after this call returns.
*/
public void clear()
{
size = 0;
}
/**
* Appends all of the elements in the specified array to the end of this
* list.
*
* @param ai
* The elements to be added to this list.
*/
public void addAll(int[] ai)
{
int numNew = ai.length;
ensureCapacity(size + numNew);
System.arraycopy(ai, 0, elements, size, numNew);
}
/**
* Inserts all of the elements in the specified array into this list,
* starting at the specified position.
* Shifts the element currently at that position (if any) and any subsequent
* elements to the right (increases their indices).
* The new elements will appear in the list in the order that they exist in
* the array argument.
*
* @param index
* Index at which to insert first element from the specified array.
* @param ai
* Elements to be inserted into this list.
*
* @exception IndexOutOfBoundsException
* If index is out of range (index < 0 || index > size()).
*/
public void addAll(int index, int[] ai)
{
if (index < 0 || index > size)
throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
int numNew = ai.length;
ensureCapacity(size + numNew);
int numMoved = size - index;
if (numMoved > 0)
System.arraycopy(elements, index, elements, index + numNew, numMoved);
System.arraycopy(ai, 0, elements, index, numNew);
size += numNew;
}
/**
* Returns true if this list contains all of the elements in the
* specified list.
* * This implementation iterates over the specified array, checking each * element in turn to see if it"s contained in this list. * If all elements are so contained true is returned, otherwise * false. * * @param ai * Array to be checked for containment in this list. * * @return * true if this list contains all of the elements in the * specified array. * * @see #contains */ public boolean containsAll(int[] ai) { for (int i = 0; i < ai.length; ++i) { if (!contains(ai[i])) return false; } return true; } /** * Removes from this list all of its elements that are contained in the * specified array. * <p> * This implementation iterates over this list, checking each element in * turn to see if it"s contained in the specified array. * If it"s so contained, it"s removed from this list. * * @param ai * Elements to be removed from this list. * * @return * true if this list changed as a result of the call. * * @see #remove * @see #contains */ public boolean removeAll(int[] ai) { IntArrayList l = new IntArrayList(ai); boolean modified = false; for (int i = 0; i < size; ++i) { while (i < size && l.contains(elements[i])) { remove(i); modified = true; } } return modified; } /** * Retains only the elements in this list that are contained in the * specified array. * In other words, removes from this list all of its elements that are not * contained in the specified array. * <p> * This implementation iterates over this list, checking each element in * turn to see if it"s contained in the specified array. * If it"s not so contained, it"s removed from this list. * * @param ai * Elements to be retained in this list. * * @return * true if this list changed as a result of the call. * * @see #remove * @see #contains */ public boolean retainAll(int[] ai) { IntArrayList l = new IntArrayList(ai); boolean modified = false; for (int i = 0; i < size; ++i) { while (i < size && !l.contains(elements[i])) { remove(i); modified = true; } } return modified; } /** * Compares the specified object with this list for equality. * Returns true if and only if the specified object is also an * IntArrayList, both lists have the same size, and all corresponding pairs * of elements in the two lists are equal. * * @param o the object to be compared for equality with this list. * * @return true if the specified object is equal to this list. */ public boolean equals(Object o) { if (o == this) return true; if (!(o instanceof IntArrayList)) return false; return Arrays.equals(toArray(), ((IntArrayList)o).toArray()); } /** * Returns the hash code value for this list. * * @return The hash code value for this list. */ public int hashCode() { int hashCode = 1; for (int i = 0; i < size; ++i) hashCode = 31 * hashCode + elements[i]; return hashCode; } /** * Returns a string representation of this list. * The string representation consists of a list of the elements, enclosed * in square brackets ("[]"). * Adjacent elements are separated by the characters ", " (comma * and space). * Elements are converted to strings as by String.valueOf(int). * * @return * A string representation of this collection. */ public String toString() { StringBuffer buf = new StringBuffer(); buf.append("["); for (int i = 0; i < size; ++i) { if (i > 0) buf.append(", "); buf.append(elements[i]); } buf.append("]"); return buf.toString(); } } </source>
Int Vector
<source lang="java">
/* Copyright (C) 2003 Vladimir Roubtsov. All rights reserved.
* * This program and the accompanying materials are made available under * the terms of the Common Public License v1.0 which accompanies this distribution, * and is available at http://www.eclipse.org/legal/cpl-v10.html * * $Id: IntVector.java,v 1.1.1.1 2004/05/09 16:57:53 vlad_r Exp $ */
// ---------------------------------------------------------------------------- /**
* @author Vlad Roubtsov, (C) 2001 */
public final class IntVector implements Cloneable {
// public: ................................................................
public IntVector ()
{
this (5);
}
public IntVector (final int initCapacity)
{
m_values = new int [initCapacity];
}
// ACCESSORS:
public int get (final int index)
{
if (index > m_size - 1)
throw new IndexOutOfBoundsException ("get[" + index + "] on vector of size " + m_size);
return m_values [index];
}
public int [] values ()
{
if (m_size == 0)
return new int[0];
else
{
final int size = m_size;
final int [] result = new int [size];
if (size < COPY_THRESHOLD)
{
for (int i = 0; i < size; ++ i) result [i] = m_values [i];
}
else
{
System.arraycopy (m_values, 0, result, 0, size);
}
return result;
}
}
public int size ()
{
return m_size;
}
// Cloneable:
/**
* Performs deep copy.
*/
public Object clone ()
{
try
{
final IntVector _clone = (IntVector) super.clone ();
// deep clone:
if (m_size < COPY_THRESHOLD)
{
_clone.m_values = new int [m_values.length];
final int [] _clone_values = _clone.m_values;
for (int i = 0; i < m_size; ++ i) _clone_values [i] = m_values [i];
}
else
{
_clone.m_values = (int []) m_values.clone ();
}
return _clone;
}
catch (CloneNotSupportedException e)
{
throw new InternalError (e.toString ());
}
}
public String toString ()
{
final StringBuffer s = new StringBuffer (super.toString() + ", size " + m_size + ": ");
for (int i = 0; i < m_size; ++ i)
{
if (i > 0) s.append (", ");
s.append (m_values [i]);
}
return s.toString ();
}
// MUTATORS:
public int set (final int index, final int value)
{
if (index > m_size - 1)
throw new IndexOutOfBoundsException ("get[" + index + "] on vector of size " + m_size);
final int current_value = m_values [index];
m_values [index] = value;
return current_value;
}
public void add (final int value)
{
final int capacity = m_values.length;
if (capacity == m_size)
{
final int [] values = new int [1 + (capacity << 1)];
if (capacity < COPY_THRESHOLD)
{
for (int i = 0; i < capacity; ++ i) values [i] = m_values [i];
}
else
{
System.arraycopy (m_values, 0, values, 0, capacity);
}
m_values = values;
}
m_values [m_size ++] = value;
}
// protected: .............................................................
// package: ...............................................................
// private: ...............................................................
private int [] m_values; // never null
private int m_size;
private static final int COPY_THRESHOLD = 10;
} // end of class // ----------------------------------------------------------------------------
</source>
Int Vector (from java-objects-database)
<source lang="java">
/* Copyright (C) 2007 Mobixess Inc. http://www.java-objects-database.ru This file is part of the JODB (Java Objects Database) open source project. JODB is free software; you can redistribute it and/or modify it under the terms of version 2 of the GNU General Public License as published by the Free Software Foundation. JODB is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with this program; if not, write to the Free Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
- /
import java.io.Serializable; public class IntVector implements Serializable {
/**
*
*/
private static final long serialVersionUID = 1L;
public final static int DEFAULT_INCREMENT = 256;
private int _increment;
private int _data[];
private int _size = 0;
public IntVector() {
_increment = DEFAULT_INCREMENT;
_data = new int[_increment];
}
public IntVector(int increment) {
_increment = increment;
_data = new int[increment];
}
public IntVector(int initialSize, int increment) {
_increment = increment;
_data = new int[initialSize];
_size = initialSize;
}
public IntVector(int[] data) {
_data = new int[data.length];
_size = data.length;
_increment = DEFAULT_INCREMENT;
System.arraycopy(data, 0, _data, 0, _size);
}
/**
* Get the length of the list.
*
* @return length of the list
*/
public final int size() {
return _size;
}
/**
* Get the length of the list.
*
* @return length of the list
*/
public final void setSize(int sz) {
_size = sz;
}
/**
* Append a int onto the vector.
*
* @param value
* Int to add to the list
*/
public final void addElement(int value) {
ensureCapacity(_size+1);
_data[_size] = value;
_size++;
}
private void ensureCapacity(int size){
if (size >= _data.length) {
int newData[] = new int[size + _increment];
System.arraycopy(_data, 0, newData, 0, _data.length);
_data = newData;
}
}
/**
* Append several int values onto the vector.
*
* @param value
* Int to add to the list
*/
public final void addElements(int value, int numberOfElements) {
ensureCapacity(_size+numberOfElements);
for (int i = 0; i < numberOfElements; i++) {
_data[_size] = value;
_size++;
}
}
/**
* Inserts the specified node in this vector at the specified index.
*
* @param value
* Int to insert
* @param at
* Index of where to insert
*/
public final void insertElementAt(int value, int at) {
ensureCapacity(_size+1);
if (at <= (_size - 1)) {
System.arraycopy(_data, at, _data, at + 1, _size - at);
}
_data[at] = value;
_size++;
}
public final void removeAllElements() {
for (int i = 0; i < _size; i++) {
_data[i] = java.lang.Integer.MIN_VALUE;
}
_size = 0;
}
/**
* Removes the first occurrence of the argument from this vector. If the
* object is found in this vector, each component in the vector with an
* index greater or equal to the object"s index is shifted downward to have
* an index one smaller than the value it had previously.
*
* @param s
* Int to remove from array
*
* @return True if the int was removed, false if it was not found
*/
public final boolean removeElement(int s) {
for (int i = 0; i < _size; i++) {
if (_data[i] == s) {
if ((i + 1) < _size)
System.arraycopy(_data, i + 1, _data, i - 1, _size - i);
else
_data[i] = java.lang.Integer.MIN_VALUE;
_size--;
return true;
}
}
return false;
}
/**
* Deletes the component at the specified index. Each component in this
* vector with an index greater or equal to the specified index is shifted
* downward to have an index one smaller than the value it had previously.
*
* @param i
* index of where to remove and int
*/
public final void removeElementAt(int i) {
if (i > _size)
System.arraycopy(_data, i + 1, _data, i, _size);
else
_data[i] = java.lang.Integer.MIN_VALUE;
_size--;
}
/**
* 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.
*
* @param node
* object to set
* @param index
* Index of where to set the object
*/
public final void setElementAt(int value, int index) {
_data[index] = value;
}
/**
* Get the nth element.
*
* @param i
* index of object to get
*
* @return object at given index
*/
public final int elementAt(int i) {
return _data[i];
}
/**
* Tell if the table contains the given node.
*
* @param s
* object to look for
*
* @return true if the object is in the list
*/
public final boolean contains(int s) {
for (int i = 0; i < _size; i++) {
if (_data[i] == s) return true;
}
return false;
}
/**
* Searches for the first occurence of the given argument, beginning the
* search at index, and testing for equality using the equals method.
*
* @param elem
* object to look for
* @param index
* Index of where to begin search
* @return 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.
*/
public final int indexOf(int elem, int index) {
for (int i = index; i < _size; i++) {
if (_data[i] == elem) return i;
}
return java.lang.Integer.MIN_VALUE;
}
/**
* Searches for the first occurence of the given argument, beginning the
* search at index, and testing for equality using the equals method.
*
* @param elem
* object to look for
* @return 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.
*/
public final int indexOf(int elem) {
for (int i = 0; i < _size; i++) {
if (_data[i] == elem) return i;
}
return java.lang.Integer.MIN_VALUE;
}
/**
* Searches for the first occurence of the given argument, beginning the
* search at index, and testing for equality using the equals method.
*
* @param elem
* Object to look for
* @return 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.
*/
public final int lastIndexOf(int elem) {
for (int i = (_size - 1); i >= 0; i--) {
if (_data[i] == elem) return i;
}
return java.lang.Integer.MIN_VALUE;
}
public int[] getDataAsArray() {
return _data;
}
public final int binarySearch(int key){
int low = 0;
int high = _size;
while (low <= high) {
int mid = (low + high) >> 1;
int midVal = _data[mid];
if (midVal < key)
low = mid + 1;
else if (midVal > key)
high = mid - 1;
else
return mid; // key found
}
return -(low + 1); // key not found.
}
}
</source>
Lazy List creation based on ArrayList
<source lang="java">
// // $Id: LazyList.java,v 1.16 2004/10/23 09:03:22 gregwilkins Exp $ // Copyright 1999-2004 Mort Bay Consulting Pty. Ltd. // ------------------------------------------------------------------------ // Licensed under the Apache License, Version 2.0 (the "License"); // you may not use this file except in compliance with the License. // You may obtain a copy of the License at // http://www.apache.org/licenses/LICENSE-2.0 // Unless required by applicable law or agreed to in writing, software // distributed under the License is distributed on an "AS IS" BASIS, // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. // See the License for the specific language governing permissions and // limitations under the License. // import java.io.Serializable; import java.util.ArrayList; import java.util.Collection; import java.util.Collections; import java.util.Iterator; import java.util.List; import java.util.ListIterator; /* ------------------------------------------------------------ */ /** Lazy List creation.
* A List helper class that attempts to avoid unneccessary List * creation. If a method needs to create a List to return, but it is * expected that this will either be empty or frequently contain a * single item, then using LazyList will avoid additional object * creations by using Collections.EMPTY_LIST or * Collections.singletonList where possible. ** <p>
Usage
*
* Object lazylist =null;
* while(loopCondition)
* {
* Object item = getItem();
* if (item.isToBeAdded())
* lazylist = LazyList.add(lazylist,item);
* }
* return LazyList.getList(lazylist);
*
* * An ArrayList of default size is used as the initial LazyList. * * @see java.util.List * @version $Revision: 1.16 $ * @author Greg Wilkins (gregw) */
public class LazyList {
private static final String[] __EMTPY_STRING_ARRAY = new String[0];
/* ------------------------------------------------------------ */
private LazyList()
{}
/* ------------------------------------------------------------ */
/** Add an item to a LazyList
* @param list The list to add to or null if none yet created.
* @param item The item to add.
* @return The lazylist created or added to.
*/
public static Object add(Object list, Object item)
{
if (list==null)
{
if (item instanceof List || item==null)
{
List l = new ArrayList();
l.add(item);
return l;
}
return item;
}
if (list instanceof List)
{
((List)list).add(item);
return list;
}
List l=new ArrayList();
l.add(list);
l.add(item);
return l;
}
/* ------------------------------------------------------------ */
/** Add an item to a LazyList
* @param list The list to add to or null if none yet created.
* @param index The index to add the item at.
* @param item The item to add.
* @return The lazylist created or added to.
*/
public static Object add(Object list, int index, Object item)
{
if (list==null)
{
if (index>0 || item instanceof List || item==null)
{
List l = new ArrayList();
l.add(index,item);
return l;
}
return item;
}
if (list instanceof List)
{
((List)list).add(index,item);
return list;
}
List l=new ArrayList();
l.add(list);
l.add(index,item);
return l;
}
/* ------------------------------------------------------------ */
/** Add the contents of a Collection to a LazyList
* @param list The list to add to or null if none yet created.
* @param collection The Collection whose contents should be added.
* @return The lazylist created or added to.
* @deprecated Use addCollection
*/
protected Object add(Object list, Collection collection)
{
Iterator i=collection.iterator();
while(i.hasNext())
list=LazyList.add(list,i.next());
return list;
}
/* ------------------------------------------------------------ */
/** Add the contents of a Collection to a LazyList
* @param list The list to add to or null if none yet created.
* @param collection The Collection whose contents should be added.
* @return The lazylist created or added to.
*/
public static Object addCollection(Object list, Collection collection)
{
Iterator i=collection.iterator();
while(i.hasNext())
list=LazyList.add(list,i.next());
return list;
}
/* ------------------------------------------------------------ */
public static Object ensureSize(Object list, int initialSize)
{
if (list==null)
return new ArrayList(initialSize);
if (list instanceof ArrayList)
return list;
List l= new ArrayList(initialSize);
l.add(list);
return list;
}
/* ------------------------------------------------------------ */
public static Object remove(Object list, Object o)
{
if (list==null)
return null;
if (list instanceof List)
{
List l = (List)list;
l.remove(o);
if (l.size()==0)
return null;
return list;
}
if (list.equals(o))
return null;
return list;
}
/* ------------------------------------------------------------ */
public static Object remove(Object list, int i)
{
if (list==null)
return null;
if (list instanceof List)
{
List l = (List)list;
l.remove(i);
if (l.size()==0)
return null;
return list;
}
if (i==0)
return null;
return list;
}
/* ------------------------------------------------------------ */
/** Get the real List from a LazyList.
*
* @param list A LazyList returned from LazyList.add(Object)
* @return The List of added items, which may be an EMPTY_LIST
* or a SingletonList.
*/
public static List getList(Object list)
{
return getList(list,false);
}
/* ------------------------------------------------------------ */
/** Get the real List from a LazyList.
*
* @param list A LazyList returned from LazyList.add(Object) or null
* @param nullForEmpty If true, null is returned instead of an
* empty list.
* @return The List of added items, which may be null, an EMPTY_LIST
* or a SingletonList.
*/
public static List getList(Object list, boolean nullForEmpty)
{
if (list==null)
return nullForEmpty?null:Collections.EMPTY_LIST;
if (list instanceof List)
return (List)list;
List l = new ArrayList(1);
l.add(list);
return l;
}
/* ------------------------------------------------------------ */
public static String[] toStringArray(Object list)
{
if (list==null)
return __EMTPY_STRING_ARRAY;
if (list instanceof List)
{
List l = (List)list;
String[] a = new String[l.size()];
for (int i=l.size();i-->0;)
{
Object o=l.get(i);
if (o!=null)
a[i]=o.toString();
}
return a;
}
return new String[] {list.toString()};
}
/* ------------------------------------------------------------ */
/** The size of a lazy List
* @param list A LazyList returned from LazyList.add(Object) or null
* @return the size of the list.
*/
public static int size(Object list)
{
if (list==null)
return 0;
if (list instanceof List)
return ((List)list).size();
return 1;
}
/* ------------------------------------------------------------ */
/** Get item from the list
* @param list A LazyList returned from LazyList.add(Object) or null
* @param i int index
* @return the item from the list.
*/
public static Object get(Object list, int i)
{
if (list==null)
throw new IndexOutOfBoundsException();
if (list instanceof List)
return ((List)list).get(i);
if (i==0)
return list;
throw new IndexOutOfBoundsException();
}
/* ------------------------------------------------------------ */
public static boolean contains(Object list,Object item)
{
if (list==null)
return false;
if (list instanceof List)
return ((List)list).contains(item);
return list.equals(item);
}
/* ------------------------------------------------------------ */
public static Object clone(Object list)
{
if (list==null)
return null;
if (list instanceof List)
return new ArrayList((List)list);
return list;
}
/* ------------------------------------------------------------ */
public static String toString(Object list)
{
if (list==null)
return "[]";
if (list instanceof List)
return ((List)list).toString();
return "["+list+"]";
}
/* ------------------------------------------------------------ */
public static Iterator iterator(Object list)
{
if (list==null)
return Collections.EMPTY_LIST.iterator();
if (list instanceof List)
return ((List)list).iterator();
return getList(list).iterator();
}
/* ------------------------------------------------------------ */
public static ListIterator listIterator(Object list)
{
if (list==null)
return Collections.EMPTY_LIST.listIterator();
if (list instanceof List)
return ((List)list).listIterator();
return getList(list).listIterator();
}
}
</source>
Long Vector
<source lang="java">
/* Copyright (C) 2007 Mobixess Inc. http://www.java-objects-database.ru This file is part of the JODB (Java Objects Database) open source project. JODB is free software; you can redistribute it and/or modify it under the terms of version 2 of the GNU General Public License as published by the Free Software Foundation. JODB is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with this program; if not, write to the Free Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
- /
import java.io.Serializable; public class LongVector implements Serializable {
/**
*
*/
private static final long serialVersionUID = 1L;
public final static int DEFAULT_INCREMENT = 256;
private int _increment;
private long _data[];
private int _size = 0;
public LongVector() {
_increment = DEFAULT_INCREMENT;
_data = new long[_increment];
}
public LongVector(int increment) {
_increment = increment;
_data = new long[increment];
}
public LongVector(int initialSize, int increment) {
_increment = increment;
_data = new long[initialSize];
_size = initialSize;
}
public LongVector(long[] data) {
_data = new long[data.length];
_size = data.length;
_increment = DEFAULT_INCREMENT;
System.arraycopy(data, 0, _data, 0, _size);
}
/**
* Get the length of the list.
*
* @return length of the list
*/
public final int size() {
return _size;
}
/**
* Get the length of the list.
*
* @return length of the list
*/
public final void setSize(int sz) {
_size = sz;
}
/**
* Append a int onto the vector.
*
* @param value
* Int to add to the list
*/
public final void addElement(long value) {
ensureCapacity(_size+1);
_data[_size] = value;
_size++;
}
private void ensureCapacity(int size){
if (size >= _data.length) {
long newData[] = new long[size + _increment];
System.arraycopy(_data, 0, newData, 0, _data.length);
_data = newData;
}
}
/**
* Append several int values onto the vector.
*
* @param value
* Int to add to the list
*/
public final void addElements(long value, int numberOfElements) {
ensureCapacity(_size+numberOfElements);
for (int i = 0; i < numberOfElements; i++) {
_data[_size] = value;
_size++;
}
}
/**
* Inserts the specified node in this vector at the specified index.
*
* @param value
* Int to insert
* @param at
* Index of where to insert
*/
public final void insertElementAt(long value, int at) {
ensureCapacity(_size+1);
if (at <= (_size - 1)) {
System.arraycopy(_data, at, _data, at + 1, _size - at);
}
_data[at] = value;
_size++;
}
public final void removeAllElements() {
for (int i = 0; i < _size; i++) {
_data[i] = java.lang.Integer.MIN_VALUE;
}
_size = 0;
}
/**
* Removes the first occurrence of the argument from this vector. If the
* object is found in this vector, each component in the vector with an
* index greater or equal to the object"s index is shifted downward to have
* an index one smaller than the value it had previously.
*
*
* @return True if the int was removed, false if it was not found
*/
public final boolean removeElement(long s) {
for (int i = 0; i < _size; i++) {
if (_data[i] == s) {
if ((i + 1) < _size)
System.arraycopy(_data, i + 1, _data, i - 1, _size - i);
else
_data[i] = java.lang.Integer.MIN_VALUE;
_size--;
return true;
}
}
return false;
}
/**
* Deletes the component at the specified index. Each component in this
* vector with an index greater or equal to the specified index is shifted
* downward to have an index one smaller than the value it had previously.
*
* @param i
* index of where to remove
*/
public final void removeElementAt(int i) {
if (i > _size)
System.arraycopy(_data, i + 1, _data, i, _size);
else
_data[i] = java.lang.Integer.MIN_VALUE;
_size--;
}
/**
* 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.
*
* @param node
* object to set
* @param index
* Index of where to set the object
*/
public final void setElementAt(long value, int index) {
_data[index] = value;
}
/**
* Get the nth element.
*
* @param i
* index of object to get
*
* @return object at given index
*/
public final long elementAt(int i) {
return _data[i];
}
/**
* Tell if the table contains the given node.
*
* @param s
* object to look for
*
* @return true if the object is in the list
*/
public final boolean contains(long s) {
for (int i = 0; i < _size; i++) {
if (_data[i] == s) return true;
}
return false;
}
/**
* Searches for the first occurence of the given argument, beginning the
* search at index, and testing for equality using the equals method.
*
* @param elem
* object to look for
* @param index
* Index of where to begin search
* @return 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.
*/
public final int indexOf(long elem, int index) {
for (int i = index; i < _size; i++) {
if (_data[i] == elem) return i;
}
return java.lang.Integer.MIN_VALUE;
}
/**
* Searches for the first occurence of the given argument, beginning the
* search at index, and testing for equality using the equals method.
*
* @param elem
* object to look for
* @return 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.
*/
public final int indexOf(long elem) {
for (int i = 0; i < _size; i++) {
if (_data[i] == elem) return i;
}
return java.lang.Integer.MIN_VALUE;
}
/**
* Searches for the first occurence of the given argument, beginning the
* search at index, and testing for equality using the equals method.
*
* @param elem
* Object to look for
* @return 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.
*/
public final int lastIndexOf(long elem) {
for (int i = (_size - 1); i >= 0; i--) {
if (_data[i] == elem) return i;
}
return java.lang.Integer.MIN_VALUE;
}
public long[] getDataAsArray() {
if(_data.length == _size){
return _data;
}
long[] result = new long[_size];
System.arraycopy(_data, 0, result, 0, _size);
return result;
}
public final int binarySearch(long key){
int low = 0;
int high = _size;
while (low <= high) {
int mid = (low + high) >> 1;
long midVal = _data[mid];
if (midVal < key)
low = mid + 1;
else if (midVal > key)
high = mid - 1;
else
return mid; // key found
}
return -(low + 1); // key not found.
}
}
</source>
Simple object pool
<source lang="java">
/*
* Licensed to the Apache Software Foundation (ASF) under one or more * contributor license agreements. See the NOTICE file distributed with * this work for additional information regarding copyright ownership. * The ASF licenses this file to You under the Apache License, Version 2.0 * (the "License"); you may not use this file except in compliance with * the License. You may obtain a copy of the License at * * http://www.apache.org/licenses/LICENSE-2.0 * * Unless required by applicable law or agreed to in writing, software * distributed under the License is distributed on an "AS IS" BASIS, * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. * See the License for the specific language governing permissions and * limitations under the License. */
/**
* Simple object pool. Based on ThreadPool and few other classes * * The pool will ignore overflow and return null if empty. * * @author Gal Shachor * @author Costin Manolache */
public final class SimplePool {
/*
* Where the threads are held.
*/
private Object pool[];
private int max;
private int last;
private int current = -1;
private Object lock;
public static final int DEFAULT_SIZE = 32;
static final int debug = 0;
public SimplePool() {
this(DEFAULT_SIZE, DEFAULT_SIZE);
}
public SimplePool(int size) {
this(size, size);
}
public SimplePool(int size, int max) {
this.max = max;
pool = new Object[size];
this.last = size - 1;
lock = new Object();
}
public void set(Object o) {
put(o);
}
/**
* Add the object to the pool, silent nothing if the pool is full
*/
public void put(Object o) {
synchronized (lock) {
if (current < last) {
current++;
pool[current] = o;
} else if (current < max) {
// realocate
int newSize = pool.length * 2;
if (newSize > max)
newSize = max + 1;
Object tmp[] = new Object[newSize];
last = newSize - 1;
System.arraycopy(pool, 0, tmp, 0, pool.length);
pool = tmp;
current++;
pool[current] = o;
}
}
}
/**
* Get an object from the pool, null if the pool is empty.
*/
public Object get() {
Object item = null;
synchronized (lock) {
if (current >= 0) {
item = pool[current];
pool[current] = null;
current -= 1;
}
}
return item;
}
/**
* Return the size of the pool
*/
public int getMax() {
return max;
}
/**
* Number of object in the pool
*/
public int getCount() {
return current + 1;
}
public void shutdown() {
}
}
</source>
Your own auto-growth Array
<source lang="java">
/*
* * The Apache Software License, Version 1.1 * * Copyright (c) 1999-2003 The Apache Software Foundation. All rights * reserved. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions * are met: * * 1. Redistributions of source code must retain the above copyright * notice, this list of conditions and the following disclaimer. * * 2. Redistributions in binary form must reproduce the above copyright * notice, this list of conditions and the following disclaimer in * the documentation and/or other materials provided with the * distribution. * * 3. The end-user documentation included with the redistribution, if * any, must include the following acknowlegement: * "This product includes software developed by the * Apache Software Foundation (http://www.apache.org/)." * Alternately, this acknowlegement may appear in the software itself, * if and wherever such third-party acknowlegements normally appear. * * 4. The names "The Jakarta Project", "Jakarta Element Construction Set", * "Jakarta ECS" , and "Apache Software Foundation" must not be used * to endorse or promote products derived * from this software without prior written permission. For written * permission, please contact apache@apache.org. * * 5. Products derived from this software may not be called "Apache", * "Jakarta Element Construction Set" nor "Jakarta ECS" nor may "Apache" * appear in their names without prior written permission of the Apache Group. * * THIS SOFTWARE IS PROVIDED ``AS IS"" AND ANY EXPRESSED OR IMPLIED * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE * DISCLAIMED. IN NO EVENT SHALL THE APACHE SOFTWARE FOUNDATION OR * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF * SUCH DAMAGE. * */
public class Array implements java.util.Enumeration,java.io.Serializable {
private int current = 0;
private int size = 10;
private int grow = 2;
private int place = 0;
private Object[] elements = null;
private Object[] tmpElements = null;
public Array()
{
init();
}
public Array(int size)
{
setSize(size);
init();
}
public Array(int size,int grow)
{
setSize(size);
setGrow(grow);
init();
}
private void init()
{
elements = new Object[size];
}
public Object nextElement() throws java.util.NoSuchElementException
{
if ( elements[place] != null && place != current)
{
place++;
return elements[place - 1];
}
else
{
place = 0;
throw new java.util.NoSuchElementException();
}
}
public boolean hasMoreElements()
{
if( place < elements.length && current != place )
return true;
return false;
}
public void setSize(int size)
{
this.size = size;
}
public int getCurrentSize()
{
return current;
}
public void rehash()
{
tmpElements = new Object[size];
int count = 0;
for ( int x = 0; x < elements.length; x++ )
{
if( elements[x] != null )
{
tmpElements[count] = elements[x];
count++;
}
}
elements = (Object[])tmpElements.clone();
tmpElements = null;
current = count;
}
public void setGrow(int grow)
{
this.grow = grow;
}
public void grow()
{
size = size+=(size/grow);
rehash();
}
public void add(Object o)
{
if( current == elements.length )
grow();
try
{
elements[current] = o;
current++;
}
catch(java.lang.ArrayStoreException ase)
{
}
}
public void add(int location,Object o)
{
try
{
elements[location] = o;
}
catch(java.lang.ArrayStoreException ase)
{
}
}
public void remove(int location)
{
elements[location] = null;
}
public int location(Object o) throws NoSuchObjectException
{
int loc = -1;
for ( int x = 0; x < elements.length; x++ )
{
if((elements[x] != null && elements[x] == o )||
(elements[x] != null && elements[x].equals(o)))
{
loc = x;
break;
}
}
if( loc == -1 )
throw new NoSuchObjectException();
return(loc);
}
public Object get(int location)
{
return elements[location];
}
public java.util.Enumeration elements()
{
return this;
}
} class NoSuchObjectException extends Exception {
public NoSuchObjectException()
{
super("No such object found.");
}
}
</source>
