001: /*
002: * Copyright 2001-2004 The Apache Software Foundation
003: *
004: * Licensed under the Apache License, Version 2.0 (the "License");
005: * you may not use this file except in compliance with the License.
006: * You may obtain a copy of the License at
007: *
008: * http://www.apache.org/licenses/LICENSE-2.0
009: *
010: * Unless required by applicable law or agreed to in writing, software
011: * distributed under the License is distributed on an "AS IS" BASIS,
012: * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
013: * See the License for the specific language governing permissions and
014: * limitations under the License.
015: */
016: package org.apache.commons.collections;
017:
018: import java.util.Collection;
019: import java.util.Comparator;
020: import java.util.ConcurrentModificationException;
021: import java.util.Iterator;
022: import java.util.Map;
023: import java.util.Set;
024: import java.util.SortedMap;
025: import java.util.TreeMap;
026:
027: /**
028: * <p>A customized implementation of <code>java.util.TreeMap</code> designed
029: * to operate in a multithreaded environment where the large majority of
030: * method calls are read-only, instead of structural changes. When operating
031: * in "fast" mode, read calls are non-synchronized and write calls perform the
032: * following steps:</p>
033: * <ul>
034: * <li>Clone the existing collection
035: * <li>Perform the modification on the clone
036: * <li>Replace the existing collection with the (modified) clone
037: * </ul>
038: * <p>When first created, objects of this class default to "slow" mode, where
039: * all accesses of any type are synchronized but no cloning takes place. This
040: * is appropriate for initially populating the collection, followed by a switch
041: * to "fast" mode (by calling <code>setFast(true)</code>) after initialization
042: * is complete.</p>
043: *
044: * <p><strong>NOTE</strong>: If you are creating and accessing a
045: * <code>TreeMap</code> only within a single thread, you should use
046: * <code>java.util.TreeMap</code> directly (with no synchronization), for
047: * maximum performance.</p>
048: *
049: * <p><strong>NOTE</strong>: <i>This class is not cross-platform.
050: * Using it may cause unexpected failures on some architectures.</i>
051: * It suffers from the same problems as the double-checked locking idiom.
052: * In particular, the instruction that clones the internal collection and the
053: * instruction that sets the internal reference to the clone can be executed
054: * or perceived out-of-order. This means that any read operation might fail
055: * unexpectedly, as it may be reading the state of the internal collection
056: * before the internal collection is fully formed.
057: * For more information on the double-checked locking idiom, see the
058: * <a href="http://www.cs.umd.edu/~pugh/java/memoryModel/DoubleCheckedLocking.html">
059: * Double-Checked Locking Idiom Is Broken Declaration</a>.</p>
060: *
061: * @since Commons Collections 1.0
062: * @version $Revision: 155406 $ $Date: 2005-02-26 12:55:26 +0000 (Sat, 26 Feb 2005) $
063: *
064: * @author Craig R. McClanahan
065: * @author Stephen Colebourne
066: */
067: public class FastTreeMap extends TreeMap {
068:
069: /**
070: * The underlying map we are managing.
071: */
072: protected TreeMap map = null;
073:
074: /**
075: * Are we operating in "fast" mode?
076: */
077: protected boolean fast = false;
078:
079: // Constructors
080: // ----------------------------------------------------------------------
081:
082: /**
083: * Construct a an empty map.
084: */
085: public FastTreeMap() {
086: super ();
087: this .map = new TreeMap();
088: }
089:
090: /**
091: * Construct an empty map with the specified comparator.
092: *
093: * @param comparator the comparator to use for ordering tree elements
094: */
095: public FastTreeMap(Comparator comparator) {
096: super ();
097: this .map = new TreeMap(comparator);
098: }
099:
100: /**
101: * Construct a new map with the same mappings as the specified map,
102: * sorted according to the keys's natural order
103: *
104: * @param map the map whose mappings are to be copied
105: */
106: public FastTreeMap(Map map) {
107: super ();
108: this .map = new TreeMap(map);
109: }
110:
111: /**
112: * Construct a new map with the same mappings as the specified map,
113: * sorted according to the same ordering
114: *
115: * @param map the map whose mappings are to be copied
116: */
117: public FastTreeMap(SortedMap map) {
118: super ();
119: this .map = new TreeMap(map);
120: }
121:
122: // Property access
123: // ----------------------------------------------------------------------
124:
125: /**
126: * Returns true if this map is operating in fast mode.
127: *
128: * @return true if this map is operating in fast mode
129: */
130: public boolean getFast() {
131: return (this .fast);
132: }
133:
134: /**
135: * Sets whether this map is operating in fast mode.
136: *
137: * @param fast true if this map should operate in fast mode
138: */
139: public void setFast(boolean fast) {
140: this .fast = fast;
141: }
142:
143: // Map access
144: // ----------------------------------------------------------------------
145: // These methods can forward straight to the wrapped Map in 'fast' mode.
146: // (because they are query methods)
147:
148: /**
149: * Return the value to which this map maps the specified key. Returns
150: * <code>null</code> if the map contains no mapping for this key, or if
151: * there is a mapping with a value of <code>null</code>. Use the
152: * <code>containsKey()</code> method to disambiguate these cases.
153: *
154: * @param key the key whose value is to be returned
155: * @return the value mapped to that key, or null
156: */
157: public Object get(Object key) {
158: if (fast) {
159: return (map.get(key));
160: } else {
161: synchronized (map) {
162: return (map.get(key));
163: }
164: }
165: }
166:
167: /**
168: * Return the number of key-value mappings in this map.
169: *
170: * @return the current size of the map
171: */
172: public int size() {
173: if (fast) {
174: return (map.size());
175: } else {
176: synchronized (map) {
177: return (map.size());
178: }
179: }
180: }
181:
182: /**
183: * Return <code>true</code> if this map contains no mappings.
184: *
185: * @return is the map currently empty
186: */
187: public boolean isEmpty() {
188: if (fast) {
189: return (map.isEmpty());
190: } else {
191: synchronized (map) {
192: return (map.isEmpty());
193: }
194: }
195: }
196:
197: /**
198: * Return <code>true</code> if this map contains a mapping for the
199: * specified key.
200: *
201: * @param key the key to be searched for
202: * @return true if the map contains the key
203: */
204: public boolean containsKey(Object key) {
205: if (fast) {
206: return (map.containsKey(key));
207: } else {
208: synchronized (map) {
209: return (map.containsKey(key));
210: }
211: }
212: }
213:
214: /**
215: * Return <code>true</code> if this map contains one or more keys mapping
216: * to the specified value.
217: *
218: * @param value the value to be searched for
219: * @return true if the map contains the value
220: */
221: public boolean containsValue(Object value) {
222: if (fast) {
223: return (map.containsValue(value));
224: } else {
225: synchronized (map) {
226: return (map.containsValue(value));
227: }
228: }
229: }
230:
231: /**
232: * Return the comparator used to order this map, or <code>null</code>
233: * if this map uses its keys' natural order.
234: *
235: * @return the comparator used to order the map, or null if natural order
236: */
237: public Comparator comparator() {
238: if (fast) {
239: return (map.comparator());
240: } else {
241: synchronized (map) {
242: return (map.comparator());
243: }
244: }
245: }
246:
247: /**
248: * Return the first (lowest) key currently in this sorted map.
249: *
250: * @return the first key in the map
251: */
252: public Object firstKey() {
253: if (fast) {
254: return (map.firstKey());
255: } else {
256: synchronized (map) {
257: return (map.firstKey());
258: }
259: }
260: }
261:
262: /**
263: * Return the last (highest) key currently in this sorted map.
264: *
265: * @return the last key in the map
266: */
267: public Object lastKey() {
268: if (fast) {
269: return (map.lastKey());
270: } else {
271: synchronized (map) {
272: return (map.lastKey());
273: }
274: }
275: }
276:
277: // Map modification
278: // ----------------------------------------------------------------------
279: // These methods perform special behaviour in 'fast' mode.
280: // The map is cloned, updated and then assigned back.
281: // See the comments at the top as to why this won't always work.
282:
283: /**
284: * Associate the specified value with the specified key in this map.
285: * If the map previously contained a mapping for this key, the old
286: * value is replaced and returned.
287: *
288: * @param key the key with which the value is to be associated
289: * @param value the value to be associated with this key
290: * @return the value previously mapped to the key, or null
291: */
292: public Object put(Object key, Object value) {
293: if (fast) {
294: synchronized (this ) {
295: TreeMap temp = (TreeMap) map.clone();
296: Object result = temp.put(key, value);
297: map = temp;
298: return (result);
299: }
300: } else {
301: synchronized (map) {
302: return (map.put(key, value));
303: }
304: }
305: }
306:
307: /**
308: * Copy all of the mappings from the specified map to this one, replacing
309: * any mappings with the same keys.
310: *
311: * @param in the map whose mappings are to be copied
312: */
313: public void putAll(Map in) {
314: if (fast) {
315: synchronized (this ) {
316: TreeMap temp = (TreeMap) map.clone();
317: temp.putAll(in);
318: map = temp;
319: }
320: } else {
321: synchronized (map) {
322: map.putAll(in);
323: }
324: }
325: }
326:
327: /**
328: * Remove any mapping for this key, and return any previously
329: * mapped value.
330: *
331: * @param key the key whose mapping is to be removed
332: * @return the value removed, or null
333: */
334: public Object remove(Object key) {
335: if (fast) {
336: synchronized (this ) {
337: TreeMap temp = (TreeMap) map.clone();
338: Object result = temp.remove(key);
339: map = temp;
340: return (result);
341: }
342: } else {
343: synchronized (map) {
344: return (map.remove(key));
345: }
346: }
347: }
348:
349: /**
350: * Remove all mappings from this map.
351: */
352: public void clear() {
353: if (fast) {
354: synchronized (this ) {
355: map = new TreeMap();
356: }
357: } else {
358: synchronized (map) {
359: map.clear();
360: }
361: }
362: }
363:
364: // Basic object methods
365: // ----------------------------------------------------------------------
366:
367: /**
368: * Compare the specified object with this list for equality. This
369: * implementation uses exactly the code that is used to define the
370: * list equals function in the documentation for the
371: * <code>Map.equals</code> method.
372: *
373: * @param o the object to be compared to this list
374: * @return true if the two maps are equal
375: */
376: public boolean equals(Object o) {
377: // Simple tests that require no synchronization
378: if (o == this ) {
379: return (true);
380: } else if (!(o instanceof Map)) {
381: return (false);
382: }
383: Map mo = (Map) o;
384:
385: // Compare the two maps for equality
386: if (fast) {
387: if (mo.size() != map.size()) {
388: return (false);
389: }
390: Iterator i = map.entrySet().iterator();
391: while (i.hasNext()) {
392: Map.Entry e = (Map.Entry) i.next();
393: Object key = e.getKey();
394: Object value = e.getValue();
395: if (value == null) {
396: if (!(mo.get(key) == null && mo.containsKey(key))) {
397: return (false);
398: }
399: } else {
400: if (!value.equals(mo.get(key))) {
401: return (false);
402: }
403: }
404: }
405: return (true);
406: } else {
407: synchronized (map) {
408: if (mo.size() != map.size()) {
409: return (false);
410: }
411: Iterator i = map.entrySet().iterator();
412: while (i.hasNext()) {
413: Map.Entry e = (Map.Entry) i.next();
414: Object key = e.getKey();
415: Object value = e.getValue();
416: if (value == null) {
417: if (!(mo.get(key) == null && mo
418: .containsKey(key))) {
419: return (false);
420: }
421: } else {
422: if (!value.equals(mo.get(key))) {
423: return (false);
424: }
425: }
426: }
427: return (true);
428: }
429: }
430: }
431:
432: /**
433: * Return the hash code value for this map. This implementation uses
434: * exactly the code that is used to define the list hash function in the
435: * documentation for the <code>Map.hashCode</code> method.
436: *
437: * @return a suitable integer hash code
438: */
439: public int hashCode() {
440: if (fast) {
441: int h = 0;
442: Iterator i = map.entrySet().iterator();
443: while (i.hasNext()) {
444: h += i.next().hashCode();
445: }
446: return (h);
447: } else {
448: synchronized (map) {
449: int h = 0;
450: Iterator i = map.entrySet().iterator();
451: while (i.hasNext()) {
452: h += i.next().hashCode();
453: }
454: return (h);
455: }
456: }
457: }
458:
459: /**
460: * Return a shallow copy of this <code>FastTreeMap</code> instance.
461: * The keys and values themselves are not copied.
462: *
463: * @return a clone of this map
464: */
465: public Object clone() {
466: FastTreeMap results = null;
467: if (fast) {
468: results = new FastTreeMap(map);
469: } else {
470: synchronized (map) {
471: results = new FastTreeMap(map);
472: }
473: }
474: results.setFast(getFast());
475: return (results);
476: }
477:
478: // Sub map views
479: // ----------------------------------------------------------------------
480:
481: /**
482: * Return a view of the portion of this map whose keys are strictly
483: * less than the specified key.
484: *
485: * @param key Key higher than any in the returned map
486: * @return a head map
487: */
488: public SortedMap headMap(Object key) {
489: if (fast) {
490: return (map.headMap(key));
491: } else {
492: synchronized (map) {
493: return (map.headMap(key));
494: }
495: }
496: }
497:
498: /**
499: * Return a view of the portion of this map whose keys are in the
500: * range fromKey (inclusive) to toKey (exclusive).
501: *
502: * @param fromKey Lower limit of keys for the returned map
503: * @param toKey Upper limit of keys for the returned map
504: * @return a sub map
505: */
506: public SortedMap subMap(Object fromKey, Object toKey) {
507: if (fast) {
508: return (map.subMap(fromKey, toKey));
509: } else {
510: synchronized (map) {
511: return (map.subMap(fromKey, toKey));
512: }
513: }
514: }
515:
516: /**
517: * Return a view of the portion of this map whose keys are greater than
518: * or equal to the specified key.
519: *
520: * @param key Key less than or equal to any in the returned map
521: * @return a tail map
522: */
523: public SortedMap tailMap(Object key) {
524: if (fast) {
525: return (map.tailMap(key));
526: } else {
527: synchronized (map) {
528: return (map.tailMap(key));
529: }
530: }
531: }
532:
533: // Map views
534: // ----------------------------------------------------------------------
535:
536: /**
537: * Return a collection view of the mappings contained in this map. Each
538: * element in the returned collection is a <code>Map.Entry</code>.
539: */
540: public Set entrySet() {
541: return new EntrySet();
542: }
543:
544: /**
545: * Return a set view of the keys contained in this map.
546: */
547: public Set keySet() {
548: return new KeySet();
549: }
550:
551: /**
552: * Return a collection view of the values contained in this map.
553: */
554: public Collection values() {
555: return new Values();
556: }
557:
558: // Map view inner classes
559: // ----------------------------------------------------------------------
560:
561: /**
562: * Abstract collection implementation shared by keySet(), values() and entrySet().
563: */
564: private abstract class CollectionView implements Collection {
565:
566: public CollectionView() {
567: }
568:
569: protected abstract Collection get(Map map);
570:
571: protected abstract Object iteratorNext(Map.Entry entry);
572:
573: public void clear() {
574: if (fast) {
575: synchronized (FastTreeMap.this ) {
576: map = new TreeMap();
577: }
578: } else {
579: synchronized (map) {
580: get(map).clear();
581: }
582: }
583: }
584:
585: public boolean remove(Object o) {
586: if (fast) {
587: synchronized (FastTreeMap.this ) {
588: TreeMap temp = (TreeMap) map.clone();
589: boolean r = get(temp).remove(o);
590: map = temp;
591: return r;
592: }
593: } else {
594: synchronized (map) {
595: return get(map).remove(o);
596: }
597: }
598: }
599:
600: public boolean removeAll(Collection o) {
601: if (fast) {
602: synchronized (FastTreeMap.this ) {
603: TreeMap temp = (TreeMap) map.clone();
604: boolean r = get(temp).removeAll(o);
605: map = temp;
606: return r;
607: }
608: } else {
609: synchronized (map) {
610: return get(map).removeAll(o);
611: }
612: }
613: }
614:
615: public boolean retainAll(Collection o) {
616: if (fast) {
617: synchronized (FastTreeMap.this ) {
618: TreeMap temp = (TreeMap) map.clone();
619: boolean r = get(temp).retainAll(o);
620: map = temp;
621: return r;
622: }
623: } else {
624: synchronized (map) {
625: return get(map).retainAll(o);
626: }
627: }
628: }
629:
630: public int size() {
631: if (fast) {
632: return get(map).size();
633: } else {
634: synchronized (map) {
635: return get(map).size();
636: }
637: }
638: }
639:
640: public boolean isEmpty() {
641: if (fast) {
642: return get(map).isEmpty();
643: } else {
644: synchronized (map) {
645: return get(map).isEmpty();
646: }
647: }
648: }
649:
650: public boolean contains(Object o) {
651: if (fast) {
652: return get(map).contains(o);
653: } else {
654: synchronized (map) {
655: return get(map).contains(o);
656: }
657: }
658: }
659:
660: public boolean containsAll(Collection o) {
661: if (fast) {
662: return get(map).containsAll(o);
663: } else {
664: synchronized (map) {
665: return get(map).containsAll(o);
666: }
667: }
668: }
669:
670: public Object[] toArray(Object[] o) {
671: if (fast) {
672: return get(map).toArray(o);
673: } else {
674: synchronized (map) {
675: return get(map).toArray(o);
676: }
677: }
678: }
679:
680: public Object[] toArray() {
681: if (fast) {
682: return get(map).toArray();
683: } else {
684: synchronized (map) {
685: return get(map).toArray();
686: }
687: }
688: }
689:
690: public boolean equals(Object o) {
691: if (o == this )
692: return true;
693: if (fast) {
694: return get(map).equals(o);
695: } else {
696: synchronized (map) {
697: return get(map).equals(o);
698: }
699: }
700: }
701:
702: public int hashCode() {
703: if (fast) {
704: return get(map).hashCode();
705: } else {
706: synchronized (map) {
707: return get(map).hashCode();
708: }
709: }
710: }
711:
712: public boolean add(Object o) {
713: throw new UnsupportedOperationException();
714: }
715:
716: public boolean addAll(Collection c) {
717: throw new UnsupportedOperationException();
718: }
719:
720: public Iterator iterator() {
721: return new CollectionViewIterator();
722: }
723:
724: private class CollectionViewIterator implements Iterator {
725:
726: private Map expected;
727: private Map.Entry lastReturned = null;
728: private Iterator iterator;
729:
730: public CollectionViewIterator() {
731: this .expected = map;
732: this .iterator = expected.entrySet().iterator();
733: }
734:
735: public boolean hasNext() {
736: if (expected != map) {
737: throw new ConcurrentModificationException();
738: }
739: return iterator.hasNext();
740: }
741:
742: public Object next() {
743: if (expected != map) {
744: throw new ConcurrentModificationException();
745: }
746: lastReturned = (Map.Entry) iterator.next();
747: return iteratorNext(lastReturned);
748: }
749:
750: public void remove() {
751: if (lastReturned == null) {
752: throw new IllegalStateException();
753: }
754: if (fast) {
755: synchronized (FastTreeMap.this ) {
756: if (expected != map) {
757: throw new ConcurrentModificationException();
758: }
759: FastTreeMap.this .remove(lastReturned.getKey());
760: lastReturned = null;
761: expected = map;
762: }
763: } else {
764: iterator.remove();
765: lastReturned = null;
766: }
767: }
768: }
769: }
770:
771: /**
772: * Set implementation over the keys of the FastTreeMap
773: */
774: private class KeySet extends CollectionView implements Set {
775:
776: protected Collection get(Map map) {
777: return map.keySet();
778: }
779:
780: protected Object iteratorNext(Map.Entry entry) {
781: return entry.getKey();
782: }
783:
784: }
785:
786: /**
787: * Collection implementation over the values of the FastTreeMap
788: */
789: private class Values extends CollectionView {
790:
791: protected Collection get(Map map) {
792: return map.values();
793: }
794:
795: protected Object iteratorNext(Map.Entry entry) {
796: return entry.getValue();
797: }
798: }
799:
800: /**
801: * Set implementation over the entries of the FastTreeMap
802: */
803: private class EntrySet extends CollectionView implements Set {
804:
805: protected Collection get(Map map) {
806: return map.entrySet();
807: }
808:
809: protected Object iteratorNext(Map.Entry entry) {
810: return entry;
811: }
812:
813: }
814:
815: }
|