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