Java教程:CommonsCollections學(xué)習(xí)筆記（三）

這個(gè)Map類是基于紅黑樹構(gòu)建的，每個(gè)樹節(jié)點(diǎn)有兩個(gè)域，一個(gè)存放節(jié)點(diǎn)的Key,一個(gè)存放節(jié)點(diǎn)的Value,相當(dāng)于是兩棵紅黑樹，一棵是關(guān)于key的紅黑樹，一棵是關(guān)于Value的紅黑樹。
    關(guān)于紅黑樹的詳細(xì)介紹，參考《C#與數(shù)據(jù)結(jié)構(gòu)--樹論--紅黑樹（Red Black Tree）》這篇文章。
    public final class DoubleOrderedMap extends AbstractMap
    {
    private Node[] rootNode = new Node[] { null, null };//根節(jié)點(diǎn)
    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);//在紅黑樹中查找節(jié)點(diǎn)
    Object rval = null;
    if (node != null)
    {
    rval = node.getData(oppositeIndex(index));
    doRedBlackDelete(node);//在紅黑樹中刪除指定節(jié)點(diǎn)
    }
    return rval;
    }
    private Object doGet(final Comparable o, final int index)
    {
    checkNonNullComparable(o, index);//檢查參數(shù)非空
    Node node = lookup(o, index);//按Key或Value查找指定節(jié)點(diǎn)
    return ((node == null)? null: node.getData(oppositeIndex(index)));
    }
    private Node lookup(final Comparable data, final int index)
    {
    Node rval = null;
    Node node = rootNode[index];//根節(jié)點(diǎn)
    while (node != null)
    {
    int cmp = compare(data, node.getData(index));//與當(dāng)前節(jié)點(diǎn)比較
    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)
    {//返回指定節(jié)點(diǎn)的最右子節(jié)點(diǎn)
    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)
    {//返回下一個(gè)大于指定節(jié)點(diǎn)的節(jié)點(diǎn)
    Node rval = null;
    if (node == null) {
    rval = null;
    } else if (node.getRight(index) != null)
    {//右子樹不為空，返回右子樹最左子節(jié)點(diǎn)
    rval = leastNode(node.getRight(index), index);
    }
    else
    {//不斷向上，只要仍然是右子節(jié)點(diǎn)
    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)
    {//設(shè)置為根節(jié)點(diǎn)
    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)
    {//設(shè)置為根節(jié)點(diǎn)
    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);
    }