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