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