KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > riotfamily > common > collection > FlatMap


1 /* ***** BEGIN LICENSE BLOCK *****
2  * Version: MPL 1.1
3  * The contents of this file are subject to the Mozilla Public License Version
4  * 1.1 (the "License"); you may not use this file except in compliance with
5  * the License. You may obtain a copy of the License at
6  * http://www.mozilla.org/MPL/
7  *
8  * Software distributed under the License is distributed on an "AS IS" basis,
9  * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
10  * for the specific language governing rights and limitations under the
11  * License.
12  *
13  * The Original Code is Riot.
14  *
15  * The Initial Developer of the Original Code is
16  * Neteye GmbH.
17  * Portions created by the Initial Developer are Copyright (C) 2006
18  * the Initial Developer. All Rights Reserved.
19  *
20  * Contributor(s):
21  * Felix Gnass [fgnass at neteye dot de]
22  *
23  * ***** END LICENSE BLOCK ***** */

24 package org.riotfamily.common.collection;
25
26 import java.io.Serializable JavaDoc;
27 import java.util.AbstractCollection JavaDoc;
28 import java.util.AbstractSet JavaDoc;
29 import java.util.Collection JavaDoc;
30 import java.util.HashMap JavaDoc;
31 import java.util.Iterator JavaDoc;
32 import java.util.Map JavaDoc;
33 import java.util.NoSuchElementException JavaDoc;
34 import java.util.Set JavaDoc;
35
36 /**
37  * A <code>Map</code> implementation that stores data in simple fields until
38  * the size is greater than 3.
39  *
40  * This is a striped version of Stephen Colebourne's Flat3Map implementation
41  * from the Jakarta Commons Collections project.
42  *
43  * @link http://jakarta.apache.org/commons/collections/
44  */

45 public class FlatMap implements Map JavaDoc, Serializable JavaDoc, Cloneable JavaDoc {
46
47     private int size;
48
49     private int hash1;
50
51     private int hash2;
52
53     private int hash3;
54
55     private Object JavaDoc key1;
56
57     private Object JavaDoc key2;
58
59     private Object JavaDoc key3;
60
61     private Object JavaDoc value1;
62
63     private Object JavaDoc value2;
64
65     private Object JavaDoc value3;
66
67     private HashMap JavaDoc delegateMap;
68
69     public FlatMap() {
70         super();
71     }
72
73     /**
74      * Constructor copying elements from another map.
75      *
76      * @param map the map to copy
77      * @throws NullPointerException if the map is null
78      */

79     public FlatMap(Map JavaDoc map) {
80         super();
81         putAll(map);
82     }
83
84     /**
85      * Gets the value mapped to the key specified.
86      *
87      * @param key the key
88      * @return the mapped value, null if no match
89      */

90     public Object JavaDoc get(Object JavaDoc key) {
91         if (delegateMap != null) {
92             return delegateMap.get(key);
93         }
94         if (key == null) {
95             switch (size) {
96             case 3:
97                 if (key3 == null)
98                     return value3;
99             case 2:
100                 if (key2 == null)
101                     return value2;
102             case 1:
103                 if (key1 == null)
104                     return value1;
105             }
106         }
107         else {
108             if (size > 0) {
109                 int hashCode = key.hashCode();
110                 switch (size) {
111                 case 3:
112                     if (hash3 == hashCode && key.equals(key3))
113                         return value3;
114                 case 2:
115                     if (hash2 == hashCode && key.equals(key2))
116                         return value2;
117                 case 1:
118                     if (hash1 == hashCode && key.equals(key1))
119                         return value1;
120                 }
121             }
122         }
123         return null;
124     }
125
126     /**
127      * Gets the size of the map.
128      *
129      * @return the size
130      */

131     public int size() {
132         if (delegateMap != null) {
133             return delegateMap.size();
134         }
135         return size;
136     }
137
138     /**
139      * Checks whether the map is currently empty.
140      *
141      * @return true if the map is currently size zero
142      */

143     public boolean isEmpty() {
144         return (size() == 0);
145     }
146
147     /**
148      * Checks whether the map contains the specified key.
149      *
150      * @param key the key to search for
151      * @return true if the map contains the key
152      */

153     public boolean containsKey(Object JavaDoc key) {
154         if (delegateMap != null) {
155             return delegateMap.containsKey(key);
156         }
157         if (key == null) {
158             switch (size) {
159             case 3:
160                 if (key3 == null)
161                     return true;
162             case 2:
163                 if (key2 == null)
164                     return true;
165             case 1:
166                 if (key1 == null)
167                     return true;
168             }
169         }
170         else {
171             if (size > 0) {
172                 int hashCode = key.hashCode();
173                 switch (size) {
174                 case 3:
175                     if (hash3 == hashCode && key.equals(key3))
176                         return true;
177                 case 2:
178                     if (hash2 == hashCode && key.equals(key2))
179                         return true;
180                 case 1:
181                     if (hash1 == hashCode && key.equals(key1))
182                         return true;
183                 }
184             }
185         }
186         return false;
187     }
188
189     /**
190      * Checks whether the map contains the specified value.
191      *
192      * @param value the value to search for
193      * @return true if the map contains the key
194      */

195     public boolean containsValue(Object JavaDoc value) {
196         if (delegateMap != null) {
197             return delegateMap.containsValue(value);
198         }
199         if (value == null) {
200             switch (size) {
201             case 3:
202                 if (value3 == null)
203                     return true;
204             case 2:
205                 if (value2 == null)
206                     return true;
207             case 1:
208                 if (value1 == null)
209                     return true;
210             }
211         }
212         else {
213             switch (size) {
214             case 3:
215                 if (value.equals(value3))
216                     return true;
217             case 2:
218                 if (value.equals(value2))
219                     return true;
220             case 1:
221                 if (value.equals(value1))
222                     return true;
223             }
224         }
225         return false;
226     }
227
228     /**
229      * Puts a key-value mapping into this map.
230      *
231      * @param key the key to add
232      * @param value the value to add
233      * @return the value previously mapped to this key, null if none
234      */

235     public Object JavaDoc put(Object JavaDoc key, Object JavaDoc value) {
236         if (delegateMap != null) {
237             return delegateMap.put(key, value);
238         }
239
240         if (key == null) {
241             switch (size) {
242             case 3:
243                 if (key3 == null) {
244                     Object JavaDoc old = value3;
245                     value3 = value;
246                     return old;
247                 }
248             case 2:
249                 if (key2 == null) {
250                     Object JavaDoc old = value2;
251                     value2 = value;
252                     return old;
253                 }
254             case 1:
255                 if (key1 == null) {
256                     Object JavaDoc old = value1;
257                     value1 = value;
258                     return old;
259                 }
260             }
261         }
262         else {
263             if (size > 0) {
264                 int hashCode = key.hashCode();
265                 switch (size) {
266                 case 3:
267                     if (hash3 == hashCode && key.equals(key3)) {
268                         Object JavaDoc old = value3;
269                         value3 = value;
270                         return old;
271                     }
272                 case 2:
273                     if (hash2 == hashCode && key.equals(key2)) {
274                         Object JavaDoc old = value2;
275                         value2 = value;
276                         return old;
277                     }
278                 case 1:
279                     if (hash1 == hashCode && key.equals(key1)) {
280                         Object JavaDoc old = value1;
281                         value1 = value;
282                         return old;
283                     }
284                 }
285             }
286         }
287
288         switch (size) {
289         default:
290             convertToMap();
291             delegateMap.put(key, value);
292             return null;
293         case 2:
294             hash3 = (key == null ? 0 : key.hashCode());
295             key3 = key;
296             value3 = value;
297             break;
298         case 1:
299             hash2 = (key == null ? 0 : key.hashCode());
300             key2 = key;
301             value2 = value;
302             break;
303         case 0:
304             hash1 = (key == null ? 0 : key.hashCode());
305             key1 = key;
306             value1 = value;
307             break;
308         }
309         size++;
310         return null;
311     }
312
313     /**
314      * Puts all the values from the specified map into this map.
315      *
316      * @param map the map to add
317      * @throws NullPointerException if the map is null
318      */

319     public void putAll(Map JavaDoc map) {
320         int size = map.size();
321         if (size == 0) {
322             return;
323         }
324         if (delegateMap != null) {
325             delegateMap.putAll(map);
326             return;
327         }
328         if (size < 4) {
329             for (Iterator JavaDoc it = map.entrySet().iterator(); it.hasNext();) {
330                 Map.Entry JavaDoc entry = (Map.Entry JavaDoc) it.next();
331                 put(entry.getKey(), entry.getValue());
332             }
333         }
334         else {
335             convertToMap();
336             delegateMap.putAll(map);
337         }
338     }
339
340     /**
341      * Converts the flat map data to a map.
342      */

343     private void convertToMap() {
344         delegateMap = new HashMap JavaDoc();
345         switch (size) {
346         case 3:
347             delegateMap.put(key3, value3);
348         case 2:
349             delegateMap.put(key2, value2);
350         case 1:
351             delegateMap.put(key1, value1);
352         }
353
354         size = 0;
355         hash1 = hash2 = hash3 = 0;
356         key1 = key2 = key3 = null;
357         value1 = value2 = value3 = null;
358     }
359
360     /**
361      * Removes the specified mapping from this map.
362      *
363      * @param key the mapping to remove
364      * @return the value mapped to the removed key, null if key not in map
365      */

366     public Object JavaDoc remove(Object JavaDoc key) {
367         if (delegateMap != null) {
368             return delegateMap.remove(key);
369         }
370         if (size == 0) {
371             return null;
372         }
373         if (key == null) {
374             switch (size) {
375             case 3:
376                 if (key3 == null) {
377                     Object JavaDoc old = value3;
378                     hash3 = 0;
379                     key3 = null;
380                     value3 = null;
381                     size = 2;
382                     return old;
383                 }
384                 if (key2 == null) {
385                     Object JavaDoc old = value3;
386                     hash2 = hash3;
387                     key2 = key3;
388                     value2 = value3;
389                     hash3 = 0;
390                     key3 = null;
391                     value3 = null;
392                     size = 2;
393                     return old;
394                 }
395                 if (key1 == null) {
396                     Object JavaDoc old = value3;
397                     hash1 = hash3;
398                     key1 = key3;
399                     value1 = value3;
400                     hash3 = 0;
401                     key3 = null;
402                     value3 = null;
403                     size = 2;
404                     return old;
405                 }
406                 return null;
407             case 2:
408                 if (key2 == null) {
409                     Object JavaDoc old = value2;
410                     hash2 = 0;
411                     key2 = null;
412                     value2 = null;
413                     size = 1;
414                     return old;
415                 }
416                 if (key1 == null) {
417                     Object JavaDoc old = value2;
418                     hash1 = hash2;
419                     key1 = key2;
420                     value1 = value2;
421                     hash2 = 0;
422                     key2 = null;
423                     value2 = null;
424                     size = 1;
425                     return old;
426                 }
427                 return null;
428             case 1:
429                 if (key1 == null) {
430                     Object JavaDoc old = value1;
431                     hash1 = 0;
432                     key1 = null;
433                     value1 = null;
434                     size = 0;
435                     return old;
436                 }
437             }
438         }
439         else {
440             if (size > 0) {
441                 int hashCode = key.hashCode();
442                 switch (size) {
443                 case 3:
444                     if (hash3 == hashCode && key.equals(key3)) {
445                         Object JavaDoc old = value3;
446                         hash3 = 0;
447                         key3 = null;
448                         value3 = null;
449                         size = 2;
450                         return old;
451                     }
452                     if (hash2 == hashCode && key.equals(key2)) {
453                         Object JavaDoc old = value3;
454                         hash2 = hash3;
455                         key2 = key3;
456                         value2 = value3;
457                         hash3 = 0;
458                         key3 = null;
459                         value3 = null;
460                         size = 2;
461                         return old;
462                     }
463                     if (hash1 == hashCode && key.equals(key1)) {
464                         Object JavaDoc old = value3;
465                         hash1 = hash3;
466                         key1 = key3;
467                         value1 = value3;
468                         hash3 = 0;
469                         key3 = null;
470                         value3 = null;
471                         size = 2;
472                         return old;
473                     }
474                     return null;
475                 case 2:
476                     if (hash2 == hashCode && key.equals(key2)) {
477                         Object JavaDoc old = value2;
478                         hash2 = 0;
479                         key2 = null;
480                         value2 = null;
481                         size = 1;
482                         return old;
483                     }
484                     if (hash1 == hashCode && key.equals(key1)) {
485                         Object JavaDoc old = value2;
486                         hash1 = hash2;
487                         key1 = key2;
488                         value1 = value2;
489                         hash2 = 0;
490                         key2 = null;
491                         value2 = null;
492                         size = 1;
493                         return old;
494                     }
495                     return null;
496                 case 1:
497                     if (hash1 == hashCode && key.equals(key1)) {
498                         Object JavaDoc old = value1;
499                         hash1 = 0;
500                         key1 = null;
501                         value1 = null;
502                         size = 0;
503                         return old;
504                     }
505                 }
506             }
507         }
508         return null;
509     }
510
511     /**
512      * Clears the map, resetting the size to zero and nullifying references to
513      * avoid garbage collection issues.
514      */

515     public void clear() {
516         if (delegateMap != null) {
517             delegateMap.clear();
518             delegateMap = null;
519         }
520         else {
521             size = 0;
522             hash1 = hash2 = hash3 = 0;
523             key1 = key2 = key3 = null;
524             value1 = value2 = value3 = null;
525         }
526     }
527
528     /**
529      * Gets the entrySet view of the map. Changes made to the view affect this
530      * map. The Map Entry is not an independent object and changes as the
531      * iterator progresses.
532      *
533      * @return the entrySet view
534      */

535     public Set JavaDoc entrySet() {
536         if (delegateMap != null) {
537             return delegateMap.entrySet();
538         }
539         return new EntrySet(this);
540     }
541
542     /**
543      * EntrySet
544      */

545     static class EntrySet extends AbstractSet JavaDoc {
546         private final FlatMap parent;
547
548         EntrySet(FlatMap parent) {
549             super();
550             this.parent = parent;
551         }
552
553         public int size() {
554             return parent.size();
555         }
556
557         public void clear() {
558             parent.clear();
559         }
560
561         public boolean remove(Object JavaDoc obj) {
562             if (obj instanceof Map.Entry JavaDoc == false) {
563                 return false;
564             }
565             Map.Entry JavaDoc entry = (Map.Entry JavaDoc) obj;
566             Object JavaDoc key = entry.getKey();
567             boolean result = parent.containsKey(key);
568             parent.remove(key);
569             return result;
570         }
571
572         public Iterator JavaDoc iterator() {
573             if (parent.delegateMap != null) {
574                 return parent.delegateMap.entrySet().iterator();
575             }
576             if (parent.size() == 0) {
577                 return EmptyIterator.INSTANCE;
578             }
579             return new EntrySetIterator(parent);
580         }
581     }
582
583     /**
584      * EntrySetIterator and MapEntry
585      */

586     static class EntrySetIterator implements Iterator JavaDoc, Map.Entry JavaDoc {
587         private final FlatMap parent;
588
589         private int nextIndex = 0;
590
591         private boolean canRemove = false;
592
593         EntrySetIterator(FlatMap parent) {
594             super();
595             this.parent = parent;
596         }
597
598         public boolean hasNext() {
599             return (nextIndex < parent.size);
600         }
601
602         public Object JavaDoc next() {
603             if (hasNext() == false) {
604                 throw new NoSuchElementException JavaDoc(
605                         "No next() entry in the iteration");
606             }
607             canRemove = true;
608             nextIndex++;
609             return this;
610         }
611
612         public void remove() {
613             if (canRemove == false) {
614                 throw new IllegalStateException JavaDoc(
615                         "remove() can only be called once after next()");
616             }
617             parent.remove(getKey());
618             nextIndex--;
619             canRemove = false;
620         }
621
622         public Object JavaDoc getKey() {
623             if (canRemove == false) {
624                 throw new IllegalStateException JavaDoc("getKey() can only be called "
625                         + "after next() and before remove()");
626             }
627             switch (nextIndex) {
628             case 3:
629                 return parent.key3;
630             case 2:
631                 return parent.key2;
632             case 1:
633                 return parent.key1;
634             }
635             throw new IllegalStateException JavaDoc("Invalid map index");
636         }
637
638         public Object JavaDoc getValue() {
639             if (canRemove == false) {
640                 throw new IllegalStateException JavaDoc("getValue() can only be "
641                         + "called after next() and before remove()");
642             }
643             switch (nextIndex) {
644             case 3:
645                 return parent.value3;
646             case 2:
647                 return parent.value2;
648             case 1:
649                 return parent.value1;
650             }
651             throw new IllegalStateException JavaDoc("Invalid map index");
652         }
653
654         public Object JavaDoc setValue(Object JavaDoc value) {
655             if (canRemove == false) {
656                 throw new IllegalStateException JavaDoc("setValue() can only be "
657                         + "called after next() and before remove()");
658             }
659             Object JavaDoc old = getValue();
660             switch (nextIndex) {
661             case 3:
662                 parent.value3 = value;
663             case 2:
664                 parent.value2 = value;
665             case 1:
666                 parent.value1 = value;
667             }
668             return old;
669         }
670
671         public boolean equals(Object JavaDoc obj) {
672             if (canRemove == false) {
673                 return false;
674             }
675             if (obj instanceof Map.Entry JavaDoc == false) {
676                 return false;
677             }
678             Map.Entry JavaDoc other = (Map.Entry JavaDoc) obj;
679             Object JavaDoc key = getKey();
680             Object JavaDoc value = getValue();
681             return (key == null ? other.getKey() == null : key.equals(other
682                     .getKey()))
683                     && (value == null ? other.getValue() == null : value
684                             .equals(other.getValue()));
685         }
686
687         public int hashCode() {
688             if (canRemove == false) {
689                 return 0;
690             }
691             Object JavaDoc key = getKey();
692             Object JavaDoc value = getValue();
693             return (key == null ? 0 : key.hashCode())
694                     ^ (value == null ? 0 : value.hashCode());
695         }
696
697         public String JavaDoc toString() {
698             if (canRemove) {
699                 return getKey() + "=" + getValue();
700             }
701             else {
702                 return "";
703             }
704         }
705     }
706
707     /**
708      * Gets the keySet view of the map. Changes made to the view affect this
709      * map.
710      *
711      * @return the keySet view
712      */

713     public Set JavaDoc keySet() {
714         if (delegateMap != null) {
715             return delegateMap.keySet();
716         }
717         return new KeySet(this);
718     }
719
720     /**
721      * KeySet
722      */

723     static class KeySet extends AbstractSet JavaDoc {
724         private final FlatMap parent;
725
726         KeySet(FlatMap parent) {
727             super();
728             this.parent = parent;
729         }
730
731         public int size() {
732             return parent.size();
733         }
734
735         public void clear() {
736             parent.clear();
737         }
738
739         public boolean contains(Object JavaDoc key) {
740             return parent.containsKey(key);
741         }
742
743         public boolean remove(Object JavaDoc key) {
744             boolean result = parent.containsKey(key);
745             parent.remove(key);
746             return result;
747         }
748
749         public Iterator JavaDoc iterator() {
750             if (parent.delegateMap != null) {
751                 return parent.delegateMap.keySet().iterator();
752             }
753             if (parent.size() == 0) {
754                 return EmptyIterator.INSTANCE;
755             }
756             return new KeySetIterator(parent);
757         }
758     }
759
760     /**
761      * KeySetIterator
762      */

763     static class KeySetIterator extends EntrySetIterator {
764
765         KeySetIterator(FlatMap parent) {
766             super(parent);
767         }
768
769         public Object JavaDoc next() {
770             super.next();
771             return getKey();
772         }
773     }
774
775     /**
776      * Gets the values view of the map. Changes made to the view affect this
777      * map.
778      *
779      * @return the values view
780      */

781     public Collection JavaDoc values() {
782         if (delegateMap != null) {
783             return delegateMap.values();
784         }
785         return new Values(this);
786     }
787
788     /**
789      * Values
790      */

791     static class Values extends AbstractCollection JavaDoc {
792         private final FlatMap parent;
793
794         Values(FlatMap parent) {
795             super();
796             this.parent = parent;
797         }
798
799         public int size() {
800             return parent.size();
801         }
802
803         public void clear() {
804             parent.clear();
805         }
806
807         public boolean contains(Object JavaDoc value) {
808             return parent.containsValue(value);
809         }
810
811         public Iterator JavaDoc iterator() {
812             if (parent.delegateMap != null) {
813                 return parent.delegateMap.values().iterator();
814             }
815             if (parent.size() == 0) {
816                 return EmptyIterator.INSTANCE;
817             }
818             return new ValuesIterator(parent);
819         }
820     }
821
822     /**
823      * ValuesIterator
824      */

825     static class ValuesIterator extends EntrySetIterator {
826
827         ValuesIterator(FlatMap parent) {
828             super(parent);
829         }
830
831         public Object JavaDoc next() {
832             super.next();
833             return getValue();
834         }
835     }
836
837     /**
838      * Compares this map with another.
839      *
840      * @param obj the object to compare to
841      * @return true if equal
842      */

843     public boolean equals(Object JavaDoc obj) {
844         if (obj == this) {
845             return true;
846         }
847         if (delegateMap != null) {
848             return delegateMap.equals(obj);
849         }
850         if (obj instanceof Map JavaDoc == false) {
851             return false;
852         }
853         Map JavaDoc other = (Map JavaDoc) obj;
854         if (size != other.size()) {
855             return false;
856         }
857         if (size > 0) {
858             Object JavaDoc otherValue = null;
859             switch (size) {
860             case 3:
861                 if (other.containsKey(key3) == false) {
862                     otherValue = other.get(key3);
863                     if (value3 == null ? otherValue != null : !value3
864                             .equals(otherValue)) {
865                         return false;
866                     }
867                 }
868             case 2:
869                 if (other.containsKey(key2) == false) {
870                     otherValue = other.get(key2);
871                     if (value2 == null ? otherValue != null : !value2
872                             .equals(otherValue)) {
873                         return false;
874                     }
875                 }
876             case 1:
877                 if (other.containsKey(key1) == false) {
878                     otherValue = other.get(key1);
879                     if (value1 == null ? otherValue != null : !value1
880                             .equals(otherValue)) {
881                         return false;
882                     }
883                 }
884             }
885         }
886         return true;
887     }
888
889     /**
890      * Gets the standard Map hashCode.
891      *
892      * @return the hash code defined in the Map interface
893      */

894     public int hashCode() {
895         if (delegateMap != null) {
896             return delegateMap.hashCode();
897         }
898         int total = 0;
899         switch (size) {
900         case 3:
901             total += (hash3 ^ (value3 == null ? 0 : value3.hashCode()));
902         case 2:
903             total += (hash2 ^ (value2 == null ? 0 : value2.hashCode()));
904         case 1:
905             total += (hash1 ^ (value1 == null ? 0 : value1.hashCode()));
906         }
907         return total;
908     }
909
910     /**
911      * Gets the map as a String.
912      *
913      * @return a string version of the map
914      */

915     public String JavaDoc toString() {
916         if (delegateMap != null) {
917             return delegateMap.toString();
918         }
919         if (size == 0) {
920             return "{}";
921         }
922         StringBuffer JavaDoc buf = new StringBuffer JavaDoc(128);
923         buf.append('{');
924         switch (size) {
925         case 3:
926             buf.append((key3 == this ? "(this Map)" : key3));
927             buf.append('=');
928             buf.append((value3 == this ? "(this Map)" : value3));
929             buf.append(',');
930         case 2:
931             buf.append((key2 == this ? "(this Map)" : key2));
932             buf.append('=');
933             buf.append((value2 == this ? "(this Map)" : value2));
934             buf.append(',');
935         case 1:
936             buf.append((key1 == this ? "(this Map)" : key1));
937             buf.append('=');
938             buf.append((value1 == this ? "(this Map)" : value1));
939         }
940         buf.append('}');
941         return buf.toString();
942     }
943
944 }
945
Popular Tags