svn commit: r350181 [118/198] - in /incubator/harmony/enhanced/trunk/sandbox/contribs/ibm_core: ./ depends/ depends/files/ depends/jars/ depends/libs/ depends/libs/linux.IA32/ depends/libs/win.IA32/ depends/oss/ depends/oss/linux.IA32/ depends/oss/win....

[ge...@apache.org]

Added: incubator/harmony/enhanced/trunk/sandbox/contribs/ibm_core/java-src/luni/src/java/util/HashMap.java
URL: http://svn.apache.org/viewcvs/incubator/harmony/enhanced/trunk/sandbox/contribs/ibm_core/java-src/luni/src/java/util/HashMap.java?rev=350181&view=auto
==============================================================================
--- incubator/harmony/enhanced/trunk/sandbox/contribs/ibm_core/java-src/luni/src/java/util/HashMap.java (added)
+++ incubator/harmony/enhanced/trunk/sandbox/contribs/ibm_core/java-src/luni/src/java/util/HashMap.java Wed Nov 30 21:29:27 2005
@@ -0,0 +1,647 @@
+/* Copyright 1998, 2005 The Apache Software Foundation or its licensors, as applicable
+ * 
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ * 
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ * 
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package java.util;
+
+
+import java.io.IOException;
+import java.io.ObjectInputStream;
+import java.io.ObjectOutputStream;
+import java.io.ObjectStreamField;
+import java.io.Serializable;
+
+/**
+ * HashMap is an implementation of Map. All optional operations are supported,
+ * adding and removing. Keys and values can be any objects.
+ * 
+ */
+public class HashMap extends AbstractMap implements Map, Cloneable,
+		Serializable {
+	static final long serialVersionUID = 362498820763181265L;
+
+	transient int elementCount;
+
+	transient HashMapEntry[] elementData;
+
+	int loadFactor;
+
+	int threshold;
+
+	transient int modCount = 0;
+
+	private static final int DEFAULT_SIZE = 16;
+
+	static class HashMapEntry extends MapEntry {
+		HashMapEntry next;
+
+		HashMapEntry(Object theKey, Object theValue) {
+			super(theKey, theValue);
+		}
+
+		public Object clone() {
+			HashMapEntry entry = (HashMapEntry) super.clone();
+			if (next != null)
+				entry.next = (HashMapEntry) next.clone();
+			return entry;
+		}
+
+		public String toString() {
+			return key + "=" + value;
+		}
+	}
+
+	static class HashMapIterator implements Iterator {
+		private int position = 0;
+
+		int expectedModCount;
+
+		MapEntry.Type type;
+
+		boolean canRemove = false;
+
+		HashMapEntry entry;
+
+		HashMapEntry lastEntry;
+
+		HashMap associatedMap;
+
+		HashMapIterator(MapEntry.Type value, HashMap hm) {
+			associatedMap = hm;
+			type = value;
+			expectedModCount = hm.modCount;
+		}
+
+		public boolean hasNext() {
+			if (entry != null)
+				return true;
+			while (position < associatedMap.elementData.length) {
+				if (associatedMap.elementData[position] == null)
+					position++;
+				else
+					return true;
+			}
+			return false;
+		}
+
+		void checkConcurrentMod() throws ConcurrentModificationException {
+			if (expectedModCount != associatedMap.modCount)
+				throw new ConcurrentModificationException();
+		}
+
+		public Object next() {
+			checkConcurrentMod();
+			if (!hasNext())
+				throw new NoSuchElementException();
+
+			HashMapEntry result;
+			if (entry == null) {
+				result = lastEntry = associatedMap.elementData[position++];
+				entry = lastEntry.next;
+			} else {
+				if (lastEntry.next != entry)
+					lastEntry = lastEntry.next;
+				result = entry;
+				entry = entry.next;
+			}
+			canRemove = true;
+			return type.get(result);
+		}
+
+		public void remove() {
+			checkConcurrentMod();
+			if (!canRemove)
+				throw new IllegalStateException();
+
+			canRemove = false;
+			associatedMap.modCount++;
+			if (lastEntry.next == entry) {
+				while (associatedMap.elementData[--position] == null)
+					;
+				associatedMap.elementData[position] = associatedMap.elementData[position].next;
+				entry = null;
+			} else
+				lastEntry.next = entry;
+			associatedMap.elementCount--;
+			expectedModCount++;
+		}
+	}
+
+	static class HashMapEntrySet extends AbstractSet {
+		private HashMap associatedMap;
+
+		public HashMapEntrySet(HashMap hm) {
+			associatedMap = hm;
+		}
+
+		HashMap hashMap() {
+			return associatedMap;
+		}
+
+		public int size() {
+			return associatedMap.elementCount;
+		}
+
+		public void clear() {
+			associatedMap.clear();
+		}
+
+		public boolean remove(Object object) {
+			if (contains(object)) {
+				associatedMap.remove(((Map.Entry) object).getKey());
+				return true;
+			}
+			return false;
+		}
+
+		public boolean contains(Object object) {
+			if (object instanceof Map.Entry) {
+				HashMapEntry entry = associatedMap
+						.getEntry(((Map.Entry) object).getKey());
+				return object.equals(entry);
+			}
+			return false;
+		}
+
+		public Iterator iterator() {
+			return new HashMapIterator(new MapEntry.Type() {
+				public Object get(MapEntry entry) {
+					return entry;
+				}
+			}, associatedMap);
+		}
+	}
+
+	/**
+	 * Create a new element array
+	 * 
+	 * @param s
+	 * @return Reference to the element array
+	 */
+	HashMapEntry[] newElementArray(int s) {
+		return new HashMapEntry[s];
+	}
+
+	/**
+	 * Contructs a new empty instance of HashMap.
+	 * 
+	 */
+	public HashMap() {
+		this(DEFAULT_SIZE);
+	}
+
+	/**
+	 * Constructs a new instance of HashMap with the specified capacity.
+	 * 
+	 * @param capacity
+	 *            the initial capacity of this HashMap
+	 * 
+	 * @exception IllegalArgumentException
+	 *                when the capacity is less than zero
+	 */
+	public HashMap(int capacity) {
+		if (capacity >= 0) {
+			elementCount = 0;
+			elementData = newElementArray(capacity == 0 ? 1 : capacity);
+			loadFactor = 7500; // Default load factor of 0.75
+			computeMaxSize();
+		} else
+			throw new IllegalArgumentException();
+	}
+
+	/**
+	 * Constructs a new instance of HashMap with the specified capacity and load
+	 * factor.
+	 * 
+	 * 
+	 * @param capacity
+	 *            the initial capacity
+	 * @param loadFactor
+	 *            the initial load factor
+	 * 
+	 * @exception IllegalArgumentException
+	 *                when the capacity is less than zero or the load factor is
+	 *                less or equal to zero
+	 */
+	public HashMap(int capacity, float loadFactor) {
+		if (capacity >= 0 && loadFactor > 0) {
+			elementCount = 0;
+			elementData = newElementArray(capacity == 0 ? 1 : capacity);
+			this.loadFactor = (int) (loadFactor * 10000);
+			computeMaxSize();
+		} else
+			throw new IllegalArgumentException();
+	}
+
+	/**
+	 * Constructs a new instance of HashMap containing the mappings from the
+	 * specified Map.
+	 * 
+	 * @param map
+	 *            the mappings to add
+	 */
+	public HashMap(Map map) {
+		this(map.size() < 6 ? 11 : map.size() * 2);
+		putAll(map);
+	}
+
+	/**
+	 * Removes all mappings from this HashMap, leaving it empty.
+	 * 
+	 * @see #isEmpty
+	 * @see #size
+	 */
+	public void clear() {
+		if (elementCount > 0) {
+			elementCount = 0;
+			Arrays.fill(elementData, null);
+			modCount++;
+		}
+	}
+
+	/**
+	 * Answers a new HashMap with the same mappings and size as this HashMap.
+	 * 
+	 * @return a shallow copy of this HashMap
+	 * 
+	 * @see java.lang.Cloneable
+	 */
+	public Object clone() {
+		try {
+			HashMap map = (HashMap) super.clone();
+			map.elementData = newElementArray(elementData.length);
+			HashMapEntry entry;
+			for (int i = 0; i < elementData.length; i++) {
+				if ((entry = elementData[i]) != null)
+					map.elementData[i] = (HashMapEntry) entry.clone();
+			}
+			return map;
+		} catch (CloneNotSupportedException e) {
+			return null;
+		}
+	}
+
+	private void computeMaxSize() {
+		threshold = (int) ((long) elementData.length * loadFactor / 10000);
+	}
+
+	/**
+	 * Searches this HashMap for the specified key.
+	 * 
+	 * @param key
+	 *            the object to search for
+	 * @return true if <code>key</code> is a key of this HashMap, false
+	 *         otherwise
+	 */
+	public boolean containsKey(Object key) {
+		return getEntry(key) != null;
+	}
+
+	/**
+	 * Tests two keys for equality. This method just calls key.equals but can be
+	 * overridden.
+	 * 
+	 * @param k1
+	 *            first key to compare
+	 * @param k2
+	 *            second key to compare
+	 * @return true iff the keys are considered equal
+	 */
+	boolean keysEqual(Object k1, Object k2) {
+		return k1.equals(k2);
+	}
+
+	/**
+	 * Searches this HashMap for the specified value.
+	 * 
+	 * @param value
+	 *            the object to search for
+	 * @return true if <code>value</code> is a value of this HashMap, false
+	 *         otherwise
+	 */
+	public boolean containsValue(Object value) {
+		if (value != null) {
+			for (int i = elementData.length; --i >= 0;) {
+				HashMapEntry entry = elementData[i];
+				while (entry != null) {
+					if (value.equals(entry.value))
+						return true;
+					entry = entry.next;
+				}
+			}
+		} else {
+			for (int i = elementData.length; --i >= 0;) {
+				HashMapEntry entry = elementData[i];
+				while (entry != null) {
+					if (entry.value == null)
+						return true;
+					entry = entry.next;
+				}
+			}
+		}
+		return false;
+	}
+
+	/**
+	 * Answers a Set of the mappings contained in this HashMap. Each element in
+	 * the set is a Map.Entry. The set is backed by this HashMap so changes to
+	 * one are relected by the other. The set does not support adding.
+	 * 
+	 * @return a Set of the mappings
+	 */
+	public Set entrySet() {
+		return new HashMapEntrySet(this);
+	}
+
+	/**
+	 * Answers the value of the mapping with the specified key.
+	 * 
+	 * @param key
+	 *            the key
+	 * @return the value of the mapping with the specified key
+	 */
+	public Object get(Object key) {
+		HashMapEntry m = getEntry(key);
+		if (m != null) {
+			return m.value;
+		}
+		return null;
+	}
+
+	HashMapEntry getEntry(Object key) {
+		int index = getModuloHash(key);
+		return findEntry(key, index);
+	}
+
+	int getModuloHash(Object key) {
+		if (key == null)
+			return 0;
+		return (key.hashCode() & 0x7FFFFFFF) % elementData.length;
+	}
+
+	HashMapEntry findEntry(Object key, int index) {
+		HashMapEntry m;
+		m = elementData[index];
+		if (key != null) {
+			while (m != null && !keysEqual(key, m.key))
+				m = m.next;
+		} else {
+			while (m != null && m.key != null)
+				m = m.next;
+		}
+		return m;
+	}
+
+	/**
+	 * Answers if this HashMap has no elements, a size of zero.
+	 * 
+	 * @return true if this HashMap has no elements, false otherwise
+	 * 
+	 * @see #size
+	 */
+	public boolean isEmpty() {
+		return elementCount == 0;
+	}
+
+	/**
+	 * Answers a Set of the keys contained in this HashMap. The set is backed by
+	 * this HashMap so changes to one are relected by the other. The set does
+	 * not support adding.
+	 * 
+	 * @return a Set of the keys
+	 */
+	public Set keySet() {
+		if (keySet == null) {
+			keySet = new AbstractSet() {
+				public boolean contains(Object object) {
+					return containsKey(object);
+				}
+
+				public int size() {
+					return HashMap.this.size();
+				}
+
+				public void clear() {
+					HashMap.this.clear();
+				}
+
+				public boolean remove(Object key) {
+					if (containsKey(key)) {
+						HashMap.this.remove(key);
+						return true;
+					}
+					return false;
+				}
+
+				public Iterator iterator() {
+					return new HashMapIterator(new MapEntry.Type() {
+						public Object get(MapEntry entry) {
+							return entry.key;
+						}
+					}, HashMap.this);
+				}
+			};
+		}
+		return keySet;
+	}
+
+	/**
+	 * Maps the specified key to the specified value.
+	 * 
+	 * @param key
+	 *            the key
+	 * @param value
+	 *            the value
+	 * @return the value of any previous mapping with the specified key or null
+	 *         if there was no mapping
+	 */
+	public Object put(Object key, Object value) {
+		int index = getModuloHash(key);
+		HashMapEntry entry = findEntry(key, index);
+
+		if (entry == null) {
+			modCount++;
+			if (++elementCount > threshold) {
+				rehash();
+				index = key == null ? 0 : (key.hashCode() & 0x7FFFFFFF)
+						% elementData.length;
+			}
+			entry = createEntry(key, index, null);
+		}
+		Object result = entry.value;
+		entry.value = value;
+		return result;
+	}
+
+	HashMapEntry createEntry(Object key, int index, Object value) {
+		HashMapEntry entry = new HashMapEntry(key, value);
+		entry.next = elementData[index];
+		elementData[index] = entry;
+		return entry;
+	}
+
+	/**
+	 * Copies every mapping in the specified Map to this HashMap.
+	 * 
+	 * @param map
+	 *            the Map to copy mappings from
+	 */
+	public void putAll(Map map) {
+		super.putAll(map);
+	}
+
+	void rehash() {
+		int length = elementData.length << 1;
+		if (length == 0)
+			length = 1;
+		HashMapEntry[] newData = newElementArray(length);
+		for (int i = 0; i < elementData.length; i++) {
+			HashMapEntry entry = elementData[i];
+			while (entry != null) {
+				Object key = entry.key;
+				int index = key == null ? 0 : (key.hashCode() & 0x7FFFFFFF)
+						% length;
+				HashMapEntry next = entry.next;
+				entry.next = newData[index];
+				newData[index] = entry;
+				entry = next;
+			}
+		}
+		elementData = newData;
+		computeMaxSize();
+	}
+
+	/**
+	 * Removes a mapping with the specified key from this HashMap.
+	 * 
+	 * @param key
+	 *            the key of the mapping to remove
+	 * @return the value of the removed mapping or null if key is not a key in
+	 *         this HashMap
+	 */
+	public Object remove(Object key) {
+		HashMapEntry entry = removeEntry(key);
+		if (entry != null) {
+			return entry.value;
+		}
+		return null;
+	}
+
+	HashMapEntry removeEntry(Object key) {
+		int index = 0;
+		HashMapEntry entry;
+		HashMapEntry last = null;
+		if (key != null) {
+			index = (key.hashCode() & 0x7FFFFFFF) % elementData.length;
+			entry = elementData[index];
+			while (entry != null && !keysEqual(key, entry.key)) {
+				last = entry;
+				entry = entry.next;
+			}
+		} else {
+			entry = elementData[0];
+			while (entry != null && entry.key != null) {
+				last = entry;
+				entry = entry.next;
+			}
+		}
+		if (entry == null)
+			return null;
+		if (last == null)
+			elementData[index] = entry.next;
+		else
+			last.next = entry.next;
+		modCount++;
+		elementCount--;
+		return entry;
+	}
+
+	/**
+	 * Answers the number of mappings in this HashMap.
+	 * 
+	 * @return the number of mappings in this HashMap
+	 */
+	public int size() {
+		return elementCount;
+	}
+
+	/**
+	 * Answers a Collection of the values contained in this HashMap. The
+	 * collection is backed by this HashMap so changes to one are relected by
+	 * the other. The collection does not support adding.
+	 * 
+	 * @return a Collection of the values
+	 */
+	public Collection values() {
+		if (valuesCollection == null) {
+			valuesCollection = new AbstractCollection() {
+				public boolean contains(Object object) {
+					return containsValue(object);
+				}
+
+				public int size() {
+					return HashMap.this.size();
+				}
+
+				public void clear() {
+					HashMap.this.clear();
+				}
+
+				public Iterator iterator() {
+					return new HashMapIterator(new MapEntry.Type() {
+						public Object get(MapEntry entry) {
+							return entry.value;
+						}
+					}, HashMap.this);
+				}
+			};
+		}
+		return valuesCollection;
+	}
+
+	private static final ObjectStreamField[] serialPersistentFields = {
+			new ObjectStreamField("loadFactor", Float.TYPE),
+			new ObjectStreamField("threshold", Integer.TYPE) };
+
+	private void writeObject(ObjectOutputStream stream) throws IOException {
+		ObjectOutputStream.PutField fields = stream.putFields();
+		fields.put("loadFactor", (float) loadFactor / 10000);
+		fields.put("threshold", threshold);
+		stream.writeFields();
+		stream.writeInt(elementData.length);
+		stream.writeInt(elementCount);
+		Iterator iterator = entrySet().iterator();
+		while (iterator.hasNext()) {
+			HashMapEntry entry = (HashMapEntry) iterator.next();
+			stream.writeObject(entry.key);
+			stream.writeObject(entry.value);
+			entry = entry.next;
+		}
+	}
+
+	private void readObject(ObjectInputStream stream) throws IOException,
+			ClassNotFoundException {
+		ObjectInputStream.GetField fields = stream.readFields();
+		loadFactor = (int) (fields.get("loadFactor", 0.75f) * 10000);
+		threshold = fields.get("threshold", 0);
+		int length = stream.readInt();
+		elementData = new HashMapEntry[length];
+		elementCount = stream.readInt();
+		for (int i = elementCount; --i >= 0;) {
+			Object key = stream.readObject();
+			int index = (key.hashCode() & 0x7FFFFFFF) % length;
+			createEntry(key, index, stream.readObject());
+		}
+	}
+}

Added: incubator/harmony/enhanced/trunk/sandbox/contribs/ibm_core/java-src/luni/src/java/util/HashSet.java
URL: http://svn.apache.org/viewcvs/incubator/harmony/enhanced/trunk/sandbox/contribs/ibm_core/java-src/luni/src/java/util/HashSet.java?rev=350181&view=auto
==============================================================================
--- incubator/harmony/enhanced/trunk/sandbox/contribs/ibm_core/java-src/luni/src/java/util/HashSet.java (added)
+++ incubator/harmony/enhanced/trunk/sandbox/contribs/ibm_core/java-src/luni/src/java/util/HashSet.java Wed Nov 30 21:29:27 2005
@@ -0,0 +1,206 @@
+/* Copyright 1998, 2005 The Apache Software Foundation or its licensors, as applicable
+ * 
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ * 
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ * 
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package java.util;
+
+
+import java.io.IOException;
+import java.io.ObjectInputStream;
+import java.io.ObjectOutputStream;
+import java.io.Serializable;
+
+/**
+ * HashSet is an implementation of Set. All optional operations are supported,
+ * adding and removing. The elements can be any objects.
+ */
+public class HashSet extends AbstractSet implements Set, Cloneable,
+		Serializable {
+
+	static final long serialVersionUID = -5024744406713321676L;
+
+	transient HashMap backingMap;
+
+	/**
+	 * Contructs a new empty instance of HashSet.
+	 */
+	public HashSet() {
+		this(new HashMap());
+	}
+
+	/**
+	 * Constructs a new instance of HashSet with the specified capacity.
+	 * 
+	 * @param capacity
+	 *            the initial capacity of this HashSet
+	 */
+	public HashSet(int capacity) {
+		this(new HashMap(capacity));
+	}
+
+	/**
+	 * Constructs a new instance of HashSet with the specified capacity and load
+	 * factor.
+	 * 
+	 * @param capacity
+	 *            the initial capacity
+	 * @param loadFactor
+	 *            the initial load factor
+	 */
+	public HashSet(int capacity, float loadFactor) {
+		this(new HashMap(capacity, loadFactor));
+	}
+
+	/**
+	 * Constructs a new instance of HashSet containing the unique elements in
+	 * the specified collection.
+	 * 
+	 * @param collection
+	 *            the collection of elements to add
+	 */
+	public HashSet(Collection collection) {
+		this(new HashMap(collection.size() < 6 ? 11 : collection.size() * 2));
+		Iterator it = collection.iterator();
+		while (it.hasNext())
+			add(it.next());
+	}
+
+	HashSet(HashMap backingMap) {
+		this.backingMap = backingMap;
+	}
+
+	/**
+	 * Adds the specified object to this HashSet.
+	 * 
+	 * @param object
+	 *            the object to add
+	 * @return true when this HashSet did not already contain the object, false
+	 *         otherwise
+	 */
+	public boolean add(Object object) {
+		return backingMap.put(object, this) == null;
+	}
+
+	/**
+	 * Removes all elements from this HashSet, leaving it empty.
+	 * 
+	 * @see #isEmpty
+	 * @see #size
+	 */
+	public void clear() {
+		backingMap.clear();
+	}
+
+	/**
+	 * Answers a new HashSet with the same elements and size as this HashSet.
+	 * 
+	 * @return a shallow copy of this HashSet
+	 * 
+	 * @see java.lang.Cloneable
+	 */
+	public Object clone() {
+		try {
+			HashSet clone = (HashSet) super.clone();
+			clone.backingMap = (HashMap) backingMap.clone();
+			return clone;
+		} catch (CloneNotSupportedException e) {
+			return null;
+		}
+	}
+
+	/**
+	 * Searches this HashSet for the specified object.
+	 * 
+	 * @param object
+	 *            the object to search for
+	 * @return true if <code>object</code> is an element of this HashSet,
+	 *         false otherwise
+	 */
+	public boolean contains(Object object) {
+		return backingMap.containsKey(object);
+	}
+
+	/**
+	 * Answers if this HashSet has no elements, a size of zero.
+	 * 
+	 * @return true if this HashSet has no elements, false otherwise
+	 * 
+	 * @see #size
+	 */
+	public boolean isEmpty() {
+		return backingMap.isEmpty();
+	}
+
+	/**
+	 * Answers an Iterator on the elements of this HashSet.
+	 * 
+	 * @return an Iterator on the elements of this HashSet
+	 * 
+	 * @see Iterator
+	 */
+	public Iterator iterator() {
+		return backingMap.keySet().iterator();
+	}
+
+	/**
+	 * Removes an occurrence of the specified object from this HashSet.
+	 * 
+	 * @param object
+	 *            the object to remove
+	 * @return true if this HashSet is modified, false otherwise
+	 */
+	public boolean remove(Object object) {
+		return backingMap.remove(object) != null;
+	}
+
+	/**
+	 * Answers the number of elements in this HashSet.
+	 * 
+	 * @return the number of elements in this HashSet
+	 */
+	public int size() {
+		return backingMap.size();
+	}
+
+	private void writeObject(ObjectOutputStream stream) throws IOException {
+		stream.defaultWriteObject();
+		stream.writeInt(backingMap.elementData.length);
+		stream.writeFloat((float) backingMap.loadFactor / 10000);
+		stream.writeInt(backingMap.elementCount);
+		for (int i = backingMap.elementData.length; --i >= 0;) {
+			HashMap.HashMapEntry entry = backingMap.elementData[i];
+			while (entry != null) {
+				stream.writeObject(entry.key);
+				entry = entry.next;
+			}
+		}
+	}
+
+	private void readObject(ObjectInputStream stream) throws IOException,
+			ClassNotFoundException {
+		stream.defaultReadObject();
+		int length = stream.readInt();
+		float loadFactor = stream.readFloat();
+		backingMap = createBackingMap(length, loadFactor);
+		int elementCount = stream.readInt();
+		for (int i = elementCount; --i >= 0;) {
+			Object key = stream.readObject();
+			backingMap.put(key, this);
+		}
+	}
+
+	HashMap createBackingMap(int capacity, float loadFactor) {
+		return new HashMap(capacity, loadFactor);
+	}
+}

Added: incubator/harmony/enhanced/trunk/sandbox/contribs/ibm_core/java-src/luni/src/java/util/Hashtable.java
URL: http://svn.apache.org/viewcvs/incubator/harmony/enhanced/trunk/sandbox/contribs/ibm_core/java-src/luni/src/java/util/Hashtable.java?rev=350181&view=auto
==============================================================================
--- incubator/harmony/enhanced/trunk/sandbox/contribs/ibm_core/java-src/luni/src/java/util/Hashtable.java (added)
+++ incubator/harmony/enhanced/trunk/sandbox/contribs/ibm_core/java-src/luni/src/java/util/Hashtable.java Wed Nov 30 21:29:27 2005
@@ -0,0 +1,832 @@
+/* Copyright 1998, 2005 The Apache Software Foundation or its licensors, as applicable
+ * 
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ * 
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ * 
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package java.util;
+
+
+import java.io.IOException;
+import java.io.ObjectInputStream;
+import java.io.ObjectOutputStream;
+import java.io.Serializable;
+
+/**
+ * Hashtable associates keys with values. Keys and values cannot be null. The
+ * size of the Hashtable is the number of key/value pairs it contains. The
+ * capacity is the number of key/value pairs the Hashtable can hold. The load
+ * factor is a float value which determines how full the Hashtable gets before
+ * expanding the capacity. If the load factor of the Hashtable is exceeded, the
+ * capacity is doubled.
+ * 
+ * @see Enumeration
+ * @see java.io.Serializable
+ * @see java.lang.Object#equals
+ * @see java.lang.Object#hashCode
+ */
+
+public class Hashtable extends Dictionary implements Map, Cloneable,
+		Serializable {
+
+	static final long serialVersionUID = 1421746759512286392L;
+
+	transient int elementCount;
+
+	transient HashtableEntry[] elementData;
+
+	private float loadFactor;
+
+	private int threshold;
+
+	transient int firstSlot = 0;
+
+	transient int lastSlot = -1;
+
+	transient int modCount = 0;
+
+	private static final Enumeration emptyEnumerator = new Hashtable(0)
+			.getEmptyEnumerator();
+
+	private static HashtableEntry newEntry(Object key, Object value, int hash) {
+		return new HashtableEntry(key, value);
+	}
+
+	private static class HashtableEntry extends MapEntry {
+		HashtableEntry next;
+
+		HashtableEntry(Object theKey, Object theValue) {
+			super(theKey, theValue);
+		}
+
+		public Object clone() {
+			HashtableEntry entry = (HashtableEntry) super.clone();
+			if (next != null)
+				entry.next = (HashtableEntry) next.clone();
+			return entry;
+		}
+
+		public Object setValue(Object object) {
+			if (object == null)
+				throw new NullPointerException();
+			Object result = value;
+			value = object;
+			return result;
+		}
+
+		public int getKeyHash() {
+			return key.hashCode();
+		}
+
+		public boolean equalsKey(Object aKey, int hash) {
+			return key.equals(aKey);
+		}
+
+		public String toString() {
+			return key + "=" + value;
+		}
+	}
+
+	private final class HashIterator implements Iterator {
+		private int position, expectedModCount;
+
+		private MapEntry.Type type;
+
+		private HashtableEntry lastEntry;
+
+		private int lastPosition;
+
+		private boolean canRemove = false;
+
+		HashIterator(MapEntry.Type value) {
+			type = value;
+			position = lastSlot;
+			expectedModCount = modCount;
+		}
+
+		public boolean hasNext() {
+			if (lastEntry != null && lastEntry.next != null) {
+				return true;
+			}
+			while (position >= firstSlot) {
+				if (elementData[position] == null)
+					position--;
+				else
+					return true;
+			}
+			return false;
+		}
+
+		public Object next() {
+			if (expectedModCount == modCount) {
+				if (lastEntry != null) {
+					lastEntry = lastEntry.next;
+				}
+				if (lastEntry == null) {
+					while (position >= firstSlot
+							&& (lastEntry = elementData[position]) == null) {
+						position--;
+					}
+					if (lastEntry != null) {
+						lastPosition = position;
+						// decrement the position so we don't find the same slot
+						// next time
+						position--;
+					}
+				}
+				if (lastEntry != null) {
+					canRemove = true;
+					return type.get(lastEntry);
+				}
+				throw new NoSuchElementException();
+			} else
+				throw new ConcurrentModificationException();
+		}
+
+		public void remove() {
+			if (expectedModCount == modCount) {
+				if (canRemove) {
+					canRemove = false;
+					synchronized (Hashtable.this) {
+						boolean removed = false;
+						HashtableEntry entry = elementData[lastPosition];
+						if (entry == lastEntry) {
+							elementData[lastPosition] = entry.next;
+							removed = true;
+						} else {
+							while (entry != null && entry.next != lastEntry) {
+								entry = entry.next;
+							}
+							if (entry != null) {
+								entry = lastEntry.next;
+								removed = true;
+							}
+						}
+						if (removed) {
+							modCount++;
+							elementCount--;
+							expectedModCount++;
+							return;
+						}
+						// the entry must have been (re)moved outside of the
+						// iterator
+						// but this condition wasn't caught by the modCount
+						// check
+						// throw ConcurrentModificationException() outside of
+						// synchronized block
+					}
+				} else
+					throw new IllegalStateException();
+			}
+			throw new ConcurrentModificationException();
+		}
+	}
+
+	private final class HashEnumerator implements Enumeration {
+		boolean key;
+
+		int start;
+
+		HashtableEntry entry;
+
+		HashEnumerator(boolean isKey) {
+			key = isKey;
+			start = lastSlot + 1;
+		}
+
+		public boolean hasMoreElements() {
+			if (entry != null)
+				return true;
+			while (--start >= firstSlot)
+				if (elementData[start] != null) {
+					entry = elementData[start];
+					return true;
+				}
+			return false;
+		}
+
+		public Object nextElement() {
+			if (hasMoreElements()) {
+				Object result = key ? entry.key : entry.value;
+				entry = entry.next;
+				return result;
+			} else
+				throw new NoSuchElementException();
+		}
+	}
+
+	/**
+	 * Constructs a new Hashtable using the default capacity and load factor.
+	 */
+	public Hashtable() {
+		this(11);
+	}
+
+	/**
+	 * Constructs a new Hashtable using the specified capacity and the default
+	 * load factor.
+	 * 
+	 * @param capacity
+	 *            the initial capacity
+	 */
+	public Hashtable(int capacity) {
+		if (capacity >= 0) {
+			elementCount = 0;
+			elementData = new HashtableEntry[capacity == 0 ? 1 : capacity];
+			firstSlot = elementData.length;
+			loadFactor = 0.75f;
+			computeMaxSize();
+		} else
+			throw new IllegalArgumentException();
+	}
+
+	/**
+	 * Constructs a new Hashtable using the specified capacity and load factor.
+	 * 
+	 * @param capacity
+	 *            the initial capacity
+	 * @param loadFactor
+	 *            the initial load factor
+	 */
+	public Hashtable(int capacity, float loadFactor) {
+		if (capacity >= 0 && loadFactor > 0) {
+			elementCount = 0;
+			firstSlot = capacity;
+			elementData = new HashtableEntry[capacity == 0 ? 1 : capacity];
+			this.loadFactor = loadFactor;
+			computeMaxSize();
+		} else
+			throw new IllegalArgumentException();
+	}
+
+	/**
+	 * Constructs a new instance of Hashtable containing the mappings from the
+	 * specified Map.
+	 * 
+	 * @param map
+	 *            the mappings to add
+	 */
+	public Hashtable(Map map) {
+		this(map.size() < 6 ? 11 : (map.size() * 4 / 3) + 11);
+		putAll(map);
+	}
+
+	private HashEnumerator getEmptyEnumerator() {
+		return new HashEnumerator(false);
+	}
+
+	/**
+	 * Removes all key/value pairs from this Hashtable, leaving the size zero
+	 * and the capacity unchanged.
+	 * 
+	 * @see #isEmpty
+	 * @see #size
+	 */
+	public synchronized void clear() {
+		elementCount = 0;
+		Arrays.fill(elementData, null);
+		modCount++;
+	}
+
+	/**
+	 * Answers a new Hashtable with the same key/value pairs, capacity and load
+	 * factor.
+	 * 
+	 * @return a shallow copy of this Hashtable
+	 * 
+	 * @see java.lang.Cloneable
+	 */
+	public synchronized Object clone() {
+		try {
+			Hashtable hashtable = (Hashtable) super.clone();
+			hashtable.elementData = (HashtableEntry[]) elementData.clone();
+			HashtableEntry entry;
+			for (int i = elementData.length; --i >= 0;)
+				if ((entry = elementData[i]) != null)
+					hashtable.elementData[i] = (HashtableEntry) entry.clone();
+			return hashtable;
+		} catch (CloneNotSupportedException e) {
+			return null;
+		}
+	}
+
+	private void computeMaxSize() {
+		threshold = (int) (elementData.length * loadFactor);
+	}
+
+	/**
+	 * Answers if this Hashtable contains the specified object as the value of
+	 * at least one of the key/value pairs.
+	 * 
+	 * @param value
+	 *            the object to look for as a value in this Hashtable
+	 * @return true if object is a value in this Hashtable, false otherwise
+	 * 
+	 * @see #containsKey
+	 * @see java.lang.Object#equals
+	 */
+	public synchronized boolean contains(Object value) {
+		if (value == null) 
+			throw new NullPointerException();
+
+			for (int i = elementData.length; --i >= 0;) {
+				HashtableEntry entry = elementData[i];
+				while (entry != null) {
+					if (value.equals(entry.value))
+						return true;
+					entry = entry.next;
+				}
+			}
+			return false;
+	}
+
+	/**
+	 * Answers if this Hashtable contains the specified object as a key of one
+	 * of the key/value pairs.
+	 * 
+	 * @param key
+	 *            the object to look for as a key in this Hashtable
+	 * @return true if object is a key in this Hashtable, false otherwise
+	 * 
+	 * @see #contains
+	 * @see java.lang.Object#equals
+	 */
+	public synchronized boolean containsKey(Object key) {
+		return getEntry(key) != null;
+	}
+
+	/**
+	 * Searches this Hashtable for the specified value.
+	 * 
+	 * @param value
+	 *            the object to search for
+	 * @return true if <code>value</code> is a value of this Hashtable, false
+	 *         otherwise
+	 */
+	public boolean containsValue(Object value) {
+		return contains(value);
+	}
+
+	/**
+	 * Answers an Enumeration on the values of this Hashtable. The results of
+	 * the Enumeration may be affected if the contents of this Hashtable are
+	 * modified.
+	 * 
+	 * @return an Enumeration of the values of this Hashtable
+	 * 
+	 * @see #keys
+	 * @see #size
+	 * @see Enumeration
+	 */
+	public synchronized Enumeration elements() {
+		if (elementCount == 0)
+			return emptyEnumerator;
+		return new HashEnumerator(false);
+	}
+
+	/**
+	 * Answers a Set of the mappings contained in this Hashtable. Each element
+	 * in the set is a Map.Entry. The set is backed by this Hashtable so changes
+	 * to one are relected by the other. The set does not support adding.
+	 * 
+	 * @return a Set of the mappings
+	 */
+	public Set entrySet() {
+		return new Collections.SynchronizedSet(new AbstractSet() {
+			public int size() {
+				return elementCount;
+			}
+
+			public void clear() {
+				Hashtable.this.clear();
+			}
+
+			public boolean remove(Object object) {
+				if (contains(object)) {
+					Hashtable.this.remove(((Map.Entry) object).getKey());
+					return true;
+				}
+				return false;
+			}
+
+			public boolean contains(Object object) {
+				if (object instanceof Map.Entry) {
+					HashtableEntry entry = getEntry(((Map.Entry) object)
+							.getKey());
+					return object.equals(entry);
+				}
+				return false;
+			}
+
+			public Iterator iterator() {
+				return new HashIterator(new MapEntry.Type() {
+					public Object get(MapEntry entry) {
+						return entry;
+					}
+				});
+			}
+		}, this);
+	}
+
+	/**
+	 * Compares the specified object to this Hashtable and answer if they are
+	 * equal. The object must be an instance of Map and contain the same
+	 * key/value pairs.
+	 * 
+	 * @param object
+	 *            the object to compare with this object
+	 * @return true if the specified object is equal to this Map, false
+	 *         otherwise
+	 * 
+	 * @see #hashCode
+	 */
+	public synchronized boolean equals(Object object) {
+		if (this == object)
+			return true;
+		if (object instanceof Map) {
+			Map map = (Map) object;
+			if (size() != map.size())
+				return false;
+
+			Set objectSet = map.entrySet();
+			Iterator it = entrySet().iterator();
+			while (it.hasNext())
+				if (!objectSet.contains(it.next()))
+					return false;
+			return true;
+		}
+		return false;
+	}
+
+	/**
+	 * Answers the value associated with the specified key in this Hashtable.
+	 * 
+	 * @param key
+	 *            the key of the value returned
+	 * @return the value associated with the specified key, null if the
+	 *         specified key does not exist
+	 * 
+	 * @see #put
+	 */
+	public synchronized Object get(Object key) {
+		int hash = key.hashCode();
+		int index = (hash & 0x7FFFFFFF) % elementData.length;
+		HashtableEntry entry = elementData[index];
+		while (entry != null) {
+			if (entry.equalsKey(key, hash))
+				return entry.value;
+			entry = entry.next;
+		}
+		return null;
+	}
+
+	HashtableEntry getEntry(Object key) {
+		int hash = key.hashCode();
+		int index = (hash & 0x7FFFFFFF) % elementData.length;
+		HashtableEntry entry = elementData[index];
+		while (entry != null) {
+			if (entry.equalsKey(key, hash))
+				return entry;
+			entry = entry.next;
+		}
+		return null;
+	}
+
+	/**
+	 * Answers an integer hash code for the receiver. Objects which are equal
+	 * answer the same value for this method.
+	 * 
+	 * @return the receiver's hash
+	 * 
+	 * @see #equals
+	 */
+	public synchronized int hashCode() {
+		int result = 0;
+		Iterator it = entrySet().iterator();
+		while (it.hasNext()) {
+			Map.Entry entry = (Map.Entry) it.next();
+			Object key = entry.getKey();
+			Object value = entry.getValue();
+			int hash = (key != this ? key.hashCode() : 0)
+					^ (value != this ? (value != null ? value.hashCode() : 0)
+							: 0);
+			result += hash;
+		}
+		return result;
+	}
+
+	/**
+	 * Answers if this Hashtable has no key/value pairs, a size of zero.
+	 * 
+	 * @return true if this Hashtable has no key/value pairs, false otherwise
+	 * 
+	 * @see #size
+	 */
+	public synchronized boolean isEmpty() {
+		return elementCount == 0;
+	}
+
+	/**
+	 * Answers an Enumeration on the keys of this Hashtable. The results of the
+	 * Enumeration may be affected if the contents of this Hashtable are
+	 * modified.
+	 * 
+	 * @return an Enumeration of the keys of this Hashtable
+	 * 
+	 * @see #elements
+	 * @see #size
+	 * @see Enumeration
+	 */
+	public synchronized Enumeration keys() {
+		if (elementCount == 0)
+			return emptyEnumerator;
+		return new HashEnumerator(true);
+	}
+
+	/**
+	 * Answers a Set of the keys contained in this Hashtable. The set is backed
+	 * by this Hashtable so changes to one are relected by the other. The set
+	 * does not support adding.
+	 * 
+	 * @return a Set of the keys
+	 */
+	public Set keySet() {
+		return new Collections.SynchronizedSet(new AbstractSet() {
+			public boolean contains(Object object) {
+				return containsKey(object);
+			}
+
+			public int size() {
+				return elementCount;
+			}
+
+			public void clear() {
+				Hashtable.this.clear();
+			}
+
+			public boolean remove(Object key) {
+				if (containsKey(key)) {
+					Hashtable.this.remove(key);
+					return true;
+				}
+				return false;
+			}
+
+			public Iterator iterator() {
+				return new HashIterator(new MapEntry.Type() {
+					public Object get(MapEntry entry) {
+						return entry.key;
+					}
+				});
+			}
+		}, this);
+	}
+
+	/**
+	 * Associate the specified value with the specified key in this Hashtable.
+	 * If the key already exists, the old value is replaced. The key and value
+	 * cannot be null.
+	 * 
+	 * @param key
+	 *            the key to add
+	 * @param value
+	 *            the value to add
+	 * @return the old value associated with the specified key, null if the key
+	 *         did not exist
+	 * 
+	 * @see #elements
+	 * @see #get
+	 * @see #keys
+	 * @see java.lang.Object#equals
+	 */
+	public synchronized Object put(Object key, Object value) {
+		if (key != null && value != null) {
+			int hash = key.hashCode();
+			int index = (hash & 0x7FFFFFFF) % elementData.length;
+			HashtableEntry entry = elementData[index];
+			while (entry != null && !entry.equalsKey(key, hash))
+				entry = entry.next;
+			if (entry == null) {
+				modCount++;
+				if (++elementCount > threshold) {
+					rehash();
+					index = (hash & 0x7FFFFFFF) % elementData.length;
+				}
+				if (index < firstSlot)
+					firstSlot = index;
+				if (index > lastSlot)
+					lastSlot = index;
+				entry = newEntry(key, value, hash);
+				entry.next = elementData[index];
+				elementData[index] = entry;
+				return null;
+			}
+			Object result = entry.value;
+			entry.value = value;
+			return result;
+		} else
+			throw new NullPointerException();
+	}
+
+	/**
+	 * Copies every mapping in the specified Map to this Hashtable.
+	 * 
+	 * @param map
+	 *            the Map to copy mappings from
+	 */
+	public synchronized void putAll(Map map) {
+		Iterator it = map.entrySet().iterator();
+		while (it.hasNext()) {
+			Map.Entry entry = (Map.Entry) it.next();
+			put(entry.getKey(), entry.getValue());
+		}
+	}
+
+	/**
+	 * Increases the capacity of this Hashtable. This method is sent when the
+	 * size of this Hashtable exceeds the load factor.
+	 */
+	protected void rehash() {
+		int length = (elementData.length << 1) + 1;
+		if (length == 0)
+			length = 1;
+		int newFirst = length;
+		int newLast = -1;
+		HashtableEntry[] newData = new HashtableEntry[length];
+		for (int i = lastSlot + 1; --i >= firstSlot;) {
+			HashtableEntry entry = elementData[i];
+			while (entry != null) {
+				int index = (entry.getKeyHash() & 0x7FFFFFFF) % length;
+				if (index < newFirst)
+					newFirst = index;
+				if (index > newLast)
+					newLast = index;
+				HashtableEntry next = entry.next;
+				entry.next = newData[index];
+				newData[index] = entry;
+				entry = next;
+			}
+		}
+		firstSlot = newFirst;
+		lastSlot = newLast;
+		elementData = newData;
+		computeMaxSize();
+	}
+
+	/**
+	 * Remove the key/value pair with the specified key from this Hashtable.
+	 * 
+	 * @param key
+	 *            the key to remove
+	 * @return the value associated with the specified key, null if the
+	 *         specified key did not exist
+	 * 
+	 * @see #get
+	 * @see #put
+	 */
+	public synchronized Object remove(Object key) {
+		int hash = key.hashCode();
+		int index = (hash & 0x7FFFFFFF) % elementData.length;
+		HashtableEntry last = null;
+		HashtableEntry entry = elementData[index];
+		while (entry != null && !entry.equalsKey(key, hash)) {
+			last = entry;
+			entry = entry.next;
+		}
+		if (entry != null) {
+			modCount++;
+			if (last == null)
+				elementData[index] = entry.next;
+			else
+				last.next = entry.next;
+			elementCount--;
+			Object result = entry.value;
+			entry.value = null;
+			return result;
+		}
+		return null;
+	}
+
+	/**
+	 * Answers the number of key/value pairs in this Hashtable.
+	 * 
+	 * @return the number of key/value pairs in this Hashtable
+	 * 
+	 * @see #elements
+	 * @see #keys
+	 */
+	public synchronized int size() {
+		return elementCount;
+	}
+
+	/**
+	 * Answers the string representation of this Hashtable.
+	 * 
+	 * @return the string representation of this Hashtable
+	 */
+	public synchronized String toString() {
+		if (isEmpty())
+			return "{}";
+
+		StringBuffer buffer = new StringBuffer(size() * 28);
+		buffer.append('{');
+		for (int i = lastSlot; i >= firstSlot; i--) {
+			HashtableEntry entry = elementData[i];
+			while (entry != null) {
+				if (entry.key != this) {
+					buffer.append(entry.key);
+				} else {
+					buffer.append("(this Map)");
+				}
+				buffer.append('=');
+				if (entry.value != this) {
+					buffer.append(entry.value);
+				} else {
+					buffer.append("(this Map)");
+				}
+				buffer.append(", ");
+				entry = entry.next;
+			}
+		}
+		// Remove the last ", "
+		if (elementCount > 0)
+			buffer.setLength(buffer.length() - 2);
+		buffer.append('}');
+		return buffer.toString();
+	}
+
+	/**
+	 * Answers a Collection of the values contained in this Hashtable. The
+	 * collection is backed by this Hashtable so changes to one are reflected by
+	 * the other. The collection does not support adding.
+	 * 
+	 * @return a Collection of the values
+	 */
+	public Collection values() {
+		return new Collections.SynchronizedCollection(new AbstractCollection() {
+			public boolean contains(Object object) {
+				return Hashtable.this.contains(object);
+			}
+
+			public int size() {
+				return elementCount;
+			}
+
+			public void clear() {
+				Hashtable.this.clear();
+			}
+
+			public Iterator iterator() {
+				return new HashIterator(new MapEntry.Type() {
+					public Object get(MapEntry entry) {
+						return entry.value;
+					}
+				});
+			}
+		}, this);
+	}
+
+	private synchronized void writeObject(ObjectOutputStream stream)
+			throws IOException {
+		stream.defaultWriteObject();
+		stream.writeInt(elementData.length);
+		stream.writeInt(elementCount);
+		for (int i = elementData.length; --i >= 0;) {
+			HashtableEntry entry = elementData[i];
+			while (entry != null) {
+				stream.writeObject(entry.key);
+				stream.writeObject(entry.value);
+				entry = entry.next;
+			}
+		}
+	}
+
+	private void readObject(ObjectInputStream stream) throws IOException,
+			ClassNotFoundException {
+		stream.defaultReadObject();
+		int length = stream.readInt();
+		elementData = new HashtableEntry[length];
+		elementCount = stream.readInt();
+		for (int i = elementCount; --i >= 0;) {
+			Object key = stream.readObject();
+			int hash = key.hashCode();
+			int index = (hash & 0x7FFFFFFF) % length;
+			if (index < firstSlot)
+				firstSlot = index;
+			if (index > lastSlot)
+				lastSlot = index;
+			HashtableEntry entry = newEntry(key, stream.readObject(), hash);
+			entry.next = elementData[index];
+			elementData[index] = entry;
+		}
+	}
+}

Added: incubator/harmony/enhanced/trunk/sandbox/contribs/ibm_core/java-src/luni/src/java/util/IdentityHashMap.java
URL: http://svn.apache.org/viewcvs/incubator/harmony/enhanced/trunk/sandbox/contribs/ibm_core/java-src/luni/src/java/util/IdentityHashMap.java?rev=350181&view=auto
==============================================================================
--- incubator/harmony/enhanced/trunk/sandbox/contribs/ibm_core/java-src/luni/src/java/util/IdentityHashMap.java (added)
+++ incubator/harmony/enhanced/trunk/sandbox/contribs/ibm_core/java-src/luni/src/java/util/IdentityHashMap.java Wed Nov 30 21:29:27 2005
@@ -0,0 +1,657 @@
+/* Copyright 2004, 2005 The Apache Software Foundation or its licensors, as applicable
+ * 
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ * 
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ * 
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package java.util;
+
+
+import java.io.IOException;
+import java.io.ObjectInputStream;
+import java.io.ObjectOutputStream;
+import java.io.Serializable;
+
+/**
+ * IdentityHashMap
+ * 
+ * This is a variant on HashMap which tests equality by reference instead of by
+ * value. Basically, keys and values are compared for equality by checking if
+ * their references are equal rather than by calling the "equals" function.
+ * 
+ * IdentityHashMap uses open addressing (linear probing in particular) for
+ * collision resolution. This is different from HashMap which uses Chaining.
+ * 
+ * Like HashMap, IdentityHashMap is not thread safe, so access by multiple
+ * threads must be synchronized by an external mechanism such as
+ * Collections.synchronizedMap.
+ */
+public class IdentityHashMap extends AbstractMap implements Map, Serializable,
+		Cloneable {
+
+	static final long serialVersionUID = 8188218128353913216L;
+
+	/*
+	 * The internal data structure to hold key value pairs This array holds keys
+	 * and values alternatingly.
+	 */
+	transient Object[] elementData;
+
+	/* Actual number of key-value pairs. */
+	int size;
+
+	/*
+	 * maximum number of elements that can be put in this map before having to
+	 * rehash.
+	 */
+	transient int threshold;
+
+	/*
+	 * default treshold value that an IdentityHashMap created using the default
+	 * constructor would have.
+	 */
+	private static final int DEFAULT_MAX_SIZE = 21;
+
+	/* Default load factor of 0.75; */
+	private static final int loadFactor = 7500;
+
+	/*
+	 * modification count, to keep track of structural modificiations between
+	 * the Identityhashmap and the iterator
+	 */
+	transient int modCount = 0;
+
+	static class IdentityHashMapEntry extends MapEntry {
+		IdentityHashMapEntry(Object theKey, Object theValue) {
+			super(theKey, theValue);
+		}
+
+		public Object clone() {
+			return (IdentityHashMapEntry) super.clone();
+		}
+
+		public boolean equals(Object object) {
+			if (this == object)
+				return true;
+			if (object instanceof Map.Entry) {
+				Map.Entry entry = (Map.Entry) object;
+				return (key == entry.getKey()) && (value == entry.getValue());
+			}
+			return false;
+		}
+
+		public int hashCode() {
+			return System.identityHashCode(key)
+					^ System.identityHashCode(value);
+		}
+
+		public String toString() {
+			return key + "=" + value;
+		}
+	}
+
+	static class IdentityHashMapIterator implements Iterator {
+		private int position = 0; // the current position
+
+		// the position of the entry that was last returned from next()
+		private int lastPosition = 0;
+
+		IdentityHashMap associatedMap;
+
+		int expectedModCount;
+
+		MapEntry.Type type;
+
+		boolean canRemove = false;
+
+		IdentityHashMapIterator(MapEntry.Type value, IdentityHashMap hm) {
+			associatedMap = hm;
+			type = value;
+			expectedModCount = hm.modCount;
+		}
+
+		public boolean hasNext() {
+			while (position < associatedMap.elementData.length) {
+				// check if position is an empty spot, not just an entry with
+				// null key
+				if (associatedMap.elementData[position] == null
+						&& associatedMap.elementData[position + 1] == null)
+					position = position + 2;
+				else
+					return true;
+			}
+			return false;
+		}
+
+		void checkConcurrentMod() throws ConcurrentModificationException {
+			if (expectedModCount != associatedMap.modCount)
+				throw new ConcurrentModificationException();
+		}
+
+		public Object next() {
+			checkConcurrentMod();
+			if (!hasNext())
+				throw new NoSuchElementException();
+
+			IdentityHashMapEntry result = new IdentityHashMapEntry(
+					associatedMap.elementData[position],
+					associatedMap.elementData[position + 1]);
+			lastPosition = position;
+			position += 2;
+
+			canRemove = true;
+			return type.get(result);
+		}
+
+		public void remove() {
+			checkConcurrentMod();
+			if (!canRemove)
+				throw new IllegalStateException();
+
+			canRemove = false;
+			associatedMap.remove(associatedMap.elementData[lastPosition]);
+			expectedModCount++;
+		}
+	}
+
+	static class IdentityHashMapEntrySet extends AbstractSet {
+		private IdentityHashMap associatedMap;
+
+		public IdentityHashMapEntrySet(IdentityHashMap hm) {
+			associatedMap = hm;
+		}
+
+		IdentityHashMap hashMap() {
+			return associatedMap;
+		}
+
+		public int size() {
+			return associatedMap.size;
+		}
+
+		public void clear() {
+			associatedMap.clear();
+		}
+
+		public boolean remove(Object object) {
+			if (contains(object)) {
+				associatedMap.remove(((Map.Entry) object).getKey());
+				return true;
+			}
+			return false;
+		}
+
+		public boolean contains(Object object) {
+			if (object instanceof Map.Entry) {
+				IdentityHashMapEntry entry = associatedMap
+						.getEntry(((Map.Entry) object).getKey());
+				// we must call equals on the entry obtained from "this"
+				return entry != null && entry.equals(object);
+			}
+			return false;
+		}
+
+		public Iterator iterator() {
+			return new IdentityHashMapIterator(new MapEntry.Type() {
+				public Object get(MapEntry entry) {
+					return entry;
+				}
+			}, associatedMap);
+		}
+	}
+
+	/**
+	 * Create an IdentityHashMap with default maximum size
+	 */
+	public IdentityHashMap() {
+		this(DEFAULT_MAX_SIZE);
+	}
+
+	/**
+	 * Create an IdentityHashMap with the given maximum size parameter
+	 * 
+	 * @param maxSize
+	 *            The estimated maximum number of entries that will be put in
+	 *            this map.
+	 */
+	public IdentityHashMap(int maxSize) {
+		if (maxSize >= 0) {
+			this.size = 0;
+			threshold = getThreshold(maxSize);
+			elementData = newElementArray(computeElementArraySize());
+		} else
+			throw new IllegalArgumentException();
+	}
+
+	private int getThreshold(int maxSize) {
+		// assign the treshold to maxsize initially, this will change to a
+		// higher value if rehashing occurs.
+		return maxSize > 3 ? maxSize : 3;
+	}
+
+	private int computeElementArraySize() {
+		return (int) (((long) threshold * 10000) / loadFactor) * 2;
+	}
+
+	/**
+	 * Create a new element array
+	 * 
+	 * @param s
+	 *            the number of elements
+	 * @return Reference to the element array
+	 */
+	private Object[] newElementArray(int s) {
+		return new Object[s];
+	}
+
+	/**
+	 * Create an IdentityHashMap using the given Map as initial values.
+	 * 
+	 * @param map
+	 *            A map of (key,value) pairs to copy into the IdentityHashMap
+	 */
+	public IdentityHashMap(Map map) {
+		this(map.size() < 6 ? 11 : map.size() * 2);
+		putAll(map);
+	}
+
+	/**
+	 * Removes all elements from this Map, leaving it empty.
+	 * 
+	 * @exception UnsupportedOperationException
+	 *                when removing from this Map is not supported
+	 * 
+	 * @see #isEmpty
+	 * @see #size
+	 */
+	public void clear() {
+		size = 0;
+		for (int i = 0; i < elementData.length; i++) {
+			elementData[i] = null;
+		}
+	}
+
+	/**
+	 * Searches this Map for the specified key.
+	 * 
+	 * @param key
+	 *            the object to search for
+	 * @return true if <code>key</code> is a key of this Map, false otherwise
+	 */
+	public boolean containsKey(Object key) {
+		int index = findIndex(key, elementData);
+		if (key != null)
+			return elementData[index] == key;
+		// if key is null, we have to make sure
+		// what we found is not one of the empty spots
+		return (elementData[index] == null && elementData[index + 1] != null);
+
+	}
+
+	/**
+	 * Searches this Map for the specified value.
+	 * 
+	 * 
+	 * @param value
+	 *            the object to search for
+	 * @return true if <code>value</code> is a value of this Map, false
+	 *         otherwise
+	 */
+	public boolean containsValue(Object value) {
+		for (int i = 1; i < elementData.length; i = i + 2) {
+			if (elementData[i] == value) {
+				if (value != null)
+					return true;
+				// if value is null, we have to make sure what we found is
+				// not one of the empty spots
+				if (elementData[i - 1] != null)
+					return true;
+			}
+		}
+		return false;
+	}
+
+	/**
+	 * Answers the value of the mapping with the specified key.
+	 * 
+	 * @param key
+	 *            the key
+	 * @return the value of the mapping with the specified key
+	 */
+	public Object get(Object key) {
+		int index = findIndex(key, elementData);
+
+		if (elementData[index] == key)
+			return elementData[index + 1];
+		
+		return null;
+	}
+
+	private IdentityHashMapEntry getEntry(Object key) {
+		int index = findIndex(key, elementData);
+		if (elementData[index] == key)
+			return new IdentityHashMapEntry(key, elementData[index + 1]);
+		
+		return null;
+	}
+
+	/**
+	 * Returns the index where the key is found at, or the index of the next
+	 * empty spot if the key is not found in this table.
+	 */
+	private int findIndex(Object key, Object[] array) {
+		int length = array.length;
+		int index = getModuloHash(key, length);
+		int last = (index + length - 2) % length;
+		while (index != last) {
+			if (array[index] == key
+					|| (array[index] == null && array[index + 1] == null))
+				break;
+			index = (index + 2) % length;
+		}
+		return index;
+	}
+
+	private int getModuloHash(Object key, int length) {
+		return ((System.identityHashCode(key) & 0x7FFFFFFF) % (length / 2)) * 2;
+	}
+
+	/**
+	 * Maps the specified key to the specified value.
+	 * 
+	 * @param key
+	 *            the key
+	 * @param value
+	 *            the value
+	 * @return the value of any previous mapping with the specified key or null
+	 *         if there was no mapping
+	 */
+	public Object put(Object key, Object value) {
+		int index = findIndex(key, elementData);
+
+		// if the key doesn't exist in the table
+		if (elementData[index] != key
+				|| (key == null && elementData[index + 1] == null)) {
+			// if key is null, and value is null
+			// this is one of the empty spots, there is not entry for key "null"
+			// in the table
+			modCount++;
+			if (++size > threshold) {
+				rehash();
+				index = findIndex(key, elementData);
+			}
+
+			// insert the key and assign the value to null initially
+			elementData[index] = key;
+			elementData[index + 1] = null;
+		}
+
+		// insert value to where it needs to go, return the old value
+		Object result = elementData[index + 1];
+		elementData[index + 1] = value;
+		return result;
+	}
+
+	private void rehash() {
+		int newlength = elementData.length << 1;
+		if (newlength == 0)
+			newlength = 1;
+		Object[] newData = newElementArray(newlength);
+		for (int i = 0; i < elementData.length; i = i + 2) {
+			Object key = elementData[i];
+			if (key != null || (key == null && elementData[i + 1] != null)) { // if
+				// not
+				// empty
+				int index = findIndex(key, newData);
+				newData[index] = key;
+				newData[index + 1] = elementData[i + 1];
+			}
+		}
+		elementData = newData;
+		computeMaxSize();
+	}
+
+	private void computeMaxSize() {
+		threshold = (int) ((long) (elementData.length / 2) * loadFactor / 10000);
+	}
+
+	/**
+	 * Removes a mapping with the specified key from this IdentityHashMap.
+	 * 
+	 * @param key
+	 *            the key of the mapping to remove
+	 * @return the value of the removed mapping, or null if key is not a key in
+	 *         this Map
+	 */
+	public Object remove(Object key) {
+		boolean hashedOk;
+
+		int index, next, hash;
+		Object result, object;
+		index = next = findIndex(key, elementData);
+
+		// store the value for this key
+		result = elementData[index + 1];
+		if (result == null && key == null)
+			return null;
+
+		// shift the following elements up if needed
+		// until we reach an empty spot
+		int length = elementData.length;
+		while (true) {
+			next = (next + 2) % length;
+			object = elementData[next];
+			if (object == null && elementData[next + 1] == null)
+				break;
+
+			hash = getModuloHash(object, length);
+			hashedOk = hash > index;
+			if (next < index) {
+				hashedOk = hashedOk || (hash <= next);
+			} else {
+				hashedOk = hashedOk && (hash <= next);
+			}
+			if (!hashedOk) {
+				elementData[index] = object;
+				elementData[index + 1] = elementData[next];
+				index = next;
+			}
+		}
+
+		size--;
+		modCount++;
+
+		// clear both the key and the value
+		elementData[index] = null;
+		elementData[index + 1] = null;
+
+		return result;
+	}
+
+	/**
+	 * Answers a Set of the mappings contained in this IdentityHashMap. Each
+	 * element in the set is a Map.Entry. The set is backed by this Map so
+	 * changes to one are relected by the other. The set does not support
+	 * adding.
+	 * 
+	 * @return a Set of the mappings
+	 */
+	public Set entrySet() {
+		return new IdentityHashMapEntrySet(this);
+	}
+
+	/**
+	 * Answers a Set of the keys contained in this IdentityHashMap. The set is
+	 * backed by this IdentityHashMap so changes to one are relected by the
+	 * other. The set does not support adding.
+	 * 
+	 * @return a Set of the keys
+	 */
+	public Set keySet() {
+		if (keySet == null) {
+			keySet = new AbstractSet() {
+				public boolean contains(Object object) {
+					return containsKey(object);
+				}
+
+				public int size() {
+					return IdentityHashMap.this.size();
+				}
+
+				public void clear() {
+					IdentityHashMap.this.clear();
+				}
+
+				public boolean remove(Object key) {
+					if (containsKey(key)) {
+						IdentityHashMap.this.remove(key);
+						return true;
+					}
+					return false;
+				}
+
+				public Iterator iterator() {
+					return new IdentityHashMapIterator(new MapEntry.Type() {
+						public Object get(MapEntry entry) {
+							return entry.key;
+						}
+					}, IdentityHashMap.this);
+				}
+			};
+		}
+		return keySet;
+	}
+
+	/**
+	 * Answers a Collection of the values contained in this IdentityHashMap. The
+	 * collection is backed by this IdentityHashMap so changes to one are
+	 * relected by the other. The collection does not support adding.
+	 * 
+	 * @return a Collection of the values
+	 */
+	public Collection values() {
+		if (valuesCollection == null) {
+			valuesCollection = new AbstractCollection() {
+				public boolean contains(Object object) {
+					return containsValue(object);
+				}
+
+				public int size() {
+					return IdentityHashMap.this.size();
+				}
+
+				public void clear() {
+					IdentityHashMap.this.clear();
+				}
+
+				public Iterator iterator() {
+					return new IdentityHashMapIterator(new MapEntry.Type() {
+						public Object get(MapEntry entry) {
+							return entry.value;
+						}
+					}, IdentityHashMap.this);
+				}
+			};
+		}
+		return valuesCollection;
+	}
+
+	/**
+	 * Compares this map with other objects. This map is equal to another map is
+	 * it represents the same set of mappings. With this map, two mappings are
+	 * the same if both the key and the value are equal by reference.
+	 * 
+	 * When compared with a map that is not an IdentityHashMap, the equals
+	 * method is not necessarily symmetric (a.equals(b) implies b.equals(a)) nor
+	 * transitive (a.equals(b) and b.equals(c) implies a.equals(c)).
+	 * 
+	 * @return whether the argument object is equal to this object
+	 */
+	public boolean equals(Object object) {
+		// we need to override the equals method in AbstractMap because
+		// AbstractMap.equals will call ((Map) object).entrySet().contains() to
+		// determine equality of the entries, so it will defer to the argument
+		// for comparison, meaning that reference-based comparison will not take
+		// place. We must ensure that all comparison is implemented by methods
+		// in this class (or in one of our inner classes) for reference-based
+		// comparison to take place.
+		if (this == object)
+			return true;
+		if (object instanceof Map) {
+			Map map = (Map) object;
+			if (size() != map.size())
+				return false;
+
+			Set set = entrySet();
+			// ensure we use the equals method of the set created by "this"
+			return set.equals(map.entrySet());
+		}
+		return false;
+	}
+
+	/**
+	 * Answers a new IdentityHashMap with the same mappings and size as this
+	 * one.
+	 * 
+	 * @return a shallow copy of this IdentityHashMap
+	 * 
+	 * @see java.lang.Cloneable
+	 */
+	public Object clone() {
+		try {
+			return (IdentityHashMap) super.clone();
+		} catch (CloneNotSupportedException e) {
+			return null;
+		}
+	}
+
+	/**
+	 * Answers if this IdentityHashMap has no elements, a size of zero.
+	 * 
+	 * @return true if this IdentityHashMap has no elements, false otherwise
+	 * 
+	 * @see #size
+	 */
+	public boolean isEmpty() {
+		return size == 0;
+	}
+
+	/**
+	 * Answers the number of mappings in this IdentityHashMap.
+	 * 
+	 * @return the number of mappings in this IdentityHashMap
+	 */
+	public int size() {
+		return size;
+	}
+
+	private void writeObject(ObjectOutputStream stream) throws IOException {
+		stream.writeInt(size);
+		Iterator iterator = entrySet().iterator();
+		while (iterator.hasNext()) {
+			MapEntry entry = (MapEntry) iterator.next();
+			stream.writeObject(entry.key);
+			stream.writeObject(entry.value);
+		}
+	}
+
+	private void readObject(ObjectInputStream stream) throws IOException,
+			ClassNotFoundException {
+		int savedSize = stream.readInt();
+		threshold = getThreshold(DEFAULT_MAX_SIZE);
+		elementData = newElementArray(computeElementArraySize());
+		for (int i = savedSize; --i >= 0;) {
+			Object key = stream.readObject();
+			put(key, stream.readObject());
+		}
+	}
+}

Added: incubator/harmony/enhanced/trunk/sandbox/contribs/ibm_core/java-src/luni/src/java/util/Iterator.java
URL: http://svn.apache.org/viewcvs/incubator/harmony/enhanced/trunk/sandbox/contribs/ibm_core/java-src/luni/src/java/util/Iterator.java?rev=350181&view=auto
==============================================================================
--- incubator/harmony/enhanced/trunk/sandbox/contribs/ibm_core/java-src/luni/src/java/util/Iterator.java (added)
+++ incubator/harmony/enhanced/trunk/sandbox/contribs/ibm_core/java-src/luni/src/java/util/Iterator.java Wed Nov 30 21:29:27 2005
@@ -0,0 +1,57 @@
+/* Copyright 1998, 2002 The Apache Software Foundation or its licensors, as applicable
+ * 
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ * 
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ * 
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package java.util;
+
+
+/**
+ * An Iterator is used to sequence over a collection of objects.
+ */
+public interface Iterator {
+	/**
+	 * Answers if there are more elements to iterate.
+	 * 
+	 * @return true if there are more elements, false otherwise
+	 * 
+	 * @see #next
+	 */
+	public boolean hasNext();
+
+	/**
+	 * Answers the next object in the iteration.
+	 * 
+	 * @return the next object
+	 * 
+	 * @exception NoSuchElementException
+	 *                when there are no more elements
+	 * 
+	 * @see #hasNext
+	 */
+	public Object next();
+
+	/**
+	 * Removes the last object returned by <code>next</code> from the
+	 * collection.
+	 * 
+	 * @exception UnsupportedOperationException
+	 *                when removing is not supported by the collection being
+	 *                iterated
+	 * @exception IllegalStateException
+	 *                when <code>next</code> has not been called, or
+	 *                <code>remove</code> has already been called after the
+	 *                last call to <code>next</code>
+	 */
+	public void remove();
+}

Added: incubator/harmony/enhanced/trunk/sandbox/contribs/ibm_core/java-src/luni/src/java/util/LinkedHashMap.java
URL: http://svn.apache.org/viewcvs/incubator/harmony/enhanced/trunk/sandbox/contribs/ibm_core/java-src/luni/src/java/util/LinkedHashMap.java?rev=350181&view=auto
==============================================================================
--- incubator/harmony/enhanced/trunk/sandbox/contribs/ibm_core/java-src/luni/src/java/util/LinkedHashMap.java (added)
+++ incubator/harmony/enhanced/trunk/sandbox/contribs/ibm_core/java-src/luni/src/java/util/LinkedHashMap.java Wed Nov 30 21:29:27 2005
@@ -0,0 +1,508 @@
+/* Copyright 2004, 2005 The Apache Software Foundation or its licensors, as applicable
+ * 
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ * 
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ * 
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package java.util;
+
+
+/**
+ * LinkedHashMap
+ * 
+ */
+public class LinkedHashMap extends HashMap {
+	
+	static final long serialVersionUID = 3801124242820219131L;
+
+	private boolean accessOrder;
+
+	transient private LinkedHashMapEntry head, tail;
+
+	/**
+	 * Contructs a new empty instance of LinkedHashMap.
+	 */
+	public LinkedHashMap() {
+		super();
+		accessOrder = false;
+		head = null;
+	}
+
+	/**
+	 * Constructor with specified size.
+	 * 
+	 * @param s
+	 *            Size of LinkedHashMap required
+	 */
+	public LinkedHashMap(int s) {
+		super(s);
+		accessOrder = false;
+		head = null;
+	}
+
+	/**
+	 * Constructor with specified size and load factor.
+	 * 
+	 * @param s
+	 *            Size of LinkedHashMap required
+	 * @param lf
+	 *            Load factor
+	 */
+	public LinkedHashMap(int s, float lf) {
+		super(s, lf);
+		accessOrder = false;
+		head = null;
+		tail = null;
+	}
+
+	/**
+	 * Constructor with specified size, load factor and access order
+	 * 
+	 * @param s
+	 *            Size of LinkedHashmap required
+	 * @param lf
+	 *            Load factor
+	 * @param order
+	 *            If true indicates that traversal order should begin with most
+	 *            recently accessed
+	 */
+	public LinkedHashMap(int s, float lf, boolean order) {
+		super(s, lf);
+		accessOrder = order;
+		head = null;
+		tail = null;
+	}
+
+	/**
+	 * Constructor with input map
+	 * 
+	 * @param m
+	 *            Input map
+	 */
+	public LinkedHashMap(Map m) {
+		accessOrder = false;
+		head = null;
+		tail = null;
+		putAll(m);
+	}
+
+	static final class LinkedHashIterator extends HashMapIterator {
+		LinkedHashIterator(MapEntry.Type value, LinkedHashMap hm) {
+			super(value, hm);
+			entry = hm.head;
+		}
+
+		public boolean hasNext() {
+			return (entry != null);
+		}
+
+		public Object next() {
+			checkConcurrentMod();
+			if (!hasNext())
+				throw new NoSuchElementException();
+			Object result = type.get(entry);
+			lastEntry = entry;
+			entry = ((LinkedHashMapEntry) entry).chainForward;
+			canRemove = true;
+			return result;
+		}
+
+		public void remove() {
+			checkConcurrentMod();
+			if (!canRemove)
+				throw new IllegalStateException();
+
+			canRemove = false;
+			associatedMap.modCount++;
+
+			int index = associatedMap.getModuloHash(lastEntry.key);
+			LinkedHashMapEntry m = (LinkedHashMapEntry) associatedMap.elementData[index];
+			if (m == lastEntry) {
+				associatedMap.elementData[index] = lastEntry.next;
+			} else {
+				while (m.next != null) {
+					if (m.next == lastEntry)
+						break;
+					m = (LinkedHashMapEntry) m.next;
+				}
+				// assert m.next == entry
+				m.next = lastEntry.next;
+			}
+			LinkedHashMapEntry lhme = (LinkedHashMapEntry) lastEntry;
+			LinkedHashMapEntry p = lhme.chainBackward;
+			LinkedHashMapEntry n = lhme.chainForward;
+			LinkedHashMap lhm = (LinkedHashMap) associatedMap;
+			if (p != null) {
+				p.chainForward = n;
+				if (n != null)
+					n.chainBackward = p;
+				else
+					lhm.tail = p;
+			} else {
+				lhm.head = n;
+				if (n != null)
+					n.chainBackward = null;
+				else
+					lhm.tail = null;
+			}
+			associatedMap.elementCount--;
+			expectedModCount++;
+		}
+	}
+
+	static final class LinkedHashMapEntrySet extends HashMapEntrySet {
+		public LinkedHashMapEntrySet(LinkedHashMap lhm) {
+			super(lhm);
+		}
+
+		public Iterator iterator() {
+			return new LinkedHashIterator(new MapEntry.Type() {
+				public Object get(MapEntry entry) {
+					return entry;
+				}
+			}, (LinkedHashMap) hashMap());
+		}
+	}
+
+	static final class LinkedHashMapEntry extends HashMapEntry {
+		LinkedHashMapEntry chainForward, chainBackward;
+
+		LinkedHashMapEntry(Object theKey, Object theValue) {
+			super(theKey, theValue);
+			chainForward = null;
+			chainBackward = null;
+		}
+
+		public Object clone() {
+			LinkedHashMapEntry entry = (LinkedHashMapEntry) super.clone();
+			entry.chainBackward = chainBackward;
+			entry.chainForward = chainForward;
+			LinkedHashMapEntry lnext = (LinkedHashMapEntry) entry.next;
+			if (lnext != null)
+				entry.next = (LinkedHashMapEntry) lnext.clone();
+			return entry;
+		}
+	}
+
+	/**
+	 * Create a new element array
+	 * 
+	 * @param s
+	 * @return Reference to the element array
+	 */
+	HashMapEntry[] newElementArray(int s) {
+		return new LinkedHashMapEntry[s];
+	}
+
+	/**
+	 * Retrieve the map value corresponding to the given key.
+	 * 
+	 * @param key
+	 *            Key value
+	 * @return mapped value or null if the key is not in the map
+	 */
+	public Object get(Object key) {
+		LinkedHashMapEntry m = (LinkedHashMapEntry) getEntry(key);
+		if (m == null)
+			return null;
+		if (accessOrder && tail != m) {
+			LinkedHashMapEntry p = m.chainBackward;
+			LinkedHashMapEntry n = m.chainForward;
+			n.chainBackward = p;
+			if (p != null)
+				p.chainForward = n;
+			else
+				head = n;
+			m.chainForward = null;
+			m.chainBackward = tail;
+			tail.chainForward = m;
+			tail = m;
+		}
+		return m.value;
+	}
+
+	/*
+	 * @param key
+	 * @param index
+	 * @return
+	 */
+	HashMapEntry createEntry(Object key, int index, Object value) {
+		LinkedHashMapEntry m = new LinkedHashMapEntry(key, value);
+		m.next = elementData[index];
+		elementData[index] = m;
+		linkEntry(m);
+		return m;
+	}
+
+	/**
+	 * Set the mapped value for the given key to the given value.
+	 * 
+	 * @param key
+	 *            Key value
+	 * @param value
+	 *            New mapped value
+	 * @return The old value if the key was already in the map or null
+	 *         otherwise.
+	 */
+	public Object put(Object key, Object value) {
+		int index = getModuloHash(key);
+		LinkedHashMapEntry m = (LinkedHashMapEntry) findEntry(key, index);
+
+		if (m == null) {
+			modCount++;
+			// Check if we need to remove the oldest entry
+			// The check includes accessOrder since an accessOrder LinkedHashMap
+			// does not record
+			// the oldest member in 'head'.
+			if (++elementCount > threshold) {
+				rehash();
+				index = key == null ? 0 : (key.hashCode() & 0x7FFFFFFF)
+						% elementData.length;
+			}
+			m = (LinkedHashMapEntry) createEntry(key, index, null);
+		} else {
+			linkEntry(m);
+		}
+
+		Object result = m.value;
+		m.value = value;
+
+		if (removeEldestEntry(head))
+			remove(head.key);
+
+		return result;
+	}
+
+	/*
+	 * @param m
+	 */
+	void linkEntry(LinkedHashMapEntry m) {
+		if (tail == m) {
+			return;
+		}
+
+		if (head == null) {
+			// Check if the map is empty
+			head = tail = m;
+			return;
+		}
+
+		// we need to link the new entry into either the head or tail
+		// of the chain depending on if the LinkedHashMap is accessOrder or not
+		LinkedHashMapEntry p = m.chainBackward;
+		LinkedHashMapEntry n = m.chainForward;
+		if (p == null) {
+			if (n != null) {
+				// The entry must be the head but not the tail
+				if (accessOrder) {
+					head = n;
+					n.chainBackward = null;
+					m.chainBackward = tail;
+					m.chainForward = null;
+					tail.chainForward = m;
+					tail = m;
+				}
+			} else {
+				// This is a new entry
+				m.chainBackward = tail;
+				m.chainForward = null;
+				tail.chainForward = m;
+				tail = m;
+			}
+			return;
+		}
+
+		if (n == null) {
+			// The entry must be the tail so we can't get here
+			return;
+		}
+
+		// The entry is neither the head nor tail
+		if (accessOrder) {
+			p.chainForward = n;
+			n.chainBackward = p;
+			m.chainForward = null;
+			m.chainBackward = tail;
+			tail.chainForward = m;
+			tail = m;
+		}
+
+	}
+
+	/**
+	 * Put all entries from the given map into the LinkedHashMap
+	 * 
+	 * @param m
+	 *            Input map
+	 */
+	public void putAll(Map m) {
+		Iterator i = m.entrySet().iterator();
+		while (i.hasNext()) {
+			Map.Entry e = (MapEntry) i.next();
+			put(e.getKey(), e.getValue());
+		}
+	}
+
+	/**
+	 * Answers a Set of the mappings contained in this HashMap. Each element in
+	 * the set is a Map.Entry. The set is backed by this HashMap so changes to
+	 * one are relected by the other. The set does not support adding.
+	 * 
+	 * @return a Set of the mappings
+	 */
+	public Set entrySet() {
+		return new LinkedHashMapEntrySet(this);
+	}
+
+	/**
+	 * Answers a Set of the keys contained in this HashMap. The set is backed by
+	 * this HashMap so changes to one are relected by the other. The set does
+	 * not support adding.
+	 * 
+	 * @return a Set of the keys
+	 */
+	public Set keySet() {
+		if (keySet == null) {
+			keySet = new AbstractSet() {
+				public boolean contains(Object object) {
+					return containsKey(object);
+				}
+
+				public int size() {
+					return LinkedHashMap.this.size();
+				}
+
+				public void clear() {
+					LinkedHashMap.this.clear();
+				}
+
+				public boolean remove(Object key) {
+					if (containsKey(key)) {
+						LinkedHashMap.this.remove(key);
+						return true;
+					}
+					return false;
+				}
+
+				public Iterator iterator() {
+					return new LinkedHashIterator(new MapEntry.Type() {
+						public Object get(MapEntry entry) {
+							return entry.key;
+						}
+					}, LinkedHashMap.this);
+				}
+			};
+		}
+		return keySet;
+	}
+
+	/**
+	 * Answers a Collection of the values contained in this HashMap. The
+	 * collection is backed by this HashMap so changes to one are relected by
+	 * the other. The collection does not support adding.
+	 * 
+	 * @return a Collection of the values
+	 */
+	public Collection values() {
+		if (valuesCollection == null) {
+			valuesCollection = new AbstractCollection() {
+				public boolean contains(Object object) {
+					return containsValue(object);
+				}
+
+				public int size() {
+					return LinkedHashMap.this.size();
+				}
+
+				public void clear() {
+					LinkedHashMap.this.clear();
+				}
+
+				public Iterator iterator() {
+					return new LinkedHashIterator(new MapEntry.Type() {
+						public Object get(MapEntry entry) {
+							return entry.value;
+						}
+					}, LinkedHashMap.this);
+				}
+			};
+		}
+		return valuesCollection;
+	}
+
+	/**
+	 * Remove the entry corresponding to the given key.
+	 * 
+	 * @param key
+	 *            the key
+	 * @return the value associated with the key or null if the key was no in
+	 *         the map
+	 */
+	public Object remove(Object key) {
+		LinkedHashMapEntry m = (LinkedHashMapEntry) removeEntry(key);
+		if (m == null)
+			return null;
+		LinkedHashMapEntry p = m.chainBackward;
+		LinkedHashMapEntry n = m.chainForward;
+		if (p != null)
+			p.chainForward = n;
+		else
+			head = n;
+		if (n != null)
+			n.chainBackward = p;
+		else
+			tail = p;
+		return m.value;
+	}
+
+	/**
+	 * This method is queried from the put and putAll methods to check if the
+	 * eldest member of the map should be deleted before adding the new member.
+	 * If this map was created with accessOrder = true, then the result of
+	 * removeEldesrEntry is assumed to be false.
+	 * 
+	 * @param eldest
+	 * @return true if the eldest member should be removed
+	 */
+	protected boolean removeEldestEntry(Map.Entry eldest) {
+		return false;
+	}
+
+	/**
+	 * Removes all mappings from this HashMap, leaving it empty.
+	 * 
+	 * @see #isEmpty()
+	 * @see #size()
+	 */
+	public void clear() {
+		super.clear();
+		head = tail = null;
+	}
+
+	/**
+	 * Answers a new HashMap with the same mappings and size as this HashMap.
+	 * 
+	 * @return a shallow copy of this HashMap
+	 * 
+	 * @see java.lang.Cloneable
+	 */
+	public Object clone() {
+		LinkedHashMap map = (LinkedHashMap) super.clone();
+		map.clear();
+		Iterator entries = entrySet().iterator();
+		while (entries.hasNext()) {
+			Map.Entry entry = (Map.Entry) entries.next();
+			map.put(entry.getKey(), entry.getValue());
+		}
+		return map;
+	}
+}

Added: incubator/harmony/enhanced/trunk/sandbox/contribs/ibm_core/java-src/luni/src/java/util/LinkedHashSet.java
URL: http://svn.apache.org/viewcvs/incubator/harmony/enhanced/trunk/sandbox/contribs/ibm_core/java-src/luni/src/java/util/LinkedHashSet.java?rev=350181&view=auto
==============================================================================
--- incubator/harmony/enhanced/trunk/sandbox/contribs/ibm_core/java-src/luni/src/java/util/LinkedHashSet.java (added)
+++ incubator/harmony/enhanced/trunk/sandbox/contribs/ibm_core/java-src/luni/src/java/util/LinkedHashSet.java Wed Nov 30 21:29:27 2005
@@ -0,0 +1,77 @@
+/* Copyright 2005, 2005 The Apache Software Foundation or its licensors, as applicable
+ * 
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ * 
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ * 
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package java.util;
+
+
+import java.io.Serializable;
+
+/**
+ * LinkedHashSet
+ * 
+ */
+public class LinkedHashSet extends HashSet implements Set, Cloneable,
+		Serializable {
+	
+	/**
+	 * Contructs a new empty instance of LinkedHashSet.
+	 */
+	public LinkedHashSet() {
+		super(new LinkedHashMap());
+	}
+
+	/**
+	 * Constructs a new instance of LinkedHashSet with the specified capacity.
+	 * 
+	 * @param capacity
+	 *            the initial capacity of this HashSet
+	 */
+	public LinkedHashSet(int capacity) {
+		super(new LinkedHashMap(capacity));
+	}
+
+	/**
+	 * Constructs a new instance of LinkedHashSet with the specified capacity
+	 * and load factor.
+	 * 
+	 * @param capacity
+	 *            the initial capacity
+	 * @param loadFactor
+	 *            the initial load factor
+	 */
+	public LinkedHashSet(int capacity, float loadFactor) {
+		super(new LinkedHashMap(capacity, loadFactor));
+	}
+
+	/**
+	 * Constructs a new instance of LinkedHashSet containing the unique elements
+	 * in the specified collection.
+	 * 
+	 * @param collection
+	 *            the collection of elements to add
+	 */
+	public LinkedHashSet(Collection collection) {
+		super(new LinkedHashMap(collection.size() < 6 ? 11
+				: collection.size() * 2));
+		Iterator it = collection.iterator();
+		while (it.hasNext())
+			add(it.next());
+	}
+
+	/* overrides method in HashMap */
+	HashMap createBackingMap(int capacity, float loadFactor) {
+		return new LinkedHashMap(capacity, loadFactor);
+	}
+}