javascript函数库-集合框架

/****************
Collections
NOTE:sort()returnanewList
****************/
functionCollections(){}
Collections.sort=function(){
if(arguments.length==1){
vars=newSortedList();
s.addAll(arguments[0]);
returns;
}
elseif(arguments.length==2){
vars=newSortedList();
s.setComparator(arguments[1]);
s.addAll(arguments[0]);
returns;
}
else
throw"IllegalArgument";
}
/***************
Arrays
****************/
functionArrays(){}
Arrays.asList=function(arr){
returnnewArrayList(arr);
}

//ListIterator
functionListIterator(table,len){
this.table=table;
this.len=len;
this.index=0;

this.hasNext=function(){
returnthis.index}

this.next=function(){
if(!this.hasNext())
throw"NosuchElement!";
returnthis.table[this.index++];
}
}

/********************
ArrayList
********************/
functionArrayList(){
this.buffer=newArray();
if(arguments.length>0)this.buffer=arguments[0];
this.length=this.buffer.length;
}
ArrayList.prototype.hashCode=function(){
varh=0;
for(vari=0;ih+=this.buffer[i].hashCode();
returnh;
}

ArrayList.prototype.size=function(){
returnthis.length;
}

ArrayList.prototype.clear=function(){
for(vari=0;ithis.buffer.length=0;
this.length=0;
}

ArrayList.prototype.isEmpty=function(){
returnthis.length==0;
}

ArrayList.prototype.toArray=function(){
varcopy=newArray();
for(vari=0;icopy[i]=this.buffer[i];
}
returncopy;
}
ArrayList.prototype.get=function(index){
if(index>=0&&indexreturnthis.buffer[index];
returnnull;
}

ArrayList.prototype.remove=function(param){
varindex=0;

if(isNaN(param)){
index=this.indexOf(param);
}
elseindex=param;

if(index>=0&&indexfor(vari=index;ithis.buffer[i]=this.buffer[i+1];
this.length-=1;
returntrue;
}
elsereturnfalse;
}

ArrayList.prototype.add=function(){
varargs=arguments;
if(args.length==1){
this.buffer[this.length++]=args[0];
returntrue;
}
elseif(args.length==2){
varindex=args[0];
varobj=args[1];
if(index>=0&&index<=this.length){
for(vari=this.length;i>index;i--)
this.buffer[i]=this.buffer[i-1];
this.buffer[i]=obj;
this.length+=1;
returntrue;
}
}
returnfalse;
}

ArrayList.prototype.indexOf=function(obj){
for(vari=0;iif(this.buffer[i].equals(obj))returni;
}
return-1;
}

ArrayList.prototype.lastIndexOf=function(obj){
for(vari=this.length-1;i>=0;i--){
if(this.buffer[i].equals(obj))returni;
}
return-1;
}

ArrayList.prototype.contains=function(obj){
returnthis.indexOf(obj)!=-1;
}

ArrayList.prototype.equals=function(obj){
if(this.size()!=obj.size())returnfalse;
for(vari=0;iif(!obj.get(i).equals(this.buffer[i]))returnfalse;
}
returntrue;
}

ArrayList.prototype.addAll=function(list){
varmod=false;
for(varit=list.iterator();it.hasNext();){
varv=it.next();
if(this.add(v))mod=true;
}
returnmod;
}

ArrayList.prototype.containsAll=function(list){
for(vari=0;iif(!this.contains(list.get(i)))returnfalse;
}
returntrue;
}

ArrayList.prototype.removeAll=function(list){
for(vari=0;ithis.remove(this.indexOf(list.get(i)));
}
}

ArrayList.prototype.retainAll=function(list){
for(vari=this.length-1;i>=0;i--){
if(!list.contains(this.buffer[i])){
this.remove(i);
}
}
}

ArrayList.prototype.subList=function(begin,end){
if(begin<0)begin=0;
if(end>this.length)end=this.length;
varnewsize=end-begin;
varnewbuffer=newArray();
for(vari=0;inewbuffer[i]=this.buffer[begin+i];
}
returnnewArrayList(newbuffer);
}
ArrayList.prototype.set=function(index,obj){
if(index>=0&&indextemp=this.buffer[index];
this.buffer[index]=obj;
returntemp;
}
}

ArrayList.prototype.iterator=functioniterator(){
returnnewListIterator(this.buffer,this.length);
}

/*****************************
SortedListextendsArrayList
*****************************/
functionSortedList(){
this.com=null;
}
SortedList.prototype=newArrayList();
SortedList.prototype.setComparator=function(comp){
if(this.length!=0)throw"Onlycanbesetwhenlistisempty";
this.com=comp;
}

SortedList.prototype.getComparator=function(){
returnthis.com;
}

//override
SortedList.prototype.add=function(obj){
varindex=this.indexOf(obj);
for(vari=this.length;i>index;){
this.buffer[i]=this.buffer[--i];
}

this.buffer[index]=obj;
this.length++;
}
//override
SortedList.prototype.indexOf=function(obj){
if(this.length==0)return0;

varmin=0,max=this.length-1;
varmid=0;
while(min<=max){

mid=(min+max)>>1;
varc=0;
if(this.com==null)c=obj.compareTo(this.buffer[mid]);
elsec=this.com.compare(obj,this.buffer[mid]);

if(c==0){
returnmid;
}
elseif(c<0){
max=mid-1;
}
else{
min=mid+1;
}
}
mid=(min+max)>>1;
returnmid+1;
}
//override
SortedList.prototype.contains=function(obj){
if(this.length==0)returnfalse;
varmin=0,max=this.length-1;
varmid=0;
while(min<=max){
mid=(min+max)>>1;
varc=0;
if(this.com==null)c=obj.compareTo(this.buffer[mid]);
elsec=this.com.compare(obj,this.buffer[mid]);
if(c==0){
returntrue;
}
elseif(c<0){
max=mid-1;
}
else{
min=mid+1;
}
}
returnfalse;
}
//override
SortedList.prototype.subList=function(begin,end){
varsl=newSortedList();
s1.setComparator(this.com);
varsub=ArrayList.prototype.subList(begin.end);
sl.addAll(sub);
returnsl;
}

/****************************
HashMap
****************************/

functionEntry(h,k,v,n){
this.value=v;
this.next=n;
this.key=k;
this.hash=h;

this.getKey=function(){
returnthis.key;
}

this.getValue=function(){
returnthis.value;
}
this.setValue=function(newValue){
varoldValue=this.value;
this.value=newValue;
returnoldValue;
}

this.equals=function(o){
vare=o;
vark1=this.getKey();
vark2=e.getKey();
varv1=this.getValue();
varv2=e.getValue();
return(k1.equals(k2)&&v1.equals(v2));
}

this.hashCode=function(){
returnthis.key.hashCode()^this.value.hashCode();
}

this.toString=function(){
returnthis.getKey()+"="+this.getValue();
}
}

functionHashIterator(table,index,ne){

this.table=table;
this.ne=ne;
this.index=index;
this.current=null;

this.hasNext=function(){
returnthis.ne!=null;
}

this.next=function(){

vare=this.ne;
if(e==null)
throw"NosuchElement";

varn=e.next;
vart=this.table;
vari=this.index;
while(n==null&&i>0)
n=t[--i];
this.index=i;
this.ne=n;
this.current=e;

returnthis.current;
}
}

functionHashMap()
{
this.len=8;
this.table=newArray();
this.length=0;
}
//refertojava.util.HashMap
HashMap.hash=function(x){
varh=x.hashCode();
h+=~(h<<9);
h^=(h>>>14);
h+=(h<<4);
h^=(h>>>10);
returnh;
}

HashMap.prototype.rehash=function(){
varoldTable=this.table;
this.table=newArray();

//transfer
for(vari=0;ivare=oldTable[i];
if(e!=null){
oldTable[i]=null;
do{
varnext=e.next;
varj=this.indexFor(e.hash);
e.next=this.table[j];
this.table[j]=e;
e=next;
}while(e!=null);
}
}
}

HashMap.prototype.indexFor=function(h){
varindex=h&(this.len-1);
returnindex;
}

HashMap.prototype.size=function(){
returnthis.length;
}

HashMap.prototype.isEmpty=function(){
returnthis.length==0;
}

HashMap.prototype.get=function(key){
varhash=HashMap.hash(key);
vari=this.indexFor(hash);

vare=this.table[i];

while(true){
if(e==null)
returnnull;
if(e.hash==hash&&key.equals(e.key))
returne.value;
e=e.next;
}
}

HashMap.prototype.containsKey=function(key){
varhash=HashMap.hash(key);
vari=this.indexFor(hash);
vare=this.table[i];

while(e!=null){
if(e.hash==hash&&key.equals(e.key))
returntrue;
e=e.next;
}
returnfalse;
}

HashMap.prototype.put=function(key,value){
varhash=HashMap.hash(key);
vari=this.indexFor(hash);

for(vare=this.table[i];e!=null;e=e.next){
if(e.hash==hash&&key.equals(e.key)){
varoldValue=e.value;
e.value=value;
returnoldValue;
}
}

this.addEntry(hash,key,value,i);

varr=Math.ceil(this.length*1.5);

if(r>this.len){
this.len=this.len<<1;
this.rehash();
}
returnnull;
}

HashMap.prototype.putAll=function(map){
varmod=false;
for(varit=map.iterator();it.hasNext();){
vare=it.next();
if(this.put(e.getKey(),e.getValue()))mod=true;
}
}

HashMap.prototype.remove=function(key){
vare=this.removeEntryForKey(key);
return(e==null?null:e.value);
}

HashMap.prototype.removeEntryForKey=function(key){
varhash=HashMap.hash(key);
vari=this.indexFor(hash);

varprev=this.table[i];
vare=prev;

while(e!=null){
varnext=e.next;
if(e.hash==hash&&key.equals(e.key)){
this.length--;
if(prev.equals(e))
this.table[i]=next;
else
prev.next=next;
returne;
}
prev=e;
e=next;
}
returne;
}

HashMap.prototype.clear=function(){
for(vari=0;ithis.table[i]=null;
this.length=0;
}

HashMap.prototype.containsValue=function(value){
if(value==null)returnfalse;

vartab=this.table;
for(vari=0;ifor(vare=tab[i];e!=null;e=e.next)
if(value.equals(e.value))
returntrue;
returnfalse;
}

HashMap.prototype.addEntry=function(hash,key,value,bucketIndex){
this.table[bucketIndex]=newEntry(hash,key,value,this.table[bucketIndex]);
this.length++;
}

HashMap.prototype.iterator=function(){
vari=this.table.length;

varnext=null;
while(i>0&&next==null){
next=this.table[--i];
}

returnnewHashIterator(this.table,i,next);
}

HashMap.prototype.hashCode=function(){
varh=0;
for(varit=this.iterator();it.hasNext();){
h+=it.next().hashCode();
}
returnh;
}

HashMap.prototype.equals=function(map){
if(!this.typeMatches(map))returnfalse;
if(map.size()!=this.size())returnfalse;

for(varit=this.iterator();it.hasNext();){
vare=it.next();
varkey=e.getKey();
varvalue=e.getValue();

if(!value.equals(map.get(key)))returnfalse

}
returntrue;
}

/*************************
HashSet
**************************/

functionHashSetIterator(ite){
this.it=ite;

this.hasNext=function(){
returnthis.it.hasNext();
}

this.next=function(){
returnthis.it.next().getKey();
}
}

functionHashSet(){
this.map=newHashMap();
}
HashSet.NULL=newNumber("!THISISNULL!");

HashSet.prototype.size=function(){
returnthis.map.size();
}

HashSet.prototype.isEmpty=function(){
returnthis.map.isEmpty();
}

HashSet.prototype.contains=function(o){
returnthis.map.containsKey(o);
}

HashSet.prototype.add=function(o){
returnthis.map.put(o,HashSet.NULL)==null;
}

HashSet.prototype.addAll=function(set){
varmod=false;
for(varit=set.iterator();it.hasNext();){
if(this.add(it.next()))mod=true;
}
returnmod;
}

HashSet.prototype.remove=function(o){
returnthis.map.remove(o).equals(HashSet.NULL);
}

HashSet.prototype.clear=function(){
this.map.clear();
}

HashSet.prototype.iterator=function(){
returnnewHashSetIterator(this.map.iterator());
}

HashSet.prototype.equals=function(o){
if(!this.typeMatches(o))returnfalse;
if(o.size()!=this.size())returnfalse;
for(varit=this.iterator();it.hasNext();){
if(!o.contains(it.next()))returnfalse;
}
returntrue;
}

HashSet.prototype.hashCode=function(){
varh=0;
for(varit=this.iterator();it.hasNext();){
h+=it.next().hashCode();
}
returnh;
}

HashSet.prototype.toArray=function(){
vararr=newArray();
vari=0;
for(varit=this.iterator();it.hasNext();){
arr[i++]=it.next();
}
returnarr;
}