Mercurial > projects > dwt-addons
view dwtx/jface/viewers/CustomHashtable.d @ 104:04b47443bb01
Reworked the collection uses to make use of a wrapper collection that is compatible to the Java Collections.
These new wrappers now use the tango.util.containers instead of the tango.util.collections.
author | Frank Benoit <benoit@tionex.de> |
---|---|
date | Thu, 07 Aug 2008 15:01:33 +0200 |
parents | ea8ff534f622 |
children |
line wrap: on
line source
/******************************************************************************* * 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: * Peter Shipton - original hashtable implementation * Nick Edgar - added element comparer support * Port to the D programming language: * Frank Benoit <benoit@tionex.de> *******************************************************************************/ module dwtx.jface.viewers.CustomHashtable; import dwtx.jface.viewers.IElementComparer; // import java.util.Enumeration; // import java.util.NoSuchElementException; import dwt.dwthelper.utils; import dwtx.dwtxhelper.Collection; import tango.core.Exception; static import tango.text.Text; alias tango.text.Text.Text!(char) StringBuffer; /** * 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 { alias Object.toHash toHash; /** * HashMapEntry is an internal class which is used to hold the entries of a Hashtable. */ private static class HashMapEntry { Object key, value; HashMapEntry next; this(Object theKey, Object theValue) { key = theKey; value = theValue; } } private static final class EmptyEnumerator : Enumeration { public bool hasMoreElements() { return false; } public Object nextElement() { throw new NoSuchElementException(null); } } private class HashEnumerator : Enumeration { bool key; int start; HashMapEntry entry; this(bool isKey) { key = isKey; start = firstSlot; } public bool hasMoreElements() { if (entry !is null) { return true; } while (start <= lastSlot) { if (elementData[start++] !is 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(null); } } } /+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 const EmptyEnumerator emptyEnumerator; static this(){ emptyEnumerator = new EmptyEnumerator(); } /** * The default capacity used when not specified in the constructor. */ public static const int DEFAULT_CAPACITY = 13; /** * Constructs a new Hashtable using the default capacity * and load factor. */ public this() { this(13); } /** * Constructs a new Hashtable using the specified capacity * and the default load factor. * * @param capacity the initial capacity */ public this(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 this(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 this(int capacity, IElementComparer comparer) { if (capacity >= 0) { elementCount = 0; elementData = new HashMapEntry[capacity is 0 ? 1 : capacity]; firstSlot = elementData.length; loadFactor = 0.75f; computeMaxSize(); } else { throw new IllegalArgumentException(null); } 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 table the original hash table to copy from * * @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 this(CustomHashtable table, IElementComparer comparer) { this(table.size() * 2, comparer); for (int i = table.elementData.length; --i >= 0;) { HashMapEntry entry = table.elementData[i]; while (entry !is null) { put(entry.key, entry.value); entry = entry.next; } } } /** * Returns the element comparer used to compare keys and to obtain * hash codes for keys, or <code>null</code> if no comparer has been * provided. * * @return the element comparer or <code>null</code> * * @since 3.2 */ public IElementComparer getComparer() { return comparer; } private void computeMaxSize() { threshold = cast(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 bool containsKey(Object key) { return getEntry(key) !is 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 is 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 = (toHash(key) & 0x7FFFFFFF) % elementData.length; HashMapEntry entry = elementData[index]; while (entry !is null) { if (keyEquals(key, entry.key)) { return entry.value; } entry = entry.next; } return null; } private HashMapEntry getEntry(Object key) { int index = (toHash(key) & 0x7FFFFFFF) % elementData.length; HashMapEntry entry = elementData[index]; while (entry !is null) { if (keyEquals(key, entry.key)) { return entry; } entry = entry.next; } return null; } /** * Answers the hash code for the given key. */ private hash_t toHash(Object key) { if (comparer is null) { return key.toHash(); } else { return comparer.toHash(key); } } /** * Compares two keys for equality. */ private bool keyEquals(Object a, Object b) { if (comparer is null) { return a.opEquals(b) !is 0; } else { return comparer.opEquals(a, b) !is 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 */ public Enumeration keys() { if (elementCount is 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 !is null && value !is null) { int index = (toHash(key) & 0x7FFFFFFF) % elementData.length; HashMapEntry entry = elementData[index]; while (entry !is null && !keyEquals(key, entry.key)) { entry = entry.next; } if (entry is null) { if (++elementCount > threshold) { rehash(); index = (toHash(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 is 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 !is null) { int index = (toHash(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 = (toHash(key) & 0x7FFFFFFF) % elementData.length; HashMapEntry entry = elementData[index]; while (entry !is null && !keyEquals(key, entry.key)) { last = entry; entry = entry.next; } if (entry !is null) { if (last is 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 override String toString() { if (size() is 0) { return "{}"; //$NON-NLS-1$ } StringBuffer buffer = new StringBuffer(); buffer.append('{'); for (int i = elementData.length; --i >= 0;) { HashMapEntry entry = elementData[i]; while (entry !is null) { if( buffer.length > 1 ){ buffer.append(", "); //$NON-NLS-1$ } buffer.append(entry.key.toString); buffer.append('='); buffer.append(entry.value.toString); entry = entry.next; } } buffer.append('}'); return buffer.toString(); } }