1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21 package org.millscript.commons.util.map;
22
23 import java.io.IOException;
24 import java.io.ObjectInputStream;
25 import java.io.ObjectOutputStream;
26 import java.io.Serializable;
27
28 import org.millscript.commons.alert.alerts.Fault;
29 import org.millscript.commons.util.IList;
30 import org.millscript.commons.util.IMap;
31 import org.millscript.commons.util.ListIterator;
32 import org.millscript.commons.util.MapIterator;
33 import org.millscript.commons.util.Maplet;
34 import org.millscript.commons.util.alerts.ListIndexOutOfBoundsAlert;
35 import org.millscript.commons.util.alerts.NoSuchKeyInMapAlert;
36 import org.millscript.commons.util.iterator.AbstractListIterator;
37 import org.millscript.commons.util.iterator.AbstractMapIterator;
38 import org.millscript.commons.util.iterator.ArrayListIterator;
39 import org.millscript.commons.util.list.AbstractIList;
40 import org.millscript.commons.util.list.IArrayList;
41 import org.millscript.commons.util.maplet.IMaplet;
42
43 /**
44 * This class provides an immutable <code>Map</code> implementation that uses
45 * an array of hash code buckets to store the data.
46 */
47 public class EHashMap< K, V > extends AbstractEMap< K, V > implements Cloneable, Serializable {
48
49
50
51 /**
52 * This is the ID from the release 0.1.0 for future compatibility.
53 */
54 private static final long serialVersionUID = -8774040887210604644L;
55
56 /**
57 * This class implements a map iterator which iterates over an array of
58 * hash buckets, sharing the backing store with it's enclosing mutable map.
59 * <p>
60 * As expected, the iterator uses a copy-on-write contract with its
61 * enclosing class during the iteration. Simple updates will not cause a
62 * copy, but structural(i.e. inserts/removes) will cause a copy for the
63 * duration of the iteration.
64 * </p>
65 */
66 public static class HashMapIterator< K, V > extends AbstractMapIterator< K, V > {
67
68 /**
69 * The maplet for the current point in the iteration.
70 */
71 private HashMaplet< K, V > currentMaplet;
72
73 /**
74 * The next maplet in the iteration. If this is <code>null</code> there
75 * are no more elements in the iteration.
76 */
77 private HashMaplet< K, V > nextMaplet;
78
79 /**
80 * The current position of the iterator within the hash map bucket
81 * array.
82 */
83 private int pos = -1;
84
85 /**
86 * The backing store for this hash map is a fixed array of HashMaplet
87 * buckets.
88 */
89 private final HashMaplet< K, V >[] store;
90
91 /**
92 * Constructs a new hash map iterator to iterate over the specified
93 * mutable hash map
94 *
95 * @param maplets the array of hash map buckets to iterate over
96 * @param share if <code>true</code> the specified object array will be
97 * shared otherwise the array will be copied.
98 */
99 @SuppressWarnings( "unchecked" )
100 public HashMapIterator( final EHashMap< K, V > map, final boolean share ) {
101 if ( share ) {
102 this.store = map.store;
103 } else {
104 this.store = new HashMaplet[ map.store.length ];
105 for ( int i = 0; i < map.store.length; i++ ) {
106 HashMaplet< K, V > maplet = map.store[ i ];
107 if ( maplet != null ) {
108 HashMaplet< K, V > copy = new HashMaplet< K, V >( maplet );
109 this.store[ i ] = copy;
110 for ( maplet = maplet.next; maplet != null; maplet = maplet.next ) {
111 copy.next = new HashMaplet< K, V >( maplet );
112 }
113 }
114 }
115 }
116 }
117
118 /**
119 * @see org.millscript.commons.util.iterator.AbstractMapIterator#advance()
120 */
121 @Override
122 protected void advance() {
123
124 this.checkNext();
125
126 this.currentMaplet = this.nextMaplet;
127 if ( this.nextMaplet != null ) {
128 this.nextMaplet = this.nextMaplet.next;
129 }
130 }
131
132 /**
133 * Checks that the next maplet field is populated with the next maplet
134 * if one is available.
135 */
136 private void checkNext() {
137 if ( this.nextMaplet == null ) {
138
139 if ( ++pos < this.store.length ) {
140 this.nextMaplet = this.store[ pos ];
141
142 this.checkNext();
143 }
144 }
145 }
146
147 /**
148 * @see org.millscript.commons.util.iterator.AbstractMapIterator#getKey()
149 */
150 @Override
151 protected K getKey() {
152 return currentMaplet.key;
153 }
154
155 /**
156 * @see org.millscript.commons.util.iterator.AbstractMapIterator#getMaplet()
157 */
158 @Override
159 protected Maplet< K, V > getMaplet() {
160 return currentMaplet;
161 }
162
163 /**
164 * @see org.millscript.commons.util.iterator.AbstractMapIterator#getValue()
165 */
166 @Override
167 protected V getValue() {
168 return currentMaplet.value;
169 }
170
171 /**
172 * @see org.millscript.commons.util.MapIterator#hasNext()
173 */
174 public boolean hasNext() {
175 this.checkNext();
176 return this.nextMaplet != null;
177 }
178
179 /**
180 * @see org.millscript.commons.util.iterator.AbstractMapIterator#outOfBounds()
181 */
182 @Override
183 protected boolean outOfBounds() {
184 return currentMaplet == null;
185 }
186
187 }
188
189 /**
190 * This class implements a map iterator which iterates over an array
191 * of hash map buckets, returning each maplet key, sharing the backing
192 * store with it's enclosing mutable map.
193 */
194 public static class HashMapKeysIterator< K > extends HashMapXIterator< K > {
195
196 /**
197 * Constructs a new hash map iterator to iterate over the specified
198 * mutable hash map returning the maplet keys.
199 *
200 * @param map the mutable hash map to iterate over
201 * @param first the index(one based, inclusive) of the first name
202 * @param last the index(one based, inclusive) of the last name
203 */
204 public HashMapKeysIterator( final EHashMap< ?, ? > map, final int first, final int last ) {
205 super( map, first, last );
206 }
207
208 /**
209 * @see org.millscript.commons.util.map.IHashMap.HashMapXIterator#getAppropriateNodePart(org.millscript.commons.util.Maplet)
210 */
211 @Override
212 @SuppressWarnings( "unchecked" )
213 K getAppropriateMapletPart( final Maplet< ?, ? > maplet ) {
214 return (K) maplet.getKey();
215 }
216
217 }
218
219 /**
220 * This class implements an immutable list which is backed by an array of
221 * hash map buckets, but NOTE the values in the list are actually the
222 * individual hash maplet keys. The backing store is shared with it's
223 * enclosing mutable map.
224 */
225 public static class HashMapKeysList< K > extends HashMapXList< K > {
226
227 /**
228 * Constructs a new mutable hash map backed list of the individual
229 * maplet keys.
230 *
231 * @param map the mutable hash map to use as a backing list
232 * @param first the index(one based, inclusive) of the first name
233 * @param last the index(one based, inclusive) of the last name
234 */
235 HashMapKeysList( final EHashMap< ?, ? > map, final int first, final int last ) {
236 super( map, first, last );
237 }
238
239 /**
240 * @see org.millscript.commons.util.map.IHashMap.HashMapXList#getAppropriateNodePart(org.millscript.commons.util.Maplet)
241 */
242 @Override
243 @SuppressWarnings( "unchecked" )
244 K getAppropriateMapletPart( final Maplet< ?, ? > maplet ) {
245 return (K) maplet.getKey();
246 }
247
248 /**
249 * @see org.millscript.commons.util.map.IHashMap.HashMapKeysIterator.HashMapXList#sharedIterator()
250 */
251 @Override
252 ListIterator< K > sharedIterator() {
253 return new HashMapKeysIterator< K >( this.backingMap, this.firstIndex, this.lastIndex );
254 }
255
256 /**
257 * @see org.millscript.commons.util.map.EHashMap.HashMapXList#sharedSlice(int, int)
258 */
259 @Override
260 IList< K > sharedSlice( final int first, final int last ) {
261 return new HashMapKeysList< K >( this.backingMap, first, last );
262 }
263
264 }
265
266 /**
267 * This class provides a mutable implementation of a <code>Maplet</code>
268 * which also acts as a bucket in our hashmap. This implementation only
269 * supports mutating the maplet value, not the key.
270 */
271 private static class HashMaplet< K, V > implements Maplet< K, V > {
272
273 /**
274 * This maplets key.
275 */
276 final K key;
277
278 /**
279 * The next hash maplet in this chain.
280 */
281 HashMaplet< K, V > next;
282
283 /**
284 * This maplets value.
285 */
286 V value;
287
288 /**
289 * Constructs a new hash maplet with the specified key and value.
290 *
291 * @param k the maplet key
292 * @param v the maplet value
293 */
294 private HashMaplet( final K k, final V v ) {
295 this.key = k;
296 this.value = v;
297 }
298
299 /**
300 * Constructs a new hash maplet taking its key and value from the
301 * specified maplet.
302 *
303 * @param m the maplet to copy the key and value from
304 */
305 private HashMaplet( final Maplet< K, V > m ) {
306 this.key = m.getKey();
307 this.value = m.getValue();
308 }
309
310 /**
311 * @see org.millscript.commons.util.Maplet#getKey()
312 */
313 public K getKey() {
314 return this.key;
315 }
316
317 /**
318 * @see org.millscript.commons.util.Maplet#getValue()
319 */
320 public V getValue() {
321 return this.value;
322 }
323
324 }
325
326 /**
327 * This class implements a map iterator which iterates over an array
328 * of hash map buckets, returning each maplet as the value.
329 */
330 public static class HashMapMapletIterator< K, V > extends HashMapXIterator< Maplet< K, V > > {
331
332 /**
333 * Constructs a new hash map iterator to iterate over the specified
334 * array of hash map buckets returning the maplet as the value.
335 *
336 * @param map the mutable hash map to iterate over
337 * @param first the index(one based, inclusive) of the first name
338 * @param last the index(one based, inclusive) of the last name
339 */
340 public HashMapMapletIterator( final EHashMap< ?, ? > map, final int first, final int last ) {
341 super( map, first, last );
342 }
343
344 /**
345 * @see org.millscript.commons.util.map.IHashMap.HashMapXIterator#getAppropriateNodePart(org.millscript.commons.util.Maplet)
346 */
347 @Override
348 @SuppressWarnings( "unchecked" )
349 Maplet< K, V > getAppropriateMapletPart( final Maplet< ?, ? > maplet ) {
350 return (Maplet< K, V >) maplet;
351 }
352
353 }
354
355 /**
356 * This class implements an immutable list which is backed by an array of
357 * hash map buckets, but NOTE the values in the list are actually the
358 * individual hash maplets themselves.
359 */
360 public static class HashMapMapletList< K, V > extends HashMapXList< Maplet< K, V > > {
361
362 /**
363 * Constructs a new hash maplet array list of the individual maplets.
364 *
365 * @param map the mutable hash map to use as a backing map
366 * @param first the index(one based, inclusive) of the first name
367 * @param last the index(one based, inclusive) of the last name
368 */
369 HashMapMapletList( final EHashMap< ?, ? > map, final int first, final int last ) {
370 super( map, first, last );
371 }
372
373 /**
374 * @see org.millscript.commons.util.map.IHashMap.HashMapXList#getAppropriateNodePart(org.millscript.commons.util.Maplet)
375 */
376 @Override
377 @SuppressWarnings( "unchecked" )
378 Maplet< K, V > getAppropriateMapletPart( final Maplet< ?, ? > maplet ) {
379 return (Maplet< K, V >) maplet;
380 }
381
382 /**
383 * @see org.millscript.commons.util.map.IHashMap.HashMapKeysIterator.HashMapXList#sharedIterator()
384 */
385 @Override
386 ListIterator< Maplet< K, V > > sharedIterator() {
387 return new HashMapMapletIterator< K, V >( this.backingMap, this.firstIndex, this.lastIndex );
388 }
389
390 /**
391 * @see org.millscript.commons.util.map.IHashMap.HashMapXList#sharedSlice(int, int)
392 */
393 @Override
394 IList< Maplet< K, V > > sharedSlice( final int first, final int last ) {
395 return new HashMapMapletList< K, V >( this.backingMap, first, last );
396 }
397
398 }
399
400 /**
401 * This class implements a map iterator which iterates over an array
402 * of hash map buckets, returning each maplet value, sharing the backing
403 * store with it's enclosing mutable map.
404 */
405 public static class HashMapValuesIterator< V > extends HashMapXIterator< V > {
406
407 /**
408 * Constructs a new hash map iterator to iterate over the specified
409 * mutable hash map returning the maplet values.
410 *
411 * @param map the mutable hash map to iterate over
412 * @param first the index(one based, inclusive) of the first name
413 * @param last the index(one based, inclusive) of the last name
414 */
415 public HashMapValuesIterator( final EHashMap< ?, ? > map, final int first, final int last ) {
416 super( map, first, last );
417 }
418
419 /**
420 * @see org.millscript.commons.util.map.IHashMap.HashMapXIterator#getAppropriateNodePart(org.millscript.commons.util.Maplet)
421 */
422 @Override
423 @SuppressWarnings( "unchecked" )
424 V getAppropriateMapletPart( final Maplet< ?, ? > maplet ) {
425 return (V) maplet.getValue();
426 }
427
428 }
429
430 /**
431 * This class implements an immutable list which is backed by an array of
432 * hash map buckets, but NOTE the values in the list are actually the
433 * individual hash maplet values. The backing store is shared with it's
434 * enclosing mutable map.
435 */
436 public static class HashMapValuesList< V > extends HashMapXList< V > {
437
438 /**
439 * Constructs a new mutable hash map backed list of the individual
440 * maplet values.
441 *
442 * @param map the mutable hash map to use as a backing list
443 * @param first the index(one based, inclusive) of the first name
444 * @param last the index(one based, inclusive) of the last name
445 */
446 HashMapValuesList( final EHashMap< ?, ? > map, final int first, final int last ) {
447 super( map, first, last );
448 }
449
450 /**
451 * @see org.millscript.commons.util.map.IHashMap.HashMapXList#getAppropriateNodePart(org.millscript.commons.util.Maplet)
452 */
453 @Override
454 @SuppressWarnings( "unchecked" )
455 V getAppropriateMapletPart( final Maplet< ?, ? > maplet ) {
456 return (V) maplet.getValue();
457 }
458
459 /**
460 * @see org.millscript.commons.util.map.IHashMap.HashMapKeysIterator.HashMapXList#sharedIterator()
461 */
462 @Override
463 ListIterator< V > sharedIterator() {
464 return new HashMapValuesIterator< V >( this.backingMap, this.firstIndex, this.lastIndex );
465 }
466
467 /**
468 * @see org.millscript.commons.util.map.EHashMap.HashMapXList#sharedSlice(int, int)
469 */
470 @Override
471 IList< V > sharedSlice( final int first, final int last ) {
472 return new HashMapValuesList< V >( this.backingMap, first, last );
473 }
474
475 }
476
477 /**
478 * This class implements a map iterator which iterates over an array
479 * of hash map buckets, returning either the keys or values. The backing
480 * store is shared with it's enclosing mutable map.
481 */
482 private static abstract class HashMapXIterator< E > extends AbstractListIterator< E > {
483
484 /**
485 * The maplet for the current point in the iteration.
486 */
487 private HashMaplet< ?, ? > currentMaplet;
488
489 /**
490 * The next maplet in the iteration. If this is <code>null</code> there
491 * are no more elements in the iteration.
492 */
493 private HashMaplet< ?, ? > nextMaplet;
494
495 /**
496 * The current position of the iterator within the hash map bucket
497 * array.
498 */
499 private int bucketIndex = -1;
500
501 /**
502 * The number of elements this iterator will return.
503 */
504 private final int size;
505
506 /**
507 * The backing store for this hash map is a fixed array of HashMaplet
508 * buckets.
509 */
510 private final HashMaplet< ?, ? >[] store;
511
512 /**
513 * Constructs a new hash map iterator to iterate over the specified
514 * mutable hash map returning either the maplet keys or values.
515 *
516 * @param map the mutable hash map to iterate over
517 * @param first the index(one based, inclusive) of the first name
518 * @param last the index(one based, inclusive) of the last name
519 */
520 public HashMapXIterator( final EHashMap< ?, ? > map, final int first, final int last ) {
521 int fb = 0;
522 HashMaplet< ?, ? > fm = null;
523 int totalMaplets = 0;
524
525 for ( int i = 0; i < map.store.length; i++ ) {
526
527 for ( HashMaplet< ?, ? > hmp = map.store[ i ]; hmp != null; hmp = hmp.next ) {
528
529 if ( ++totalMaplets == first ) {
530
531 fb = i;
532 fm = hmp;
533 }
534 }
535 }
536 if ( first > last ) {
537 this.currentMaplet = null;
538 this.nextMaplet = null;
539 this.bucketIndex = 0;
540 this.size = 0;
541 this.store = null;
542 } else if ( first < 1 || first > totalMaplets ) {
543 throw new ListIndexOutOfBoundsAlert(
544 "First index in slice must be between 1 and the number of entries in the map"
545 ).culprit(
546 "index",
547 first
548 ).decorate( map ).mishap();
549 } else if ( last > totalMaplets ) {
550 throw new ListIndexOutOfBoundsAlert(
551 "Last index in slice must not be greater than the number of entries in the map"
552 ).culprit(
553 "index",
554 last
555 ).decorate( map ).mishap();
556 } else {
557 this.currentMaplet = null;
558 this.nextMaplet = fm;
559 this.bucketIndex = fb;
560 this.size = last - first + 1;
561 this.store = map.store;
562 }
563 }
564
565 /**
566 * @see org.millscript.commons.util.iterator.AbstractMapIterator#advance()
567 */
568 @Override
569 protected void advance() {
570
571 super.advance();
572
573 this.currentMaplet = this.nextMaplet;
574 if ( super.position >= this.size ) {
575 this.nextMaplet = null;
576 } else if ( this.nextMaplet != null ) {
577 this.nextMaplet = this.nextMaplet.next;
578 }
579
580 this.checkNext();
581 }
582
583 /**
584 * Checks that the next maplet field is populated with the next maplet
585 * if one is available.
586 */
587 private void checkNext() {
588 if ( this.nextMaplet == null ) {
589
590 if ( ++bucketIndex < this.store.length ) {
591 this.nextMaplet = this.store[ bucketIndex ];
592
593 this.checkNext();
594 }
595 }
596 }
597
598 /**
599 * Returns the appropriate part of the specified maplet for this list.
600 *
601 * @param maplet the maplet to get the appropriate part from
602 * @return the appropriate part of the specified maplet
603 */
604 abstract E getAppropriateMapletPart( Maplet< ?, ? > maplet );
605
606 /**
607 * @see org.millscript.commons.util.iterator.AbstractMapIterator#getValue()
608 */
609 @Override
610 protected E getValue() {
611 return this.getAppropriateMapletPart( this.currentMaplet );
612 }
613
614 /**
615 * @see org.millscript.commons.util.MapIterator#hasNext()
616 */
617 public boolean hasNext() {
618 return this.nextMaplet != null;
619 }
620
621 /**
622 * @see org.millscript.commons.util.iterator.AbstractMapIterator#outOfBounds()
623 */
624 @Override
625 protected boolean outOfBounds() {
626 return this.currentMaplet == null;
627 }
628
629 }
630
631 /**
632 * The class provides the skeletal implementation of a list backed by an
633 * array of hash map buckets, where the list values are either the maplet
634 * keys or values. The backing store is shared with it's enclosing mutable
635 * map.
636 */
637 private static abstract class HashMapXList< E > extends AbstractIList< E > {
638
639 /**
640 * The mutable hash map this list gets its backing store from.
641 */
642 final EHashMap< ?, ? > backingMap;
643
644 /**
645 * The index of the first bucket in the backing store that the first
646 * maplet in the list is held in.
647 */
648 private final int firstBucket;
649
650 /**
651 * The index of the first maplet in the backing store that is returned.
652 */
653 final int firstIndex;
654
655 /**
656 * The first maplet in the list(in the first bucket).
657 */
658 private final HashMaplet< ?, ? > firstHashMaplet;
659
660 /**
661 * The index of the last maplet in the backing store that is returned.
662 */
663 final int lastIndex;
664
665 /**
666 * The backing mutable hash map for this list.
667 */
668 final HashMaplet< ?, ? >[] store;
669
670 /**
671 * Constructs a new mutable hash map backed list of either the
672 * individual map keys or values.
673 *
674 * @param map the mutable hash map to use as a backing map
675 * @param first the index(one based, inclusive) of the first name
676 * @param last the index(one based, inclusive) of the last name
677 */
678 private HashMapXList( final EHashMap< ?, ? > map, final int first, final int last ) {
679 int fb = 0;
680 HashMaplet< ?, ? > fm = null;
681 int totalMaplets = 0;
682
683 for ( int i = 0; i < map.store.length; i++ ) {
684
685 for ( HashMaplet< ?, ? > hmp = map.store[ i ]; hmp != null; hmp = hmp.next ) {
686
687 if ( ++totalMaplets == first ) {
688
689 fb = i;
690 fm = hmp;
691 }
692 }
693 }
694 if ( first > last ) {
695 this.firstBucket = 0;
696 this.firstHashMaplet = null;
697 this.store = null;
698 } else if ( first < 1 || first > totalMaplets ) {
699 throw new ListIndexOutOfBoundsAlert(
700 "First index in slice must be between 1 and the number of entries in the map"
701 ).culprit(
702 "index",
703 first
704 ).decorate( map ).mishap();
705 } else if ( last > totalMaplets ) {
706 throw new ListIndexOutOfBoundsAlert(
707 "Last index in slice must not be greater than the number of entries in the map"
708 ).culprit(
709 "index",
710 last
711 ).decorate( map ).mishap();
712 } else {
713 this.firstBucket = fb;
714 this.firstHashMaplet = fm;
715 this.store = map.store;
716 }
717 this.backingMap = map;
718 this.firstIndex = first;
719 this.lastIndex = last;
720 }
721
722 /**
723 * @see org.millscript.commons.util.list.AbstractIList#doGet(int)
724 */
725 @Override
726 protected E doGet( final int pos ) {
727 int i = this.firstBucket;
728 int p = 1;
729 HashMaplet< ?, ? > hmp = this.firstHashMaplet;
730 while ( p <= this.size() && i < this.store.length ) {
731 if ( p == pos ) {
732 return this.getAppropriateMapletPart( hmp );
733 } else {
734
735 hmp = hmp.next;
736 while ( hmp == null && ++i < this.store.length ) {
737 hmp = this.store[ i ];
738 }
739 p++;
740 }
741 }
742 throw new Fault(
743 "Specified position is neither out of bounds or within the list!"
744 ).culprit( "index", pos ).decorate( this ).mishap();
745 }
746
747 /**
748 * @see org.millscript.commons.util.list.AbstractIList#doSlice(int, int, boolean)
749 */
750 @Override
751 @SuppressWarnings( "unchecked" )
752 protected IList< E > doSlice( final int first, final int last, final boolean share ) {
753 if ( share ) {
754 return this.sharedSlice( first, last );
755 } else {
756
757 final E[] objects = (E[]) new Object[ this.size() ];
758 int i = this.firstBucket;
759 int pos = 0;
760 HashMaplet< ?, ? > hmp = this.firstHashMaplet;
761 while ( pos < this.size() && i < this.store.length ) {
762 objects[ pos ] = this.getAppropriateMapletPart( hmp );
763
764 hmp = hmp.next;
765 while ( hmp == null && ++i < this.store.length ) {
766 hmp = this.store[ i ];
767 }
768 pos++;
769 }
770 return new IArrayList< E >( objects, true );
771 }
772 }
773
774 /**
775 * Returns the appropriate part of the specified maplet for this list.
776 *
777 * @param maplet the maplet to get the appropriate part from
778 * @return the appropriate part of the specified maplet
779 */
780 abstract E getAppropriateMapletPart( Maplet< ?, ? > maplet );
781
782 /**
783 * @see org.millscript.commons.util.IList#indexOf(java.lang.Object)
784 */
785 public int indexOf( final E value ) {
786 int i = this.firstBucket;
787 int pos = 1;
788 HashMaplet< ?, ? > hmp = this.firstHashMaplet;
789 if ( value == null ) {
790 while ( pos <= this.size() && i < this.store.length ) {
791 if ( this.getAppropriateMapletPart( hmp ) == null ) {
792 return pos;
793 } else {
794
795 hmp = hmp.next;
796 while ( hmp == null && ++i < this.store.length ) {
797 hmp = this.store[ i ];
798 }
799 pos++;
800 }
801 }
802 } else {
803 while ( pos <= this.size() && i < this.store.length ) {
804 if ( value.equals( this.getAppropriateMapletPart( hmp ) ) ) {
805 return pos;
806 } else {
807
808 hmp = hmp.next;
809 while ( hmp == null && ++i < this.store.length ) {
810 hmp = this.store[ i ];
811 }
812 pos++;
813 }
814 }
815 }
816 return 0;
817 }
818
819 /**
820 * @see org.millscript.commons.util.IMap#iterator(boolean)
821 */
822 @SuppressWarnings( "unchecked" )
823 public ListIterator< E > iterator( final boolean share ) {
824 if ( share ) {
825 return this.sharedIterator();
826 } else {
827
828
829 final E[] objects = (E[]) new Object[ this.size() ];
830 for ( int i = 0, j = 0; i < this.store.length; i++ ) {
831 for ( HashMaplet< ?, ? > maplet = this.store[ i ]; maplet != null; maplet = maplet.next ) {
832 objects[ j++ ] = this.getAppropriateMapletPart( maplet );
833 }
834 }
835 return new ArrayListIterator< E >( objects, true );
836 }
837 }
838
839 /**
840 * Returns a map iterator which shares backing store with this list.
841 *
842 * @return a map iterator which shares this lists backing store
843 */
844 abstract ListIterator< E > sharedIterator();
845
846 /**
847 * Returns a slice of this list which shares backing store with this
848 * list.
849 *
850 * @param first the index(one based) of the first element in the slice
851 * @param last the index(one based) of the last element in the slice
852 * @return a slice of this list which shares this lists backing store
853 */
854 abstract IList< E > sharedSlice( int first, int last );
855
856 /**
857 * @see org.millscript.commons.util.IMap#size()
858 */
859 public int size() {
860 return this.lastIndex <= this.firstIndex ? 0
861 : this.lastIndex - this.firstIndex + 1;
862 }
863
864 }
865
866 private static float DEFAULT_LOAD_FACTOR = 0.75f;
867
868 private static int DEFAULT_CAPACITY = 17;
869
870 private transient int size;
871
872
873 /**
874 * The backing store for this hash map is a variable array of HashMaplet
875 * buckets.
876 */
877 transient HashMaplet< K, V >[] store;
878
879 private transient int triggerRehashSize;
880
881 /**
882 * Constructs a new, emtpy mutable hash map.
883 */
884 @SuppressWarnings( "unchecked" )
885 public EHashMap() {
886 this.store = new HashMaplet[ DEFAULT_CAPACITY ];
887 this.triggerRehashSize = (int) ( DEFAULT_CAPACITY * DEFAULT_LOAD_FACTOR );
888 }
889
890 /**
891 * Constructs a new mutable hash map which contains all the mappings from
892 * the specified map.
893 *
894 * @param map the <code>Map</code> to copy mappings from
895 */
896 @SuppressWarnings( "unchecked" )
897 public EHashMap( final IMap< K, V > map ) {
898 final MapIterator< K, V > it = map.iterator( true );
899 final HashMaplet< K, V >[] maplets = new HashMaplet[ map.size() * 2 + 1 ];
900 while ( it.hasNext() ) {
901 final int pos = it.nextKey() == null ? 0 : ( it.currentKey().hashCode() & 0x7FFFFFFF ) % maplets.length;
902 if ( maplets[ pos ] == null ) {
903 maplets[ pos ] = new HashMaplet< K, V >( it.currentKey(), it.currentValue() );
904 this.size++;
905 } else {
906 for ( HashMaplet< K, V > hmp = maplets[ pos ]; hmp != null; hmp = hmp.next ) {
907 if ( hmp.key == null ? it.currentKey() == null : hmp.key.equals( it.currentKey() ) ) {
908 hmp.value = it.currentValue();
909 break;
910 } else if ( hmp.next == null ) {
911 hmp.next = new HashMaplet< K, V >( it.currentKey(), it.currentValue() );
912 this.size++;
913 }
914 }
915 }
916 }
917 this.store = maplets;
918 this.triggerRehashSize = (int) ( this.store.length * DEFAULT_LOAD_FACTOR );
919 }
920
921 /**
922 * @see java.lang.Object#clone()
923 */
924 @Override
925 @SuppressWarnings( "unchecked" )
926 public Object clone() throws CloneNotSupportedException {
927 final EHashMap< K, V > map = (EHashMap< K, V >) super.clone();
928 map.store = new HashMaplet[ this.store.length ];
929 for ( int i = 0; i < this.store.length; i++ ) {
930 HashMaplet< K, V > clonedMaplet = null;
931 for ( HashMaplet< K, V > originalMaplet = this.store[ i ]; originalMaplet != null; originalMaplet = originalMaplet.next ) {
932 if ( clonedMaplet == null ) {
933 clonedMaplet = new HashMaplet< K, V >( originalMaplet );
934 map.store[ i ] = clonedMaplet;
935 } else {
936 clonedMaplet.next = new HashMaplet< K, V >( originalMaplet );
937 clonedMaplet = clonedMaplet.next;
938 }
939 }
940 }
941 return map;
942 }
943
944 /**
945 * @see org.millscript.commons.util.IMap#contains(java.lang.Object, java.lang.Object)
946 */
947 public boolean contains( final K key, final V value ) {
948 final int pos = key == null ? 0 : ( key.hashCode() & 0x7FFFFFFF ) % this.store.length;
949 for ( HashMaplet hmp = this.store[ pos ]; hmp != null; hmp = hmp.next ) {
950 if ( hmp.key == null ? key == null : hmp.key.equals( key ) ) {
951
952
953 return hmp.value == null ? value == null
954 : hmp.value.equals( value );
955 }
956 }
957 return false;
958 }
959
960 /**
961 * @see org.millscript.commons.util.IMap#containsKey(java.lang.Object)
962 */
963 public boolean containsKey( final K key ) {
964 final int pos = key == null ? 0 : ( key.hashCode() & 0x7FFFFFFF ) % this.store.length;
965 for ( HashMaplet hmp = this.store[ pos ]; hmp != null; hmp = hmp.next ) {
966 if ( hmp.key == null ? key == null : hmp.key.equals( key ) ) {
967 return true;
968 }
969 }
970 return false;
971 }
972
973 /**
974 * @see org.millscript.commons.util.IMap#containsValue(java.lang.Object)
975 */
976 public boolean containsValue( final V value ) {
977
978 for ( int i = 0; i < this.store.length; i++ ) {
979 for ( HashMaplet hmp = this.store[ i ]; hmp != null; hmp = hmp.next ) {
980 if ( hmp.value == null ? value == null : hmp.value.equals( value ) ) {
981 return true;
982 }
983 }
984 }
985 return false;
986 }
987
988 /**
989 * @see org.millscript.commons.util.IMap#get(java.lang.Object)
990 */
991 public V get( final K key ) {
992 final int pos = key == null ? 0 : ( key.hashCode() & 0x7FFFFFFF ) % this.store.length;
993 for ( HashMaplet< K, V > hmp = this.store[ pos ]; hmp != null; hmp = hmp.next ) {
994 if ( hmp.key == null ? key == null : hmp.key.equals( key ) ) {
995 return hmp.value;
996 }
997 }
998 return this.getDefault().get( this, key );
999 }
1000
1001 /**
1002 * @see org.millscript.commons.util.EMap#insert(java.lang.Object, java.lang.Object)
1003 */
1004 public void insert( final K key, final V value ) {
1005 final int pos = key == null ? 0 : ( key.hashCode() & 0x7FFFFFFF ) % this.store.length;
1006 if ( this.store[ pos ] == null ) {
1007 this.store[ pos ] = new HashMaplet< K, V >( key, value );
1008
1009 this.size++;
1010 } else {
1011 for ( HashMaplet< K, V > hmp = this.store[ pos ]; hmp != null; hmp = hmp.next ) {
1012 if ( hmp.key == null ? key == null : hmp.key.equals( key ) ) {
1013
1014
1015 hmp.value = value;
1016 break;
1017 } else if ( hmp.next == null ) {
1018
1019
1020
1021
1022 if ( this.size == this.triggerRehashSize ) {
1023 this.insertWithRehash( key, value );
1024 } else {
1025 hmp.next = new HashMaplet< K, V >( key, value );
1026
1027 this.size++;
1028 }
1029 break;
1030 }
1031 }
1032 }
1033 }
1034
1035 /**
1036 * Inserts the specified key-value mapping after performing a rehash of the
1037 * backing store to increase it's size.
1038 *
1039 * @param key the new key to add to the mapping
1040 * @param value the new value to associate with the given key
1041 */
1042 @SuppressWarnings( "unchecked" )
1043 protected void insertWithRehash( final K key, final V value ) {
1044 final HashMaplet< K, V >[] newStore = new HashMaplet[ this.store.length * 2 + 1 ];
1045 for ( int i = 0; i < this.store.length; i++ ) {
1046 HashMaplet< K, V > hashMaplet = this.store[ i ];
1047 while ( hashMaplet != null ) {
1048 final int pos = hashMaplet.key == null ? 0 : ( hashMaplet.key.hashCode() & 0x7FFFFFFF ) % newStore.length;
1049 if ( newStore[ pos ] == null ) {
1050 newStore[ pos ] = new HashMaplet< K, V >( hashMaplet );
1051 } else {
1052
1053
1054
1055 for ( HashMaplet< K, V > hmp = newStore[ pos ]; hmp != null; hmp = hmp.next ) {
1056 if ( hmp.key == null ? hashMaplet.key == null : hmp.key.equals( hashMaplet.key ) ) {
1057 hmp.value = hashMaplet.value;
1058 break;
1059 } else if ( hmp.next == null ) {
1060 hmp.next = new HashMaplet< K, V >( hashMaplet );
1061 break;
1062 }
1063 }
1064 }
1065 hashMaplet = hashMaplet.next;
1066 }
1067 }
1068 this.store = newStore;
1069 this.triggerRehashSize = (int) ( this.store.length * DEFAULT_LOAD_FACTOR );
1070
1071 this.insert( key, value );
1072 }
1073
1074 /**
1075 * @see org.millscript.commons.util.IMap#iterator(boolean)
1076 */
1077 @SuppressWarnings( "unchecked" )
1078 public MapIterator< K, V > iterator( final boolean share ) {
1079 if ( share ) {
1080 return new HashMapIterator< K, V >( this, true );
1081 } else {
1082
1083
1084
1085 final Maplet< K, V >[] maplets = new Maplet[ this.size() ];
1086 for ( int i = 0, j = 0; i < this.store.length; i++ ) {
1087 for ( HashMaplet< K, V > maplet = this.store[ i ]; maplet != null; maplet = maplet.next ) {
1088 maplets[ j++ ] = new IMaplet< K, V >( maplet );
1089 }
1090 }
1091 return new IMapletArrayMap.MapletArrayMapIterator< K, V >( maplets, true );
1092 }
1093 }
1094
1095 /**
1096 * Reads this object from the specified {@link ObjectInputStream}.
1097 *
1098 * @param stream the {@link ObjectInputStream} to read the objects data
1099 * from
1100 * @serialData Reads the default object, followed by the integer
1101 * number of mappings, the integer number of buckets and then an
1102 * alternating sequence of key-value pairs
1103 * @throws ClassNotFoundException if a required class cannot be found
1104 * @throws IOException if something goes wrong during the
1105 * deserialization process
1106 */
1107 @SuppressWarnings( "unchecked" )
1108 private void readObject( final ObjectInputStream stream ) throws ClassNotFoundException, IOException {
1109
1110 stream.defaultReadObject();
1111
1112 this.size = stream.readInt();
1113
1114 this.store = new HashMaplet[ stream.readInt() ];
1115
1116 this.triggerRehashSize = (int) ( this.store.length * DEFAULT_LOAD_FACTOR );
1117
1118 for ( int i = 0; i < size; i++ ) {
1119 final K key = (K) stream.readObject();
1120 final V value = (V) stream.readObject();
1121 final int pos = key == null ? 0 : ( key.hashCode() & 0x7FFFFFFF ) % this.store.length;
1122 if ( this.store[ pos ] == null ) {
1123 this.store[ pos ] = new HashMaplet< K, V >( key, value );
1124 } else {
1125
1126 HashMaplet< K, V > hmp = this.store[ pos ];
1127 while ( hmp.next != null ) {
1128 hmp = hmp.next;
1129 }
1130 hmp.next = new HashMaplet< K, V >( key, value );
1131 }
1132 }
1133 }
1134
1135 /**
1136 * @see org.millscript.commons.util.EMap#remove(java.lang.Object, java.lang.Object)
1137 */
1138 public void remove( final K key, final V value ) {
1139 final int pos = key == null ? 0 : ( key.hashCode() & 0x7FFFFFFF ) % this.store.length;
1140 HashMaplet< K, V > previousInChain = null;
1141 for ( HashMaplet< K, V > hmp = this.store[ pos ]; hmp != null; hmp = hmp.next ) {
1142 if ( hmp.key == null ? key == null : hmp.key.equals( key ) ) {
1143
1144 if ( hmp.value == null ? value == null : hmp.value.equals( value ) ) {
1145
1146
1147 if ( previousInChain == null ) {
1148
1149
1150 this.store[ pos ] = hmp.next;
1151 } else {
1152
1153
1154 previousInChain.next = hmp.next;
1155 }
1156
1157 this.size--;
1158 break;
1159 }
1160 }
1161
1162
1163 previousInChain = hmp;
1164 }
1165 }
1166
1167 /**
1168 * @see org.millscript.commons.util.EMap#removeAll()
1169 */
1170 @SuppressWarnings( "unchecked" )
1171 public void removeAll() {
1172 this.size = 0;
1173 this.store = new HashMaplet[ DEFAULT_CAPACITY ];
1174 this.triggerRehashSize = (int) ( DEFAULT_CAPACITY * DEFAULT_LOAD_FACTOR );
1175 }
1176
1177 /**
1178 * @see org.millscript.commons.util.EMap#removeKey(java.lang.Object)
1179 */
1180 public void removeKey( final K key ) {
1181 final int pos = key == null ? 0 : ( key.hashCode() & 0x7FFFFFFF ) % this.store.length;
1182 HashMaplet< K, V > previousInChain = null;
1183 for ( HashMaplet< K, V > hmp = this.store[ pos ]; hmp != null; hmp = hmp.next ) {
1184 if ( hmp.key == null ? key == null : hmp.key.equals( key ) ) {
1185
1186 if ( previousInChain == null ) {
1187
1188
1189 this.store[ pos ] = hmp.next;
1190 } else {
1191
1192
1193 previousInChain.next = hmp.next;
1194 }
1195
1196 this.size--;
1197 break;
1198 } else {
1199 previousInChain = hmp;
1200 }
1201 }
1202 }
1203
1204 /**
1205 * @see org.millscript.commons.util.EMap#removeValue(java.lang.Object)
1206 */
1207 public void removeValue( final V value ) {
1208
1209 for ( int i = 0; i < this.store.length; i++ ) {
1210 HashMaplet< K, V > previousInChain = null;
1211 for ( HashMaplet< K, V > hmp = this.store[ i ]; hmp != null; hmp = hmp.next ) {
1212 if ( hmp.value == null ? value == null : hmp.value.equals( value ) ) {
1213
1214 if ( previousInChain == null ) {
1215
1216
1217 this.store[ i ] = hmp.next;
1218 } else {
1219
1220
1221 previousInChain.next = hmp.next;
1222 }
1223 this.size--;
1224 } else {
1225 previousInChain = hmp;
1226 }
1227 }
1228 }
1229 }
1230
1231 /**
1232 * @see org.millscript.commons.util.map.AbstractIMap#sharedKeyList()
1233 */
1234 @Override
1235 protected IList< K > sharedKeyList() {
1236 return new HashMapKeysList< K >( this, 1, this.size() );
1237 }
1238
1239 /**
1240 * @see org.millscript.commons.util.map.AbstractIMap#sharedMapletList()
1241 */
1242 @Override
1243 protected IList< Maplet< K, V > > sharedMapletList() {
1244 return new HashMapMapletList< K, V >( this, 1, this.size() );
1245 }
1246
1247 /**
1248 * @see org.millscript.commons.util.map.AbstractIMap#sharedValueList()
1249 */
1250 @Override
1251 protected IList< V > sharedValueList() {
1252 return new HashMapValuesList< V >( this, 1, this.size() );
1253 }
1254
1255 /**
1256 * @see org.millscript.commons.util.IMap#size()
1257 */
1258 public int size() {
1259 return this.size;
1260 }
1261
1262 /**
1263 * @see org.millscript.commons.util.UMap#update(java.lang.Object, java.lang.Object)
1264 */
1265 public void update( final K key, final V value ) {
1266 final int pos = key == null ? 0 : ( key.hashCode() & 0x7FFFFFFF ) % this.store.length;
1267 for ( HashMaplet< K, V > hmp = this.store[ pos ]; hmp != null; hmp = hmp.next ) {
1268 if ( hmp.key == null ? key == null : hmp.key.equals( key ) ) {
1269 hmp.value = value;
1270
1271
1272 return;
1273 }
1274 }
1275
1276 throw new NoSuchKeyInMapAlert(
1277 "Only pre-existing keys can have their values updated"
1278 ).culpritKey( key ).decorate( this ).mishap();
1279 }
1280
1281 /**
1282 * Writes this object to the specified {@link ObjectOutputStream}.
1283 *
1284 * @param stream the {@link ObjectOutputStream} to write this object to
1285 * @serialData Writes the default object, followed by the integer
1286 * number of mappings, the integer number of buckets and then an
1287 * alternating sequence of key-value pairs
1288 * @throws IOException if something goes wrong during the
1289 * serialization process
1290 */
1291 private void writeObject( final ObjectOutputStream stream ) throws IOException {
1292
1293 stream.defaultWriteObject();
1294
1295 stream.writeInt( this.size() );
1296
1297 stream.writeInt( this.store.length );
1298
1299 for ( MapIterator< K, V > it = this.iterator( true ); it.hasNext(); ) {
1300 stream.writeObject( it.nextKey() );
1301 stream.writeObject( it.currentValue() );
1302 }
1303 }
1304
1305 }