classes:
collections
arrays
arraylist
sortedlist extends arraylist
hashmap
hashset
*/
/****************
collections
note:sort() return a new list
****************/
function collections(){}
collections.sort=function(){
if(arguments.length==1){
 var s=new sortedlist();
 s.addall(arguments[0]);
 return s;
}
else if(arguments.length==2){
 var s=new sortedlist();
 s.setcomparator(arguments[1]);
 s.addall(arguments[0]);
 return s;
}
else 
 throw illegalargument;
}
/***************
arrays
****************/
function arrays(){}
arrays.aslist=function(arr){
return new arraylist(arr);
}
//listiterator
function listiterator(table,len){
   this.table=table;
this.len=len;                          
   this.index=0;
this.hasnext=function() {
 return this.index   }
this.next=function() { 
 if(!this.hasnext())
  throw no such element!;
 return this.table[this.index++];
   }
}
/********************
arraylist
********************/
function arraylist(){
this.buffer=new array();
if(arguments.length>0) this.buffer=arguments[0];
this.length=this.buffer.length;
}
arraylist.prototype.hashcode=function(){
var h=0;
for(var i=0;i h+=this.buffer[i].hashcode();
return h;
}
arraylist.prototype.size=function(){
return this.length;
}
arraylist.prototype.clear=function(){
for(var i=0;ithis.buffer.length=0;
this.length=0;
}
arraylist.prototype.isempty=function(){
return this.length==0;
}
arraylist.prototype.toarray=function(){
var copy=new array();
for(var i=0;i copy[i]=this.buffer[i];
}
return copy;
}
arraylist.prototype.get=function(index){
if(index>=0 && index return this.buffer[index];
return null;
}
arraylist.prototype.remove=function(param){
var index=0;
if(isnan(param)){
 index=this.indexof(param);
}
else index=param;
if(index>=0 && index for(var i=index;i  this.buffer[i]=this.buffer[i+1];
  this.length-=1;
  return true;
}
else return false;
}
arraylist.prototype.add=function(){
var args=arguments;
if(args.length==1){
 this.buffer[this.length++]=args[0];
 return true;
}
else if(args.length==2){
 var index=args[0];
 var obj=args[1];
 if(index>=0 && index  for(var i=this.length;i>index;i--)
   this.buffer[i]=this.buffer[i-1];
  this.buffer[i]=obj;
  this.length+=1;
  return true;
 }
}
return false;
}
arraylist.prototype.indexof=function(obj){
for(var i=0;i if(this.buffer[i].equals(obj)) return i;
}
return -1;
}
arraylist.prototype.lastindexof=function(obj){
for(var i=this.length-1;i>=0;i--){
 if(this.buffer[i].equals(obj)) return i;
}
return -1;
}
arraylist.prototype.contains=function(obj){
return this.indexof(obj)!=-1;
}
arraylist.prototype.equals=function(obj){
if(this.size()!=obj.size()) return false;
for(var i=0;i if(!obj.get(i).equals(this.buffer[i])) return false;
}
return true;
}
arraylist.prototype.addall=function(list){
var mod=false;
for(var it=list.iterator();it.hasnext();){
 var v=it.next();
 if(this.add(v)) mod=true;
}
return mod;  
}
arraylist.prototype.containsall=function(list){
for(var i=0;i if(!this.contains(list.get(i))) return false;
}
return true;
}
arraylist.prototype.removeall=function(list){
for(var i=0;i this.remove(this.indexof(list.get(i)));
}
}
arraylist.prototype.retainall=function(list){
for(var i=this.length-1;i>=0;i--){
 if(!list.contains(this.buffer[i])){
  this.remove(i);
 }
}
}
arraylist.prototype.sublist=function(begin,end){
if(beginif(end>this.length) end=this.length;
var newsize=end-begin;
var newbuffer=new array();
for(var i=0;i newbuffer[i]=this.buffer[begin+i];
}
return new arraylist(newbuffer);
}
arraylist.prototype.set=function(index,obj){
if(index>=0 && index temp=this.buffer[index];
 this.buffer[index]=obj;
 return temp;
}
}
arraylist.prototype.iterator=function iterator(){
return new listiterator(this.buffer,this.length);
}
/*****************************
sortedlist extends arraylist
*****************************/
function sortedlist(){
  this.com=null;
}
sortedlist.prototype=new arraylist();
sortedlist.prototype.setcomparator=function(comp){
if(this.length!=0) throw only can be set when list is empty;
this.com=comp;
}
sortedlist.prototype.getcomparator=function(){
return this.com;
}
//override
sortedlist.prototype.add=function(obj){
var index = this.indexof(obj);
for(var i=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) return 0;
var min=0,max=this.length-1;
var mid=0;
while(min  
 mid = (min+max) >> 1;
 var c=0;
 if(this.com==null) c=obj.compareto(this.buffer[mid]);
 else c=this.com.compare(obj,this.buffer[mid]);
if(c==0){
  return mid;
 }
 else if(c  max=mid-1;
 }
 else{
  min=mid+1;
 }
}
mid =(min+max) >>1;
return mid+1;
}
//override
sortedlist.prototype.contains=function(obj){
if(this.length==0) return false;
var min=0,max=this.length-1;
var mid=0;
while(min mid = (min+max) >> 1;
 var c=0;
 if(this.com==null) c=obj.compareto(this.buffer[mid]);
 else  c=this.com.compare(obj,this.buffer[mid]);
 if(c==0){
  return true;
 }
 else if(c  max=mid-1;
 }
 else{
  min=mid+1;
 }
}
return false;
}
//override
sortedlist.prototype.sublist=function(begin,end){
var sl=new sortedlist();
s1.setcomparator(this.com);
var sub=arraylist.prototype.sublist(begin.end);
sl.addall(sub);
return sl;
}
/****************************
hashmap
****************************/
function entry(h,k,v,n){
  this.value = v; 
  this.next = n;
  this.key = k;
  this.hash = h;
this.getkey=function(){
 return this.key;
  }
this.getvalue=function() {
 return this.value;
  }
  this.setvalue=function(newvalue) {
 var oldvalue = this.value;
 this.value = newvalue;
 return oldvalue;
  }
this.equals=function(o){
  var e = o;
  var k1 = this.getkey();
  var k2 = e.getkey();
  var v1 = this.getvalue();
  var v2 = e.getvalue();
  return (k1.equals(k2) && v1.equals(v2));
  }
this.hashcode=function() {
   return this.key.hashcode() ^ this.value.hashcode();
  }
this.tostring=function() {
 return this.getkey() + = + this.getvalue();
  }
}
function hashiterator(table,index,ne){
this.table=table;
this.ne=ne;                  
this.index=index;            
this.current=null;
this.hasnext=function() {
 return this.ne != null;
}
this.next=function() {
var e = this.ne;
 if (e == null) 
  throw no such element;
var n = e.next;
 var t = this.table;
 var i = this.index;
 while (n == null && i > 0)
  n = t[--i];
 this.index = i;
 this.ne = n;
 this.current=e;
return this.current;
}
}
function hashmap()
{
this.len=8;
this.table=new array();
this.length=0;
}
// refer to java.util.hashmap
hashmap.hash=function(x){
   var h = x.hashcode();
   h += ~(h    h ^=  (h >>> 14);
   h +=  (h    h ^=  (h >>> 10);
   return h;
}
hashmap.prototype.rehash=function(){       
   var oldtable = this.table;   
   this.table=new array();
//transfer        
   for (var i = 0; i       var e = oldtable[i];
       if (e != null) {
          oldtable[i] = null;
          do {
              var next = e.next;
              var j = this.indexfor(e.hash);  
              e.next = this.table[j];
              this.table[j] = e;
              e = next;
           } while (e != null);
       }
   }
}
hashmap.prototype.indexfor=function(h) {
var index= h & (this.len-1);
return index;
}
hashmap.prototype.size=function() {
return this.length;
}
hashmap.prototype.isempty=function() {
return this.length == 0;
}
hashmap.prototype.get=function(key) {
var hash =hashmap.hash(key);
var i = this.indexfor(hash);
var e = this.table[i];
while (true) {
 if (e ==null)
  return null;
 if (e.hash == hash && key.equals(e.key)) 
  return e.value;
 e = e.next;
}
}
hashmap.prototype.containskey=function(key) {
var hash =hashmap.hash(key);
var i = this.indexfor(hash);
var e = this.table[i];
while (e != null) {
 if (e.hash == hash && key.equals(e.key)) 
  return true;
 e = e.next;
}
return false;
}
hashmap.prototype.put=function(key,value) {
var hash = hashmap.hash(key);
var i = this.indexfor(hash);
for (var e = this.table[i]; e != null; e = e.next) {
 if (e.hash == hash && key.equals(e.key)) {
  var oldvalue = e.value;
  e.value = value;
  return oldvalue;
 }
}
this.addentry(hash, key, value, i);
var r=math.ceil(this.length * 1.5);
if(r > this.len){
 this.len= this.len  this.rehash();
}
return null;
}
hashmap.prototype.putall=function (map){
var mod=false;
for(var it=map.iterator();it.hasnext();){
 var e=it.next();
 if(this.put(e.getkey(),e.getvalue())) mod=true;
}
}
hashmap.prototype.remove=function(key) {
   var e = this.removeentryforkey(key); 
   return (e ==null ? null : e.value);
}
hashmap.prototype.removeentryforkey=function(key) {
var hash = hashmap.hash(key);
var i = this.indexfor(hash);
var prev = this.table[i];
var e = prev;
while (e != null) {
 var next = e.next;
 if (e.hash == hash && key.equals(e.key)) {
  this.length--;
  if (prev.equals(e)) 
   this.table[i] = next;
  else
   prev.next = next;
  return e;
 }
 prev = e;
 e = next;
}
return e;
}
hashmap.prototype.clear=function() {
   for (var i = 0; i        this.table[i] = null;
   this.length = 0;
}
hashmap.prototype.containsvalue=function(value) {
if (value == null) return false;
var tab = this.table;
for (var i = 0; i  for (var e = tab[i] ; e != null ; e = e.next)
  if (value.equals(e.value))
   return true;
return false;
}
hashmap.prototype.addentry=function(hash, key, value, bucketindex) {
this.table[bucketindex] = new entry(hash, key, value, this.table[bucketindex]);
this.length++;
}
hashmap.prototype.iterator=function(){
var i=this.table.length;
var next=null;
while(i>0 && next==null){
 next=this.table[--i];
}
return new hashiterator(this.table,i,next);
}
hashmap.prototype.hashcode=function(){
var h=0;
for(var it=this.iterator();it.hasnext();){
 h+=it.next().hashcode();
}
return h;
}
hashmap.prototype.equals=function(map){
if(!this.typematches(map)) return false;
if(map.size()!=this.size()) return false;
for(var it=this.iterator();it.hasnext();){ 
 var e=it.next();
 var key=e.getkey();
 var value=e.getvalue();
if(!value.equals(map.get(key))) return false
}
return true;
}
/*************************
hashset
**************************/
function hashsetiterator(ite){
   this.it=ite;
this.hasnext=function() {
 return this.it.hasnext();
   }
this.next=function() { 
 return this.it.next().getkey();
   }
}
function hashset(){  
this.map=new hashmap();
}
hashset.null=new number(!this is null!);
hashset.prototype.size=function(){
return this.map.size();
}
hashset.prototype.isempty=function() {
return this.map.isempty();
}
hashset.prototype.contains=function(o) {
return this.map.containskey(o);
}
hashset.prototype.add=function(o){
return this.map.put(o,hashset.null)==null;
}
hashset.prototype.addall=function(set){
var mod=false;
for(var it=set.iterator();it.hasnext();){
 if(this.add(it.next())) mod=true;
}
return mod;
}
hashset.prototype.remove=function(o) {
return this.map.remove(o).equals(hashset.null);
}
hashset.prototype.clear=function() {
this.map.clear();
}
hashset.prototype.iterator=function(){
return new hashsetiterator(this.map.iterator());
}
hashset.prototype.equals=function(o) {
if(!this.typematches(o)) return false;
if (o.size() != this.size()) return false;
for(var it=this.iterator();it.hasnext();){
 if(!o.contains(it.next())) return false;
}
return true;
}
hashset.prototype.hashcode=function() {
var h=0;
for(var it=this.iterator();it.hasnext();){
 h+=it.next().hashcode();
}
return h;
}
hashset.prototype.toarray=function(){
var arr=new array();
var i=0;
for(var it=this.iterator();it.hasnext();){
 arr[i++]=it.next();
}
return arr;
}