com.samskivert.util
Class ListUtil

java.lang.Object
  com.samskivert.util.ListUtil

public class ListUtil
extends Object

List util is for the times when you just can't bear the overhead of an ArrayList object to manage your list of objects. It provides a suite of list management routines that operate on bare Object arrays. Some of those routines mimic the behavior of array lists, others provide other more specialized (generally faster but making requirements of the caller) list behavior.

An example is probably in order:

 Object[] list = null;
 String foo = "foo";
 String bar = "bar";

 // add our objects to a list
 list = ListUtil.add(list, foo);
 list = ListUtil.add(list, bar);

 // remove foo from the list (does so by clearing out that index, but it
 // doesn't slide subsequent elements down)
 ListUtil.clear(list, foo);

 // use the version of remove that calls equals() rather than just
 // checking for equality of references
 String anotherBar = "bar";
 ListUtil.clear(list, anotherBar);

 // append our objects to the end of the list letting list util know
 // that we're tracking the list size
 list = ListUtil.add(list, 0, foo);
 list = ListUtil.add(list, 1, bar);

 // remove the elements from the list, compacting it to preserve
 // element continuity
 ListUtil.remove(list, 0);
 ListUtil.remove(list, bar);
 

See the documentation for the individual functions for their exact behavior.

Nested Class Summary

protected static interface

ListUtil.EqualityComparator Used to allow the same code to optionally use reference equality and Object.equals(java.lang.Object).equality.

Field Summary

protected static int	DEFAULT_LIST_SIZE The size of a list to create if we have to create one entirely from scratch rather than just expand it.
protected static ListUtil.EqualityComparator	EQUALS_COMP
protected static ListUtil.EqualityComparator	REFERENCE_COMP

Constructor Summary

ListUtil()

Method Summary

protected static Object[]	accomodate(Object[] list, int index) Creates a new list that will accomodate the specified index and copies the contents of the old list to the first.
static Object[]	add(Object[] list, int startIdx, Object element) Adds the specified element to the next empty slot in the specified list.
static Object[]	add(Object[] list, Object element) Adds the specified element to the first empty slot in the specified list.
protected static Object	clear(ListUtil.EqualityComparator eqc, Object[] list, Object element) Helper function for clearRef(java.lang.Object[], java.lang.Object), etc.
static Object	clear(Object[] list, Object element) Clears out the first element that is functionally equal to the supplied element (list[idx].equals(element)).
static Object	clearRef(Object[] list, Object element) Clears out the first element that is referentially equal to the supplied element (list[idx] == element).
protected static boolean	contains(ListUtil.EqualityComparator eqc, Object[] list, Object element) Helper function for containsRef(java.lang.Object[], java.lang.Object), etc.
static boolean	contains(Object[] list, Object element) Looks for an element that is functionally equal to the supplied element (list[idx].equals(element)).
static boolean	containsRef(Object[] list, Object element) Looks for an object that is referentially equal to the supplied element (list[idx] == element).
protected static int	indexOf(ListUtil.EqualityComparator eqc, Object[] list, Object element) Helper function for indexOfRef(java.lang.Object[], java.lang.Object), etc.
static int	indexOf(Object[] list, Object element) Looks for an element that is functionally equal to the supplied element (list[idx].equals(element)).
static int	indexOfNull(Object[] list) Returns the lowest index in the array that contains null, or -1 if there is no room to add elements without expanding the array.
static int	indexOfRef(Object[] list, Object element) Looks for an object that is referentially equal to the supplied element (list[idx] == element) and returns its index in the array.
static Object[]	insert(Object[] list, int index, Object element) Inserts the supplied element at the specified position in the array, shifting the remaining elements down.
static void	main(String[] args) Run some tests.
static int	nextPowerOfTwo(int value) Rounds the specified value up to the next nearest power of two.
protected static NullPointerException	NPE() Throw a NullPointerException with the bad news.
protected static Object	remove(ListUtil.EqualityComparator eqc, Object[] list, Object element) Helper function for removeRef(java.lang.Object[], java.lang.Object), etc.
static Object	remove(Object[] list, int index) Removes the element at the specified index.
static Object	remove(Object[] list, Object element) Removes the first element that is functionally equal to the supplied element (list[idx].equals(element)).
static Object	removeRef(Object[] list, Object element) Removes the first element that is referentially equal to the supplied element (list[idx] == element).
static int	size(Object[] list) Returns the number of elements in the supplied list.
protected static Object[]	testAndAdd(ListUtil.EqualityComparator eqc, Object[] list, Object element) Helper function for testAndAddRef(java.lang.Object[], java.lang.Object), etc.
static Object[]	testAndAdd(Object[] list, Object element) Searches through the list checking to see if the element supplied is already in the list (using equals() to check for equality) and adds it if it is not.
static Object[]	testAndAddRef(Object[] list, Object element) Searches through the list checking to see if the element supplied is already in the list (using reference equality to check for existence) and adds it if it is not.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

REFERENCE_COMP

protected static final ListUtil.EqualityComparator REFERENCE_COMP

EQUALS_COMP

protected static final ListUtil.EqualityComparator EQUALS_COMP

DEFAULT_LIST_SIZE

protected static final int DEFAULT_LIST_SIZE

The size of a list to create if we have to create one entirely from scratch rather than just expand it.

See Also:

Constant Field Values

Constructor Detail

ListUtil

public ListUtil()

Method Detail

nextPowerOfTwo

public static int nextPowerOfTwo(int value)

Rounds the specified value up to the next nearest power of two.

add

public static Object[] add(Object[] list,
                           Object element)

Adds the specified element to the first empty slot in the specified list. Begins searching for empty slots at zeroth index.

Parameters:

list - the list to which to add the element. Can be null.

element - the element to add.

Returns:

a reference to the list with element added (might not be the list you passed in due to expansion, or allocation).

add

public static Object[] add(Object[] list,
                           int startIdx,
                           Object element)

Adds the specified element to the next empty slot in the specified list. Begins searching for empty slots at the specified index. This can be used to quickly add elements to a list that preserves consecutivity by calling it with the size of the list as the first index to check.

Parameters:

list - the list to which to add the element. Can be null.

startIdx - the index at which to start looking for a spot.

element - the element to add.

Returns:

a reference to the list with element added (might not be the list you passed in due to expansion, or allocation).

insert

public static Object[] insert(Object[] list,
                              int index,
                              Object element)

Inserts the supplied element at the specified position in the array, shifting the remaining elements down. The array will be expanded if necessary.

Parameters:

list - the list in which to insert the element. Can be null.

index - the index at which to insert the element.

element - the element to insert.

Returns:

a reference to the list with element inserted (might not be the list you passed in due to expansion, or allocation).

testAndAddRef

public static Object[] testAndAddRef(Object[] list,
                                     Object element)

Searches through the list checking to see if the element supplied is already in the list (using reference equality to check for existence) and adds it if it is not.

Parameters:

list - the list to which to add the element. Can be null.

element - the element to test and add.

Returns:

a reference to the list with element added (might not be the list you passed in due to expansion, or allocation) or null if the element was already in the original array.

testAndAdd

public static Object[] testAndAdd(Object[] list,
                                  Object element)

Searches through the list checking to see if the element supplied is already in the list (using equals() to check for equality) and adds it if it is not.

Parameters:

list - the list to which to add the element. Can be null.

element - the element to test and add.

Returns:

a reference to the list with element added (might not be the list you passed in due to expansion, or allocation) or null if the element was already in the original array.

testAndAdd

protected static Object[] testAndAdd(ListUtil.EqualityComparator eqc,
                                     Object[] list,
                                     Object element)

Helper function for testAndAddRef(java.lang.Object[], java.lang.Object), etc.

containsRef

public static boolean containsRef(Object[] list,
                                  Object element)

Looks for an object that is referentially equal to the supplied element (list[idx] == element).

Returns:

true if a matching element was found, false otherwise.

contains

public static boolean contains(Object[] list,
                               Object element)

Looks for an element that is functionally equal to the supplied element (list[idx].equals(element)).

Returns:

true if a matching element was found, false otherwise.

contains

protected static boolean contains(ListUtil.EqualityComparator eqc,
                                  Object[] list,
                                  Object element)

Helper function for containsRef(java.lang.Object[], java.lang.Object), etc.

indexOfNull

public static int indexOfNull(Object[] list)

Returns the lowest index in the array that contains null, or -1 if there is no room to add elements without expanding the array.

indexOfRef

public static int indexOfRef(Object[] list,
                             Object element)

Looks for an object that is referentially equal to the supplied element (list[idx] == element) and returns its index in the array.

Returns:

the index of the first matching element if one was found, -1 otherwise.

indexOf

public static int indexOf(Object[] list,
                          Object element)

Looks for an element that is functionally equal to the supplied element (list[idx].equals(element)).

Returns:

the index of the matching element if one was found, -1 otherwise.

indexOf

protected static int indexOf(ListUtil.EqualityComparator eqc,
                             Object[] list,
                             Object element)

Helper function for indexOfRef(java.lang.Object[], java.lang.Object), etc.

clearRef

public static Object clearRef(Object[] list,
                              Object element)

Clears out the first element that is referentially equal to the supplied element (list[idx] == element).

Returns:

the element that was removed or null if it was not found.

clear

public static Object clear(Object[] list,
                           Object element)

Clears out the first element that is functionally equal to the supplied element (list[idx].equals(element)).

Returns:

the object that was cleared from the array or null if no matching object was found.

clear

protected static Object clear(ListUtil.EqualityComparator eqc,
                              Object[] list,
                              Object element)

Helper function for clearRef(java.lang.Object[], java.lang.Object), etc.

removeRef

public static Object removeRef(Object[] list,
                               Object element)

Removes the first element that is referentially equal to the supplied element (list[idx] == element). The elements after the removed element will be slid down the array one spot to fill the place of the removed element.

Returns:

the object that was removed from the array or null if no matching object was found.

remove

public static Object remove(Object[] list,
                            Object element)

Removes the first element that is functionally equal to the supplied element (list[idx].equals(element)). The elements after the removed element will be slid down the array one spot to fill the place of the removed element.

Returns:

the object that was removed from the array or null if no matching object was found.

remove

protected static Object remove(ListUtil.EqualityComparator eqc,
                               Object[] list,
                               Object element)

Helper function for removeRef(java.lang.Object[], java.lang.Object), etc.

remove

public static Object remove(Object[] list,
                            int index)

Removes the element at the specified index. The elements after the removed element will be slid down the array one spot to fill the place of the removed element. If a null array is supplied or one that is not large enough to accomodate this index, null is returned.

Returns:

the object that was removed from the array or null if no object existed at that location.

size

public static int size(Object[] list)

Returns the number of elements in the supplied list.

accomodate

protected static Object[] accomodate(Object[] list,
                                     int index)

Creates a new list that will accomodate the specified index and copies the contents of the old list to the first.

NPE

protected static NullPointerException NPE()

Throw a NullPointerException with the bad news.

main

public static void main(String[] args)

Run some tests.