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