Collections Data Structure Java

/* CollectionsX.java
{{IS_NOTE
  Purpose:
  Description:
  History:
  2001/09/15 13:46:20, Create, Tom M. Yeh.
}}IS_NOTE
Copyright (C) 2001 Potix Corporation. All Rights Reserved.
{{IS_RIGHT
  This program is distributed under GPL Version 3.0 in the hope that
  it will be useful, but WITHOUT ANY WARRANTY.
}}IS_RIGHT
*/
import java.util.AbstractCollection;
import java.util.Collection;
import java.util.Collections;
import java.util.Set;
import java.util.Map;
import java.util.AbstractList;
import java.util.List;
import java.util.LinkedList;
import java.util.Iterator;
import java.util.ListIterator;
import java.util.Enumeration;
import java.util.NoSuchElementException;
/**
 * The collection related utilities.
 *
 * @author tomyeh
 * @see java.util.Collections
 */
public class CollectionsX {
  /** An enumeration on top of a collection or iterator.
   */
  public static final class CollectionEnumeration implements Enumeration {
    private final Iterator _iter;
    public CollectionEnumeration(Collection c) {
      this(c != null ? c.iterator(): null);
    }
    public CollectionEnumeration(Iterator iter) {
      _iter = iter;
    }
    public final boolean hasMoreElements() {
      return _iter != null && _iter.hasNext();
    }
    public final Object nextElement() {
      if (_iter != null)
        return _iter.next();
      throw new NoSuchElementException();
    }
  }
  /** An enumeration on top of an array.
   */
  public static final class ArrayEnumeration implements Enumeration {
    private final Object[] _ary;
    private int _cursor = 0;
    public ArrayEnumeration(Object[] ary) {
      _ary = ary;
    }
    public final boolean hasMoreElements() {
      return _ary != null && _cursor < _ary.length;
    }
    public final Object nextElement() {
      if (hasMoreElements())
        return _ary[_cursor++];
      throw new NoSuchElementException();
    }
  }
  /** An enumeration that enumerates one element.
   */
  public static final class OneEnumeration implements Enumeration {
    private boolean _nomore;
    private final Object _one;
    public OneEnumeration(Object one) {
      _one = one;
    }
    public final boolean hasMoreElements() {
      return !_nomore;
    }
    public final Object nextElement() {
      if (_nomore)
        throw new NoSuchElementException();
      _nomore = true;
      return _one;
    }
  }
  /** An readonly collection on top of an array.
   */
  public static final class ArrayCollection extends AbstractCollection {
    private final Object[] _ary;
    public ArrayCollection(Object[] ary) {
      _ary = ary;
    }
    public final int size() {
      return _ary != null ? _ary.length: 0;
    }
    public Iterator iterator() {
      return new ArrayIterator(_ary);
    }
  }
  /** An readonly list on top of an array.
   */
  public static final class ArrayList extends AbstractList {
    private final Object[] _ary;
    public ArrayList(Object[] ary) {
      _ary = ary;
    }
    public final int size() {
      return _ary != null ? _ary.length: 0;
    }
    public final Object get(int index) {
      return _ary[index];
    }
  }
  /** An iterator on top of an array.
   */
  public static class ArrayIterator implements Iterator {
    /*package*/ final Object[] _ary;
    /*package*/ int _cursor = 0, _last = -1;
    /** @param ary an array or null. */
    public ArrayIterator(Object[] ary) {
      _ary = ary;
    }
    public final boolean hasNext() {
      return _ary != null && _cursor < _ary.length;
    }
    public final Object next() {
      if (hasNext())
        return _ary[_last = _cursor++];
      throw new NoSuchElementException("cursor="+_cursor);
    }
    public final void remove() {
      throw new UnsupportedOperationException();
    }
  }
  public static class ArrayListIterator extends ArrayIterator
  implements ListIterator {
    /** @param ary an array or null. */
    public ArrayListIterator(Object[] ary) {
      super(ary);
    }
    /** @param ary an array or null. */
    public ArrayListIterator(Object[] ary, int index) {
      super(ary);
      _cursor = index;
      final int len = _ary != null ? _ary.length: 0;
      if (_cursor < 0 || _cursor > len)
        throw new IndexOutOfBoundsException("index="+index+" but len="+len);
    }
    public final boolean hasPrevious() {
      return _ary != null && _cursor > 0;
    }
    public final Object previous() {
      if (hasPrevious())
        return _ary[_last = --_cursor];
      throw new NoSuchElementException("cursor="+_cursor);
    }
    public final int nextIndex() {
      return _cursor;
    }
    public final int previousIndex() {
      return _cursor - 1;
    }
    public final void set(Object o) {
      if (_last < 0)
        throw new IllegalStateException("neither next nor previous have been called");
      _ary[_last] = o;
    }
    public final void add(Object o) {
      throw new UnsupportedOperationException();
    }
  }
  /** A collection that contains only one element.
   */
  public static final class OneCollection extends AbstractCollection {
    private final Object _one;
    public OneCollection(Object one) {
      _one = one;
    }
    public final int size() {
      return 1;
    }
    public Iterator iterator() {
      return new OneIterator(_one);
    }
  }
  /** An iterator that iterates one element.
   */
  public static final class OneIterator implements Iterator {
    private boolean _nomore;
    private final Object _one;
    public OneIterator(Object one) {
      _one = one;
    }
    public final boolean hasNext() {
      return !_nomore;
    }
    public final Object next() {
      if (_nomore)
        throw new NoSuchElementException();
      _nomore = true;
      return _one;
    }
    public final void remove() {
      throw new UnsupportedOperationException();
    }
  }
  /** An iterator that iterates thru an Enumeration.
   */
  public static final class EnumerationIterator implements Iterator {
    private final Enumeration _enm;
    /**
     * @param enm the enumeration. If null, it means empty.
     */
    public EnumerationIterator(Enumeration enm) {
      _enm = enm;
    }
    public final boolean hasNext() {
      return _enm != null && _enm.hasMoreElements();
    }
    public final Object next() {
      if (_enm == null)
        throw new NoSuchElementException();
      return _enm.nextElement();
    }
    public final void remove() {
      throw new UnsupportedOperationException();
    }
  };
  /** Empty iterator.
   */
  public static final Iterator EMPTY_ITERATOR =
    new Iterator() {
      public final boolean hasNext() {
        return false;
      }
      public final Object next() {
        throw new NoSuchElementException();
      }
      public final void remove() {
        throw new IllegalStateException();
      }
    };
  /** Empty enumeration.
   */
  public static final Enumeration EMPTY_ENUMERATION =
    new Enumeration() {
      public final boolean hasMoreElements() {
        return false;
      }
      public final Object nextElement() {
        throw new NoSuchElementException();
      }
    };
  /**
   * Returns the specified range of the specified collection into a new array.
     * The initial index of the range (from) must lie between zero
     * and col.size, inclusive. 
     * The final index of the range (to), which must be greater than or
     * equal to from.
     * 

The returned array will be "safe" in that no references to it are
     * maintained by this list.  (In other words, this method must allocate
     * a new array).  The caller is thus free to modify the returned array.
     *
     * 

This method acts as bridge between array-based and collection-based
     * APIs.
   * @param col the collection to be copied.
   * @param from the initial index of the range to be copied, inclusive.
     * @param to the final index of the range to be copied, exclusive.
     * @since 3.0.6
   */
  public static final Object[] toArray(Collection col, int from, int to) {
    int newLength = to - from;
    if (newLength < 0)
            throw new IllegalArgumentException(from + " > " + to);
    Object[] result = new Object[newLength];
        int i = 0, j = 0;
        for (Iterator it = col.iterator(); it.hasNext() && i < result.length;) {
          if (j++ < from) {
            it.next();
            continue;
          }
            result[i++] = it.next();
        }
    return result;
    }
  /** Adds all elements returned by the iterator to a collection.
   * @param iter the iterator; null is OK
   * @return the number element being added
   */
  public static final int addAll(Collection col, Iterator iter) {
    int cnt = 0;
    if (iter != null)
      for (; iter.hasNext(); ++cnt)
        col.add(iter.next());
    return cnt;
  }
  /** Adds all elements returned by the enumerator to a collection.
   * @param enm the enumeration; null is OK
   * @return the number element being added
   */
  public static final int addAll(Collection col, Enumeration enm) {
    int cnt = 0;
    if (enm != null)
      for (; enm.hasMoreElements(); ++cnt)
        col.add(enm.nextElement());
    return cnt;
  }
  /** Adds all elements of an array to a collection.
   * @param ary the array; null is OK
   * @return the number element being added
   */
  public static final int addAll(Collection col, Object[] ary) {
    int cnt = 0;
    if (ary != null)
      for (; cnt < ary.length; ++cnt)
        col.add(ary[cnt]);
    return cnt;
  }
  /** Tests whether two sets has any intersection.
   */
  public static final boolean isIntersected(Set a, Set b) {
    final int sza = a != null ? a.size(): 0;
    final int szb = b != null ? b.size(): 0;
    if (sza == 0 || szb == 0)
      return false;
    final Set large, small;
    if (sza > szb) {
      large = a;
      small = b;
    } else {
      large = b;
      small = a;
    }
    for (final Iterator it = small.iterator(); it.hasNext();)
      if (large.contains(it.next()))
        return true;
    return false;
  }
 
  /**
   * Based on the given collection type of Object, return an iterator. The
   * Collection type of object can be Collection, Map (return the entry), or
   * Array.
   */
  public static final Iterator iterator(Object obj) {
    if (obj instanceof Object[]) {
      return new ArrayIterator((Object[])obj);
    } else if (obj instanceof Collection) {
      return ((Collection)obj).iterator();
    } else if (obj instanceof Map) {
      return ((Map)obj).entrySet().iterator();
    }
    throw new IllegalArgumentException("obj must be a Collection, a Map, or an Object array. obj: "+obj);
  }
}