001: /* ***** BEGIN LICENSE BLOCK *****
002: * Version: MPL 1.1
003: * The contents of this file are subject to the Mozilla Public License Version
004: * 1.1 (the "License"); you may not use this file except in compliance with
005: * the License. You may obtain a copy of the License at
006: * http://www.mozilla.org/MPL/
007: *
008: * Software distributed under the License is distributed on an "AS IS" basis,
009: * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
010: * for the specific language governing rights and limitations under the
011: * License.
012: *
013: * The Original Code is Riot.
014: *
015: * The Initial Developer of the Original Code is
016: * Neteye GmbH.
017: * Portions created by the Initial Developer are Copyright (C) 2006
018: * the Initial Developer. All Rights Reserved.
019: *
020: * Contributor(s):
021: * Felix Gnass [fgnass at neteye dot de]
022: *
023: * ***** END LICENSE BLOCK ***** */
024: package org.riotfamily.common.collection;
025:
026: import java.io.Serializable;
027: import java.util.AbstractCollection;
028: import java.util.AbstractSet;
029: import java.util.Collection;
030: import java.util.HashMap;
031: import java.util.Iterator;
032: import java.util.Map;
033: import java.util.NoSuchElementException;
034: import java.util.Set;
035:
036: /**
037: * A <code>Map</code> implementation that stores data in simple fields until
038: * the size is greater than 3.
039: *
040: * This is a striped version of Stephen Colebourne's Flat3Map implementation
041: * from the Jakarta Commons Collections project.
042: *
043: * @link http://jakarta.apache.org/commons/collections/
044: */
045: public class FlatMap implements Map, Serializable, Cloneable {
046:
047: private int size;
048:
049: private int hash1;
050:
051: private int hash2;
052:
053: private int hash3;
054:
055: private Object key1;
056:
057: private Object key2;
058:
059: private Object key3;
060:
061: private Object value1;
062:
063: private Object value2;
064:
065: private Object value3;
066:
067: private HashMap delegateMap;
068:
069: public FlatMap() {
070: super ();
071: }
072:
073: /**
074: * Constructor copying elements from another map.
075: *
076: * @param map the map to copy
077: * @throws NullPointerException if the map is null
078: */
079: public FlatMap(Map map) {
080: super ();
081: putAll(map);
082: }
083:
084: /**
085: * Gets the value mapped to the key specified.
086: *
087: * @param key the key
088: * @return the mapped value, null if no match
089: */
090: public Object get(Object key) {
091: if (delegateMap != null) {
092: return delegateMap.get(key);
093: }
094: if (key == null) {
095: switch (size) {
096: case 3:
097: if (key3 == null)
098: return value3;
099: case 2:
100: if (key2 == null)
101: return value2;
102: case 1:
103: if (key1 == null)
104: return value1;
105: }
106: } else {
107: if (size > 0) {
108: int hashCode = key.hashCode();
109: switch (size) {
110: case 3:
111: if (hash3 == hashCode && key.equals(key3))
112: return value3;
113: case 2:
114: if (hash2 == hashCode && key.equals(key2))
115: return value2;
116: case 1:
117: if (hash1 == hashCode && key.equals(key1))
118: return value1;
119: }
120: }
121: }
122: return null;
123: }
124:
125: /**
126: * Gets the size of the map.
127: *
128: * @return the size
129: */
130: public int size() {
131: if (delegateMap != null) {
132: return delegateMap.size();
133: }
134: return size;
135: }
136:
137: /**
138: * Checks whether the map is currently empty.
139: *
140: * @return true if the map is currently size zero
141: */
142: public boolean isEmpty() {
143: return (size() == 0);
144: }
145:
146: /**
147: * Checks whether the map contains the specified key.
148: *
149: * @param key the key to search for
150: * @return true if the map contains the key
151: */
152: public boolean containsKey(Object key) {
153: if (delegateMap != null) {
154: return delegateMap.containsKey(key);
155: }
156: if (key == null) {
157: switch (size) {
158: case 3:
159: if (key3 == null)
160: return true;
161: case 2:
162: if (key2 == null)
163: return true;
164: case 1:
165: if (key1 == null)
166: return true;
167: }
168: } else {
169: if (size > 0) {
170: int hashCode = key.hashCode();
171: switch (size) {
172: case 3:
173: if (hash3 == hashCode && key.equals(key3))
174: return true;
175: case 2:
176: if (hash2 == hashCode && key.equals(key2))
177: return true;
178: case 1:
179: if (hash1 == hashCode && key.equals(key1))
180: return true;
181: }
182: }
183: }
184: return false;
185: }
186:
187: /**
188: * Checks whether the map contains the specified value.
189: *
190: * @param value the value to search for
191: * @return true if the map contains the key
192: */
193: public boolean containsValue(Object value) {
194: if (delegateMap != null) {
195: return delegateMap.containsValue(value);
196: }
197: if (value == null) {
198: switch (size) {
199: case 3:
200: if (value3 == null)
201: return true;
202: case 2:
203: if (value2 == null)
204: return true;
205: case 1:
206: if (value1 == null)
207: return true;
208: }
209: } else {
210: switch (size) {
211: case 3:
212: if (value.equals(value3))
213: return true;
214: case 2:
215: if (value.equals(value2))
216: return true;
217: case 1:
218: if (value.equals(value1))
219: return true;
220: }
221: }
222: return false;
223: }
224:
225: /**
226: * Puts a key-value mapping into this map.
227: *
228: * @param key the key to add
229: * @param value the value to add
230: * @return the value previously mapped to this key, null if none
231: */
232: public Object put(Object key, Object value) {
233: if (delegateMap != null) {
234: return delegateMap.put(key, value);
235: }
236:
237: if (key == null) {
238: switch (size) {
239: case 3:
240: if (key3 == null) {
241: Object old = value3;
242: value3 = value;
243: return old;
244: }
245: case 2:
246: if (key2 == null) {
247: Object old = value2;
248: value2 = value;
249: return old;
250: }
251: case 1:
252: if (key1 == null) {
253: Object old = value1;
254: value1 = value;
255: return old;
256: }
257: }
258: } else {
259: if (size > 0) {
260: int hashCode = key.hashCode();
261: switch (size) {
262: case 3:
263: if (hash3 == hashCode && key.equals(key3)) {
264: Object old = value3;
265: value3 = value;
266: return old;
267: }
268: case 2:
269: if (hash2 == hashCode && key.equals(key2)) {
270: Object old = value2;
271: value2 = value;
272: return old;
273: }
274: case 1:
275: if (hash1 == hashCode && key.equals(key1)) {
276: Object old = value1;
277: value1 = value;
278: return old;
279: }
280: }
281: }
282: }
283:
284: switch (size) {
285: default:
286: convertToMap();
287: delegateMap.put(key, value);
288: return null;
289: case 2:
290: hash3 = (key == null ? 0 : key.hashCode());
291: key3 = key;
292: value3 = value;
293: break;
294: case 1:
295: hash2 = (key == null ? 0 : key.hashCode());
296: key2 = key;
297: value2 = value;
298: break;
299: case 0:
300: hash1 = (key == null ? 0 : key.hashCode());
301: key1 = key;
302: value1 = value;
303: break;
304: }
305: size++;
306: return null;
307: }
308:
309: /**
310: * Puts all the values from the specified map into this map.
311: *
312: * @param map the map to add
313: * @throws NullPointerException if the map is null
314: */
315: public void putAll(Map map) {
316: int size = map.size();
317: if (size == 0) {
318: return;
319: }
320: if (delegateMap != null) {
321: delegateMap.putAll(map);
322: return;
323: }
324: if (size < 4) {
325: for (Iterator it = map.entrySet().iterator(); it.hasNext();) {
326: Map.Entry entry = (Map.Entry) it.next();
327: put(entry.getKey(), entry.getValue());
328: }
329: } else {
330: convertToMap();
331: delegateMap.putAll(map);
332: }
333: }
334:
335: /**
336: * Converts the flat map data to a map.
337: */
338: private void convertToMap() {
339: delegateMap = new HashMap();
340: switch (size) {
341: case 3:
342: delegateMap.put(key3, value3);
343: case 2:
344: delegateMap.put(key2, value2);
345: case 1:
346: delegateMap.put(key1, value1);
347: }
348:
349: size = 0;
350: hash1 = hash2 = hash3 = 0;
351: key1 = key2 = key3 = null;
352: value1 = value2 = value3 = null;
353: }
354:
355: /**
356: * Removes the specified mapping from this map.
357: *
358: * @param key the mapping to remove
359: * @return the value mapped to the removed key, null if key not in map
360: */
361: public Object remove(Object key) {
362: if (delegateMap != null) {
363: return delegateMap.remove(key);
364: }
365: if (size == 0) {
366: return null;
367: }
368: if (key == null) {
369: switch (size) {
370: case 3:
371: if (key3 == null) {
372: Object old = value3;
373: hash3 = 0;
374: key3 = null;
375: value3 = null;
376: size = 2;
377: return old;
378: }
379: if (key2 == null) {
380: Object old = value3;
381: hash2 = hash3;
382: key2 = key3;
383: value2 = value3;
384: hash3 = 0;
385: key3 = null;
386: value3 = null;
387: size = 2;
388: return old;
389: }
390: if (key1 == null) {
391: Object old = value3;
392: hash1 = hash3;
393: key1 = key3;
394: value1 = value3;
395: hash3 = 0;
396: key3 = null;
397: value3 = null;
398: size = 2;
399: return old;
400: }
401: return null;
402: case 2:
403: if (key2 == null) {
404: Object old = value2;
405: hash2 = 0;
406: key2 = null;
407: value2 = null;
408: size = 1;
409: return old;
410: }
411: if (key1 == null) {
412: Object old = value2;
413: hash1 = hash2;
414: key1 = key2;
415: value1 = value2;
416: hash2 = 0;
417: key2 = null;
418: value2 = null;
419: size = 1;
420: return old;
421: }
422: return null;
423: case 1:
424: if (key1 == null) {
425: Object old = value1;
426: hash1 = 0;
427: key1 = null;
428: value1 = null;
429: size = 0;
430: return old;
431: }
432: }
433: } else {
434: if (size > 0) {
435: int hashCode = key.hashCode();
436: switch (size) {
437: case 3:
438: if (hash3 == hashCode && key.equals(key3)) {
439: Object old = value3;
440: hash3 = 0;
441: key3 = null;
442: value3 = null;
443: size = 2;
444: return old;
445: }
446: if (hash2 == hashCode && key.equals(key2)) {
447: Object old = value3;
448: hash2 = hash3;
449: key2 = key3;
450: value2 = value3;
451: hash3 = 0;
452: key3 = null;
453: value3 = null;
454: size = 2;
455: return old;
456: }
457: if (hash1 == hashCode && key.equals(key1)) {
458: Object old = value3;
459: hash1 = hash3;
460: key1 = key3;
461: value1 = value3;
462: hash3 = 0;
463: key3 = null;
464: value3 = null;
465: size = 2;
466: return old;
467: }
468: return null;
469: case 2:
470: if (hash2 == hashCode && key.equals(key2)) {
471: Object old = value2;
472: hash2 = 0;
473: key2 = null;
474: value2 = null;
475: size = 1;
476: return old;
477: }
478: if (hash1 == hashCode && key.equals(key1)) {
479: Object old = value2;
480: hash1 = hash2;
481: key1 = key2;
482: value1 = value2;
483: hash2 = 0;
484: key2 = null;
485: value2 = null;
486: size = 1;
487: return old;
488: }
489: return null;
490: case 1:
491: if (hash1 == hashCode && key.equals(key1)) {
492: Object old = value1;
493: hash1 = 0;
494: key1 = null;
495: value1 = null;
496: size = 0;
497: return old;
498: }
499: }
500: }
501: }
502: return null;
503: }
504:
505: /**
506: * Clears the map, resetting the size to zero and nullifying references to
507: * avoid garbage collection issues.
508: */
509: public void clear() {
510: if (delegateMap != null) {
511: delegateMap.clear();
512: delegateMap = null;
513: } else {
514: size = 0;
515: hash1 = hash2 = hash3 = 0;
516: key1 = key2 = key3 = null;
517: value1 = value2 = value3 = null;
518: }
519: }
520:
521: /**
522: * Gets the entrySet view of the map. Changes made to the view affect this
523: * map. The Map Entry is not an independent object and changes as the
524: * iterator progresses.
525: *
526: * @return the entrySet view
527: */
528: public Set entrySet() {
529: if (delegateMap != null) {
530: return delegateMap.entrySet();
531: }
532: return new EntrySet(this );
533: }
534:
535: /**
536: * EntrySet
537: */
538: static class EntrySet extends AbstractSet {
539: private final FlatMap parent;
540:
541: EntrySet(FlatMap parent) {
542: super ();
543: this .parent = parent;
544: }
545:
546: public int size() {
547: return parent.size();
548: }
549:
550: public void clear() {
551: parent.clear();
552: }
553:
554: public boolean remove(Object obj) {
555: if (obj instanceof Map.Entry == false) {
556: return false;
557: }
558: Map.Entry entry = (Map.Entry) obj;
559: Object key = entry.getKey();
560: boolean result = parent.containsKey(key);
561: parent.remove(key);
562: return result;
563: }
564:
565: public Iterator iterator() {
566: if (parent.delegateMap != null) {
567: return parent.delegateMap.entrySet().iterator();
568: }
569: if (parent.size() == 0) {
570: return EmptyIterator.INSTANCE;
571: }
572: return new EntrySetIterator(parent);
573: }
574: }
575:
576: /**
577: * EntrySetIterator and MapEntry
578: */
579: static class EntrySetIterator implements Iterator, Map.Entry {
580: private final FlatMap parent;
581:
582: private int nextIndex = 0;
583:
584: private boolean canRemove = false;
585:
586: EntrySetIterator(FlatMap parent) {
587: super ();
588: this .parent = parent;
589: }
590:
591: public boolean hasNext() {
592: return (nextIndex < parent.size);
593: }
594:
595: public Object next() {
596: if (hasNext() == false) {
597: throw new NoSuchElementException(
598: "No next() entry in the iteration");
599: }
600: canRemove = true;
601: nextIndex++;
602: return this ;
603: }
604:
605: public void remove() {
606: if (canRemove == false) {
607: throw new IllegalStateException(
608: "remove() can only be called once after next()");
609: }
610: parent.remove(getKey());
611: nextIndex--;
612: canRemove = false;
613: }
614:
615: public Object getKey() {
616: if (canRemove == false) {
617: throw new IllegalStateException(
618: "getKey() can only be called "
619: + "after next() and before remove()");
620: }
621: switch (nextIndex) {
622: case 3:
623: return parent.key3;
624: case 2:
625: return parent.key2;
626: case 1:
627: return parent.key1;
628: }
629: throw new IllegalStateException("Invalid map index");
630: }
631:
632: public Object getValue() {
633: if (canRemove == false) {
634: throw new IllegalStateException(
635: "getValue() can only be "
636: + "called after next() and before remove()");
637: }
638: switch (nextIndex) {
639: case 3:
640: return parent.value3;
641: case 2:
642: return parent.value2;
643: case 1:
644: return parent.value1;
645: }
646: throw new IllegalStateException("Invalid map index");
647: }
648:
649: public Object setValue(Object value) {
650: if (canRemove == false) {
651: throw new IllegalStateException(
652: "setValue() can only be "
653: + "called after next() and before remove()");
654: }
655: Object old = getValue();
656: switch (nextIndex) {
657: case 3:
658: parent.value3 = value;
659: case 2:
660: parent.value2 = value;
661: case 1:
662: parent.value1 = value;
663: }
664: return old;
665: }
666:
667: public boolean equals(Object obj) {
668: if (canRemove == false) {
669: return false;
670: }
671: if (obj instanceof Map.Entry == false) {
672: return false;
673: }
674: Map.Entry other = (Map.Entry) obj;
675: Object key = getKey();
676: Object value = getValue();
677: return (key == null ? other.getKey() == null : key
678: .equals(other.getKey()))
679: && (value == null ? other.getValue() == null
680: : value.equals(other.getValue()));
681: }
682:
683: public int hashCode() {
684: if (canRemove == false) {
685: return 0;
686: }
687: Object key = getKey();
688: Object value = getValue();
689: return (key == null ? 0 : key.hashCode())
690: ^ (value == null ? 0 : value.hashCode());
691: }
692:
693: public String toString() {
694: if (canRemove) {
695: return getKey() + "=" + getValue();
696: } else {
697: return "";
698: }
699: }
700: }
701:
702: /**
703: * Gets the keySet view of the map. Changes made to the view affect this
704: * map.
705: *
706: * @return the keySet view
707: */
708: public Set keySet() {
709: if (delegateMap != null) {
710: return delegateMap.keySet();
711: }
712: return new KeySet(this );
713: }
714:
715: /**
716: * KeySet
717: */
718: static class KeySet extends AbstractSet {
719: private final FlatMap parent;
720:
721: KeySet(FlatMap parent) {
722: super ();
723: this .parent = parent;
724: }
725:
726: public int size() {
727: return parent.size();
728: }
729:
730: public void clear() {
731: parent.clear();
732: }
733:
734: public boolean contains(Object key) {
735: return parent.containsKey(key);
736: }
737:
738: public boolean remove(Object key) {
739: boolean result = parent.containsKey(key);
740: parent.remove(key);
741: return result;
742: }
743:
744: public Iterator iterator() {
745: if (parent.delegateMap != null) {
746: return parent.delegateMap.keySet().iterator();
747: }
748: if (parent.size() == 0) {
749: return EmptyIterator.INSTANCE;
750: }
751: return new KeySetIterator(parent);
752: }
753: }
754:
755: /**
756: * KeySetIterator
757: */
758: static class KeySetIterator extends EntrySetIterator {
759:
760: KeySetIterator(FlatMap parent) {
761: super (parent);
762: }
763:
764: public Object next() {
765: super .next();
766: return getKey();
767: }
768: }
769:
770: /**
771: * Gets the values view of the map. Changes made to the view affect this
772: * map.
773: *
774: * @return the values view
775: */
776: public Collection values() {
777: if (delegateMap != null) {
778: return delegateMap.values();
779: }
780: return new Values(this );
781: }
782:
783: /**
784: * Values
785: */
786: static class Values extends AbstractCollection {
787: private final FlatMap parent;
788:
789: Values(FlatMap parent) {
790: super ();
791: this .parent = parent;
792: }
793:
794: public int size() {
795: return parent.size();
796: }
797:
798: public void clear() {
799: parent.clear();
800: }
801:
802: public boolean contains(Object value) {
803: return parent.containsValue(value);
804: }
805:
806: public Iterator iterator() {
807: if (parent.delegateMap != null) {
808: return parent.delegateMap.values().iterator();
809: }
810: if (parent.size() == 0) {
811: return EmptyIterator.INSTANCE;
812: }
813: return new ValuesIterator(parent);
814: }
815: }
816:
817: /**
818: * ValuesIterator
819: */
820: static class ValuesIterator extends EntrySetIterator {
821:
822: ValuesIterator(FlatMap parent) {
823: super (parent);
824: }
825:
826: public Object next() {
827: super .next();
828: return getValue();
829: }
830: }
831:
832: /**
833: * Compares this map with another.
834: *
835: * @param obj the object to compare to
836: * @return true if equal
837: */
838: public boolean equals(Object obj) {
839: if (obj == this ) {
840: return true;
841: }
842: if (delegateMap != null) {
843: return delegateMap.equals(obj);
844: }
845: if (obj instanceof Map == false) {
846: return false;
847: }
848: Map other = (Map) obj;
849: if (size != other.size()) {
850: return false;
851: }
852: if (size > 0) {
853: Object otherValue = null;
854: switch (size) {
855: case 3:
856: if (other.containsKey(key3) == false) {
857: otherValue = other.get(key3);
858: if (value3 == null ? otherValue != null : !value3
859: .equals(otherValue)) {
860: return false;
861: }
862: }
863: case 2:
864: if (other.containsKey(key2) == false) {
865: otherValue = other.get(key2);
866: if (value2 == null ? otherValue != null : !value2
867: .equals(otherValue)) {
868: return false;
869: }
870: }
871: case 1:
872: if (other.containsKey(key1) == false) {
873: otherValue = other.get(key1);
874: if (value1 == null ? otherValue != null : !value1
875: .equals(otherValue)) {
876: return false;
877: }
878: }
879: }
880: }
881: return true;
882: }
883:
884: /**
885: * Gets the standard Map hashCode.
886: *
887: * @return the hash code defined in the Map interface
888: */
889: public int hashCode() {
890: if (delegateMap != null) {
891: return delegateMap.hashCode();
892: }
893: int total = 0;
894: switch (size) {
895: case 3:
896: total += (hash3 ^ (value3 == null ? 0 : value3.hashCode()));
897: case 2:
898: total += (hash2 ^ (value2 == null ? 0 : value2.hashCode()));
899: case 1:
900: total += (hash1 ^ (value1 == null ? 0 : value1.hashCode()));
901: }
902: return total;
903: }
904:
905: /**
906: * Gets the map as a String.
907: *
908: * @return a string version of the map
909: */
910: public String toString() {
911: if (delegateMap != null) {
912: return delegateMap.toString();
913: }
914: if (size == 0) {
915: return "{}";
916: }
917: StringBuffer buf = new StringBuffer(128);
918: buf.append('{');
919: switch (size) {
920: case 3:
921: buf.append((key3 == this ? "(this Map)" : key3));
922: buf.append('=');
923: buf.append((value3 == this ? "(this Map)" : value3));
924: buf.append(',');
925: case 2:
926: buf.append((key2 == this ? "(this Map)" : key2));
927: buf.append('=');
928: buf.append((value2 == this ? "(this Map)" : value2));
929: buf.append(',');
930: case 1:
931: buf.append((key1 == this ? "(this Map)" : key1));
932: buf.append('=');
933: buf.append((value1 == this ? "(this Map)" : value1));
934: }
935: buf.append('}');
936: return buf.toString();
937: }
938:
939: }
|