//This JavaScript library is copyright 2002 by Gavin Kistner and Refinery, Inc. 
//Reuse or modification permitted provided the previous line is included. 
//mailto:gavin@refinery.com 
//http://www.refinery.com/ 

/***************************************************************************************************
* JavaScript Array Set Mathematics Library
* version 1.2.1, April 26th, 2002  [IEMac5.1-/IEWin5.0-/OldNS .splice() replacement works properly] 
*
* Methods: array1.union( array2 [,compareFunction] ) 
*          array1.subtract( array2 [,compareFunction] ) 
*          array1.intersect( array2 [,compareFunction] ) 
*          array1.exclusion( array2 [,compareFunction] ) 
*          array1.removeDuplicates( [compareFunction] ) 
*
*          array1.unsortedUnion( array2 [,compareFunction] ) 
*          array1.unsortedSubtract( array2 [,compareFunction] ) 
*          array1.unsortedIntersect( array2 [,compareFunction] ) 
*          array1.unsortedExclusion( array2 [,compareFunction] ) 
*          array1.unsortedRemoveDuplicates( [compareFunction] ) 
*
*
* Notes:   All methods return a 'set' Array where duplicates have been removed.
*
*          The union(), subtract(), intersect(), and removeDuplicates() methods
*          are faster than their 'unsorted' counterparts, but return a sorted set:
*          var a = ['a','e','c'];
*          var b = ['b','c','d'];
*          a.unsortedUnion(b)  -->  'a','e','c','b','d' 
*          a.union(b)          -->  'a','b','c','d','e' 
*
*          Calling any of the methods on an array whose element pairs cannot all be
*          reliably ordered (objects for which a < b, a > b, and a==b ALL return false) 
*          will produce inaccurate results UNLESS the (usually) optional
*          'compareFunction' parameter is passed. This should specify a custom
*          comparison function, as required by the standard Array.sort(myFunc) method
*          For example:
*          var siblings = [ {name:'Dain'} , {name:'Chandra'} , {name:'Baird'} , {name:'Linden'} ];
*          var brothers = [ {name:'Dain'} , {name:'Baird'} ];
*          function compareNames(a,b){ return (a.name < b.name)?-1:(a.name > b.name)?1:0 } 
*          var sisters=siblings.unsortedSubtract(brothers, compareNames);
*
***************************************************************************************************/ 


if (Array.prototype.splice && typeof([0].splice(0))=="number") Array.prototype.splice = null;
if (!Array.prototype.splice) Array.prototype.splice = function(ind,cnt){ 
   var len = this.length;
   var arglen = arguments.length;
   if (arglen==0) return ind;
   if (typeof(ind)!= "number") ind = 0;
   else if (ind<0) ind = Math.max(0,len+ind);
   if (ind>len){ 
      if(arglen>2) ind=len;
      else return [];
   } 
   if (arglen<2) cnt = len-ind;
   cnt = (typeof(cnt)=="number") ? Math.max(0,cnt) : 0;
   var removeArray = this.slice(ind,ind+cnt);
   var endArray = this.slice(ind+cnt);
   len = this.length = ind;
   for (var i=2;i<arglen;i++) this[len++] = arguments[i];
   for (var i=0,endlen=endArray.length;i<endlen;i++) this[len++] = endArray[i];
   return removeArray;
} 

//*** SORTED IMPLEMENTATIONS *************************************************** 
Array.prototype.union=function(a2,compareFunction){ 
   return this.concat(a2?a2:null).removeDuplicates(compareFunction);
} 
Array.prototype.subtract=function(a2,compareFunction){ 
   if (!compareFunction) compareFunction=null;
   var a1=this.removeDuplicates(compareFunction);
   if (!a2) return a1;
   var a2=a2.removeDuplicates(compareFunction);
   var len2=a2.length;
   if (compareFunction){ 
      for (var i=0;i<a1.length;i++){ 
         var src=a1[i],found=false,src;
         for (var j=0;j<len2&&compareFunction(src2=a2[j],src)!=1;j++) if (compareFunction(src,src2)==0) { found=true; break; } 
         if (found) a1.splice(i--,1);
      } 
   }else{ 
      for (var i=0;i<a1.length;i++){ 
         var src=a1[i],found=false,src;
         for (var j=0;(j<len2)&&(src>=(src2=a2[j]));j++) if (src2==src) { found=true; break; } 
         if (found) a1.splice(i--,1);
      } 
   } 
   return a1;
} 
Array.prototype.intersect=function(a2,compareFunction){ 
   if (!compareFunction) compareFunction=null;
   var a1=this.removeDuplicates(compareFunction);
   if (!a2) return a1;
   var a2=a2.removeDuplicates(compareFunction);
   var len2=a2.length;
   if (len2<a1.length){ 
      var c=a2; a2=a1; a1=c; c=null;
      len2=a2.length;
   } 
   if (compareFunction){ 
      for (var i=0;i<a1.length;i++){ 
         var src=a1[i],found=false,src;
         for (var j=0;j<len2&&compareFunction(src2=a2[j],src)!=1;j++) if (compareFunction(src,src2)==0) { found=true; break; } 
         if (!found) a1.splice(i--,1);
      } 
   }else{ 
      for (var i=0;i<a1.length;i++){ 
         var src=a1[i],found=false,src;
         for (var j=0;(j<len2)&&(src>=(src2=a2[j]));j++) if (src2==src) { found=true; break; } 
         if (!found) a1.splice(i--,1);
      } 
   } 
   return a1;
} 
Array.prototype.removeDuplicates=function(compareFunction){ 
   if (!compareFunction) compareFunction=null;
   var a1=this.concat().sort(compareFunction);
   if (compareFunction){ 
      for (var i=0;i<a1.length;i++){ 
         var src=a1[i];
         for (var j=i+1;j<a1.length&&compareFunction(a1[j],src)==0;j++){} 
         if (j-1>i) a1.splice(i+1,j-i-1);
      } 
   }else{ 
      for (var i=0;i<a1.length;i++){ 
         var src=a1[i];
         for (var j=i+1;j<a1.length&&a1[j]==src;j++){} 
         if (j-1>i) a1.splice(i+1,j-i-1);
      } 
   } 
   return a1;
} 
Array.prototype.exclusion=function(a2,compareFunction){ 
   if (!compareFunction) compareFunction=null;
   var a1=this.removeDuplicates(compareFunction);
   if (!a2) return a1;
   return a1.subtract(a2,compareFunction).concat(a2.subtract(a1,compareFunction)).sort(compareFunction);
} 

//*** UNSORTED IMPLEMENTATIONS ************************************************* 
Array.prototype.unsortedUnion=function(a2,compareFunction){ 
   if (!compareFunction) compareFunction=null;
   return this.concat(a2?a2:null).unsortedRemoveDuplicates(compareFunction);
} 
Array.prototype.unsortedSubtract=function(a2,compareFunction){ 
   if (!compareFunction) compareFunction=null;
   var a1=this.unsortedRemoveDuplicates(compareFunction);
   if (!a2) return a1;
   var subtrahend=a2.unsortedRemoveDuplicates(compareFunction);
   if (compareFunction){ 
      for (var i=0;i<a1.length;i++){ 
         var src=a1[i];
         for (var j=0,len=subtrahend.length;j<len;j++) if (compareFunction(subtrahend[j],src)==0) { a1.splice(i--,1); break; } 
      } 
   }else{ 
      for (var i=0;i<a1.length;i++){ 
         var src=a1[i];
         for (var j=0,len=subtrahend.length;j<len;j++) if (subtrahend[j]==src) { a1.splice(i--,1); break; } 
      } 
   } 
   return a1;
} 
Array.prototype.unsortedIntersect=function(a2,compareFunction){ 
   if (!compareFunction) compareFunction=null;
   if (!a2) return this.unsortedRemoveDuplicates(compareFunction);
   var a1=this;
   var len2=a2.length;
   a1=a1.unsortedRemoveDuplicates(compareFunction);
   if (compareFunction){ 
      for (var i=0;i<a1.length;i++){ 
         var src=a1[i];
         for (var j=0;j<len2;j++) if (compareFunction(a2[j],src)==0) break;
         if (j==len2) a1.splice(i--,1);
      } 
   }else{ 
      for (var i=0;i<a1.length;i++){ 
         var src=a1[i];
         for (var j=0;j<len2;j++) if (a2[j]==src) break;
         if (j==len2) a1.splice(i--,1);
      } 
   } 
   return a1;
} 
Array.prototype.unsortedRemoveDuplicates=function(compareFunction){ 
   var a1=this.concat();
   if (compareFunction){ 
      for (var i=0;i<a1.length;i++){ 
         var src=a1[i];
         for (var j=i+1;j<a1.length;j++) if (compareFunction(a1[j],src)==0) a1.splice(j,1);
      } 
   }else{ 
      for (var i=0;i<a1.length;i++){ 
         var src=a1[i];
         for (var j=i+1;j<a1.length;j++) if (a1[j]==src) a1.splice(j--,1);
      } 
   } 
   return a1;
} 
Array.prototype.unsortedExclusion=function(a2,compareFunction){ 
   if (!compareFunction) compareFunction=null;
   var a1=this.unsortedRemoveDuplicates(compareFunction);
   if (!a2) return a1;
   return a1.unsortedSubtract(a2,compareFunction).concat(a2.unsortedSubtract(a1,compareFunction)).sort(compareFunction);
}