bundles/org.eclipse.jface/src/org/eclipse/jface/viewers/CustomHashtable.java - platform/eclipse.platform.ui - Git at Google

 /*******************************************************************************
  * Copyright (c) 2000, 2004 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:
  *     Peter Shipton - original hashtable implementation
  *     Nick Edgar - added element comparer support
  *******************************************************************************/

 package org.eclipse.jface.viewers;

 import java.util.Enumeration;
 import java.util.NoSuchElementException;

 /**
  * CustomHashtable 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.
  * <p>
  * CustomHashtable allows a custom comparator and hash code provider.
  */
 /* package */final class CustomHashtable {

     /**
      * HashMapEntry is an internal class which is used to hold the entries of a Hashtable.
      */
     private static class HashMapEntry {
         Object key, value;

         HashMapEntry next;

         HashMapEntry(Object theKey, Object theValue) {
             key = theKey;
             value = theValue;
         }
     }

     private static final class EmptyEnumerator implements Enumeration {
         public boolean hasMoreElements() {
             return false;
         }

         public Object nextElement() {
             throw new NoSuchElementException();
         }
     }

     private class HashEnumerator implements Enumeration {
         boolean key;

         int start;

         HashMapEntry entry;

         HashEnumerator(boolean isKey) {
             key = isKey;
             start = firstSlot;
         }

         public boolean hasMoreElements() {
             if (entry != null)
                 return true;
             while (start <= lastSlot)
                 if (elementData[start++] != null) {
                     entry = elementData[start - 1];
                     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();
         }
     }

     transient int elementCount;

     transient HashMapEntry[] elementData;

     private float loadFactor;

     private int threshold;

     transient int firstSlot = 0;

     transient int lastSlot = -1;

     transient private IElementComparer comparer;

     private static final EmptyEnumerator emptyEnumerator = new EmptyEnumerator();

     /**
      * The default capacity used when not specified in the constructor.
      */
     public static final int DEFAULT_CAPACITY = 13;

     /**
      * Constructs a new Hashtable using the default capacity
      * and load factor.
      */
     public CustomHashtable() {
         this(13);
     }

     /**
      * Constructs a new Hashtable using the specified capacity
      * and the default load factor.
      *
      * @param capacity the initial capacity
      */
     public CustomHashtable(int capacity) {
         this(capacity, null);
     }

     /**
      * Constructs a new hash table with the default capacity and the given
      * element comparer.
      *
      * @param comparer the element comparer to use to compare keys and obtain
      *   hash codes for keys, or <code>null</code>  to use the normal
      *   <code>equals</code> and <code>hashCode</code> methods
      */
     public CustomHashtable(IElementComparer comparer) {
         this(DEFAULT_CAPACITY, comparer);
     }

     /**
      * Constructs a new hash table with the given capacity and the given
      * element comparer.
      *
      * @param capacity the maximum number of elements that can be added without
      *   rehashing
      * @param comparer the element comparer to use to compare keys and obtain
      *   hash codes for keys, or <code>null</code>  to use the normal
      *   <code>equals</code> and <code>hashCode</code> methods
      */
     public CustomHashtable(int capacity, IElementComparer comparer) {
         if (capacity >= 0) {
             elementCount = 0;
             elementData = new HashMapEntry[capacity == 0 ? 1 : capacity];
             firstSlot = elementData.length;
             loadFactor = 0.75f;
             computeMaxSize();
         } else
             throw new IllegalArgumentException();
         this.comparer = comparer;
     }

     /**
      * Constructs a new hash table with enough capacity to hold all keys in the
      * given hash table, then adds all key/value pairs in the given hash table
      * to the new one, using the given element comparer.
      *
      * @param capacity the maximum number of elements that can be added without
      *   rehashing
      * @param comparer the element comparer to use to compare keys and obtain
      *   hash codes for keys, or <code>null</code>  to use the normal
      *   <code>equals</code> and <code>hashCode</code> methods
      */
     public CustomHashtable(CustomHashtable table, IElementComparer comparer) {
         this(table.size() * 2, comparer);
         for (int i = table.elementData.length; --i >= 0;) {
             HashMapEntry entry = table.elementData[i];
             while (entry != null) {
                 put(entry.key, entry.value);
                 entry = entry.next;
             }
         }
     }

     private void computeMaxSize() {
         threshold = (int) (elementData.length * loadFactor);
     }

     /**
      * 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
      */
     public boolean containsKey(Object key) {
         return getEntry(key) != null;
     }

     /**
      * 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
      */
     public Enumeration elements() {
         if (elementCount == 0)
             return emptyEnumerator;
         return new HashEnumerator(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
      */
     public Object get(Object key) {
         int index = (hashCode(key) & 0x7FFFFFFF) % elementData.length;
         HashMapEntry entry = elementData[index];
         while (entry != null) {
             if (keyEquals(key, entry.key))
                 return entry.value;
             entry = entry.next;
         }
         return null;
     }

     private HashMapEntry getEntry(Object key) {
         int index = (hashCode(key) & 0x7FFFFFFF) % elementData.length;
         HashMapEntry entry = elementData[index];
         while (entry != null) {
             if (keyEquals(key, entry.key))
                 return entry;
             entry = entry.next;
         }
         return null;
     }

     /**
      * Answers the hash code for the given key.
      */
     private int hashCode(Object key) {
         if (comparer == null)
             return key.hashCode();
         else
             return comparer.hashCode(key);
     }

     /**
      * Compares two keys for equality.
      */
     private boolean keyEquals(Object a, Object b) {
         if (comparer == null)
             return a.equals(b);
         else
             return comparer.equals(a, b);
     }

     /**
      * 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
      */
     public Enumeration keys() {
         if (elementCount == 0)
             return emptyEnumerator;
         return new HashEnumerator(true);
     }

     /**
      * 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
      */
     public Object put(Object key, Object value) {
         if (key != null && value != null) {
             int index = (hashCode(key) & 0x7FFFFFFF) % elementData.length;
             HashMapEntry entry = elementData[index];
             while (entry != null && !keyEquals(key, entry.key))
                 entry = entry.next;
             if (entry == null) {
                 if (++elementCount > threshold) {
                     rehash();
                     index = (hashCode(key) & 0x7FFFFFFF) % elementData.length;
                 }
                 if (index < firstSlot)
                     firstSlot = index;
                 if (index > lastSlot)
                     lastSlot = index;
                 entry = new HashMapEntry(key, value);
                 entry.next = elementData[index];
                 elementData[index] = entry;
                 return null;
             }
             Object result = entry.value;
             entry.key = key; // important to avoid hanging onto keys that are equal but "old" -- see bug 30607
             entry.value = value;
             return result;
         } else
             throw new NullPointerException();
     }

     /**
      * Increases the capacity of this Hashtable. This method is sent when
      * the size of this Hashtable exceeds the load factor.
      */
     private void rehash() {
         int length = elementData.length << 1;
         if (length == 0)
             length = 1;
         firstSlot = length;
         lastSlot = -1;
         HashMapEntry[] newData = new HashMapEntry[length];
         for (int i = elementData.length; --i >= 0;) {
             HashMapEntry entry = elementData[i];
             while (entry != null) {
                 int index = (hashCode(entry.key) & 0x7FFFFFFF) % length;
                 if (index < firstSlot)
                     firstSlot = index;
                 if (index > lastSlot)
                     lastSlot = index;
                 HashMapEntry next = entry.next;
                 entry.next = newData[index];
                 newData[index] = entry;
                 entry = next;
             }
         }
         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
      */
     public Object remove(Object key) {
         HashMapEntry last = null;
         int index = (hashCode(key) & 0x7FFFFFFF) % elementData.length;
         HashMapEntry entry = elementData[index];
         while (entry != null && !keyEquals(key, entry.key)) {
             last = entry;
             entry = entry.next;
         }
         if (entry != null) {
             if (last == null)
                 elementData[index] = entry.next;
             else
                 last.next = entry.next;
             elementCount--;
             return entry.value;
         }
         return null;
     }

     /**
      * Answers the number of key/value pairs in this Hashtable.
      *
      * @return		the number of key/value pairs in this Hashtable
      */
     public int size() {
         return elementCount;
     }

     /**
      * Answers the string representation of this Hashtable.
      *
      * @return		the string representation of this Hashtable
      */
     public String toString() {
         if (size() == 0)
             return "{}"; //$NON-NLS-1$

         StringBuffer buffer = new StringBuffer();
         buffer.append('{');
         for (int i = elementData.length; --i >= 0;) {
             HashMapEntry entry = elementData[i];
             while (entry != null) {
                 buffer.append(entry.key);
                 buffer.append('=');
                 buffer.append(entry.value);
                 buffer.append(", "); //$NON-NLS-1$
                 entry = entry.next;
             }
         }
         // Remove the last ", "
         if (elementCount > 0)
             buffer.setLength(buffer.length() - 2);
         buffer.append('}');
         return buffer.toString();
     }
 }
	/*******************************************************************************
	* Copyright (c) 2000, 2004 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:
	* Peter Shipton - original hashtable implementation
	* Nick Edgar - added element comparer support
	*******************************************************************************/

	package org.eclipse.jface.viewers;

	import java.util.Enumeration;
	import java.util.NoSuchElementException;

	/**
	* CustomHashtable 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.
	* <p>
	* CustomHashtable allows a custom comparator and hash code provider.
	*/
	/* package */final class CustomHashtable {

	/**
	* HashMapEntry is an internal class which is used to hold the entries of a Hashtable.
	*/
	private static class HashMapEntry {
	Object key, value;

	HashMapEntry next;

	HashMapEntry(Object theKey, Object theValue) {
	key = theKey;
	value = theValue;
	}
	}

	private static final class EmptyEnumerator implements Enumeration {
	public boolean hasMoreElements() {
	return false;
	}

	public Object nextElement() {
	throw new NoSuchElementException();
	}
	}

	private class HashEnumerator implements Enumeration {
	boolean key;

	int start;

	HashMapEntry entry;

	HashEnumerator(boolean isKey) {
	key = isKey;
	start = firstSlot;
	}

	public boolean hasMoreElements() {
	if (entry != null)
	return true;
	while (start <= lastSlot)
	if (elementData[start++] != null) {
	entry = elementData[start - 1];
	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();
	}
	}

	transient int elementCount;

	transient HashMapEntry[] elementData;

	private float loadFactor;

	private int threshold;

	transient int firstSlot = 0;

	transient int lastSlot = -1;

	transient private IElementComparer comparer;

	private static final EmptyEnumerator emptyEnumerator = new EmptyEnumerator();

	/**
	* The default capacity used when not specified in the constructor.
	*/
	public static final int DEFAULT_CAPACITY = 13;

	/**
	* Constructs a new Hashtable using the default capacity
	* and load factor.
	*/
	public CustomHashtable() {
	this(13);
	}

	/**
	* Constructs a new Hashtable using the specified capacity
	* and the default load factor.
	*
	* @param capacity the initial capacity
	*/
	public CustomHashtable(int capacity) {
	this(capacity, null);
	}

	/**
	* Constructs a new hash table with the default capacity and the given
	* element comparer.
	*
	* @param comparer the element comparer to use to compare keys and obtain
	* hash codes for keys, or <code>null</code> to use the normal
	* <code>equals</code> and <code>hashCode</code> methods
	*/
	public CustomHashtable(IElementComparer comparer) {
	this(DEFAULT_CAPACITY, comparer);
	}

	/**
	* Constructs a new hash table with the given capacity and the given
	* element comparer.
	*
	* @param capacity the maximum number of elements that can be added without
	* rehashing
	* @param comparer the element comparer to use to compare keys and obtain
	* hash codes for keys, or <code>null</code> to use the normal
	* <code>equals</code> and <code>hashCode</code> methods
	*/
	public CustomHashtable(int capacity, IElementComparer comparer) {
	if (capacity >= 0) {
	elementCount = 0;
	elementData = new HashMapEntry[capacity == 0 ? 1 : capacity];
	firstSlot = elementData.length;
	loadFactor = 0.75f;
	computeMaxSize();
	} else
	throw new IllegalArgumentException();
	this.comparer = comparer;
	}

	/**
	* Constructs a new hash table with enough capacity to hold all keys in the
	* given hash table, then adds all key/value pairs in the given hash table
	* to the new one, using the given element comparer.
	*
	* @param capacity the maximum number of elements that can be added without
	* rehashing
	* @param comparer the element comparer to use to compare keys and obtain
	* hash codes for keys, or <code>null</code> to use the normal
	* <code>equals</code> and <code>hashCode</code> methods
	*/
	public CustomHashtable(CustomHashtable table, IElementComparer comparer) {
	this(table.size() * 2, comparer);
	for (int i = table.elementData.length; --i >= 0;) {
	HashMapEntry entry = table.elementData[i];
	while (entry != null) {
	put(entry.key, entry.value);
	entry = entry.next;
	}
	}
	}

	private void computeMaxSize() {
	threshold = (int) (elementData.length * loadFactor);
	}

	/**
	* 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
	*/
	public boolean containsKey(Object key) {
	return getEntry(key) != null;
	}

	/**
	* 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
	*/
	public Enumeration elements() {
	if (elementCount == 0)
	return emptyEnumerator;
	return new HashEnumerator(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
	*/
	public Object get(Object key) {
	int index = (hashCode(key) & 0x7FFFFFFF) % elementData.length;
	HashMapEntry entry = elementData[index];
	while (entry != null) {
	if (keyEquals(key, entry.key))
	return entry.value;
	entry = entry.next;
	}
	return null;
	}

	private HashMapEntry getEntry(Object key) {
	int index = (hashCode(key) & 0x7FFFFFFF) % elementData.length;
	HashMapEntry entry = elementData[index];
	while (entry != null) {
	if (keyEquals(key, entry.key))
	return entry;
	entry = entry.next;
	}
	return null;
	}

	/**
	* Answers the hash code for the given key.
	*/
	private int hashCode(Object key) {
	if (comparer == null)
	return key.hashCode();
	else
	return comparer.hashCode(key);
	}

	/**
	* Compares two keys for equality.
	*/
	private boolean keyEquals(Object a, Object b) {
	if (comparer == null)
	return a.equals(b);
	else
	return comparer.equals(a, b);
	}

	/**
	* 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
	*/
	public Enumeration keys() {
	if (elementCount == 0)
	return emptyEnumerator;
	return new HashEnumerator(true);
	}

	/**
	* 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
	*/
	public Object put(Object key, Object value) {
	if (key != null && value != null) {
	int index = (hashCode(key) & 0x7FFFFFFF) % elementData.length;
	HashMapEntry entry = elementData[index];
	while (entry != null && !keyEquals(key, entry.key))
	entry = entry.next;
	if (entry == null) {
	if (++elementCount > threshold) {
	rehash();
	index = (hashCode(key) & 0x7FFFFFFF) % elementData.length;
	}
	if (index < firstSlot)
	firstSlot = index;
	if (index > lastSlot)
	lastSlot = index;
	entry = new HashMapEntry(key, value);
	entry.next = elementData[index];
	elementData[index] = entry;
	return null;
	}
	Object result = entry.value;
	entry.key = key; // important to avoid hanging onto keys that are equal but "old" -- see bug 30607
	entry.value = value;
	return result;
	} else
	throw new NullPointerException();
	}

	/**
	* Increases the capacity of this Hashtable. This method is sent when
	* the size of this Hashtable exceeds the load factor.
	*/
	private void rehash() {
	int length = elementData.length << 1;
	if (length == 0)
	length = 1;
	firstSlot = length;
	lastSlot = -1;
	HashMapEntry[] newData = new HashMapEntry[length];
	for (int i = elementData.length; --i >= 0;) {
	HashMapEntry entry = elementData[i];
	while (entry != null) {
	int index = (hashCode(entry.key) & 0x7FFFFFFF) % length;
	if (index < firstSlot)
	firstSlot = index;
	if (index > lastSlot)
	lastSlot = index;
	HashMapEntry next = entry.next;
	entry.next = newData[index];
	newData[index] = entry;
	entry = next;
	}
	}
	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
	*/
	public Object remove(Object key) {
	HashMapEntry last = null;
	int index = (hashCode(key) & 0x7FFFFFFF) % elementData.length;
	HashMapEntry entry = elementData[index];
	while (entry != null && !keyEquals(key, entry.key)) {
	last = entry;
	entry = entry.next;
	}
	if (entry != null) {
	if (last == null)
	elementData[index] = entry.next;
	else
	last.next = entry.next;
	elementCount--;
	return entry.value;
	}
	return null;
	}

	/**
	* Answers the number of key/value pairs in this Hashtable.
	*
	* @return the number of key/value pairs in this Hashtable
	*/
	public int size() {
	return elementCount;
	}

	/**
	* Answers the string representation of this Hashtable.
	*
	* @return the string representation of this Hashtable
	*/
	public String toString() {
	if (size() == 0)
	return "{}"; //$NON-NLS-1$

	StringBuffer buffer = new StringBuffer();
	buffer.append('{');
	for (int i = elementData.length; --i >= 0;) {
	HashMapEntry entry = elementData[i];
	while (entry != null) {
	buffer.append(entry.key);
	buffer.append('=');
	buffer.append(entry.value);
	buffer.append(", "); //$NON-NLS-1$
	entry = entry.next;
	}
	}
	// Remove the last ", "
	if (elementCount > 0)
	buffer.setLength(buffer.length() - 2);
	buffer.append('}');
	return buffer.toString();
	}
	}