1 // ==========================================================================
  2 // Project:   SproutCore Costello - Property Observing Library
  3 // Copyright: ©2006-2011 Strobe Inc. and contributors.
  4 //            Portions ©2008-2011 Apple Inc. All rights reserved.
  5 // License:   Licensed under MIT license (see license.js)
  6 // ==========================================================================
  7 
  8 sc_require('mixins/enumerable');
  9 sc_require('mixins/observable');
 10 sc_require('mixins/freezable');
 11 sc_require('mixins/copyable');
 12 
 13 /**
 14   @class
 15 
 16   A collection of ranges.  You can use an IndexSet to keep track of non-
 17   continuous ranges of items in a parent array.  IndexSet's are used for
 18   selection, for managing invalidation ranges and other data-propagation.
 19 
 20   Examples
 21   ---
 22 
 23         var set = SC.IndexSet.create(ranges);
 24         set.contains(index);
 25         set.add(index, length);
 26         set.remove(index, length);
 27 
 28         // uses a backing SC.Array object to return each index
 29         set.forEach(function (object) { .. })
 30 
 31         // returns ranges
 32         set.forEachRange(function (start, length) { .. });
 33 
 34   Implementation Notes
 35   ---
 36 
 37   An IndexSet stores indices on the object.  A positive value great than the
 38   index tells you the end of an occupied range.  A negative values tells you
 39   the end of an empty range.  A value less than the index is a search
 40   accelerator.  It tells you the start of the nearest range.
 41 
 42   @extends SC.Enumerable
 43   @extends SC.Observable
 44   @extends SC.Copyable
 45   @extends SC.Freezable
 46   @since SproutCore 1.0
 47 */
 48 SC.IndexSet = SC.mixin({},
 49   SC.Observable, SC.Enumerable, SC.Freezable, SC.Copyable,
 50 /** @scope SC.IndexSet.prototype */ {
 51 
 52   /** @private
 53     Walks a content array and copies its contents to a new array.  For large
 54     content arrays this is faster than using slice()
 55   */
 56   _sc_sliceContent: function (c) {
 57     if (c.length < 1000) return c.slice(); // use native when faster
 58     var cur = 0, ret = [], next = c[0];
 59     while(next !== 0) {
 60       ret[cur] = next;
 61       cur = (next<0) ? (0-next) : next;
 62       next = c[cur];
 63     }
 64     ret[cur] = 0;
 65 
 66     this._hint(0, cur, ret); // hints are not copied manually - add them
 67     return ret;
 68   },
 69 
 70   //@if(debug)
 71   /** @private Validates the standard IndexSet method arguments. */
 72   _sc_validateIndexSetArguments: function (start, length) {
 73     // Validate arguments. Potential bad usages include trying to call SC.IndexSet.create() with SproutCore's standard property-hash
 74     // idiom, and passing in the results of bad math (NaN in particular causes problems).
 75     var startIsValid = NO,
 76         lengthIsValid = NO;
 77     // Unpack hash.
 78     if (SC.typeOf(start) === SC.T_HASH && !start.isIndexSet && SC.none(length)) {
 79       length = start.length;
 80       start = start.start;
 81     }
 82     // Validate start.
 83     if (SC.none(start)) startIsValid = YES;
 84     else if (SC.typeOf(start) === SC.T_NUMBER && !isNaN(start)) startIsValid = YES;
 85     else if (start.isIndexSet && SC.none(length)) startIsValid = YES;
 86     // Validate length.
 87     if (SC.none(start) && !SC.none(length)) lengthIsValid = NO; // stay invalid.
 88     else if (SC.none(length)) lengthIsValid = YES;
 89     else if (SC.typeOf(length) === SC.T_NUMBER && !isNaN(length)) lengthIsValid = YES;
 90 
 91     // Check validity and throw if needed.
 92     if (!startIsValid || !lengthIsValid) {
 93       var argsString = SC.A(arguments).join(', ');
 94       throw new Error("SC.IndexSet created with invalid parameters (%@). You must call SC.IndexSet with zero, one or two valid numeric arguments.".fmt(argsString));
 95     }
 96   },
 97   //@endif
 98 
 99   /**
100     To create an empty IndexSet, call `create` with no arguments. To create a set with one index, call `create` with one
101     argument: the index to add. To create a fuller set, call create with two arguments: the start index and the length to
102     add.
103 
104     To create a more complicated set of indices, create an index set and populate individual ranges using `.add()`.
105 
106     @param {Number|SC.IndexSet} start The start of the range or an index set.
107     @param {Number} [length] The length of the range (by default set to 1 if start is a Number)
108     @returns {SC.IndexSet}
109   */
110   create: function (start, length) {
111     //@if (debug)
112     this._sc_validateIndexSetArguments.apply(this, arguments);
113     //@endif
114 
115     var ret = SC.beget(this);
116     ret.initObservable();
117     ret.registerDependentKey('min', '[]');
118 
119     // optimized method to clone an index set.
120     if (start && start.isIndexSet) {
121       ret._content = this._sc_sliceContent(start._content);
122       ret.max = start.max;
123       ret.length = start.length;
124       ret.source = start.source;
125 
126     // otherwise just do a regular add
127     } else {
128       ret._content = [0];
129       if (start !== undefined) ret.add(start, length);
130     }
131     return ret;
132   },
133 
134   /**
135     Walk like a duck.
136 
137     @type Boolean
138   */
139   isIndexSet: YES,
140 
141   /**  @private
142     Internal setting determines the preferred skip size for hinting sets.
143 
144     @type Number
145   */
146   HINT_SIZE: 256,
147 
148   /**
149     Total number of indexes contained in the set
150 
151     @type Number
152   */
153   length: 0,
154 
155   /**
156     One greater than the largest index currently stored in the set.  This
157     is sometimes useful when determining the total range of items covering
158     the index set.
159 
160     @type Number
161   */
162   max: 0,
163 
164   /**
165     The first index included in the set or -1.
166 
167     @type Number
168   */
169   min: function () {
170     var content = this._content,
171         cur = content[0];
172     return (cur === 0) ? -1 : (cur>0) ? 0 : Math.abs(cur);
173 
174   }.property('[]').cacheable(),
175 
176   /**
177     Returns the first index in the set .
178 
179     @type Number
180   */
181   firstObject: function () {
182     return (this.get('length')>0) ? this.get('min') : undefined;
183   }.property(),
184 
185   /**
186     Returns the starting index of the nearest range for the specified
187     index.
188 
189     @param {Number} index
190     @returns {Number} starting index
191   */
192   rangeStartForIndex: function (index) {
193     var content = this._content,
194         max     = this.get('max'),
195         ret, next, accel;
196 
197     // fast cases
198     if (index >= max) return max;
199     if (Math.abs(content[index]) > index) return index; // we hit a border
200 
201     // use accelerator to find nearest content range
202     accel = index - (index % SC.IndexSet.HINT_SIZE);
203     ret = content[accel];
204 
205     // If there are no hints, we are in the infinite range.
206     if (SC.none(ret)) { ret = this._infRange; }
207 
208     if (ret<0 || ret>index) ret = accel;
209     next = content[ret];
210 
211     // the accelerator pointed to the middle of a range
212     if (next === undefined) {
213       next = this.rangeStartForIndex(ret);
214     } else {
215       next = Math.abs(next);
216     }
217 
218     // now step forward through ranges until we find one that includes the
219     // index.
220     while (next < index) {
221       ret = next;
222       next = Math.abs(content[ret]);
223     }
224     return ret;
225   },
226 
227   /**
228     Returns YES if the passed index set contains the exact same indexes as
229     the receiver.  If you pass any object other than an index set, returns NO.
230 
231     @param {Object} obj another object.
232     @returns {Boolean}
233   */
234   isEqual: function (obj) {
235 
236     // optimize for some special cases
237     if (obj === this) return YES;
238     if (!obj || !obj.isIndexSet || (obj.max !== this.max) || (obj.length !== this.length)) return NO;
239 
240     // ok, now we need to actually compare the ranges of the two.
241     var lcontent = this._content,
242         rcontent = obj._content,
243         cur      = 0,
244         next     = lcontent[cur];
245 
246     do {
247       if (rcontent[cur] !== next) return NO;
248       cur = Math.abs(next);
249       next = lcontent[cur];
250     } while (cur !== 0);
251     return YES;
252   },
253 
254   /**
255     Returns the first index in the set before the passed index or null if
256     there are no previous indexes in the set.
257 
258     @param {Number} index index to check
259     @returns {Number} index or -1
260   */
261   indexBefore: function (index) {
262 
263     if (index === 0) return -1; // fast path
264     index--; // start with previous index
265 
266     var content = this._content,
267         max     = this.get('max'),
268         start   = this.rangeStartForIndex(index);
269     if (!content) return null;
270 
271     if (!isFinite(start)) return index; // fast path
272 
273     // loop backwards until we find a range that is in the set.
274     while((start===max) || (content[start]<0)) {
275       if (start === 0) return -1; // nothing before; just quit
276       index = start - 1;
277       start = this.rangeStartForIndex(index);
278     }
279 
280     return index;
281   },
282 
283   /**
284     Returns the first index in the set after the passed index or null if
285     there are no additional indexes in the set.
286 
287     @param {Number} index index to check
288     @returns {Number} index or -1
289   */
290   indexAfter: function (index) {
291     var content = this._content,
292         max     = this.get('max'),
293         start, next;
294 
295     if (!content || (index >= max)) return -1; // fast path
296     index++; // start with next index
297 
298     // loop forwards until we find a range that is in the set.
299     start = this.rangeStartForIndex(index);
300     next  = content[start];
301     while(next<0) {
302       if (next === 0) return -1; //nothing after; just quit
303       index = start = Math.abs(next);
304       next  = content[start];
305     }
306 
307     return index;
308   },
309 
310   /**
311     Returns YES if the index set contains the named index
312 
313     @param {Number} start index or range
314     @param {Number} length optional range length
315     @returns {Boolean}
316   */
317   contains: function (start, length) {
318     //@if (debug)
319     this._sc_validateIndexSetArguments.apply(this, arguments);
320     //@endif
321 
322     var content, cur, next, rstart, rnext;
323 
324     // normalize input
325     if (length === undefined) {
326       if (start === null || start === undefined) return NO;
327 
328       if (typeof start === SC.T_NUMBER) {
329         length = 1;
330 
331       // if passed an index set, check each receiver range
332       } else if (start && start.isIndexSet) {
333         if (start === this) return YES; // optimization
334 
335         content = start._content;
336         cur = 0;
337         next = content[cur];
338         while (next !== 0) {
339           if ((next>0) && !this.contains(cur, next-cur)) return NO;
340           cur = Math.abs(next);
341           next = content[cur];
342         }
343         return YES;
344 
345       } else {
346         length = start.length;
347         start = start.start;
348       }
349     }
350 
351     rstart = this.rangeStartForIndex(start);
352     if (isFinite(rstart)) {
353       rnext  = this._content[rstart];
354 
355       return (rnext>0) && (rstart <= start) && (rnext >= (start+length));
356     } else {
357       return true;
358     }
359   },
360 
361   /**
362     Returns YES if the index set contains any of the passed indexes.  You
363     can pass a single index, a range or an index set.
364 
365     @param {Number} start index, range, or IndexSet
366     @param {Number} length optional range length
367     @returns {Boolean}
368   */
369   intersects: function (start, length) {
370     //@if (debug)
371     this._sc_validateIndexSetArguments.apply(this, arguments);
372     //@endif
373 
374     var content, cur, next, lim;
375 
376     // normalize input
377     if (length === undefined) {
378       if (typeof start === SC.T_NUMBER) {
379         length = 1;
380 
381       // if passed an index set, check each receiver range
382       } else if (start && start.isIndexSet) {
383         if (start === this) return YES; // optimization
384 
385         content = start._content;
386         cur = 0;
387         next = content[cur];
388         while (next !== 0) {
389           if ((next>0) && this.intersects(cur, next-cur)) return YES;
390           cur = Math.abs(next);
391           next = content[cur];
392         }
393         return NO;
394 
395       } else {
396         length = start.length;
397         start = start.start;
398       }
399     }
400 
401     cur     = this.rangeStartForIndex(start);
402     content = this._content;
403     next    = content[cur];
404     lim     = start + length;
405     while (cur < lim) {
406       if (next === 0) return NO; // no match and at end!
407       if ((next > 0) && (next > start)) return YES; // found a match
408       cur = Math.abs(next);
409       next = content[cur];
410     }
411     return NO; // no match
412   },
413 
414   /**
415     Returns a new IndexSet without the passed range or indexes.   This is a
416     convenience over simply cloning and removing.  Does some optimizations.
417 
418     @param {Number} start index, range, or IndexSet
419     @param {Number} length optional range length
420     @returns {SC.IndexSet} new index set
421   */
422   without: function (start, length) {
423     if (start === this) return SC.IndexSet.create(); // just need empty set
424     return this.clone().remove(start, length);
425   },
426 
427   /**
428     Replace the index set's current content with the passed index set.  This
429     is faster than clearing the index set adding the values again.
430 
431     @param {Number} start index, Range, or another IndexSet
432     @param {Number} length optional length of range.
433     @returns {SC.IndexSet} receiver
434   */
435   replace: function (start, length) {
436     //@if (debug)
437     this._sc_validateIndexSetArguments.apply(this, arguments);
438     //@endif
439 
440     if (length === undefined) {
441       if (typeof start === SC.T_NUMBER) {
442         length = 1;
443       } else if (start && start.isIndexSet) {
444         this._content = this._sc_sliceContent(start._content);
445         this.beginPropertyChanges()
446           .set('max', start.max)
447           .set('length', start.length)
448           .set('source', start.source)
449           .enumerableContentDidChange();
450         this.endPropertyChanges();
451         return this;
452 
453       } else {
454         length = start.length;
455         start  = start.start;
456       }
457     }
458 
459     this._content.length=1;
460     this._content[0] = 0;
461     this.length = this.max = 0; // reset without notifying since add()
462     return this.add(start, length);
463   },
464 
465   /**
466     Adds the specified range of indexes to the set.  You can also pass another
467     IndexSet to union the contents of the index set with the receiver.
468 
469     @param {Number} start Start index, Range, or another IndexSet
470     @param {Number} [length=1] The length of range.
471     @returns {SC.IndexSet} receiver
472   */
473   add: function (start, length) {
474     //@if (debug)
475     this._sc_validateIndexSetArguments.apply(this, arguments);
476     //@endif
477 
478     if (this.isFrozen) throw new Error(SC.FROZEN_ERROR);
479 
480     var content, cur, next;
481 
482     // normalize IndexSet input
483     if (start && start.isIndexSet) {
484 
485       content = start._content;
486 
487       if (!content) return this; // nothing to do
488 
489       cur = 0;
490       next = content[0];
491       while(next !== 0) {
492         if (next>0) this.add(cur, next-cur);
493         cur = next<0 ? 0-next : next;
494         next = content[cur];
495       }
496       return this;
497 
498     } else if (length === undefined) {
499 
500       if (start === null || start === undefined) {
501         return this; // nothing to do
502       } else if (typeof start === SC.T_NUMBER) {
503         length = 1;
504       } else {
505         length = start.length;
506         start = start.start;
507       }
508     } else if (length === null) length = 1;
509 
510     // if no length - do nothing.
511     if (length <= 0) return this;
512 
513     // special case - appending to end of set
514     var max     = this.get('max'),
515         oldmax  = max,
516         delta, value;
517 
518     content = this._content;
519 
520     if (start === max) {
521 
522       // if adding to the end and the end is in set, merge.
523       if (start > 0) {
524         cur = this.rangeStartForIndex(start-1);
525         next = content[cur];
526 
527         // just extend range at end
528         if (next > 0) {
529           delete content[max]; // no 0
530           content[cur] = max = start + length;
531           start = cur;
532 
533         // previous range was not in set, just tack onto the end
534         } else {
535           content[max] = max = start + length;
536         }
537       } else {
538         content[start] = max = length;
539       }
540 
541       content[max] = 0;
542       this.set('max', max);
543       this.set('length', this.length + length);
544       length = max - start;
545 
546     } else if (start > max) {
547       content[max] = 0-start; // empty!
548       content[start] = start+length;
549       content[start+length] = 0; // set end
550       this.set('max', start + length);
551       this.set('length', this.length + length);
552 
553       // affected range goes from starting range to end of content.
554       length = start + length - max;
555       start = max;
556 
557     // otherwise, merge into existing range
558     } else {
559 
560       // find nearest starting range.  split or join that range
561       cur   = this.rangeStartForIndex(start);
562       next  = content[cur];
563       max   = start + length;
564       delta = 0;
565 
566       // we are right on a boundary and we had a range or were the end, then
567       // go back one more.
568       if ((start>0) && (cur === start) && (next <= 0)) {
569         cur = this.rangeStartForIndex(start-1);
570         next = content[cur];
571       }
572 
573       // previous range is not in set.  splice it here
574       if (next < 0) {
575         content[cur] = 0-start;
576 
577         // if previous range extends beyond this range, splice afterwards also
578         if (Math.abs(next) > max) {
579           content[start] = 0-max;
580           content[max] = next;
581         } else content[start] = next;
582 
583       // previous range is in set.  merge the ranges
584       } else {
585         start = cur;
586         if (next > max) {
587           // delta -= next - max;
588           max = next;
589         }
590       }
591 
592       // at this point there should be clean starting point for the range.
593       // just walk the ranges, adding up the length delta and then removing
594       // the range until we find a range that passes last
595       cur = start;
596       while (cur < max) {
597         // get next boundary.  splice if needed - if value is 0, we are at end
598         // just skip to last
599         value = content[cur];
600         if (value === 0) {
601           content[max] = 0;
602           next = max;
603           delta += max - cur;
604         } else {
605           next  = Math.abs(value);
606           if (next > max) {
607             content[max] = value;
608             next = max;
609           }
610 
611           // ok, cur range is entirely inside top range.
612           // add to delta if needed
613           if (value < 0) delta += next - cur;
614         }
615 
616         delete content[cur]; // and remove range
617         cur = next;
618       }
619 
620       // cur should always === last now.  if the following range is in set,
621       // merge in also - don't adjust delta because these aren't new indexes
622       if ((cur = content[max]) > 0) {
623         delete content[max];
624         max = cur;
625       }
626 
627       // finally set my own range.
628       content[start] = max;
629       if (max > oldmax) this.set('max', max);
630 
631       // adjust length
632       this.set('length', this.get('length') + delta);
633 
634       // compute hint range
635       length = max - start;
636     }
637 
638     this._hint(start, length);
639     if (delta !== 0) this.enumerableContentDidChange();
640     return this;
641   },
642 
643   /**
644     Removes the specified range of indexes from the set
645 
646     @param {Number} start index, Range, or IndexSet
647     @param {Number} length optional length of range.
648     @returns {SC.IndexSet} receiver
649   */
650   remove: function (start, length) {
651     //@if (debug)
652     this._sc_validateIndexSetArguments.apply(this, arguments);
653     //@endif
654 
655     if (this.isFrozen) throw new Error(SC.FROZEN_ERROR);
656 
657     // normalize input
658     if (length === undefined) {
659       if (start === null || start === undefined) {
660         return this; // nothing to do
661 
662       } else if (typeof start === SC.T_NUMBER) {
663         length = 1;
664 
665       // if passed an index set, just add each range in the index set.
666       } else if (start.isIndexSet) {
667         start.forEachRange(this.remove, this);
668         return this;
669 
670       } else {
671         length = start.length;
672         start = start.start;
673       }
674     }
675 
676     if (length <= 0) return this; // nothing to do
677 
678     // special case - appending to end of set
679     var max     = this.get('max'),
680         content = this._content,
681         cur, next, delta, value, last;
682 
683     // if we're past the end, do nothing.
684     if (start >= max) return this;
685 
686     // find nearest starting range.  split or join that range
687     cur   = this.rangeStartForIndex(start);
688     next  = content[cur];
689     last  = start + length;
690     delta = 0;
691 
692     // we are right on a boundary and we had a range or were the end, then
693     // go back one more.
694     if ((start > 0) && (cur === start) && (next > 0)) {
695       cur = this.rangeStartForIndex(start-1);
696       next = content[cur];
697     }
698 
699     // previous range is in set.  splice it here
700     if (next > 0) {
701       content[cur] = start;
702 
703       // if previous range extends beyond this range, splice afterwards also
704       if (next > last) {
705         content[start] = last;
706         content[last] = next;
707       } else content[start] = next;
708 
709     // previous range is not in set.  merge the ranges
710     } else {
711       start = cur;
712       next  = Math.abs(next);
713       if (next > last) {
714         last = next;
715       }
716     }
717 
718     // If splicing into the infinite range, we have to add hints up to the start
719     // of the splice and adjust our pointer to the start of the infinite range.
720     if (!isFinite(next)) {
721       this._hint(cur, start - cur);
722 
723       // Infinite range
724       this._infRange = last;
725     }
726 
727     // at this point there should be clean starting point for the range.
728     // just walk the ranges, adding up the length delta and then removing
729     // the range until we find a range that passes last
730     cur = start;
731     while (cur < last) {
732       // get next boundary.  splice if needed - if value is 0, we are at end
733       // just skip to last
734       value = content[cur];
735       if (value === 0) {
736         content[last] = 0;
737         next = last;
738 
739       } else {
740         next  = Math.abs(value);
741         if (next > last) {
742           content[last] = value;
743           next = last;
744         }
745 
746         // ok, cur range is entirely inside top range.
747         // add to delta if needed
748         if (value > 0) delta += next - cur;
749       }
750 
751       delete content[cur]; // and remove range
752       cur = next;
753     }
754 
755     // cur should always === last now.  if the following range is not in set,
756     // merge in also - don't adjust delta because these aren't new indexes
757     if ((cur = content[last]) < 0) {
758       delete content[last];
759       last = Math.abs(cur);
760     }
761 
762     // set my own range - if the next item is 0, then clear it.
763     if (content[last] === 0) {
764       delete content[last];
765       content[start] = 0;
766       this.set('max', start); //max has changed
767 
768     } else {
769       content[start] = 0-last;
770     }
771 
772     // adjust length
773     if (isFinite(delta)) {
774       this.set('length', this.get('length') - delta);
775     } else {
776       this.set('length', 0);
777     }
778 
779     // compute hint range.  Constrain it to the length of the content.
780     length = Math.min(content.length, last - start);
781 
782     this._hint(start, length);
783     if (delta !== 0) this.enumerableContentDidChange();
784     return this;
785   },
786 
787   /** @private
788     iterates through a named range, setting hints every HINT_SIZE indexes
789     pointing to the nearest range start.  The passed range must start on a
790     range boundary.  It can end anywhere.
791   */
792   _hint: function (start, length, content) {
793     if (content === undefined) content = this._content;
794 
795     var skip    = SC.IndexSet.HINT_SIZE,
796         next    = Math.abs(content[start]), // start of next range
797         loc     = start - (start % skip) + skip, // next hint loc
798         lim     = start + length; // stop
799 
800     while (loc < lim) {
801       // make sure we are in current range
802       while ((next !== 0) && (next <= loc)) {
803         start = next;
804         next  = Math.abs(content[start]);
805       }
806 
807       // past end
808       if (next === 0) {
809         delete content[loc];
810 
811       } else if (!isFinite(next)) {
812         // We can't hint the infinite range the normal way.  Instead we have a
813         // single pointer to the start of the infinite range that we use when
814         // no hints exist.
815         this._infRange = start;
816         loc = Infinity;
817 
818       // do not change if on actual boundary
819       } else if (loc !== start) {
820         content[loc] = start;  // set hint
821       }
822 
823       loc += skip;
824     }
825   },
826 
827   /**
828     Clears the set
829   */
830   clear: function () {
831     if (this.isFrozen) throw new Error(SC.FROZEN_ERROR);
832 
833     var oldlen = this.length;
834     this._content.length = 1;
835     this._content[0] = 0;
836     this._infRange = null;
837     this.set('length', 0).set('max', 0);
838     if (oldlen > 0) this.enumerableContentDidChange();
839   },
840 
841   /**
842     Add all the ranges in the passed array.
843 
844     @param {Enumerable} objects The list of ranges you want to add
845   */
846   addEach: function (objects) {
847     if (this.isFrozen) throw new Error(SC.FROZEN_ERROR);
848 
849     this.beginPropertyChanges();
850     var idx = objects.get('length');
851     if (objects.isSCArray) {
852       while(--idx >= 0) this.add(objects.objectAt(idx));
853     } else if (objects.isEnumerable) {
854       objects.forEach(function (idx) { this.add(idx); }, this);
855     }
856     this.endPropertyChanges();
857 
858     return this;
859   },
860 
861   /**
862     Removes all the ranges in the passed array.
863 
864     @param {Object...} objects The list of objects you want to remove
865   */
866   removeEach: function (objects) {
867     if (this.isFrozen) throw new Error(SC.FROZEN_ERROR);
868 
869     this.beginPropertyChanges();
870 
871     var idx = objects.get('length');
872     if (objects.isSCArray) {
873       while(--idx >= 0) this.remove(objects.objectAt(idx));
874     } else if (objects.isEnumerable) {
875       objects.forEach(function (idx) { this.remove(idx); }, this);
876     }
877 
878     this.endPropertyChanges();
879 
880     return this;
881   },
882 
883   /**
884    Clones the set into a new set.
885   */
886   clone: function () {
887     return SC.IndexSet.create(this);
888   },
889 
890   /**
891     Returns a string describing the internal range structure.  Useful for
892     debugging.
893 
894     @returns {String}
895   */
896   inspect: function () {
897     var content = this._content,
898         len     = content.length,
899         idx     = 0,
900         ret     = [],
901         item;
902 
903     for(idx=0;idx<len;idx++) {
904       item = content[idx];
905       if (item !== undefined) ret.push("%@:%@".fmt(idx,item));
906     }
907     return "SC.IndexSet<%@>".fmt(ret.join(' , '));
908   },
909 
910   /**
911     Invoke the callback, passing each occupied range instead of each
912     index.  This can be a more efficient way to iterate in some cases.  The
913     callback should have the signature:
914 
915           callback(start, length, indexSet, source) { ... }
916 
917     If you pass a target as a second option, the callback will be called in
918     the target context.
919 
920     @param {Function} callback The method to run on each iteration
921     @param {Object} target the object to call the callback on
922     @returns {SC.IndexSet} receiver
923   */
924   forEachRange: function (callback, target) {
925     var content = this._content,
926         cur     = 0,
927         next    = content[cur],
928         source  = this.source;
929 
930     if (target === undefined) target = null;
931     while (next !== 0) {
932       if (next > 0) callback.call(target, cur, next - cur, this, source);
933       cur  = Math.abs(next);
934       next = content[cur];
935     }
936 
937     return this;
938   },
939 
940   /**
941     Invokes the callback for each index within the passed start/length range.
942     Otherwise works just like regular forEach().
943 
944     @param {Number} start starting index
945     @param {Number} length length of range
946     @param {Function} callback
947     @param {Object} target
948     @returns {SC.IndexSet} receiver
949   */
950   forEachIn: function (start, length, callback, target) {
951     var content = this._content,
952         cur     = 0,
953         idx     = 0,
954         lim     = start + length,
955         source  = this.source,
956         next    = content[cur];
957 
958     if (target === undefined) target = null;
959     while (next !== 0) {
960       if (cur < start) cur = start; // skip forward
961       while((cur < next) && (cur < lim)) {
962         callback.call(target, cur++, idx++, this, source);
963       }
964 
965       if (cur >= lim) {
966         cur = next = 0;
967       } else {
968         cur  = Math.abs(next);
969         next = content[cur];
970       }
971     }
972     return this;
973   },
974 
975   /**
976     Total number of indexes within the specified range.
977 
978     @param {Number|SC.IndexSet} start index, range object or IndexSet
979     @param {Number} length optional range length
980     @returns {Number} count of indexes
981   */
982   lengthIn: function (start, length) {
983     //@if (debug)
984     this._sc_validateIndexSetArguments.apply(this, arguments);
985     //@endif
986 
987     var ret = 0;
988 
989     // normalize input
990     if (length === undefined) {
991       if (start === null || start === undefined) {
992         return 0; // nothing to do
993 
994       } else if (typeof start === SC.T_NUMBER) {
995         length = 1;
996 
997       // if passed an index set, just add each range in the index set.
998       } else if (start.isIndexSet) {
999         start.forEachRange(function (start, length) {
1000           ret += this.lengthIn(start, length);
1001         }, this);
1002         return ret;
1003 
1004       } else {
1005         length = start.length;
1006         start = start.start;
1007       }
1008     }
1009 
1010     // fast path
1011     if (this.get('length') === 0) return 0;
1012 
1013     var content = this._content,
1014         cur     = 0,
1015         next    = content[cur],
1016         lim     = start + length;
1017 
1018     while (cur<lim && next !== 0) {
1019       if (next>0) {
1020         ret += (next>lim) ? lim-cur : next-cur;
1021       }
1022       cur  = Math.abs(next);
1023       next = content[cur];
1024     }
1025 
1026     return ret;
1027   },
1028 
1029   // ..........................................................
1030   // OBJECT API
1031   //
1032 
1033   /**
1034     Optionally set the source property on an index set and then you can
1035     iterate over the actual object values referenced by the index set.  See
1036     indexOf(), lastIndexOf(), forEachObject(), addObject() and removeObject().
1037   */
1038   source: null,
1039 
1040   /**
1041     Returns the first index in the set that matches the passed object.  You
1042     must have a source property on the set for this to work.
1043 
1044     @param {Object} object the object to check
1045     @param {Number} startAt optional starting point
1046     @returns {Number} found index or -1 if not in set
1047   */
1048   indexOf: function (object, startAt) {
1049     var source  = this.source;
1050     if (!source) throw new Error("%@.indexOf() requires source".fmt(this));
1051 
1052     var len     = source.get('length'),
1053 
1054         // start with the first index in the set
1055         content = this._content,
1056         cur     = content[0]<0 ? Math.abs(content[0]) : 0,
1057         idx;
1058 
1059     while(cur>=0 && cur<len) {
1060       idx = source.indexOf(object, cur);
1061       if (idx<0) return -1; // not found in source
1062       if (this.contains(idx)) return idx; // found in source and in set.
1063       cur = idx+1;
1064     }
1065 
1066     return -1; // not found
1067   },
1068 
1069   /**
1070     Returns the last index in the set that matches the passed object.  You
1071     must have a source property on the set for this to work.
1072 
1073     @param {Object} object the object to check
1074     @param {Number} startAt optional starting point
1075     @returns {Number} found index or -1 if not in set
1076   */
1077   lastIndexOf: function (object, startAt) {
1078     var source  = this.source;
1079     if (!source) throw new Error("%@.lastIndexOf() requires source".fmt(this));
1080 
1081     // start with the last index in the set
1082     var len     = source.get('length'),
1083         cur     = this.max-1,
1084         idx;
1085 
1086     if (cur >= len) cur = len-1;
1087     while (cur>=0) {
1088       idx = source.lastIndexOf(object, cur);
1089       if (idx<0) return -1; // not found in source
1090       if (this.contains(idx)) return idx; // found in source and in set.
1091       cur = idx+1;
1092     }
1093 
1094     return -1; // not found
1095   },
1096 
1097   /**
1098     Iterates through the objects at each index location in the set.  You must
1099     have a source property on the set for this to work.  The callback you pass
1100     will be invoked for each object in the set with the following signature:
1101 
1102           function callback(object, index, source, indexSet) { ... }
1103 
1104     If you pass a target, it will be used when the callback is called.
1105 
1106     @param {Function} callback function to invoke.
1107     @param {Object} target optional content. otherwise uses window
1108     @returns {SC.IndexSet} receiver
1109   */
1110   forEachObject: function (callback, target) {
1111     var source  = this.source;
1112     if (!source) throw new Error("%@.forEachObject() requires source".fmt(this));
1113 
1114     var content = this._content,
1115         cur     = 0,
1116         next    = content[cur];
1117 
1118     if (target === undefined) target = null;
1119     while (next !== 0) {
1120 
1121       while(cur < next) {
1122         callback.call(target, source.objectAt(cur), cur, source, this);
1123         cur++;
1124       }
1125 
1126       cur  = Math.abs(next);
1127       next = content[cur];
1128     }
1129     return this;
1130   },
1131 
1132   /**
1133     Adds all indexes where the object appears to the set.  If firstOnly is
1134     passed, then it will find only the first index and add it.  If  you know
1135     the object only appears in the source array one time, firstOnly may make
1136     this method faster.
1137 
1138     Requires source to work.
1139 
1140     @param {Object} object the object to add
1141     @param {Boolean} firstOnly Set to true if you can assume that the first
1142        match is the only one
1143     @returns {SC.IndexSet} receiver
1144   */
1145   addObject: function (object, firstOnly) {
1146     var source  = this.source;
1147     if (!source) throw new Error("%@.addObject() requires source".fmt(this));
1148 
1149     var len = source.get('length'),
1150         cur = 0, idx;
1151 
1152     while(cur>=0 && cur<len) {
1153       idx = source.indexOf(object, cur);
1154       if (idx >= 0) {
1155         this.add(idx);
1156         if (firstOnly) return this;
1157         cur = idx++;
1158       } else return this;
1159     }
1160     return this;
1161   },
1162 
1163   /**
1164     Adds any indexes matching the passed objects.  If firstOnly is passed,
1165     then only finds the first index for each object.
1166 
1167     @param {SC.Enumerable} objects the objects to add
1168     @param {Boolean} firstOnly Set to true if you can assume that the first
1169        match is the only one
1170     @returns {SC.IndexSet} receiver
1171   */
1172   addObjects: function (objects, firstOnly) {
1173     objects.forEach(function (object) {
1174       this.addObject(object, firstOnly);
1175     }, this);
1176     return this;
1177   },
1178 
1179   /**
1180     Removes all indexes where the object appears to the set.  If firstOnly is
1181     passed, then it will find only the first index and add it.  If  you know
1182     the object only appears in the source array one time, firstOnly may make
1183     this method faster.
1184 
1185     Requires source to work.
1186 
1187     @param {Object} object the object to add
1188     @param {Boolean} firstOnly Set to true if you can assume that the first
1189        match is the only one
1190     @returns {SC.IndexSet} receiver
1191   */
1192   removeObject: function (object, firstOnly) {
1193     var source  = this.source;
1194     if (!source) throw new Error("%@.removeObject() requires source".fmt(this));
1195 
1196     var len = source.get('length'),
1197         cur = 0, idx;
1198 
1199     while(cur>=0 && cur<len) {
1200       idx = source.indexOf(object, cur);
1201       if (idx >= 0) {
1202         this.remove(idx);
1203         if (firstOnly) return this;
1204         cur = idx+1;
1205       } else return this;
1206     }
1207     return this;
1208   },
1209 
1210   /**
1211     Removes any indexes matching the passed objects.  If firstOnly is passed,
1212     then only finds the first index for each object.
1213 
1214     @param {SC.Enumerable} objects the objects to add
1215     @param {Boolean} firstOnly Set to true if you can assume that the first
1216        match is the only one
1217     @returns {SC.IndexSet} receiver
1218   */
1219   removeObjects: function (objects, firstOnly) {
1220     objects.forEach(function (object) {
1221       this.removeObject(object, firstOnly);
1222     }, this);
1223     return this;
1224   },
1225 
1226 
1227   // .......................................
1228   // PRIVATE
1229   //
1230 
1231   /**
1232     Usually observing notifications from IndexSet are not useful, so
1233     suppress them by default.
1234 
1235     @type Boolean
1236   */
1237   LOG_OBSERVING: NO,
1238 
1239   /** @private - optimized call to forEach() */
1240   forEach: function (callback, target) {
1241     var content = this._content,
1242         cur     = 0,
1243         idx     = 0,
1244         source  = this.source,
1245         next    = content[cur];
1246 
1247     if (target === undefined) target = null;
1248     while (next !== 0) {
1249       if (isFinite(next)) {
1250         while(cur < next) {
1251           callback.call(target, cur++, idx++, this, source);
1252         }
1253         cur  = Math.abs(next);
1254         next = content[cur];
1255       } else {
1256         throw new Error("Developer Error: You may not iterate an infinite range in SC.IndexSet.");
1257       }
1258     }
1259     return this;
1260   },
1261 
1262   /** @private - support iterators */
1263   nextObject: function (ignore, idx, context) {
1264     var content = this._content,
1265         next    = context.next,
1266         max     = this.get('max'); // next boundary
1267 
1268     // seed.
1269     if (idx === null) {
1270       idx = next = 0;
1271 
1272     } else if (idx >= max) {
1273       delete context.next; // cleanup context
1274       return null; // nothing left to do
1275 
1276     } else idx++; // look on next index
1277 
1278     // look for next non-empty range if needed.
1279     if (idx === next) {
1280       do {
1281         idx = Math.abs(next);
1282         next = content[idx];
1283       } while(next < 0);
1284       context.next = next;
1285     }
1286 
1287     return idx;
1288   },
1289 
1290   toString: function () {
1291     var str = [];
1292     this.forEachRange(function (start, length) {
1293       str.push(length === 1 ? start : "%@..%@".fmt(start, start + length - 1));
1294     }, this);
1295     return "SC.IndexSet<%@>".fmt(str.join(','));
1296   }
1297 
1298 });
1299 
1300 SC.IndexSet.slice = SC.IndexSet.copy = SC.IndexSet.clone;
1301 SC.IndexSet.EMPTY = SC.IndexSet.create().freeze();
1302