| /******************************************************************************* |
| * Copyright (c) 2000, 2012 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<KeyedElement> iterator() { |
| return new EquinoxSetIterator(); |
| } |
| |
| class EquinoxSetIterator implements Iterator<KeyedElement> { |
| private int currentIndex = -1; |
| private int found; |
| |
| public boolean hasNext() { |
| return found < elementCount; |
| } |
| |
| public KeyedElement 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; |
| } |
| } |