📄 doubleorderedmap.java
字号:
/* * Copyright 1999-2004 The Apache Software Foundation * * Licensed 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.AbstractCollection;
import java.util.AbstractMap;
import java.util.AbstractSet;
import java.util.Collection;
import java.util.ConcurrentModificationException;
import java.util.Iterator;
import java.util.Map;
import java.util.NoSuchElementException;
import java.util.Set;
/**
* Red-Black tree-based implementation of Map. This class guarantees
* that the map will be in both ascending key order and ascending
* value order, sorted according to the natural order for the key's
* and value's classes.<p>
*
* This Map is intended for applications that need to be able to look
* up a key-value pairing by either key or value, and need to do so
* with equal efficiency.<p>
*
* While that goal could be accomplished by taking a pair of TreeMaps
* and redirecting requests to the appropriate TreeMap (e.g.,
* containsKey would be directed to the TreeMap that maps values to
* keys, containsValue would be directed to the TreeMap that maps keys
* to values), there are problems with that implementation,
* particularly when trying to keep the two TreeMaps synchronized with
* each other. And if the data contained in the TreeMaps is large, the
* cost of redundant storage becomes significant.<p>
*
* This solution keeps the data properly synchronized and minimizes
* the data storage. The red-black algorithm is based on TreeMap's,
* but has been modified to simultaneously map a tree node by key and
* by value. This doubles the cost of put operations (but so does
* using two TreeMaps), and nearly doubles the cost of remove
* operations (there is a savings in that the lookup of the node to be
* removed only has to be performed once). And since only one node
* contains the key and value, storage is significantly less than that
* required by two TreeMaps.<p>
*
* There are some limitations placed on data kept in this Map. The
* biggest one is this:<p>
*
* When performing a put operation, neither the key nor the value may
* already exist in the Map. In the java.util Map implementations
* (HashMap, TreeMap), you can perform a put with an already mapped
* key, and neither cares about duplicate values at all ... but this
* implementation's put method with throw an IllegalArgumentException
* if either the key or the value is already in the Map.<p>
*
* Obviously, that same restriction (and consequence of failing to
* heed that restriction) applies to the putAll method.<p>
*
* The Map.Entry instances returned by the appropriate methods will
* not allow setValue() and will throw an
* UnsupportedOperationException on attempts to call that method.<p>
*
* New methods are added to take advantage of the fact that values are
* kept sorted independently of their keys:<p>
*
* Object getKeyForValue(Object value) is the opposite of get; it
* takes a value and returns its key, if any.<p>
*
* Object removeValue(Object value) finds and removes the specified
* value and returns the now un-used key.<p>
*
* Set entrySetByValue() returns the Map.Entry's in a Set whose
* iterator will iterate over the Map.Entry's in ascending order by
* their corresponding values.<p>
*
* Set keySetByValue() returns the keys in a Set whose iterator will
* iterate over the keys in ascending order by their corresponding
* values.<p>
*
* Collection valuesByValue() returns the values in a Collection whose
* iterator will iterate over the values in ascending order.<p>
*
* @since 2.0
* @author Marc Johnson (marcj at users dot sourceforge dot net)
*/
// final for performance
public final class DoubleOrderedMap extends AbstractMap {
private Node[] rootNode = new Node[]{ null,
null };
private int nodeCount = 0;
private int modifications = 0;
private Set[] setOfKeys = new Set[]{ null,
null };
private Set[] setOfEntries = new Set[]{ null,
null };
private Collection[] collectionOfValues = new Collection[]{
null,
null };
private static final int KEY = 0;
private static final int VALUE = 1;
private static final int SUM_OF_INDICES = KEY + VALUE;
private static final int FIRST_INDEX = 0;
private static final int NUMBER_OF_INDICES = 2;
private static final String[] dataName = new String[]{ "key",
"value"
};
/**
* Construct a new DoubleOrderedMap
*/
public DoubleOrderedMap() {}
/**
* Constructs a new DoubleOrderedMap from an existing Map, with keys and
* values sorted
*
* @param map the map whose mappings are to be placed in this map.
*
* @exception ClassCastException if the keys in the map are not
* Comparable, or are not mutually
* comparable; also if the values in
* the map are not Comparable, or
* are not mutually Comparable
* @exception NullPointerException if any key or value in the map
* is null
* @exception IllegalArgumentException if there are duplicate keys
* or duplicate values in the
* map
*/
public DoubleOrderedMap(final Map map)
throws ClassCastException, NullPointerException,
IllegalArgumentException {
putAll(map);
}
/**
* Returns the key to which this map maps the specified value.
* Returns null if the map contains no mapping for this value.
*
* @param value value whose associated key is to be returned.
*
* @return the key to which this map maps the specified value, or
* null if the map contains no mapping for this value.
*
* @exception ClassCastException if the value is of an
* inappropriate type for this map.
* @exception NullPointerException if the value is null
*/
public Object getKeyForValue(final Object value)
throws ClassCastException, NullPointerException {
return doGet((Comparable) value, VALUE);
}
/**
* Removes the mapping for this value from this map if present
*
* @param value value whose mapping is to be removed from the map.
*
* @return previous key associated with specified value, or null
* if there was no mapping for value.
*/
public Object removeValue(final Object value) {
return doRemove((Comparable) value, VALUE);
}
/**
* Returns a set view of the mappings contained in this map. Each
* element in the returned set is a Map.Entry. The set is backed
* by the map, so changes to the map are reflected in the set, and
* vice-versa. If the map is modified while an iteration over the
* set is in progress, the results of the iteration are
* undefined. The set supports element removal, which removes the
* corresponding mapping from the map, via the Iterator.remove,
* Set.remove, removeAll, retainAll and clear operations. It does
* not support the add or addAll operations.<p>
*
* The difference between this method and entrySet is that
* entrySet's iterator() method returns an iterator that iterates
* over the mappings in ascending order by key. This method's
* iterator method iterates over the mappings in ascending order
* by value.
*
* @return a set view of the mappings contained in this map.
*/
public Set entrySetByValue() {
if (setOfEntries[VALUE] == null) {
setOfEntries[VALUE] = new AbstractSet() {
public Iterator iterator() {
return new DoubleOrderedMapIterator(VALUE) {
protected Object doGetNext() {
return lastReturnedNode;
}
};
}
public boolean contains(Object o) {
if (!(o instanceof Map.Entry)) {
return false;
}
Map.Entry entry = (Map.Entry) o;
Object key = entry.getKey();
Node node = lookup((Comparable) entry.getValue(),
VALUE);
return (node != null) && node.getData(KEY).equals(key);
}
public boolean remove(Object o) {
if (!(o instanceof Map.Entry)) {
return false;
}
Map.Entry entry = (Map.Entry) o;
Object key = entry.getKey();
Node node = lookup((Comparable) entry.getValue(),
VALUE);
if ((node != null) && node.getData(KEY).equals(key)) {
doRedBlackDelete(node);
return true;
}
return false;
}
public int size() {
return DoubleOrderedMap.this.size();
}
public void clear() {
DoubleOrderedMap.this.clear();
}
};
}
return setOfEntries[VALUE];
}
/**
* Returns a set view of the keys contained in this map. The set
* is backed by the map, so changes to the map are reflected in
* the set, and vice-versa. If the map is modified while an
* iteration over the set is in progress, the results of the
* iteration are undefined. The set supports element removal,
* which removes the corresponding mapping from the map, via the
* Iterator.remove, Set.remove, removeAll, retainAll, and clear
* operations. It does not support the add or addAll
* operations.<p>
*
* The difference between this method and keySet is that keySet's
* iterator() method returns an iterator that iterates over the
* keys in ascending order by key. This method's iterator method
* iterates over the keys in ascending order by value.
*
* @return a set view of the keys contained in this map.
*/
public Set keySetByValue() {
if (setOfKeys[VALUE] == null) {
setOfKeys[VALUE] = new AbstractSet() {
public Iterator iterator() {
return new DoubleOrderedMapIterator(VALUE) {
protected Object doGetNext() {
return lastReturnedNode.getData(KEY);
}
};
}
public int size() {
return DoubleOrderedMap.this.size();
}
public boolean contains(Object o) {
return containsKey(o);
}
public boolean remove(Object o) {
int oldnodeCount = nodeCount;
DoubleOrderedMap.this.remove(o);
return nodeCount != oldnodeCount;
}
public void clear() {
DoubleOrderedMap.this.clear();
}
};
}
return setOfKeys[VALUE];
}
/**
* Returns a collection view of the values contained in this
* map. The collection is backed by the map, so changes to the map
* are reflected in the collection, and vice-versa. If the map is
* modified while an iteration over the collection is in progress,
* the results of the iteration are undefined. The collection
* supports element removal, which removes the corresponding
* mapping from the map, via the Iterator.remove,
* Collection.remove, removeAll, retainAll and clear operations.
* It does not support the add or addAll operations.<p>
*
* The difference between this method and values is that values's
* iterator() method returns an iterator that iterates over the
* values in ascending order by key. This method's iterator method
* iterates over the values in ascending order by key.
*
* @return a collection view of the values contained in this map.
*/
public Collection valuesByValue() {
if (collectionOfValues[VALUE] == null) {
collectionOfValues[VALUE] = new AbstractCollection() {
public Iterator iterator() {
return new DoubleOrderedMapIterator(VALUE) {
protected Object doGetNext() {
return lastReturnedNode.getData(VALUE);
}
};
}
public int size() {
return DoubleOrderedMap.this.size();
}
public boolean contains(Object o) {
return containsValue(o);
}
public boolean remove(Object o) {
int oldnodeCount = nodeCount;
removeValue(o);
return nodeCount != oldnodeCount;
}
public boolean removeAll(Collection c) {
boolean modified = false;
Iterator iter = c.iterator();
while (iter.hasNext()) {
if (removeValue(iter.next()) != null) {
modified = true;
}
}
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -