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