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 import java.lang.ref.Reference;
28 import java.lang.ref.ReferenceQueue;
29 import java.lang.reflect.Field;
30
31 import org.millscript.commons.alert.alerts.Fault;
32 import org.millscript.commons.util.IList;
33 import org.millscript.commons.util.IMap;
34 import org.millscript.commons.util.ListIterator;
35 import org.millscript.commons.util.MapIterator;
36 import org.millscript.commons.util.Maplet;
37 import org.millscript.commons.util.alerts.ListIndexOutOfBoundsAlert;
38 import org.millscript.commons.util.alerts.NoSuchKeyInMapAlert;
39 import org.millscript.commons.util.iterator.AbstractListIterator;
40 import org.millscript.commons.util.iterator.AbstractMapIterator;
41 import org.millscript.commons.util.iterator.ArrayListIterator;
42 import org.millscript.commons.util.list.AbstractIList;
43 import org.millscript.commons.util.list.IArrayList;
44 import org.millscript.commons.util.maplet.IMaplet;
45
46 /**
47 * This class provides a mutable hash <code>Map</code> implementation that
48 * stores keys using {@link java.lang.ref.Reference} objects. This allows
49 * mappings within the map to be removed at the discretion of the garbage
50 * collector, depending on the type of reference used.
51 */
52 public abstract class AbstractEReferenceHashMap< K, V > extends AbstractEMap< K, V > implements Cloneable, Serializable {
53
54
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 map the mutable hash map 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 AbstractEReferenceHashMap< 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 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.getKey();
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 AbstractEReferenceHashMap< ?, ? > 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 AbstractEReferenceHashMap< ?, ? > 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.AbstractEReferenceHashMap.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 Reference< 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 Reference< 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 HashMaplet< K, V > m ) {
306 this.key = m.key;
307 this.value = m.value;
308 }
309
310 /**
311 * @see org.millscript.commons.util.Maplet#getKey()
312 */
313 public K getKey() {
314 if ( this.key == null ) {
315 return null;
316 } else {
317 return this.key.get();
318 }
319 }
320
321 /**
322 * @see org.millscript.commons.util.Maplet#getValue()
323 */
324 public V getValue() {
325 return this.value;
326 }
327
328 }
329
330 /**
331 * This class implements a map iterator which iterates over an array
332 * of hash map buckets, returning each maplet as the value.
333 */
334 public static class HashMapMapletIterator< K, V > extends HashMapXIterator< Maplet< K, V > > {
335
336 /**
337 * Constructs a new hash map iterator to iterate over the specified
338 * array of hash map buckets returning the maplet as the value.
339 *
340 * @param map the mutable hash map to iterate over
341 * @param first the index(one based, inclusive) of the first name
342 * @param last the index(one based, inclusive) of the last name
343 */
344 public HashMapMapletIterator( final AbstractEReferenceHashMap< ?, ? > map, final int first, final int last ) {
345 super( map, first, last );
346 }
347
348 /**
349 * @see org.millscript.commons.util.map.IHashMap.HashMapXIterator#getAppropriateNodePart(org.millscript.commons.util.Maplet)
350 */
351 @Override
352 @SuppressWarnings( "unchecked" )
353 Maplet< K, V > getAppropriateMapletPart( final Maplet< ?, ? > maplet ) {
354 return (Maplet< K, V >) maplet;
355 }
356
357 }
358
359 /**
360 * This class implements an immutable list which is backed by an array of
361 * hash map buckets, but NOTE the values in the list are actually the
362 * individual hash maplets themselves.
363 */
364 public static class HashMapMapletList< K, V > extends HashMapXList< Maplet< K, V > > {
365
366 /**
367 * Constructs a new hash maplet array list of the individual maplets.
368 *
369 * @param map the mutable hash map to use as a backing map
370 * @param first the index(one based, inclusive) of the first name
371 * @param last the index(one based, inclusive) of the last name
372 */
373 HashMapMapletList( final AbstractEReferenceHashMap< ?, ? > map, final int first, final int last ) {
374 super( map, first, last );
375 }
376
377 /**
378 * @see org.millscript.commons.util.map.IHashMap.HashMapXList#getAppropriateNodePart(org.millscript.commons.util.Maplet)
379 */
380 @Override
381 @SuppressWarnings( "unchecked" )
382 Maplet< K, V > getAppropriateMapletPart( final Maplet< ?, ? > maplet ) {
383 return (Maplet< K, V >) maplet;
384 }
385
386 /**
387 * @see org.millscript.commons.util.map.IHashMap.HashMapKeysIterator.HashMapXList#sharedIterator()
388 */
389 @Override
390 ListIterator< Maplet< K, V > > sharedIterator() {
391 return new HashMapMapletIterator< K, V >( this.backingMap, this.firstIndex, this.lastIndex );
392 }
393
394 /**
395 * @see org.millscript.commons.util.map.IHashMap.HashMapXList#sharedSlice(int, int)
396 */
397 @Override
398 IList< Maplet< K, V > > sharedSlice( final int first, final int last ) {
399 return new HashMapMapletList< K, V >( this.backingMap, first, last );
400 }
401
402 }
403
404 /**
405 * This class implements a map iterator which iterates over an array
406 * of hash map buckets, returning each maplet value, sharing the backing
407 * store with it's enclosing mutable map.
408 */
409 public static class HashMapValuesIterator< V > extends HashMapXIterator< V > {
410
411 /**
412 * Constructs a new hash map iterator to iterate over the specified
413 * mutable hash map returning the maplet values.
414 *
415 * @param map the mutable hash map to iterate over
416 * @param first the index(one based, inclusive) of the first name
417 * @param last the index(one based, inclusive) of the last name
418 */
419 public HashMapValuesIterator( final AbstractEReferenceHashMap< ?, ? > map, final int first, final int last ) {
420 super( map, first, last );
421 }
422
423 /**
424 * @see org.millscript.commons.util.map.IHashMap.HashMapXIterator#getAppropriateNodePart(org.millscript.commons.util.Maplet)
425 */
426 @Override
427 @SuppressWarnings( "unchecked" )
428 V getAppropriateMapletPart( final Maplet< ?, ? > maplet ) {
429 return (V) maplet.getValue();
430 }
431
432 }
433
434 /**
435 * This class implements an immutable list which is backed by an array of
436 * hash map buckets, but NOTE the values in the list are actually the
437 * individual hash maplet values. The backing store is shared with it's
438 * enclosing mutable map.
439 */
440 public static class HashMapValuesList< V > extends HashMapXList< V > {
441
442 /**
443 * Constructs a new mutable hash map backed list of the individual
444 * maplet values.
445 *
446 * @param map the mutable hash map to use as a backing list
447 * @param first the index(one based, inclusive) of the first name
448 * @param last the index(one based, inclusive) of the last name
449 */
450 HashMapValuesList( final AbstractEReferenceHashMap< ?, ? > map, final int first, final int last ) {
451 super( map, first, last );
452 }
453
454 /**
455 * @see org.millscript.commons.util.map.IHashMap.HashMapXList#getAppropriateNodePart(org.millscript.commons.util.Maplet)
456 */
457 @Override
458 @SuppressWarnings( "unchecked" )
459 V getAppropriateMapletPart( final Maplet< ?, ? > maplet ) {
460 return (V) maplet.getValue();
461 }
462
463 /**
464 * @see org.millscript.commons.util.map.IHashMap.HashMapKeysIterator.HashMapXList#sharedIterator()
465 */
466 @Override
467 ListIterator< V > sharedIterator() {
468 return new HashMapValuesIterator< V >( this.backingMap, this.firstIndex, this.lastIndex );
469 }
470
471 /**
472 * @see org.millscript.commons.util.map.AbstractEReferenceHashMap.HashMapXList#sharedSlice(int, int)
473 */
474 @Override
475 IList< V > sharedSlice( final int first, final int last ) {
476 return new HashMapValuesList< V >( this.backingMap, first, last );
477 }
478
479 }
480
481 /**
482 * This class implements a map iterator which iterates over an array
483 * of hash map buckets, returning either the keys or values. The backing
484 * store is shared with it's enclosing mutable map.
485 */
486 private static abstract class HashMapXIterator< V > extends AbstractListIterator< V > {
487
488 /**
489 * The maplet for the current point in the iteration.
490 */
491 private HashMaplet< ?, ? > currentMaplet;
492
493 /**
494 * The next maplet in the iteration. If this is <code>null</code> there
495 * are no more elements in the iteration.
496 */
497 private HashMaplet< ?, ? > nextMaplet;
498
499 /**
500 * The current position of the iterator within the hash map bucket
501 * array.
502 */
503 private int bucketIndex = -1;
504
505 /**
506 * The number of elements this iterator will return.
507 */
508 private final int size;
509
510 /**
511 * The backing store for this hash map is a fixed array of HashMaplet
512 * buckets.
513 */
514 private final HashMaplet< ?, ? >[] store;
515
516 /**
517 * Constructs a new hash map iterator to iterate over the specified
518 * mutable hash map returning either the maplet keys or values.
519 *
520 * @param map the mutable hash map to iterate over
521 * @param first the index(one based, inclusive) of the first name
522 * @param last the index(one based, inclusive) of the last name
523 */
524 public HashMapXIterator( final AbstractEReferenceHashMap< ?, ? > map, final int first, final int last ) {
525 int fb = 0;
526 HashMaplet< ?, ? > fm = null;
527 int totalMaplets = 0;
528
529 for ( int i = 0; i < map.store.length; i++ ) {
530
531 for ( HashMaplet< ?, ? > hmp = map.store[ i ]; hmp != null; hmp = hmp.next ) {
532
533 if ( ++totalMaplets == first ) {
534
535 fb = i;
536 fm = hmp;
537 }
538 }
539 }
540 if ( first > last ) {
541 this.currentMaplet = null;
542 this.nextMaplet = null;
543 this.bucketIndex = 0;
544 this.size = 0;
545 this.store = null;
546 } else if ( first < 1 || first > totalMaplets ) {
547 throw new ListIndexOutOfBoundsAlert(
548 "First index in slice must be between 1 and the number of entries in the map"
549 ).culprit(
550 "index",
551 first
552 ).decorate( map ).mishap();
553 } else if ( last > totalMaplets ) {
554 throw new ListIndexOutOfBoundsAlert(
555 "Last index in slice must not be greater than the number of entries in the map"
556 ).culprit(
557 "index",
558 last
559 ).decorate( map ).mishap();
560 } else {
561 this.currentMaplet = null;
562 this.nextMaplet = fm;
563 this.bucketIndex = fb;
564 this.size = last - first + 1;
565 this.store = map.store;
566 }
567 }
568
569 /**
570 * @see org.millscript.commons.util.iterator.AbstractMapIterator#advance()
571 */
572 @Override
573 protected void advance() {
574
575 super.advance();
576
577 this.currentMaplet = this.nextMaplet;
578 this.nextMaplet = this.nextMaplet.next;
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 V getAppropriateMapletPart( Maplet< ?, ? > maplet );
605
606 /**
607 * @see org.millscript.commons.util.iterator.AbstractMapIterator#getValue()
608 */
609 @Override
610 protected V 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 super.position > this.size || 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< V > extends AbstractIList< V > {
638
639 /**
640 * The mutable hash map this list gets its backing store from.
641 */
642 final AbstractEReferenceHashMap< ?, ? > 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 AbstractEReferenceHashMap< ?, ? > 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 V 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< V > doSlice( final int first, final int last, final boolean share ) {
753 if ( share ) {
754 return this.sharedSlice( first, last );
755 } else {
756
757 final V[] objects = (V[]) 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< V >( 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 V getAppropriateMapletPart( Maplet< ?, ? > maplet );
781
782 /**
783 * @see org.millscript.commons.util.IList#indexOf(java.lang.Object)
784 */
785 public int indexOf( final V 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< V > iterator( final boolean share ) {
824 if ( share ) {
825 return this.sharedIterator();
826 } else {
827
828
829 final V[] objects = (V[]) 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< V >( 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< V > 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< V > 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 /**
871 * The reference queue we'll use to keep track of collected keys.
872 */
873 protected final transient ReferenceQueue< K > referenceQueue = new ReferenceQueue< K >();
874
875 /**
876 * The size(number of mappings) in this map.
877 */
878 private transient int size;
879
880
881 /**
882 * The backing store for this hash map is a variable array of HashMaplet
883 * buckets.
884 */
885 transient HashMaplet< K, V >[] store;
886
887 private transient int triggerRehashSize;
888
889 /**
890 * Constructs a new, emtpy mutable hash map.
891 */
892 @SuppressWarnings( "unchecked" )
893 public AbstractEReferenceHashMap() {
894 this.store = new HashMaplet[ DEFAULT_CAPACITY ];
895 this.triggerRehashSize = (int) ( DEFAULT_CAPACITY * DEFAULT_LOAD_FACTOR );
896 }
897
898 /**
899 * Constructs a new mutable hash map which contains all the mappings from
900 * the specified map.
901 *
902 * @param map the <code>Map</code> to copy mappings from
903 */
904 @SuppressWarnings( "unchecked" )
905 public AbstractEReferenceHashMap( final IMap< K, V > map ) {
906 final MapIterator< K, V > it = map.iterator( true );
907 final HashMaplet< K, V >[] maplets = new HashMaplet[ map.size() * 2 + 1 ];
908 while ( it.hasNext() ) {
909 final int pos = it.nextKey() == null ? 0 : ( it.currentKey().hashCode() & 0x7FFFFFFF ) % maplets.length;
910 if ( maplets[ pos ] == null ) {
911 maplets[ pos ] = new HashMaplet< K, V >( this.makeReference( it.currentKey() ), it.currentValue() );
912 this.size++;
913 } else {
914 for ( HashMaplet< K, V > hmp = maplets[ pos ]; hmp != null; hmp = hmp.next ) {
915 if ( hmp.getKey() == null ? it.currentKey() == null : hmp.getKey().equals( it.currentKey() ) ) {
916 hmp.value = it.currentValue();
917 break;
918 } else if ( hmp.next == null ) {
919 hmp.next = new HashMaplet< K, V >( this.makeReference( it.currentKey() ), it.currentValue() );
920 this.size++;
921 }
922 }
923 }
924 }
925 this.store = maplets;
926 this.triggerRehashSize = (int) ( this.store.length * DEFAULT_LOAD_FACTOR );
927 }
928
929 /**
930 * This method should be called to clear any queued references, which
931 * implies the keys are no longer valid in this mapping.
932 */
933 protected void clearQueuedReferences() {
934 for ( Reference< ? extends K > ref = this.referenceQueue.poll(); ref != null; ref = this.referenceQueue.poll() ) {
935
936
937 HashMaplet< K, V > previousInChain = null;
938 HashMaplet< K, V > currentInChain = null;
939 for ( int i = 0; i < this.store.length; ) {
940 if ( currentInChain == null ) {
941 previousInChain = null;
942 currentInChain = this.store[ i++ ];
943
944
945 continue;
946 } else if ( currentInChain.key == ref ) {
947
948 if ( previousInChain == null ) {
949
950
951 this.store[ i ] = currentInChain.next;
952 } else {
953
954
955 previousInChain.next = currentInChain.next;
956 }
957 this.size--;
958
959
960 break;
961 } else {
962 previousInChain = currentInChain;
963 currentInChain = currentInChain.next;
964 }
965 }
966 }
967 }
968
969 /**
970 * @see java.lang.Object#clone()
971 */
972 @Override
973 @SuppressWarnings( "unchecked" )
974 public Object clone() throws CloneNotSupportedException {
975 final AbstractEReferenceHashMap< K, V > map = (AbstractEReferenceHashMap< K, V >) super.clone();
976 map.store = new HashMaplet[ this.store.length ];
977 for ( int i = 0; i < this.store.length; i++ ) {
978 HashMaplet< K, V > clonedMaplet = null;
979 for ( HashMaplet< K, V > originalMaplet = this.store[ i ]; originalMaplet != null; originalMaplet = originalMaplet.next ) {
980 if ( clonedMaplet == null ) {
981 clonedMaplet = new HashMaplet< K, V >(
982 this.makeReference( originalMaplet.getKey() ),
983 originalMaplet.getValue()
984 );
985 map.store[ i ] = clonedMaplet;
986 } else {
987 clonedMaplet.next = new HashMaplet< K, V >(
988 this.makeReference( originalMaplet.getKey() ),
989 originalMaplet.getValue()
990 );
991 clonedMaplet = clonedMaplet.next;
992 }
993 }
994 }
995 return map;
996 }
997
998 /**
999 * @see org.millscript.commons.util.IMap#contains(java.lang.Object, java.lang.Object)
1000 */
1001 public boolean contains( final K key, final V value ) {
1002 this.clearQueuedReferences();
1003 final int pos = key == null ? 0 : ( key.hashCode() & 0x7FFFFFFF ) % this.store.length;
1004 for ( HashMaplet< K, V > hmp = this.store[ pos ]; hmp != null; hmp = hmp.next ) {
1005 if ( key == null ? hmp.getKey() == null : key.equals( hmp.getKey() ) ) {
1006
1007
1008 return value == null ? hmp.value == null
1009 : value.equals( hmp.value );
1010 }
1011 }
1012 return false;
1013 }
1014
1015 /**
1016 * @see org.millscript.commons.util.IMap#containsKey(java.lang.Object)
1017 */
1018 public boolean containsKey( final K key ) {
1019 this.clearQueuedReferences();
1020 final int pos = key == null ? 0 : ( key.hashCode() & 0x7FFFFFFF ) % this.store.length;
1021 for ( HashMaplet< K, V > hmp = this.store[ pos ]; hmp != null; hmp = hmp.next ) {
1022 if ( key == null ? hmp.getKey() == null : key.equals( hmp.getKey() ) ) {
1023 return true;
1024 }
1025 }
1026 return false;
1027 }
1028
1029 /**
1030 * @see org.millscript.commons.util.IMap#containsValue(java.lang.Object)
1031 */
1032 public boolean containsValue( final V value ) {
1033 this.clearQueuedReferences();
1034
1035 for ( int i = 0; i < this.store.length; i++ ) {
1036 for ( HashMaplet< K, V > hmp = this.store[ i ]; hmp != null; hmp = hmp.next ) {
1037 if ( value == null ? hmp.value == null : value.equals( hmp.value ) ) {
1038 return true;
1039 }
1040 }
1041 }
1042 return false;
1043 }
1044
1045 /**
1046 * @see org.millscript.commons.util.IMap#get(java.lang.Object)
1047 */
1048 public V get( final K key ) {
1049 this.clearQueuedReferences();
1050 final int pos = key == null ? 0 : ( key.hashCode() & 0x7FFFFFFF ) % this.store.length;
1051 for ( HashMaplet< K, V > hmp = this.store[ pos ]; hmp != null; hmp = hmp.next ) {
1052 if ( key == null ? hmp.getKey() == null : key.equals( hmp.getKey() ) ) {
1053 return hmp.value;
1054 }
1055 }
1056 return this.getDefault().get( this, key );
1057 }
1058
1059 /**
1060 * @see org.millscript.commons.util.EMap#insert(java.lang.Object, java.lang.Object)
1061 */
1062 public void insert( final K key, final V value ) {
1063 this.clearQueuedReferences();
1064 final int pos = key == null ? 0 : ( key.hashCode() & 0x7FFFFFFF ) % this.store.length;
1065 if ( this.store[ pos ] == null ) {
1066 this.store[ pos ] = new HashMaplet< K, V >( this.makeReference( key ), value );
1067
1068 this.size++;
1069 } else {
1070 for ( HashMaplet< K, V > hmp = this.store[ pos ]; hmp != null; hmp = hmp.next ) {
1071 if ( key == null ? hmp.getKey() == null : key.equals( hmp.getKey() ) ) {
1072
1073
1074 hmp.value = value;
1075 break;
1076 } else if ( hmp.next == null ) {
1077
1078
1079
1080
1081 if ( this.size == this.triggerRehashSize ) {
1082 this.insertWithRehash( key, value );
1083 } else {
1084 hmp.next = new HashMaplet< K, V >( this.makeReference( key ), value );
1085
1086 this.size++;
1087 }
1088 break;
1089 }
1090 }
1091 }
1092 }
1093
1094 /**
1095 * Inserts the specified key-value mapping after performing a rehash of the
1096 * backing store to increase it's size.
1097 *
1098 * @param key the new key to add to the mapping
1099 * @param value the new value to associate with the given key
1100 */
1101 @SuppressWarnings( "unchecked" )
1102 protected void insertWithRehash( final K key, final V value ) {
1103 final HashMaplet< K, V >[] newStore = new HashMaplet[ this.store.length * 2 + 1 ];
1104 for ( int i = 0; i < this.store.length; i++ ) {
1105 HashMaplet< K, V > hashMaplet = this.store[ i ];
1106 while ( hashMaplet != null ) {
1107 final int pos = hashMaplet.getKey() == null ? 0 : ( hashMaplet.getKey().hashCode() & 0x7FFFFFFF ) % newStore.length;
1108 if ( newStore[ pos ] == null ) {
1109 newStore[ pos ] = new HashMaplet< K, V >( hashMaplet );
1110 } else {
1111
1112
1113
1114 for ( HashMaplet< K, V > hmp = newStore[ pos ]; hmp != null; hmp = hmp.next ) {
1115 if ( hmp.getKey() == null ? hashMaplet.getKey() == null : hmp.getKey().equals( hashMaplet.getKey() ) ) {
1116 hmp.value = hashMaplet.value;
1117 break;
1118 } else if ( hmp.next == null ) {
1119 hmp.next = new HashMaplet< K, V >( hashMaplet );
1120 break;
1121 }
1122 }
1123 }
1124 hashMaplet = hashMaplet.next;
1125 }
1126 }
1127 this.store = newStore;
1128 this.triggerRehashSize = (int) ( this.store.length * DEFAULT_LOAD_FACTOR );
1129
1130 this.insert( key, value );
1131 }
1132
1133 /**
1134 * @see org.millscript.commons.util.IMap#iterator(boolean)
1135 */
1136 @SuppressWarnings( "unchecked" )
1137 public MapIterator< K, V > iterator( final boolean share ) {
1138 if ( share ) {
1139 return new HashMapIterator< K, V >( this, true );
1140 } else {
1141
1142
1143
1144 final Maplet< K, V >[] maplets = new Maplet[ this.size() ];
1145 for ( int i = 0, j = 0; i < this.store.length; i++ ) {
1146 for ( HashMaplet< K, V > maplet = this.store[ i ]; maplet != null; maplet = maplet.next ) {
1147 maplets[ j++ ] = new IMaplet< K, V >( maplet );
1148 }
1149 }
1150 return new IMapletArrayMap.MapletArrayMapIterator< K, V >( maplets, true );
1151 }
1152 }
1153
1154 public abstract Reference< K > makeReference( final K key );
1155
1156 /**
1157 * Reads this object from the specified {@link ObjectInputStream}.
1158 *
1159 * @param stream the {@link ObjectInputStream} to read the objects data
1160 * from
1161 * @serialData Reads the default object, followed by the integer
1162 * number of mappings, the integer number of buckets and then an
1163 * alternating sequence of key-value pairs
1164 * @throws ClassNotFoundException if a required class cannot be found
1165 * @throws IOException if something goes wrong during the
1166 * deserialization process
1167 * @throws NoSuchFieldException
1168 * @throws SecurityException
1169 * @throws IllegalAccessException
1170 * @throws IllegalArgumentException
1171 */
1172 @SuppressWarnings( "unchecked" )
1173 private void readObject( final ObjectInputStream stream ) throws ClassNotFoundException, IOException, SecurityException, NoSuchFieldException, IllegalArgumentException, IllegalAccessException {
1174
1175 stream.defaultReadObject();
1176
1177
1178
1179
1180
1181
1182 final Field referenceQueue = AbstractEReferenceHashMap.class.getDeclaredField( "referenceQueue" );
1183 referenceQueue.setAccessible( true );
1184 referenceQueue.set( this, new ReferenceQueue< K >() );
1185 referenceQueue.setAccessible( false );
1186
1187 this.size = stream.readInt();
1188
1189 this.store = new HashMaplet[ stream.readInt() ];
1190
1191 this.triggerRehashSize = (int) ( this.store.length * DEFAULT_LOAD_FACTOR );
1192
1193 for ( int i = 0; i < size; i++ ) {
1194 final K key = (K) stream.readObject();
1195 final V value = (V) stream.readObject();
1196 final int pos = key == null ? 0 : ( key.hashCode() & 0x7FFFFFFF ) % this.store.length;
1197 if ( this.store[ pos ] == null ) {
1198 this.store[ pos ] = new HashMaplet< K, V >( this.makeReference( key ), value );
1199 } else {
1200
1201 HashMaplet< K, V > hmp = this.store[ pos ];
1202 while ( hmp.next != null ) {
1203 hmp = hmp.next;
1204 }
1205 hmp.next = new HashMaplet< K, V >( this.makeReference( key ), value );
1206 }
1207 }
1208 }
1209
1210 /**
1211 * @see org.millscript.commons.util.EMap#remove(java.lang.Object, java.lang.Object)
1212 */
1213 public void remove( final K key, final V value ) {
1214 this.clearQueuedReferences();
1215 final int pos = key == null ? 0 : ( key.hashCode() & 0x7FFFFFFF ) % this.store.length;
1216 HashMaplet< K, V > previousInChain = null;
1217 for ( HashMaplet< K, V > hmp = this.store[ pos ]; hmp != null; hmp = hmp.next ) {
1218 if ( key == null ? hmp.getKey() == null : key.equals( hmp.getKey() ) ) {
1219
1220 if ( value == null ? hmp.value == null : value.equals( hmp.value ) ) {
1221
1222
1223 if ( previousInChain == null ) {
1224
1225
1226 this.store[ pos ] = hmp.next;
1227 } else {
1228
1229
1230 previousInChain.next = hmp.next;
1231 }
1232
1233 hmp.key.clear();
1234 this.size--;
1235 break;
1236 }
1237 }
1238
1239
1240 previousInChain = hmp;
1241 }
1242 }
1243
1244 /**
1245 * @see org.millscript.commons.util.EMap#removeAll()
1246 */
1247 @SuppressWarnings( "unchecked" )
1248 public void removeAll() {
1249 this.size = 0;
1250 this.store = new HashMaplet[ DEFAULT_CAPACITY ];
1251 this.triggerRehashSize = (int) ( DEFAULT_CAPACITY * DEFAULT_LOAD_FACTOR );
1252 }
1253
1254 /**
1255 * @see org.millscript.commons.util.EMap#removeKey(java.lang.Object)
1256 */
1257 public void removeKey( final K key ) {
1258 this.clearQueuedReferences();
1259 final int pos = key == null ? 0 : ( key.hashCode() & 0x7FFFFFFF ) % this.store.length;
1260 HashMaplet< K, V > previousInChain = null;
1261 for ( HashMaplet< K, V > hmp = this.store[ pos ]; hmp != null; hmp = hmp.next ) {
1262 if ( key == null ? hmp.getKey() == null : key.equals( hmp.getKey() ) ) {
1263
1264 if ( previousInChain == null ) {
1265
1266
1267 this.store[ pos ] = hmp.next;
1268 } else {
1269
1270
1271 previousInChain.next = hmp.next;
1272 }
1273
1274 hmp.key.clear();
1275 this.size--;
1276 break;
1277 } else {
1278 previousInChain = hmp;
1279 }
1280 }
1281 }
1282
1283 /**
1284 * @see org.millscript.commons.util.EMap#removeValue(java.lang.Object)
1285 */
1286 public void removeValue( final V value ) {
1287 this.clearQueuedReferences();
1288
1289 for ( int i = 0; i < this.store.length; i++ ) {
1290 HashMaplet< K, V > previousInChain = null;
1291 for ( HashMaplet< K, V > hmp = this.store[ i ]; hmp != null; hmp = hmp.next ) {
1292 if ( value == null ? hmp.value == null : value.equals( hmp.value ) ) {
1293
1294 if ( previousInChain == null ) {
1295
1296
1297 this.store[ i ] = hmp.next;
1298 } else {
1299
1300
1301 previousInChain.next = hmp.next;
1302 }
1303 hmp.key.clear();
1304 this.size--;
1305 } else {
1306 previousInChain = hmp;
1307 }
1308 }
1309 }
1310 }
1311
1312 /**
1313 * @see org.millscript.commons.util.map.AbstractIMap#sharedKeyList()
1314 */
1315 @Override
1316 protected IList< K > sharedKeyList() {
1317 return new HashMapKeysList< K >( this, 1, this.size() );
1318 }
1319
1320 /**
1321 * @see org.millscript.commons.util.map.AbstractIMap#sharedMapletList()
1322 */
1323 @Override
1324 protected IList< Maplet< K, V > > sharedMapletList() {
1325 return new HashMapMapletList< K, V >( this, 1, this.size() );
1326 }
1327
1328 /**
1329 * @see org.millscript.commons.util.map.AbstractIMap#sharedValueList()
1330 */
1331 @Override
1332 protected IList< V > sharedValueList() {
1333 return new HashMapValuesList< V >( this, 1, this.size() );
1334 }
1335
1336 /**
1337 * @see org.millscript.commons.util.IMap#size()
1338 */
1339 public int size() {
1340 return this.size;
1341 }
1342
1343 /**
1344 * @see org.millscript.commons.util.UMap#update(java.lang.Object, java.lang.Object)
1345 */
1346 public void update( final K key, final V value ) {
1347 this.clearQueuedReferences();
1348 final int pos = key == null ? 0 : ( key.hashCode() & 0x7FFFFFFF ) % this.store.length;
1349 for ( HashMaplet< K, V > hmp = this.store[ pos ]; hmp != null; hmp = hmp.next ) {
1350 if ( key == null ? hmp.getKey() == null : key.equals( hmp.getKey() ) ) {
1351 hmp.value = value;
1352
1353
1354 return;
1355 }
1356 }
1357
1358 throw new NoSuchKeyInMapAlert(
1359 "Only pre-existing keys can have their values updated"
1360 ).culpritKey( key ).decorate( this ).mishap();
1361 }
1362
1363 /**
1364 * Writes this object to the specified {@link ObjectOutputStream}.
1365 *
1366 * @param stream the {@link ObjectOutputStream} to write this object to
1367 * @serialData Writes the default object, followed by the integer
1368 * number of mappings, the integer number of buckets and then an
1369 * alternating sequence of key-value pairs
1370 * @throws IOException if something goes wrong during the
1371 * serialization process
1372 */
1373 private void writeObject( final ObjectOutputStream stream ) throws IOException {
1374
1375 stream.defaultWriteObject();
1376
1377 stream.writeInt( this.size() );
1378
1379 stream.writeInt( this.store.length );
1380
1381 for ( MapIterator< K, V > it = this.iterator( true ); it.hasNext(); ) {
1382 stream.writeObject( it.nextKey() );
1383 stream.writeObject( it.currentValue() );
1384 }
1385 }
1386
1387 }