Commons Collections学习笔记（三）

Commons Collections学习笔记（三）2011-07-20 博客园 Phinecos这个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;
           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];
}

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）;
}
private void doRedBlackInsert（final Node insertedNode, final int index）
  {//进行红黑树节点插入后的调整
     Node currentNode = insertedNode;//新插入节点置为当前节点
     makeRed（currentNode, index）;//标记新节点为红色
     while （（currentNode ！= null） && （currentNode ！= rootNode[index]）&& （isRed（currentNode.getParent （index）, index）））
     {//确保当前节点父节点为红色才继续处理
       if （isLeftChild（getParent（currentNode, index）, index））
       {//父节点是祖父节点的左孩子
         Node y = getRightChild（getGrandParent（currentNode, index）,index）;//叔节点是祖父节点的右孩子
         if （isRed（y, index））
         {//红叔（图4）
           makeBlack（getParent（currentNode, index）, index）;//标记父节点为黑色
           makeBlack（y, index）;//标记叔节点为黑色
           makeRed（getGrandParent（currentNode, index）, index）;//标记祖父节点为红色
           currentNode = getGrandParent（currentNode, index）;//置祖父节点为当前节点
         }
         else
         {//黑叔（对应图5和图6）
           if （isRightChild（currentNode, index））
           {//当前节点是父节点的右孩子（图6）
             currentNode = getParent（currentNode, index）;//置父节点为当前节点
             rotateLeft（currentNode, index）;//左旋
           }
           makeBlack（getParent（currentNode, index）, index）;//当前节点的父节点置为黑色
           makeRed（getGrandParent（currentNode, index）, index）;//祖父节点置为红色
           if （getGrandParent（currentNode, index） ！= null）
           {//对祖父节点进行右旋
             rotateRight（getGrandParent（currentNode, index）,index）;
           }
         }
       } else
       {//父节点是祖父节点的右孩子
         Node y = getLeftChild（getGrandParent（currentNode, index）,index）;//叔节点是祖父节点的左孩子
         if （isRed（y, index））
         {//红叔（图4）
           makeBlack（getParent（currentNode, index）, index）;//标记父节点为黑色
           makeBlack（y, index）;//标记叔节点为黑色
           makeRed（getGrandParent（currentNode, index）, index）;//标记祖父节点为红色
           currentNode = getGrandParent（currentNode, index）;//置祖父节点为当前节点
         }
         else
         {//黑叔（对应图7和图8）
           if （isLeftChild（currentNode, index））
           {//当前节点是父节点的左孩子（图8）
             currentNode = getParent（currentNode, index）;//置父节点为当前节点
             rotateRight（currentNode, index）;//右旋
           }
           makeBlack（getParent（currentNode, index）, index）;//当前节点的父节点置为黑色
           makeRed（getGrandParent（currentNode, index）, index）;//祖父节点置为红色
           if （getGrandParent（currentNode, index） ！= null）
           {//对祖父节点进行左旋
             rotateLeft（getGrandParent（currentNode, index）, index）;
           }
         }
       }
     }
     makeBlack（rootNode[index], index）;//标记根节点为黑色
   }

private void doRedBlackDelete（final Node deletedNode）
{//在红黑树中删除指定节点
     for （int index = FIRST_INDEX; index < NUMBER_OF_INDICES; index++） {
       // if deleted node has both left and children, swap with
       // the next greater node
       if （（deletedNode.getLeft（index） ！= null）
           && （deletedNode.getRight（index） ！= null）） {
         swapPosition（nextGreater（deletedNode, index）, deletedNode,
               index）;
       }
       Node replacement = （（deletedNode.getLeft（index） ！= null）
                 ？ deletedNode.getLeft（index）
                 : deletedNode.getRight（index））;
       if （replacement ！= null） {
         replacement.setParent（deletedNode.getParent（index）, index）;

         if （deletedNode.getParent（index） == null） {
           rootNode[index] = replacement;
         } else if （deletedNode
              == deletedNode.getParent（index）.getLeft（index）） {
           deletedNode.getParent（index）.setLeft（replacement, index）;
         } else {
           deletedNode.getParent（index）.setRight（replacement, index）;
         }
         deletedNode.setLeft（null, index）;
         deletedNode.setRight（null, index）;
         deletedNode.setParent（null, index）;
         if （isBlack（deletedNode, index）） {
           doRedBlackDeleteFixup（replacement, index）;
         }
       } else {
         // replacement is null
         if （deletedNode.getParent（index） == null） {
           // empty tree
           rootNode[index] = null;
         } else {
           // deleted node had no children
           if （isBlack（deletedNode, index）） {
             doRedBlackDeleteFixup（deletedNode, index）;
           }
           if （deletedNode.getParent（index） ！= null） {
             if （deletedNode
                 == deletedNode.getParent（index）
                   .getLeft（index）） {
               deletedNode.getParent（index）.setLeft（null, index）;
             } else {
               deletedNode.getParent（index）.setRight（null,
                          index）;
             }
             deletedNode.setParent（null, index）;
           }
         }
       }
     }
     shrink（）;
   }

   private void doRedBlackDeleteFixup（final Node replacementNode,
                    final int index）
{