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: 799857 $ $Date: 2009-08-01 09:07:12 -0400 (Sat, 01 Aug 2009) $
040 * @since 2.0
041 */
042 public class OpenIntToFieldHashMap<T extends FieldElement<T>> implements Serializable {
043
044 /** Serializable version identifier. */
045 private static final long serialVersionUID = -9179080286849120720L;
046
047 /** Load factor for the map. */
048 private static final float LOAD_FACTOR = 0.5f;
049
050 /** Default starting size.
051 * <p>This must be a power of two for bit mask to work properly. </p>
052 */
053 private static final int DEFAULT_EXPECTED_SIZE = 16;
054
055 /** Multiplier for size growth when map fills up.
056 * <p>This must be a power of two for bit mask to work properly. </p>
057 */
058 private static final int RESIZE_MULTIPLIER = 2;
059
060 /** Number of bits to perturb the index when probing for collision resolution. */
061 private static final int PERTURB_SHIFT = 5;
062
063 /** Status indicator for free table entries. */
064 protected static final byte FREE = 0;
065
066 /** Status indicator for full table entries. */
067 protected static final byte FULL = 1;
068
069 /** Status indicator for removed table entries. */
070 protected static final byte REMOVED = 2;
071
072 /** Field to which the elements belong. */
073 private final Field<T> field;
074
075 /** Keys table. */
076 private int[] keys;
077
078 /** Values table. */
079 private T[] values;
080
081 /** States table. */
082 private byte[] states;
083
084 /** Return value for missing entries. */
085 private final T missingEntries;
086
087 /** Current size of the map. */
088 private int size;
089
090 /** Bit mask for hash values. */
091 private int mask;
092
093 /** Modifications count. */
094 private transient int count;
095
096 /**
097 * Build an empty map with default size and using zero for missing entries.
098 * @param field field to which the elements belong
099 */
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 for (int perturb = perturb(hash), j = index; states[index] != FREE; perturb >>= PERTURB_SHIFT) {
202 j = probe(perturb, j);
203 index = j & mask;
204 if (containsKey(key, index)) {
205 return values[index];
206 }
207 }
208
209 return missingEntries;
210
211 }
212
213 /**
214 * Check if a value is associated with a key.
215 * @param key key to check
216 * @return true if a value is associated with key
217 */
218 public boolean containsKey(final int key) {
219
220 final int hash = hashOf(key);
221 int index = hash & mask;
222 if (containsKey(key, index)) {
223 return true;
224 }
225
226 if (states[index] == FREE) {
227 return false;
228 }
229
230 for (int perturb = perturb(hash), j = index; states[index] != FREE; perturb >>= PERTURB_SHIFT) {
231 j = probe(perturb, j);
232 index = j & mask;
233 if (containsKey(key, index)) {
234 return true;
235 }
236 }
237
238 return false;
239
240 }
241
242 /**
243 * Get an iterator over map elements.
244 * <p>The specialized iterators returned are fail-fast: they throw a
245 * <code>ConcurrentModificationException</code> when they detect the map
246 * has been modified during iteration.</p>
247 * @return iterator over the map elements
248 */
249 public Iterator iterator() {
250 return new Iterator();
251 }
252
253 /**
254 * Perturb the hash for starting probing.
255 * @param hash initial hash
256 * @return perturbed hash
257 */
258 private static int perturb(final int hash) {
259 return hash & 0x7fffffff;
260 }
261
262 /**
263 * Find the index at which a key should be inserted
264 * @param key key to lookup
265 * @return index at which key should be inserted
266 */
267 private int findInsertionIndex(final int key) {
268 return findInsertionIndex(keys, states, key, mask);
269 }
270
271 /**
272 * Find the index at which a key should be inserted
273 * @param keys keys table
274 * @param states states table
275 * @param key key to lookup
276 * @param mask bit mask for hash values
277 * @return index at which key should be inserted
278 */
279 private static int findInsertionIndex(final int[] keys, final byte[] states,
280 final int key, final int mask) {
281 final int hash = hashOf(key);
282 int index = hash & mask;
283 if (states[index] == FREE) {
284 return index;
285 } else if (states[index] == FULL && keys[index] == key) {
286 return changeIndexSign(index);
287 }
288
289 int perturb = perturb(hash);
290 int j = index;
291 if (states[index] == FULL) {
292 while (true) {
293 j = probe(perturb, j);
294 index = j & mask;
295 perturb >>= PERTURB_SHIFT;
296
297 if (states[index] != FULL || keys[index] == key) {
298 break;
299 }
300 }
301 }
302
303 if (states[index] == FREE) {
304 return index;
305 } else if (states[index] == FULL) {
306 // due to the loop exit condition,
307 // if (states[index] == FULL) then keys[index] == key
308 return changeIndexSign(index);
309 }
310
311 final int firstRemoved = index;
312 while (true) {
313 j = probe(perturb, j);
314 index = j & mask;
315
316 if (states[index] == FREE) {
317 return firstRemoved;
318 } else if (states[index] == FULL && keys[index] == key) {
319 return changeIndexSign(index);
320 }
321
322 perturb >>= PERTURB_SHIFT;
323
324 }
325
326 }
327
328 /**
329 * Compute next probe for collision resolution
330 * @param perturb perturbed hash
331 * @param j previous probe
332 * @return next probe
333 */
334 private static int probe(final int perturb, final int j) {
335 return (j << 2) + j + perturb + 1;
336 }
337
338 /**
339 * Change the index sign
340 * @param index initial index
341 * @return changed index
342 */
343 private static int changeIndexSign(final int index) {
344 return -index - 1;
345 }
346
347 /**
348 * Get the number of elements stored in the map.
349 * @return number of elements stored in the map
350 */
351 public int size() {
352 return size;
353 }
354
355
356 /**
357 * Remove the value associated with a key.
358 * @param key key to which the value is associated
359 * @return removed value
360 */
361 public T remove(final int key) {
362
363 final int hash = hashOf(key);
364 int index = hash & mask;
365 if (containsKey(key, index)) {
366 return doRemove(index);
367 }
368
369 if (states[index] == FREE) {
370 return missingEntries;
371 }
372
373 for (int perturb = perturb(hash), j = index; states[index] != FREE; perturb >>= PERTURB_SHIFT) {
374 j = probe(perturb, j);
375 index = j & mask;
376 if (containsKey(key, index)) {
377 return doRemove(index);
378 }
379 }
380
381 return missingEntries;
382
383 }
384
385 /**
386 * Check if the tables contain an element associated with specified key
387 * at specified index.
388 * @param key key to check
389 * @param index index to check
390 * @return true if an element is associated with key at index
391 */
392 private boolean containsKey(final int key, final int index) {
393 return (key != 0 || states[index] == FULL) && keys[index] == key;
394 }
395
396 /**
397 * Remove an element at specified index.
398 * @param index index of the element to remove
399 * @return removed value
400 */
401 private T doRemove(int index) {
402 keys[index] = 0;
403 states[index] = REMOVED;
404 final T previous = values[index];
405 values[index] = missingEntries;
406 --size;
407 ++count;
408 return previous;
409 }
410
411 /**
412 * Put a value associated with a key in the map.
413 * @param key key to which value is associated
414 * @param value value to put in the map
415 * @return previous value associated with the key
416 */
417 public T put(final int key, final T value) {
418 int index = findInsertionIndex(key);
419 T previous = missingEntries;
420 boolean newMapping = true;
421 if (index < 0) {
422 index = changeIndexSign(index);
423 previous = values[index];
424 newMapping = false;
425 }
426 keys[index] = key;
427 states[index] = FULL;
428 values[index] = value;
429 if (newMapping) {
430 ++size;
431 if (shouldGrowTable()) {
432 growTable();
433 }
434 ++count;
435 }
436 return previous;
437
438 }
439
440 /**
441 * Grow the tables.
442 */
443 private void growTable() {
444
445 final int oldLength = states.length;
446 final int[] oldKeys = keys;
447 final T[] oldValues = values;
448 final byte[] oldStates = states;
449
450 final int newLength = RESIZE_MULTIPLIER * oldLength;
451 final int[] newKeys = new int[newLength];
452 final T[] newValues = buildArray(newLength);
453 final byte[] newStates = new byte[newLength];
454 final int newMask = newLength - 1;
455 for (int i = 0; i < oldLength; ++i) {
456 if (oldStates[i] == FULL) {
457 final int key = oldKeys[i];
458 final int index = findInsertionIndex(newKeys, newStates, key, newMask);
459 newKeys[index] = key;
460 newValues[index] = oldValues[i];
461 newStates[index] = FULL;
462 }
463 }
464
465 mask = newMask;
466 keys = newKeys;
467 values = newValues;
468 states = newStates;
469
470 }
471
472 /**
473 * Check if tables should grow due to increased size.
474 * @return true if tables should grow
475 */
476 private boolean shouldGrowTable() {
477 return size > (mask + 1) * LOAD_FACTOR;
478 }
479
480 /**
481 * Compute the hash value of a key
482 * @param key key to hash
483 * @return hash value of the key
484 */
485 private static int hashOf(final int key) {
486 final int h = key ^ ((key >>> 20) ^ (key >>> 12));
487 return h ^ (h >>> 7) ^ (h >>> 4);
488 }
489
490
491 /** Iterator class for the map. */
492 public class Iterator {
493
494 /** Reference modification count. */
495 private final int referenceCount;
496
497 /** Index of current element. */
498 private int current;
499
500 /** Index of next element. */
501 private int next;
502
503 /**
504 * Simple constructor.
505 */
506 private Iterator() {
507
508 // preserve the modification count of the map to detect concurrent modifications later
509 referenceCount = count;
510
511 // initialize current index
512 next = -1;
513 try {
514 advance();
515 } catch (NoSuchElementException nsee) {
516 // ignored
517 }
518
519 }
520
521 /**
522 * Check if there is a next element in the map.
523 * @return true if there is a next element
524 */
525 public boolean hasNext() {
526 return next >= 0;
527 }
528
529 /**
530 * Get the key of current entry.
531 * @return key of current entry
532 * @exception ConcurrentModificationException if the map is modified during iteration
533 * @exception NoSuchElementException if there is no element left in the map
534 */
535 public int key()
536 throws ConcurrentModificationException, NoSuchElementException {
537 if (referenceCount != count) {
538 throw MathRuntimeException.createConcurrentModificationException("map has been modified while iterating");
539 }
540 if (current < 0) {
541 throw MathRuntimeException.createNoSuchElementException("iterator exhausted");
542 }
543 return keys[current];
544 }
545
546 /**
547 * Get the value of current entry.
548 * @return value of current entry
549 * @exception ConcurrentModificationException if the map is modified during iteration
550 * @exception NoSuchElementException if there is no element left in the map
551 */
552 public T value()
553 throws ConcurrentModificationException, NoSuchElementException {
554 if (referenceCount != count) {
555 throw MathRuntimeException.createConcurrentModificationException("map has been modified while iterating");
556 }
557 if (current < 0) {
558 throw MathRuntimeException.createNoSuchElementException("iterator exhausted");
559 }
560 return values[current];
561 }
562
563 /**
564 * Advance iterator one step further.
565 * @exception ConcurrentModificationException if the map is modified during iteration
566 * @exception NoSuchElementException if there is no element left in the map
567 */
568 public void advance()
569 throws ConcurrentModificationException, NoSuchElementException {
570
571 if (referenceCount != count) {
572 throw MathRuntimeException.createConcurrentModificationException("map has been modified while iterating");
573 }
574
575 // advance on step
576 current = next;
577
578 // prepare next step
579 try {
580 while (states[++next] != FULL) {
581 // nothing to do
582 }
583 } catch (ArrayIndexOutOfBoundsException e) {
584 next = -2;
585 if (current < 0) {
586 throw MathRuntimeException.createNoSuchElementException("iterator exhausted");
587 }
588 }
589
590 }
591
592 }
593
594 /**
595 * Read a serialized object.
596 * @param stream input stream
597 * @throws IOException if object cannot be read
598 * @throws ClassNotFoundException if the class corresponding
599 * to the serialized object cannot be found
600 */
601 private void readObject(final ObjectInputStream stream)
602 throws IOException, ClassNotFoundException {
603 stream.defaultReadObject();
604 count = 0;
605 }
606
607 /** Build an array of elements.
608 * @param length size of the array to build
609 * @return a new array
610 */
611 @SuppressWarnings("unchecked")
612 private T[] buildArray(final int length) {
613 return (T[]) Array.newInstance(field.getZero().getClass(), length);
614 }
615
616 }