2 // (c) 2009-2012 Jeremy Ashkenas, DocumentCloud Inc.
3 // Underscore is freely distributable under the MIT license.
4 // Portions of Underscore are inspired or borrowed from Prototype,
5 // Oliver Steele's Functional, and John Resig's Micro-Templating.
6 // For all details and documentation:
7 // http://documentcloud.github.com/underscore
14 // Establish the root object, `window` in the browser, or `global` on the server.
17 // Save the previous value of the `_` variable.
18 var previousUnderscore
= root
._
;
20 // Establish the object that gets returned to break out of a loop iteration.
23 // Save bytes in the minified (but not gzipped) version:
24 var ArrayProto
= Array
.prototype, ObjProto
= Object
.prototype, FuncProto
= Function
.prototype;
26 // Create quick reference variables for speed access to core prototypes.
27 var slice
= ArrayProto
.slice
,
28 unshift
= ArrayProto
.unshift
,
29 toString
= ObjProto
.toString
,
30 hasOwnProperty
= ObjProto
.hasOwnProperty
;
32 // All **ECMAScript 5** native function implementations that we hope to use
35 nativeForEach
= ArrayProto
.forEach
,
36 nativeMap
= ArrayProto
.map
,
37 nativeReduce
= ArrayProto
.reduce
,
38 nativeReduceRight
= ArrayProto
.reduceRight
,
39 nativeFilter
= ArrayProto
.filter
,
40 nativeEvery
= ArrayProto
.every
,
41 nativeSome
= ArrayProto
.some
,
42 nativeIndexOf
= ArrayProto
.indexOf
,
43 nativeLastIndexOf
= ArrayProto
.lastIndexOf
,
44 nativeIsArray
= Array
.isArray
,
45 nativeKeys
= Object
.keys
,
46 nativeBind
= FuncProto
.bind
;
48 // Create a safe reference to the Underscore object for use below.
49 var _ = function(obj
) { return new wrapper(obj
); };
51 // Export the Underscore object for **Node.js**, with
52 // backwards-compatibility for the old `require()` API. If we're in
53 // the browser, add `_` as a global object via a string identifier,
54 // for Closure Compiler "advanced" mode.
55 if (typeof exports
!== 'undefined') {
56 if (typeof module
!== 'undefined' && module
.exports
) {
57 exports
= module
.exports
= _
;
67 // Collection Functions
68 // --------------------
70 // The cornerstone, an `each` implementation, aka `forEach`.
71 // Handles objects with the built-in `forEach`, arrays, and raw objects.
72 // Delegates to **ECMAScript 5**'s native `forEach` if available.
73 var each
= _
.each
= _
.forEach = function(obj
, iterator
, context
) {
74 if (obj
== null) return;
75 if (nativeForEach
&& obj
.forEach
=== nativeForEach
) {
76 obj
.forEach(iterator
, context
);
77 } else if (obj
.length
=== +obj
.length
) {
78 for (var i
= 0, l
= obj
.length
; i
< l
; i
++) {
79 if (i
in obj
&& iterator
.call(context
, obj
[i
], i
, obj
) === breaker
) return;
82 for (var key
in obj
) {
83 if (_
.has(obj
, key
)) {
84 if (iterator
.call(context
, obj
[key
], key
, obj
) === breaker
) return;
90 // Return the results of applying the iterator to each element.
91 // Delegates to **ECMAScript 5**'s native `map` if available.
92 _
.map
= _
.collect = function(obj
, iterator
, context
) {
94 if (obj
== null) return results
;
95 if (nativeMap
&& obj
.map
=== nativeMap
) return obj
.map(iterator
, context
);
96 each(obj
, function(value
, index
, list
) {
97 results
[results
.length
] = iterator
.call(context
, value
, index
, list
);
99 if (obj
.length
=== +obj
.length
) results
.length
= obj
.length
;
103 // **Reduce** builds up a single result from a list of values, aka `inject`,
104 // or `foldl`. Delegates to **ECMAScript 5**'s native `reduce` if available.
105 _
.reduce
= _
.foldl
= _
.inject = function(obj
, iterator
, memo
, context
) {
106 var initial
= arguments
.length
> 2;
107 if (obj
== null) obj
= [];
108 if (nativeReduce
&& obj
.reduce
=== nativeReduce
) {
109 if (context
) iterator
= _
.bind(iterator
, context
);
110 return initial
? obj
.reduce(iterator
, memo
) : obj
.reduce(iterator
);
112 each(obj
, function(value
, index
, list
) {
117 memo
= iterator
.call(context
, memo
, value
, index
, list
);
120 if (!initial
) throw new TypeError('Reduce of empty array with no initial value');
124 // The right-associative version of reduce, also known as `foldr`.
125 // Delegates to **ECMAScript 5**'s native `reduceRight` if available.
126 _
.reduceRight
= _
.foldr = function(obj
, iterator
, memo
, context
) {
127 var initial
= arguments
.length
> 2;
128 if (obj
== null) obj
= [];
129 if (nativeReduceRight
&& obj
.reduceRight
=== nativeReduceRight
) {
130 if (context
) iterator
= _
.bind(iterator
, context
);
131 return initial
? obj
.reduceRight(iterator
, memo
) : obj
.reduceRight(iterator
);
133 var reversed
= _
.toArray(obj
).reverse();
134 if (context
&& !initial
) iterator
= _
.bind(iterator
, context
);
135 return initial
? _
.reduce(reversed
, iterator
, memo
, context
) : _
.reduce(reversed
, iterator
);
138 // Return the first value which passes a truth test. Aliased as `detect`.
139 _
.find
= _
.detect = function(obj
, iterator
, context
) {
141 any(obj
, function(value
, index
, list
) {
142 if (iterator
.call(context
, value
, index
, list
)) {
150 // Return all the elements that pass a truth test.
151 // Delegates to **ECMAScript 5**'s native `filter` if available.
152 // Aliased as `select`.
153 _
.filter
= _
.select = function(obj
, iterator
, context
) {
155 if (obj
== null) return results
;
156 if (nativeFilter
&& obj
.filter
=== nativeFilter
) return obj
.filter(iterator
, context
);
157 each(obj
, function(value
, index
, list
) {
158 if (iterator
.call(context
, value
, index
, list
)) results
[results
.length
] = value
;
163 // Return all the elements for which a truth test fails.
164 _
.reject = function(obj
, iterator
, context
) {
166 if (obj
== null) return results
;
167 each(obj
, function(value
, index
, list
) {
168 if (!iterator
.call(context
, value
, index
, list
)) results
[results
.length
] = value
;
173 // Determine whether all of the elements match a truth test.
174 // Delegates to **ECMAScript 5**'s native `every` if available.
176 _
.every
= _
.all = function(obj
, iterator
, context
) {
178 if (obj
== null) return result
;
179 if (nativeEvery
&& obj
.every
=== nativeEvery
) return obj
.every(iterator
, context
);
180 each(obj
, function(value
, index
, list
) {
181 if (!(result
= result
&& iterator
.call(context
, value
, index
, list
))) return breaker
;
186 // Determine if at least one element in the object matches a truth test.
187 // Delegates to **ECMAScript 5**'s native `some` if available.
189 var any
= _
.some
= _
.any = function(obj
, iterator
, context
) {
190 iterator
|| (iterator
= _
.identity
);
192 if (obj
== null) return result
;
193 if (nativeSome
&& obj
.some
=== nativeSome
) return obj
.some(iterator
, context
);
194 each(obj
, function(value
, index
, list
) {
195 if (result
|| (result
= iterator
.call(context
, value
, index
, list
))) return breaker
;
200 // Determine if a given value is included in the array or object using `===`.
201 // Aliased as `contains`.
202 _
.include
= _
.contains = function(obj
, target
) {
204 if (obj
== null) return found
;
205 if (nativeIndexOf
&& obj
.indexOf
=== nativeIndexOf
) return obj
.indexOf(target
) != -1;
206 found
= any(obj
, function(value
) {
207 return value
=== target
;
212 // Invoke a method (with arguments) on every item in a collection.
213 _
.invoke = function(obj
, method
) {
214 var args
= slice
.call(arguments
, 2);
215 return _
.map(obj
, function(value
) {
216 return (_
.isFunction(method
) ? method
|| value
: value
[method
]).apply(value
, args
);
220 // Convenience version of a common use case of `map`: fetching a property.
221 _
.pluck = function(obj
, key
) {
222 return _
.map(obj
, function(value
){ return value
[key
]; });
225 // Return the maximum element or (element-based computation).
226 _
.max = function(obj
, iterator
, context
) {
227 if (!iterator
&& _
.isArray(obj
)) return Math
.max
.apply(Math
, obj
);
228 if (!iterator
&& _
.isEmpty(obj
)) return -Infinity
;
229 var result
= {computed
: -Infinity
};
230 each(obj
, function(value
, index
, list
) {
231 var computed
= iterator
? iterator
.call(context
, value
, index
, list
) : value
;
232 computed
>= result
.computed
&& (result
= {value
: value
, computed
: computed
});
237 // Return the minimum element (or element-based computation).
238 _
.min = function(obj
, iterator
, context
) {
239 if (!iterator
&& _
.isArray(obj
)) return Math
.min
.apply(Math
, obj
);
240 if (!iterator
&& _
.isEmpty(obj
)) return Infinity
;
241 var result
= {computed
: Infinity
};
242 each(obj
, function(value
, index
, list
) {
243 var computed
= iterator
? iterator
.call(context
, value
, index
, list
) : value
;
244 computed
< result
.computed
&& (result
= {value
: value
, computed
: computed
});
250 _
.shuffle = function(obj
) {
251 var shuffled
= [], rand
;
252 each(obj
, function(value
, index
, list
) {
256 rand
= Math
.floor(Math
.random() * (index
+ 1));
257 shuffled
[index
] = shuffled
[rand
];
258 shuffled
[rand
] = value
;
264 // Sort the object's values by a criterion produced by an iterator.
265 _
.sortBy = function(obj
, iterator
, context
) {
266 return _
.pluck(_
.map(obj
, function(value
, index
, list
) {
269 criteria
: iterator
.call(context
, value
, index
, list
)
271 }).sort(function(left
, right
) {
272 var a
= left
.criteria
, b
= right
.criteria
;
273 return a
< b
? -1 : a
> b
? 1 : 0;
277 // Groups the object's values by a criterion. Pass either a string attribute
278 // to group by, or a function that returns the criterion.
279 _
.groupBy = function(obj
, val
) {
281 var iterator
= _
.isFunction(val
) ? val : function(obj
) { return obj
[val
]; };
282 each(obj
, function(value
, index
) {
283 var key
= iterator(value
, index
);
284 (result
[key
] || (result
[key
] = [])).push(value
);
289 // Use a comparator function to figure out at what index an object should
290 // be inserted so as to maintain order. Uses binary search.
291 _
.sortedIndex = function(array
, obj
, iterator
) {
292 iterator
|| (iterator
= _
.identity
);
293 var low
= 0, high
= array
.length
;
295 var mid
= (low
+ high
) >> 1;
296 iterator(array
[mid
]) < iterator(obj
) ? low
= mid
+ 1 : high
= mid
;
301 // Safely convert anything iterable into a real, live array.
302 _
.toArray = function(iterable
) {
303 if (!iterable
) return [];
304 if (iterable
.toArray
) return iterable
.toArray();
305 if (_
.isArray(iterable
)) return slice
.call(iterable
);
306 if (_
.isArguments(iterable
)) return slice
.call(iterable
);
307 return _
.values(iterable
);
310 // Return the number of elements in an object.
311 _
.size = function(obj
) {
312 return _
.toArray(obj
).length
;
318 // Get the first element of an array. Passing **n** will return the first N
319 // values in the array. Aliased as `head`. The **guard** check allows it to work
321 _
.first
= _
.head = function(array
, n
, guard
) {
322 return (n
!= null) && !guard
? slice
.call(array
, 0, n
) : array
[0];
325 // Returns everything but the last entry of the array. Especcialy useful on
326 // the arguments object. Passing **n** will return all the values in
327 // the array, excluding the last N. The **guard** check allows it to work with
329 _
.initial = function(array
, n
, guard
) {
330 return slice
.call(array
, 0, array
.length
- ((n
== null) || guard
? 1 : n
));
333 // Get the last element of an array. Passing **n** will return the last N
334 // values in the array. The **guard** check allows it to work with `_.map`.
335 _
.last = function(array
, n
, guard
) {
336 if ((n
!= null) && !guard
) {
337 return slice
.call(array
, Math
.max(array
.length
- n
, 0));
339 return array
[array
.length
- 1];
343 // Returns everything but the first entry of the array. Aliased as `tail`.
344 // Especially useful on the arguments object. Passing an **index** will return
345 // the rest of the values in the array from that index onward. The **guard**
346 // check allows it to work with `_.map`.
347 _
.rest
= _
.tail = function(array
, index
, guard
) {
348 return slice
.call(array
, (index
== null) || guard
? 1 : index
);
351 // Trim out all falsy values from an array.
352 _
.compact = function(array
) {
353 return _
.filter(array
, function(value
){ return !!value
; });
356 // Return a completely flattened version of an array.
357 _
.flatten = function(array
, shallow
) {
358 return _
.reduce(array
, function(memo
, value
) {
359 if (_
.isArray(value
)) return memo
.concat(shallow
? value
: _
.flatten(value
));
360 memo
[memo
.length
] = value
;
365 // Return a version of the array that does not contain the specified value(s).
366 _
.without = function(array
) {
367 return _
.difference(array
, slice
.call(arguments
, 1));
370 // Produce a duplicate-free version of the array. If the array has already
371 // been sorted, you have the option of using a faster algorithm.
372 // Aliased as `unique`.
373 _
.uniq
= _
.unique = function(array
, isSorted
, iterator
) {
374 var initial
= iterator
? _
.map(array
, iterator
) : array
;
376 _
.reduce(initial
, function(memo
, el
, i
) {
377 if (0 == i
|| (isSorted
=== true ? _
.last(memo
) != el
: !_
.include(memo
, el
))) {
378 memo
[memo
.length
] = el
;
379 result
[result
.length
] = array
[i
];
386 // Produce an array that contains the union: each distinct element from all of
387 // the passed-in arrays.
388 _
.union = function() {
389 return _
.uniq(_
.flatten(arguments
, true));
392 // Produce an array that contains every item shared between all the
393 // passed-in arrays. (Aliased as "intersect" for back-compat.)
394 _
.intersection
= _
.intersect = function(array
) {
395 var rest
= slice
.call(arguments
, 1);
396 return _
.filter(_
.uniq(array
), function(item
) {
397 return _
.every(rest
, function(other
) {
398 return _
.indexOf(other
, item
) >= 0;
403 // Take the difference between one array and a number of other arrays.
404 // Only the elements present in just the first array will remain.
405 _
.difference = function(array
) {
406 var rest
= _
.flatten(slice
.call(arguments
, 1));
407 return _
.filter(array
, function(value
){ return !_
.include(rest
, value
); });
410 // Zip together multiple lists into a single array -- elements that share
411 // an index go together.
413 var args
= slice
.call(arguments
);
414 var length
= _
.max(_
.pluck(args
, 'length'));
415 var results
= new Array(length
);
416 for (var i
= 0; i
< length
; i
++) results
[i
] = _
.pluck(args
, "" + i
);
420 // If the browser doesn't supply us with indexOf (I'm looking at you, **MSIE**),
421 // we need this function. Return the position of the first occurrence of an
422 // item in an array, or -1 if the item is not included in the array.
423 // Delegates to **ECMAScript 5**'s native `indexOf` if available.
424 // If the array is large and already in sort order, pass `true`
425 // for **isSorted** to use binary search.
426 _
.indexOf = function(array
, item
, isSorted
) {
427 if (array
== null) return -1;
430 i
= _
.sortedIndex(array
, item
);
431 return array
[i
] === item
? i
: -1;
433 if (nativeIndexOf
&& array
.indexOf
=== nativeIndexOf
) return array
.indexOf(item
);
434 for (i
= 0, l
= array
.length
; i
< l
; i
++) if (i
in array
&& array
[i
] === item
) return i
;
438 // Delegates to **ECMAScript 5**'s native `lastIndexOf` if available.
439 _
.lastIndexOf = function(array
, item
) {
440 if (array
== null) return -1;
441 if (nativeLastIndexOf
&& array
.lastIndexOf
=== nativeLastIndexOf
) return array
.lastIndexOf(item
);
442 var i
= array
.length
;
443 while (i
--) if (i
in array
&& array
[i
] === item
) return i
;
447 // Generate an integer Array containing an arithmetic progression. A port of
448 // the native Python `range()` function. See
449 // [the Python documentation](http://docs.python.org/library/functions.html#range).
450 _
.range = function(start
, stop
, step
) {
451 if (arguments
.length
<= 1) {
455 step
= arguments
[2] || 1;
457 var len
= Math
.max(Math
.ceil((stop
- start
) / step
), 0);
459 var range
= new Array(len
);
462 range
[idx
++] = start
;
469 // Function (ahem) Functions
470 // ------------------
472 // Reusable constructor function for prototype setting.
473 var ctor = function(){};
475 // Create a function bound to a given object (assigning `this`, and arguments,
476 // optionally). Binding with arguments is also known as `curry`.
477 // Delegates to **ECMAScript 5**'s native `Function.bind` if available.
478 // We check for `func.bind` first, to fail fast when `func` is undefined.
479 _
.bind
= function bind(func
, context
) {
481 if (func
.bind
=== nativeBind
&& nativeBind
) return nativeBind
.apply(func
, slice
.call(arguments
, 1));
482 if (!_
.isFunction(func
)) throw new TypeError
;
483 args
= slice
.call(arguments
, 2);
484 return bound = function() {
485 if (!(this instanceof bound
)) return func
.apply(context
, args
.concat(slice
.call(arguments
)));
486 ctor
.prototype = func
.prototype;
488 var result
= func
.apply(self
, args
.concat(slice
.call(arguments
)));
489 if (Object(result
) === result
) return result
;
494 // Bind all of an object's methods to that object. Useful for ensuring that
495 // all callbacks defined on an object belong to it.
496 _
.bindAll = function(obj
) {
497 var funcs
= slice
.call(arguments
, 1);
498 if (funcs
.length
== 0) funcs
= _
.functions(obj
);
499 each(funcs
, function(f
) { obj
[f
] = _
.bind(obj
[f
], obj
); });
503 // Memoize an expensive function by storing its results.
504 _
.memoize = function(func
, hasher
) {
506 hasher
|| (hasher
= _
.identity
);
508 var key
= hasher
.apply(this, arguments
);
509 return _
.has(memo
, key
) ? memo
[key
] : (memo
[key
] = func
.apply(this, arguments
));
513 // Delays a function for the given number of milliseconds, and then calls
514 // it with the arguments supplied.
515 _
.delay = function(func
, wait
) {
516 var args
= slice
.call(arguments
, 2);
517 return setTimeout(function(){ return func
.apply(func
, args
); }, wait
);
520 // Defers a function, scheduling it to run after the current call stack has
522 _
.defer = function(func
) {
523 return _
.delay
.apply(_
, [func
, 1].concat(slice
.call(arguments
, 1)));
526 // Returns a function, that, when invoked, will only be triggered at most once
527 // during a given window of time.
528 _
.throttle = function(func
, wait
) {
529 var context
, args
, timeout
, throttling
, more
;
530 var whenDone
= _
.debounce(function(){ more
= throttling
= false; }, wait
);
532 context
= this; args
= arguments
;
533 var later = function() {
535 if (more
) func
.apply(context
, args
);
538 if (!timeout
) timeout
= setTimeout(later
, wait
);
542 func
.apply(context
, args
);
549 // Returns a function, that, as long as it continues to be invoked, will not
550 // be triggered. The function will be called after it stops being called for
552 _
.debounce = function(func
, wait
) {
555 var context
= this, args
= arguments
;
556 var later = function() {
558 func
.apply(context
, args
);
560 clearTimeout(timeout
);
561 timeout
= setTimeout(later
, wait
);
565 // Returns a function that will be executed at most one time, no matter how
566 // often you call it. Useful for lazy initialization.
567 _
.once = function(func
) {
568 var ran
= false, memo
;
570 if (ran
) return memo
;
572 return memo
= func
.apply(this, arguments
);
576 // Returns the first function passed as an argument to the second,
577 // allowing you to adjust arguments, run code before and after, and
578 // conditionally execute the original function.
579 _
.wrap = function(func
, wrapper
) {
581 var args
= [func
].concat(slice
.call(arguments
, 0));
582 return wrapper
.apply(this, args
);
586 // Returns a function that is the composition of a list of functions, each
587 // consuming the return value of the function that follows.
588 _
.compose = function() {
589 var funcs
= arguments
;
591 var args
= arguments
;
592 for (var i
= funcs
.length
- 1; i
>= 0; i
--) {
593 args
= [funcs
[i
].apply(this, args
)];
599 // Returns a function that will only be executed after being called N times.
600 _
.after = function(times
, func
) {
601 if (times
<= 0) return func();
603 if (--times
< 1) { return func
.apply(this, arguments
); }
610 // Retrieve the names of an object's properties.
611 // Delegates to **ECMAScript 5**'s native `Object.keys`
612 _
.keys
= nativeKeys
|| function(obj
) {
613 if (obj
!== Object(obj
)) throw new TypeError('Invalid object');
615 for (var key
in obj
) if (_
.has(obj
, key
)) keys
[keys
.length
] = key
;
619 // Retrieve the values of an object's properties.
620 _
.values = function(obj
) {
621 return _
.map(obj
, _
.identity
);
624 // Return a sorted list of the function names available on the object.
625 // Aliased as `methods`
626 _
.functions
= _
.methods = function(obj
) {
628 for (var key
in obj
) {
629 if (_
.isFunction(obj
[key
])) names
.push(key
);
634 // Extend a given object with all the properties in passed-in object(s).
635 _
.extend = function(obj
) {
636 each(slice
.call(arguments
, 1), function(source
) {
637 for (var prop
in source
) {
638 obj
[prop
] = source
[prop
];
644 // Fill in a given object with default properties.
645 _
.defaults = function(obj
) {
646 each(slice
.call(arguments
, 1), function(source
) {
647 for (var prop
in source
) {
648 if (obj
[prop
] == null) obj
[prop
] = source
[prop
];
654 // Create a (shallow-cloned) duplicate of an object.
655 _
.clone = function(obj
) {
656 if (!_
.isObject(obj
)) return obj
;
657 return _
.isArray(obj
) ? obj
.slice() : _
.extend({}, obj
);
660 // Invokes interceptor with the obj, and then returns obj.
661 // The primary purpose of this method is to "tap into" a method chain, in
662 // order to perform operations on intermediate results within the chain.
663 _
.tap = function(obj
, interceptor
) {
668 // Internal recursive comparison function.
669 function eq(a
, b
, stack
) {
670 // Identical objects are equal. `0 === -0`, but they aren't identical.
671 // See the Harmony `egal` proposal: http://wiki.ecmascript.org/doku.php?id=harmony:egal.
672 if (a
=== b
) return a
!== 0 || 1 / a
== 1 / b
;
673 // A strict comparison is necessary because `null == undefined`.
674 if (a
== null || b
== null) return a
=== b
;
675 // Unwrap any wrapped objects.
676 if (a
._chain
) a
= a
._wrapped
;
677 if (b
._chain
) b
= b
._wrapped
;
678 // Invoke a custom `isEqual` method if one is provided.
679 if (a
.isEqual
&& _
.isFunction(a
.isEqual
)) return a
.isEqual(b
);
680 if (b
.isEqual
&& _
.isFunction(b
.isEqual
)) return b
.isEqual(a
);
681 // Compare `[[Class]]` names.
682 var className
= toString
.call(a
);
683 if (className
!= toString
.call(b
)) return false;
685 // Strings, numbers, dates, and booleans are compared by value.
686 case '[object String]':
687 // Primitives and their corresponding object wrappers are equivalent; thus, `"5"` is
688 // equivalent to `new String("5")`.
689 return a
== String(b
);
690 case '[object Number]':
691 // `NaN`s are equivalent, but non-reflexive. An `egal` comparison is performed for
692 // other numeric values.
693 return a
!= +a
? b
!= +b
: (a
== 0 ? 1 / a
== 1 / b
: a
== +b
);
694 case '[object Date]':
695 case '[object Boolean]':
696 // Coerce dates and booleans to numeric primitive values. Dates are compared by their
697 // millisecond representations. Note that invalid dates with millisecond representations
698 // of `NaN` are not equivalent.
700 // RegExps are compared by their source patterns and flags.
701 case '[object RegExp]':
702 return a
.source
== b
.source
&&
703 a
.global
== b
.global
&&
704 a
.multiline
== b
.multiline
&&
705 a
.ignoreCase
== b
.ignoreCase
;
707 if (typeof a
!= 'object' || typeof b
!= 'object') return false;
708 // Assume equality for cyclic structures. The algorithm for detecting cyclic
709 // structures is adapted from ES 5.1 section 15.12.3, abstract operation `JO`.
710 var length
= stack
.length
;
712 // Linear search. Performance is inversely proportional to the number of
713 // unique nested structures.
714 if (stack
[length
] == a
) return true;
716 // Add the first object to the stack of traversed objects.
718 var size
= 0, result
= true;
719 // Recursively compare objects and arrays.
720 if (className
== '[object Array]') {
721 // Compare array lengths to determine if a deep comparison is necessary.
723 result
= size
== b
.length
;
725 // Deep compare the contents, ignoring non-numeric properties.
727 // Ensure commutative equality for sparse arrays.
728 if (!(result
= size
in a
== size
in b
&& eq(a
[size
], b
[size
], stack
))) break;
732 // Objects with different constructors are not equivalent.
733 if ('constructor' in a
!= 'constructor' in b
|| a
.constructor != b
.constructor) return false;
734 // Deep compare objects.
737 // Count the expected number of properties.
739 // Deep compare each member.
740 if (!(result
= _
.has(b
, key
) && eq(a
[key
], b
[key
], stack
))) break;
743 // Ensure that both objects contain the same number of properties.
746 if (_
.has(b
, key
) && !(size
--)) break;
751 // Remove the first object from the stack of traversed objects.
756 // Perform a deep comparison to check if two objects are equal.
757 _
.isEqual = function(a
, b
) {
761 // Is a given array, string, or object empty?
762 // An "empty" object has no enumerable own-properties.
763 _
.isEmpty = function(obj
) {
764 if (_
.isArray(obj
) || _
.isString(obj
)) return obj
.length
=== 0;
765 for (var key
in obj
) if (_
.has(obj
, key
)) return false;
769 // Is a given value a DOM element?
770 _
.isElement = function(obj
) {
771 return !!(obj
&& obj
.nodeType
== 1);
774 // Is a given value an array?
775 // Delegates to ECMA5's native Array.isArray
776 _
.isArray
= nativeIsArray
|| function(obj
) {
777 return toString
.call(obj
) == '[object Array]';
780 // Is a given variable an object?
781 _
.isObject = function(obj
) {
782 return obj
=== Object(obj
);
785 // Is a given variable an arguments object?
786 _
.isArguments = function(obj
) {
787 return toString
.call(obj
) == '[object Arguments]';
789 if (!_
.isArguments(arguments
)) {
790 _
.isArguments = function(obj
) {
791 return !!(obj
&& _
.has(obj
, 'callee'));
795 // Is a given value a function?
796 _
.isFunction = function(obj
) {
797 return toString
.call(obj
) == '[object Function]';
800 // Is a given value a string?
801 _
.isString = function(obj
) {
802 return toString
.call(obj
) == '[object String]';
805 // Is a given value a number?
806 _
.isNumber = function(obj
) {
807 return toString
.call(obj
) == '[object Number]';
810 // Is the given value `NaN`?
811 _
.isNaN = function(obj
) {
812 // `NaN` is the only value for which `===` is not reflexive.
816 // Is a given value a boolean?
817 _
.isBoolean = function(obj
) {
818 return obj
=== true || obj
=== false || toString
.call(obj
) == '[object Boolean]';
821 // Is a given value a date?
822 _
.isDate = function(obj
) {
823 return toString
.call(obj
) == '[object Date]';
826 // Is the given value a regular expression?
827 _
.isRegExp = function(obj
) {
828 return toString
.call(obj
) == '[object RegExp]';
831 // Is a given value equal to null?
832 _
.isNull = function(obj
) {
836 // Is a given variable undefined?
837 _
.isUndefined = function(obj
) {
838 return obj
=== void 0;
842 _
.has = function(obj
, key
) {
843 return hasOwnProperty
.call(obj
, key
);
849 // Run Underscore.js in *noConflict* mode, returning the `_` variable to its
850 // previous owner. Returns a reference to the Underscore object.
851 _
.noConflict = function() {
852 root
._
= previousUnderscore
;
856 // Keep the identity function around for default iterators.
857 _
.identity = function(value
) {
861 // Run a function **n** times.
862 _
.times = function (n
, iterator
, context
) {
863 for (var i
= 0; i
< n
; i
++) iterator
.call(context
, i
);
866 // Escape a string for HTML interpolation.
867 _
.escape = function(string
) {
868 return (''+string
).replace(/&/g, '&').replace(/</g, '<').replace(/>/g, '>').replace(/"/g, '"').replace(/'/g, ''').replace(/\//g,'/');
871 // Add your own custom functions to the Underscore object, ensuring that
872 // they're correctly added to the OOP wrapper as well.
873 _.mixin = function(obj) {
874 each(_.functions(obj), function(name){
875 addToWrapper(name, _[name] = obj[name]);
879 // Generate a unique integer id (unique within the entire client session).
880 // Useful for temporary DOM ids.
882 _.uniqueId = function(prefix) {
883 var id = idCounter++;
884 return prefix ? prefix + id : id;
887 // By default, Underscore uses ERB-style template delimiters, change the
888 // following template settings to use alternative delimiters.
889 _.templateSettings = {
890 evaluate : /<%([\s\S]+?)%>/g,
891 interpolate : /<%=([\s\S]+?)%>/g,
892 escape : /<%-([\s\S]+?)%>/g
895 // When customizing `templateSettings`, if you don't want to define an
896 // interpolation, evaluation or escaping regex, we need one that is
897 // guaranteed not to match.
900 // Within an interpolation, evaluation, or escaping, remove HTML escaping
901 // that had been previously added.
902 var unescape = function(code) {
903 return code.replace(/\\\\/g, '\\').replace(/\\'/g, "'");
906 // JavaScript micro-templating, similar to John Resig's implementation
.
907 // Underscore templating handles arbitrary delimiters, preserves whitespace,
908 // and correctly escapes quotes within interpolated code.
909 _
.template = function(str
, data
) {
910 var c
= _
.templateSettings
;
911 var tmpl
= 'var __p=[],print=function(){__p.push.apply(__p,arguments);};' +
912 'with(obj||{}){__p.push(\'' +
913 str
.replace(/\\/g
, '\\\\')
914 .replace(/'/g, "\\'")
915 .replace(c.escape || noMatch, function(match, code) {
916 return "',_.escape(" + unescape(code) + "),'";
918 .replace(c.interpolate || noMatch, function(match, code) {
919 return "'," + unescape(code) + ",'";
921 .replace(c.evaluate || noMatch, function(match, code) {
922 return "');" + unescape(code).replace(/[\r\n\t]/g, ' ') + ";__p.push('";
924 .replace(/\r/g, '\\r')
925 .replace(/\n/g, '\\n')
926 .replace(/\t/g, '\\t')
927 + "');}return __p.join('');";
928 var func = new Function('obj
', '_
', tmpl);
929 if (data) return func(data, _);
930 return function(data) {
931 return func.call(this, data, _);
935 // Add a "chain" function, which will delegate to the wrapper.
936 _.chain = function(obj) {
937 return _(obj).chain();
943 // If Underscore is called as a function, it returns a wrapped object that
944 // can be used OO-style. This wrapper holds altered versions of all the
945 // underscore functions. Wrapped objects may be chained.
946 var wrapper = function(obj) { this._wrapped = obj; };
948 // Expose `wrapper.prototype` as `_.prototype`
949 _.prototype = wrapper.prototype;
951 // Helper function to continue chaining intermediate results.
952 var result = function(obj, chain) {
953 return chain ? _(obj).chain() : obj;
956 // A method to easily add functions to the OOP wrapper.
957 var addToWrapper = function(name, func) {
958 wrapper.prototype[name] = function() {
959 var args = slice.call(arguments);
960 unshift.call(args, this._wrapped);
961 return result(func.apply(_, args), this._chain);
965 // Add all of the Underscore functions to the wrapper object.
968 // Add all mutator Array functions to the wrapper.
969 each(['pop
', 'push
', 'reverse
', 'shift
', 'sort
', 'splice
', 'unshift
'], function(name) {
970 var method = ArrayProto[name];
971 wrapper.prototype[name] = function() {
972 var wrapped = this._wrapped;
973 method.apply(wrapped, arguments);
974 var length = wrapped.length;
975 if ((name == 'shift
' || name == 'splice
') && length === 0) delete wrapped[0];
976 return result(wrapped, this._chain);
980 // Add all accessor Array functions to the wrapper.
981 each(['concat
', 'join
', 'slice
'], function(name) {
982 var method = ArrayProto[name];
983 wrapper.prototype[name] = function() {
984 return result(method.apply(this._wrapped, arguments), this._chain);
988 // Start chaining a wrapped Underscore object.
989 wrapper.prototype.chain = function() {
994 // Extracts the result from a wrapped and chained object.
995 wrapper.prototype.value = function() {
996 return this._wrapped;