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 }