这个Map类是基于红黑树构建的，每个树节点有两个域，一个存放节点的Key,一个存放节点的Value,相当于是两棵红黑树，一棵是关于key的红黑树，一棵是关于Value的红黑树。
关于红黑树的详细介绍，参考《C#与数据结构--树论--红黑树（Red Black Tree）》这篇文章。
public final class DoubleOrderedMap extends AbstractMap
{
private Node[] rootNode = new Node[] { null, null };//根节点
public Set entrySetByValue()
{//按Value获取Entry集合
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;
Objectkey = entry.getKey();
Nodenode= 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;
Objectkey = entry.getKey();
Nodenode= 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];
}
private Object doRemove(final Comparable o, final int index)
{
Node node = lookup(o, index);//在红黑树中查找节点
Object rval = null;
if (node != null)
{
rval = node.getData(oppositeIndex(index));
doRedBlackDelete(node);//在红黑树中删除指定节点
}
return rval;
}
private Object doGet(final Comparable o, final int index)
{
checkNonNullComparable(o, index);//检查参数非空
Node node = lookup(o, index);//按Key或Value查找指定节点
return ((node == null)? null: node.getData(oppositeIndex(index)));
}
private Node lookup(final Comparable data, final int index)
{
Node rval = null;
Node node = rootNode[index];//根节点
while (node != null)
{
int cmp = compare(data, node.getData(index));//与当前节点比较
if (cmp == 0)
{//找到了
rval = node;
break;
} else {//在左子树或右子树中寻找
node = (cmp < 0)
? node.getLeft(index)
: node.getRight(index);
}
}
return rval;
}
private static Node leastNode(final Node node, final int index)
{//返回指定节点的最右子节点
Node rval = node;
if (rval != null) {
while (rval.getLeft(index) != null) {
rval = rval.getLeft(index);
}
}
return rval;
}
private Node nextGreater(final Node node, final int index)
{//返回下一个大于指定节点的节点
Node rval = null;
if (node == null) {
rval = null;
} else if (node.getRight(index) != null)
{//右子树不为空，返回右子树最左子节点
rval = leastNode(node.getRight(index), index);
}
else
{//不断向上，只要仍然是右子节点
Node parent = node.getParent(index);
Node child= node;
while ((parent != null) && (child == parent.getRight(index))) {
child= parent;
parent = parent.getParent(index);
}
rval = parent;
}
return rval;
}
private void rotateLeft(final Node node, final int index)
{//左旋操作
Node rightChild = node.getRight(index);
node.setRight(rightChild.getLeft(index), index);
if (rightChild.getLeft(index) != null) {
rightChild.getLeft(index).setParent(node, index);
}
rightChild.setParent(node.getParent(index), index);
if (node.getParent(index) == null)
{//设置为根节点
rootNode[index] = rightChild;
} else if (node.getParent(index).getLeft(index) == node) {
node.getParent(index).setLeft(rightChild, index);
} else {
node.getParent(index).setRight(rightChild, index);
}
rightChild.setLeft(node, index);
node.setParent(rightChild, index);
}
private void rotateRight(final Node node, final int index)
{//右旋操作
Node leftChild = node.getLeft(index);
node.setLeft(leftChild.getRight(index), index);
if (leftChild.getRight(index) != null) {
leftChild.getRight(index).setParent(node, index);
}
leftChild.setParent(node.getParent(index), index);
if (node.getParent(index) == null)
{//设置为根节点
rootNode[index] = leftChild;
} else if (node.getParent(index).getRight(index) == node) {
node.getParent(index).setRight(leftChild, index);
} else {
node.getParent(index).setLeft(leftChild, index);
}
leftChild.setRight(node, index);
node.setParent(leftChild, index);
}
责任编辑：小草
