📄 treebidimap.java
字号:
/** Whether to return KEY or VALUE order. */
protected final int orderType;
/** Whether to return KEY, VALUE, MAPENTRY or INVERSEMAPENTRY data. */
protected final int dataType;
/**
* Constructor.
*
* @param main the main map
* @param orderType the KEY or VALUE int for the order
* @param dataType the KEY, VALUE, MAPENTRY or INVERSEMAPENTRY int
*/
View(final TreeBidiMap main, final int orderType, final int dataType) {
super();
this.main = main;
this.orderType = orderType;
this.dataType = dataType;
}
public Iterator iterator() {
return new ViewIterator(main, orderType, dataType);
}
public int size() {
return main.size();
}
public boolean contains(final Object obj) {
checkNonNullComparable(obj, dataType);
return (main.lookup((Comparable) obj, dataType) != null);
}
public boolean remove(final Object obj) {
return (main.doRemove((Comparable) obj, dataType) != null);
}
public void clear() {
main.clear();
}
}
//-----------------------------------------------------------------------
/**
* An iterator over the map.
*/
static class ViewIterator implements OrderedIterator {
/** The parent map. */
protected final TreeBidiMap main;
/** Whether to return KEY or VALUE order. */
protected final int orderType;
/** Whether to return KEY, VALUE, MAPENTRY or INVERSEMAPENTRY data. */
protected final int dataType;
/** The last node returned by the iterator. */
protected Node lastReturnedNode;
/** The next node to be returned by the iterator. */
protected Node nextNode;
/** The previous node in the sequence returned by the iterator. */
protected Node previousNode;
/** The modification count. */
private int expectedModifications;
/**
* Constructor.
*
* @param main the main map
* @param orderType the KEY or VALUE int for the order
* @param dataType the KEY, VALUE, MAPENTRY or INVERSEMAPENTRY int
*/
ViewIterator(final TreeBidiMap main, final int orderType, final int dataType) {
super();
this.main = main;
this.orderType = orderType;
this.dataType = dataType;
expectedModifications = main.modifications;
nextNode = leastNode(main.rootNode[orderType], orderType);
lastReturnedNode = null;
previousNode = null;
}
public final boolean hasNext() {
return (nextNode != null);
}
public final Object next() {
if (nextNode == null) {
throw new NoSuchElementException();
}
if (main.modifications != expectedModifications) {
throw new ConcurrentModificationException();
}
lastReturnedNode = nextNode;
previousNode = nextNode;
nextNode = main.nextGreater(nextNode, orderType);
return doGetData();
}
public boolean hasPrevious() {
return (previousNode != null);
}
public Object previous() {
if (previousNode == null) {
throw new NoSuchElementException();
}
if (main.modifications != expectedModifications) {
throw new ConcurrentModificationException();
}
nextNode = lastReturnedNode;
if (nextNode == null) {
nextNode = main.nextGreater(previousNode, orderType);
}
lastReturnedNode = previousNode;
previousNode = main.nextSmaller(previousNode, orderType);
return doGetData();
}
/**
* Gets the data value for the lastReturnedNode field.
* @return the data value
*/
protected Object doGetData() {
switch (dataType) {
case KEY:
return lastReturnedNode.getKey();
case VALUE:
return lastReturnedNode.getValue();
case MAPENTRY:
return lastReturnedNode;
case INVERSEMAPENTRY:
return new UnmodifiableMapEntry(lastReturnedNode.getValue(), lastReturnedNode.getKey());
}
return null;
}
public final void remove() {
if (lastReturnedNode == null) {
throw new IllegalStateException();
}
if (main.modifications != expectedModifications) {
throw new ConcurrentModificationException();
}
main.doRedBlackDelete(lastReturnedNode);
expectedModifications++;
lastReturnedNode = null;
if (nextNode == null) {
previousNode = main.greatestNode(main.rootNode[orderType], orderType);
} else {
previousNode = main.nextSmaller(nextNode, orderType);
}
}
}
//-----------------------------------------------------------------------
/**
* An iterator over the map.
*/
static class ViewMapIterator extends ViewIterator implements OrderedMapIterator {
private final int oppositeType;
/**
* Constructor.
*
* @param main the main map
* @param orderType the KEY or VALUE int for the order
*/
ViewMapIterator(final TreeBidiMap main, final int orderType) {
super(main, orderType, orderType);
this.oppositeType = oppositeIndex(dataType);
}
public Object getKey() {
if (lastReturnedNode == null) {
throw new IllegalStateException("Iterator getKey() can only be called after next() and before remove()");
}
return lastReturnedNode.getData(dataType);
}
public Object getValue() {
if (lastReturnedNode == null) {
throw new IllegalStateException("Iterator getValue() can only be called after next() and before remove()");
}
return lastReturnedNode.getData(oppositeType);
}
public Object setValue(final Object obj) {
throw new UnsupportedOperationException();
}
}
//-----------------------------------------------------------------------
/**
* A view of this map.
*/
static class EntryView extends View {
private final int oppositeType;
/**
* Constructor.
*
* @param main the main map
* @param orderType the KEY or VALUE int for the order
* @param dataType the MAPENTRY or INVERSEMAPENTRY int for the returned data
*/
EntryView(final TreeBidiMap main, final int orderType, final int dataType) {
super(main, orderType, dataType);
this.oppositeType = main.oppositeIndex(orderType);
}
public boolean contains(Object obj) {
if (obj instanceof Map.Entry == false) {
return false;
}
Map.Entry entry = (Map.Entry) obj;
Object value = entry.getValue();
Node node = main.lookup((Comparable) entry.getKey(), orderType);
return (node != null && node.getData(oppositeType).equals(value));
}
public boolean remove(Object obj) {
if (obj instanceof Map.Entry == false) {
return false;
}
Map.Entry entry = (Map.Entry) obj;
Object value = entry.getValue();
Node node = main.lookup((Comparable) entry.getKey(), orderType);
if (node != null && node.getData(oppositeType).equals(value)) {
main.doRedBlackDelete(node);
return true;
}
return false;
}
}
//-----------------------------------------------------------------------
/**
* A node used to store the data.
*/
static 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) {
super();
data = new Comparable[] { key, value };
leftNode = new Node[2];
rightNode = new Node[2];
parentNode = new Node[2];
blackColor = new boolean[] { true, true };
calculatedHashCode = false;
}
/**
* Get the specified data.
*
* @param index the KEY or VALUE int
* @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 the KEY or VALUE int
*/
private void setLeft(final Node node, final int index) {
leftNode[index] = node;
}
/**
* Get the left node.
*
* @param index the KEY or VALUE int
* @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 the KEY or VALUE int
*/
private void setRight(final Node node, final int index) {
rightNode[index] = node;
}
/**
* Get the right node.
*
* @param index the KEY or VALUE int
* @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 the KEY or VALUE int
*/
private void setParent(final Node node, final int index) {
parentNode[index] = node;
}
/**
* Get the parent node.
*
* @param index the KEY or VALUE int
* @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 the KEY or VALUE int
*/
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 the KEY or VALUE int
* @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 the KEY or VALUE int
* @return true if non-black
*/
private⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -