Classes:
Collections
Arrays
ArrayList
SortedListextendsArrayList
HashMap
HashSet
*/
/****************
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.len;
}
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;i<this.lengh;i++)
h+=this.buffer[i].hashCode();
returnh;
}
ArrayList.prototype.size=function(){
returnthis.length;
}
ArrayList.prototype.clear=function(){
for(vari=0;i<this.length;i++)this.buffer[i]=null;
this.buffer.length=0;
this.length=0;
}
ArrayList.prototype.isEmpty=function(){
returnthis.length==0;
}
ArrayList.prototype.toArray=function(){
varcopy=newArray();
for(vari=0;i<this.length;i++){
copy[i]=this.buffer[i];
}
returncopy;
}
ArrayList.prototype.get=function(index){
if(index>=0&&index<this.length)
returnthis.buffer[index];
returnnull;
}
ArrayList.prototype.remove=function(param){
varindex=0;
if(isNaN(param)){
index=this.indexOf(param);
}
elseindex=param;
if(index>=0&&index<this.length){
for(vari=index;i<this.length-1;i++)
this.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;i<this.length;i++){
if(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;i<this.length;i++){
if(!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;i<list.size();i++){
if(!this.contains(list.get(i)))returnfalse;
}
returntrue;
}
ArrayList.prototype.removeAll=function(list){
for(vari=0;i<list.size();i++){
this.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;i<newsize;i++){
newbuffer[i]=this.buffer[begin+i];
}
returnnewArrayList(newbuffer);
}
ArrayList.prototype.set=function(index,obj){
if(index>=0&&index<this.length){
temp=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;i<oldTable.length;i++){
vare=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;i<this.table.length;i++)
this.table[i]=null;
this.length=0;
}
HashMap.prototype.containsValue=function(value){
if(value==null)returnfalse;
vartab=this.table;
for(vari=0;i<tab.length;i++)
for(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;
}
【javascript函数库-集合框架】相关文章：
★ JavaScript中isPrototypeOf函数作用和使用实例