Mercurial > projects > dwt-addons
annotate 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 |
| rev | line source |
|---|---|
| 10 | 1 /******************************************************************************* |
| 2 * Copyright (c) 2000, 2006 IBM Corporation and others. | |
| 3 * All rights reserved. This program and the accompanying materials | |
| 4 * are made available under the terms of the Eclipse Public License v1.0 | |
| 5 * which accompanies this distribution, and is available at | |
| 6 * http://www.eclipse.org/legal/epl-v10.html | |
| 7 * | |
| 8 * Contributors: | |
| 9 * Peter Shipton - original hashtable implementation | |
| 10 * Nick Edgar - added element comparer support | |
| 11 * Port to the D programming language: | |
| 12 * Frank Benoit <benoit@tionex.de> | |
| 13 *******************************************************************************/ | |
| 14 | |
| 15 module dwtx.jface.viewers.CustomHashtable; | |
| 16 | |
| 17 import dwtx.jface.viewers.IElementComparer; | |
| 18 // import java.util.Enumeration; | |
| 19 // import java.util.NoSuchElementException; | |
| 20 | |
| 21 import dwt.dwthelper.utils; | |
|
104
04b47443bb01
Reworked the collection uses to make use of a wrapper collection that is compatible to the Java Collections.
Frank Benoit <benoit@tionex.de>
parents:
43
diff
changeset
|
22 import dwtx.dwtxhelper.Collection; |
| 10 | 23 import tango.core.Exception; |
| 24 static import tango.text.Text; | |
| 25 alias tango.text.Text.Text!(char) StringBuffer; | |
| 26 | |
| 27 /** | |
| 28 * CustomHashtable associates keys with values. Keys and values cannot be null. | |
| 29 * The size of the Hashtable is the number of key/value pairs it contains. | |
| 30 * The capacity is the number of key/value pairs the Hashtable can hold. | |
| 31 * The load factor is a float value which determines how full the Hashtable | |
| 32 * gets before expanding the capacity. If the load factor of the Hashtable | |
| 33 * is exceeded, the capacity is doubled. | |
| 34 * <p> | |
| 35 * CustomHashtable allows a custom comparator and hash code provider. | |
| 36 */ | |
| 37 /* package */final class CustomHashtable { | |
|
43
ea8ff534f622
Fix override and super aliases
Frank Benoit <benoit@tionex.de>
parents:
10
diff
changeset
|
38 alias Object.toHash toHash; |
| 10 | 39 |
| 40 /** | |
| 41 * HashMapEntry is an internal class which is used to hold the entries of a Hashtable. | |
| 42 */ | |
| 43 private static class HashMapEntry { | |
| 44 Object key, value; | |
| 45 | |
| 46 HashMapEntry next; | |
| 47 | |
| 48 this(Object theKey, Object theValue) { | |
| 49 key = theKey; | |
| 50 value = theValue; | |
| 51 } | |
| 52 } | |
| 53 | |
| 54 private static final class EmptyEnumerator : Enumeration { | |
| 55 public bool hasMoreElements() { | |
| 56 return false; | |
| 57 } | |
| 58 | |
| 59 public Object nextElement() { | |
| 60 throw new NoSuchElementException(null); | |
| 61 } | |
| 62 } | |
| 63 | |
| 64 private class HashEnumerator : Enumeration { | |
| 65 bool key; | |
| 66 | |
| 67 int start; | |
| 68 | |
| 69 HashMapEntry entry; | |
| 70 | |
| 71 this(bool isKey) { | |
| 72 key = isKey; | |
| 73 start = firstSlot; | |
| 74 } | |
| 75 | |
| 76 public bool hasMoreElements() { | |
| 77 if (entry !is null) { | |
| 78 return true; | |
| 79 } | |
| 80 while (start <= lastSlot) { | |
| 81 if (elementData[start++] !is null) { | |
| 82 entry = elementData[start - 1]; | |
| 83 return true; | |
| 84 } | |
| 85 } | |
| 86 return false; | |
| 87 } | |
| 88 | |
| 89 public Object nextElement() { | |
| 90 if (hasMoreElements()) { | |
| 91 Object result = key ? entry.key : entry.value; | |
| 92 entry = entry.next; | |
| 93 return result; | |
| 94 } else { | |
| 95 throw new NoSuchElementException(null); | |
| 96 } | |
| 97 } | |
| 98 } | |
| 99 | |
| 100 /+transient+/ int elementCount; | |
| 101 | |
| 102 /+transient+/ HashMapEntry[] elementData; | |
| 103 | |
| 104 private float loadFactor; | |
| 105 | |
| 106 private int threshold; | |
| 107 | |
| 108 /+transient+/ int firstSlot = 0; | |
| 109 | |
| 110 /+transient+/ int lastSlot = -1; | |
| 111 | |
| 112 /+transient+/ private IElementComparer comparer; | |
| 113 | |
| 114 private static const EmptyEnumerator emptyEnumerator; | |
| 115 static this(){ | |
| 116 emptyEnumerator = new EmptyEnumerator(); | |
| 117 } | |
| 118 | |
| 119 /** | |
| 120 * The default capacity used when not specified in the constructor. | |
| 121 */ | |
| 122 public static const int DEFAULT_CAPACITY = 13; | |
| 123 | |
| 124 /** | |
| 125 * Constructs a new Hashtable using the default capacity | |
| 126 * and load factor. | |
| 127 */ | |
| 128 public this() { | |
| 129 this(13); | |
| 130 } | |
| 131 | |
| 132 /** | |
| 133 * Constructs a new Hashtable using the specified capacity | |
| 134 * and the default load factor. | |
| 135 * | |
| 136 * @param capacity the initial capacity | |
| 137 */ | |
| 138 public this(int capacity) { | |
| 139 this(capacity, null); | |
| 140 } | |
| 141 | |
| 142 /** | |
| 143 * Constructs a new hash table with the default capacity and the given | |
| 144 * element comparer. | |
| 145 * | |
| 146 * @param comparer the element comparer to use to compare keys and obtain | |
| 147 * hash codes for keys, or <code>null</code> to use the normal | |
| 148 * <code>equals</code> and <code>hashCode</code> methods | |
| 149 */ | |
| 150 public this(IElementComparer comparer) { | |
| 151 this(DEFAULT_CAPACITY, comparer); | |
| 152 } | |
| 153 | |
| 154 /** | |
| 155 * Constructs a new hash table with the given capacity and the given | |
| 156 * element comparer. | |
| 157 * | |
| 158 * @param capacity the maximum number of elements that can be added without | |
| 159 * rehashing | |
| 160 * @param comparer the element comparer to use to compare keys and obtain | |
| 161 * hash codes for keys, or <code>null</code> to use the normal | |
| 162 * <code>equals</code> and <code>hashCode</code> methods | |
| 163 */ | |
| 164 public this(int capacity, IElementComparer comparer) { | |
| 165 if (capacity >= 0) { | |
| 166 elementCount = 0; | |
| 167 elementData = new HashMapEntry[capacity is 0 ? 1 : capacity]; | |
| 168 firstSlot = elementData.length; | |
| 169 loadFactor = 0.75f; | |
| 170 computeMaxSize(); | |
| 171 } else { | |
| 172 throw new IllegalArgumentException(null); | |
| 173 } | |
| 174 this.comparer = comparer; | |
| 175 } | |
| 176 | |
| 177 /** | |
| 178 * Constructs a new hash table with enough capacity to hold all keys in the | |
| 179 * given hash table, then adds all key/value pairs in the given hash table | |
| 180 * to the new one, using the given element comparer. | |
| 181 * @param table the original hash table to copy from | |
| 182 * | |
| 183 * @param comparer the element comparer to use to compare keys and obtain | |
| 184 * hash codes for keys, or <code>null</code> to use the normal | |
| 185 * <code>equals</code> and <code>hashCode</code> methods | |
| 186 */ | |
| 187 public this(CustomHashtable table, IElementComparer comparer) { | |
| 188 this(table.size() * 2, comparer); | |
| 189 for (int i = table.elementData.length; --i >= 0;) { | |
| 190 HashMapEntry entry = table.elementData[i]; | |
| 191 while (entry !is null) { | |
| 192 put(entry.key, entry.value); | |
| 193 entry = entry.next; | |
| 194 } | |
| 195 } | |
| 196 } | |
| 197 | |
| 198 /** | |
| 199 * Returns the element comparer used to compare keys and to obtain | |
| 200 * hash codes for keys, or <code>null</code> if no comparer has been | |
| 201 * provided. | |
| 202 * | |
| 203 * @return the element comparer or <code>null</code> | |
| 204 * | |
| 205 * @since 3.2 | |
| 206 */ | |
| 207 public IElementComparer getComparer() { | |
| 208 return comparer; | |
| 209 } | |
| 210 | |
| 211 private void computeMaxSize() { | |
| 212 threshold = cast(int) (elementData.length * loadFactor); | |
| 213 } | |
| 214 | |
| 215 /** | |
| 216 * Answers if this Hashtable contains the specified object as a key | |
| 217 * of one of the key/value pairs. | |
| 218 * | |
| 219 * @param key the object to look for as a key in this Hashtable | |
| 220 * @return true if object is a key in this Hashtable, false otherwise | |
| 221 */ | |
| 222 public bool containsKey(Object key) { | |
| 223 return getEntry(key) !is null; | |
| 224 } | |
| 225 | |
| 226 /** | |
| 227 * Answers an Enumeration on the values of this Hashtable. The | |
| 228 * results of the Enumeration may be affected if the contents | |
| 229 * of this Hashtable are modified. | |
| 230 * | |
| 231 * @return an Enumeration of the values of this Hashtable | |
| 232 */ | |
| 233 public Enumeration elements() { | |
| 234 if (elementCount is 0) { | |
| 235 return emptyEnumerator; | |
| 236 } | |
| 237 return new HashEnumerator(false); | |
| 238 } | |
| 239 | |
| 240 /** | |
| 241 * Answers the value associated with the specified key in | |
| 242 * this Hashtable. | |
| 243 * | |
| 244 * @param key the key of the value returned | |
| 245 * @return the value associated with the specified key, null if the specified key | |
| 246 * does not exist | |
| 247 */ | |
| 248 public Object get(Object key) { | |
| 249 int index = (toHash(key) & 0x7FFFFFFF) % elementData.length; | |
| 250 HashMapEntry entry = elementData[index]; | |
| 251 while (entry !is null) { | |
| 252 if (keyEquals(key, entry.key)) { | |
| 253 return entry.value; | |
| 254 } | |
| 255 entry = entry.next; | |
| 256 } | |
| 257 return null; | |
| 258 } | |
| 259 | |
| 260 private HashMapEntry getEntry(Object key) { | |
| 261 int index = (toHash(key) & 0x7FFFFFFF) % elementData.length; | |
| 262 HashMapEntry entry = elementData[index]; | |
| 263 while (entry !is null) { | |
| 264 if (keyEquals(key, entry.key)) { | |
| 265 return entry; | |
| 266 } | |
| 267 entry = entry.next; | |
| 268 } | |
| 269 return null; | |
| 270 } | |
| 271 | |
| 272 /** | |
| 273 * Answers the hash code for the given key. | |
| 274 */ | |
| 275 private hash_t toHash(Object key) { | |
| 276 if (comparer is null) { | |
| 277 return key.toHash(); | |
| 278 } else { | |
| 279 return comparer.toHash(key); | |
| 280 } | |
| 281 } | |
| 282 | |
| 283 /** | |
| 284 * Compares two keys for equality. | |
| 285 */ | |
| 286 private bool keyEquals(Object a, Object b) { | |
| 287 if (comparer is null) { | |
| 288 return a.opEquals(b) !is 0; | |
| 289 } else { | |
| 290 return comparer.opEquals(a, b) !is 0; | |
| 291 } | |
| 292 } | |
| 293 | |
| 294 /** | |
| 295 * Answers an Enumeration on the keys of this Hashtable. The | |
| 296 * results of the Enumeration may be affected if the contents | |
| 297 * of this Hashtable are modified. | |
| 298 * | |
| 299 * @return an Enumeration of the keys of this Hashtable | |
| 300 */ | |
| 301 public Enumeration keys() { | |
| 302 if (elementCount is 0) { | |
| 303 return emptyEnumerator; | |
| 304 } | |
| 305 return new HashEnumerator(true); | |
| 306 } | |
| 307 | |
| 308 /** | |
| 309 * Associate the specified value with the specified key in this Hashtable. | |
| 310 * If the key already exists, the old value is replaced. The key and value | |
| 311 * cannot be null. | |
| 312 * | |
| 313 * @param key the key to add | |
| 314 * @param value the value to add | |
| 315 * @return the old value associated with the specified key, null if the key did | |
| 316 * not exist | |
| 317 */ | |
| 318 public Object put(Object key, Object value) { | |
| 319 if (key !is null && value !is null) { | |
| 320 int index = (toHash(key) & 0x7FFFFFFF) % elementData.length; | |
| 321 HashMapEntry entry = elementData[index]; | |
| 322 while (entry !is null && !keyEquals(key, entry.key)) { | |
| 323 entry = entry.next; | |
| 324 } | |
| 325 if (entry is null) { | |
| 326 if (++elementCount > threshold) { | |
| 327 rehash(); | |
| 328 index = (toHash(key) & 0x7FFFFFFF) % elementData.length; | |
| 329 } | |
| 330 if (index < firstSlot) { | |
| 331 firstSlot = index; | |
| 332 } | |
| 333 if (index > lastSlot) { | |
| 334 lastSlot = index; | |
| 335 } | |
| 336 entry = new HashMapEntry(key, value); | |
| 337 entry.next = elementData[index]; | |
| 338 elementData[index] = entry; | |
| 339 return null; | |
| 340 } | |
| 341 Object result = entry.value; | |
| 342 entry.key = key; // important to avoid hanging onto keys that are equal but "old" -- see bug 30607 | |
| 343 entry.value = value; | |
| 344 return result; | |
| 345 } else { | |
| 346 throw new NullPointerException(); | |
| 347 } | |
| 348 } | |
| 349 | |
| 350 /** | |
| 351 * Increases the capacity of this Hashtable. This method is sent when | |
| 352 * the size of this Hashtable exceeds the load factor. | |
| 353 */ | |
| 354 private void rehash() { | |
| 355 int length = elementData.length << 1; | |
| 356 if (length is 0) { | |
| 357 length = 1; | |
| 358 } | |
| 359 firstSlot = length; | |
| 360 lastSlot = -1; | |
| 361 HashMapEntry[] newData = new HashMapEntry[length]; | |
| 362 for (int i = elementData.length; --i >= 0;) { | |
| 363 HashMapEntry entry = elementData[i]; | |
| 364 while (entry !is null) { | |
| 365 int index = (toHash(entry.key) & 0x7FFFFFFF) % length; | |
| 366 if (index < firstSlot) { | |
| 367 firstSlot = index; | |
| 368 } | |
| 369 if (index > lastSlot) { | |
| 370 lastSlot = index; | |
| 371 } | |
| 372 HashMapEntry next = entry.next; | |
| 373 entry.next = newData[index]; | |
| 374 newData[index] = entry; | |
| 375 entry = next; | |
| 376 } | |
| 377 } | |
| 378 elementData = newData; | |
| 379 computeMaxSize(); | |
| 380 } | |
| 381 | |
| 382 /** | |
| 383 * Remove the key/value pair with the specified key from this Hashtable. | |
| 384 * | |
| 385 * @param key the key to remove | |
| 386 * @return the value associated with the specified key, null if the specified key | |
| 387 * did not exist | |
| 388 */ | |
| 389 public Object remove(Object key) { | |
| 390 HashMapEntry last = null; | |
| 391 int index = (toHash(key) & 0x7FFFFFFF) % elementData.length; | |
| 392 HashMapEntry entry = elementData[index]; | |
| 393 while (entry !is null && !keyEquals(key, entry.key)) { | |
| 394 last = entry; | |
| 395 entry = entry.next; | |
| 396 } | |
| 397 if (entry !is null) { | |
| 398 if (last is null) { | |
| 399 elementData[index] = entry.next; | |
| 400 } else { | |
| 401 last.next = entry.next; | |
| 402 } | |
| 403 elementCount--; | |
| 404 return entry.value; | |
| 405 } | |
| 406 return null; | |
| 407 } | |
| 408 | |
| 409 /** | |
| 410 * Answers the number of key/value pairs in this Hashtable. | |
| 411 * | |
| 412 * @return the number of key/value pairs in this Hashtable | |
| 413 */ | |
| 414 public int size() { | |
| 415 return elementCount; | |
| 416 } | |
| 417 | |
| 418 /** | |
| 419 * Answers the string representation of this Hashtable. | |
| 420 * | |
| 421 * @return the string representation of this Hashtable | |
| 422 */ | |
| 423 public override String toString() { | |
| 424 if (size() is 0) { | |
| 425 return "{}"; //$NON-NLS-1$ | |
| 426 } | |
| 427 | |
| 428 StringBuffer buffer = new StringBuffer(); | |
| 429 buffer.append('{'); | |
| 430 for (int i = elementData.length; --i >= 0;) { | |
| 431 HashMapEntry entry = elementData[i]; | |
| 432 while (entry !is null) { | |
| 433 if( buffer.length > 1 ){ | |
| 434 buffer.append(", "); //$NON-NLS-1$ | |
| 435 } | |
| 436 buffer.append(entry.key.toString); | |
| 437 buffer.append('='); | |
| 438 buffer.append(entry.value.toString); | |
| 439 entry = entry.next; | |
| 440 } | |
| 441 } | |
| 442 buffer.append('}'); | |
| 443 return buffer.toString(); | |
| 444 } | |
| 445 } |