Bug 435739 Poor performance of Firefox 3 with no X RENDER extension
[wine-gecko.git] / testing / mochitest / MochiKit / Iter.js
blobbb3767de94034f9b720680bb36bad62e83a157d3
1 /***
3 MochiKit.Iter 1.4
5 See <http://mochikit.com/> for documentation, downloads, license, etc.
7 (c) 2005 Bob Ippolito.  All rights Reserved.
9 ***/
11 if (typeof(dojo) != 'undefined') {
12     dojo.provide('MochiKit.Iter');
13     dojo.require('MochiKit.Base');
16 if (typeof(JSAN) != 'undefined') {
17     JSAN.use("MochiKit.Base", []);
18 }   
20 try {
21     if (typeof(MochiKit.Base) == 'undefined') {
22         throw "";
23     }
24 } catch (e) {
25     throw "MochiKit.Iter depends on MochiKit.Base!";
26 }  
27             
28 if (typeof(MochiKit.Iter) == 'undefined') {
29     MochiKit.Iter = {};
30 }           
31         
32 MochiKit.Iter.NAME = "MochiKit.Iter";
33 MochiKit.Iter.VERSION = "1.4";
34 MochiKit.Base.update(MochiKit.Iter, {
35     __repr__: function () {
36         return "[" + this.NAME + " " + this.VERSION + "]";
37     },
38     toString: function () {
39         return this.__repr__();
40     },
42     /** @id MochiKit.Iter.registerIteratorFactory  */
43     registerIteratorFactory: function (name, check, iterfactory, /* optional */ override) {
44         MochiKit.Iter.iteratorRegistry.register(name, check, iterfactory, override);
45     },
47     /** @id MochiKit.Iter.iter */
48     iter: function (iterable, /* optional */ sentinel) {
49         var self = MochiKit.Iter;
50         if (arguments.length == 2) {
51             return self.takewhile(
52                 function (a) { return a != sentinel; },
53                 iterable
54             );
55         }
56         if (typeof(iterable.next) == 'function') {
57             return iterable;
58         } else if (typeof(iterable.iter) == 'function') {
59             return iterable.iter();
60         /*
61         }  else if (typeof(iterable.__iterator__) == 'function') {
62             //
63             // XXX: We can't support JavaScript 1.7 __iterator__ directly
64             //      because of Object.prototype.__iterator__
65             //
66             return iterable.__iterator__();
67         */
68         }
70         try {
71             return self.iteratorRegistry.match(iterable);
72         } catch (e) {
73             var m = MochiKit.Base;
74             if (e == m.NotFound) {
75                 e = new TypeError(typeof(iterable) + ": " + m.repr(iterable) + " is not iterable");
76             }
77             throw e;
78         }
79     },
81     /** @id MochiKit.Iter.count */
82     count: function (n) {
83         if (!n) {
84             n = 0;
85         }
86         var m = MochiKit.Base;
87         return {
88             repr: function () { return "count(" + n + ")"; },
89             toString: m.forwardCall("repr"),
90             next: m.counter(n)
91         };
92     },
94     /** @id MochiKit.Iter.cycle */
95     cycle: function (p) {
96         var self = MochiKit.Iter;
97         var m = MochiKit.Base;
98         var lst = [];
99         var iterator = self.iter(p);
100         return {
101             repr: function () { return "cycle(...)"; },
102             toString: m.forwardCall("repr"),
103             next: function () {
104                 try {
105                     var rval = iterator.next();
106                     lst.push(rval);
107                     return rval;
108                 } catch (e) {
109                     if (e != self.StopIteration) {
110                         throw e;
111                     }
112                     if (lst.length === 0) {
113                         this.next = function () {
114                             throw self.StopIteration;
115                         };
116                     } else {
117                         var i = -1;
118                         this.next = function () {
119                             i = (i + 1) % lst.length;
120                             return lst[i];
121                         };
122                     }
123                     return this.next();
124                 }
125             }
126         };
127     },
129     /** @id MochiKit.Iter.repeat */
130     repeat: function (elem, /* optional */n) {
131         var m = MochiKit.Base;
132         if (typeof(n) == 'undefined') {
133             return {
134                 repr: function () {
135                     return "repeat(" + m.repr(elem) + ")";
136                 },
137                 toString: m.forwardCall("repr"),
138                 next: function () {
139                     return elem;
140                 }
141             };
142         }
143         return {
144             repr: function () {
145                 return "repeat(" + m.repr(elem) + ", " + n + ")";
146             },
147             toString: m.forwardCall("repr"),
148             next: function () {
149                 if (n <= 0) {
150                     throw MochiKit.Iter.StopIteration;
151                 }
152                 n -= 1;
153                 return elem;
154             }
155         };
156     },
157             
158     /** @id MochiKit.Iter.next */
159     next: function (iterator) {
160         return iterator.next();
161     },
163     /** @id MochiKit.Iter.izip */
164     izip: function (p, q/*, ...*/) {
165         var m = MochiKit.Base;
166         var self = MochiKit.Iter;
167         var next = self.next;
168         var iterables = m.map(self.iter, arguments);
169         return {
170             repr: function () { return "izip(...)"; },
171             toString: m.forwardCall("repr"),
172             next: function () { return m.map(next, iterables); }
173         };
174     },
176     /** @id MochiKit.Iter.ifilter */
177     ifilter: function (pred, seq) {
178         var m = MochiKit.Base;
179         seq = MochiKit.Iter.iter(seq);
180         if (pred === null) {
181             pred = m.operator.truth;
182         }
183         return {
184             repr: function () { return "ifilter(...)"; },
185             toString: m.forwardCall("repr"),
186             next: function () {
187                 while (true) {
188                     var rval = seq.next();
189                     if (pred(rval)) {
190                         return rval;
191                     }
192                 }
193                 // mozilla warnings aren't too bright
194                 return undefined;
195             }
196         };
197     },
199     /** @id MochiKit.Iter.ifilterfalse */
200     ifilterfalse: function (pred, seq) {
201         var m = MochiKit.Base;
202         seq = MochiKit.Iter.iter(seq);
203         if (pred === null) {
204             pred = m.operator.truth;
205         }
206         return {
207             repr: function () { return "ifilterfalse(...)"; },
208             toString: m.forwardCall("repr"),
209             next: function () {
210                 while (true) {
211                     var rval = seq.next();
212                     if (!pred(rval)) {
213                         return rval;
214                     }
215                 }
216                 // mozilla warnings aren't too bright
217                 return undefined;
218             }
219         };
220     },
221      
222     /** @id MochiKit.Iter.islice */
223     islice: function (seq/*, [start,] stop[, step] */) {
224         var self = MochiKit.Iter;
225         var m = MochiKit.Base;
226         seq = self.iter(seq);
227         var start = 0;
228         var stop = 0;
229         var step = 1;
230         var i = -1;
231         if (arguments.length == 2) {
232             stop = arguments[1];
233         } else if (arguments.length == 3) {
234             start = arguments[1];
235             stop = arguments[2];
236         } else {
237             start = arguments[1];
238             stop = arguments[2];
239             step = arguments[3];
240         }
241         return {
242             repr: function () {
243                 return "islice(" + ["...", start, stop, step].join(", ") + ")";
244             },
245             toString: m.forwardCall("repr"),
246             next: function () {
247                 var rval;
248                 while (i < start) {
249                     rval = seq.next();
250                     i++;
251                 }
252                 if (start >= stop) {
253                     throw self.StopIteration;
254                 }
255                 start += step;
256                 return rval;
257             }
258         };
259     },
261     /** @id MochiKit.Iter.imap */
262     imap: function (fun, p, q/*, ...*/) {
263         var m = MochiKit.Base;
264         var self = MochiKit.Iter;
265         var iterables = m.map(self.iter, m.extend(null, arguments, 1));
266         var map = m.map;
267         var next = self.next;
268         return {
269             repr: function () { return "imap(...)"; },
270             toString: m.forwardCall("repr"),
271             next: function () {
272                 return fun.apply(this, map(next, iterables));
273             }
274         };
275     },
276         
277     /** @id MochiKit.Iter.applymap */
278     applymap: function (fun, seq, self) {
279         seq = MochiKit.Iter.iter(seq);
280         var m = MochiKit.Base;
281         return {
282             repr: function () { return "applymap(...)"; },
283             toString: m.forwardCall("repr"),
284             next: function () {
285                 return fun.apply(self, seq.next());
286             }
287         };
288     },
290     /** @id MochiKit.Iter.chain */
291     chain: function (p, q/*, ...*/) {
292         // dumb fast path
293         var self = MochiKit.Iter;
294         var m = MochiKit.Base;
295         if (arguments.length == 1) {
296             return self.iter(arguments[0]);
297         }
298         var argiter = m.map(self.iter, arguments);
299         return {
300             repr: function () { return "chain(...)"; },
301             toString: m.forwardCall("repr"),
302             next: function () {
303                 while (argiter.length > 1) {
304                     try {
305                         return argiter[0].next();
306                     } catch (e) {
307                         if (e != self.StopIteration) {
308                             throw e;
309                         }
310                         argiter.shift();
311                     }
312                 }
313                 if (argiter.length == 1) {
314                     // optimize last element
315                     var arg = argiter.shift();
316                     this.next = m.bind("next", arg);
317                     return this.next();
318                 }
319                 throw self.StopIteration;
320             }
321         };
322     },
324     /** @id MochiKit.Iter.takewhile */
325     takewhile: function (pred, seq) {
326         var self = MochiKit.Iter;
327         seq = self.iter(seq);
328         return {
329             repr: function () { return "takewhile(...)"; },
330             toString: MochiKit.Base.forwardCall("repr"),
331             next: function () {
332                 var rval = seq.next();
333                 if (!pred(rval)) {
334                     this.next = function () {
335                         throw self.StopIteration;
336                     };
337                     this.next();
338                 }
339                 return rval;
340             }
341         };
342     },
344     /** @id MochiKit.Iter.dropwhile */
345     dropwhile: function (pred, seq) {
346         seq = MochiKit.Iter.iter(seq);
347         var m = MochiKit.Base;
348         var bind = m.bind;
349         return {
350             "repr": function () { return "dropwhile(...)"; },
351             "toString": m.forwardCall("repr"),
352             "next": function () {
353                 while (true) {
354                     var rval = seq.next();
355                     if (!pred(rval)) {
356                         break;
357                     }
358                 }
359                 this.next = bind("next", seq);
360                 return rval;
361             }
362         };
363     },
365     _tee: function (ident, sync, iterable) {
366         sync.pos[ident] = -1;
367         var m = MochiKit.Base;
368         var listMin = m.listMin;
369         return {
370             repr: function () { return "tee(" + ident + ", ...)"; },
371             toString: m.forwardCall("repr"),
372             next: function () {
373                 var rval;
374                 var i = sync.pos[ident];
376                 if (i == sync.max) {
377                     rval = iterable.next();
378                     sync.deque.push(rval);
379                     sync.max += 1;
380                     sync.pos[ident] += 1;
381                 } else {
382                     rval = sync.deque[i - sync.min];
383                     sync.pos[ident] += 1;
384                     if (i == sync.min && listMin(sync.pos) != sync.min) {
385                         sync.min += 1;
386                         sync.deque.shift();
387                     }
388                 }
389                 return rval;
390             }
391         };
392     },
394     /** @id MochiKit.Iter.tee */
395     tee: function (iterable, n/* = 2 */) {
396         var rval = [];
397         var sync = {
398             "pos": [],
399             "deque": [],
400             "max": -1,
401             "min": -1
402         };
403         if (arguments.length == 1 || typeof(n) == "undefined" || n === null) {
404             n = 2;
405         }
406         var self = MochiKit.Iter;
407         iterable = self.iter(iterable);
408         var _tee = self._tee;
409         for (var i = 0; i < n; i++) {
410             rval.push(_tee(i, sync, iterable));
411         }
412         return rval;
413     },
415     /** @id MochiKit.Iter.list */
416     list: function (iterable) {
417         // Fast-path for Array and Array-like
418         var m = MochiKit.Base;
419         if (typeof(iterable.slice) == 'function') {
420             return iterable.slice();
421         } else if (m.isArrayLike(iterable)) {
422             return m.concat(iterable);
423         }
425         var self = MochiKit.Iter;
426         iterable = self.iter(iterable);
427         var rval = [];
428         try {
429             while (true) {
430                 rval.push(iterable.next());
431             }
432         } catch (e) {
433             if (e != self.StopIteration) {
434                 throw e;
435             }
436             return rval;
437         }
438         // mozilla warnings aren't too bright
439         return undefined;
440     },
442         
443     /** @id MochiKit.Iter.reduce */
444     reduce: function (fn, iterable, /* optional */initial) {
445         var i = 0;
446         var x = initial;
447         var self = MochiKit.Iter;
448         iterable = self.iter(iterable);
449         if (arguments.length < 3) {
450             try {
451                 x = iterable.next();
452             } catch (e) {
453                 if (e == self.StopIteration) {
454                     e = new TypeError("reduce() of empty sequence with no initial value");
455                 }
456                 throw e;
457             }
458             i++;
459         }
460         try {
461             while (true) {
462                 x = fn(x, iterable.next());
463             }
464         } catch (e) {
465             if (e != self.StopIteration) {
466                 throw e;
467             }
468         }
469         return x;
470     },
472     /** @id MochiKit.Iter.range */
473     range: function (/* [start,] stop[, step] */) {
474         var start = 0;
475         var stop = 0;
476         var step = 1;
477         if (arguments.length == 1) {
478             stop = arguments[0];
479         } else if (arguments.length == 2) {
480             start = arguments[0];
481             stop = arguments[1];
482         } else if (arguments.length == 3) {
483             start = arguments[0];
484             stop = arguments[1];
485             step = arguments[2];
486         } else {
487             throw new TypeError("range() takes 1, 2, or 3 arguments!");
488         }
489         if (step === 0) {
490             throw new TypeError("range() step must not be 0");
491         }
492         return {
493             next: function () {
494                 if ((step > 0 && start >= stop) || (step < 0 && start <= stop)) {
495                     throw MochiKit.Iter.StopIteration;
496                 }
497                 var rval = start;
498                 start += step;
499                 return rval;
500             },
501             repr: function () {
502                 return "range(" + [start, stop, step].join(", ") + ")";
503             },
504             toString: MochiKit.Base.forwardCall("repr")
505         };
506     },
507             
508     /** @id MochiKit.Iter.sum */
509     sum: function (iterable, start/* = 0 */) {
510         if (typeof(start) == "undefined" || start === null) {
511             start = 0;
512         }
513         var x = start;
514         var self = MochiKit.Iter;
515         iterable = self.iter(iterable);
516         try {
517             while (true) {
518                 x += iterable.next();
519             }
520         } catch (e) {
521             if (e != self.StopIteration) {
522                 throw e;
523             }
524         }
525         return x;
526     },
527             
528     /** @id MochiKit.Iter.exhaust */
529     exhaust: function (iterable) {
530         var self = MochiKit.Iter;
531         iterable = self.iter(iterable);
532         try {
533             while (true) {
534                 iterable.next();
535             }
536         } catch (e) {
537             if (e != self.StopIteration) {
538                 throw e;
539             }
540         }
541     },
543     /** @id MochiKit.Iter.forEach */
544     forEach: function (iterable, func, /* optional */self) {
545         var m = MochiKit.Base;
546         if (arguments.length > 2) {
547             func = m.bind(func, self);
548         }
549         // fast path for array
550         if (m.isArrayLike(iterable)) {
551             try {
552                 for (var i = 0; i < iterable.length; i++) {
553                     func(iterable[i]);
554                 }
555             } catch (e) {
556                 if (e != MochiKit.Iter.StopIteration) {
557                     throw e;
558                 }
559             }
560         } else {
561             self = MochiKit.Iter;
562             self.exhaust(self.imap(func, iterable));
563         }
564     },
566     /** @id MochiKit.Iter.every */
567     every: function (iterable, func) {
568         var self = MochiKit.Iter;
569         try {
570             self.ifilterfalse(func, iterable).next();
571             return false;
572         } catch (e) {
573             if (e != self.StopIteration) {
574                 throw e;
575             }
576             return true;
577         }
578     },
580     /** @id MochiKit.Iter.sorted */
581     sorted: function (iterable, /* optional */cmp) {
582         var rval = MochiKit.Iter.list(iterable);
583         if (arguments.length == 1) {
584             cmp = MochiKit.Base.compare;
585         }
586         rval.sort(cmp);
587         return rval;
588     },
590     /** @id MochiKit.Iter.reversed */
591     reversed: function (iterable) {
592         var rval = MochiKit.Iter.list(iterable);
593         rval.reverse();
594         return rval;
595     },
597     /** @id MochiKit.Iter.some */
598     some: function (iterable, func) {
599         var self = MochiKit.Iter;
600         try {
601             self.ifilter(func, iterable).next();
602             return true;
603         } catch (e) {
604             if (e != self.StopIteration) {
605                 throw e;
606             }
607             return false;
608         }
609     },
611     /** @id MochiKit.Iter.iextend */
612     iextend: function (lst, iterable) {
613         if (MochiKit.Base.isArrayLike(iterable)) {
614             // fast-path for array-like
615             for (var i = 0; i < iterable.length; i++) {
616                 lst.push(iterable[i]);
617             }
618         } else {
619             var self = MochiKit.Iter;
620             iterable = self.iter(iterable);
621             try {
622                 while (true) {
623                     lst.push(iterable.next());
624                 }
625             } catch (e) {
626                 if (e != self.StopIteration) {
627                     throw e;
628                 }
629             }
630         }
631         return lst;
632     },
634     /** @id MochiKit.Iter.groupby */
635     groupby: function(iterable, /* optional */ keyfunc) {
636         var m = MochiKit.Base;
637         var self = MochiKit.Iter;
638         if (arguments.length < 2) {
639             keyfunc = m.operator.identity;
640         }
641         iterable = self.iter(iterable);
643         // shared
644         var pk = undefined;
645         var k = undefined;
646         var v;
648         function fetch() {
649             v = iterable.next();
650             k = keyfunc(v);
651         };
653         function eat() {
654             var ret = v;
655             v = undefined;
656             return ret;
657         };
659         var first = true;
660         var compare = m.compare;
661         return {
662             repr: function () { return "groupby(...)"; },
663             next: function() {
664                 // iterator-next
666                 // iterate until meet next group
667                 while (compare(k, pk) === 0) {
668                     fetch();
669                     if (first) {
670                         first = false;
671                         break;
672                     }
673                 }
674                 pk = k;
675                 return [k, {
676                     next: function() {
677                         // subiterator-next
678                         if (v == undefined) { // Is there something to eat?
679                             fetch();
680                         }
681                         if (compare(k, pk) !== 0) {
682                             throw self.StopIteration;
683                         }
684                         return eat();
685                     }
686                 }];
687             }
688         };
689     },
691     /** @id MochiKit.Iter.groupby_as_array */
692     groupby_as_array: function (iterable, /* optional */ keyfunc) {
693         var m = MochiKit.Base;
694         var self = MochiKit.Iter;
695         if (arguments.length < 2) {
696             keyfunc = m.operator.identity;
697         }
699         iterable = self.iter(iterable);
700         var result = [];
701         var first = true;
702         var prev_key;
703         var compare = m.compare;
704         while (true) {
705             try {
706                 var value = iterable.next();
707                 var key = keyfunc(value);
708             } catch (e) {
709                 if (e == self.StopIteration) {
710                     break;
711                 }
712                 throw e;
713             }
714             if (first || compare(key, prev_key) !== 0) {
715                 var values = [];
716                 result.push([key, values]);
717             }
718             values.push(value);
719             first = false;
720             prev_key = key;
721         }
722         return result;
723     },
725     /** @id MochiKit.Iter.arrayLikeIter */
726     arrayLikeIter: function (iterable) {
727         var i = 0;
728         return {
729             repr: function () { return "arrayLikeIter(...)"; },
730             toString: MochiKit.Base.forwardCall("repr"),
731             next: function () {
732                 if (i >= iterable.length) {
733                     throw MochiKit.Iter.StopIteration;
734                 }
735                 return iterable[i++];
736             }
737         };
738     },
740     /** @id MochiKit.Iter.hasIterateNext */
741     hasIterateNext: function (iterable) {
742         return (iterable && typeof(iterable.iterateNext) == "function");
743     },
745     /** @id MochiKit.Iter.iterateNextIter */
746     iterateNextIter: function (iterable) {
747         return {
748             repr: function () { return "iterateNextIter(...)"; },
749             toString: MochiKit.Base.forwardCall("repr"),
750             next: function () {
751                 var rval = iterable.iterateNext();
752                 if (rval === null || rval === undefined) {
753                     throw MochiKit.Iter.StopIteration;
754                 }
755                 return rval;
756             }
757         };
758     }
762 MochiKit.Iter.EXPORT_OK = [
763     "iteratorRegistry",
764     "arrayLikeIter",
765     "hasIterateNext",
766     "iterateNextIter",
769 MochiKit.Iter.EXPORT = [
770     "StopIteration",
771     "registerIteratorFactory",
772     "iter",
773     "count",
774     "cycle",
775     "repeat",
776     "next",
777     "izip",
778     "ifilter",
779     "ifilterfalse",
780     "islice",
781     "imap",
782     "applymap",
783     "chain",
784     "takewhile",
785     "dropwhile",
786     "tee",
787     "list",
788     "reduce",
789     "range",
790     "sum",
791     "exhaust",
792     "forEach",
793     "every",
794     "sorted",
795     "reversed",
796     "some",
797     "iextend",
798     "groupby",
799     "groupby_as_array"
802 MochiKit.Iter.__new__ = function () {
803     var m = MochiKit.Base;
804     // Re-use StopIteration if exists (e.g. SpiderMonkey)
805     if (typeof(StopIteration) != "undefined") {
806         this.StopIteration = StopIteration;
807     } else {
808         /** @id MochiKit.Iter.StopIteration */
809         this.StopIteration = new m.NamedError("StopIteration");
810     }
811     this.iteratorRegistry = new m.AdapterRegistry();
812     // Register the iterator factory for arrays
813     this.registerIteratorFactory(
814         "arrayLike",
815         m.isArrayLike,
816         this.arrayLikeIter
817     );
819     this.registerIteratorFactory(
820         "iterateNext",
821         this.hasIterateNext,
822         this.iterateNextIter
823     );
825     this.EXPORT_TAGS = {
826         ":common": this.EXPORT,
827         ":all": m.concat(this.EXPORT, this.EXPORT_OK)
828     };
830     m.nameFunctions(this);
831         
834 MochiKit.Iter.__new__();
837 // XXX: Internet Explorer blows
839 if (MochiKit.__export__) {
840     reduce = MochiKit.Iter.reduce;
843 MochiKit.Base._exportSymbols(this, MochiKit.Iter);