Java > Open Source Codes > org > apache > commons > collections > FastTreeMap


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

A to Z: JavaDoc & Examples

---

Daily Java News & Articles

---

Open Source Projects

---

Open Source Codes

---

Free Computer Books

---

Remove Frame

---

Popular Tags