| /* |
| * Licensed to the Apache Software Foundation (ASF) under one or more |
| * contributor license agreements. See the NOTICE file distributed with |
| * this work for additional information regarding copyright ownership. |
| * The ASF licenses this file to You under the Apache License, Version 2.0 |
| * (the "License"); you may not use this file except in compliance with |
| * the License. You may obtain a copy of the License at |
| * |
| * http://www.apache.org/licenses/LICENSE-2.0 |
| * |
| * Unless required by applicable law or agreed to in writing, software |
| * distributed under the License is distributed on an "AS IS" BASIS, |
| * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| * See the License for the specific language governing permissions and |
| * limitations under the License. |
| */ |
| package org.apache.commons.collections; |
| |
| import java.util.Collection; |
| import java.util.Comparator; |
| import java.util.ConcurrentModificationException; |
| import java.util.Iterator; |
| import java.util.Map; |
| import java.util.Set; |
| import java.util.SortedMap; |
| import java.util.TreeMap; |
| |
| /** |
| * <p>A customized implementation of <code>java.util.TreeMap</code> designed |
| * to operate in a multithreaded environment where the large majority of |
| * method calls are read-only, instead of structural changes. When operating |
| * in "fast" mode, read calls are non-synchronized and write calls perform the |
| * following steps:</p> |
| * <ul> |
| * <li>Clone the existing collection |
| * <li>Perform the modification on the clone |
| * <li>Replace the existing collection with the (modified) clone |
| * </ul> |
| * <p>When first created, objects of this class default to "slow" mode, where |
| * all accesses of any type are synchronized but no cloning takes place. This |
| * is appropriate for initially populating the collection, followed by a switch |
| * to "fast" mode (by calling <code>setFast(true)</code>) after initialization |
| * is complete.</p> |
| * |
| * <p><strong>NOTE</strong>: If you are creating and accessing a |
| * <code>TreeMap</code> only within a single thread, you should use |
| * <code>java.util.TreeMap</code> directly (with no synchronization), for |
| * maximum performance.</p> |
| * |
| * <p><strong>NOTE</strong>: <i>This class is not cross-platform. |
| * Using it may cause unexpected failures on some architectures.</i> |
| * It suffers from the same problems as the double-checked locking idiom. |
| * In particular, the instruction that clones the internal collection and the |
| * instruction that sets the internal reference to the clone can be executed |
| * or perceived out-of-order. This means that any read operation might fail |
| * unexpectedly, as it may be reading the state of the internal collection |
| * before the internal collection is fully formed. |
| * For more information on the double-checked locking idiom, see the |
| * <a href="http://www.cs.umd.edu/~pugh/java/memoryModel/DoubleCheckedLocking.html"> |
| * Double-Checked Locking Idiom Is Broken Declaration</a>.</p> |
| * |
| * @since Commons Collections 1.0 |
| * @version $Revision$ $Date$ |
| * |
| * @author Craig R. McClanahan |
| * @author Stephen Colebourne |
| */ |
| public class FastTreeMap extends TreeMap { |
| |
| /** |
| * The underlying map we are managing. |
| */ |
| protected TreeMap map = null; |
| |
| /** |
| * Are we operating in "fast" mode? |
| */ |
| protected boolean fast = false; |
| |
| |
| // Constructors |
| // ---------------------------------------------------------------------- |
| |
| /** |
| * Construct a an empty map. |
| */ |
| public FastTreeMap() { |
| super(); |
| this.map = new TreeMap(); |
| } |
| |
| /** |
| * Construct an empty map with the specified comparator. |
| * |
| * @param comparator the comparator to use for ordering tree elements |
| */ |
| public FastTreeMap(Comparator comparator) { |
| super(); |
| this.map = new TreeMap(comparator); |
| } |
| |
| /** |
| * Construct a new map with the same mappings as the specified map, |
| * sorted according to the keys's natural order |
| * |
| * @param map the map whose mappings are to be copied |
| */ |
| public FastTreeMap(Map map) { |
| super(); |
| this.map = new TreeMap(map); |
| } |
| |
| /** |
| * Construct a new map with the same mappings as the specified map, |
| * sorted according to the same ordering |
| * |
| * @param map the map whose mappings are to be copied |
| */ |
| public FastTreeMap(SortedMap map) { |
| super(); |
| this.map = new TreeMap(map); |
| } |
| |
| |
| // Property access |
| // ---------------------------------------------------------------------- |
| |
| /** |
| * Returns true if this map is operating in fast mode. |
| * |
| * @return true if this map is operating in fast mode |
| */ |
| public boolean getFast() { |
| return (this.fast); |
| } |
| |
| /** |
| * Sets whether this map is operating in fast mode. |
| * |
| * @param fast true if this map should operate in fast mode |
| */ |
| public void setFast(boolean fast) { |
| this.fast = fast; |
| } |
| |
| |
| // Map access |
| // ---------------------------------------------------------------------- |
| // These methods can forward straight to the wrapped Map in 'fast' mode. |
| // (because they are query methods) |
| |
| /** |
| * Return the value to which this map maps the specified key. Returns |
| * <code>null</code> if the map contains no mapping for this key, or if |
| * there is a mapping with a value of <code>null</code>. Use the |
| * <code>containsKey()</code> method to disambiguate these cases. |
| * |
| * @param key the key whose value is to be returned |
| * @return the value mapped to that key, or null |
| */ |
| public Object get(Object key) { |
| if (fast) { |
| return (map.get(key)); |
| } else { |
| synchronized (map) { |
| return (map.get(key)); |
| } |
| } |
| } |
| |
| /** |
| * Return the number of key-value mappings in this map. |
| * |
| * @return the current size of the map |
| */ |
| public int size() { |
| if (fast) { |
| return (map.size()); |
| } else { |
| synchronized (map) { |
| return (map.size()); |
| } |
| } |
| } |
| |
| /** |
| * Return <code>true</code> if this map contains no mappings. |
| * |
| * @return is the map currently empty |
| */ |
| public boolean isEmpty() { |
| if (fast) { |
| return (map.isEmpty()); |
| } else { |
| synchronized (map) { |
| return (map.isEmpty()); |
| } |
| } |
| } |
| |
| /** |
| * Return <code>true</code> if this map contains a mapping for the |
| * specified key. |
| * |
| * @param key the key to be searched for |
| * @return true if the map contains the key |
| */ |
| public boolean containsKey(Object key) { |
| if (fast) { |
| return (map.containsKey(key)); |
| } else { |
| synchronized (map) { |
| return (map.containsKey(key)); |
| } |
| } |
| } |
| |
| /** |
| * Return <code>true</code> if this map contains one or more keys mapping |
| * to the specified value. |
| * |
| * @param value the value to be searched for |
| * @return true if the map contains the value |
| */ |
| public boolean containsValue(Object value) { |
| if (fast) { |
| return (map.containsValue(value)); |
| } else { |
| synchronized (map) { |
| return (map.containsValue(value)); |
| } |
| } |
| } |
| |
| /** |
| * Return the comparator used to order this map, or <code>null</code> |
| * if this map uses its keys' natural order. |
| * |
| * @return the comparator used to order the map, or null if natural order |
| */ |
| public Comparator comparator() { |
| if (fast) { |
| return (map.comparator()); |
| } else { |
| synchronized (map) { |
| return (map.comparator()); |
| } |
| } |
| } |
| |
| /** |
| * Return the first (lowest) key currently in this sorted map. |
| * |
| * @return the first key in the map |
| */ |
| public Object firstKey() { |
| if (fast) { |
| return (map.firstKey()); |
| } else { |
| synchronized (map) { |
| return (map.firstKey()); |
| } |
| } |
| } |
| |
| /** |
| * Return the last (highest) key currently in this sorted map. |
| * |
| * @return the last key in the map |
| */ |
| public Object lastKey() { |
| if (fast) { |
| return (map.lastKey()); |
| } else { |
| synchronized (map) { |
| return (map.lastKey()); |
| } |
| } |
| } |
| |
| |
| // Map modification |
| // ---------------------------------------------------------------------- |
| // These methods perform special behaviour in 'fast' mode. |
| // The map is cloned, updated and then assigned back. |
| // See the comments at the top as to why this won't always work. |
| |
| /** |
| * Associate the specified value with the specified key in this map. |
| * If the map previously contained a mapping for this key, the old |
| * value is replaced and returned. |
| * |
| * @param key the key with which the value is to be associated |
| * @param value the value to be associated with this key |
| * @return the value previously mapped to the key, or null |
| */ |
| public Object put(Object key, Object value) { |
| if (fast) { |
| synchronized (this) { |
| TreeMap temp = (TreeMap) map.clone(); |
| Object result = temp.put(key, value); |
| map = temp; |
| return (result); |
| } |
| } else { |
| synchronized (map) { |
| return (map.put(key, value)); |
| } |
| } |
| } |
| |
| /** |
| * Copy all of the mappings from the specified map to this one, replacing |
| * any mappings with the same keys. |
| * |
| * @param in the map whose mappings are to be copied |
| */ |
| public void putAll(Map in) { |
| if (fast) { |
| synchronized (this) { |
| TreeMap temp = (TreeMap) map.clone(); |
| temp.putAll(in); |
| map = temp; |
| } |
| } else { |
| synchronized (map) { |
| map.putAll(in); |
| } |
| } |
| } |
| |
| /** |
| * Remove any mapping for this key, and return any previously |
| * mapped value. |
| * |
| * @param key the key whose mapping is to be removed |
| * @return the value removed, or null |
| */ |
| public Object remove(Object key) { |
| if (fast) { |
| synchronized (this) { |
| TreeMap temp = (TreeMap) map.clone(); |
| Object result = temp.remove(key); |
| map = temp; |
| return (result); |
| } |
| } else { |
| synchronized (map) { |
| return (map.remove(key)); |
| } |
| } |
| } |
| |
| /** |
| * Remove all mappings from this map. |
| */ |
| public void clear() { |
| if (fast) { |
| synchronized (this) { |
| map = new TreeMap(); |
| } |
| } else { |
| synchronized (map) { |
| map.clear(); |
| } |
| } |
| } |
| |
| |
| // Basic object methods |
| // ---------------------------------------------------------------------- |
| |
| /** |
| * Compare the specified object with this list for equality. This |
| * implementation uses exactly the code that is used to define the |
| * list equals function in the documentation for the |
| * <code>Map.equals</code> method. |
| * |
| * @param o the object to be compared to this list |
| * @return true if the two maps are equal |
| */ |
| public boolean equals(Object o) { |
| // Simple tests that require no synchronization |
| if (o == this) { |
| return (true); |
| } else if (!(o instanceof Map)) { |
| return (false); |
| } |
| Map mo = (Map) o; |
| |
| // Compare the two maps for equality |
| if (fast) { |
| if (mo.size() != map.size()) { |
| return (false); |
| } |
| Iterator i = map.entrySet().iterator(); |
| while (i.hasNext()) { |
| Map.Entry e = (Map.Entry) i.next(); |
| Object key = e.getKey(); |
| Object value = e.getValue(); |
| if (value == null) { |
| if (!(mo.get(key) == null && mo.containsKey(key))) { |
| return (false); |
| } |
| } else { |
| if (!value.equals(mo.get(key))) { |
| return (false); |
| } |
| } |
| } |
| return (true); |
| } else { |
| synchronized (map) { |
| if (mo.size() != map.size()) { |
| return (false); |
| } |
| Iterator i = map.entrySet().iterator(); |
| while (i.hasNext()) { |
| Map.Entry e = (Map.Entry) i.next(); |
| Object key = e.getKey(); |
| Object value = e.getValue(); |
| if (value == null) { |
| if (!(mo.get(key) == null && mo.containsKey(key))) { |
| return (false); |
| } |
| } else { |
| if (!value.equals(mo.get(key))) { |
| return (false); |
| } |
| } |
| } |
| return (true); |
| } |
| } |
| } |
| |
| /** |
| * Return the hash code value for this map. This implementation uses |
| * exactly the code that is used to define the list hash function in the |
| * documentation for the <code>Map.hashCode</code> method. |
| * |
| * @return a suitable integer hash code |
| */ |
| public int hashCode() { |
| if (fast) { |
| int h = 0; |
| Iterator i = map.entrySet().iterator(); |
| while (i.hasNext()) { |
| h += i.next().hashCode(); |
| } |
| return (h); |
| } else { |
| synchronized (map) { |
| int h = 0; |
| Iterator i = map.entrySet().iterator(); |
| while (i.hasNext()) { |
| h += i.next().hashCode(); |
| } |
| return (h); |
| } |
| } |
| } |
| |
| /** |
| * Return a shallow copy of this <code>FastTreeMap</code> instance. |
| * The keys and values themselves are not copied. |
| * |
| * @return a clone of this map |
| */ |
| public Object clone() { |
| FastTreeMap results = null; |
| if (fast) { |
| results = new FastTreeMap(map); |
| } else { |
| synchronized (map) { |
| results = new FastTreeMap(map); |
| } |
| } |
| results.setFast(getFast()); |
| return (results); |
| } |
| |
| |
| // Sub map views |
| // ---------------------------------------------------------------------- |
| |
| /** |
| * Return a view of the portion of this map whose keys are strictly |
| * less than the specified key. |
| * |
| * @param key Key higher than any in the returned map |
| * @return a head map |
| */ |
| public SortedMap headMap(Object key) { |
| if (fast) { |
| return (map.headMap(key)); |
| } else { |
| synchronized (map) { |
| return (map.headMap(key)); |
| } |
| } |
| } |
| |
| /** |
| * Return a view of the portion of this map whose keys are in the |
| * range fromKey (inclusive) to toKey (exclusive). |
| * |
| * @param fromKey Lower limit of keys for the returned map |
| * @param toKey Upper limit of keys for the returned map |
| * @return a sub map |
| */ |
| public SortedMap subMap(Object fromKey, Object toKey) { |
| if (fast) { |
| return (map.subMap(fromKey, toKey)); |
| } else { |
| synchronized (map) { |
| return (map.subMap(fromKey, toKey)); |
| } |
| } |
| } |
| |
| /** |
| * Return a view of the portion of this map whose keys are greater than |
| * or equal to the specified key. |
| * |
| * @param key Key less than or equal to any in the returned map |
| * @return a tail map |
| */ |
| public SortedMap tailMap(Object key) { |
| if (fast) { |
| return (map.tailMap(key)); |
| } else { |
| synchronized (map) { |
| return (map.tailMap(key)); |
| } |
| } |
| } |
| |
| |
| // Map views |
| // ---------------------------------------------------------------------- |
| |
| /** |
| * Return a collection view of the mappings contained in this map. Each |
| * element in the returned collection is a <code>Map.Entry</code>. |
| */ |
| public Set entrySet() { |
| return new EntrySet(); |
| } |
| |
| /** |
| * Return a set view of the keys contained in this map. |
| */ |
| public Set keySet() { |
| return new KeySet(); |
| } |
| |
| /** |
| * Return a collection view of the values contained in this map. |
| */ |
| public Collection values() { |
| return new Values(); |
| } |
| |
| // Map view inner classes |
| // ---------------------------------------------------------------------- |
| |
| /** |
| * Abstract collection implementation shared by keySet(), values() and entrySet(). |
| */ |
| private abstract class CollectionView implements Collection { |
| |
| public CollectionView() { |
| } |
| |
| protected abstract Collection get(Map map); |
| protected abstract Object iteratorNext(Map.Entry entry); |
| |
| |
| public void clear() { |
| if (fast) { |
| synchronized (FastTreeMap.this) { |
| map = new TreeMap(); |
| } |
| } else { |
| synchronized (map) { |
| get(map).clear(); |
| } |
| } |
| } |
| |
| public boolean remove(Object o) { |
| if (fast) { |
| synchronized (FastTreeMap.this) { |
| TreeMap temp = (TreeMap) map.clone(); |
| boolean r = get(temp).remove(o); |
| map = temp; |
| return r; |
| } |
| } else { |
| synchronized (map) { |
| return get(map).remove(o); |
| } |
| } |
| } |
| |
| public boolean removeAll(Collection o) { |
| if (fast) { |
| synchronized (FastTreeMap.this) { |
| TreeMap temp = (TreeMap) map.clone(); |
| boolean r = get(temp).removeAll(o); |
| map = temp; |
| return r; |
| } |
| } else { |
| synchronized (map) { |
| return get(map).removeAll(o); |
| } |
| } |
| } |
| |
| public boolean retainAll(Collection o) { |
| if (fast) { |
| synchronized (FastTreeMap.this) { |
| TreeMap temp = (TreeMap) map.clone(); |
| boolean r = get(temp).retainAll(o); |
| map = temp; |
| return r; |
| } |
| } else { |
| synchronized (map) { |
| return get(map).retainAll(o); |
| } |
| } |
| } |
| |
| public int size() { |
| if (fast) { |
| return get(map).size(); |
| } else { |
| synchronized (map) { |
| return get(map).size(); |
| } |
| } |
| } |
| |
| |
| public boolean isEmpty() { |
| if (fast) { |
| return get(map).isEmpty(); |
| } else { |
| synchronized (map) { |
| return get(map).isEmpty(); |
| } |
| } |
| } |
| |
| public boolean contains(Object o) { |
| if (fast) { |
| return get(map).contains(o); |
| } else { |
| synchronized (map) { |
| return get(map).contains(o); |
| } |
| } |
| } |
| |
| public boolean containsAll(Collection o) { |
| if (fast) { |
| return get(map).containsAll(o); |
| } else { |
| synchronized (map) { |
| return get(map).containsAll(o); |
| } |
| } |
| } |
| |
| public Object[] toArray(Object[] o) { |
| if (fast) { |
| return get(map).toArray(o); |
| } else { |
| synchronized (map) { |
| return get(map).toArray(o); |
| } |
| } |
| } |
| |
| public Object[] toArray() { |
| if (fast) { |
| return get(map).toArray(); |
| } else { |
| synchronized (map) { |
| return get(map).toArray(); |
| } |
| } |
| } |
| |
| |
| public boolean equals(Object o) { |
| if (o == this) return true; |
| if (fast) { |
| return get(map).equals(o); |
| } else { |
| synchronized (map) { |
| return get(map).equals(o); |
| } |
| } |
| } |
| |
| public int hashCode() { |
| if (fast) { |
| return get(map).hashCode(); |
| } else { |
| synchronized (map) { |
| return get(map).hashCode(); |
| } |
| } |
| } |
| |
| public boolean add(Object o) { |
| throw new UnsupportedOperationException(); |
| } |
| |
| public boolean addAll(Collection c) { |
| throw new UnsupportedOperationException(); |
| } |
| |
| public Iterator iterator() { |
| return new CollectionViewIterator(); |
| } |
| |
| private class CollectionViewIterator implements Iterator { |
| |
| private Map expected; |
| private Map.Entry lastReturned = null; |
| private Iterator iterator; |
| |
| public CollectionViewIterator() { |
| this.expected = map; |
| this.iterator = expected.entrySet().iterator(); |
| } |
| |
| public boolean hasNext() { |
| if (expected != map) { |
| throw new ConcurrentModificationException(); |
| } |
| return iterator.hasNext(); |
| } |
| |
| public Object next() { |
| if (expected != map) { |
| throw new ConcurrentModificationException(); |
| } |
| lastReturned = (Map.Entry)iterator.next(); |
| return iteratorNext(lastReturned); |
| } |
| |
| public void remove() { |
| if (lastReturned == null) { |
| throw new IllegalStateException(); |
| } |
| if (fast) { |
| synchronized (FastTreeMap.this) { |
| if (expected != map) { |
| throw new ConcurrentModificationException(); |
| } |
| FastTreeMap.this.remove(lastReturned.getKey()); |
| lastReturned = null; |
| expected = map; |
| } |
| } else { |
| iterator.remove(); |
| lastReturned = null; |
| } |
| } |
| } |
| } |
| |
| /** |
| * Set implementation over the keys of the FastTreeMap |
| */ |
| private class KeySet extends CollectionView implements Set { |
| |
| protected Collection get(Map map) { |
| return map.keySet(); |
| } |
| |
| protected Object iteratorNext(Map.Entry entry) { |
| return entry.getKey(); |
| } |
| |
| } |
| |
| /** |
| * Collection implementation over the values of the FastTreeMap |
| */ |
| private class Values extends CollectionView { |
| |
| protected Collection get(Map map) { |
| return map.values(); |
| } |
| |
| protected Object iteratorNext(Map.Entry entry) { |
| return entry.getValue(); |
| } |
| } |
| |
| /** |
| * Set implementation over the entries of the FastTreeMap |
| */ |
| private class EntrySet extends CollectionView implements Set { |
| |
| protected Collection get(Map map) { |
| return map.entrySet(); |
| } |
| |
| |
| protected Object iteratorNext(Map.Entry entry) { |
| return entry; |
| } |
| |
| } |
| |
| } |