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