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.Serializable;
24
25 import org.millscript.commons.alert.alerts.Fault;
26 import org.millscript.commons.util.IList;
27 import org.millscript.commons.util.IMap;
28 import org.millscript.commons.util.ListIterator;
29 import org.millscript.commons.util.MapIterator;
30 import org.millscript.commons.util.Maplet;
31 import org.millscript.commons.util.alerts.KeyAlreadyExistsAlert;
32 import org.millscript.commons.util.alerts.ListIndexOutOfBoundsAlert;
33 import org.millscript.commons.util.iterator.AbstractListIterator;
34 import org.millscript.commons.util.iterator.AbstractMapIterator;
35 import org.millscript.commons.util.iterator.ArrayListIterator;
36 import org.millscript.commons.util.list.AbstractIList;
37 import org.millscript.commons.util.list.IArrayList;
38 import org.millscript.commons.util.maplet.IMaplet;
39
40 /**
41 * This class provides an immutable <code>Map</code> implementation that uses
42 * an array of hash code buckets to store the data.
43 */
44 public class IHashMap< K, V > extends AbstractIMap< K, V > implements Cloneable, Serializable {
45
46 /**
47 * This is the ID from the release 0.1.0 for future compatibility.
48 */
49 private static final long serialVersionUID = 4139147353786425142L;
50
51 /**
52 * This class implements a map iterator which iterates over an array
53 * of hash map buckets.
54 */
55 public static class HashMapIterator< K, V > extends AbstractMapIterator< K, V > {
56
57 /**
58 * The maplet for the current point in the iteration.
59 */
60 private HashMaplet< K, V > currentMaplet;
61
62 /**
63 * The next maplet in the iteration. If this is <code>null</code> there
64 * are no more elements in the iteration.
65 */
66 private HashMaplet< K, V > nextMaplet;
67
68 /**
69 * The current position of the iterator within the hash map bucket
70 * array.
71 */
72 private int pos = -1;
73
74 /**
75 * The backing store for this hash map is a fixed array of HashMaplet
76 * buckets.
77 */
78 private final HashMaplet< K, V >[] store;
79
80 /**
81 * Constructs a new hash map iterator to iterate over the specified
82 * array of hash map buckets.
83 *
84 * @param maplets the array of hash map buckets to iterate over
85 * @param share if <code>true</code> the specified object array will be
86 * shared otherwise the array will be copied.
87 */
88 @SuppressWarnings( "unchecked" )
89 public HashMapIterator( final HashMaplet< K, V >[] maplets, final boolean share ) {
90 if ( share ) {
91 this.store = maplets;
92 } else {
93 this.store = new HashMaplet[ maplets.length ];
94 for ( int i = 0; i < maplets.length; i++ ) {
95 HashMaplet< K, V > maplet = maplets[ i ];
96 if ( maplet != null ) {
97 HashMaplet< K, V > copy = new HashMaplet< K, V >( maplet );
98 this.store[ i ] = copy;
99 for ( maplet = maplet.next; maplet != null; maplet = maplet.next ) {
100 copy.next = new HashMaplet< K, V >( maplet );
101 }
102 }
103 }
104 }
105 }
106
107 /**
108 * @see org.millscript.commons.util.iterator.AbstractMapIterator#advance()
109 */
110 @Override
111 protected void advance() {
112
113 this.checkNext();
114
115 this.currentMaplet = this.nextMaplet;
116 if ( this.nextMaplet == null ) {
117 this.nextMaplet = null;
118 } else {
119 this.nextMaplet = this.nextMaplet.next;
120 }
121 }
122
123 /**
124 * Checks that the next maplet field is populated with the next maplet
125 * if one is available.
126 */
127 private void checkNext() {
128 if ( this.nextMaplet == null && this.store != null ) {
129
130 if ( ++pos < this.store.length ) {
131 this.nextMaplet = this.store[ pos ];
132
133 this.checkNext();
134 }
135 }
136 }
137
138 /**
139 * @see org.millscript.commons.util.iterator.AbstractMapIterator#getKey()
140 */
141 @Override
142 protected K getKey() {
143 return this.currentMaplet.getKey();
144 }
145
146 /**
147 * @see org.millscript.commons.util.iterator.AbstractMapIterator#getMaplet()
148 */
149 @Override
150 protected Maplet< K, V > getMaplet() {
151 return this.currentMaplet;
152 }
153
154 /**
155 * @see org.millscript.commons.util.iterator.AbstractMapIterator#getValue()
156 */
157 @Override
158 protected V getValue() {
159 return this.currentMaplet.getValue();
160 }
161
162 /**
163 * @see org.millscript.commons.util.MapIterator#hasNext()
164 */
165 public boolean hasNext() {
166 this.checkNext();
167 return this.nextMaplet != null;
168 }
169
170 /**
171 * @see org.millscript.commons.util.iterator.AbstractMapIterator#outOfBounds()
172 */
173 @Override
174 protected boolean outOfBounds() {
175 return this.currentMaplet == null;
176 }
177
178 }
179
180 /**
181 * This class implements a map iterator which iterates over an array
182 * of hash map buckets, returning each maplet key.
183 */
184 public static class HashMapKeysIterator< K > extends HashMapXIterator< K > {
185
186 /**
187 * Constructs a new hash map iterator to iterate over the specified
188 * array of hash map buckets returning the maplet keys.
189 *
190 * @param maplets the array of hash map buckets to iterate over
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 HashMapKeysIterator( final HashMaplet< ?, ? >[] maplets, final int first, final int last ) {
195 super( maplets, first, last );
196 }
197
198 /**
199 * @see org.millscript.commons.util.map.IHashMap.HashMapXIterator#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
209 /**
210 * This class implements an immutable list which is backed by an array of
211 * hash map buckets, but NOTE the values in the list are actually the
212 * individual hash maplet keys.
213 */
214 public static class HashMapKeysList< K > extends HashMapXList< K > {
215
216 /**
217 * Constructs a new hash maplet array list of the individual maplet
218 * keys.
219 *
220 * @param maplets the backing array of maplets
221 * @param first the index(one based, inclusive) of the first name
222 * @param last the index(one based, inclusive) of the last name
223 */
224 HashMapKeysList( final HashMaplet< ?, ? >[] maplets, final int first, final int last ) {
225 super( maplets, first, last );
226 }
227
228 /**
229 * @see org.millscript.commons.util.map.IHashMap.HashMapXList#getAppropriateMapletPart(org.millscript.commons.util.Maplet)
230 */
231 @Override
232 @SuppressWarnings( "unchecked" )
233 K getAppropriateMapletPart( final Maplet< ?, ? > maplet ) {
234 return (K) maplet.getKey();
235 }
236
237 /**
238 * @see org.millscript.commons.util.map.IHashMap.HashMapKeysIterator.HashMapXList#sharedIterator()
239 */
240 @Override
241 ListIterator< K > sharedIterator() {
242 return new HashMapKeysIterator< K >( this.store, this.firstIndex, this.lastIndex );
243 }
244
245 /**
246 * @see org.millscript.commons.util.map.IHashMap.HashMapXList#sharedSlice(int, int)
247 */
248 @Override
249 IList< K > sharedSlice( final int first, final int last ) {
250 return new HashMapKeysList< K >( this.store, first, last );
251 }
252
253 }
254
255 /**
256 * This class provides an immutable implementation of a <code>Maplet</code>
257 * which also acts as a bucket in our hashmap.
258 */
259 private static class HashMaplet< K, V > extends IMaplet< K, V > {
260
261 /**
262 * This is the ID from the release 0.1.0 for future compatibility.
263 */
264 private static final long serialVersionUID = 1031069510688414098L;
265
266 /**
267 * The next hash maplet in this chain.
268 */
269 HashMaplet< K, V > next;
270
271 /**
272 * Constructs a new hash maplet with the given key and value.
273 *
274 * @param k the maplets key
275 * @param v the maplets value
276 */
277 private HashMaplet( final K k, final V v ) {
278 super( k, v );
279 }
280
281 /**
282 * Constructs a new hash maplet taking its key and value from the
283 * specified maplet.
284 *
285 * @param m the maplet to copy the key and value from
286 */
287 private HashMaplet( final Maplet< K, V > m ) {
288 super( m );
289 }
290
291 }
292
293 /**
294 * This class implements a map iterator which iterates over an array
295 * of hash map buckets, returning each maplet as the value.
296 */
297 public static class HashMapMapletIterator< K, V > extends HashMapXIterator< Maplet< K, V > > {
298
299 /**
300 * Constructs a new hash map iterator to iterate over the specified
301 * array of hash map buckets returning the maplet as the value.
302 *
303 * @param maplets the array of hash map buckets to iterate over
304 * @param first the index(one based, inclusive) of the first name
305 * @param last the index(one based, inclusive) of the last name
306 */
307 public HashMapMapletIterator( final HashMaplet< ?, ? >[] maplets, final int first, final int last ) {
308 super( maplets, first, last );
309 }
310
311 /**
312 * @see org.millscript.commons.util.map.IHashMap.HashMapXIterator#getAppropriateMapletPart(org.millscript.commons.util.Maplet)
313 */
314 @Override
315 @SuppressWarnings( "unchecked" )
316 Maplet< K, V > getAppropriateMapletPart( final Maplet< ?, ? > maplet ) {
317 return (Maplet< K, V >) maplet;
318 }
319
320 }
321
322 /**
323 * This class implements an immutable list which is backed by an array of
324 * hash map buckets, but NOTE the values in the list are actually the
325 * individual hash maplets themselves.
326 */
327 public static class HashMapMapletList< K, V > extends HashMapXList< Maplet< K, V > > {
328
329 /**
330 * Constructs a new hash maplet array list of the individual maplets.
331 *
332 * @param maplets the backing array of maplets
333 * @param first the index(one based, inclusive) of the first name
334 * @param last the index(one based, inclusive) of the last name
335 */
336 HashMapMapletList( final HashMaplet< ?, ? >[] maplets, final int first, final int last ) {
337 super( maplets, first, last );
338 }
339
340 /**
341 * @see org.millscript.commons.util.map.IHashMap.HashMapXList#getAppropriateMapletPart(org.millscript.commons.util.Maplet)
342 */
343 @Override
344 @SuppressWarnings( "unchecked" )
345 Maplet< K, V > getAppropriateMapletPart( final Maplet< ?, ? > maplet ) {
346 return (Maplet< K, V >) maplet;
347 }
348
349 /**
350 * @see org.millscript.commons.util.map.IHashMap.HashMapKeysIterator.HashMapXList#sharedIterator()
351 */
352 @Override
353 ListIterator< Maplet< K, V > > sharedIterator() {
354 return new HashMapMapletIterator< K, V >( this.store, this.firstIndex, this.lastIndex );
355 }
356
357 /**
358 * @see org.millscript.commons.util.map.IHashMap.HashMapXList#sharedSlice(int, int)
359 */
360 @Override
361 IList< Maplet< K, V > > sharedSlice( final int first, final int last ) {
362 return new HashMapMapletList< K, V >( this.store, first, last );
363 }
364
365 }
366
367 /**
368 * This class implements a map iterator which iterates over an array
369 * of hash map buckets, returning each maplet value.
370 */
371 public static class HashMapValuesIterator< V > extends HashMapXIterator< V > {
372
373 /**
374 * Constructs a new hash map iterator to iterate over the specified
375 * array of hash map buckets returning the maplet values.
376 *
377 * @param maplets the array of hash map buckets to iterate over
378 * @param first the index(one based, inclusive) of the first name
379 * @param last the index(one based, inclusive) of the last name
380 */
381 public HashMapValuesIterator( final HashMaplet< ?, ? >[] maplets, final int first, final int last ) {
382 super( maplets, first, last );
383 }
384
385 /**
386 * @see org.millscript.commons.util.map.IHashMap.HashMapXIterator#getAppropriateMapletPart(org.millscript.commons.util.Maplet)
387 */
388 @Override
389 @SuppressWarnings( "unchecked" )
390 V getAppropriateMapletPart( final Maplet< ?, ? > maplet ) {
391 return (V) maplet.getValue();
392 }
393
394 }
395
396 /**
397 * This class implements an immutable list which is backed by an array of
398 * hash map buckets, but NOTE the values in the list are actually the
399 * individual hash maplet values.
400 */
401 public static class HashMapValuesList< V > extends HashMapXList< V > {
402
403 /**
404 * Constructs a new hash maplet array list of the individual maplet
405 * values.
406 *
407 * @param maplets the backing array of maplets
408 * @param first the index(one based, inclusive) of the first name
409 * @param last the index(one based, inclusive) of the last name
410 */
411 HashMapValuesList( final HashMaplet< ?, ? >[] maplets, final int first, final int last ) {
412 super( maplets, first, last );
413 }
414
415 /**
416 * @see org.millscript.commons.util.map.IHashMap.HashMapXList#getAppropriateMapletPart(org.millscript.commons.util.Maplet)
417 */
418 @Override
419 @SuppressWarnings( "unchecked" )
420 V getAppropriateMapletPart( final Maplet< ?, ? > maplet ) {
421 return (V) maplet.getValue();
422 }
423
424 /**
425 * @see org.millscript.commons.util.map.IHashMap.HashMapKeysIterator.HashMapXList#sharedIterator()
426 */
427 @Override
428 ListIterator< V > sharedIterator() {
429 return new HashMapValuesIterator< V >( this.store, this.firstIndex, this.lastIndex );
430 }
431
432 /**
433 * @see org.millscript.commons.util.map.IHashMap.HashMapXList#sharedSlice(int, int)
434 */
435 @Override
436 IList< V > sharedSlice( final int first, final int last ) {
437 return new HashMapValuesList< V >( this.store, first, last );
438 }
439
440 }
441
442 /**
443 * This class implements a map iterator which iterates over an array
444 * of hash map buckets, returning either the keys or values.
445 */
446 private static abstract class HashMapXIterator< V > extends AbstractListIterator< V > {
447
448 /**
449 * The maplet for the current point in the iteration.
450 */
451 private HashMaplet< ?, ? > currentMaplet;
452
453 /**
454 * The next maplet in the iteration. If this is <code>null</code> there
455 * are no more elements in the iteration.
456 */
457 private HashMaplet< ?, ? > nextMaplet;
458
459 /**
460 * The current position of the iterator within the hash map bucket
461 * array.
462 */
463 private int bucketIndex = -1;
464
465 /**
466 * The number of elements this iterator will return.
467 */
468 private final int size;
469
470 /**
471 * The backing store for this hash map is a fixed array of HashMaplet
472 * buckets.
473 */
474 private final HashMaplet< ?, ? >[] store;
475
476 /**
477 * Constructs a new hash map iterator to iterate over the specified
478 * array of hash map buckets returning either the maplet keys or
479 * values.
480 *
481 * @param maplets the array of hash map buckets to iterate over
482 * @param first the index(one based, inclusive) of the first name
483 * @param last the index(one based, inclusive) of the last name
484 */
485 public HashMapXIterator( final HashMaplet< ?, ? >[] maplets, final int first, final int last ) {
486 int fb = 0;
487 HashMaplet< ?, ? > fm = null;
488 int totalMaplets = 0;
489
490 for ( int i = 0; i < maplets.length; i++ ) {
491
492 for ( HashMaplet< ?, ? > hmp = maplets[ i ]; hmp != null; hmp = hmp.next ) {
493
494 if ( ++totalMaplets == first ) {
495
496 fb = i;
497 fm = hmp;
498 }
499 }
500 }
501 if ( first > last ) {
502 this.currentMaplet = null;
503 this.nextMaplet = null;
504 this.bucketIndex = 0;
505 this.size = 0;
506 this.store = null;
507 } else if ( first < 1 || first > totalMaplets ) {
508 throw new ListIndexOutOfBoundsAlert(
509 "First index in slice must be between 1 and the number of entries in the map"
510 ).culprit(
511 "index",
512 first
513 ).decorate( maplets ).mishap();
514 } else if ( last > totalMaplets ) {
515 throw new ListIndexOutOfBoundsAlert(
516 "Last index in slice must not be greater than the number of entries in the map"
517 ).culprit(
518 "index",
519 last
520 ).decorate( maplets ).mishap();
521 } else {
522 this.currentMaplet = null;
523 this.nextMaplet = fm;
524 this.bucketIndex = fb;
525 this.size = last - first + 1;
526 this.store = maplets;
527 }
528 }
529
530 /**
531 * @see org.millscript.commons.util.iterator.AbstractMapIterator#advance()
532 */
533 @Override
534 protected void advance() {
535
536 super.advance();
537
538 this.currentMaplet = this.nextMaplet;
539 if ( super.position >= this.size ) {
540 this.nextMaplet = null;
541 } else if ( this.nextMaplet != null ) {
542 this.nextMaplet = this.nextMaplet.next;
543 }
544
545 this.checkNext();
546 }
547
548 /**
549 * Checks that the next maplet field is populated with the next maplet
550 * if one is available.
551 */
552 private void checkNext() {
553 if ( this.nextMaplet == null ) {
554
555 if ( ++bucketIndex < this.store.length ) {
556 this.nextMaplet = this.store[ bucketIndex ];
557
558 this.checkNext();
559 }
560 }
561 }
562
563 /**
564 * Returns the appropriate part of the specified maplet for this list.
565 *
566 * @param maplet the maplet to get the appropriate part from
567 * @return the appropriate part of the specified maplet
568 */
569 abstract V getAppropriateMapletPart( Maplet< ?, ? > maplet );
570
571 /**
572 * @see org.millscript.commons.util.iterator.AbstractMapIterator#getValue()
573 */
574 @Override
575 protected V getValue() {
576 return this.getAppropriateMapletPart( currentMaplet );
577 }
578
579 /**
580 * @see org.millscript.commons.util.MapIterator#hasNext()
581 */
582 public boolean hasNext() {
583 return this.nextMaplet != null;
584 }
585
586 /**
587 * @see org.millscript.commons.util.iterator.AbstractMapIterator#outOfBounds()
588 */
589 @Override
590 protected boolean outOfBounds() {
591 return this.currentMaplet == null;
592 }
593
594 }
595
596 /**
597 * The class provides the skeletal implementation of a list backed by an
598 * array of hash map buckets, where the list values are either the maplet
599 * keys or values.
600 */
601 private static abstract class HashMapXList< V > extends AbstractIList< V > {
602
603 /**
604 * The index of the first bucket in the backing store that the first
605 * maplet in the list is held in.
606 */
607 private final int firstBucket;
608
609 /**
610 * The index of the first maplet in the backing store that is returned.
611 */
612 final int firstIndex;
613
614 /**
615 * The first maplet in the list(in the first bucket).
616 */
617 private final HashMaplet< ?, ? > firstHashMaplet;
618
619 /**
620 * The index of the last maplet in the backing store that is returned.
621 */
622 final int lastIndex;
623
624 /**
625 * The backing store for this hash map list is a fixed array of
626 * HashMaplet buckets.
627 */
628 final HashMaplet< ?, ? >[] store;
629
630 /**
631 * Constructs a new hash maplet array list of either the individual
632 * maplet keys or values.
633 *
634 * @param maplets the backing array of maplets
635 * @param first the index(one based, inclusive) of the first name
636 * @param last the index(one based, inclusive) of the last name
637 */
638 private HashMapXList( final HashMaplet< ?, ? >[] maplets, final int first, final int last ) {
639 int fb = 0;
640 HashMaplet< ?, ? > fm = null;
641 int totalMaplets = 0;
642
643 for ( int i = 0; maplets != null && i < maplets.length; i++ ) {
644
645 for ( HashMaplet< ?, ? > hmp = maplets[ i ]; hmp != null; hmp = hmp.next ) {
646
647 if ( ++totalMaplets == first ) {
648
649 fb = i;
650 fm = hmp;
651 }
652 }
653 }
654 if ( first > last ) {
655 this.firstBucket = 0;
656 this.firstHashMaplet = null;
657 this.store = null;
658 } else if ( first < 1 || first > totalMaplets ) {
659 throw new ListIndexOutOfBoundsAlert(
660 "First index in slice must be between 1 and the number of entries in the map"
661 ).culprit(
662 "index",
663 first
664 ).decorate( maplets ).mishap();
665 } else if ( last > totalMaplets ) {
666 throw new ListIndexOutOfBoundsAlert(
667 "Last index in slice must not be greater than the number of entries in the map"
668 ).culprit(
669 "index",
670 last
671 ).decorate( maplets ).mishap();
672 } else {
673 this.firstBucket = fb;
674 this.firstHashMaplet = fm;
675 this.store = maplets;
676 }
677 this.firstIndex = first;
678 this.lastIndex = last;
679 }
680
681 /**
682 * @see org.millscript.commons.util.list.AbstractIList#doGet(int)
683 */
684 @Override
685 protected V doGet( final int pos ) {
686 int i = this.firstBucket;
687 int p = 1;
688 HashMaplet< ?, ? > hmp = this.firstHashMaplet;
689 while ( p <= this.size() && i < this.store.length ) {
690 if ( p == pos ) {
691 return this.getAppropriateMapletPart( hmp );
692 } else {
693
694 hmp = hmp.next;
695 while ( hmp == null && ++i < this.store.length ) {
696 hmp = this.store[ i ];
697 }
698 p++;
699 }
700 }
701 throw new Fault(
702 "Specified position is neither out of bounds or within the list!"
703 ).culprit( "index", pos ).decorate( this ).mishap();
704 }
705
706 /**
707 * @see org.millscript.commons.util.list.AbstractIList#doSlice(int, int, boolean)
708 */
709 @Override
710 @SuppressWarnings( "unchecked" )
711 protected IList< V > doSlice( final int first, final int last, final boolean share ) {
712 if ( share ) {
713 return this.sharedSlice( first, last );
714 } else {
715
716 final V[] objects = (V[]) new Object[ this.size() ];
717 int i = this.firstBucket;
718 int pos = 0;
719 HashMaplet< ?, ? > hmp = this.firstHashMaplet;
720 while ( pos < this.size() && i < this.store.length ) {
721 objects[ pos ] = this.getAppropriateMapletPart( hmp );
722
723 hmp = hmp.next;
724 while ( hmp == null && ++i < this.store.length ) {
725 hmp = this.store[ i ];
726 }
727 pos++;
728 }
729 return new IArrayList< V >( objects, true );
730 }
731 }
732
733 /**
734 * Returns the appropriate part of the specified maplet for this list.
735 *
736 * @param maplet the maplet to get the appropriate part from
737 * @return the appropriate part of the specified maplet
738 */
739 abstract V getAppropriateMapletPart( Maplet< ?, ? > maplet );
740
741 /**
742 * @see org.millscript.commons.util.IList#indexOf(java.lang.Object)
743 */
744 public int indexOf( final V value ) {
745 int i = this.firstBucket;
746 int pos = 1;
747 HashMaplet< ?, ? > hmp = this.firstHashMaplet;
748 if ( value == null ) {
749 while ( pos <= this.size() && i < this.store.length ) {
750 if ( this.getAppropriateMapletPart( hmp ) == null ) {
751 return pos;
752 } else {
753
754 hmp = hmp.next;
755 while ( hmp == null && ++i < this.store.length ) {
756 hmp = this.store[ i ];
757 }
758 pos++;
759 }
760 }
761 } else {
762 while ( pos <= this.size() && i < this.store.length ) {
763 if ( value.equals( this.getAppropriateMapletPart( hmp ) ) ) {
764 return pos;
765 } else {
766
767 hmp = hmp.next;
768 while ( hmp == null && ++i < this.store.length ) {
769 hmp = this.store[ i ];
770 }
771 pos++;
772 }
773 }
774 }
775 return 0;
776 }
777
778 /**
779 * @see org.millscript.commons.util.IMap#iterator(boolean)
780 */
781 @SuppressWarnings( "unchecked" )
782 public ListIterator< V > iterator( final boolean share ) {
783 if ( share ) {
784 return this.sharedIterator();
785 } else {
786
787
788 final V[] objects = (V[]) new Object[ this.size() ];
789 for ( int i = 0, j = 0; i < this.store.length; i++ ) {
790 for ( HashMaplet< ?, ? > maplet = this.store[ i ]; maplet != null; maplet = maplet.next ) {
791 objects[ j++ ] = this.getAppropriateMapletPart( maplet );
792 }
793 }
794 return new ArrayListIterator< V >( objects, true );
795 }
796 }
797
798 /**
799 * Returns a map iterator which shares backing store with this list.
800 *
801 * @return a map iterator which shares this lists backing store
802 */
803 abstract ListIterator< V > sharedIterator();
804
805 /**
806 * Returns a slice of this list which shares backing store with this
807 * list.
808 *
809 * @param first the index(one based) of the first element in the slice
810 * @param last the index(one based) of the last element in the slice
811 * @return a slice of this list which shares this lists backing store
812 */
813 abstract IList< V > sharedSlice( int first, int last );
814
815 /**
816 * @see org.millscript.commons.util.IMap#size()
817 */
818 public int size() {
819 return this.lastIndex <= this.firstIndex ? 0
820 : this.lastIndex - this.firstIndex + 1;
821 }
822
823 }
824
825 /**
826 * The number of mappings in this map.
827 */
828 private final int size;
829
830 /**
831 * The backing store for this hash map is a fixed array of HashMaplet
832 * buckets.
833 */
834 private final HashMaplet< K, V >[] store;
835
836 /**
837 * Constructs a new, emtpy immutable hash map.
838 */
839 public IHashMap() {
840 this.size = 0;
841 this.store = null;
842 }
843
844 /**
845 * Constructs a new immutable hash map which contains all the mappings from
846 * the specified map.
847 *
848 * @param map the <code>Map</code> to copy mappings from
849 */
850 @SuppressWarnings( "unchecked" )
851 public IHashMap( final IMap< K, V > map ) {
852 final MapIterator< K, V > it = map.iterator( true );
853 this.size = map.size();
854 final HashMaplet< K, V >[] maplets = new HashMaplet[ this.size ];
855 this.store = maplets;
856 while ( it.hasNext() ) {
857 final int pos = it.nextKey() == null ? 0 : ( it.currentKey().hashCode() & 0x7FFFFFFF ) % maplets.length;
858 if ( maplets[ pos ] == null ) {
859 maplets[ pos ] = new HashMaplet< K, V >( it.currentKey(), it.currentValue() );
860 } else {
861 for ( HashMaplet< K, V > hmp = maplets[ pos ]; hmp != null; hmp = hmp.next ) {
862 if ( hmp.getKey() == null ? it.currentKey() == null : hmp.getKey().equals( it.currentKey() ) ) {
863 throw new KeyAlreadyExistsAlert(
864 "Specified key is already present in this map"
865 ).culprit(
866 "existing maplet",
867 hmp
868 ).culprit(
869 "duplicate maplet",
870 it.currentMaplet()
871 ).mishap();
872 } else if ( hmp.next == null ) {
873 hmp.next = new HashMaplet< K, V >( it.currentKey(), it.currentValue() );
874 break;
875 }
876 }
877 }
878 }
879 }
880
881 /**
882 * @see java.lang.Object#clone()
883 */
884 @Override
885 public Object clone() throws CloneNotSupportedException {
886
887 return super.clone();
888 }
889
890 /**
891 * @see org.millscript.commons.util.IMap#contains(java.lang.Object, java.lang.Object)
892 */
893 public boolean contains( final K key, final V value ) {
894 if ( this.store != null ) {
895 final int pos = key == null ? 0 : ( key.hashCode() & 0x7FFFFFFF ) % this.store.length;
896 for ( HashMaplet< K, V > hmp = this.store[ pos ]; hmp != null; hmp = hmp.next ) {
897 if ( key == null ? hmp.getKey() == null : key.equals( hmp.getKey() ) ) {
898
899
900 return value == null ? hmp.getValue() == null
901 : value.equals( hmp.getValue() );
902 }
903 }
904 }
905 return false;
906 }
907
908 /**
909 * @see org.millscript.commons.util.IMap#containsKey(java.lang.Object)
910 */
911 public boolean containsKey( final K key ) {
912 if ( this.store != null ) {
913 final int pos = key == null ? 0 : ( key.hashCode() & 0x7FFFFFFF ) % this.store.length;
914 for ( HashMaplet< K, V > hmp = this.store[ pos ]; hmp != null; hmp = hmp.next ) {
915 if ( key == null ? hmp.getKey() == null : key.equals( hmp.getKey() ) ) {
916 return true;
917 }
918 }
919 }
920 return false;
921 }
922
923 /**
924 * @see org.millscript.commons.util.IMap#containsValue(java.lang.Object)
925 */
926 public boolean containsValue( final V value ) {
927 if ( this.store != null ) {
928
929 for ( int i = 0; i < this.store.length; i++ ) {
930 for ( HashMaplet< K, V > hmp = this.store[ i ]; hmp != null; hmp = hmp.next ) {
931 if ( value == null ? hmp.getValue() == null : value.equals( hmp.getValue() ) ) {
932 return true;
933 }
934 }
935 }
936 }
937 return false;
938 }
939
940 /**
941 * @see org.millscript.commons.util.IMap#get(java.lang.Object)
942 */
943 public V get( final K key ) {
944 if ( this.store != null ) {
945 final int pos = key == null ? 0 : ( key.hashCode() & 0x7FFFFFFF ) % this.store.length;
946 for ( HashMaplet< K, V > hmp = this.store[ pos ]; hmp != null; hmp = hmp.next ) {
947 if ( hmp.getKey() == null ? key == null : hmp.getKey().equals( key ) ) {
948 return hmp.getValue();
949 }
950 }
951 }
952 return this.getDefault().get( this, key );
953 }
954
955 /**
956 * @see org.millscript.commons.util.IMap#isEmtpy()
957 */
958 @Override
959 public boolean isEmtpy() {
960 if ( this.store != null && this.store.length != 0 ) {
961 for ( int i = 0; i < this.store.length; i++ ) {
962
963 if ( this.store[ i ] != null ) {
964 return false;
965 }
966 }
967 }
968 return true;
969 }
970
971 /**
972 * @see org.millscript.commons.util.IMap#iterator(boolean)
973 */
974 @SuppressWarnings( "unchecked" )
975 public MapIterator< K, V > iterator( final boolean share ) {
976 if ( share ) {
977 return new HashMapIterator< K, V >( this.store, share );
978 } else {
979
980
981
982 final Maplet< K, V >[] maplets = new Maplet[ this.size() ];
983 for ( int i = 0, j = 0; i < this.store.length; i++ ) {
984 for ( HashMaplet< K, V > maplet = this.store[ i ]; maplet != null; maplet = maplet.next ) {
985 maplets[ j++ ] = new IMaplet< K, V >( maplet );
986 }
987 }
988 return new IMapletArrayMap.MapletArrayMapIterator< K, V >( maplets, true );
989 }
990 }
991
992 /**
993 * @see org.millscript.commons.util.map.AbstractIMap#sharedKeyList()
994 */
995 @Override
996 protected IList< K > sharedKeyList() {
997 return new HashMapKeysList< K >( this.store, 1, this.size() );
998 }
999
1000 /**
1001 * @see org.millscript.commons.util.map.AbstractIMap#sharedMapletList()
1002 */
1003 @Override
1004 protected IList< Maplet< K, V > > sharedMapletList() {
1005 return new HashMapMapletList< K, V >( this.store, 1, this.size() );
1006 }
1007
1008 /**
1009 * @see org.millscript.commons.util.map.AbstractIMap#sharedValueList()
1010 */
1011 @Override
1012 protected IList< V > sharedValueList() {
1013 return new HashMapValuesList< V >( this.store, 1, this.size() );
1014 }
1015
1016 /**
1017 * @see org.millscript.commons.util.IMap#size()
1018 */
1019 public int size() {
1020 return this.size;
1021 }
1022
1023 }