Collections Data Structure Java

  1. Home
  2. Java
  3. Collections Data Structure
  4. A map of values by class
/*
 * SubclassMap.java Created Jul 9, 2009 by Andrew Butler, PSL
 */
//package prisms.util;
import java.lang.reflect.Array;
/**
 * A map of values by class. This differs significantly from a normal key-value
 * map in that a value may be returned for a class input if an entry exists for
 * one of the class's superclasses (or inherited interfaces); an entry is not
 * required for the class itself.
 * 
 * @param 
 *            The type whose subtypes are used as keys in this map
 * @param 
 *            The type of value stored in this map
 */
public class SubClassMap {
  class MapItem {
    final Class theClass;
    V theValue;
    MapItem(Class clazz, V value) {
      theClass = clazz;
      theValue = value;
    }
  }
  private MapItem[] theItems;
  /**
   * Creates a SubClassMap
   */
  public SubClassMap() {
    theItems = new SubClassMap.MapItem[0];
  }
  /**
   * Adds or sets a value in this map
   * 
   * @param clazz
   *            The class to set the value for. After this, calls to
   *            {@link #get(Class)} with an argument that is
   *            clazz or one of its subclasses will return
   *            value unless there is another entry in the map
   *            for a subtype of clazz that is also a supertype
   *            of the argument to get(Class).
   * @param value
   *            The value to store in the map
   */
  public void put(Class clazz, V value) {
    for (MapItem item : theItems)
      if (item.theClass == clazz) {
        item.theValue = value;
        return;
      }
    theItems = ArrayUtils.add(theItems, new MapItem(clazz, value));
  }
  /**
   * Removes a value from this map
   * 
   * @param clazz
   *            The class to remove the value for. After this. calls to
   *            {@link #get(Class)} with an argument that is
   *            clazz or one of its subclasses will return the
   *            value associated with clazz's nearest superclass
   *            unless there is another entry in the map for a subtype of
   *            clazz that is also a supertype of the argument to
   *            get(Class).
   * @param allDescending
   *            Whether all subclasses of clazz should be removed
   *            as well
   */
  public void remove(Class clazz, boolean allDescending) {
    for (int i = 0; i < theItems.length; i++) {
      if (theItems[i].theClass == clazz
          || (allDescending && clazz
              .isAssignableFrom(theItems[i].theClass)))
        theItems = ArrayUtils.remove(theItems, i);
    }
  }
  /**
   * Gets the value assigned to subClass or its nearest supertype
   * for which there is an entry in this map.
   * 
   * @param subClass
   *            The type to get the value for
   * @return The value associated with the given type or its nearest
   *         superclass for which this map has an entry
   */
  public V get(Class subClass) {
    MapItem[] matches = new SubClassMap.MapItem[0];
    for (MapItem item : theItems) {
      if (item.theClass == subClass)
        return item.theValue;
      else if (item.theClass.isAssignableFrom(subClass))
        matches = ArrayUtils.add(matches, item);
    }
    if (matches.length == 0)
      return null;
    int minDist = 0;
    MapItem match = null;
    for (MapItem item : matches) {
      int dist = getTypeDistance(item.theClass, subClass);
      if (match == null || dist < minDist) {
        minDist = dist;
        match = item;
      }
    }
    return match.theValue;
  }
  private static int getTypeDistance(Class clazz, Class subClass) {
    if (clazz == subClass)
      return 0;
    int dist = getTypeDistance(clazz, subClass.getSuperclass());
    if (dist >= 0)
      return dist + 1;
    for (Class intf : subClass.getInterfaces()) {
      dist = getTypeDistance(clazz, intf);
      if (dist >= 0)
        return dist + 1;
    }
    return -1;
  }
}
/**
 * ArrayUtils provides some static methods for manipulating arrays easily when
 * using a tool such as {@link java.util.ArrayList} is inconvenient.
 */
final class ArrayUtils {
  /**
   * Gets the first element in the given array for which the
   * {@link EqualsChecker#equals(Object, Object)} returns true, or null if
   * this never occurs. The equals method is called with the element as the
   * first argument and the test parameter as the second.
   * 
   * @param 
   *            The type of array to get an element of
   * @param array
   *            The array to get the element of
   * @param test
   *            The object to compare the others with. This may be null.
   * @param checker
   *            The checker to determine which element to get
   * @return The first element in the array for which the
   *         {@link EqualsChecker#equals(Object, Object)} returns true, or
   *         null if this never occurs
   */
  public static  T get(T[] array, Object test, EqualsChecker checker) {
    for (T el : array)
      if (checker.equals(el, test))
        return el;
    return null;
  }
  /**
   * Inserts an element into the array--for primitive types
   * 
   * @param anArray
   *            The array to insert into
   * @param anElement
   *            The element to insert
   * @param anIndex
   *            The index for the new element
   * @return The new array with all elements of anArray, but with
   *         anElement inserted at index anIndex
   */
  public static Object addP(Object anArray, Object anElement, int anIndex) {
    Object ret;
    int length;
    if (anArray == null) {
      if (anIndex != 0)
        throw new ArrayIndexOutOfBoundsException("Cannot set "
            + anIndex + " element in a null array");
      ret = Array.newInstance(anElement.getClass(), 1);
      Array.set(ret, 0, anElement);
      return ret;
    } else {
      length = Array.getLength(anArray);
      ret = Array.newInstance(anArray.getClass().getComponentType(),
          length + 1);
    }
    System.arraycopy(anArray, 0, ret, 0, anIndex);
    put(ret, anElement, anIndex);
    System.arraycopy(anArray, anIndex, ret, anIndex + 1, length - anIndex);
    return ret;
  }
  /**
   * Inserts an element into the array
   * 
   * @param 
   *            The type of the object array
   * @param anArray
   *            The array to insert into
   * @param anElement
   *            The element to insert
   * @param anIndex
   *            The index for the new element
   * @return The new array with all elements of anArray, but with
   *         anElement inserted at index anIndex
   */
  public static  T[] add(T[] anArray, T anElement, int anIndex) {
    T[] ret;
    if (anArray == null) {
      if (anIndex != 0)
        throw new ArrayIndexOutOfBoundsException("Cannot set "
            + anIndex + " element in a null array");
      ret = (T[]) Array.newInstance(anElement.getClass(), 1);
      ret[0] = anElement;
      return ret;
    } else
      ret = (T[]) Array.newInstance(
          anArray.getClass().getComponentType(), anArray.length + 1);
    System.arraycopy(anArray, 0, ret, 0, anIndex);
    put(ret, anElement, anIndex);
    System.arraycopy(anArray, anIndex, ret, anIndex + 1, anArray.length
        - anIndex);
    return ret;
  }
  /**
   * @param anArray
   *            The array to extend
   * @param anElement
   *            The element to add into anArray
   * @return A new array of length anArray.length+1 whose
   *         contents are those of anArray followed by
   *         anElement
   */
  public static Object addP(Object anArray, Object anElement) {
    int len = anArray == null ? 0 : Array.getLength(anArray);
    return addP(anArray, anElement, len);
  }
  /**
   * @param 
   *            The type of the array
   * @param anArray
   *            The array to extend
   * @param anElement
   *            The element to add into anArray
   * @return A new array of length anArray.length+1 whose
   *         contents are those of anArray followed by
   *         anElement
   */
  public static  T[] add(T[] anArray, T anElement) {
    int len = anArray == null ? 0 : Array.getLength(anArray);
    return add(anArray, anElement, len);
  }
  /**
   * Moves an element in an array from one index to another
   * 
   * @param 
   *            The type of the array
   * @param anArray
   *            The array to move an element within
   * @param from
   *            The index of the element to move
   * @param to
   *            The index to move the element to
   * @return The original array
   */
  public static  T[] move(T[] anArray, int from, int to) {
    final T element = anArray[from];
    for (; from < to; from++)
      anArray[from] = anArray[from + 1];
    for (; from > to; from--)
      anArray[from] = anArray[from - 1];
    anArray[to] = element;
    return anArray;
  }
  /**
   * Moves an element in a primitive array from one index to another
   * 
   * @param anArray
   *            The array to move an element within
   * @param from
   *            The index of the element to move
   * @param to
   *            The index to move the element to
   * @return The original array
   */
  public static Object moveP(Object anArray, int from, int to) {
    if (anArray instanceof Object[])
      return move((Object[]) anArray, from, to);
    final Object element = Array.get(anArray, from);
    for (; from < to; from++)
      Array.set(anArray, from, Array.get(anArray, from + 1));
    for (; from > to; from--)
      Array.set(anArray, from, Array.get(anArray, from - 1));
    Array.set(anArray, to, element);
    return anArray;
  }
  private static void put(Object array, Object element, int index) {
    try {
      if (array instanceof Object[]) {
        try {
          ((Object[]) array)[index] = element;
        } catch (ArrayStoreException e) {
          throw new IllegalArgumentException(e.getMessage()
              + ": "
              + (element == null ? "null" : element.getClass()
                  .getName()) + " into "
              + array.getClass().getName());
        }
      } else {
        try {
          Array.set(array, index, element);
        } catch (IllegalArgumentException e) {
          throw new IllegalArgumentException(e.getMessage()
              + ": "
              + (element == null ? "null" : element.getClass()
                  .getName()) + " into "
              + array.getClass().getName(), e);
        }
      }
    } catch (ArrayIndexOutOfBoundsException e) {
      throw new ArrayIndexOutOfBoundsException(index + " into "
          + Array.getLength(array));
    }
  }
  /**
   * Merges all elements of a set of arrays into a single array with no
   * duplicates. For primitive types.
   * 
   * @param type
   *            The type of the result
   * @param arrays
   *            The arrays to merge
   * @return A new array containing all elements of array1 and
   *         all elements of array2 that are not present in
   *         array1
   * @throws NullPointerException
   *             If either array is null
   * @throws ArrayStoreException
   *             If elements in the arrays are incompatible with
   *             type
   */
  public static Object mergeInclusiveP(Class type, Object... arrays) {
    java.util.LinkedHashSet set = new java.util.LinkedHashSet();
    int i, j;
    for (i = 0; i < arrays.length; i++) {
      int len = Array.getLength(arrays[i]);
      for (j = 0; j < len; j++)
        set.add(Array.get(arrays[i], j));
    }
    Object ret = Array.newInstance(type, set.size());
    i = 0;
    for (Object el : set) {
      put(ret, el, i);
      i++;
    }
    return ret;
  }
  /**
   * Merges all elements of a set of arrays into a single array with no
   * duplicates.
   * 
   * @param 
   *            The type of the result
   * @param 
   *            The type of the input arrays
   * @param type
   *            The type of the result
   * @param arrays
   *            The arrays to merge
   * @return A new array containing all elements of array1 and
   *         all elements of array2 that are not present in
   *         array1
   * @throws NullPointerException
   *             If either array is null
   */
  public static  T1[] mergeInclusive(Class type,
      T2[]... arrays) {
    java.util.LinkedHashSet set = new java.util.LinkedHashSet();
    int i, j;
    for (i = 0; i < arrays.length; i++) {
      for (j = 0; j < arrays[i].length; j++)
        set.add(arrays[i][j]);
    }
    return set.toArray((T1[]) Array.newInstance(type, set.size()));
  }
  /**
   * Merges elements found in each of a set of arrays into a single array with
   * no duplicates. For primitive types.
   * 
   * @param type
   *            The type of the result
   * @param arrays
   *            The arrays to merge
   * @return A new array containing all common elements between
   *         array1 and array2
   * @throws NullPointerException
   *             If either array is null
   * @throws ArrayStoreException
   *             If elements in the arrays are incompatible with
   *             type
   */
  public static Object mergeExclusiveP(Class type, Object... arrays) {
    if (arrays.length == 0)
      return Array.newInstance(type, 0);
    java.util.ArrayList retSet = new java.util.ArrayList();
    int i, j, k;
    int len = Array.getLength(arrays[0]);
    for (j = 0; j < len; j++)
      retSet.add(Array.get(arrays[0], j));
    for (i = 1; i < arrays.length; i++) {
      for (j = 0; j < retSet.size(); j++) {
        len = Array.getLength(arrays[i]);
        boolean hasEl = false;
        for (k = 0; k < len; k++)
          if (equalsUnordered(retSet.get(j), Array.get(arrays[i], k))) {
            hasEl = true;
            break;
          }
        if (!hasEl) {
          retSet.remove(j);
          j--;
        }
      }
    }
    Object ret = Array.newInstance(type, retSet.size());
    for (i = 0; i < retSet.size(); i++)
      Array.set(ret, i, retSet.get(i));
    return ret;
  }
  /**
   * Merges elements found in both of two arrays into a single array with no
   * duplicates.
   * 
   * @param 
   *            The type of the result
   * @param 
   *            The type of the input arrays
   * @param type
   *            The type of the result
   * @param arrays
   *            The arrays to merge
   * @return A new array containing all common elements between
   *         array1 and array2
   * @throws NullPointerException
   *             If either array is null
   */
  public static  T1[] mergeExclusive(Class type,
      T2[]... arrays) {
    if (arrays.length == 0)
      return (T1[]) Array.newInstance(type, 0);
    java.util.ArrayList retSet = new java.util.ArrayList();
    int i, j, k;
    for (j = 0; j < arrays[0].length; j++)
      retSet.add(arrays[0][j]);
    for (i = 1; i < arrays.length; i++) {
      for (j = 0; j < retSet.size(); j++) {
        boolean hasEl = false;
        for (k = 0; k < arrays[i].length; k++)
          if (equalsUnordered(retSet.get(j), arrays[i][k])) {
            hasEl = true;
            break;
          }
        if (!hasEl) {
          retSet.remove(j);
          j--;
        }
      }
    }
    return retSet.toArray((T1[]) Array.newInstance(type, retSet.size()));
  }
  /**
   * Concatenates a series of arrays of any type
   * 
   * @param type
   *            The type of the arrays
   * @param arrays
   *            The arrays to concatenate
   * @return An array containing all elements of the arrays
   */
  public static Object concatP(Class type, Object... arrays) {
    if (arrays.length == 0)
      return Array.newInstance(type, 0);
    if (arrays.length == 1)
      return arrays[0];
    int size = 0;
    int[] sizes = new int[arrays.length];
    for (int a = 0; a < arrays.length; a++) {
      sizes[a] = Array.getLength(arrays[a]);
      size += sizes[a];
    }
    Object ret = Array.newInstance(type, size);
    int aLen = 0;
    for (int a = 0; a < arrays.length; a++) {
      System.arraycopy(arrays[a], 0, ret, aLen, sizes[a]);
      aLen += sizes[a];
    }
    return ret;
  }
  /**
   * Concatenates a series of arrays of a non-primitive type
   * 
   * @param 
   *            The type of the arrays
   * @param type
   *            The type of the arrays
   * @param arrays
   *            The arrays to concatenate
   * @return An array containing all elements of the arrays
   */
  public static  T[] concat(Class type, T[]... arrays) {
    if (arrays.length == 0)
      return (T[]) Array.newInstance(type, 0);
    if (arrays.length == 1)
      return arrays[0];
    int size = 0;
    for (int a = 0; a < arrays.length; a++) {
      if (arrays[a] != null)
        size += arrays[a].length;
    }
    T[] ret = (T[]) Array.newInstance(type, size);
    int aLen = 0;
    for (int a = 0; a < arrays.length; a++) {
      if (arrays[a] == null)
        continue;
      System.arraycopy(arrays[a], 0, ret, aLen, arrays[a].length);
      aLen += arrays[a].length;
    }
    return ret;
  }
  /**
   * @param 
   *            The type of the array to search
   * @param anArray
   *            The array to search
   * @param anElement
   *            The element to search for
   * @return The first index 0<=idx<anArray.length such
   *         that {@link #equals(Object, Object)} returns true for both
   *         anArray[idx] and anElement, or -1 if no
   *         such index exists
   */
  public static  int indexOf(T[] anArray, T anElement) {
    if (anArray == null)
      return -1;
    for (int i = 0; i < anArray.length; i++)
      if (equals(anArray[i], anElement))
        return i;
    return -1;
  }
  /**
   * @param anArray
   *            The array to search
   * @param anElement
   *            The element to search for
   * @return The first index 0<=idx<anArray.length such
   *         that {@link #equals(Object, Object)} returns true for both
   *         anArray[idx] and anElement, or -1 if no
   *         such index exists
   */
  public static int indexOfP(Object anArray, Object anElement) {
    if (anArray == null)
      return -1;
    if (anArray instanceof Object[]) {
      Object[] array2 = (Object[]) anArray;
      for (int i = 0; i < array2.length; i++) {
        if (equals(array2[i], anElement))
          return i;
      }
      return -1;
    } else {
      int i, len;
      len = Array.getLength(anArray);
      for (i = 0; i < len; i++) {
        if (equals(Array.get(anArray, i), anElement))
          return i;
      }
      return -1;
    }
  }
  /**
   * Removes the specified object from the array. For primitive types.
   * 
   * @param anArray
   *            The array to remove an element from
   * @param anIndex
   *            The index of the element to remove
   * @return A new array with all the elements of anArray except
   *         the element at anIndex
   */
  public static Object removeP(Object anArray, int anIndex) {
    Object ret;
    int length;
    if (anArray == null)
      return null;
    else {
      length = Array.getLength(anArray);
      ret = Array.newInstance(anArray.getClass().getComponentType(),
          length - 1);
    }
    System.arraycopy(anArray, 0, ret, 0, anIndex);
    System.arraycopy(anArray, anIndex + 1, ret, anIndex, length - anIndex
        - 1);
    return ret;
  }
  /**
   * Removes the specified object from the array
   * 
   * @param 
   *            The type of the array
   * @param anArray
   *            The array to remove an element from
   * @param anIndex
   *            The index of the element to remove
   * @return A new array with all the elements of anArray except
   *         the element at anIndex
   */
  public static  T[] remove(T[] anArray, int anIndex) {
    T[] ret;
    if (anArray == null)
      return null;
    else {
      ret = (T[]) Array.newInstance(
          anArray.getClass().getComponentType(), anArray.length - 1);
    }
    System.arraycopy(anArray, 0, ret, 0, anIndex);
    System.arraycopy(anArray, anIndex + 1, ret, anIndex, anArray.length
        - anIndex - 1);
    return ret;
  }
  /**
   * Removes the specified object from the array
   * 
   * @param anArray
   *            The array to remove an element from
   * @param anElement
   *            The element to remove
   * @return A new array with all the elements of anArray except
   *         anElement
   */
  public static Object removeP(Object anArray, Object anElement) {
    int idx = indexOfP(anArray, anElement);
    if (idx >= 0)
      return removeP(anArray, idx);
    else
      return anArray;
  }
  /**
   * Removes the specified object from the array
   * 
   * @param 
   *            The type of the array
   * @param anArray
   *            The array to remove an element from
   * @param anElement
   *            The element to remove
   * @return A new array with all the elements of anArray except
   *         anElement
   */
  public static  T[] remove(T[] anArray, T anElement) {
    int idx = indexOf(anArray, anElement);
    if (idx >= 0)
      return remove(anArray, idx);
    else
      return anArray;
  }
  /**
   * Removes all contents of array2 from array1. All
   * instances of array2 will also be removed from
   * array1. For primitive types.
   * 
   * @param array1
   *            The array to remove elements from
   * @param array2
   *            The array containing the elements to remove; or the element to
   *            remove itself
   * @return array1 missing all the contents of
   *         array2
   */
  public static Object removeAllP(Object array1, Object array2) {
    if (array1 == null || array2 == null)
      return array1;
    if (!array1.getClass().isArray())
      return null;
    if (!array2.getClass().isArray())
      array2 = new Object[] { array2 };
    else
      array2 = addP(array2, array2);
    java.util.BitSet remove = new java.util.BitSet();
    int len1 = Array.getLength(array1);
    int len2 = Array.getLength(array2);
    int i, j;
    for (i = 0; i < len1; i++) {
      for (j = 0; j < len2; j++) {
        if (equals(Array.get(array1, i), Array.get(array2, j))) {
          remove.set(i);
          break;
        }
      }
    }
    Object ret = Array.newInstance(array1.getClass().getComponentType(),
        len1 - remove.cardinality());
    // This copying section might be replaced by a more efficient version
    // using System.arraycopy()--this would be much faster than reflection,
    // especially for large arrays needing only a few elements removed
    for (i = 0, j = 0; i < len1; i++) {
      if (!remove.get(i)) {
        put(ret, Array.get(array1, i), j);
        j++;
      }
    }
    return ret;
  }
  /**
   * Removes all contents of array2 from array1. All
   * instances of array2 will also be removed from
   * array1.
   * 
   * @param 
   *            The type of the array
   * @param array1
   *            The array to remove elements from
   * @param array2
   *            The array containing the elements to remove; or the element to
   *            remove itself
   * @return array1 missing all the contents of
   *         array2
   */
  public static  T[] removeAll(T[] array1, Object array2) {
    if (array1 == null || array2 == null)
      return array1;
    if (!array1.getClass().isArray())
      return null;
    if (!array2.getClass().isArray())
      array2 = new Object[] { array2 };
    java.util.BitSet remove = new java.util.BitSet();
    int len1 = array1.length;
    int len2 = Array.getLength(array2);
    int i, j;
    for (i = 0; i < len1; i++) {
      for (j = 0; j < len2; j++) {
        if (equals(array1[i], Array.get(array2, j))) {
          remove.set(i);
          break;
        }
      }
    }
    T[] ret = (T[]) Array.newInstance(array1.getClass().getComponentType(),
        len1 - remove.cardinality());
    // This copying section might be replaced by a more efficient version
    // using System.arraycopy()--this would be much faster than reflection,
    // especially for large arrays needing only a few elements removed
    for (i = 0, j = 0; i < len1; i++) {
      if (!remove.get(i)) {
        ret[j] = array1[i];
        j++;
      }
    }
    return ret;
  }
  /**
   * Searches an array (possibly primitive) for an element
   * 
   * @param anArray
   *            The array to search
   * @param anElement
   *            The element to search for
   * @return True if anArray contains anElement,
   *         false otherwise
   */
  public static boolean containsP(Object anArray, Object anElement) {
    if (anArray == null)
      return false;
    if (anArray instanceof Object[]) {
      Object[] oa = (Object[]) anArray;
      for (int i = 0; i < oa.length; i++) {
        if (equals(oa[i], anElement))
          return true;
      }
    } else {
      int len = Array.getLength(anArray);
      for (int i = 0; i < len; i++) {
        if (equals(Array.get(anArray, i), anElement))
          return true;
      }
    }
    return false;
  }
  /**
   * @param 
   *            The type of the array to search
   * @param anArray
   *            The array to search
   * @param anElement
   *            The element to search for
   * @return True if anArray contains anElement,
   *         false otherwise
   */
  public static  boolean contains(T[] anArray, T anElement) {
    if (anArray == null)
      return false;
    for (int i = 0; i < anArray.length; i++) {
      if (equals(anArray[i], anElement))
        return true;
    }
    return false;
  }
  /**
   * Like {@link #containsP(Object, Object)} but the equality test is by
   * identity instead of the equals method
   * 
   * @param anArray
   *            The array to search
   * @param anElement
   *            The element to search for
   * @return True if anArray contains anElement by
   *         identity, false otherwise
   */
  public static boolean containspID(Object anArray, Object anElement) {
    if (anArray == null)
      return false;
    if (anArray instanceof Object[]) {
      Object[] oa = (Object[]) anArray;
      for (int i = 0; i < oa.length; i++) {
        if (oa[i] == anElement)
          return true;
      }
    } else {
      int len = Array.getLength(anArray);
      for (int i = 0; i < len; i++) {
        if (Array.get(anArray, i) == anElement)
          return true;
      }
    }
    return false;
  }
  /**
   * Like {@link #contains(Object[], Object)} but the equality test is by
   * identity instead of the equals method
   * 
   * @param 
   *            The type of the array to search
   * @param 
   *            The type of the element to search for
   * @param anArray
   *            The array to search
   * @param anElement
   *            The element to search for
   * @return True if anArray contains anElement by
   *         identity, false otherwise
   */
  public static  boolean containsID(T[] anArray, E anElement) {
    if (anArray == null)
      return false;
    for (int i = 0; i < anArray.length; i++) {
      if (anArray[i] == anElement)
        return true;
    }
    return false;
  }
  /**
   * A utility version of equals that allows comparison of null objects and
   * arrays. WARNING: Does not account for an array that contains a reference
   * to itself, directly or indirectly
   * 
   * @param o1
   *            The first object to compare
   * @param o2
   *            The second object to compare
   * @return true if o1 and o2 are arrays and their
   *         elements are equivalent or if either
   *         o1==null && o2==null or o1.equals(o2),
   *         false otherwise
   */
  public static boolean equals(Object o1, Object o2) {
    if (o1 == null)
      return o2 == null;
    if (o2 == null)
      return false;
    if (o1 instanceof Object[] && o2 instanceof Object[])
      return equals((Object[]) o1, (Object[]) o2);
    if (o1.getClass().isArray() && o2.getClass().isArray()) {
      if (!o1.getClass().equals(o2.getClass()))
        return false;
      int len = Array.getLength(o1);
      if (len != Array.getLength(o2))
        return false;
      for (int i = 0; i < len; i++) {
        if (!equals(Array.get(o1, i), Array.get(o2, i)))
          return false;
      }
      return true;
    }
    return o1.equals(o2);
  }
  private static boolean equals(Object[] o1, Object[] o2) {
    if (o1 == null)
      return o2 == null;
    if (o2 == null)
      return false;
    if (!o1.getClass().equals(o2.getClass()))
      return false;
    if (o1.length != o2.length)
      return false;
    for (int i = 0; i < o1.length; i++) {
      if (!equals(o1[i], o2[i]))
        return false;
    }
    return true;
  }
  /**
   * Like {@link #equals(Object, Object)}, but compares arrays without regard
   * to order
   * 
   * @param o1
   *            The first object to compare
   * @param o2
   *            The second object to compare
   * @return true if o1 and o2 are arrays and their
   *         elements are equivalent or if either
   *         o1==null && o2==null or o1.equals(o2),
   *         false otherwise
   */
  public static boolean equalsUnordered(Object o1, Object o2) {
    return equalsUnordered(o1, o2, new EqualsChecker() {
      public boolean equals(Object o3, Object o4) {
        if (o3 == null)
          return o4 == null;
        if (o4 == null)
          return false;
        if (!o3.getClass().isArray()) {
          if (o4.getClass().isArray())
            return false;
          return o3.equals(o4);
        } else if (!o4.getClass().isArray())
          return false;
        return equalsUnordered(o3, o4);
      }
    });
  }
  /**
   * Checks two values for equality
   */
  public static interface EqualsChecker {
    /**
     * Checks two values for equality
     * 
     * @param o1
     *            The first value to check
     * @param o2
     *            The second value to check
     * @return Whether the two values are equal
     */
    boolean equals(Object o1, Object o2);
  }
  /**
   * Like {@link #equals(Object, Object)}, but compares arrays without regard
   * to order and uses an independent checker to check for equality of
   * elements
   * 
   * @param o1
   *            The first object to compare
   * @param o2
   *            The second object to compare
   * @param checker
   *            The checker to check elements for equality
   * @return true if o1 and o2 are arrays and their
   *         elements are equivalent or if either
   *         o1==null && o2==null or o1.equals(o2),
   *         false otherwise
   */
  public static boolean equalsUnordered(Object o1, Object o2,
      EqualsChecker checker) {
    if (o1 == null)
      return o2 == null;
    if (o2 == null)
      return false;
    if (o1 instanceof Object[] && o2 instanceof Object[])
      return equalsUnordered((Object[]) o1, (Object[]) o2, checker);
    if (o1.getClass().isArray() && o2.getClass().isArray()) {
      if (!o1.getClass().equals(o2.getClass()))
        return false;
      int len = Array.getLength(o1);
      if (len != Array.getLength(o2))
        return false;
      if (len == 0)
        return true;
      long[] bs = new long[(len - 1) / 64 + 1];
      long mask;
      int i, j, bsIdx;
      o1Loop: for (i = 0; i < len; i++) {
        mask = 0;
        for (j = 0; j < len; j++) {
          bsIdx = j / 64;
          if (mask == 0)
            mask = 0x8000000000000000L;
          if ((bs[bsIdx] & mask) == 0
              && checker.equals(Array.get(o1, i),
                  Array.get(o2, j))) {
            bs[bsIdx] |= mask;
            continue o1Loop;
          }
          mask >>>= 1;
        }
        return false;
      }
      return true;
    }
    return checker.equals(o1, o2);
  }
  private static boolean equalsUnordered(Object[] o1, Object[] o2,
      EqualsChecker checker) {
    if (o1 == null)
      return o2 == null;
    if (o2 == null)
      return false;
    if (o1.length != o2.length)
      return false;
    if (o1.length == 0)
      return true;
    long[] bs = new long[(o2.length - 1) / 64 + 1];
    long mask;
    int i, j, bsIdx;
    o1Loop: for (i = 0; i < o1.length; i++) {
      mask = 0;
      for (j = 0; j < o2.length; j++) {
        bsIdx = j / 64;
        if (mask == 0)
          mask = 0x8000000000000000L;
        if ((bs[bsIdx] & mask) == 0 && checker.equals(o1[i], o2[j])) {
          bs[bsIdx] |= mask;
          continue o1Loop;
        }
        mask >>>= 1;
      }
      return false;
    }
    return true;
  }
  /**
   * A compliment to the {@link #equals(Object, Object)} method, this method
   * returns a hashcode for array such that it is consistent with
   * the equals contract for the {@link Object#equals(Object)} method,
   * represented by the {@link #equals(Object, Object)} method.
   * 
   * @param array
   *            The array to get a hashcode for
   * @return A hashcode based on array and its contents, if any
   */
  public static int hashCode(Object array) {
    if (array == null)
      return 0;
    if (!array.getClass().isArray())
      return array.hashCode();
    int ret = array.getClass().getComponentType().hashCode();
    int len = Array.getLength(array);
    for (int i = 0; i < len; i++) {
      ret *= hashCode(Array.get(array, i));
      ret += 29;
    }
    return ret;
  }
  /**
   * A utility method for printing out the contents of an array (not deeply)
   * 
   * @param array
   *            The array to print
   * @return A String containing the representation of the contents of
   *         array
   */
  public static String toString(Object array) {
    if (array == null)
      return "" + null;
    else if (array instanceof Object[]) {
      Object[] oa = (Object[]) array;
      StringBuffer ret = new StringBuffer("[");
      for (int i = 0; i < oa.length; i++) {
        ret.append(toString(oa[i]));
        if (i < oa.length - 1)
          ret.append(", ");
      }
      ret.append("]");
      return ret.toString();
    } else if (array.getClass().isArray()) {
      StringBuffer ret = new StringBuffer("[");
      int len = Array.getLength(array);
      for (int i = 0; i < len; i++) {
        ret.append(Array.get(array, i));
        if (i < len - 1)
          ret.append(", ");
      }
      ret.append("]");
      return ret.toString();
    } else
      return array.toString();
  }
  /**
   * Replaces toReplace with replacement in
   * array one time at the most
   * 
   * @param array
   *            The array to search and replace in
   * @param toReplace
   *            The object to replace
   * @param replacement
   *            The object to replace toReplace with the first
   *            time it is found
   * @return The index where toReplace was found and replaced, or
   *         -1 if it was not found in array
   */
  public static int replaceOnce(Object array, Object toReplace,
      Object replacement) {
    if (array == null)
      return -1;
    if (array instanceof Object[]) {
      Object[] array2 = (Object[]) array;
      for (int i = 0; i < array2.length; i++) {
        if (equals(array2[i], toReplace)) {
          array2[i] = replacement;
          return i;
        }
      }
      return -1;
    } else {
      int i, len;
      len = Array.getLength(array);
      for (i = 0; i < len; i++) {
        if (equals(Array.get(array, i), toReplace)) {
          put(array, replacement, i);
          return i;
        }
      }
      return -1;
    }
  }
  /**
   * Replaces toReplace with replacement in
   * array as many times as it occurs
   * 
   * @param array
   *            The array to search and replace in
   * @param toReplace
   *            The object to replace
   * @param replacement
   *            The object to replace toReplace with each time it
   *            is found
   * @return The number of times toReplace was found and replaced
   */
  public static int replaceAll(Object array, Object toReplace,
      Object replacement) {
    int count = 0;
    if (array == null)
      return count;
    if (array instanceof Object[]) {
      Object[] array2 = (Object[]) array;
      for (int i = 0; i < array2.length; i++) {
        if (equals(array2[i], toReplace)) {
          array2[i] = replacement;
          count++;
        }
      }
    } else {
      int i, len;
      len = Array.getLength(array);
      for (i = 0; i < len; i++) {
        if (equals(Array.get(array, i), toReplace)) {
          put(array, replacement, i);
          count++;
        }
      }
    }
    return count;
  }
  /**
   * Gets the elements that the two arrays have in common. Elements are
   * retrieved from the first array.
   * 
   * @param 
   *            The type of the first array and the return array
   * @param 
   *            The type of the second array
   * @param array1
   *            The first array
   * @param array2
   *            The second array
   * @return The elements in array1 that occur at least once in
   *         array2
   */
  public static  T[] commonElements(T[] array1, T2[] array2) {
    int count = 0;
    if (array1 == null || array2 == null)
      return (T[]) Array.newInstance(
          array1.getClass().getComponentType(), 0);
    int i, j;
    for (i = 0; i < array1.length; i++)
      for (j = 0; j < array2.length; j++)
        if (equals(array1[i], array2[j])) {
          count++;
          break;
        }
    T[] ret = (T[]) Array.newInstance(array1.getClass().getComponentType(),
        count);
    count = 0;
    for (i = 0; i < array1.length; i++)
      for (j = 0; j < array2.length; j++)
        if (equals(array1[i], array2[j])) {
          ret[count] = array1[i];
          count++;
          break;
        }
    return ret;
  }
  /**
   * Gets the elements that the two arrays have in common. Elements are
   * retrieved from the first array.
   * 
   * @param array1
   *            The first array
   * @param array2
   *            The second array
   * @return The elements in array1 that occur at least once in
   *         array2
   */
  public static Object[] commonElementsP(Object array1, Object array2) {
    int count = 0;
    if (array1 == null || array2 == null)
      return new Object[0];
    if (!array1.getClass().isArray() || array2.getClass().isArray())
      return new Object[0];
    int len1 = Array.getLength(array1);
    int len2 = Array.getLength(array2);
    int i, j;
    for (i = 0; i < len1; i++)
      for (j = 0; j < len2; j++)
        if (equals(Array.get(array1, i), Array.get(array2, j))) {
          count++;
          break;
        }
    Object[] ret = new Object[count];
    count = 0;
    for (i = 0; i < len1; i++)
      for (j = 0; j < len2; j++)
        if (equals(Array.get(array1, i), Array.get(array2, j))) {
          ret[count] = Array.get(array1, i);
          count++;
          break;
        }
    return ret;
  }
  /**
   * Gets the elements that are in array1, but not array 2.
   * 
   * @param 
   *            The type of the arrays
   * @param array1
   *            The first array
   * @param array2
   *            The second array
   * @return The elements in array1 that do not occur in
   *         array2
   */
  public static  T[] removedElements(T[] array1, T[] array2) {
    int count = 0;
    if (array1 == null || array2 == null)
      return array1;
    int len1 = array1.length;
    int len2 = array2.length;
    int i, j;
    for (i = 0; i < len1; i++) {
      count++;
      for (j = 0; j < len2; j++) {
        if (equals(array1[i], array2[j])) {
          count--;
          break;
        }
      }
    }
    T[] ret = (T[]) Array.newInstance(array1.getClass().getComponentType(),
        count);
    count = 0;
    for (i = 0; i < len1; i++) {
      count++;
      for (j = 0; j < len2; j++) {
        if (equals(array1[i], array2[j])) {
          count--;
          break;
        }
        ret[count] = array1[i];
      }
    }
    return ret;
  }
  /**
   * Gets the elements that are in array1, but not array 2.
   * 
   * @param array1
   *            The first array
   * @param array2
   *            The second array
   * @return The elements in array1 that do not occur in
   *         array2
   */
  public static Object[] removedElementsP(Object array1, Object array2) {
    int count = 0;
    if (array1 == null || array2 == null)
      return new Object[0];
    if (!array1.getClass().isArray() || array2.getClass().isArray())
      return new Object[0];
    int len1 = Array.getLength(array1);
    int len2 = Array.getLength(array2);
    int i, j;
    for (i = 0; i < len1; i++) {
      count++;
      for (j = 0; j < len2; j++) {
        if (equals(Array.get(array1, i), Array.get(array2, j))) {
          count--;
          break;
        }
      }
    }
    Object[] ret = new Object[count];
    count = 0;
    for (i = 0; i < len1; i++) {
      count++;
      for (j = 0; j < len2; j++) {
        if (equals(Array.get(array1, i), Array.get(array2, j))) {
          count--;
          break;
        }
        ret[count] = Array.get(array1, i);
      }
    }
    return ret;
  }
  /**
   * Gets the elements that are in array2, but not array 1.
   * 
   * @param array1
   *            The first array
   * @param array2
   *            The second array
   * @return The elements in array2 that do not occur in
   *         array1
   */
  public static Object[] addedElements(Object array1, Object array2) {
    int count = 0;
    if (array1 == null || array2 == null)
      return new Object[0];
    if (!array1.getClass().isArray() || array2.getClass().isArray())
      return new Object[0];
    int len1 = Array.getLength(array1);
    int len2 = Array.getLength(array2);
    int i, j;
    for (i = 0; i < len1; i++) {
      count++;
      for (j = 0; j < len2; j++) {
        if (equals(Array.get(array2, i), Array.get(array1, j))) {
          count--;
          break;
        }
      }
    }
    Object[] ret = new Object[count];
    count = 0;
    for (i = 0; i < len1; i++) {
      count++;
      for (j = 0; j < len2; j++) {
        if (equals(Array.get(array2, i), Array.get(array1, j))) {
          count--;
          break;
        }
        ret[count] = Array.get(array2, i);
      }
    }
    return ret;
  }
  /**
   * Reverses the order of an array
   * 
   * @param 
   *            The type of the array to reverse
   * @param array
   *            The array to reverse
   * @return The reversed array, same as the original reference
   */
  public static  T[] reverse(T[] array) {
    if (array == null)
      return array;
    T temp;
    final int aLen = array.length - 1;
    for (int i = 0; i < array.length / 2; i++) {
      temp = array[i];
      array[i] = array[aLen - i];
      array[aLen - i] = temp;
    }
    return array;
  }
  /**
   * Reverses the order of an array. Similar to {@link #reverse(Object[])} but
   * works for primitive arrays as well.
   * 
   * @param array
   *            The array to reverse
   * @return The reversed array, same as the original reference
   */
  public static Object reverseP(Object array) {
    if (array == null)
      return array;
    if (array instanceof Object[])
      return reverse((Object[]) array);
    Object temp;
    final int aLen = Array.getLength(array);
    for (int i = 0; i < aLen / 2; i++) {
      temp = Array.get(array, i);
      put(array, Array.get(array, aLen - i - 1), i);
      put(array, temp, aLen - i - 1);
    }
    return array;
  }
  /**
   * @see DifferenceListenerE
   * 
   * @param 
   *            The type of the original array
   * @param 
   *            The type of the modifying array
   */
  public static interface DifferenceListener extends
      DifferenceListenerE {
    /**
     * @see prisms.util.ArrayUtils.DifferenceListenerE#identity(java.lang.Object,
     *      java.lang.Object)
     */
    boolean identity(T1 o1, T2 o2);
    /**
     * @see prisms.util.ArrayUtils.DifferenceListenerE#added(java.lang.Object,
     *      int, int)
     */
    T1 added(T2 o, int mIdx, int retIdx);
    /**
     * @see prisms.util.ArrayUtils.DifferenceListenerE#removed(java.lang.Object,
     *      int, int, int)
     */
    T1 removed(T1 o, int oIdx, int incMod, int retIdx);
    /**
     * @see prisms.util.ArrayUtils.DifferenceListenerE#set(java.lang.Object,
     *      int, int, java.lang.Object, int, int)
     */
    T1 set(T1 o1, int idx1, int incMod, T2 o2, int idx2, int retIdx);
  }
  /**
   * 


   * This listener contains all information needed to reconcile two arrays
   * using the
   * {@link ArrayUtils#adjust(Object[], Object[], prisms.util.ArrayUtils.DifferenceListenerE)}
   * method.
   * 


   * 
   * 


   * There are many different indices that may or may not be relevant to a
   * particular listener:
   * 


       * 
  • oIdx: The index of the element in the original array

    •    * 
  • incMod: The index of the element in a copy of the original
       * array that has been modified incrementally for each add, remove, and
       * reorder operation

    •    * 
  • mIdx: The index of the element in the modifier array

    •    * 
  • retIdx: The index that the returned element (if not null) will
       * be at in the result array

    •    * 

   * oIdx and mIdx are self-explanatory. incMod and retIdx are useful for
   * listeners that modify an external ordered set incrementally with each
   * listener method invocation.
   * 


   * 
   * 


   * An Example
   * Suppose there is a list, L, whose data can only be modified
   * incrementally by the methods add(value, index), remove(index), and
   * move(fromIndex, toIndex), but can be accessed in batch by the getData
   * method, which returns an array of all data in the list. Suppose the list
   * needs to be modified to represent a new arbitrary set of data, d.
   * d may or may not contain elements represented in L. These
   * elements, if present, may be in different order and new items not present
   * in L may be present in d. To modify L to represent
   * the data in d in the correct order, the
   * {@link ArrayUtils#adjust(Object[], Object[], DifferenceListenerE)} method
   * should be called with L.getData(), d, and a listener whose
   * methods perform the following operations:
   * 


       * 
  • {@link #identity(Object, Object)}: Tests the two elements to see if
       * the item from L represents the item in d, possibly by
       * simply calling {@link Object#equals(Object)}

    •    * 
  • {@link #added(Object, int, int)}: Invokes L.add(o2, retIdx).

    •    * 
  • {@link #removed(Object, int, int, int)}: Invokes
       * L.remove(incMod). Using incMod accounts for any previous
       * modifications that may have been performed on the list from the listener.
       * 

    •    * 
  • {@link #set(Object, int, int, Object, int, int)}: Invokes
       * L.move(incMod, retIdx). This again accounts for all previous
       * changes to the list and moves the element to the index intended by the
       * adjust method.

    •    * 

   * The end result of this invocation will be that L contains all the
   * data in d, only the data in d, and is ordered identically
   * to d. The returned array may be ignored.
   * 


   * 
   * 


   * Alternate Operation:
   * 


       * 
  • If it is intended that the modification operation should only add
       * data to L, the remove method may do nothing and return o. The
       * return value will cause the adjust method to update future indexes,
       * assuming that the value is kept and not removed.

    •    * 
  • If order is not important or no move(fromIndex, toIndex) method
       * exists, the set method may do nothing and return o1. This will have no
       * effect on the result of the operation other than leaving the items
       * originally in L (those that were also present in d) in
       * their original order.

    •    * 
  • Other permutations may exist depending on the business logic used by
       * the listener.

    •    * 

   * 


   * 
   * 


   * The listener is entirely free to choose whether items are added or
   * removed from the original array and its representations by modifying
   * whether the return value from those methods is null. The adjust method
   * does not care what is returned from the add/remove/set methods except
   * whether the value is null. The listener is free to perform index moving
   * operations or not. This method will never cause an index out of bounds
   * error assuming the related data sets are not modified by anything other
   * than the listener and the data in the arrays passed into the adjust
   * method do not change.
   * 


   * 
   * @param 
   *            The type of the original array
   * @param 
   *            The type of the modifying array
   * @param 
   *            The type of exception that may be thrown
   */
  public static interface DifferenceListenerE {
    /**
     * Tests the identity of an item from each of the two sets. This method
     * should return true if one item is a representation of the other or
     * both are a representation of the same piece of data.
     * 
     * @param o1
     *            The object from the first set
     * @param o2
     *            The object from the second set
     * @return Whether the two objects are fundamentally equivalent
     * @throws E
     *             If an error occurs in this method
     */
    boolean identity(T1 o1, T2 o2) throws E;
    /**
     * Called when a value is found in the second set that is not present in
     * the first set
     * 
     * @param o
     *            The unmatched object
     * @param mIdx
     *            The index in the second array where the unmatched object
     *            was found
     * @param retIdx
     *            The index that the new element will be inserted into the
     *            final array
     * @return The new T1-type element to insert into the return array, or
     *         null if the new element is not to be inserted
     * @throws E
     *             If an error occurs in this method
     */
    T1 added(T2 o, int mIdx, int retIdx) throws E;
    /**
     * Called when a value is found in the first set that is not present in
     * the second set
     * 
     * @param o
     *            The unmatched object
     * @param oIdx
     *            The index in the first array where the unmatched object
     *            was found
     * @param incMod
     *            The index where the unmatched element would occur the
     *            incrementally modified original array
     * @param retIdx
     *            The index in the final array where the replacement will be
     *            located if a non-null value is returned
     * @return null if the original object is to be removed, otherwise its
     *         replacement
     * @throws E
     *             If an error occurs in this method
     */
    T1 removed(T1 o, int oIdx, int incMod, int retIdx) throws E;
    /**
     * Called when elements in the two arrays match
     * 
     * @param o1
     *            The element in the first array
     * @param idx1
     *            The index of the element in the first array
     * @param incMod
     *            The index where the element in the original array would
     *            occur the incrementally modified original array
     * @param o2
     *            The element in the second array
     * @param idx2
     *            The index of the element in the second array
     * @param retIdx
     *            The index of the returned element in the final array
     * @return The element to be inserted in the final array, or null if the
     *         element is to be removed
     * @throws E
     *             If an error occurs in this method
     */
    T1 set(T1 o1, int idx1, int incMod, T2 o2, int idx2, int retIdx)
        throws E;
  }
  /**
   * 


   * Reconciles differences between two ordered sets of objects. Allows a
   * programmer highly customized control between two different
   * representations of a data set. The arrays are compared and the listener
   * is notified when any differences are encountered, allowing it to
   * determine the composition of the returned array and/or perform
   * well-defined operations represented by the differences or similarities.
   * 


   * 
   * @param 
   *            The type of the original array
   * @param 
   *            The type of the modifying array
   * @param 
   *            The type of exception that may be thrown
   * @param original
   *            The original array
   * @param modifier
   *            The modifying array
   * @param dl
   *            The listener to determine how to deal with differences between
   *            the two arrays
   * @return A final array that is the result of applying select changes
   *         between the original and the modifying arrays
   * @throws E
   *             If the {@link DifferenceListenerE} throws an exception
   */
  public static  T1[] adjust(T1[] original,
      T2[] modifier, DifferenceListenerE dl) throws E {
    ArrayAdjuster adjuster = new ArrayAdjuster(
        original, modifier, dl);
    return adjuster.adjust();
  }
  static final Object NULL = new Object();
  /**
   * Adjusts arrays. This is the more complicated and capable structure used
   * by {@link ArrayUtils#adjust(Object[], Object[], DifferenceListenerE)}
   * 
   * @param 
   *            The type of the original array
   * @param 
   *            The type of the modifying array
   * @param 
   *            The type of exception that may be thrown
   */
  public static class ArrayAdjuster {
    private final T1[] original;
    private final int[] oIdxAdj;
    private final int[] oMappings;
    private final T2[] modifier;
    private final int[] mMappings;
    private final boolean[] entriesSet;
    private final DifferenceListenerE dl;
    private int maxLength;
    private boolean isNullElement;
    /**
     * Creates an adjuster that can adjust one array by another
     * 
     * @param o
     *            The original array
     * @param m
     *            The modified array
     * @param listener
     *            The listener to determine how to deal with differences
     *            between the two arrays
     * @see ArrayUtils#adjust(Object[], Object[], DifferenceListenerE)
     */
    public ArrayAdjuster(T1[] o, T2[] m,
        DifferenceListenerE listener) {
      original = o;
      oIdxAdj = new int[o.length];
      oMappings = new int[o.length];
      modifier = m;
      mMappings = new int[m.length];
      entriesSet = new boolean[m.length];
      dl = listener;
    }
    private void init() throws E {
      int o, m, r = original.length + modifier.length;
      for (m = 0; m < modifier.length; m++)
        mMappings[m] = -1;
      for (o = 0; o < original.length; o++) {
        oIdxAdj[o] = o;
        oMappings[o] = -1;
        for (m = 0; m < modifier.length; m++) {
          if (mMappings[m] >= 0)
            continue;
          if (dl.identity(original[o], modifier[m])) {
            oMappings[o] = m;
            mMappings[m] = o;
            r--;
            break;
          }
        }
      }
      maxLength = r;
    }
    /**
     * Adjusts the arrays set from the constructor
     * 
     * @return The adjusted array
     * @throws E
     *             If an error occurs in one of the listener's methods
     * @see ArrayUtils#adjust(Object[], Object[], DifferenceListenerE)
     */
    public T1[] adjust() throws E {
      init();
      int m, o, r = 0;
      Object[] ret = new Object[maxLength];
      for (o = 0; o < original.length && oMappings[o] < 0; o++)
        if (remove(o, -1, ret, r))
          r++;
      for (m = 0; m < modifier.length; m++) {
        // Add or set each modifier
        o = mMappings[m];
        if (o >= 0) {
          if (set(o, m, ret, r))
            r++;
          /* Remove the originals that occur before the next match */
          for (o++; o < original.length && oMappings[o] < 0; o++) {
            if (ret[r] != null) {
              Object temp = ret[r];
              for (int r2 = r; r < ret.length - 1 && temp != null; r2++) {
                Object temp2 = ret[r2 + 1];
                ret[r2 + 1] = temp;
                temp = temp2;
              }
            }
            if (remove(o, m + 1, ret, r))
              r++;
          }
        } else {
          if (ret[r] != null) {
            Object temp = ret[r];
            for (int r2 = r; r < ret.length - 1 && temp != null; r2++) {
              Object temp2 = ret[r2 + 1];
              ret[r2 + 1] = temp;
              temp = temp2;
            }
          }
          if (add(m, ret, r))
            r++;
        }
      }
      for (int i = 0; i < r; i++)
        if (ret[i] == NULL)
          ret[i] = null;
      T1[] actualRet = (T1[]) Array.newInstance(original.getClass()
          .getComponentType(), r);
      System.arraycopy(ret, 0, actualRet, 0, r);
      return actualRet;
    }
    /**
     * Marks the current value as a null value. If an actual null were
     * returned, adjust would interpret this as meaning the element should
     * be removed from the array, with subsequent indices being affected. If
     * this method is called from {@link DifferenceListenerE}.add, remove,
     * or set, the element's place will be saved and that element in the
     * returned array will be null.
     */
    public void nullElement() {
      isNullElement = true;
    }
    static void mergeSort(int[] order, int[] distances, int start, int end) {
      if (end - start <= 1)
        return;
      int mid = (start + end + 1) / 2;
      mergeSort(order, distances, start, mid);
      mergeSort(order, distances, mid, end);
      while (start < mid && mid < end) {
        if (distances[start] < distances[mid]) // Reverse order
        {
          int temp = distances[mid];
          int temp2 = order[mid];
          for (int i = mid; i > start; i--) {
            distances[i] = distances[i - 1];
            order[i] = order[i - 1];
          }
          distances[start] = temp;
          order[start] = temp2;
          mid++;
        }
        start++;
      }
    }
    private boolean add(int m, Object[] ret, int r) throws E {
      entriesSet[m] = true;
      T1 item = dl.added(modifier[m], m, r);
      if (isNullElement) {
        item = (T1) NULL;
        isNullElement = false;
      }
      // Adjust the incremental modification indexes
      if (item != null) {
        ret[r] = item;
        for (int i = 0; i < oIdxAdj.length; i++)
          if (oIdxAdj[i] >= r)
            oIdxAdj[i]++;
      } else {
        for (; r < ret.length - 1; r++)
          ret[r] = ret[r + 1];
      }
      return item != null;
    }
    private boolean remove(int o, int m, Object[] ret, int r) throws E {
      T1 item = dl.removed(original[o], o, oIdxAdj[o], r);
      if (isNullElement) {
        item = (T1) NULL;
        isNullElement = false;
      }
      // Adjust the incremental modification indexes
      if (item == null) {
        oIdxAdj[o] = -1;
        for (; o < oIdxAdj.length; o++)
          oIdxAdj[o]--;
      } else
        ret[r] = item;
      return item != null;
    }
    private boolean set(int o, int m, Object[] ret, int r) throws E {
      if (entriesSet[m])
        return ret[r] != null;
      if (oIdxAdj[o] > r && oIdxAdj[o] - r <= 10) {
        /*
         * If a few elements have been moved forward several indices, we
         * want to fire a few move events on those elements rather than
         * many move events for a few index differences.
         */
        int o2;
        for (o2 = o - 1; o2 >= 0; o2--)
          if (oMappings[o2] > m)
            set(o2, oMappings[o2], ret, r + oMappings[o2] - m);
      }
      entriesSet[m] = true;
      T1 item = dl.set(original[o], o, oIdxAdj[o], modifier[m], m, r);
      if (isNullElement) {
        item = (T1) NULL;
        isNullElement = false;
      }
      // Adjust the incremental modification indexes
      if (item != null) {
        ret[r] = item;
        int oAdj = oIdxAdj[o];
        if (r > oAdj) { // Element moved forward--decrement incMods up
                // to the new index
          for (int i = 0; i < oIdxAdj.length; i++)
            if (oIdxAdj[i] >= oAdj && oIdxAdj[i] <= r)
              oIdxAdj[i]--;
        } else if (r < oAdj) { // Element moved backward--increment
                    // incMods up to the original index
          for (int i = 0; i < oIdxAdj.length; i++)
            if (oIdxAdj[i] >= r && oIdxAdj[i] < oAdj)
              oIdxAdj[i]++;
        }
      } else {
        oIdxAdj[o] = -1;
        for (int i = 0; i < oIdxAdj.length; i++)
          if (oIdxAdj[i] > r)
            oIdxAdj[i]--;
        for (; r < ret.length - 1; r++)
          ret[r] = ret[r + 1];
      }
      return item != null;
    }
  }
  /**
   * A listener used for {@link #sort(Object [], SortListener)}
   * 
   * @param 
   *            The type of object to sort
   */
  public static interface SortListener extends java.util.Comparator {
    /**
     * Called just after two elements are swapped.
     * 
     * @param o1
     *            The first element being moved
     * @param idx1
     *            The index (in the pre-swap array) of the first element
     * @param o2
     *            The second element being moved
     * @param idx2
     *            The index (in the pre-swap array) of the second element
     */
    void swapped(T o1, int idx1, T o2, int idx2);
  }
  /**
   * Sorts an array, allowing for complex operations during the sort, such as
   * sorting arrays in parallel.
   * 
   * This is an implementation of selection sort. Selection sort is used
   * because although it may perform many more comparison operations than
   * other methods, there is no other method that performs fewer swaps. It is
   * anticipated that this algorithm will be used most often in the case that
   * multiple operations must take place during a swap, while comparison
   * should be fairly quick.
   * 
   * @param 
   *            The type of the array to sort
   * @param array
   *            The array to sort
   * @param listener
   *            The listener to use for comparisons and to notify of swapping
   */
  public static  void sort(T[] array, SortListener listener) {
    for (int i = 0; i < array.length - 1; i++) {
      int min = findMin(array, i, listener);
      if (min != i) {
        T ta = array[i];
        T tb = array[min];
        array[i] = tb;
        array[min] = ta;
        listener.swapped(ta, i, tb, min);
      }
    }
  }
  private static  int findMin(T[] array, int start,
      SortListener listener) {
    int minIdx = start;
    for (int i = start + 1; i < array.length; i++)
      if (listener.compare(array[i], array[minIdx]) < 0)
        minIdx = i;
    return minIdx;
  }
  /**
   * Represents some statistical information calculated on a set of float data
   */
  public static class ArrayStatistics {
    /**
     * The smallest non-NaN, non-infinite datum encountered by this
     * statistics set
     */
    public float min;
    /**
     * The largest non-NaN, non-infinite datum encountered by this
     * statistics set
     */
    public float max;
    /**
     * The number of NaN data encountered by this statistics set
     */
    public int naNCount;
    /**
     * The number of +Inf data encountered by this statistics set
     */
    public int posInfCount;
    /**
     * The number of -Inf data encountered by this statistics set
     */
    public int negInfCount;
    /**
     * The number of non-NaN, non-infinite data encountered by this
     * statistics set
     */
    public int validCount;
    /**
     * The mean value of all non-NaN, non-infinite data encountered by this
     * statistics set
     */
    public float mean;
    /**
     * A running data measure that allows the standard deviation of all
     * non-NaN, non-infinite data encountered by this statistics set
     */
    private float q;
    /**
     * Creates an ArrayStatistics set
     */
    public ArrayStatistics() {
      min = Float.MAX_VALUE;
      max = Float.MIN_VALUE;
      mean = 0;
      q = Float.NaN;
      validCount = 0;
      naNCount = 0;
      posInfCount = 0;
      negInfCount = 0;
    }
    /**
     * Adds a value to this statistics set
     * 
     * @param value
     *            The value to analyze
     */
    public void inputValue(float value) {
      if (Float.isNaN(value))
        naNCount++;
      else if (Float.isInfinite(value)) {
        if (value > 0)
          posInfCount++;
        else
          negInfCount++;
      } else if (validCount == 0) {
        mean = value;
        q = 0;
        validCount++;
      } else {
        if (value < min)
          min = value;
        if (value > max)
          max = value;
        q = q + (validCount * (mean - value) * (mean - value))
            / (validCount + 1);
        validCount++;
        mean = mean + (value - mean) / validCount;
      }
    }
    /**
     * @return The standard deviation of all non-NaN, non-infinite data
     *         encountered by this statistics set
     */
    public float getSigma() {
      return (float) Math.sqrt(q / (validCount - 1));
    }
    /**
     * @return The total number of data encountered by this statistics set
     */
    public int getTotalCount() {
      return validCount + naNCount + posInfCount + negInfCount;
    }
    @Override
    public String toString() {
      StringBuilder ret = new StringBuilder();
      ret.append(getTotalCount());
      ret.append(" values ranged ");
      ret.append(min);
      ret.append(" to ");
      ret.append(max);
      ret.append("; mean=");
      ret.append(mean);
      ret.append(", st.dev.=");
      ret.append(getSigma());
      ret.append("; ");
      ret.append(naNCount);
      ret.append("NaN, ");
      ret.append(posInfCount);
      ret.append("+Inf, ");
      ret.append(negInfCount);
      ret.append("-Inf");
      return ret.toString();
    }
  }
  /**
   * Performs a simple statistical analysis of an array of floats
   * 
   * @param array
   *            An n-dimensional array of floats
   * @param stats
   *            The ArrayStatistics object to populate, or null to create a
   *            new one
   * @return The statistics object
   */
  public static ArrayStatistics getStatistics(Object array,
      ArrayStatistics stats) {
    if (array == null)
      return null;
    if (stats == null)
      stats = new ArrayStatistics();
    if (array instanceof Object[]) {
      for (Object subArray : (Object[]) array)
        getStatistics(subArray, stats);
      return stats;
    }
    if (!(array instanceof float[]))
      throw new IllegalArgumentException(
          "Cannot statistically analyze a "
              + array.getClass().getName());
    for (float f : (float[]) array)
      stats.inputValue(f);
    return stats;
  }
  /**
   * A testing method
   * 
   * @param args
   *            The command-line arguments. The first argument is used to
   *            determine what test to run.
   */
  public static void main(String[] args) {
    String test;
    if (args.length == 0)
      test = "intSort";
    else
      test = args[0];
    if (test.equals("intSort")) {
      int[] random = new int[10000];
      int[] random2 = new int[random.length];
      for (int i = 0; i < random.length; i++)
        random[i] = (int) (Math.random() * Integer.MAX_VALUE);
      ArrayAdjuster.mergeSort(random2, random, 0, random.length);
      boolean sorted = true;
      for (int i = 0; i < random.length - 1; i++)
        if (random[i] < random[i + 1]) {
          sorted = false;
          break;
        }
      System.out.println("Sort " + (sorted ? "succeeded" : "failed"));
    } else if (test.equals("adjust")) {
      final Integer[] start = new Integer[25];
      for (int i = 0; i < start.length; i++)
        start[i] = new Integer(i);
      Integer[] modifier = new Integer[start.length];
      for (int i = 0; i < modifier.length; i++) {
        if (i % 5 != 0)
          modifier[i] = new Integer(i);
        else
          modifier[i] = new Integer(i / 5 * start.length);
      }
      Integer[] result = adjust(start, modifier,
          new DifferenceListener() {
            public boolean identity(Integer o1, Integer o2) {
              return o1.equals(o2);
            }
            public Integer added(Integer o, int mIdx, int retIdx) {
              return o;
            }
            public Integer removed(Integer o, int oIdx,
                int oIdxAdj, int retIdx) {
              return o;
            }
            public Integer set(Integer o1, int idx1, int oIdxAdj,
                Integer o2, int idx2, int retIdx) {
              if (o1.intValue() % 5 == 2)
                return null;
              return o1;
            }
          });
      System.out.println("Original array=" + toString(start));
      System.out.println("Modifier array=" + toString(modifier));
      System.out.println("Adjusted array=" + toString(result));
    } else
      throw new IllegalArgumentException("Unrecognized test: " + test);
  }
}