?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
today
[ephemerata.git] / KezvhLib / src-lib / net / kezvh / collections / Map2 / HashMap2.java
blob4a41b7d89d91e317c6abe6a2ffac59b7fd37dec0
1 /**
2 *
3 */
4 package net.kezvh.collections.Map2;
5
6 import java.io.IOException;
7 import java.lang.reflect.Array;
8 import java.util.AbstractCollection;
9 import java.util.AbstractMap;
10 import java.util.AbstractSet;
11 import java.util.ArrayList;
12 import java.util.Collection;
13 import java.util.ConcurrentModificationException;
14 import java.util.HashMap;
15 import java.util.Iterator;
16 import java.util.Map;
17 import java.util.NoSuchElementException;
18 import java.util.Set;
19
20 import net.kezvh.collections.AbstractIterator;
21 import net.kezvh.collections.MapEntryImpl;
22 import net.kezvh.collections.Pair;
23 import net.kezvh.collections.views.SetView;
24 import net.kezvh.functional.lambda.L1;
25
26 /**
27 * Sometimes you want a map with 2 keys. While one could just use java's maps but with
28 * something like Couple<K1, K2> as the key, there's an additional opperation I often
29 * want to do that you just can't do with something like that. In particular, this
30 * operation is incredibly useful if you use this collection to map the edges of a graph,
31 * and you want to iterate through all the edges into or out of a particular node.
32 *
33 * That operation is to slice the map by 1 key or the other.
34 *
35 * This class grepped a lot of its guts out of java's hashmap implementation (is that
36 * an ip issue?). However, each entry in the table also maintains connections to
37 * other entries which share it's first or second key. This way, you've got a linked
38 * list of entries for each key along each dimension.
39 *
40 * Time complexity:
41 * get(k1, k2)
42 * this is operationally identical to getting on a hashmap, so O(1)
43 * put(k1, k2, v)
44 * hashtable put + 2 linked list head inserts, so also O(1) amortized
45 * remove(k1, k2)
46 * hashtable remove + 2 doubly linked list remove, so O(1)
47 * get(k1) || get(k2)
48 * returns a list of elements backed by the map in O(1) time
49 * remove(k1) || remove(k2)
50 * O(n), where n is the number of elements in get(k1) or get(k2) respectively.
51 *
52 * @author afflux
53 * @param <K1> COMMENT
54 * @param <K2> COMMENT
55 * @param <V> COMMENT
56 */
57 public class HashMap2<K1, K2, V> implements Map2<K1, K2, V> {
58 /**
59 * The default initial capacity - MUST be a power of two.
60 */
61 static final int DEFAULT_INITIAL_CAPACITY = 16;
62
63 /**
64 * The maximum capacity, used if a higher value is implicitly specified by
65 * either of the constructors with arguments. MUST be a power of two <=
66 * 1<<30.
67 */
68 static final int MAXIMUM_CAPACITY = 1 << 30;
69
70 /**
71 * The load factor used when none specified in constructor.
72 **/
73 static final float DEFAULT_LOAD_FACTOR = 0.75f;
74
75 private static final <K1, K2, V> Entry<K1, K2, V>[] createEntries(final Entry<K1, K2, V>[] other, final int capacity) {
76 return HashMap2.createEntries(other.getClass().getComponentType(), capacity);
77 }
78
79 @SuppressWarnings("unchecked")
80 private static final <K1, K2, V> Entry<K1, K2, V>[] createEntries(final Class<?> clazz, final int capacity) {
81 return (Entry<K1, K2, V>[]) Array.newInstance(clazz, capacity);
82 }
83
84 private static final <K1, K2> int hash(final K1 k1, final K2 k2) {
85 int h;
86
87 if (k1 == null)
88 if (k2 == null)
89 h = 0;
90 else
91 h = k2.hashCode();
92 else if (k2 == null || k1.equals(k2))
93 h = k1.hashCode();
94 else
95 h = k1.hashCode() ^ k2.hashCode();
96
97 h ^= (h >>> 20) ^ (h >>> 12);
98 return h ^ (h >>> 7) ^ (h >>> 4);
99 }
100
101 private static final <K1, K2> int hash(final Pair<K1, K2> entry) {
102 return HashMap2.hash(entry.get1(), entry.get2());
103 }
104
105 private static final int indexFor(final int hash, final int length) {
106 return hash & (length - 1);
107 }
108
109 /**
110 * TODO make this a libary method
111 *
112 * @param <T> COMMENT
113 * @param a COMMENT
114 * @param b COMMENT
115 * @return COMMENT
116 */
117 private static final <T> boolean objectsEqual(final T a, final T b) {
118 if (a == null)
119 return b == null;
120 return a.equals(b);
121 }
122
123 /**
124 * so the complicated thing is this resides in 3 lists: 1 is the list of
125 * collisions 1 is the list of all entries matching key 1 1 is the list of
126 * all entries matching key 2
127 *
128 * @author afflux
129 * @param <K1>
130 * @param <K2>
131 * @param <V>
132 */
133 private static final class Entry<K1, K2, V> implements Map2.Entry<K1, K2, V>, Pair<K1, K2> {
134 private final K1 k1;
135 private final K2 k2;
136 private V value;
137 private final int hash;
138 private Entry<K1, K2, V> nextCollision;
139 private Entry<K1, K2, V> next1; // next in loop w/ fixed k1
140 private Entry<K1, K2, V> next2; // next in loop w/ fixed k2
141 private Entry<K1, K2, V> prev1; // prev in loop w/ fixed k1
142 private Entry<K1, K2, V> prev2; // prev in loop w/ fixed k2
143
144 public Entry(final int hash, final K1 k1, final K2 k2, final V v, final Entry<K1, K2, V> nextCollision) {
145 this.k1 = k1;
146 this.k2 = k2;
147 this.value = v;
148 this.nextCollision = nextCollision;
149 this.hash = hash;
150 }
151
152 /**
153 * i kind of love this function
154 *
155 * @param bimap COMMENT
156 */
157 public void removeSelf(final HashMap2<K1, K2, V> bimap) {
158 if (this.next1 != null)
159 this.next1.setPrev1(this.prev1);
160 if (this.next2 != null)
161 this.next2.setPrev2(this.prev2);
162 if (this.prev1 != null)
163 this.prev1.setNext1(this.next1);
164 if (this.prev2 != null)
165 this.prev2.setNext2(this.next2);
166 bimap.k1Heads.get(this.k1).removing(this);
167 if (bimap.k1Heads.get(this.k1).isEmpty())
168 bimap.k1Heads.remove(this.k1);
169 bimap.k2Heads.get(this.k2).removing(this);
170 if (bimap.k2Heads.get(this.k2).isEmpty())
171 bimap.k2Heads.remove(this.k2);
172 }
173
174 /**
175 * @return the next1
176 */
177 public Entry<K1, K2, V> getNext1() {
178 return this.next1;
179 }
180
181 /**
182 * @param next1 the next1 to set
183 * @return COMMENT
184 */
185 public Entry<K1, K2, V> setNext1(final Entry<K1, K2, V> next1) {
186 try {
187 return this.next1;
188 } finally {
189 this.next1 = next1;
190 }
191 }
192
193 /**
194 * @return the next2
195 */
196 public Entry<K1, K2, V> getNext2() {
197 return this.next2;
198 }
199
200 /**
201 * @param next2 the next2 to set
202 * @return COMMENT
203 */
204 public Entry<K1, K2, V> setNext2(final Entry<K1, K2, V> next2) {
205 try {
206 return this.next2;
207 } finally {
208 this.next2 = next2;
209 }
210 }
211
212 /**
213 * @return the prev1
214 */
215 public Entry<K1, K2, V> getPrev1() {
216 return this.prev1;
217 }
218
219 /**
220 * @param prev1 the prev1 to set
221 * @return COMMENT
222 */
223 public Entry<K1, K2, V> setPrev1(final Entry<K1, K2, V> prev1) {
224 try {
225 return this.prev1;
226 } finally {
227 this.prev1 = prev1;
228 }
229 }
230
231 /**
232 * @return the prev2
233 */
234 public Entry<K1, K2, V> getPrev2() {
235 return this.prev2;
236 }
237
238 /**
239 * @param prev2 the prev2 to set
240 * @return COMMENT
241 */
242 public Entry<K1, K2, V> setPrev2(final Entry<K1, K2, V> prev2) {
243 try {
244 return this.prev2;
245 } finally {
246 this.prev2 = prev2;
247 }
248 }
249
250 public boolean matchesKeys(final K1 key1, final K2 key2) {
251 return HashMap2.objectsEqual(this.k1, key1) && HashMap2.objectsEqual(this.k2, key2);
252 }
253
254 /**
255 * @return the nextCollision
256 */
257 public Entry<K1, K2, V> getNextCollision() {
258 return this.nextCollision;
259 }
260
261 /**
262 * @param nextCollision the nextCollision to set
263 */
264 public void setNextCollision(final Entry<K1, K2, V> nextCollision) {
265 this.nextCollision = nextCollision;
266 }
267
268 /**
269 * @see java.lang.Object#hashCode()
270 * @return COMMENT
271 */
272 @Override
273 public int hashCode() {
274 return this.hash;
275 }
276
277 /**
278 * @see java.lang.Object#equals(java.lang.Object)
279 * @param obj COMMENT
280 * @return COMMENT
281 */
282 @Override
283 public boolean equals(final Object obj) {
284 if (this == obj)
285 return true;
286 if (obj == null)
287 return false;
288 if (this.getClass() != obj.getClass())
289 return false;
290 final Entry<?, ?, ?> other = (Entry<?, ?, ?>) obj;
291 if (this.k1 == null) {
292 if (other.k1 != null)
293 return false;
294 } else if (!this.k1.equals(other.k1))
295 return false;
296 if (this.k2 == null) {
297 if (other.k2 != null)
298 return false;
299 } else if (!this.k2.equals(other.k2))
300 return false;
301 return true;
302 }
303
304 /**
305 * @see net.kezvh.collections.Map2.Map2.Entry#getKey1()
306 * @return COMMENT
307 */
308 @Override
309 public K1 getKey1() {
310 return this.k1;
311 }
312
313 /**
314 * @see net.kezvh.collections.Map2.Map2.Entry#getKey2()
315 * @return COMMENT
316 */
317 @Override
318 public K2 getKey2() {
319 return this.k2;
320 }
321
322 /**
323 * @see net.kezvh.collections.Map2.Map2.Entry#getValue()
324 * @return COMMENT
325 */
326 @Override
327 public V getValue() {
328 return this.value;
329 }
330
331 /**
332 * @see net.kezvh.collections.Map2.Map2.Entry#setValue(java.lang.Object)
333 * @param value COMMENT
334 * @return COMMENT
335 */
336 @Override
337 public V setValue(final V value) {
338 try {
339 return this.value;
340 } finally {
341 this.value = value;
342 }
343 }
344
345 /**
346 * @see java.util.Map.Entry#getKey()
347 * @return COMMENT
348 */
349 @Override
350 public Pair<K1, K2> getKey() {
351 return this;
352 }
353
354 /**
355 * @see net.kezvh.collections.Pair#get1()
356 * @return COMMENT
357 */
358 @Override
359 public K1 get1() {
360 return this.k1;
361 }
362
363 /**
364 * @see net.kezvh.collections.Pair#get2()
365 * @return COMMENT
366 */
367 @Override
368 public K2 get2() {
369 return this.k2;
370 }
371 }
372
373 private abstract class HeadSet extends AbstractSet<Entry<K1, K2, V>> {
374 private int headsetSize;
375
376 private Entry<K1, K2, V> head;
377
378 private final class HeadSetIterator extends AbstractIterator<Entry<K1, K2, V>> {
379 private Entry<K1, K2, V> current = HeadSet.this.head;
380
381 /**
382 * @see net.kezvh.collections.AbstractIterator#findNext()
383 * @return COMMENT
384 * @throws NoSuchElementException COMMENT
385 */
386 @Override
387 protected Entry<K1, K2, V> findNext() throws NoSuchElementException {
388 if (this.current == null)
389 throw new NoSuchElementException();
390 try {
391 return this.current;
392 } finally {
393 this.current = HeadSet.this.getNext(this.current);
394 }
395 }
396
397 /**
398 * @see net.kezvh.collections.AbstractIterator#remove()
399 */
400 @Override
401 public void remove() {
402 HashMap2.this.remove(HeadSet.this.getPrev(this.current));
403 }
404 }
405
406 public final void insertNewHead(final Entry<K1, K2, V> newHead) {
407 this.setNext(newHead, this.head);
408 if (this.head != null)
409 this.setPrev(this.head, newHead);
410 this.head = newHead;
411 this.headsetSize++;
412 }
413
414 public final void removing(final Entry<K1, K2, V> removedEntry) {
415 if (this.head == removedEntry)
416 this.head = this.getNext(removedEntry);
417 this.headsetSize--;
418 }
419
420 protected abstract Entry<K1, K2, V> getNext(Entry<K1, K2, V> entry);
421
422 protected abstract Entry<K1, K2, V> getPrev(Entry<K1, K2, V> entry);
423
424 protected abstract Entry<K1, K2, V> setNext(Entry<K1, K2, V> entry, Entry<K1, K2, V> next);
425
426 protected abstract Entry<K1, K2, V> setPrev(Entry<K1, K2, V> entry, Entry<K1, K2, V> prev);
427
428 /**
429 * @see java.util.AbstractCollection#iterator()
430 * @return COMMENT
431 */
432 @Override
433 public Iterator<Entry<K1, K2, V>> iterator() {
434 return new HeadSetIterator();
435 }
436
437 /**
438 * @see java.util.AbstractCollection#size()
439 * @return COMMENT
440 */
441 @Override
442 public int size() {
443 return this.headsetSize;
444 }
445
446 /**
447 * @see java.util.AbstractCollection#add(java.lang.Object)
448 * @param o COMMENT
449 * @return COMMENT
450 */
451 @Override
452 public boolean add(final Entry<K1, K2, V> o) {
453 return HashMap2.this.put(o) != null;
454 }
455
456 /**
457 * @see java.util.AbstractCollection#addAll(java.util.Collection)
458 * @param c COMMENT
459 * @return COMMENT
460 */
461 @Override
462 public boolean addAll(final Collection<? extends Entry<K1, K2, V>> c) {
463 return HashMap2.this.putAll(c);
464 }
465
466 /**
467 * @see java.util.AbstractCollection#clear()
468 */
469 @Override
470 public void clear() {
471 for (final Entry<K1, K2, V> entry : this)
472 HashMap2.this.remove(entry);
473 }
474
475 /**
476 * @see java.util.AbstractCollection#contains(java.lang.Object)
477 * @param o COMMENT
478 * @return COMMENT
479 */
480 @SuppressWarnings("unchecked")
481 @Override
482 public boolean contains(final Object o) {
483 if (!(o instanceof Map2.Entry))
484 return false;
485
486 final Map2.Entry<K1, K2, V> other = (Map2.Entry<K1, K2, V>) o;
487 return HashMap2.this.containsKey(other.getKey1(), other.getKey2());
488 }
489
490 /**
491 * @see java.util.AbstractCollection#containsAll(java.util.Collection)
492 * @param c COMMENT
493 * @return COMMENT
494 */
495 @Override
496 public boolean containsAll(final Collection<?> c) {
497 for (final Object entry : c)
498 if (!this.contains(entry))
499 return false;
500 return true;
501 }
502
503 /**
504 * @see java.util.AbstractCollection#isEmpty()
505 * @return COMMENT
506 */
507 @Override
508 public boolean isEmpty() {
509 return this.head == null;
510 }
511
512 /**
513 * @see java.util.AbstractCollection#remove(java.lang.Object)
514 * @param o COMMENT
515 * @return COMMENT
516 */
517 @Override
518 public boolean remove(final Object o) {
519 return HashMap2.this.remove(o) != null;
520 }
521
522 /**
523 * @see java.util.AbstractCollection#retainAll(java.util.Collection)
524 * @param c COMMENT
525 * @return COMMENT
526 */
527 @Override
528 public boolean retainAll(final Collection<?> c) {
529 boolean modified = false;
530 for (final Entry<K1, K2, V> entry : this)
531 if (!c.contains(entry))
532 modified |= HashMap2.this.remove(entry) != null;
533
534 return modified;
535 }
536
537 /**
538 * @see java.util.AbstractCollection#toArray()
539 * @return TOOD COMMENT
540 */
541 @Override
542 public Object[] toArray() {
543 final Entry<K1, K2, V>[] array = HashMap2.createEntries(this.head.getClass(), HashMap2.this.size);
544 return this.toArray(array);
545 }
546
547 @SuppressWarnings("unchecked")
548 @Override
549 public <T extends Object> T[] toArray(final T[] a) {
550 final T[] b = a.length >= HashMap2.this.size ? a : (T[]) HashMap2.createEntries(a.getClass().getComponentType(), HashMap2.this.size);
551 int i = 0;
552 for (final Entry<K1, K2, V> entry : this)
553 a[i++] = (T) entry;
554 return b;
555 }
556 }
557
558 private final class HeadSet1 extends HeadSet {
559 @Override
560 protected Entry<K1, K2, V> getPrev(final Entry<K1, K2, V> arg0) {
561 return arg0.getNext1();
562 }
563
564 @Override
565 protected Entry<K1, K2, V> getNext(final Entry<K1, K2, V> arg0) {
566 return arg0.getPrev1();
567 }
568
569 @Override
570 protected Entry<K1, K2, V> setNext(final Entry<K1, K2, V> entry, final Entry<K1, K2, V> next) {
571 return entry.setNext1(next);
572 }
573
574 @Override
575 protected Entry<K1, K2, V> setPrev(final Entry<K1, K2, V> entry, final Entry<K1, K2, V> prev) {
576 return entry.setPrev1(prev);
577 }
578 }
579
580 private final class HeadSet2 extends HeadSet {
581 @Override
582 protected Entry<K1, K2, V> getPrev(final Entry<K1, K2, V> arg0) {
583 return arg0.getNext2();
584 }
585
586 @Override
587 protected Entry<K1, K2, V> getNext(final Entry<K1, K2, V> arg0) {
588 return arg0.getPrev2();
589 }
590
591 @Override
592 protected Entry<K1, K2, V> setNext(final Entry<K1, K2, V> entry, final Entry<K1, K2, V> next) {
593 return entry.setNext2(next);
594 }
595
596 @Override
597 protected Entry<K1, K2, V> setPrev(final Entry<K1, K2, V> entry, final Entry<K1, K2, V> prev) {
598 return entry.setPrev2(prev);
599 }
600 }
601
602 private final Map<K1, HeadSet1> k1Heads = new HashMap<K1, HeadSet1>();
603 private final Map<K2, HeadSet2> k2Heads = new HashMap<K2, HeadSet2>();
604 private Entry<K1, K2, V>[] entries;
605 /**
606 * The number of key-value mappings contained in this identity hash map.
607 */
608 private transient int size;
609
610 /**
611 * The next size value at which to resize (capacity * load factor).
612 *
613 * @serial
614 */
615 private int threshold;
616
617 /**
618 * The load factor for the hash table.
619 *
620 * @serial
621 */
622 private final float loadFactor;
623
624 /**
625 * The number of times this HashMap has been structurally modified
626 * Structural modifications are those that change the number of mappings in
627 * the HashMap or otherwise modify its internal structure (e.g., rehash).
628 * This field is used to make iterators on Collection-views of the HashMap
629 * fail-fast. (See ConcurrentModificationException).
630 */
631 private transient volatile int modCount;
632
633 /**
634 * TODO refactor this so it uses AbstractIterator
635 *
636 * @author afflux
637 * @param <E>
638 */
639 private abstract class HashIterator<E> implements Iterator<E> {
640 Entry<K1, K2, V> next; // next entry to return
641 int expectedModCount; // For fast-fail
642 int index; // current slot
643 Entry<K1, K2, V> current; // current entry
644
645 public HashIterator() {
646 this.expectedModCount = HashMap2.this.modCount;
647 final Entry<K1, K2, V>[] t = HashMap2.this.entries;
648 int i = t.length;
649 Entry<K1, K2, V> n = null;
650 if (HashMap2.this.size != 0)
651 while (i > 0 && (n = t[--i]) == null) {
652 // nothing TODO maybe refactor this so it's.. not so ugly
653 }
654 this.next = n;
655 this.index = i;
656 }
657
658 public boolean hasNext() {
659 return this.next != null;
660 }
661
662 protected Entry<K1, K2, V> nextEntry() {
663 if (HashMap2.this.modCount != this.expectedModCount)
664 throw new ConcurrentModificationException();
665 final Entry<K1, K2, V> e = this.next;
666 if (e == null)
667 throw new NoSuchElementException();
668
669 Entry<K1, K2, V> n = e.getNextCollision();
670 final Entry<K1, K2, V>[] t = HashMap2.this.entries;
671 int i = this.index;
672 while (n == null && i > 0)
673 n = t[--i];
674 this.index = i;
675 this.next = n;
676 return this.current = e;
677 }
678
679 public void remove() {
680 if (this.current == null)
681 throw new IllegalStateException();
682 if (HashMap2.this.modCount != this.expectedModCount)
683 throw new ConcurrentModificationException();
684 final Pair<K1, K2> k = this.current.getKey();
685 this.current = null;
686 HashMap2.this.removeEntryForKey(k.get1(), k.get2());
687 this.expectedModCount = HashMap2.this.modCount;
688 }
689
690 }
691
692 private class ValueIterator extends HashIterator<V> {
693 public V next() {
694 return this.nextEntry().getValue();
695 }
696 }
697
698 private class KeyIterator extends HashIterator<Pair<K1, K2>> {
699 public Pair<K1, K2> next() {
700 return this.nextEntry().getKey();
701 }
702 }
703
704 private class EntryIterator extends HashIterator<Map.Entry<Pair<K1, K2>, V>> {
705 public Map.Entry<Pair<K1, K2>, V> next() {
706 return this.nextEntry();
707 }
708 }
709
710 // Subclass overrides these to alter behavior of views' iterator() method
711 Iterator<Pair<K1, K2>> newKeyIterator() {
712 return new KeyIterator();
713 }
714
715 Iterator<V> newValueIterator() {
716 return new ValueIterator();
717 }
718
719 Iterator<Map.Entry<Pair<K1, K2>, V>> newEntryIterator() {
720 return new EntryIterator();
721 }
722
723 // Views
724 /**
725 * Each of these fields are initialized to contain an instance of the
726 * appropriate view the first time this view is requested. The views are
727 * stateless, so there's no reason to create more than one of each.
728 */
729 private transient volatile Set<Pair<K1, K2>> keySet = null;
730 private transient volatile Collection<V> values = null;
731 private transient volatile Set<Map.Entry<Pair<K1, K2>, V>> entrySet = null;
732
733 /**
734 * Returns a set view of the keys contained in this map. The set is backed
735 * by the map, so changes to the map are reflected in the set, and
736 * vice-versa. The set supports element removal, which removes the
737 * corresponding mapping from this map, via the <tt>Iterator.remove</tt>,
738 * <tt>Set.remove</tt>, <tt>removeAll</tt>, <tt>retainAll</tt>, and
739 * <tt>clear</tt> operations. It does not support the <tt>add</tt> or
740 * <tt>addAll</tt> operations.
741 *
742 * @return a set view of the keys contained in this map.
743 */
744 public Set<Pair<K1, K2>> keySet() {
745 final Set<Pair<K1, K2>> ks = this.keySet;
746 return (ks != null ? ks : (this.keySet = new KeySet()));
747 }
748
749 private class KeySet extends AbstractSet<Pair<K1, K2>> {
750 @Override
751 public Iterator<Pair<K1, K2>> iterator() {
752 return HashMap2.this.newKeyIterator();
753 }
754
755 @Override
756 public int size() {
757 return HashMap2.this.size;
758 }
759
760 @Override
761 public boolean contains(final Object o) {
762 return HashMap2.this.containsKey(o);
763 }
764
765 @SuppressWarnings("unchecked")
766 @Override
767 public boolean remove(final Object o) {
768 final Pair<K1, K2> other = (Pair<K1, K2>) o;
769 return HashMap2.this.removeEntryForKey(other.get1(), other.get2()) != null;
770 }
771
772 @Override
773 public void clear() {
774 HashMap2.this.clear();
775 }
776 }
777
778 /**
779 * Returns a collection view of the values contained in this map. The
780 * collection is backed by the map, so changes to the map are reflected in
781 * the collection, and vice-versa. The collection supports element removal,
782 * which removes the corresponding mapping from this map, via the
783 * <tt>Iterator.remove</tt>, <tt>Collection.remove</tt>, <tt>removeAll</tt>,
784 * <tt>retainAll</tt>, and <tt>clear</tt> operations. It does not support
785 * the <tt>add</tt> or <tt>addAll</tt> operations.
786 *
787 * @return a collection view of the values contained in this map.
788 */
789 public Collection<V> values() {
790 final Collection<V> vs = this.values;
791 return (vs != null ? vs : (this.values = new Values()));
792 }
793
794 private class Values extends AbstractCollection<V> {
795 @Override
796 public Iterator<V> iterator() {
797 return HashMap2.this.newValueIterator();
798 }
799
800 @Override
801 public int size() {
802 return HashMap2.this.size;
803 }
804
805 @Override
806 public boolean contains(final Object o) {
807 return HashMap2.this.containsValue(o);
808 }
809
810 @Override
811 public void clear() {
812 HashMap2.this.clear();
813 }
814 }
815
816 /**
817 * Returns a collection view of the mappings contained in this map. Each
818 * element in the returned collection is a <tt>Map.Entry</tt>. The
819 * collection is backed by the map, so changes to the map are reflected in
820 * the collection, and vice-versa. The collection supports element removal,
821 * which removes the corresponding mapping from the map, via the
822 * <tt>Iterator.remove</tt>, <tt>Collection.remove</tt>, <tt>removeAll</tt>,
823 * <tt>retainAll</tt>, and <tt>clear</tt> operations. It does not support
824 * the <tt>add</tt> or <tt>addAll</tt> operations.
825 *
826 * @return a collection view of the mappings contained in this map.
827 * @see Map.Entry
828 */
829 public Set<Map.Entry<Pair<K1, K2>, V>> entrySet() {
830 final Set<Map.Entry<Pair<K1, K2>, V>> es = this.entrySet;
831 return (es != null ? es : (this.entrySet = new EntrySet()));
832 }
833
834 private Entry<K1, K2, V> getEntry(final K1 key1, final K2 key2) {
835 for (Entry<K1, K2, V> entry = this.entries[HashMap2.indexFor(HashMap2.hash(key1, key2), this.entries.length)]; entry != null; entry = entry.getNextCollision())
836 if (entry.matchesKeys(key1, key2))
837 return entry;
838 return null;
839 }
840
841 private class EntrySet extends AbstractSet<Map.Entry<Pair<K1, K2>, V>> {
842 @Override
843 public Iterator<Map.Entry<Pair<K1, K2>, V>> iterator() {
844 return HashMap2.this.newEntryIterator();
845 }
846
847 @SuppressWarnings("unchecked")
848 @Override
849 public boolean contains(final Object o) {
850 if (!(o instanceof Map2.Entry))
851 return false;
852 final Map2.Entry<K1, K2, V> e = (Map2.Entry<K1, K2, V>) o;
853 final Entry<K1, K2, V> candidate = HashMap2.this.getEntry(e.getKey1(), e.getKey2());
854 return candidate != null && candidate.equals(e);
855 }
856
857 @SuppressWarnings("unchecked")
858 @Override
859 public boolean remove(final Object o) {
860 return HashMap2.this.removeMapping((Map.Entry<Pair<K1, K2>, V>) o) != null;
861 }
862
863 @Override
864 public int size() {
865 return HashMap2.this.size;
866 }
867
868 @Override
869 public void clear() {
870 HashMap2.this.clear();
871 }
872 }
873
874 /**
875 * Save the state of the <tt>HashMap</tt> instance to a stream (i.e.,
876 * serialize it).
877 *
878 * @serialData The <i>capacity</i> of the HashMap (the length of the bucket
879 * array) is emitted (int), followed by the <i>size</i> of the
880 * HashMap (the number of key-value mappings), followed by the
881 * key (Object) and value (Object) for each key-value mapping
882 * represented by the HashMap The key-value mappings are emitted
883 * in the order that they are returned by
884 * <tt>entrySet().iterator()</tt>.
885 */
886 private void writeObject(final java.io.ObjectOutputStream s) throws IOException {
887 final Iterator<Map.Entry<Pair<K1, K2>, V>> i = this.entrySet().iterator();
888
889 // Write out the threshold, loadfactor, and any hidden stuff
890 s.defaultWriteObject();
891
892 // Write out number of buckets
893 s.writeInt(this.entries.length);
894
895 // Write out size (number of Mappings)
896 s.writeInt(this.size);
897
898 // Write out keys and values (alternating)
899 while (i.hasNext()) {
900 final Map.Entry<Pair<K1, K2>, V> e = i.next();
901 s.writeObject(e.getKey());
902 s.writeObject(e.getValue());
903 }
904 }
905
906 /**
907 * allow subclasses to do initialization after deserialization
908 */
909 protected void init() {
910 // do nothing;
911 }
912
913 private static final long serialVersionUID = 362498820763181265L;
914
915 /**
916 * Reconstitute the <tt>HashMap</tt> instance from a stream (i.e.,
917 * deserialize it).
918 */
919 @SuppressWarnings("unchecked")
920 private void readObject(final java.io.ObjectInputStream s) throws IOException, ClassNotFoundException {
921 // Read in the threshold, loadfactor, and any hidden stuff
922 s.defaultReadObject();
923
924 // Read in number of buckets and allocate the bucket array;
925 final int numBuckets = s.readInt();
926 this.entries = HashMap2.createEntries(new Entry<K1, K2, V>(0, null, null, null, null).getClass(), numBuckets);
927
928 this.init(); // Give subclass a chance to do its thing.
929
930 // Read in size (number of Mappings)
931 final int readSize = s.readInt();
932
933 // Read the keys and values, and put the mappings in the HashMap
934 for (int i = 0; i < readSize; i++) {
935 final K1 key1 = (K1) s.readObject();
936 final K2 key2 = (K2) s.readObject();
937 final V value = (V) s.readObject();
938 this.putForCreate(key1, key2, value);
939 }
940 }
941
942 // These methods are used when serializing HashSets
943 int capacity() {
944 return this.entries.length;
945 }
946
947 float loadFactor() {
948 return this.loadFactor;
949 }
950
951 /**
952 *
953 */
954 public HashMap2() {
955 this.entries = HashMap2.createEntries(new Entry<K1, K2, V>(0, null, null, null, null).getClass(), HashMap2.DEFAULT_INITIAL_CAPACITY);
956 this.loadFactor = HashMap2.DEFAULT_LOAD_FACTOR;
957 }
958
959 /**
960 * @see net.kezvh.collections.Map2.Map2#clear()
961 */
962 @Override
963 public void clear() {
964 this.entries = HashMap2.createEntries(this.entries, HashMap2.DEFAULT_INITIAL_CAPACITY);
965 this.k1Heads.clear();
966 this.k2Heads.clear();
967 }
968
969 /**
970 * Special version of remove for EntrySet.
971 */
972 private Entry<K1, K2, V> removeMapping(final Map.Entry<Pair<K1, K2>, V> o) {
973 if (!(o instanceof Map2.Entry))
974 return null;
975
976 final Map.Entry<Pair<K1, K2>, V> entry = o;
977 final Pair<K1, K2> k = entry.getKey();
978 final int hash = k.hashCode();
979 final int i = HashMap2.indexFor(hash, this.entries.length);
980 Entry<K1, K2, V> prev = this.entries[i];
981 Entry<K1, K2, V> e = prev;
982
983 while (e != null) {
984 final Entry<K1, K2, V> next = e.getNextCollision();
985 if (e.hash == hash && e.equals(entry)) {
986 this.modCount++;
987 this.size--;
988 if (prev == e)
989 this.entries[i] = next;
990 else
991 prev.setNextCollision(next);
992 e.removeSelf(this);
993 return e;
994 }
995 prev = e;
996 e = next;
997 }
998
999 return e;
1000 }
1001
1002 /**
1003 * @see net.kezvh.collections.Map2.Map2#containsKey(java.lang.Object,
1004 * java.lang.Object)
1005 * @param key1 COMMENT
1006 * @param key2 COMMENT
1007 * @return COMMENT
1008 */
1009 @Override
1010 public boolean containsKey(final K1 key1, final K2 key2) {
1011 return this.getEntry(key1, key2) != null;
1012 }
1013
1014 /**
1015 * This method is used instead of put by constructors and pseudoconstructors
1016 * (clone, readObject). It does not resize the table, check for
1017 * comodification, etc. It calls createEntry rather than addEntry.
1018 */
1019 private void putForCreate(final K1 key1, final K2 key2, final V value) {
1020 final int hash = HashMap2.hash(key1, key2);
1021 final int i = HashMap2.indexFor(hash, this.entries.length);
1022
1023 /**
1024 * Look for preexisting entry for key. This will never happen for clone
1025 * or deserialize. It will only happen for construction if the input Map
1026 * is a sorted map whose ordering is inconsistent w/ equals.
1027 */
1028 for (Entry<K1, K2, V> e = this.entries[i]; e != null; e = e.nextCollision)
1029 if (e.hash == hash && HashMap2.objectsEqual(key1, e.get1()) && HashMap2.objectsEqual(key2, e.get2())) {
1030 e.value = value;
1031 return;
1032 }
1033
1034 this.createEntry(hash, key1, key2, value, i);
1035 }
1036
1037 /**
1038 * Like addEntry except that this version is used when creating entries as
1039 * part of Map construction or "pseudo-construction" (cloning,
1040 * deserialization). This version needn't worry about resizing the table.
1041 * Subclass overrides this to alter the behavior of HashMap(Map), clone, and
1042 * readObject.
1043 */
1044 private void createEntry(final int hash, final K1 key1, final K2 key2, final V value, final int bucketIndex) {
1045 final Entry<K1, K2, V> e = this.entries[bucketIndex];
1046 this.entries[bucketIndex] = new Entry<K1, K2, V>(hash, key1, key2, value, e);
1047 this.size++;
1048 }
1049
1050 /**
1051 * @see net.kezvh.collections.Map2.Map2#entrySetOnKey1(java.lang.Object)
1052 * @param key1 COMMENT
1053 * @return COMMENT
1054 */
1055 @Override
1056 public Set<Map2.Entry<K1, K2, V>> entrySetOnKey1(final K1 key1) {
1057 return new SetView<Entry<K1, K2, V>, Map2.Entry<K1, K2, V>>(this.k1Heads.get(key1), this.getBimapEntry);
1058 }
1059
1060 private final L1<Map2.Entry<K1, K2, V>, Entry<K1, K2, V>> getBimapEntry = new L1<Map2.Entry<K1, K2, V>, Entry<K1, K2, V>>() {
1061 /**
1062 * @see net.kezvh.functional.lambda.L1#op(java.lang.Object)
1063 * @param param COMMENT
1064 * @return COMMENT
1065 */
1066 @Override
1067 public Map2.Entry<K1, K2, V> op(final Entry<K1, K2, V> param) {
1068 return param;
1069 }
1070 };
1071
1072 private final L1<K1, Entry<K1, K2, V>> getKey1 = new L1<K1, Entry<K1, K2, V>>() {
1073 /**
1074 * @see net.kezvh.functional.lambda.L1#op(java.lang.Object)
1075 * @param param COMMENT
1076 * @return COMMENT
1077 */
1078 @Override
1079 public K1 op(final Entry<K1, K2, V> param) {
1080 return param.getKey1();
1081 }
1082 };
1083
1084 private final L1<K2, Entry<K1, K2, V>> getKey2 = new L1<K2, Entry<K1, K2, V>>() {
1085 /**
1086 * @see net.kezvh.functional.lambda.L1#op(java.lang.Object)
1087 * @param param COMMENT
1088 * @return COMMENT
1089 */
1090 @Override
1091 public K2 op(final Entry<K1, K2, V> param) {
1092 return param.getKey2();
1093 }
1094 };
1095
1096 private final L1<V, Entry<K1, K2, V>> getValue = new L1<V, Entry<K1, K2, V>>() {
1097 /**
1098 * @see net.kezvh.functional.lambda.L1#op(java.lang.Object)
1099 * @param param COMMENT
1100 * @return COMMENT
1101 */
1102 @Override
1103 public V op(final Entry<K1, K2, V> param) {
1104 return param.getValue();
1105 }
1106 };
1107
1108 /**
1109 * @see net.kezvh.collections.Map2.Map2#entrySetOnKey2(java.lang.Object)
1110 * @param key2 COMMENT
1111 * @return COMMENT
1112 */
1113 @Override
1114 public Set<Map2.Entry<K1, K2, V>> entrySetOnKey2(final K2 key2) {
1115 return new SetView<Entry<K1, K2, V>, Map2.Entry<K1, K2, V>>(this.k2Heads.get(key2), this.getBimapEntry);
1116 }
1117
1118 /**
1119 * @see net.kezvh.collections.Map2.Map2#get(java.lang.Object, java.lang.Object)
1120 * @param key1 COMMENT
1121 * @param key2 COMMENT
1122 * @return COMMENT
1123 */
1124 @Override
1125 public V get(final K1 key1, final K2 key2) {
1126 return this.getEntry(key1, key2).value;
1127 }
1128
1129 /**
1130 * @see net.kezvh.collections.Map2.Map2#isEmpty()
1131 * @return COMMENT
1132 */
1133 @Override
1134 public boolean isEmpty() {
1135 return this.size == 0;
1136 }
1137
1138 /**
1139 * @see net.kezvh.collections.Map2.Map2#keySetOnKey1(java.lang.Object)
1140 * @param key1 COMMENT
1141 * @return COMMENT
1142 */
1143 @Override
1144 public Set<K2> keySetOnKey1(final K1 key1) {
1145 return new SetView<Entry<K1, K2, V>, K2>(this.k1Heads.get(key1), this.getKey2);
1146 }
1147
1148 /**
1149 * @see net.kezvh.collections.Map2.Map2#keySetOnKey2(java.lang.Object)
1150 * @param key2 COMMENT
1151 * @return COMMENT
1152 */
1153 @Override
1154 public Set<K1> keySetOnKey2(final K2 key2) {
1155 return new SetView<Entry<K1, K2, V>, K1>(this.k2Heads.get(key2), this.getKey1);
1156 }
1157
1158 /**
1159 * @see net.kezvh.collections.Map2.Map2#put(java.lang.Object, java.lang.Object,
1160 * java.lang.Object)
1161 * @param key1 COMMENT
1162 * @param key2 COMMENT
1163 * @param value COMMENT
1164 * @return COMMENT
1165 */
1166 @Override
1167 public V put(final K1 key1, final K2 key2, final V value) {
1168 final Entry<K1, K2, V> entry = this.getEntry(key1, key2);
1169 if (entry != null)
1170 return entry.setValue(value);
1171
1172 this.addEntry(key1, key2, value);
1173 return null;
1174 }
1175
1176 private void addEntry(final K1 key1, final K2 key2, final V value) {
1177 if (this.size++ >= this.threshold)
1178 this.resize(this.entries.length << 1);
1179 final int hash = HashMap2.hash(key1, key2);
1180 final int index = HashMap2.indexFor(hash, this.entries.length);
1181 final Entry<K1, K2, V> e = this.entries[index];
1182 final Entry<K1, K2, V> newEntry = new Entry<K1, K2, V>(hash, key1, key2, value, e);
1183 this.entries[index] = newEntry;
1184 HeadSet1 key1Head = this.k1Heads.get(key1);
1185 if (key1Head == null) {
1186 key1Head = new HeadSet1();
1187 this.k1Heads.put(key1, key1Head);
1188 }
1189
1190 HeadSet2 key2Head = this.k2Heads.get(key2);
1191 if (key2Head == null) {
1192 key2Head = new HeadSet2();
1193 this.k2Heads.put(key2, key2Head);
1194 }
1195
1196 key1Head.insertNewHead(newEntry);
1197 key2Head.insertNewHead(newEntry);
1198 }
1199
1200 private void resize(final int newSize) {
1201 final Entry<K1, K2, V>[] newTable = HashMap2.createEntries(this.entries.getClass().getComponentType(), newSize);
1202 for (final Entry<K1, K2, V> entry : this.entries)
1203 if (entry != null)
1204 newTable[HashMap2.indexFor(HashMap2.hash(entry), newSize)] = entry;
1205 }
1206
1207 /**
1208 * @see net.kezvh.collections.Map2.Map2#putAll(net.kezvh.collections.Map2.Map2)
1209 * @param m COMMENT
1210 */
1211 @Override
1212 public void putAll(final Map2<? extends K1, ? extends K2, ? extends V> m) {
1213 if (this.size + m.size() > this.threshold) {
1214 final int newSize = Integer.highestOneBit(this.size + m.size()) << 1;
1215 this.resize(newSize);
1216 }
1217 for (final Map.Entry<? extends Pair<? extends K1, ? extends K2>, ? extends V> o : m.entrySet())
1218 this.put(o.getKey().get1(), o.getKey().get2(), o.getValue());
1219 }
1220
1221 /**
1222 * @see net.kezvh.collections.Map2.Map2#remove(java.lang.Object,
1223 * java.lang.Object)
1224 * @param key1 COMMENT
1225 * @param key2 COMMENT
1226 * @return COMMENT
1227 */
1228 @Override
1229 public V remove(final K1 key1, final K2 key2) {
1230 final Entry<K1, K2, V> e = this.removeEntryForKey(key1, key2);
1231 return (e == null ? null : e.value);
1232 }
1233
1234 private Entry<K1, K2, V> removeEntryForKey(final K1 key1, final K2 key2) {
1235 final int hash = HashMap2.hash(key1, key2);
1236 final int index = HashMap2.indexFor(hash, this.entries.length);
1237
1238 Entry<K1, K2, V> prev = this.entries[index];
1239 Entry<K1, K2, V> e = prev;
1240
1241 while (e != null) {
1242 final Entry<K1, K2, V> next = e.getNextCollision();
1243 if (e.hash == hash && e.matchesKeys(key1, key2)) {
1244 this.modCount++;
1245 this.size--;
1246 if (prev == e)
1247 this.entries[index] = next;
1248 else
1249 prev.setNextCollision(next);
1250 e.removeSelf(this);
1251 return e;
1252 }
1253 prev = e;
1254 e = next;
1255 }
1256
1257 return e;
1258 }
1259
1260 /**
1261 * @see net.kezvh.collections.Map2.Map2#size()
1262 * @return COMMENT
1263 */
1264 @Override
1265 public int size() {
1266 return this.size;
1267 }
1268
1269 /**
1270 * @see net.kezvh.collections.Map2.Map2#valuesOnKey1(java.lang.Object)
1271 * @param key1 COMMENT
1272 * @return COMMENT
1273 */
1274 @Override
1275 public Collection<V> valuesOnKey1(final K1 key1) {
1276 return new SetView<Entry<K1, K2, V>, V>(this.k1Heads.get(key1), this.getValue);
1277 }
1278
1279 /**
1280 * @see net.kezvh.collections.Map2.Map2#valuesOnKey2(java.lang.Object)
1281 * @param key2 COMMENT
1282 * @return COMMENT
1283 */
1284 @Override
1285 public Collection<V> valuesOnKey2(final K2 key2) {
1286 return new SetView<Entry<K1, K2, V>, V>(this.k2Heads.get(key2), this.getValue);
1287 }
1288
1289 /**
1290 * @see java.util.Map#containsKey(java.lang.Object)
1291 * @param key COMMENT
1292 * @return COMMENT
1293 */
1294 @SuppressWarnings("unchecked")
1295 @Override
1296 public boolean containsKey(final Object key) {
1297 if (!(key instanceof Pair))
1298 return false;
1299
1300 final Pair<K1, K2> keys = (Pair<K1, K2>) key;
1301 return this.containsKey(keys.get1(), keys.get2());
1302 }
1303
1304 /**
1305 * @see java.util.Map#containsValue(java.lang.Object)
1306 * @param value COMMENT
1307 * @return COMMENT
1308 */
1309 @Override
1310 public boolean containsValue(final Object value) {
1311 for (final Entry<K1, K2, V> entry : this.entries)
1312 if (entry != null && HashMap2.objectsEqual(entry.getValue(), value))
1313 return true;
1314
1315 return false;
1316 }
1317
1318 /**
1319 * @see java.util.Map#get(java.lang.Object)
1320 * @param key COMMENT
1321 * @return COMMENT
1322 */
1323 @SuppressWarnings("unchecked")
1324 @Override
1325 public V get(final Object key) {
1326 if (!(key instanceof Pair))
1327 return null;
1328
1329 final Pair<K1, K2> keys = (Pair<K1, K2>) key;
1330 return this.get(keys.get1(), keys.get2());
1331 }
1332
1333 /**
1334 * @see java.util.Map#put(java.lang.Object, java.lang.Object)
1335 * @param key COMMENT
1336 * @param value COMMENT
1337 * @return COMMENT
1338 */
1339 @Override
1340 public V put(final Pair<K1, K2> key, final V value) {
1341 return this.put(key.get1(), key.get2(), value);
1342 }
1343
1344 /**
1345 * @param entry COMMENT
1346 * @return COMMENT
1347 */
1348 public V put(final Map2.Entry<K1, K2, V> entry) {
1349 return this.put(entry.getKey1(), entry.getKey2(), entry.getValue());
1350 }
1351
1352 /**
1353 * @see java.util.Map#putAll(java.util.Map)
1354 * @param c COMMENT
1355 * @return COMMENT
1356 */
1357 public boolean putAll(final Collection<? extends Map2.Entry<K1, K2, V>> c) {
1358 if (this.size + c.size() > this.threshold) {
1359 final int newSize = Integer.highestOneBit(this.size + c.size()) << 1;
1360 this.resize(newSize);
1361 }
1362 boolean changed = false;
1363 for (final Map2.Entry<K1, K2, V> o : c)
1364 changed |= this.put(o.getKey().get1(), o.getKey().get2(), o.getValue()) != null;
1365 return changed;
1366 }
1367
1368 /**
1369 * @see java.util.Map#putAll(java.util.Map)
1370 * @param t COMMENT
1371 */
1372 @Override
1373 public void putAll(final Map<? extends Pair<K1, K2>, ? extends V> t) {
1374 if (this.size + t.size() > this.threshold) {
1375 final int newSize = Integer.highestOneBit(this.size + t.size()) << 1;
1376 this.resize(newSize);
1377 }
1378 for (final Map.Entry<? extends Pair<? extends K1, ? extends K2>, ? extends V> o : t.entrySet())
1379 this.put(o.getKey().get1(), o.getKey().get2(), o.getValue());
1380 }
1381
1382 /**
1383 * @see java.util.Map#remove(java.lang.Object)
1384 * @param key COMMENT
1385 * @return COMMENT
1386 */
1387 @SuppressWarnings("unchecked")
1388 @Override
1389 public V remove(final Object key) {
1390 if (!(key instanceof Pair))
1391 return null;
1392
1393 final Pair<K1, K2> keys = (Pair<K1, K2>) key;
1394 return this.remove(keys.get1(), keys.get2());
1395 }
1396
1397 private class EntryMap1 extends AbstractMap<K2, V> {
1398 private final K1 key1;
1399
1400 private final Set<Map.Entry<K2, V>> entryMapSet;
1401
1402 private final L1<Map.Entry<K2, V>, HashMap2.Entry<K1, K2, V>> forwardMap = new L1<Map.Entry<K2, V>, HashMap2.Entry<K1, K2, V>>() {
1403 /**
1404 * @see net.kezvh.functional.lambda.L1#op(java.lang.Object)
1405 * @param param COMMENT
1406 * @return COMMENT
1407 */
1408 @Override
1409 public Map.Entry<K2, V> op(final HashMap2.Entry<K1, K2, V> param) {
1410 return new Map.Entry<K2, V>() {
1411 /**
1412 * @see java.util.Map.Entry#getKey()
1413 * @return COMMENT
1414 */
1415 @Override
1416 public K2 getKey() {
1417 return param.get2();
1418 }
1419
1420 /**
1421 * @see java.util.Map.Entry#getValue()
1422 * @return COMMENT
1423 */
1424 @Override
1425 public V getValue() {
1426 return param.getValue();
1427 }
1428
1429 @Override
1430 public V setValue(final V value) {
1431 return param.setValue(value);
1432 }
1433 };
1434 }
1435 };
1436
1437 /**
1438 * @see java.util.AbstractMap#get(java.lang.Object)
1439 * @param key COMMENT
1440 * @return COMMENT
1441 */
1442 @SuppressWarnings("unchecked")
1443 @Override
1444 public V get(final Object key) {
1445 return HashMap2.this.get(this.key1, (K2) key);
1446 }
1447
1448 @Override
1449 public V put(final K2 key, final V value) {
1450 return HashMap2.this.put(this.key1, key, value);
1451 }
1452
1453 /**
1454 * @see java.util.AbstractMap#remove(java.lang.Object)
1455 * @param key COMMENT
1456 * @return COMMENT
1457 */
1458 @SuppressWarnings("unchecked")
1459 @Override
1460 public V remove(final Object key) {
1461 return HashMap2.this.remove(this.key1, (K2) key);
1462 }
1463
1464 public EntryMap1(final K1 key1) {
1465 this.key1 = key1;
1466 this.entryMapSet = new SetView<HashMap2.Entry<K1, K2, V>, Map.Entry<K2, V>>(HashMap2.this.k1Heads.get(key1), this.forwardMap) {
1467 /**
1468 * @see java.util.AbstractCollection#add(java.lang.Object)
1469 * @param o COMMENT
1470 * @return COMMENT
1471 */
1472 @Override
1473 public boolean add(final java.util.Map.Entry<K2, V> o) {
1474 return HashMap2.this.put(key1, o.getKey(), o.getValue()) != null;
1475 }
1476
1477 /**
1478 * @see java.util.AbstractCollection#clear()
1479 */
1480 @Override
1481 public void clear() {
1482 HashMap2.this.k1Heads.get(key1).clear();
1483 }
1484
1485 /**
1486 * @see java.util.AbstractCollection#contains(java.lang.Object)
1487 * @param o COMMENT
1488 * @return COMENT
1489 */
1490 @SuppressWarnings("unchecked")
1491 @Override
1492 public boolean contains(final Object o) {
1493 if (!(o instanceof Map.Entry))
1494 return false;
1495
1496 final Map.Entry<K2, V> other = (Map.Entry<K2, V>) o;
1497 return HashMap2.this.containsKey(key1, other.getKey());
1498 }
1499
1500 /**
1501 * @see java.util.AbstractCollection#remove(java.lang.Object)
1502 * @param o COMMENT
1503 * @return COMMENT
1504 */
1505 @SuppressWarnings("unchecked")
1506 @Override
1507 public boolean remove(final Object o) {
1508 final Map.Entry<K2, V> other = (Map.Entry<K2, V>) o;
1509 return HashMap2.this.remove(key1, other.getKey()) != null;
1510 }
1511 };
1512 }
1513
1514 /**
1515 * @see java.util.AbstractMap#entrySet()
1516 * @return COMMENT
1517 */
1518 @Override
1519 public Set<java.util.Map.Entry<K2, V>> entrySet() {
1520 return this.entryMapSet;
1521 }
1522 }
1523
1524 /**
1525 * @see net.kezvh.collections.Map2.Map2#entryMapOnKey1(java.lang.Object)
1526 * @param key1 COMMENT
1527 * @return COMMENT
1528 */
1529 @Override
1530 public Map<K2, V> entryMapOnKey1(final K1 key1) {
1531 return new EntryMap1(key1);
1532 }
1533
1534 private class EntryMap2 extends AbstractMap<K1, V> {
1535 private final K2 key2;
1536 private final Set<Map.Entry<K1, V>> entryMapSet;
1537
1538 private final L1<Map.Entry<K1, V>, HashMap2.Entry<K1, K2, V>> forwardMap = new L1<Map.Entry<K1, V>, HashMap2.Entry<K1, K2, V>>() {
1539 /**
1540 * @see net.kezvh.functional.lambda.L1#op(java.lang.Object)
1541 * @param param COMMENT
1542 * @return COMMENT
1543 */
1544 @Override
1545 public Map.Entry<K1, V> op(final HashMap2.Entry<K1, K2, V> param) {
1546 return new Map.Entry<K1, V>() {
1547 /**
1548 * @see java.util.Map.Entry#getKey()
1549 * @return COMMENT
1550 */
1551 @Override
1552 public K1 getKey() {
1553 return param.get1();
1554 }
1555
1556 /**
1557 * @see java.util.Map.Entry#getValue()
1558 * @return COMMENT
1559 */
1560 @Override
1561 public V getValue() {
1562 return param.getValue();
1563 }
1564
1565 @Override
1566 public V setValue(final V value) {
1567 return param.setValue(value);
1568 }
1569 };
1570 }
1571 };
1572
1573 public EntryMap2(final K2 key2) {
1574 this.key2 = key2;
1575 this.entryMapSet = new SetView<HashMap2.Entry<K1, K2, V>, Map.Entry<K1, V>>(HashMap2.this.k1Heads.get(key2), this.forwardMap) {
1576 /**
1577 * @see java.util.AbstractCollection#add(java.lang.Object)
1578 * @param o COMMENT
1579 * @return COMMENT
1580 */
1581 @Override
1582 public boolean add(final java.util.Map.Entry<K1, V> o) {
1583 return HashMap2.this.put(o.getKey(), key2, o.getValue()) != null;
1584 }
1585
1586 /**
1587 * @see java.util.AbstractCollection#clear()
1588 */
1589 @Override
1590 public void clear() {
1591 HashMap2.this.k2Heads.get(key2).clear();
1592 }
1593
1594 /**
1595 * @see java.util.AbstractCollection#contains(java.lang.Object)
1596 * @param o COMMENT
1597 * @return COMENT
1598 */
1599 @SuppressWarnings("unchecked")
1600 @Override
1601 public boolean contains(final Object o) {
1602 if (!(o instanceof Map.Entry))
1603 return false;
1604
1605 final Map.Entry<K1, V> other = (Map.Entry<K1, V>) o;
1606 return HashMap2.this.containsKey(other.getKey(), key2);
1607 }
1608
1609 /**
1610 * @see java.util.AbstractCollection#remove(java.lang.Object)
1611 * @param o COMMENT
1612 * @return COMMENT
1613 */
1614 @SuppressWarnings("unchecked")
1615 @Override
1616 public boolean remove(final Object o) {
1617 final Map.Entry<K1, V> other = (Map.Entry<K1, V>) o;
1618 return HashMap2.this.remove(other.getKey(), key2) != null;
1619 }
1620 };
1621 }
1622
1623 /**
1624 * @see java.util.AbstractMap#entrySet()
1625 * @return COMMENT
1626 */
1627 @Override
1628 public Set<java.util.Map.Entry<K1, V>> entrySet() {
1629 return this.entryMapSet;
1630 }
1631
1632 /**
1633 * @see java.util.AbstractMap#get(java.lang.Object)
1634 * @param key COMMENT
1635 * @return COMMENT
1636 */
1637 @SuppressWarnings("unchecked")
1638 @Override
1639 public V get(final Object key) {
1640 return HashMap2.this.get((K1) key, this.key2);
1641 }
1642
1643 @Override
1644 public V put(final K1 key, final V value) {
1645 return HashMap2.this.put(key, this.key2, value);
1646 }
1647
1648 /**
1649 * @see java.util.AbstractMap#remove(java.lang.Object)
1650 * @param key COMMENT
1651 * @return COMMENT
1652 */
1653 @SuppressWarnings("unchecked")
1654 @Override
1655 public V remove(final Object key) {
1656 return HashMap2.this.remove((K1) key, this.key2);
1657 }
1658 }
1659
1660 /**
1661 * @see net.kezvh.collections.Map2.Map2#entryMapOnKey2(java.lang.Object)
1662 * @param key2 COMMENT
1663 * @return COMMENT
1664 */
1665 @Override
1666 public Map<K1, V> entryMapOnKey2(final K2 key2) {
1667 return new EntryMap2(key2);
1668 }
1669
1670 @Override
1671 public Collection<Map.Entry<K2, V>> get1(final K1 key1) {
1672 return this.entryMapOnKey1(key1).entrySet();
1673 }
1674
1675 @Override
1676 public Collection<Map.Entry<K1, V>> get2(final K2 key2) {
1677 return this.entryMapOnKey2(key2).entrySet();
1678 }
1679
1680 @Override
1681 public Collection<Map.Entry<K2, V>> remove1(final K1 key1) {
1682 final Collection<Map.Entry<K2, V>> removedEntries = new ArrayList<Map.Entry<K2, V>>(this.k1Heads.get(key1).size());
1683
1684 for (final Entry<K1, K2, V> entry : this.k1Heads.get(key1))
1685 removedEntries.add(new MapEntryImpl<K2, V>(entry.get2(), entry.getValue()));
1686
1687 for (final Map.Entry<K2, V> removedEntry : removedEntries)
1688 this.remove(key1, removedEntry.getKey());
1689
1690 return removedEntries;
1691 }
1692
1693 @Override
1694 public Collection<Map.Entry<K1, V>> remove2(final K2 key2) {
1695 final Collection<Map.Entry<K1, V>> removedEntries = new ArrayList<Map.Entry<K1, V>>(this.k2Heads.get(key2).size());
1696
1697 for (final Entry<K1, K2, V> entry : this.k1Heads.get(key2))
1698 removedEntries.add(new MapEntryImpl<K1, V>(entry.get1(), entry.getValue()));
1699
1700 for (final Map.Entry<K1, V> removedEntry : removedEntries)
1701 this.remove(removedEntry.getKey(), key2);
1702
1703 return removedEntries;
1704 }
1705 }
ephemerata