📄 doubleorderedmap.java
字号:
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;
}
}
return modified;
}
public void clear() {
DoubleOrderedMap.this.clear();
}
};
}
return collectionOfValues[KEY];
}
/**
* 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.
* <p>
* 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.
* The setValue method is not supported on the Map Entry.
*
* @return a set view of the mappings contained in this map.
*/
public Set entrySet() {
if (setOfEntries[KEY] == null) {
setOfEntries[KEY] = new AbstractSet() {
public Iterator iterator() {
return new DoubleOrderedMapIterator(KEY) {
protected Object doGetNext() {
return lastReturnedNode;
}
};
}
public boolean contains(Object o) {
if (!(o instanceof Map.Entry)) {
return false;
}
Map.Entry entry = (Map.Entry) o;
Object value = entry.getValue();
Node node = lookup((Comparable) entry.getKey(),
KEY);
return (node != null)
&& node.getData(VALUE).equals(value);
}
public boolean remove(Object o) {
if (!(o instanceof Map.Entry)) {
return false;
}
Map.Entry entry = (Map.Entry) o;
Object value = entry.getValue();
Node node = lookup((Comparable) entry.getKey(),
KEY);
if ((node != null) && node.getData(VALUE).equals(value)) {
doRedBlackDelete(node);
return true;
}
return false;
}
public int size() {
return DoubleOrderedMap.this.size();
}
public void clear() {
DoubleOrderedMap.this.clear();
}
};
}
return setOfEntries[KEY];
}
/* ********** END implementation of Map ********** */
private abstract class DoubleOrderedMapIterator implements Iterator {
private int expectedModifications;
protected Node lastReturnedNode;
private Node nextNode;
private int iteratorType;
/**
* Constructor
*
* @param type
*/
DoubleOrderedMapIterator(final int type) {
iteratorType = type;
expectedModifications = DoubleOrderedMap.this.modifications;
lastReturnedNode = null;
nextNode = leastNode(rootNode[iteratorType],
iteratorType);
}
/**
* @return 'next', whatever that means for a given kind of
* DoubleOrderedMapIterator
*/
protected abstract Object doGetNext();
/* ********** START implementation of Iterator ********** */
/**
* @return true if the iterator has more elements.
*/
public final boolean hasNext() {
return nextNode != null;
}
/**
* @return the next element in the iteration.
*
* @throws NoSuchElementException if iteration has no more
* elements.
* @throws ConcurrentModificationException if the
* DoubleOrderedMap is
* modified behind
* the iterator's
* back
*/
public final Object next()
throws NoSuchElementException,
ConcurrentModificationException {
if (nextNode == null) {
throw new NoSuchElementException();
}
if (modifications != expectedModifications) {
throw new ConcurrentModificationException();
}
lastReturnedNode = nextNode;
nextNode = nextGreater(nextNode, iteratorType);
return doGetNext();
}
/**
* Removes from the underlying collection the last element
* returned by the iterator. This method can be called only
* once per call to next. The behavior of an iterator is
* unspecified if the underlying collection is modified while
* the iteration is in progress in any way other than by
* calling this method.
*
* @throws IllegalStateException if the next method has not
* yet been called, or the
* remove method has already
* been called after the last
* call to the next method.
* @throws ConcurrentModificationException if the
* DoubleOrderedMap is
* modified behind
* the iterator's
* back
*/
public final void remove()
throws IllegalStateException,
ConcurrentModificationException {
if (lastReturnedNode == null) {
throw new IllegalStateException();
}
if (modifications != expectedModifications) {
throw new ConcurrentModificationException();
}
doRedBlackDelete(lastReturnedNode);
expectedModifications++;
lastReturnedNode = null;
}
/* ********** END implementation of Iterator ********** */
} // end private abstract class DoubleOrderedMapIterator
// final for performance
private static final class Node implements Map.Entry, KeyValue {
private Comparable[] data;
private Node[] leftNode;
private Node[] rightNode;
private Node[] parentNode;
private boolean[] blackColor;
private int hashcodeValue;
private boolean calculatedHashCode;
/**
* Make a new cell with given key and value, and with null
* links, and black (true) colors.
*
* @param key
* @param value
*/
Node(final Comparable key, final Comparable value) {
data = new Comparable[]{ key, value };
leftNode = new Node[]{ null, null };
rightNode = new Node[]{ null, null };
parentNode = new Node[]{ null, null };
blackColor = new boolean[]{ true, true };
calculatedHashCode = false;
}
/**
* get the specified data
*
* @param index KEY or VALUE
*
* @return the key or value
*/
private Comparable getData(final int index) {
return data[index];
}
/**
* Set this node's left node
*
* @param node the new left node
* @param index KEY or VALUE
*/
private void setLeft(final Node node, final int index) {
leftNode[index] = node;
}
/**
* get the left node
*
* @param index KEY or VALUE
*
* @return the left node -- may be null
*/
private Node getLeft(final int index) {
return leftNode[index];
}
/**
* Set this node's right node
*
* @param node the new right node
* @param index KEY or VALUE
*/
private void setRight(final Node node, final int index) {
rightNode[index] = node;
}
/**
* get the right node
*
* @param index KEY or VALUE
*
* @return the right node -- may be null
*/
private Node getRight(final int index) {
return rightNode[index];
}
/**
* Set this node's parent node
*
* @param node the new parent node
* @param index KEY or VALUE
*/
private void setParent(final Node node, final int index) {
parentNode[index] = node;
}
/**
* get the parent node
*
* @param index KEY or VALUE
*
* @return the parent node -- may be null
*/
private Node getParent(final int index) {
return parentNode[index];
}
/**
* exchange colors with another node
*
* @param node the node to swap with
* @param index KEY or VALUE
*/
private void swapColors(final Node node, final int index) {
// Swap colors -- old hacker's trick
blackColor[index] ^= node.blackColor[index];
node.blackColor[index] ^= blackColor[index];
blackColor[index] ^= node.blackColor[index];
}
/**
* is this node black?
*
* @param index KEY or VALUE
*
* @return true if black (which is represented as a true boolean)
*/
private boolean isBlack(final int index) {
return blackColor[index];
}
/**
* is this node red?
*
* @param index KEY or VALUE
*
* @return true if non-black
*/
private boolean isRed(final int index) {
return !blackColor[index];
}
/**
* make this node black
*
* @param index KEY or VALUE
*/
private void setBlack(final int index) {
blackColor[index] = true;
}
/**
* make this node red
*
* @param index KEY or VALUE
*/
private void setRed(final int index) {
blackColor[⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -