bundles/org.eclipse.osgi/core/adaptor/org/eclipse/osgi/framework/util/KeyedHashSet.java - equinox/rt.equinox.framework - Git at Google

 /*******************************************************************************
  * Copyright (c) 2000, 2006 IBM Corporation and others.
  * All rights reserved. This program and the accompanying materials
  * are made available under the terms of the Eclipse Public License v1.0
  * which accompanies this distribution, and is available at
  * http://www.eclipse.org/legal/epl-v10.html
  *
  * Contributors:
  *     IBM Corporation - initial API and implementation
  *******************************************************************************/
 package org.eclipse.osgi.framework.util;

 import java.util.Iterator;
 import java.util.NoSuchElementException;

 /**
  * A set data structure which only accepts {@link KeyedElement} objects as elements of the set.
  * Unlike typical set implementations this set requires each element to provide its own key.  This helps
  * reduce the overhead of storing the keys of each individual element<p>
  * This class in not thread safe, clients must ensure synchronization when modifying an object of this type.
  * @since 3.2
  */
 // This class was moved from  /org.eclipse.osgi/core/framework/org/eclipse/osgi/framework/internal/core/KeyedHashSet.java
 public class KeyedHashSet {
 	public static final int MINIMUM_SIZE = 7;
 	int elementCount = 0;
 	KeyedElement[] elements;
 	private boolean replace;
 	private int capacity;

 	/**
 	 * Constructs an KeyedHashSet which allows elements to be replaced and with the minimum initial capacity.
 	 */
 	public KeyedHashSet() {
 		this(MINIMUM_SIZE, true);
 	}

 	/**
 	 * Constructs an KeyedHashSet with the minimum initial capacity.
 	 * @param replace true if this set allows elements to be replaced
 	 */
 	public KeyedHashSet(boolean replace) {
 		this(MINIMUM_SIZE, replace);
 	}

 	/**
 	 * Constructs an KeyedHashSet which allows elements to be replaced.
 	 * @param capacity the initial capacity of this set
 	 */
 	public KeyedHashSet(int capacity) {
 		this(capacity, true);
 	}

 	/**
 	 * Constructs an KeyedHashSet
 	 * @param capacity the initial capacity of this set
 	 * @param replace true if this set allows elements to be replaced
 	 */
 	public KeyedHashSet(int capacity, boolean replace) {
 		elements = new KeyedElement[Math.max(MINIMUM_SIZE, capacity * 2)];
 		this.replace = replace;
 		this.capacity = capacity;
 	}

 	/**
 	 * Constructs a new KeyedHashSet and copies to specified KeyedHashSet's contents to the new KeyedHashSet.
 	 * @param original the KeyedHashSet to copy
 	 */
 	public KeyedHashSet(KeyedHashSet original) {
 		elements = new KeyedElement[original.elements.length];
 		System.arraycopy(original.elements, 0, elements, 0, original.elements.length);
 		elementCount = original.elementCount;
 		replace = original.replace;
 		capacity = original.capacity;
 	}

 	/**
 	 * Adds an element to this set. If an element with the same key already exists,
 	 * replaces it depending on the replace flag.
 	 * @return true if the element was added/stored, false otherwise
 	 */
 	public boolean add(KeyedElement element) {
 		int hash = hash(element);

 		// search for an empty slot at the end of the array
 		for (int i = hash; i < elements.length; i++) {
 			if (elements[i] == null) {
 				elements[i] = element;
 				elementCount++;
 				// grow if necessary
 				if (shouldGrow())
 					expand();
 				return true;
 			}
 			if (elements[i].compare(element)) {
 				if (replace)
 					elements[i] = element;
 				return replace;
 			}
 		}

 		// search for an empty slot at the beginning of the array
 		for (int i = 0; i < hash - 1; i++) {
 			if (elements[i] == null) {
 				elements[i] = element;
 				elementCount++;
 				// grow if necessary
 				if (shouldGrow())
 					expand();
 				return true;
 			}
 			if (elements[i].compare(element)) {
 				if (replace)
 					elements[i] = element;
 				return replace;
 			}
 		}

 		// if we didn't find a free slot, then try again with the expanded set
 		expand();
 		return add(element);
 	}

 	/**
 	 * Adds the specified list of elements to this set.  Some elements may not
 	 * get added if the replace flag is set.
 	 * @param toAdd the list of elements to add to this set.
 	 */
 	public void addAll(KeyedElement[] toAdd) {
 		for (int i = 0; i < toAdd.length; i++)
 			add(toAdd[i]);
 	}

 	/**
 	 * Returns true if the specified element exists in this set.
 	 * @param element the requested element
 	 * @return true if the specified element exists in this set; false otherwise.
 	 */
 	public boolean contains(KeyedElement element) {
 		return get(element) != null;
 	}

 	/**
 	 * Returns true if an element with the specified key exists in this set.
 	 * @param key the key of the requested element
 	 * @return true if an element with the specified key exists in this set; false otherwise
 	 */
 	public boolean containsKey(Object key) {
 		return getByKey(key) != null;
 	}

 	/**
 	 * Returns all elements that exist in this set
 	 * @return all elements that exist in this set
 	 */
 	public KeyedElement[] elements() {
 		return (KeyedElement[]) elements(new KeyedElement[elementCount]);
 	}

 	/**
 	 * Copies all elements that exist in this set into the specified array.  No size
 	 * checking is done.  If the specified array is to small an ArrayIndexOutOfBoundsException
 	 * will be thrown.
 	 * @param result the array to copy the existing elements into.
 	 * @return the specified array.
 	 * @throws ArrayIndexOutOfBoundsException if the specified array is to small.
 	 */
 	public Object[] elements(Object[] result) {
 		int j = 0;
 		for (int i = 0; i < elements.length; i++) {
 			KeyedElement element = elements[i];
 			if (element != null)
 				result[j++] = element;
 		}
 		return result;
 	}

 	/**
 	 * The array isn't large enough so double its size and rehash
 	 * all its current values.
 	 */
 	protected void expand() {
 		KeyedElement[] oldElements = elements;
 		elements = new KeyedElement[elements.length * 2];

 		int maxArrayIndex = elements.length - 1;
 		for (int i = 0; i < oldElements.length; i++) {
 			KeyedElement element = oldElements[i];
 			if (element != null) {
 				int hash = hash(element);
 				while (elements[hash] != null) {
 					hash++;
 					if (hash > maxArrayIndex)
 						hash = 0;
 				}
 				elements[hash] = element;
 			}
 		}
 	}

 	/**
 	 * Returns the element with the specified key, or null if not found.
 	 * @param key the requested element's key
 	 * @return the element with the specified key, or null if not found.
 	 */
 	public KeyedElement getByKey(Object key) {
 		if (elementCount == 0)
 			return null;
 		int hash = keyHash(key);

 		// search the last half of the array
 		for (int i = hash; i < elements.length; i++) {
 			KeyedElement element = elements[i];
 			if (element == null)
 				return null;
 			if (element.getKey().equals(key))
 				return element;
 		}

 		// search the beginning of the array
 		for (int i = 0; i < hash - 1; i++) {
 			KeyedElement element = elements[i];
 			if (element == null)
 				return null;
 			if (element.getKey().equals(key))
 				return element;
 		}

 		// nothing found so return null
 		return null;
 	}

 	/**
 	 * Returns the element which compares to the specified element, or null if not found.
 	 * @see KeyedElement#compare(KeyedElement)
 	 * @param otherElement the requested element
 	 * @return the element which compares to the specified element, or null if not found.
 	 */
 	public KeyedElement get(KeyedElement otherElement) {
 		if (elementCount == 0)
 			return null;
 		int hash = hash(otherElement);

 		// search the last half of the array
 		for (int i = hash; i < elements.length; i++) {
 			KeyedElement element = elements[i];
 			if (element == null)
 				return null;
 			if (element.compare(otherElement))
 				return element;
 		}

 		// search the beginning of the array
 		for (int i = 0; i < hash - 1; i++) {
 			KeyedElement element = elements[i];
 			if (element == null)
 				return null;
 			if (element.compare(otherElement))
 				return element;
 		}

 		// nothing found so return null
 		return null;
 	}

 	/**
 	 * Returns true if this set is empty
 	 * @return true if this set is empty
 	 */
 	public boolean isEmpty() {
 		return elementCount == 0;
 	}

 	/**
 	 * The element at the given index has been removed so move
 	 * elements to keep the set properly hashed.
 	 * @param anIndex the index that has been removed
 	 */
 	protected void rehashTo(int anIndex) {

 		int target = anIndex;
 		int index = anIndex + 1;
 		if (index >= elements.length)
 			index = 0;
 		KeyedElement element = elements[index];
 		while (element != null) {
 			int hashIndex = hash(element);
 			boolean match;
 			if (index < target)
 				match = !(hashIndex > target || hashIndex <= index);
 			else
 				match = !(hashIndex > target && hashIndex <= index);
 			if (match) {
 				elements[target] = element;
 				target = index;
 			}
 			index++;
 			if (index >= elements.length)
 				index = 0;
 			element = elements[index];
 		}
 		elements[target] = null;
 	}

 	/**
 	 * Removes the element with the specified key
 	 * @param key the requested element's key
 	 * @return true if an element was removed
 	 */
 	public boolean removeByKey(Object key) {
 		if (elementCount == 0)
 			return false;
 		int hash = keyHash(key);

 		for (int i = hash; i < elements.length; i++) {
 			KeyedElement element = elements[i];
 			if (element == null)
 				return false;
 			if (element.getKey().equals(key)) {
 				rehashTo(i);
 				elementCount--;
 				return true;
 			}
 		}

 		for (int i = 0; i < hash - 1; i++) {
 			KeyedElement element = elements[i];
 			if (element == null)
 				return false;
 			if (element.getKey().equals(key)) {
 				rehashTo(i);
 				elementCount--;
 				return true;
 			}
 		}

 		return true;
 	}

 	/**
 	 * Removes the element which compares to the specified element
 	 * @param toRemove the requested element to remove
 	 * @return true if an element was removed
 	 */
 	public boolean remove(KeyedElement toRemove) {
 		if (elementCount == 0)
 			return false;

 		int hash = hash(toRemove);

 		for (int i = hash; i < elements.length; i++) {
 			KeyedElement element = elements[i];
 			if (element == null)
 				return false;
 			if (element.compare(toRemove)) {
 				rehashTo(i);
 				elementCount--;
 				return true;
 			}
 		}

 		for (int i = 0; i < hash - 1; i++) {
 			KeyedElement element = elements[i];
 			if (element == null)
 				return false;
 			if (element.compare(toRemove)) {
 				rehashTo(i);
 				elementCount--;
 				return true;
 			}
 		}
 		return false;
 	}

 	private int hash(KeyedElement element) {
 		return Math.abs(element.getKeyHashCode()) % elements.length;
 	}

 	private int keyHash(Object key) {
 		return Math.abs(key.hashCode()) % elements.length;
 	}

 	/**
 	 * Removes all of the specified elements from this set
 	 * @param toRemove the requested elements to remove
 	 */
 	public void removeAll(KeyedElement[] toRemove) {
 		for (int i = 0; i < toRemove.length; i++)
 			remove(toRemove[i]);
 	}

 	private boolean shouldGrow() {
 		return elementCount > elements.length * 0.75;
 	}

 	/**
 	 * Returns the number of elements in this set
 	 * @return the number of elements in this set
 	 */
 	public int size() {
 		return elementCount;
 	}

 	public String toString() {
 		StringBuffer result = new StringBuffer(100);
 		result.append("{"); //$NON-NLS-1$
 		boolean first = true;
 		for (int i = 0; i < elements.length; i++) {
 			if (elements[i] != null) {
 				if (first)
 					first = false;
 				else
 					result.append(", "); //$NON-NLS-1$
 				result.append(elements[i]);
 			}
 		}
 		result.append("}"); //$NON-NLS-1$
 		return result.toString();
 	}

 	/**
 	 * Returns the number of collisions this set currently has
 	 * @return the number of collisions this set currently has
 	 */
 	public int countCollisions() {
 		int result = 0;
 		int lastHash = 0;
 		boolean found = false;
 		for (int i = 0; i < elements.length; i++) {
 			KeyedElement element = elements[i];
 			if (element == null)
 				found = false;
 			else {
 				int hash = hash(element);
 				if (found)
 					if (lastHash == hash)
 						result++;
 					else
 						found = false;
 				else {
 					lastHash = hash;
 					found = true;
 				}
 			}
 		}
 		return result;
 	}

 	/**
 	 * Returns an iterator of elements in this set
 	 * @return an iterator of elements in this set
 	 */
 	public Iterator iterator() {
 		return new EquinoxSetIterator();
 	}

 	class EquinoxSetIterator implements Iterator {
 		private int currentIndex = -1;
 		private int found;

 		public boolean hasNext() {
 			return found < elementCount;
 		}

 		public Object next() {
 			if (!hasNext())
 				throw new NoSuchElementException();
 			while (++currentIndex < elements.length)
 				if (elements[currentIndex] != null) {
 					found++;
 					return elements[currentIndex];
 				}
 			// this would mean we have less elements than we thought
 			throw new NoSuchElementException();
 		}

 		public void remove() {
 			// as allowed by the API
 			throw new UnsupportedOperationException();
 		}
 	}

 	/**
 	 * Clears all elements from this set
 	 */
 	public void clear() {
 		elements = new KeyedElement[Math.max(MINIMUM_SIZE, capacity * 2)];
 		elementCount = 0;
 	}
 }
	/*******************************************************************************
	* Copyright (c) 2000, 2006 IBM Corporation and others.
	* All rights reserved. This program and the accompanying materials
	* are made available under the terms of the Eclipse Public License v1.0
	* which accompanies this distribution, and is available at
	* http://www.eclipse.org/legal/epl-v10.html
	*
	* Contributors:
	* IBM Corporation - initial API and implementation
	*******************************************************************************/
	package org.eclipse.osgi.framework.util;

	import java.util.Iterator;
	import java.util.NoSuchElementException;

	/**
	* A set data structure which only accepts {@link KeyedElement} objects as elements of the set.
	* Unlike typical set implementations this set requires each element to provide its own key. This helps
	* reduce the overhead of storing the keys of each individual element<p>
	* This class in not thread safe, clients must ensure synchronization when modifying an object of this type.
	* @since 3.2
	*/
	// This class was moved from /org.eclipse.osgi/core/framework/org/eclipse/osgi/framework/internal/core/KeyedHashSet.java
	public class KeyedHashSet {
	public static final int MINIMUM_SIZE = 7;
	int elementCount = 0;
	KeyedElement[] elements;
	private boolean replace;
	private int capacity;

	/**
	* Constructs an KeyedHashSet which allows elements to be replaced and with the minimum initial capacity.
	*/
	public KeyedHashSet() {
	this(MINIMUM_SIZE, true);
	}

	/**
	* Constructs an KeyedHashSet with the minimum initial capacity.
	* @param replace true if this set allows elements to be replaced
	*/
	public KeyedHashSet(boolean replace) {
	this(MINIMUM_SIZE, replace);
	}

	/**
	* Constructs an KeyedHashSet which allows elements to be replaced.
	* @param capacity the initial capacity of this set
	*/
	public KeyedHashSet(int capacity) {
	this(capacity, true);
	}

	/**
	* Constructs an KeyedHashSet
	* @param capacity the initial capacity of this set
	* @param replace true if this set allows elements to be replaced
	*/
	public KeyedHashSet(int capacity, boolean replace) {
	elements = new KeyedElement[Math.max(MINIMUM_SIZE, capacity * 2)];
	this.replace = replace;
	this.capacity = capacity;
	}

	/**
	* Constructs a new KeyedHashSet and copies to specified KeyedHashSet's contents to the new KeyedHashSet.
	* @param original the KeyedHashSet to copy
	*/
	public KeyedHashSet(KeyedHashSet original) {
	elements = new KeyedElement[original.elements.length];
	System.arraycopy(original.elements, 0, elements, 0, original.elements.length);
	elementCount = original.elementCount;
	replace = original.replace;
	capacity = original.capacity;
	}

	/**
	* Adds an element to this set. If an element with the same key already exists,
	* replaces it depending on the replace flag.
	* @return true if the element was added/stored, false otherwise
	*/
	public boolean add(KeyedElement element) {
	int hash = hash(element);

	// search for an empty slot at the end of the array
	for (int i = hash; i < elements.length; i++) {
	if (elements[i] == null) {
	elements[i] = element;
	elementCount++;
	// grow if necessary
	if (shouldGrow())
	expand();
	return true;
	}
	if (elements[i].compare(element)) {
	if (replace)
	elements[i] = element;
	return replace;
	}
	}

	// search for an empty slot at the beginning of the array
	for (int i = 0; i < hash - 1; i++) {
	if (elements[i] == null) {
	elements[i] = element;
	elementCount++;
	// grow if necessary
	if (shouldGrow())
	expand();
	return true;
	}
	if (elements[i].compare(element)) {
	if (replace)
	elements[i] = element;
	return replace;
	}
	}

	// if we didn't find a free slot, then try again with the expanded set
	expand();
	return add(element);
	}

	/**
	* Adds the specified list of elements to this set. Some elements may not
	* get added if the replace flag is set.
	* @param toAdd the list of elements to add to this set.
	*/
	public void addAll(KeyedElement[] toAdd) {
	for (int i = 0; i < toAdd.length; i++)
	add(toAdd[i]);
	}

	/**
	* Returns true if the specified element exists in this set.
	* @param element the requested element
	* @return true if the specified element exists in this set; false otherwise.
	*/
	public boolean contains(KeyedElement element) {
	return get(element) != null;
	}

	/**
	* Returns true if an element with the specified key exists in this set.
	* @param key the key of the requested element
	* @return true if an element with the specified key exists in this set; false otherwise
	*/
	public boolean containsKey(Object key) {
	return getByKey(key) != null;
	}

	/**
	* Returns all elements that exist in this set
	* @return all elements that exist in this set
	*/
	public KeyedElement[] elements() {
	return (KeyedElement[]) elements(new KeyedElement[elementCount]);
	}

	/**
	* Copies all elements that exist in this set into the specified array. No size
	* checking is done. If the specified array is to small an ArrayIndexOutOfBoundsException
	* will be thrown.
	* @param result the array to copy the existing elements into.
	* @return the specified array.
	* @throws ArrayIndexOutOfBoundsException if the specified array is to small.
	*/
	public Object[] elements(Object[] result) {
	int j = 0;
	for (int i = 0; i < elements.length; i++) {
	KeyedElement element = elements[i];
	if (element != null)
	result[j++] = element;
	}
	return result;
	}

	/**
	* The array isn't large enough so double its size and rehash
	* all its current values.
	*/
	protected void expand() {
	KeyedElement[] oldElements = elements;
	elements = new KeyedElement[elements.length * 2];

	int maxArrayIndex = elements.length - 1;
	for (int i = 0; i < oldElements.length; i++) {
	KeyedElement element = oldElements[i];
	if (element != null) {
	int hash = hash(element);
	while (elements[hash] != null) {
	hash++;
	if (hash > maxArrayIndex)
	hash = 0;
	}
	elements[hash] = element;
	}
	}
	}

	/**
	* Returns the element with the specified key, or null if not found.
	* @param key the requested element's key
	* @return the element with the specified key, or null if not found.
	*/
	public KeyedElement getByKey(Object key) {
	if (elementCount == 0)
	return null;
	int hash = keyHash(key);

	// search the last half of the array
	for (int i = hash; i < elements.length; i++) {
	KeyedElement element = elements[i];
	if (element == null)
	return null;
	if (element.getKey().equals(key))
	return element;
	}

	// search the beginning of the array
	for (int i = 0; i < hash - 1; i++) {
	KeyedElement element = elements[i];
	if (element == null)
	return null;
	if (element.getKey().equals(key))
	return element;
	}

	// nothing found so return null
	return null;
	}

	/**
	* Returns the element which compares to the specified element, or null if not found.
	* @see KeyedElement#compare(KeyedElement)
	* @param otherElement the requested element
	* @return the element which compares to the specified element, or null if not found.
	*/
	public KeyedElement get(KeyedElement otherElement) {
	if (elementCount == 0)
	return null;
	int hash = hash(otherElement);

	// search the last half of the array
	for (int i = hash; i < elements.length; i++) {
	KeyedElement element = elements[i];
	if (element == null)
	return null;
	if (element.compare(otherElement))
	return element;
	}

	// search the beginning of the array
	for (int i = 0; i < hash - 1; i++) {
	KeyedElement element = elements[i];
	if (element == null)
	return null;
	if (element.compare(otherElement))
	return element;
	}

	// nothing found so return null
	return null;
	}

	/**
	* Returns true if this set is empty
	* @return true if this set is empty
	*/
	public boolean isEmpty() {
	return elementCount == 0;
	}

	/**
	* The element at the given index has been removed so move
	* elements to keep the set properly hashed.
	* @param anIndex the index that has been removed
	*/
	protected void rehashTo(int anIndex) {

	int target = anIndex;
	int index = anIndex + 1;
	if (index >= elements.length)
	index = 0;
	KeyedElement element = elements[index];
	while (element != null) {
	int hashIndex = hash(element);
	boolean match;
	if (index < target)
	match = !(hashIndex > target \|\| hashIndex <= index);
	else
	match = !(hashIndex > target && hashIndex <= index);
	if (match) {
	elements[target] = element;
	target = index;
	}
	index++;
	if (index >= elements.length)
	index = 0;
	element = elements[index];
	}
	elements[target] = null;
	}

	/**
	* Removes the element with the specified key
	* @param key the requested element's key
	* @return true if an element was removed
	*/
	public boolean removeByKey(Object key) {
	if (elementCount == 0)
	return false;
	int hash = keyHash(key);

	for (int i = hash; i < elements.length; i++) {
	KeyedElement element = elements[i];
	if (element == null)
	return false;
	if (element.getKey().equals(key)) {
	rehashTo(i);
	elementCount--;
	return true;
	}
	}

	for (int i = 0; i < hash - 1; i++) {
	KeyedElement element = elements[i];
	if (element == null)
	return false;
	if (element.getKey().equals(key)) {
	rehashTo(i);
	elementCount--;
	return true;
	}
	}

	return true;
	}

	/**
	* Removes the element which compares to the specified element
	* @param toRemove the requested element to remove
	* @return true if an element was removed
	*/
	public boolean remove(KeyedElement toRemove) {
	if (elementCount == 0)
	return false;

	int hash = hash(toRemove);

	for (int i = hash; i < elements.length; i++) {
	KeyedElement element = elements[i];
	if (element == null)
	return false;
	if (element.compare(toRemove)) {
	rehashTo(i);
	elementCount--;
	return true;
	}
	}

	for (int i = 0; i < hash - 1; i++) {
	KeyedElement element = elements[i];
	if (element == null)
	return false;
	if (element.compare(toRemove)) {
	rehashTo(i);
	elementCount--;
	return true;
	}
	}
	return false;
	}

	private int hash(KeyedElement element) {
	return Math.abs(element.getKeyHashCode()) % elements.length;
	}

	private int keyHash(Object key) {
	return Math.abs(key.hashCode()) % elements.length;
	}

	/**
	* Removes all of the specified elements from this set
	* @param toRemove the requested elements to remove
	*/
	public void removeAll(KeyedElement[] toRemove) {
	for (int i = 0; i < toRemove.length; i++)
	remove(toRemove[i]);
	}

	private boolean shouldGrow() {
	return elementCount > elements.length * 0.75;
	}

	/**
	* Returns the number of elements in this set
	* @return the number of elements in this set
	*/
	public int size() {
	return elementCount;
	}

	public String toString() {
	StringBuffer result = new StringBuffer(100);
	result.append("{"); //$NON-NLS-1$
	boolean first = true;
	for (int i = 0; i < elements.length; i++) {
	if (elements[i] != null) {
	if (first)
	first = false;
	else
	result.append(", "); //$NON-NLS-1$
	result.append(elements[i]);
	}
	}
	result.append("}"); //$NON-NLS-1$
	return result.toString();
	}

	/**
	* Returns the number of collisions this set currently has
	* @return the number of collisions this set currently has
	*/
	public int countCollisions() {
	int result = 0;
	int lastHash = 0;
	boolean found = false;
	for (int i = 0; i < elements.length; i++) {
	KeyedElement element = elements[i];
	if (element == null)
	found = false;
	else {
	int hash = hash(element);
	if (found)
	if (lastHash == hash)
	result++;
	else
	found = false;
	else {
	lastHash = hash;
	found = true;
	}
	}
	}
	return result;
	}

	/**
	* Returns an iterator of elements in this set
	* @return an iterator of elements in this set
	*/
	public Iterator iterator() {
	return new EquinoxSetIterator();
	}

	class EquinoxSetIterator implements Iterator {
	private int currentIndex = -1;
	private int found;

	public boolean hasNext() {
	return found < elementCount;
	}

	public Object next() {
	if (!hasNext())
	throw new NoSuchElementException();
	while (++currentIndex < elements.length)
	if (elements[currentIndex] != null) {
	found++;
	return elements[currentIndex];
	}
	// this would mean we have less elements than we thought
	throw new NoSuchElementException();
	}

	public void remove() {
	// as allowed by the API
	throw new UnsupportedOperationException();
	}
	}

	/**
	* Clears all elements from this set
	*/
	public void clear() {
	elements = new KeyedElement[Math.max(MINIMUM_SIZE, capacity * 2)];
	elementCount = 0;
	}
	}