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