了解下JAVA的Commons Collections进修条记（三）

主要缺点就是:速度比较慢,没有C和C++快
这个Map类是基于红黑树构建的，每一个树节点有两个域，一个寄存节点的Key,一个寄存节点的Value,相称因而两棵红黑树，一棵是关于key的红黑树，一棵是关于Value的红黑树。
关于红黑树的具体先容，参考《C#与数据布局--树论--红黑树（RedBlackTree）》这篇文章。
publicfinalclassDoubleOrderedMapextendsAbstractMap
{
privateNode[]rootNode=newNode[]{null,null};//根节点

publicSetentrySetByValue()
{//按Value猎取Entry汇合
　　　　if(setOfEntries[VALUE]==null){
　　　　　　setOfEntries[VALUE]=newAbstractSet(){
　　　　　　　　publicIteratoriterator(){
　　　　　　　　　　returnnewDoubleOrderedMapIterator(VALUE){
　　　　　　　　　　　　protectedObjectdoGetNext(){
　　　　　　　　　　　　　　returnlastReturnedNode;
　　　　　　　　　　　　}
　　　　　　　　　　};
　　　　　　　　}
　　　　　　　　publicbooleancontains(Objecto){
　　　　　　　　　　if(!(oinstanceofMap.Entry)){
　　　　　　　　　　　　returnfalse;
　　　　　　　　　　}
　　　　　　　　　　Map.Entryentry=(Map.Entry)o;
　　　　　　　　　　Object　　key　=entry.getKey();
　　　　　　　　　　Node　　　node　=lookup((Comparable)entry.getValue(),
　　　　　　　　　　　　　　　　　　　　　　VALUE);
　　　　　　　　　　return(node!=null)&&node.getData(KEY).equals(key);
　　　　　　　　}
　　　　　　　　publicbooleanremove(Objecto){
　　　　　　　　　　if(!(oinstanceofMap.Entry)){
　　　　　　　　　　　　returnfalse;
　　　　　　　　　　}
　　　　　　　　　　Map.Entryentry=(Map.Entry)o;
　　　　　　　　　　Object　　key　=entry.getKey();
　　　　　　　　　　Node　　　node　=lookup((Comparable)entry.getValue(),
　　　　　　　　　　　　　　　　　　　　　　VALUE);
　　　　　　　　　　if((node!=null)&&node.getData(KEY).equals(key)){
　　　　　　　　　　　　doRedBlackDelete(node);
　　　　　　　　　　　　returntrue;
　　　　　　　　　　}
　　　　　　　　　　returnfalse;
　　　　　　　　}
　　　　　　　　publicintsize(){
　　　　　　　　　　returnDoubleOrderedMap.this.size();
　　　　　　　　}
　　　　　　　　publicvoidclear(){
　　　　　　　　　　DoubleOrderedMap.this.clear();
　　　　　　　　}
　　　　　　};
　　　　}
　　　　returnsetOfEntries[VALUE];
}

privateObjectdoRemove(finalComparableo,finalintindex)
{
　　　　Node　node=lookup(o,index);//在红黑树中查找节点
　　　　Objectrval=null;
　　　　if(node!=null)
{
　　　　　　rval=node.getData(oppositeIndex(index));
　　　　　　doRedBlackDelete(node);//在红黑树中删除指定节点
　　　　}
　　　　returnrval;
　　}
privateObjectdoGet(finalComparableo,finalintindex)
{
　　　　checkNonNullComparable(o,index);//反省参数非空
　　　　Nodenode=lookup(o,index);//按Key或Value查找指定节点
　　　　return((node==null)?null:node.getData(oppositeIndex(index)));
　　}
privateNodelookup(finalComparabledata,finalintindex)
{
　　　　Noderval=null;
　　　　Nodenode=rootNode[index];//根节点
　　　　while(node!=null)
{
　　　　　　intcmp=compare(data,node.getData(index));//与以后节点对照
　　　　　　if(cmp==0)
{//找到了
　　　　　　　　rval=node;
　　　　　　　　break;
　　　　　　}else{//在左子树或右子树中寻觅
　　　　　　　　node=(cmp<0)
　　　　　　　　　　　?node.getLeft(index)
　　　　　　　　　　　:node.getRight(index);
　　　　　　}
　　　　}
　　　　returnrval;
　　}
privatestaticNodeleastNode(finalNodenode,finalintindex)
{//前往指定节点的最右子节点
　　　　Noderval=node;
　　　　if(rval!=null){
　　　　　　while(rval.getLeft(index)!=null){
　　　　　　　　rval=rval.getLeft(index);
　　　　　　}
　　　　}
　　　　returnrval;
　　}

privateNodenextGreater(finalNodenode,finalintindex)
{//前往下一个年夜于指定节点的节点
　　　　Noderval=null;
　　　　if(node==null){
　　　　　　rval=null;
　　　　}elseif(node.getRight(index)!=null)
{//右子树不为空，前往右子树最左子节点
　　　　　　rval=leastNode(node.getRight(index),index);
　　　　}
else
{//不休向上，只需仍旧是右子节点
　　　　　　Nodeparent=node.getParent(index);
　　　　　　Nodechild　=node;
　　　　　　while((parent!=null)&&(child==parent.getRight(index))){
　　　　　　　　child　=parent;
　　　　　　　　parent=parent.getParent(index);
　　　　　　}
　　　　　　rval=parent;
　　　　}
　　　　returnrval;
　　}

privatevoidrotateLeft(finalNodenode,finalintindex)
{//左旋操纵
　　　　NoderightChild=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;
　　　　}elseif(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);
　　}

privatevoidrotateRight(finalNodenode,finalintindex)
{//右旋操纵
　　　　NodeleftChild=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;
　　　　}elseif(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);
}
privatevoiddoRedBlackInsert(finalNodeinsertedNode,finalintindex)
　{//举行红黑树节点拔出后的调剂
　　　　NodecurrentNode=insertedNode;//新拔出节点置为以后节点
　　　　makeRed(currentNode,index);//标志新节点为白色
　　　　while((currentNode!=null)&&(currentNode!=rootNode[index])&&(isRed(currentNode.getParent(index),index)))
　　　　{//确保以后节点父节点为白色才持续处置
　　　　　　if(isLeftChild(getParent(currentNode,index),index))
　　　　　　{//父节点是祖父节点的左孩子
　　　　　　　　Nodey=getRightChild(getGrandParent(currentNode,index),index);//叔节点是祖父节点的右孩子
　　　　　　　　if(isRed(y,index))
　　　　　　　　{//红叔()
　　　　　　　　　　makeBlack(getParent(currentNode,index),index);//标志父节点为玄色
　　　　　　　　　　makeBlack(y,index);//标志叔节点为玄色
　　　　　　　　　　makeRed(getGrandParent(currentNode,index),index);//标志祖父节点为白色
　　　　　　　　　　currentNode=getGrandParent(currentNode,index);//置祖父节点为以后节点
　　　　　　　　}
　　　　　　　　else
　　　　　　　　{//黑叔(对应和)
　　　　　　　　　　if(isRightChild(currentNode,index))
　　　　　　　　　　{//以后节点是父节点的右孩子()
　　　　　　　　　　　　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
　　　　　　{//父节点是祖父节点的右孩子
　　　　　　　　Nodey=getLeftChild(getGrandParent(currentNode,index),index);//叔节点是祖父节点的左孩子
　　　　　　　　if(isRed(y,index))
　　　　　　　　{//红叔()
　　　　　　　　　　makeBlack(getParent(currentNode,index),index);//标志父节点为玄色
　　　　　　　　　　makeBlack(y,index);//标志叔节点为玄色
　　　　　　　　　　makeRed(getGrandParent(currentNode,index),index);//标志祖父节点为白色
　　　　　　　　　　currentNode=getGrandParent(currentNode,index);//置祖父节点为以后节点
　　　　　　　　}
　　　　　　　　else
　　　　　　　　{//黑叔(对应和)
　　　　　　　　　　if(isLeftChild(currentNode,index))
　　　　　　　　　　{//以后节点是父节点的左孩子()
　　　　　　　　　　　　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);//标志根节点为玄色
　　}

privatevoiddoRedBlackDelete(finalNodedeletedNode)
{//在红黑树中删除指定节点
　　　　for(intindex=FIRST_INDEX;index<NUMBER_OF_INDICES;index++){
　　　　　　//ifdeletednodehasbothleftandchildren,swapwith
　　　　　　//thenextgreaternode
　　　　　　if((deletedNode.getLeft(index)!=null)
　　　　　　　　　　&&(deletedNode.getRight(index)!=null)){
　　　　　　　　swapPosition(nextGreater(deletedNode,index),deletedNode,
　　　　　　　　　　　　　　index);
　　　　　　}
　　　　　　Nodereplacement=((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;
　　　　　　　　}elseif(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{
　　　　　　　　//replacementisnull
　　　　　　　　if(deletedNode.getParent(index)==null){
　　　　　　　　　　//emptytree
　　　　　　　　　　rootNode[index]=null;
　　　　　　　　}else{
　　　　　　　　　　//deletednodehadnochildren
　　　　　　　　　　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();
　　}

　　privatevoiddoRedBlackDeleteFixup(finalNodereplacementNode,
　　　　　　　　　　　　　　　　　　　finalintindex){
<p>
首先java功能强大的背后是其复杂性，就拿web来说，当今流行的框架有很多，什么struts，spring，jQuery等等，而这无疑增加了java的复杂性。

接着就是EJB了，EJB就是Enterprise JavaBean, 看名字好象它是Javabean，可是它和Javabean还是有区别的。它是一个体系结构，你可以搭建更安全、更稳定的企业应用。它的大量代码已由中间件（也就是我们常听到的 Weblogic,Websphere这些J2EE服务器）完成了，所以我们要做的程序代码量很少，大部分工作都在设计和配置中间件上。

Java自面世后就非常流行，发展迅速，对C++语言形成了有力冲击。Java 技术具有卓越的通用性、高效性、平台移植性和安全性，广泛应用于个人PC、数据中心、游戏控制台

Java 编程语言的风格十分接近C、C++语言。

另外编写和运行Java程序需要JDK(包括JRE)，在sun的官方网站上有下载，thinking in java第三版用的JDK版本是1.4,现在流行的版本1.5（sun称作J2SE 5.0，汗），不过听说Bruce的TIJ第四版国外已经出来了，是专门为J2SE 5.0而写的。

那么我书也看了，程序也做了，别人问我的问题我都能解决了，是不是就成为高手了呢？当然没那么简单，这只是万里长征走完了第一步。不信？那你出去接一个项目，你知道怎么下手吗，你知道怎么设计吗，你知道怎么组织人员进行开发吗？你现在脑子里除了一些散乱的代码之外，可能再没有别的东西了吧！

仓酷云

另外编写和运行Java程序需要JDK(包括JRE)，在sun的官方网站上有下载，thinking in java第三版用的JDK版本是1.4,现在流行的版本1.5（sun称作J2SE 5.0，汗），不过听说Bruce的TIJ第四版国外已经出来了，是专门为J2SE 5.0而写的。

还好，SUN提供了Javabean可以把你的JSP中的 Java代码封装起来，便于调用也便于重用。

Java 不同于一般的编译执行计算机语言和解释执行计算机语言。它首先将源代码编译成二进制字节码（bytecode），然后依赖各种不同平台上的虚拟机来解释执行字节码。从而实现了“一次编译、到处执行”的跨平台特性。