1 /** 
  2  * JET (Javascript Extension Tools) 
  3  * Copyright (c) 2009, KDV.cn, All rights reserved.
  4  * Code licensed under the BSD License:
  5  * http://developer.kdv.cn/jet/license.txt
  6  *
  7  * @fileOverview Jx!
  8  * @version 1.0
  9  * @author  Kinvix(<a href="mailto:Kinvix@gmail.com">Kinvix@gmail.com</a>)
 10  * @description 
 11  * 
 12  */
 13 
 14 /** 
 15  * @description
 16  * Package: jx.array
 17  *
 18  * Need package:
 19  * jx.core.js
 20  * 
 21  */
 22 
 23 /**
 24  * 4.[Javascript core]: array 数组处理
 25  */
 26 Jx().$package(function(J){
 27     
 28     /**
 29      * array 名字空间
 30      * 
 31      * @namespace
 32      * @name array
 33      */
 34     J.array = J.array || {};
 35     var $A = J.array,
 36         // javascript1.6扩展
 37         indexOf,
 38         lastIndexOf,
 39         forEach,
 40         filter,
 41         some,
 42         map,
 43         every,
 44         // javascript1.8扩展
 45         reduce,
 46         reduceRight,
 47         
 48         // JET扩展
 49         toArray,
 50         remove,
 51         replace,
 52         bubbleSort,
 53         binarySearch,
 54         
 55         //集合的操作
 56         contains,
 57         uniquelize,
 58         intersect,
 59         minus,
 60         union;
 61     
 62     
 63     
 64     /**
 65      * 正向查找数组元素在数组中的索引下标
 66      * 
 67      * @link http://developer.mozilla.org/en/docs/Core_JavaScript_1.5_Reference:Objects:Array:indexOf
 68      * @memberOf array
 69      * @function
 70      * 
 71      * @param {Array} arr 要执行操作的数组
 72      * @param {Object} obj 要查找的数组的元素
 73      * @param {Number} fromIndex 开始的索引编号
 74      * 
 75      * @return {Number}返回正向查找的索引编号
 76      */
 77     indexOf = Array.prototype.indexOf 
 78         ? function(){
 79             var args = Array.prototype.slice.call(arguments, 1);
 80             return Array.prototype.indexOf.apply(arguments[0], args);
 81         }
 82         : function (arr, obj, fromIndex) {
 83     
 84             if (fromIndex == null) {
 85                 fromIndex = 0;
 86             } else if (fromIndex < 0) {
 87                 fromIndex = Math.max(0, arr.length + fromIndex);
 88             }
 89             for (var i = fromIndex; i < arr.length; i++) {
 90                 if (arr[i] === obj){
 91                     return i;
 92                 }
 93             }
 94             return -1;
 95         };
 96     
 97     
 98         
 99     /**
100      * 反向查找数组元素在数组中的索引下标
101      * 
102      * @link http://developer.mozilla.org/en/docs/Core_JavaScript_1.5_Reference:Objects:Array:lastIndexOf
103      * @memberOf array
104      * @function
105      * 
106      * @param {Array} arr 要执行操作的数组
107      * @param {Object} obj 要查找的数组元素
108      * @param {Number} fromIndex 开始的索引编号
109      * 
110      * @return {Number}返回反向查找的索引编号
111      */
112     lastIndexOf = Array.prototype.lastIndexOf 
113         ? function(){
114             var args = Array.prototype.slice.call(arguments, 1);
115             return Array.prototype.lastIndexOf.apply(arguments[0], args);
116         }
117         : function (arr, obj, fromIndex) {
118             if (fromIndex == null) {
119                 fromIndex = arr.length - 1;
120             } else if (fromIndex < 0) {
121                 fromIndex = Math.max(0, arr.length + fromIndex);
122             }
123             for (var i = fromIndex; i >= 0; i--) {
124                 if (arr[i] === obj){
125                     return i;
126                 }
127             }
128             return -1;
129         };
130     
131     
132 
133     
134     
135     /**
136      * 遍历数组，把每个数组元素作为第一个参数来执行函数
137      * 
138      * @link http://developer.mozilla.org/en/docs/Core_JavaScript_1.5_Reference:Global_Objects:Array:forEach
139      * @memberOf array
140      * @function
141      * 
142      * @param {Array} arr 要执行操作的数组
143      * @param {Function} fun 要执行的函数
144      * @param {Object} contextObj 执行函数时的上下文对象，可以省略
145      * 
146      */
147     forEach = Array.prototype.forEach 
148         ? function(){
149             var args = Array.prototype.slice.call(arguments, 1);
150             return Array.prototype.forEach.apply(arguments[0], args);
151         }
152         : function(arr, fun /*, thisp*/) {
153             var len = arr.length;
154             if (typeof fun != "function") {
155                 throw new TypeError();
156             }
157             var thisp = arguments[2];
158             for (var i = 0; i < len; i++) {
159                 if (i in arr) {
160                     fun.call(thisp, arr[i], i, arr);
161                 }
162             }
163         };
164     
165     /**
166      * 用一个自定义函数来过滤数组
167      * 
168      * @link http://developer.mozilla.org/en/docs/Core_JavaScript_1.5_Reference:Global_Objects:Array:filter
169      * @memberOf array
170      * @function
171      * 
172      * @param {Array} arr 要执行操作的数组
173      * @param {Function} fun 过滤函数
174      * @param {Object} contextObj 执行函数时的上下文对象，可以省略
175      * 
176      * @return {Array}返回筛选出的新数组
177      */
178     filter = Array.prototype.filter 
179         ? function(){
180             var args = Array.prototype.slice.call(arguments, 1);
181             return Array.prototype.filter.apply(arguments[0], args);
182         }
183         : function(arr, fun) {
184             var len = arr.length;
185             if (typeof fun != "function") {
186               throw new TypeError();
187             }
188             var res   = [];
189             var thisp = arguments[2];
190             for (var i = 0; i < len; i++) {
191                 if (i in arr) {
192                     var val = arr[i]; // in case fun mutates this
193                     if (fun.call(thisp, val, i, arr)) {
194                         res.push(val);
195                     }
196                 }
197             }
198             return res;
199         };
200     
201     
202     
203 
204 
205     
206     /**
207      * 遍历数组，把每个数组元素作为第一个参数来执行函数，如果有任意一个或多个数组成员使得函数执行结果返回 true，则最终返回 true，否则返回 false
208      * 
209      * @link http://developer.mozilla.org/en/docs/Core_JavaScript_1.5_Reference:Global_Objects:Array:some
210      * @memberOf array
211      * @function
212      * 
213      * @param {Array} arr 要执行操作的数组
214      * @param {Function} fun 要执行的函数
215      * @param {Object} contextObj 执行函数时的上下文对象，可以省略
216      * 
217      * @return {Boolean}
218      */
219     some = Array.prototype.some 
220         ? function(){
221             var args = Array.prototype.slice.call(arguments, 1);
222             return Array.prototype.some.apply(arguments[0], args);
223         }
224         : function(arr, fun /*, thisp*/) {
225             var len = arr.length;
226             if (typeof fun != "function") {
227                 throw new TypeError();
228             }
229     
230             var thisp = arguments[2];
231             for (var i = 0; i < len; i++) {
232                 if (i in arr && fun.call(thisp, arr[i], i, arr)) {
233                     return true;
234                 }
235             }
236     
237             return false;
238         };
239     
240 
241     /**
242      * 遍历数组，把每个数组元素作为第一个参数来执行函数，并把函数的返回结果以映射的方式存入到返回的数组中
243      * 
244      * @link http://developer.mozilla.org/en/docs/Core_JavaScript_1.5_Reference:Global_Objects:Array:map
245      * @memberOf array
246      * @function
247      * 
248      * @param {Array} arr 要执行操作的数组
249      * @param {Function} fun 要执行的函数
250      * @param {Object} contextObj 执行函数时的上下文对象，可以省略
251      * 
252      * @return {Array}返回映射后的新数组
253      */
254     map = Array.prototype.map 
255         ? function(){
256             var args = Array.prototype.slice.call(arguments, 1);
257             return Array.prototype.map.apply(arguments[0], args);
258         }
259         : function(arr, fun /*, thisp*/) {
260             var len = arr.length;
261             if (typeof fun != "function") {
262                 throw new TypeError();
263             }
264             var res   = new Array(len);
265             var thisp = arguments[2];
266             for (var i = 0; i < len; i++) {
267                 if (i in arr) {
268                     res[i] = fun.call(thisp, arr[i], i, arr);
269                 }
270             }
271     
272             return res;
273         };
274     
275     
276     /**
277      * 遍历数组，把每个数组元素作为第一个参数来执行函数，如果所有的数组成员都使得函数执行结果返回 true，则最终返回 true，否则返回 false
278      * 
279      * @link http://developer.mozilla.org/en/docs/Core_JavaScript_1.5_Reference:Objects:Array:every
280      * @memberOf array
281      * @function
282      * 
283      * @param {Array} arr 要执行操作的数组
284      * @param {Function} fun 要执行的函数
285      * @param {Object} contextObj 执行函数时的上下文对象，可以省略
286      * 
287      * @return {Boolean}
288      */
289     every = Array.prototype.every 
290         ? function(){
291             var args = Array.prototype.slice.call(arguments, 1);
292             return Array.prototype.every.apply(arguments[0], args);
293         }
294         : function(arr, fun) {
295             var len = arr.length;
296             if (typeof fun != "function") {
297                 throw new TypeError();
298             }
299             var thisp = arguments[2];
300             for (var i = 0; i < len; i++) {
301                 if (i in arr && !fun.call(thisp, arr[i], i, arr)) {
302                     return false;
303                 }
304             }
305             return true;
306         };
307     
308     
309     
310     
311     
312     /**
313      * 对该数组的每项和前一次调用的结果运行一个函数，收集最后的结果。
314      * 
315      * @link http://developer.mozilla.org/en/docs/Core_JavaScript_1.8_Reference:Objects:Array:reduce
316      * @memberOf array
317      * @function
318      * 
319      * @param {Array} arr 要执行操作的数组
320      * @param {Function} fun 要执行的函数
321      * @param {Object} contextObj 执行函数时的上下文对象，可以省略
322      * 
323      * @return {Boolean}
324      */
325     reduce = Array.prototype.reduce 
326         ? function(){
327             var args = Array.prototype.slice.call(arguments, 1);
328             return Array.prototype.reduce.apply(arguments[0], args);
329         }
330         : function(arr, fun /*, initial*/){
331             var len = arr.length >>> 0;
332             if (typeof fun != "function"){
333                 throw new TypeError();
334             }
335             // no value to return if no initial value and an empty array
336             if (len == 0 && arguments.length == 2){
337                 throw new TypeError();
338             }
339             var i = 0;
340             if (arguments.length >= 3){
341                 var rv = arguments[2];
342             }
343             else{
344                 do{
345                     if (i in arr){
346                       rv = arr[i++];
347                       break;
348                     }
349                 
350                     // if array contains no values, no initial value to return
351                     if (++i >= len){
352                         throw new TypeError();
353                     }
354                 }
355                 while (true);
356             }
357             
358             for (; i < len; i++){
359                 if (i in arr){
360                     rv = fun.call(null, rv, arr[i], i, arr);
361                 }
362             }
363             
364             return rv;
365         };
366     
367     
368     
369     /**
370      * 同上，但从右向左执行。
371      * 
372      * @link http://developer.mozilla.org/en/docs/Core_JavaScript_1.8_Reference:Objects:Array:reduceRight
373      * @memberOf array
374      * @function
375      * 
376      * @param {Array} arr 要执行操作的数组
377      * @param {Function} fun 要执行的函数
378      * @param {Object} contextObj 执行函数时的上下文对象，可以省略
379      * 
380      * @return {Boolean}
381      */
382     reduceRight = Array.prototype.reduceRight 
383         ? function(){
384             var args = Array.prototype.slice.call(arguments, 1);
385             return Array.prototype.reduceRight.apply(arguments[0], args);
386         }
387         : function(arr, fun /*, initial*/){
388             var len = arr.length >>> 0;
389             if (typeof fun != "function"){
390                 throw new TypeError();
391             }
392             // no value to return if no initial value, empty array
393             if (len == 0 && arguments.length == 2){
394                 throw new TypeError();
395             }
396             var i = len - 1;
397             if (arguments.length >= 3){
398                 var rv = arguments[2];
399             }
400             else{
401                 do{
402                     if (i in arr){
403                         rv = arr[i--];
404                         break;
405                     }
406             
407                     // if array contains no values, no initial value to return
408                     if (--i < 0){
409                         throw new TypeError();
410                     }
411                 }
412                 while(true);
413             }
414             
415             for (; i >= 0; i--){
416                 if (i in arr){
417                     rv = fun.call(null, rv, arr[i], i, arr);
418                 }
419             }
420             
421             return rv;
422         };
423 
424     
425     
426     
427     /**
428      * 将任意变量转换为数组的方法
429      * 
430      * @memberOf array
431      * @param {Mixed} o 任意变量
432      * @return {Array} 返回转换后的数组
433      */
434     toArray = function(o){
435         var type = J.$typeof(o);
436         return (type) ? ((type != 'array' && type != 'arguments') ? [o] : o) : [];
437     };
438     
439     
440     
441     
442     /**
443      * 从数组中移除一个或多个数组成员
444      * 
445      * @memberOf array
446      * @param {Array} arr 要移除的数组成员，可以是单个成员也可以是成员的数组
447      * @return {Boolean} 找到并移除, 返回 true
448      */
449     remove = function(arr, members){
450         var members = toArray(members),
451             i,
452             j,
453             flag = false;
454         for(i=0; i<members.length; i++){
455             for(j=0; j<arr.length; j++){
456                 if(arr[j] === members[i]){
457                     arr.splice(j,1);
458                     flag = true;
459                 }
460             }
461         }
462         return flag;
463     };
464     
465     /**
466      * 替换一个数组成员
467      * 
468      * @memberOf array
469      * @param {Object} oldValue 当前数组成员
470      * @param {Object} newValue 要替换成的值
471      * @return {Boolean} 如果找到旧值并成功替换则返回 true，否则返回 false
472      */
473     replace = function(arr, oldValue, newValue){
474         var i;
475         for(i=0; i<arr.length; ij++){
476             if(arr[i] === oldValue){
477                 arr[i] = newValue;
478                 return true;
479             }
480         }
481         return false;
482     };
483     
484     /**
485      * 冒泡排序,默认从小到大排序
486      * @memberOf array
487      * @param {Array} arr 需要排序的数组
488      * @param {Function} compareFunc 比较方法, 传入两个参数 a,b, 若返回 大于0 则表示 a > b, 小于 0 则 a < b
489      *  可选, 默认返回 a - b的结果
490      * @return {Array} 排序后的数组
491      * @example
492      * 
493      * bubbleSort([3,5,6,2], function(a, b){
494      *  return a - b;
495      * });
496      * 
497      */
498     bubbleSort = function(arr, compareFunc) {
499         compareFunc = compareFunc || function(num1, num2){
500             return num1 - num2;
501         };
502         //数组长度
503         var n = arr.length;
504         //交换顺序的临时变量
505         var temp;//
506         //交换标志
507         var exchange;
508         //最多做n-1趟排序
509         for (var time=0; time<n-1; time++){
510             exchange = false;
511             for (var i=n-1; i>time; i--) {
512                 if (compareFunc(arr[i], arr[i - 1]) < 0) {
513                 //if (arr[i] < arr[i - 1]) {
514                     exchange = true;
515                     temp = arr[i - 1];
516                     arr[i - 1] = arr[i];
517                     arr[i] = temp;
518                 }
519             }
520             //若本趟排序未发生交换，提前终止算法
521             if (!exchange) {
522                 break;
523             }
524         }
525         return arr;
526     };
527     
528     /**
529      * 二叉搜索
530      * @memberOf array
531      * @param {Array} arr 源数组
532      * @param {Object} item 查找的目标
533      * @param {Function} compareFunc 比较方法, 传入两个参数 a,b, 若返回 大于0 则表示 a > b, 小于 0 则 a < b
534      * @return {Number} item 所处的 index
535      * 
536      */
537     binarySearch = function(arr, item, compareFunc){
538         var start = 0;
539         var end = arr.length;
540         var current = Math.floor(arr.length/2);
541         while(end != current){
542             if(compareFunc(item, arr[current]) > 0){
543                 start = current + 1;
544             }
545             else{
546                 end = current;
547             };
548     
549             current = Math.floor((start + end) / 2);
550         };
551         return current;
552     };
553     
554     /**
555      * 判断arr是否包含元素o
556      * @memberOf array
557      * @name contains
558      * @function
559      * @param {Array} arr
560      * @param {Obejct} o
561      * @return {Boolean}
562      */
563     contains = function(arr, o){
564         return (indexOf(arr, o) > -1);
565     };
566     
567     /**
568      * 唯一化一个数组
569      * @memberOf array
570      * @param {Array} arr
571      * @return {Array} 由不重复元素构成的数组
572      */
573     uniquelize = function(arr){
574         var result = [];
575         for(var i = 0, len = arr.length; i < len; i++){
576             if(!contains(result, arr[i])){
577                 result.push(arr[i]);
578             }
579         }
580         return result;
581     };
582     
583     /**
584      * 求两个集合的交集
585      * a ∩ b
586      * @memberOf array
587      * @param {Array} a
588      * @param {Array} b
589      * @return {Array} a ∩ b
590      */
591     intersect = function(a, b){
592         var result = [];
593         for(var i = 0, len = a.length; i < len; i++){
594             if(contains(b, a[i])){
595                 result.push(a[i]);
596             }
597         }
598         return result;
599     };
600     
601     /**
602      * 求两个集合的差集
603      * a - b
604      * @memberOf array
605      * @param {Array} a
606      * @param {Array} b
607      * @return {Array} a - b
608      */
609     minus = function(a, b){
610         var result = [];
611         for(var i = 0, len = a.length; i < len; i++){
612             if(!contains(b, a[i])){
613                 result.push(a[i]);
614             }
615         }
616         return result;
617     };
618     
619     /**
620      * 求两个集合的并集
621      * a U b
622      * @memberOf array
623      * @param {Array} a
624      * @param {Array} b
625      * @return {Array} a U b
626      */
627     union = function(a, b){
628         return uniquelize(a.concat(b));
629     };
630     
631     $A.indexOf = indexOf;
632     $A.lastIndexOf = lastIndexOf;
633     $A.forEach = forEach;
634     $A.filter = filter;
635     $A.some = some;
636     $A.map = map;
637     $A.every = every;
638     $A.reduce = reduce;
639     $A.reduceRight = reduceRight;
640 
641     $A.toArray = toArray;
642     $A.remove = remove;
643     $A.replace = replace;
644     $A.bubbleSort = bubbleSort;
645     $A.binarySearch = binarySearch;
646     
647     $A.contains = contains;
648     $A.uniquelize = uniquelize;
649     $A.intersect = intersect;
650     $A.minus = minus;
651     $A.union = union;
652     
653 });
654 
655 
656 
657 
658 
659 
660 
661 
662