1 /*
2 * Licensed to the Apache Software Foundation (ASF) under one or more
3 * contributor license agreements. See the NOTICE file distributed with
4 * this work for additional information regarding copyright ownership.
5 * The ASF licenses this file to You under the Apache License, Version 2.0
6 * (the "License"); you may not use this file except in compliance with
7 * the License. You may obtain a copy of the License at
8 *
9 * http://www.apache.org/licenses/LICENSE-2.0
10 *
11 * Unless required by applicable law or agreed to in writing, software
12 * distributed under the License is distributed on an "AS IS" BASIS,
13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 * See the License for the specific language governing permissions and
15 * limitations under the License.
16 */
17 package org.apache.commons.math.util;
18
19 import java.io.IOException;
20 import java.io.ObjectInputStream;
21 import java.io.Serializable;
22 import java.lang.reflect.Array;
23 import java.util.ConcurrentModificationException;
24 import java.util.NoSuchElementException;
25
26 import org.apache.commons.math.Field;
27 import org.apache.commons.math.FieldElement;
28 import org.apache.commons.math.MathRuntimeException;
29
30 /**
31 * Open addressed map from int to FieldElement.
32 * <p>This class provides a dedicated map from integers to FieldElements with a
33 * much smaller memory overhead than standard <code>java.util.Map</code>.</p>
34 * <p>This class is not synchronized. The specialized iterators returned by
35 * {@link #iterator()} are fail-fast: they throw a
36 * <code>ConcurrentModificationException</code> when they detect the map has been
37 * modified during iteration.</p>
38 * @param <T> the type of the field elements
39 * @version $Revision: 825919 $ $Date: 2009-10-16 10:51:55 -0400 (Fri, 16 Oct 2009) $
40 * @since 2.0
41 */
42 public class OpenIntToFieldHashMap<T extends FieldElement<T>> implements Serializable {
43
44 /** Status indicator for free table entries. */
45 protected static final byte FREE = 0;
46
47 /** Status indicator for full table entries. */
48 protected static final byte FULL = 1;
49
50 /** Status indicator for removed table entries. */
51 protected static final byte REMOVED = 2;
52
53 /** Serializable version identifier. */
54 private static final long serialVersionUID = -9179080286849120720L;
55
56 /** Load factor for the map. */
57 private static final float LOAD_FACTOR = 0.5f;
58
59 /** Default starting size.
60 * <p>This must be a power of two for bit mask to work properly. </p>
61 */
62 private static final int DEFAULT_EXPECTED_SIZE = 16;
63
64 /** Multiplier for size growth when map fills up.
65 * <p>This must be a power of two for bit mask to work properly. </p>
66 */
67 private static final int RESIZE_MULTIPLIER = 2;
68
69 /** Number of bits to perturb the index when probing for collision resolution. */
70 private static final int PERTURB_SHIFT = 5;
71
72 /** Field to which the elements belong. */
73 private final Field<T> field;
74
75 /** Keys table. */
76 private int[] keys;
77
78 /** Values table. */
79 private T[] values;
80
81 /** States table. */
82 private byte[] states;
83
84 /** Return value for missing entries. */
85 private final T missingEntries;
86
87 /** Current size of the map. */
88 private int size;
89
90 /** Bit mask for hash values. */
91 private int mask;
92
93 /** Modifications count. */
94 private transient int count;
95
96 /**
97 * Build an empty map with default size and using zero for missing entries.
98 * @param field field to which the elements belong
99 */
100 public OpenIntToFieldHashMap(final Field<T>field) {
101 this(field, DEFAULT_EXPECTED_SIZE, field.getZero());
102 }
103
104 /**
105 * Build an empty map with default size
106 * @param field field to which the elements belong
107 * @param missingEntries value to return when a missing entry is fetched
108 */
109 public OpenIntToFieldHashMap(final Field<T>field, final T missingEntries) {
110 this(field,DEFAULT_EXPECTED_SIZE, missingEntries);
111 }
112
113 /**
114 * Build an empty map with specified size and using zero for missing entries.
115 * @param field field to which the elements belong
116 * @param expectedSize expected number of elements in the map
117 */
118 public OpenIntToFieldHashMap(final Field<T> field,final int expectedSize) {
119 this(field,expectedSize, field.getZero());
120 }
121
122 /**
123 * Build an empty map with specified size.
124 * @param field field to which the elements belong
125 * @param expectedSize expected number of elements in the map
126 * @param missingEntries value to return when a missing entry is fetched
127 */
128 public OpenIntToFieldHashMap(final Field<T> field,final int expectedSize,
129 final T missingEntries) {
130 this.field = field;
131 final int capacity = computeCapacity(expectedSize);
132 keys = new int[capacity];
133 values = buildArray(capacity);
134 states = new byte[capacity];
135 this.missingEntries = missingEntries;
136 mask = capacity - 1;
137 }
138
139 /**
140 * Copy constructor.
141 * @param source map to copy
142 */
143 public OpenIntToFieldHashMap(final OpenIntToFieldHashMap<T> source) {
144 field = source.field;
145 final int length = source.keys.length;
146 keys = new int[length];
147 System.arraycopy(source.keys, 0, keys, 0, length);
148 values = buildArray(length);
149 System.arraycopy(source.values, 0, values, 0, length);
150 states = new byte[length];
151 System.arraycopy(source.states, 0, states, 0, length);
152 missingEntries = source.missingEntries;
153 size = source.size;
154 mask = source.mask;
155 count = source.count;
156 }
157
158 /**
159 * Compute the capacity needed for a given size.
160 * @param expectedSize expected size of the map
161 * @return capacity to use for the specified size
162 */
163 private static int computeCapacity(final int expectedSize) {
164 if (expectedSize == 0) {
165 return 1;
166 }
167 final int capacity = (int) Math.ceil(expectedSize / LOAD_FACTOR);
168 final int powerOfTwo = Integer.highestOneBit(capacity);
169 if (powerOfTwo == capacity) {
170 return capacity;
171 }
172 return nextPowerOfTwo(capacity);
173 }
174
175 /**
176 * Find the smallest power of two greater than the input value
177 * @param i input value
178 * @return smallest power of two greater than the input value
179 */
180 private static int nextPowerOfTwo(final int i) {
181 return Integer.highestOneBit(i) << 1;
182 }
183
184 /**
185 * Get the stored value associated with the given key
186 * @param key key associated with the data
187 * @return data associated with the key
188 */
189 public T get(final int key) {
190
191 final int hash = hashOf(key);
192 int index = hash & mask;
193 if (containsKey(key, index)) {
194 return values[index];
195 }
196
197 if (states[index] == FREE) {
198 return missingEntries;
199 }
200
201 int j = index;
202 for (int perturb = perturb(hash); states[index] != FREE; perturb >>= PERTURB_SHIFT) {
203 j = probe(perturb, j);
204 index = j & mask;
205 if (containsKey(key, index)) {
206 return values[index];
207 }
208 }
209
210 return missingEntries;
211
212 }
213
214 /**
215 * Check if a value is associated with a key.
216 * @param key key to check
217 * @return true if a value is associated with key
218 */
219 public boolean containsKey(final int key) {
220
221 final int hash = hashOf(key);
222 int index = hash & mask;
223 if (containsKey(key, index)) {
224 return true;
225 }
226
227 if (states[index] == FREE) {
228 return false;
229 }
230
231 int j = index;
232 for (int perturb = perturb(hash); states[index] != FREE; perturb >>= PERTURB_SHIFT) {
233 j = probe(perturb, j);
234 index = j & mask;
235 if (containsKey(key, index)) {
236 return true;
237 }
238 }
239
240 return false;
241
242 }
243
244 /**
245 * Get an iterator over map elements.
246 * <p>The specialized iterators returned are fail-fast: they throw a
247 * <code>ConcurrentModificationException</code> when they detect the map
248 * has been modified during iteration.</p>
249 * @return iterator over the map elements
250 */
251 public Iterator iterator() {
252 return new Iterator();
253 }
254
255 /**
256 * Perturb the hash for starting probing.
257 * @param hash initial hash
258 * @return perturbed hash
259 */
260 private static int perturb(final int hash) {
261 return hash & 0x7fffffff;
262 }
263
264 /**
265 * Find the index at which a key should be inserted
266 * @param key key to lookup
267 * @return index at which key should be inserted
268 */
269 private int findInsertionIndex(final int key) {
270 return findInsertionIndex(keys, states, key, mask);
271 }
272
273 /**
274 * Find the index at which a key should be inserted
275 * @param keys keys table
276 * @param states states table
277 * @param key key to lookup
278 * @param mask bit mask for hash values
279 * @return index at which key should be inserted
280 */
281 private static int findInsertionIndex(final int[] keys, final byte[] states,
282 final int key, final int mask) {
283 final int hash = hashOf(key);
284 int index = hash & mask;
285 if (states[index] == FREE) {
286 return index;
287 } else if (states[index] == FULL && keys[index] == key) {
288 return changeIndexSign(index);
289 }
290
291 int perturb = perturb(hash);
292 int j = index;
293 if (states[index] == FULL) {
294 while (true) {
295 j = probe(perturb, j);
296 index = j & mask;
297 perturb >>= PERTURB_SHIFT;
298
299 if (states[index] != FULL || keys[index] == key) {
300 break;
301 }
302 }
303 }
304
305 if (states[index] == FREE) {
306 return index;
307 } else if (states[index] == FULL) {
308 // due to the loop exit condition,
309 // if (states[index] == FULL) then keys[index] == key
310 return changeIndexSign(index);
311 }
312
313 final int firstRemoved = index;
314 while (true) {
315 j = probe(perturb, j);
316 index = j & mask;
317
318 if (states[index] == FREE) {
319 return firstRemoved;
320 } else if (states[index] == FULL && keys[index] == key) {
321 return changeIndexSign(index);
322 }
323
324 perturb >>= PERTURB_SHIFT;
325
326 }
327
328 }
329
330 /**
331 * Compute next probe for collision resolution
332 * @param perturb perturbed hash
333 * @param j previous probe
334 * @return next probe
335 */
336 private static int probe(final int perturb, final int j) {
337 return (j << 2) + j + perturb + 1;
338 }
339
340 /**
341 * Change the index sign
342 * @param index initial index
343 * @return changed index
344 */
345 private static int changeIndexSign(final int index) {
346 return -index - 1;
347 }
348
349 /**
350 * Get the number of elements stored in the map.
351 * @return number of elements stored in the map
352 */
353 public int size() {
354 return size;
355 }
356
357
358 /**
359 * Remove the value associated with a key.
360 * @param key key to which the value is associated
361 * @return removed value
362 */
363 public T remove(final int key) {
364
365 final int hash = hashOf(key);
366 int index = hash & mask;
367 if (containsKey(key, index)) {
368 return doRemove(index);
369 }
370
371 if (states[index] == FREE) {
372 return missingEntries;
373 }
374
375 int j = index;
376 for (int perturb = perturb(hash); states[index] != FREE; perturb >>= PERTURB_SHIFT) {
377 j = probe(perturb, j);
378 index = j & mask;
379 if (containsKey(key, index)) {
380 return doRemove(index);
381 }
382 }
383
384 return missingEntries;
385
386 }
387
388 /**
389 * Check if the tables contain an element associated with specified key
390 * at specified index.
391 * @param key key to check
392 * @param index index to check
393 * @return true if an element is associated with key at index
394 */
395 private boolean containsKey(final int key, final int index) {
396 return (key != 0 || states[index] == FULL) && keys[index] == key;
397 }
398
399 /**
400 * Remove an element at specified index.
401 * @param index index of the element to remove
402 * @return removed value
403 */
404 private T doRemove(int index) {
405 keys[index] = 0;
406 states[index] = REMOVED;
407 final T previous = values[index];
408 values[index] = missingEntries;
409 --size;
410 ++count;
411 return previous;
412 }
413
414 /**
415 * Put a value associated with a key in the map.
416 * @param key key to which value is associated
417 * @param value value to put in the map
418 * @return previous value associated with the key
419 */
420 public T put(final int key, final T value) {
421 int index = findInsertionIndex(key);
422 T previous = missingEntries;
423 boolean newMapping = true;
424 if (index < 0) {
425 index = changeIndexSign(index);
426 previous = values[index];
427 newMapping = false;
428 }
429 keys[index] = key;
430 states[index] = FULL;
431 values[index] = value;
432 if (newMapping) {
433 ++size;
434 if (shouldGrowTable()) {
435 growTable();
436 }
437 ++count;
438 }
439 return previous;
440
441 }
442
443 /**
444 * Grow the tables.
445 */
446 private void growTable() {
447
448 final int oldLength = states.length;
449 final int[] oldKeys = keys;
450 final T[] oldValues = values;
451 final byte[] oldStates = states;
452
453 final int newLength = RESIZE_MULTIPLIER * oldLength;
454 final int[] newKeys = new int[newLength];
455 final T[] newValues = buildArray(newLength);
456 final byte[] newStates = new byte[newLength];
457 final int newMask = newLength - 1;
458 for (int i = 0; i < oldLength; ++i) {
459 if (oldStates[i] == FULL) {
460 final int key = oldKeys[i];
461 final int index = findInsertionIndex(newKeys, newStates, key, newMask);
462 newKeys[index] = key;
463 newValues[index] = oldValues[i];
464 newStates[index] = FULL;
465 }
466 }
467
468 mask = newMask;
469 keys = newKeys;
470 values = newValues;
471 states = newStates;
472
473 }
474
475 /**
476 * Check if tables should grow due to increased size.
477 * @return true if tables should grow
478 */
479 private boolean shouldGrowTable() {
480 return size > (mask + 1) * LOAD_FACTOR;
481 }
482
483 /**
484 * Compute the hash value of a key
485 * @param key key to hash
486 * @return hash value of the key
487 */
488 private static int hashOf(final int key) {
489 final int h = key ^ ((key >>> 20) ^ (key >>> 12));
490 return h ^ (h >>> 7) ^ (h >>> 4);
491 }
492
493
494 /** Iterator class for the map. */
495 public class Iterator {
496
497 /** Reference modification count. */
498 private final int referenceCount;
499
500 /** Index of current element. */
501 private int current;
502
503 /** Index of next element. */
504 private int next;
505
506 /**
507 * Simple constructor.
508 */
509 private Iterator() {
510
511 // preserve the modification count of the map to detect concurrent modifications later
512 referenceCount = count;
513
514 // initialize current index
515 next = -1;
516 try {
517 advance();
518 } catch (NoSuchElementException nsee) {
519 // ignored
520 }
521
522 }
523
524 /**
525 * Check if there is a next element in the map.
526 * @return true if there is a next element
527 */
528 public boolean hasNext() {
529 return next >= 0;
530 }
531
532 /**
533 * Get the key of current entry.
534 * @return key of current entry
535 * @exception ConcurrentModificationException if the map is modified during iteration
536 * @exception NoSuchElementException if there is no element left in the map
537 */
538 public int key()
539 throws ConcurrentModificationException, NoSuchElementException {
540 if (referenceCount != count) {
541 throw MathRuntimeException.createConcurrentModificationException("map has been modified while iterating");
542 }
543 if (current < 0) {
544 throw MathRuntimeException.createNoSuchElementException("iterator exhausted");
545 }
546 return keys[current];
547 }
548
549 /**
550 * Get the value of current entry.
551 * @return value of current entry
552 * @exception ConcurrentModificationException if the map is modified during iteration
553 * @exception NoSuchElementException if there is no element left in the map
554 */
555 public T value()
556 throws ConcurrentModificationException, NoSuchElementException {
557 if (referenceCount != count) {
558 throw MathRuntimeException.createConcurrentModificationException("map has been modified while iterating");
559 }
560 if (current < 0) {
561 throw MathRuntimeException.createNoSuchElementException("iterator exhausted");
562 }
563 return values[current];
564 }
565
566 /**
567 * Advance iterator one step further.
568 * @exception ConcurrentModificationException if the map is modified during iteration
569 * @exception NoSuchElementException if there is no element left in the map
570 */
571 public void advance()
572 throws ConcurrentModificationException, NoSuchElementException {
573
574 if (referenceCount != count) {
575 throw MathRuntimeException.createConcurrentModificationException("map has been modified while iterating");
576 }
577
578 // advance on step
579 current = next;
580
581 // prepare next step
582 try {
583 while (states[++next] != FULL) {
584 // nothing to do
585 }
586 } catch (ArrayIndexOutOfBoundsException e) {
587 next = -2;
588 if (current < 0) {
589 throw MathRuntimeException.createNoSuchElementException("iterator exhausted");
590 }
591 }
592
593 }
594
595 }
596
597 /**
598 * Read a serialized object.
599 * @param stream input stream
600 * @throws IOException if object cannot be read
601 * @throws ClassNotFoundException if the class corresponding
602 * to the serialized object cannot be found
603 */
604 private void readObject(final ObjectInputStream stream)
605 throws IOException, ClassNotFoundException {
606 stream.defaultReadObject();
607 count = 0;
608 }
609
610 /** Build an array of elements.
611 * @param length size of the array to build
612 * @return a new array
613 */
614 @SuppressWarnings("unchecked")
615 private T[] buildArray(final int length) {
616 return (T[]) Array.newInstance(field.getZero().getClass(), length);
617 }
618
619 }