javascript函数库-集合框架_javascript技巧

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.len;
   }

   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<this.lengh;i++)
 h+=this.buffer[i].hashCode();
return h;
}

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

ArrayList.prototype.clear=function(){
for(var i=0;i<this.length;i++) this.buffer[i]=null;
this.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<this.length;i++){
 copy[i]=this.buffer[i];
}
return copy;
}
ArrayList.prototype.get=function(index){
if(index>=0 && index<this.length)
 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<this.length){
 for(var i=index;i<this.length-1;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<=this.length){
  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<this.length;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<this.length;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<list.size();i++){
 if(!this.contains(list.get(i))) return false;
}
return true;
}

ArrayList.prototype.removeAll=function(list){
for(var i=0;i<list.size();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(begin<0) begin=0;
if(end>this.length) end=this.length;
var newsize=end-begin;
var newbuffer=new Array();
for(var i=0;i<newsize;i++){
 newbuffer[i]=this.buffer[begin+i];
}
return new ArrayList(newbuffer);
}
ArrayList.prototype.set=function(index,obj){
if(index>=0 && index<this.length){
 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<=max){
  
 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<0){
  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<=max){
 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<0){
  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 << 9);
   h ^=  (h >>> 14);
   h +=  (h << 4);
   h ^=  (h >>> 10);
   return h;
}

HashMap.prototype.rehash=function(){       
   var oldTable = this.table;   
   this.table=new Array();
       
//transfer        
   for (var i = 0; i< oldTable.length; 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 << 1;
 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.length; 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 < tab.length ; 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;
}

时间： 2024-09-18 16:05:34

javascript函数库-集合框架_javascript技巧的相关文章

通用javascript脚本函数库 方便开发_javascript技巧

将下面代码保存为Common.js 类库功能: 1.Trim(str)--去除字符串两边的空格 2.XMLEncode(str)--对字符串进行XML编码 3.ShowLabel(str,str)--鼠标提示功能(显示字符,提示字符) 可以设置显示的提示的文字的字体.颜色.大小以及提示的背景颜色.边框等 4.IsEmpty(obj)--验证输入框是否为空 5.IsInt(objStr,sign,zero)--验证是否为整数,正整数,负整数,以及是否包括零 6.IsFloat(objStr,sig

JavaScript 常用函数库详解_javascript技巧

为此,收集了自己平时常用到一些JavaScript函数,它们在其它的JS库也常见,现在整理并附上注释,方便查阅,希望对大家有所帮助.注:假设以下所有函数都放在一个CC对象中,方便引用. 复制代码 代码如下: //这个方法相信是最常用的了, //它虽然没有选择器那么强大,但也有个小增强版,可查指定结点下ID所在的子元素 function $(id, p) { //id是否是字符串,还是一个HTML结点 var iss = id instanceof String || typeof id == "

JavaScript 函数的执行过程_javascript技巧

1. 每一个JavaScript函数都是Function对象的一个实例, 它有一个仅供JavaScript引擎存取的内部属性[[Scope]]. 这个[[Scope]]存储着一个作用域的集合, 这个集合就叫"作用域链", 集合中存储着"可变对象"VO或"活动对象"AO(AO比VO多this和arguments属性). 2. 当函数被创建后, 其父级作用域的作用域链中的所有可变对象会被加入到它的[[scope]]中(如果父作用域是全局, 那么当前函

浅析JavaScript函数的调用模式_javascript技巧

我们说一个函数的调用模式是作为一个函数来调用,是要与其它三种调用模式做区分 函数其他的三种调用: 方法调用模式,构造器调用模式,apply/call调用模式.  方法的调用模式:  var obj={ fun1: function(){ //方法内容 this; //指的是window } } obj.fun1() //方法的调用 构造器的调用:  function Person(name, age, job){ this.name = name; this.age = age; this.jo

javascript函数特点实例分析_javascript技巧

本文实例分析了javascript函数特点.分享给大家供大家参考.具体分析如下: <html xmlns="http://www.w3.org/1999/xhtml"> <head> <meta http-equiv="Content-Type" content="text/html; charset=utf-8" /> <title>javascript函数特点(重要)</title>

myEvent.js javascript跨浏览器事件框架_javascript技巧

event究竟有多么复杂?可见前辈的6年前的努力:最佳的addEvent是怎样诞生的,后起之秀jQuery也付出了一千六百多行血汗代码(v 1.5.1)搞定了6年后出现的各种核的浏览器. 我参考前辈的代码以及自己的理解尝试写了一个事件框架,我的框架完成了一个事件机制的核心,它能提供统一接口实现多事件绑定以及避免内存泄漏等其他一些问题,更重要的是性能还不错. 我的手法: 所有回调函数根据元素.事件类型.回调函数唯一ID缓存在一个_create对象中(其内部具体结构可见下面源码的关于_cache的注

JavaScript 函数replace深入了解_javascript技巧

replace函数接受两个参数,第一个参数为字符串或正则表达式,第一个参数同样可以接受一个字符串,还可能是一个函数.       首先对于第一个参数为字符串的我们不再需要多说"I am a boy".replace("boy","girl"),输出:"I am a girl".在这里想说的是第一个参数为正则的情形.对于正则表达式来说首先会根据是否全局的(全局//g)决定替换行为,如果是全部的则替换全部替换,非全局的只有替换首个

深入理解javascript函数参数与闭包_javascript技巧

最近在学习javascript的函数,函数是javascript的一等对象,想要学好javascript,就必须深刻理解函数.本人把学习的过程整理成文章,一是为了加深自己函数的理解,二是给读者提供学习的途径,避免走弯路.内容有些多,但都是笔者对于函数的总结. 1.函数参数 1.1:参数是什么 1.2:参数的省略 1.3:参数默认值 1.4:参数传递方式 1.5:同名参数 1.6:arguments对象 2.闭包 2.1:闭包定义 2.2:立即调用的函数表达式(IIFE, Immediately

浅谈javascript 函数属性和方法_javascript技巧

        每个函数都包含两个属性:length 和 prototype         length:当前函数希望接受的命名参数的个数         prototype:是保存他们所有实力方法的真正所在 复制代码 代码如下:         function sayName(name) {             alert(name);         }         function sum(num1, num2) {             return num1 + num2