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