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