collections.java

kaffe是一个java虚拟机的源代码。里面包含了一些java例程和标准的java包。

/*
 * Java core library component.
 *
 * Copyright (c) 1999
 *	Archie L. Cobbs.  All rights reserved.
 * Copyright (c) 1999
 *	Transvirtual Technologies, Inc.  All rights reserved.
 *
 * See the file "license.terms" for information on usage and redistribution
 * of this file.
 *
 * Author: Archie L. Cobbs <[e-mail]>
 */

package java.util;

import java.io.Serializable;

public class Collections {

	// An empty Set
	public static final Set EMPTY_SET = new EmptySet();

	private static class EmptySet extends AbstractSet
			implements Serializable {
		public int size() {
			return 0;
		}
		public Iterator iterator() {
			return new Iterator() {
				public boolean hasNext() {
					return false;
				}
				public Object next() {
					throw new NoSuchElementException();
				}
				public void remove() {
					throw new IllegalStateException();
				}
			};
		}
	}

	// An empty List
	public static final List EMPTY_LIST = new EmptyList();

	private static class EmptyList extends AbstractList
			implements Serializable {
		public int size() {
			return 0;
		}
		public Object get(int index) {
			throw new IndexOutOfBoundsException();
		}
	}

	// An empty Map
	public static final Map EMPTY_MAP = new EmptyMap();

	private static class EmptyMap extends AbstractMap
			implements Serializable {
		public Set entrySet() {
			return EMPTY_SET;
		}
	}

	// This class is not instantiable
	private Collections() {
	}

	public static void sort(List list) {
		sort(list, Arrays.DEFAULT_COMPARATOR);
	}

	public static void sort(List list, Comparator c) {
		Object a[] = list.toArray();
		Arrays.sort(a, c);
		for (int index = a.length - 1; index >= 0; index--) {
			list.set(index, a[index]);
		}
	}

	public static int binarySearch(List list, Object key) {
		return binarySearch(list, key, Arrays.DEFAULT_COMPARATOR);
	}

	public static int binarySearch(List list, Object key, Comparator c) {
		if (list instanceof AbstractSequentialList) {
			Iterator i = list.iterator();
			int index;
			for (index = 0; i.hasNext(); index++) {
				if (c.compare(i.next(), key) == 0) {
					return index;
				}
			}
			return ~index;
		} else {
			return Arrays.binarySearch(list.toArray(), key, c);
		}
	}

	public static void reverse(List list) {
		ListIterator fwd = list.listIterator(0);
		ListIterator rev = list.listIterator(list.size());
		for (int count = list.size() / 2; count > 0; count--) {
			Object o1 = fwd.next();
			Object o2 = rev.previous();
			fwd.set(o2);
			rev.set(o1);
		}
	}

	public static void shuffle(List list) {
		shuffle(list, new Random());
	}

	public static void shuffle(List list, Random rnd) {
		ListIterator i = list.listIterator(list.size());
		for (int pos = list.size() - 1; pos > 1; pos--) {
			int pos2 = rnd.nextInt(pos + 1);
			Object o1 = i.previous();
			if (pos2 != pos) {
				Object o2 = list.get(pos2);
				list.set(pos2, o1);
				list.set(pos, o2);
			}
		}
	}

	public static void fill(List list, Object o) {
		for (ListIterator i = list.listIterator(); i.hasNext(); ) {
			i.next();
			i.set(o);
		}
	}

	public static void copy(List dst, List src) {
		if (dst.size() < src.size()) {
			throw new IndexOutOfBoundsException();
		}
		ListIterator di = dst.listIterator();
		ListIterator si = src.listIterator();
		while (si.hasNext()) {
			di.next();
			di.set(si.next());
		}
	}

	public static Object min(Collection coll) {
		return min(coll, Arrays.DEFAULT_COMPARATOR);
	}

	public static Object min(Collection coll, Comparator comp) {
		if (coll.size() == 0) {
			throw new NoSuchElementException();
		}
		Iterator i = coll.iterator();
		Object min = i.next();
		while (i.hasNext()) {
			Object next = i.next();
			if (comp.compare(next, min) < 0) {
				min = next;
			}
		}
		return min;
	}

	public static Object max(Collection coll) {
		return max(coll, Arrays.DEFAULT_COMPARATOR);
	}

	public static Object max(Collection coll, Comparator comp) {
		if (coll.size() == 0) {
			throw new NoSuchElementException();
		}
		Iterator i = coll.iterator();
		Object max = i.next();
		while (i.hasNext()) {
			Object next = i.next();
			if (comp.compare(next, max) > 0) {
				max = next;
			}
		}
		return max;
	}

	public static Collection unmodifiableCollection(Collection c) {
		return new UMCollection(c);
	}

	public static Set unmodifiableSet(Set s) {
		return new UMSet(s);
	}

	public static SortedSet unmodifiableSortedSet(SortedSet s) {
		return new UMSortedSet(s);
	}

	public static List unmodifiableList(List list) {
		return new UMList(list);
	}

	public static Map unmodifiableMap(Map m) {
		return new UMMap(m);
	}

	public static SortedMap unmodifiableSortedMap(SortedMap m) {
		return new UMSortedMap(m);
	}

	public static Collection synchronizedCollection(Collection c) {
		return new SyncCollection(c);
	}

	public static Set synchronizedSet(Set s) {
		return new SyncSet(s);
	}

	public static SortedSet synchronizedSortedSet(SortedSet s) {
		return new SyncSortedSet(s);
	}

	public static List synchronizedList(List l) {
		return new SyncList(l);
	}

	public static Map synchronizedMap(Map m) {
		return new SyncMap(m);
	}

	public static SortedMap synchronizedSortedMap(SortedMap m) {
		return new SyncSortedMap(m);
	}

	public static Set singleton(final Object o) {
		return new AbstractSet() {
			public int size() {
				return 1;
			}
			public Iterator iterator() {
				return nCopies(1, o).iterator();
			}
		};
	}

	public static List singletonList(Object o) {
		return new CopyList(1, o);
	}

	public static Map singletonMap(Object key, Object value) {
		HashMap map = new HashMap(1);
		map.put(key, value);
		return unmodifiableMap(map);
	}

	public static List nCopies(final int num, final Object o) {
		if (num < 0) {
			throw new IllegalArgumentException();
		}
		if (num == 0) {
			return EMPTY_LIST;
		}
		return new CopyList(num, o);
	}

	private static class CopyList extends AbstractList
			implements Serializable {
		private final Object o;
		private final int num;
		CopyList(int num, Object o) {
			this.num = num;
			this.o = o;
		}
		public int size() {
			return num;
		}
		public Object get(int index) {
			if (index < 0 || index >= num) {
				throw new IndexOutOfBoundsException();
			}
			return o;
		}
		public int indexOf(Object o2) {
			if (o == null ? o2 == null : o.equals(o2)) {
				return 0;
			}
			return -1;
		}
		public int lastIndexOf(Object o2) {
			if (o == null ? o2 == null : o.equals(o2)) {
				return num - 1;
			}
			return -1;
		}
		public ListIterator listIterator(int index) {
			if (index < 0 || index > num) {
				throw new IndexOutOfBoundsException();
			}
			return new AbstractListIterator(this, index);
		}
		public List subList(int fromIndex, int toIndex) {
			if (fromIndex < 0 || toIndex > num) {
				throw new IndexOutOfBoundsException();
			}
			if (fromIndex > toIndex) {
				throw new IllegalArgumentException();
			}
			return nCopies(toIndex - fromIndex, o);
		}
	}

	private static final Comparator REVERSE_COMPARATOR = new Comparator() {
		public int compare(Object o1, Object o2) {
			return -((Comparable)o1).compareTo(o2);
		}
	};

	public static Comparator reverseOrder() {
		return REVERSE_COMPARATOR;
	}

	public static Enumeration enumeration(final Collection c) {
		return new Enumeration() {
			private final Iterator i = c.iterator();
			public boolean hasMoreElements() {
				return i.hasNext();
			}
			public Object nextElement() {
				return i.next();
			}
		};
	}

	// Synchronized wrapper classes:

	private static class SyncCollection
			implements Collection, Serializable {
		protected final Collection c;

		SyncCollection(Collection c) {
			this.c = c;
		}
		public synchronized int size() {
			return c.size();
		}
		public synchronized boolean isEmpty() {
			return c.isEmpty();
		}
		public synchronized boolean contains(Object o) {
			return c.contains(o);
		}
		public synchronized Iterator iterator() {
			return c.iterator();
		}
		public synchronized Object[] toArray() {
			return c.toArray();
		}
		public synchronized Object[] toArray(Object[] a) {
			return c.toArray(a);
		}
		public synchronized boolean add(Object o) {
			return c.add(o);
		}
		public synchronized boolean remove(Object o) {
			return c.remove(o);
		}
		public synchronized boolean containsAll(Collection c2) {
			return c.containsAll(c2);
		}
		public synchronized boolean addAll(Collection c2) {
			return c.addAll(c2);
		}
		public synchronized boolean removeAll(Collection c2) {
			return c.removeAll(c2);
		}
		public synchronized boolean retainAll(Collection c2) {
			return c.retainAll(c2);
		}
		public synchronized void clear() {
			c.clear();
		}
		public synchronized boolean equals(Object o) {
			return c.equals(o);
		}
		public synchronized int hashCode() {
			return c.hashCode();
		}
	}

	private static class SyncSet extends SyncCollection
			implements Set {
		SyncSet(Set s) {