Helfer ListArray

Jan Burse, erstellt 21. Nov 2018
package matula.util.data;
/**
* <p>This class provides a list array. The advantage over the usual Java
* class ArrayList is no mod count, no bounds check and more important
* automatic shrinking. The list array is implemented by an object array
* plus a size field that indicates the size which might differ from the
* length of the object array:
* </p>
* <pre>
* +----------+-----------------+------------+
* | table[0] | ... | table[n-1] |
* +----------+-----------------+------------+
* < ---------- table.length = n ----------- >
* < ----------- size --------- >
* </pre>
* <p>Each operation automatically resizes. Its also possible to access
* the object array and size field directly and perform some bulk
* operation possibly update the size field and then call resize. Each
* operation is not synchronized. Application code needs to synchronize on
* its own if necessary and might execute multiple operations insided its
* synchronized block.
* </p>
* Warranty & Liability
* To the extent permitted by applicable law and unless explicitly
* otherwise agreed upon, XLOG Technologies GmbH makes no warranties
* regarding the provided information. XLOG Technologies GmbH assumes
* no liability that any problems might be solved with the information
* provided by XLOG Technologies GmbH.
* <p/>
* Rights & License
* All industrial property rights regarding the information - copyright
* and patent rights in particular - are the sole property of XLOG
* Technologies GmbH. If the company was not the originator of some
* excerpts, XLOG Technologies GmbH has at least obtained the right to
* reproduce, change and translate the information.
* <p/>
* Reproduction is restricted to the whole unaltered document. Reproduction
* of the information is only allowed for non-commercial uses. Selling,
* giving away or letting of the execution of the library is prohibited.
* The library can be distributed as part of your applications and libraries
* for execution provided this comment remains unchanged.
* <p/>
* Restrictions
* Only to be distributed with programs that add significant and primary
* functionality to the library. Not to be distributed with additional
* software intended to replace any components of the library.
* <p/>
* Trademarks
* Jekejeke is a registered trademark of XLOG Technologies GmbH.
*/
public class ListArray<E> extends AbstractList<E> {
public static final int MIN_SIZE = 2;
public Object[] table;
/**
* <p>Create a list array.</p>
*/
public ListArray() {
reinitialize(0);
}
/**
* <p>Create a list array.</p>
*
* @param capa The ahead capacity.
*/
public ListArray(int capa) {
reinitialize(capa);
}
/**
* <p>Retrieve the stored key.</p>
*
* @param key The search key, can be null.
* @return The stored key or null.
*/
public E getKey(E key) {
int i = indexOf(key);
return (i >= 0 ? get(i) : null);
}
/**
* <p>Add key to the set at end.</p>
* <p>Assumption is that key is not yet present.</p>
*
* @param key The key, can be null.
*/
public void add(E key) {
add(size, key);
}
/**
* <p>Add key to the set at beginning.</p>
* <p>Assumption is that key is not yet present.</p>
*
* @param key The key, can be null.
*/
public void addFirst(E key) {
add(0, key);
}
/**
* <p>Remove the key from the set.</p>
*
* @param key The key, can be null.
*/
public void remove(E key) {
int k = indexOf(key);
if (k >= 0)
remove(k);
}
/***************************************************************/
/* Getter/Setter */
/***************************************************************/
/**
* <p>Retrieve an element.</p>
*
* @param i The index.
* @return The element.
*/
public E get(int i) {
return (E) table[i];
}
/**
* <p>Set an element.</p>
*
* @param i The index.
* @param e The element.
*/
public void set(int i, E e) {
table[i] = e;
}
/***************************************************************/
/* Modify Family */
/***************************************************************/
/**
* <p>Add an element at a position.</p>
*
* @param i The index.
* @param e The element.
*/
public void add(int i, E e) {
if (size >= table.length)
resize(table.length * 2);
int k = size - i;
if (k != 0)
System.arraycopy(table, i, table, i + 1, k);
table[i] = e;
size++;
}
/**
* <p>Remove an element at a position.</p>
*
* @param i The index.
*/
public void removeEntry(int i) {
int k = size - i - 1;
if (k > 0)
System.arraycopy(table, i + 1, table, i, k);
table[--size] = null;
}
/**
* <p>Remove an element at a position.</p>
*
* @param i The index.
*/
public void remove(int i) {
removeEntry(i);
resize();
}
/**
* <p>Clear the table.</p>
*/
public void clear() {
if (size == 0)
return;
if (table.length != MIN_SIZE) {
table = new Object[MIN_SIZE];
} else {
int n = Math.min(size, MIN_SIZE);
for (int i = 0; i < n; i++)
table[i] = null;
}
size = 0;
}
/***************************************************************/
/* Find Family */
/***************************************************************/
/**
* <p>Returns the first index of the element occurence.</p>
*
* @param o The element.
* @return The index, or -1.
*/
public int indexOf(Object o) {
for (int i = 0; i < size; i++)
if (o != null ? o.equals(table[i]) : null == table[i])
return i;
return -1;
}
/**
* <p>Checks whether the object is contained in the element list.</p>
*
* @param o The element.
* @return True if the element is contained in the list, otherwise false.
*/
public boolean contains(Object o) {
return indexOf(o) >= 0;
}
/**
* <p>Copy elements to an array.</p>
*
* @param target The array.
* @param pos The start index.
*/
public void toArray(E[] target, int pos) {
if (size > 0)
System.arraycopy(table, 0, target, pos, size);
}
/***************************************************************/
/* Resize Helper */
/***************************************************************/
/**
* <p>Resize the list array.</p>
*/
public void resize() {
int len = table.length;
while (size < len / 4 && len / 2 > MIN_SIZE)
len = len / 2;
if (len != table.length)
resize(len);
}
/**
* <p>Resize the list array.</p>
*
* @param s The new size.
*/
private void resize(int s) {
Object[] newtable = new Object[s];
int k = Math.min(s, table.length);
System.arraycopy(table, 0, newtable, 0, k);
table = newtable;
}
/***************************************************************/
/* Object Protocol */
/***************************************************************/
/**
* <p>Returns a string representation of this list array.</p>
*
* @return A string representation of this list array.
*/
public String toString() {
if (size == 0)
return "[]";
StringBuilder buf = new StringBuilder();
buf.append("[");
buf.append(get(0));
for (int i = 1; i < size; i++) {
buf.append(",");
buf.append(get(i));
}
buf.append("]");
return buf.toString();
}
/**
* <p>Create a shallow copy.</p>
*
* @return The shallow copy.
*/
public Object clone() {
ListArray<E> res = (ListArray<E>) super.clone();
if (size() > 0) {
System.arraycopy(table, 0, res.table, 0, size());
res.size = size();
}
return res;
}
/**
* Reset to initial default state.
*
* @param capa The ahead capacity.
*/
void reinitialize(int capa) {
super.reinitialize(capa);
int len = MIN_SIZE;
while (capa > len)
len = len * 2;
table = new Object[len];
}
}

Kommentare