API  0.9.7
 All Classes Files Functions Variables Macros Groups Pages
CPIndexSet.j
Go to the documentation of this file.
1 /*
2  * CPIndexSet.j
3  * Foundation
4  *
5  * Created by Francisco Tolmasky.
6  * Copyright 2008, 280 North, Inc.
7  *
8  * This library is free software; you can redistribute it and/or
9  * modify it under the terms of the GNU Lesser General Public
10  * License as published by the Free Software Foundation; either
11  * version 2.1 of the License, or (at your option) any later version.
12  *
13  * This library is distributed in the hope that it will be useful,
14  * but WITHOUT ANY WARRANTY; without even the implied warranty of
15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
16  * Lesser General Public License for more details.
17  *
18  * You should have received a copy of the GNU Lesser General Public
19  * License along with this library; if not, write to the Free Software
20  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
21  */
22 
23 #include "Foundation.h"
24 
25 
34 @implementation CPIndexSet : CPObject
35 {
36  unsigned _count;
37  CPArray _ranges;
38 }
39 
40 // Creating an Index Set
44 + (id)indexSet
45 {
46  return [[self alloc] init];
47 }
48 
52 + (id)indexSetWithIndex:(int)anIndex
53 {
54  return [[self alloc] initWithIndex:anIndex];
55 }
56 
61 + (id)indexSetWithIndexesInRange:(CPRange)aRange
62 {
63  return [[self alloc] initWithIndexesInRange:aRange];
64 }
65 
66 // Initializing and Index Set
67 
68 - (id)init
69 {
70  return [self initWithIndexesInRange:CPMakeRange(0, 0)];
71 }
72 
77 - (id)initWithIndex:(CPInteger)anIndex
78 {
79  if (!_IS_NUMERIC(anIndex))
80  [CPException raise:CPInvalidArgumentException
81  reason:"Invalid index"];
82 
83  return [self initWithIndexesInRange:CPMakeRange(anIndex, 1)];
84 }
85 
91 - (id)initWithIndexesInRange:(CPRange)aRange
92 {
93  if (aRange.location < 0)
94  [CPException raise:CPInvalidArgumentException reason:"Range " + CPStringFromRange(aRange) + " is out of bounds."];
95 
96  self = [super init];
97 
98  if (self)
99  {
100  _count = MAX(0, aRange.length);
101 
102  if (_count > 0)
103  _ranges = [aRange];
104  else
105  _ranges = [];
106  }
107 
108  return self;
109 }
110 
116 - (id)initWithIndexSet:(CPIndexSet)anIndexSet
117 {
118  self = [super init];
119 
120  if (self)
121  {
122  _count = [anIndexSet count];
123  _ranges = [];
124 
125  var otherRanges = anIndexSet._ranges,
126  otherRangesCount = otherRanges.length;
127 
128  while (otherRangesCount--)
129  _ranges[otherRangesCount] = CPMakeRangeCopy(otherRanges[otherRangesCount]);
130  }
131 
132  return self;
133 }
134 
135 - (BOOL)isEqual:(id)anObject
136 {
137  if (self === anObject)
138  return YES;
139 
140  if (!anObject || ![anObject isKindOfClass:[CPIndexSet class]])
141  return NO;
142 
143  return [self isEqualToIndexSet:anObject];
144 }
145 
146 // Querying an Index Set
152 - (BOOL)isEqualToIndexSet:(CPIndexSet)anIndexSet
153 {
154  if (!anIndexSet)
155  return NO;
156 
157  // Comparisons to ourself are always return YES.
158  if (self === anIndexSet)
159  return YES;
160 
161  var rangesCount = _ranges.length,
162  otherRanges = anIndexSet._ranges;
163 
164  // If we have a discrepancy in the number of ranges or the number of indexes,
165  // simply return NO.
166  if (rangesCount !== otherRanges.length || _count !== anIndexSet._count)
167  return NO;
168 
169  while (rangesCount--)
170  if (!CPEqualRanges(_ranges[rangesCount], otherRanges[rangesCount]))
171  return NO;
172 
173  return YES;
174 }
175 
176 - (BOOL)isEqual:(id)anObject
177 {
178  return self === anObject ||
179  [anObject isKindOfClass:[self class]] &&
180  [self isEqualToIndexSet:anObject];
181 }
182 
188 - (BOOL)containsIndex:(CPInteger)anIndex
189 {
190  return positionOfIndex(_ranges, anIndex) !== CPNotFound;
191 }
192 
197 - (BOOL)containsIndexesInRange:(CPRange)aRange
198 {
199  if (aRange.length <= 0)
200  return NO;
201 
202  // If we have less total indexes than aRange, we can't possibly contain aRange.
203  if (_count < aRange.length)
204  return NO;
205 
206  // Search for first location
207  var rangeIndex = positionOfIndex(_ranges, aRange.location);
208 
209  // If we don't have the first location, then we don't contain aRange.
210  if (rangeIndex === CPNotFound)
211  return NO;
212 
213  var range = _ranges[rangeIndex];
214 
215  // The intersection must contain all the indexes from the original range.
216  return CPIntersectionRange(range, aRange).length === aRange.length;
217 }
218 
223 - (BOOL)containsIndexes:(CPIndexSet)anIndexSet
224 {
225  var otherCount = anIndexSet._count;
226 
227  if (otherCount <= 0)
228  return YES;
229 
230  // If we have less total indexes than anIndexSet, we can't possibly contain aRange.
231  if (_count < otherCount)
232  return NO;
233 
234  var otherRanges = anIndexSet._ranges,
235  otherRangesCount = otherRanges.length;
236 
237  while (otherRangesCount--)
238  if (![self containsIndexesInRange:otherRanges[otherRangesCount]])
239  return NO;
240 
241  return YES;
242 }
243 
249 - (BOOL)intersectsIndexesInRange:(CPRange)aRange
250 {
251  if (_count <= 0)
252  return NO;
253 
254  var lhsRangeIndex = assumedPositionOfIndex(_ranges, aRange.location);
255 
256  if (FLOOR(lhsRangeIndex) === lhsRangeIndex)
257  return YES;
258 
259  var rhsRangeIndex = assumedPositionOfIndex(_ranges, CPMaxRange(aRange) - 1);
260 
261  if (FLOOR(rhsRangeIndex) === rhsRangeIndex)
262  return YES;
263 
264  return lhsRangeIndex !== rhsRangeIndex;
265 }
266 
270 - (int)count
271 {
272  return _count;
273 }
274 
275 // Accessing Indexes
279 - (CPInteger)firstIndex
280 {
281  if (_count > 0)
282  return _ranges[0].location;
283 
284  return CPNotFound;
285 }
286 
290 - (CPInteger)lastIndex
291 {
292  if (_count > 0)
293  return CPMaxRange(_ranges[_ranges.length - 1]) - 1;
294 
295  return CPNotFound;
296 }
297 
302 - (CPInteger)indexGreaterThanIndex:(CPInteger)anIndex
303 {
304  // The first possible index that would satisfy this requirement.
305  ++anIndex;
306 
307  // Attempt to find it or something bigger.
308  var rangeIndex = assumedPositionOfIndex(_ranges, anIndex);
309 
310  // Nothing at all found?
311  if (rangeIndex === CPNotFound)
312  return CPNotFound;
313 
314  rangeIndex = CEIL(rangeIndex);
315 
316  if (rangeIndex >= _ranges.length)
317  return CPNotFound;
318 
319  var range = _ranges[rangeIndex];
320 
321  // Check if it's actually in this range.
322  if (CPLocationInRange(anIndex, range))
323  return anIndex;
324 
325  // If not, it must be the first element of this range.
326  return range.location;
327 }
328 
333 - (CPInteger)indexLessThanIndex:(CPInteger)anIndex
334 {
335  // The first possible index that would satisfy this requirement.
336  --anIndex;
337 
338  // Attempt to find it or something smaller.
339  var rangeIndex = assumedPositionOfIndex(_ranges, anIndex);
340 
341  // Nothing at all found?
342  if (rangeIndex === CPNotFound)
343  return CPNotFound;
344 
345  rangeIndex = FLOOR(rangeIndex);
346 
347  if (rangeIndex < 0)
348  return CPNotFound;
349 
350  var range = _ranges[rangeIndex];
351 
352  // Check if it's actually in this range.
353  if (CPLocationInRange(anIndex, range))
354  return anIndex;
355 
356  // If not, it must be the first element of this range.
357  return CPMaxRange(range) - 1;
358 }
359 
364 - (CPInteger)indexGreaterThanOrEqualToIndex:(CPInteger)anIndex
365 {
366  return [self indexGreaterThanIndex:anIndex - 1];
367 }
368 
373 - (CPInteger)indexLessThanOrEqualToIndex:(CPInteger)anIndex
374 {
375  return [self indexLessThanIndex:anIndex + 1];
376 }
377 
387 - (CPInteger)getIndexes:(CPArray)anArray maxCount:(CPInteger)aMaxCount inIndexRange:(CPRange)aRange
388 {
389  if (!_count || aMaxCount === 0 || aRange && !aRange.length)
390  {
391  if (aRange)
392  aRange.length = 0;
393 
394  return 0;
395  }
396 
397  var total = 0;
398 
399  if (aRange)
400  {
401  var firstIndex = aRange.location,
402  lastIndex = CPMaxRange(aRange) - 1,
403  rangeIndex = CEIL(assumedPositionOfIndex(_ranges, firstIndex)),
404  lastRangeIndex = FLOOR(assumedPositionOfIndex(_ranges, lastIndex));
405  }
406  else
407  {
408  var firstIndex = [self firstIndex],
409  lastIndex = [self lastIndex],
410  rangeIndex = 0,
411  lastRangeIndex = _ranges.length - 1;
412  }
413 
414  while (rangeIndex <= lastRangeIndex)
415  {
416  var range = _ranges[rangeIndex],
417  index = MAX(firstIndex, range.location),
418  maxRange = MIN(lastIndex + 1, CPMaxRange(range));
419 
420  for (; index < maxRange; ++index)
421  {
422  anArray[total++] = index;
423 
424  if (total === aMaxCount)
425  {
426  // Update aRange if it exists...
427  if (aRange)
428  {
429  aRange.location = index + 1;
430  aRange.length = lastIndex + 1 - index - 1;
431  }
432 
433  return aMaxCount;
434  }
435  }
436 
437  ++rangeIndex;
438  }
439 
440  // Update aRange if it exists...
441  if (aRange)
442  {
443  aRange.location = CPNotFound;
444  aRange.length = 0;
445  }
446 
447  return total;
448 }
449 
450 - (CPString)description
451 {
452  var description = [super description];
453 
454  if (_count)
455  {
456  var index = 0,
457  count = _ranges.length;
458 
459  description += "[number of indexes: " + _count + " (in " + count;
460 
461  if (count === 1)
462  description += " range), indexes: (";
463  else
464  description += " ranges), indexes: (";
465 
466  for (; index < count; ++index)
467  {
468  var range = _ranges[index];
469 
470  description += range.location;
471 
472  if (range.length > 1)
473  description += "-" + (CPMaxRange(range) - 1);
474 
475  if (index + 1 < count)
476  description += " ";
477  }
478 
479  description += ")]";
480  }
481 
482  else
483  description += "(no indexes)";
484 
485  return description;
486 }
487 
488 - (void)enumerateIndexesUsingBlock:(Function /*(int idx, @ref BOOL stop) */)aFunction
489 {
490  [self enumerateIndexesWithOptions:CPEnumerationNormal usingBlock:aFunction];
491 }
492 
493 - (void)enumerateIndexesWithOptions:(CPEnumerationOptions)options usingBlock:(Function /*(int idx, @ref BOOL stop)*/)aFunction
494 {
495  if (!_count)
496  return;
497  [self enumerateIndexesInRange:CPMakeRange(0, CPMaxRange(_ranges[_ranges.length - 1])) options:options usingBlock:aFunction];
498 }
499 
500 - (void)enumerateIndexesInRange:(CPRange)enumerationRange options:(CPEnumerationOptions)options usingBlock:(Function /*(int idx, @ref BOOL stop)*/)aFunction
501 {
502  if (!_count || CPEmptyRange(enumerationRange))
503  return;
504 
505  var shouldStop = NO,
506  index,
507  stop,
508  increment;
509 
510  if (options & CPEnumerationReverse)
511  {
512  index = _ranges.length - 1,
513  stop = -1,
514  increment = -1;
515  }
516  else
517  {
518  index = 0;
519  stop = _ranges.length;
520  increment = 1;
521  }
522 
523  for (; index !== stop; index += increment)
524  {
525  var range = _ranges[index],
526  rangeIndex,
527  rangeStop,
528  rangeIncrement;
529 
530  if (options & CPEnumerationReverse)
531  {
532  rangeIndex = CPMaxRange(range) - 1;
533  rangeStop = range.location - 1;
534  rangeIncrement = -1;
535  }
536  else
537  {
538  rangeIndex = range.location;
539  rangeStop = CPMaxRange(range);
540  rangeIncrement = 1;
541  }
542 
543  for (; rangeIndex !== rangeStop; rangeIndex += rangeIncrement)
544  {
545  if (CPLocationInRange(rangeIndex, enumerationRange))
546  {
547  aFunction(rangeIndex, @ref(shouldStop));
548  if (shouldStop)
549  return;
550  }
551  }
552  }
553 }
554 
555 - (unsigned)indexPassingTest:(Function /*(int anIndex)*/)aPredicate
556 {
557  return [self indexWithOptions:CPEnumerationNormal passingTest:aPredicate];
558 }
559 
560 - (CPIndexSet)indexesPassingTest:(Function /*(int anIndex)*/)aPredicate
561 {
562  return [self indexesWithOptions:CPEnumerationNormal passingTest:aPredicate];
563 }
564 
565 - (unsigned)indexWithOptions:(CPEnumerationOptions)anOptions passingTest:(Function /*(int anIndex)*/)aPredicate
566 {
567  if (!_count)
568  return CPNotFound;
569 
570  return [self indexInRange:CPMakeRange(0, CPMaxRange(_ranges[_ranges.length - 1])) options:anOptions passingTest:aPredicate];
571 }
572 
573 - (CPIndexSet)indexesWithOptions:(CPEnumerationOptions)anOptions passingTest:(Function /*(int anIndex)*/)aPredicate
574 {
575  if (!_count)
576  return [CPIndexSet indexSet];
577 
578  return [self indexesInRange:CPMakeRange(0, CPMaxRange(_ranges[_ranges.length - 1])) options:anOptions passingTest:aPredicate];
579 }
580 
581 - (unsigned)indexInRange:(CPRange)aRange options:(CPEnumerationOptions)anOptions passingTest:(Function /*(int anIndex)*/)aPredicate
582 {
583  if (!_count || CPEmptyRange(aRange))
584  return CPNotFound;
585 
586  var shouldStop = NO,
587  index,
588  stop,
589  increment;
590 
591  if (anOptions & CPEnumerationReverse)
592  {
593  index = _ranges.length - 1,
594  stop = -1,
595  increment = -1;
596  }
597  else
598  {
599  index = 0;
600  stop = _ranges.length;
601  increment = 1;
602  }
603 
604  for (; index !== stop; index += increment)
605  {
606  var range = _ranges[index],
607  rangeIndex,
608  rangeStop,
609  rangeIncrement;
610 
611  if (anOptions & CPEnumerationReverse)
612  {
613  rangeIndex = CPMaxRange(range) - 1;
614  rangeStop = range.location - 1;
615  rangeIncrement = -1;
616  }
617  else
618  {
619  rangeIndex = range.location;
620  rangeStop = CPMaxRange(range);
621  rangeIncrement = 1;
622  }
623 
624  for (; rangeIndex !== rangeStop; rangeIndex += rangeIncrement)
625  {
626  if (CPLocationInRange(rangeIndex, aRange))
627  {
628  if (aPredicate(rangeIndex, @ref(shouldStop)))
629  return rangeIndex;
630 
631  if (shouldStop)
632  return CPNotFound;
633  }
634  }
635  }
636 
637  return CPNotFound;
638 }
639 
640 - (CPIndexSet)indexesInRange:(CPRange)aRange options:(CPEnumerationOptions)anOptions passingTest:(Function /*(int anIndex)*/)aPredicate
641 {
642  if (!_count || CPEmptyRange(aRange))
643  return [CPIndexSet indexSet];
644 
645  var shouldStop = NO,
646  index,
647  stop,
648  increment;
649 
650  if (anOptions & CPEnumerationReverse)
651  {
652  index = _ranges.length - 1,
653  stop = -1,
654  increment = -1;
655  }
656  else
657  {
658  index = 0;
659  stop = _ranges.length;
660  increment = 1;
661  }
662 
663  var indexesPassingTest = [CPMutableIndexSet indexSet];
664 
665  for (; index !== stop; index += increment)
666  {
667  var range = _ranges[index],
668  rangeIndex,
669  rangeStop,
670  rangeIncrement;
671 
672  if (anOptions & CPEnumerationReverse)
673  {
674  rangeIndex = CPMaxRange(range) - 1;
675  rangeStop = range.location - 1;
676  rangeIncrement = -1;
677  }
678  else
679  {
680  rangeIndex = range.location;
681  rangeStop = CPMaxRange(range);
682  rangeIncrement = 1;
683  }
684 
685  for (; rangeIndex !== rangeStop; rangeIndex += rangeIncrement)
686  {
687  if (CPLocationInRange(rangeIndex, aRange))
688  {
689  if (aPredicate(rangeIndex, @ref(shouldStop)))
690  [indexesPassingTest addIndex:rangeIndex];
691 
692  if (shouldStop)
693  return indexesPassingTest;
694  }
695  }
696  }
697 
698  return indexesPassingTest;
699 }
700 
701 @end
702 
704 
705 // Adding indexes.
710 - (void)addIndex:(CPInteger)anIndex
711 {
712  [self addIndexesInRange:CPMakeRange(anIndex, 1)];
713 }
714 
719 - (void)addIndexes:(CPIndexSet)anIndexSet
720 {
721  var otherRanges = anIndexSet._ranges,
722  otherRangesCount = otherRanges.length;
723 
724  // Simply add each range within anIndexSet.
725  while (otherRangesCount--)
726  [self addIndexesInRange:otherRanges[otherRangesCount]];
727 }
728 
733 - (void)addIndexesInRange:(CPRange)aRange
734 {
735  if (aRange.location < 0)
736  [CPException raise:CPInvalidArgumentException reason:"Range " + CPStringFromRange(aRange) + " is out of bounds."];
737 
738  // If empty range, bail.
739  if (aRange.length <= 0)
740  return;
741 
742  // If we currently don't have any indexes, this represents our entire set.
743  if (_count <= 0)
744  {
745  _count = aRange.length;
746  _ranges = [aRange];
747 
748  return;
749  }
750 
751  var rangeCount = _ranges.length,
752  lhsRangeIndex = assumedPositionOfIndex(_ranges, aRange.location - 1),
753  lhsRangeIndexCEIL = CEIL(lhsRangeIndex);
754 
755  if (lhsRangeIndexCEIL === lhsRangeIndex && lhsRangeIndexCEIL < rangeCount)
756  aRange = CPUnionRange(aRange, _ranges[lhsRangeIndexCEIL]);
757 
758  var rhsRangeIndex = assumedPositionOfIndex(_ranges, CPMaxRange(aRange)),
759  rhsRangeIndexFLOOR = FLOOR(rhsRangeIndex);
760 
761  if (rhsRangeIndexFLOOR === rhsRangeIndex && rhsRangeIndexFLOOR >= 0)
762  aRange = CPUnionRange(aRange, _ranges[rhsRangeIndexFLOOR]);
763 
764  var removalCount = rhsRangeIndexFLOOR - lhsRangeIndexCEIL + 1;
765 
766  if (removalCount === _ranges.length)
767  {
768  _ranges = [aRange];
769  _count = aRange.length;
770  }
771 
772  else if (removalCount === 1)
773  {
774  if (lhsRangeIndexCEIL < _ranges.length)
775  _count -= _ranges[lhsRangeIndexCEIL].length;
776 
777  _count += aRange.length;
778  _ranges[lhsRangeIndexCEIL] = aRange;
779  }
780 
781  else
782  {
783  if (removalCount > 0)
784  {
785  var removal = lhsRangeIndexCEIL,
786  lastRemoval = lhsRangeIndexCEIL + removalCount - 1;
787 
788  for (; removal <= lastRemoval; ++removal)
789  _count -= _ranges[removal].length;
790 
791  [_ranges removeObjectsInRange:CPMakeRange(lhsRangeIndexCEIL, removalCount)];
792  }
793 
794  [_ranges insertObject:aRange atIndex:lhsRangeIndexCEIL];
795 
796  _count += aRange.length;
797  }
798 }
799 
800 // Removing Indexes
805 - (void)removeIndex:(CPInteger)anIndex
806 {
807  [self removeIndexesInRange:CPMakeRange(anIndex, 1)];
808 }
809 
815 - (void)removeIndexes:(CPIndexSet)anIndexSet
816 {
817  var otherRanges = anIndexSet._ranges,
818  otherRangesCount = otherRanges.length;
819 
820  // Simply remove each index from anIndexSet
821  while (otherRangesCount--)
822  [self removeIndexesInRange:otherRanges[otherRangesCount]];
823 }
824 
828 - (void)removeAllIndexes
829 {
830  _ranges = [];
831  _count = 0;
832 }
833 
839 - (void)removeIndexesInRange:(CPRange)aRange
840 {
841  // If empty range, bail.
842  if (aRange.length <= 0)
843  return;
844 
845  // If we currently don't have any indexes, there's nothing to remove.
846  if (_count <= 0)
847  return;
848 
849  var rangeCount = _ranges.length,
850  lhsRangeIndex = assumedPositionOfIndex(_ranges, aRange.location),
851  lhsRangeIndexCEIL = CEIL(lhsRangeIndex);
852 
853  // Do we fall on an actual existing range?
854  if (lhsRangeIndex === lhsRangeIndexCEIL && lhsRangeIndexCEIL < rangeCount)
855  {
856  var existingRange = _ranges[lhsRangeIndexCEIL];
857 
858  // If these ranges don't start in the same place, we have to cull it.
859  if (aRange.location !== existingRange.location)
860  {
861  var maxRange = CPMaxRange(aRange),
862  existingMaxRange = CPMaxRange(existingRange);
863 
864  existingRange.length = aRange.location - existingRange.location;
865 
866  // If this range is internal to the existing range, we have a unique splitting case.
867  if (maxRange < existingMaxRange)
868  {
869  _count -= aRange.length;
870  [_ranges insertObject:CPMakeRange(maxRange, existingMaxRange - maxRange) atIndex:lhsRangeIndexCEIL + 1];
871 
872  return;
873  }
874  else
875  {
876  _count -= existingMaxRange - aRange.location;
877  lhsRangeIndexCEIL += 1;
878  }
879  }
880  }
881 
882  var rhsRangeIndex = assumedPositionOfIndex(_ranges, CPMaxRange(aRange) - 1),
883  rhsRangeIndexFLOOR = FLOOR(rhsRangeIndex);
884 
885  if (rhsRangeIndex === rhsRangeIndexFLOOR && rhsRangeIndexFLOOR >= 0)
886  {
887  var maxRange = CPMaxRange(aRange),
888  existingRange = _ranges[rhsRangeIndexFLOOR],
889  existingMaxRange = CPMaxRange(existingRange);
890 
891  if (maxRange !== existingMaxRange)
892  {
893  _count -= maxRange - existingRange.location;
894  rhsRangeIndexFLOOR -= 1; // This is accounted for, and thus as if we got the previous spot.
895 
896  existingRange.location = maxRange;
897  existingRange.length = existingMaxRange - maxRange;
898  }
899  }
900 
901  var removalCount = rhsRangeIndexFLOOR - lhsRangeIndexCEIL + 1;
902 
903  if (removalCount > 0)
904  {
905  var removal = lhsRangeIndexCEIL,
906  lastRemoval = lhsRangeIndexCEIL + removalCount - 1;
907 
908  for (; removal <= lastRemoval; ++removal)
909  _count -= _ranges[removal].length;
910 
911  [_ranges removeObjectsInRange:CPMakeRange(lhsRangeIndexCEIL, removalCount)];
912  }
913 }
914 
915 // Shifting Index Groups
922 - (void)shiftIndexesStartingAtIndex:(CPInteger)anIndex by:(int)aDelta
923 {
924  if (!_count || aDelta == 0)
925  return;
926 
927  // Later indexes have a higher probability of being shifted
928  // than lower ones, so start at the end and work backwards.
929  var i = _ranges.length - 1,
930  shifted = CPMakeRange(CPNotFound, 0);
931 
932  for (; i >= 0; --i)
933  {
934  var range = _ranges[i],
935  maximum = CPMaxRange(range);
936 
937  if (anIndex >= maximum)
938  break;
939 
940  // If our index is within our range, but not the first index,
941  // then this range will be split.
942  if (anIndex > range.location)
943  {
944  // Split the range into shift and unshifted.
945  shifted = CPMakeRange(anIndex + aDelta, maximum - anIndex);
946  range.length = anIndex - range.location;
947 
948  // If our delta is positive, then we can simply add the range
949  // to the array.
950  if (aDelta > 0)
951  [_ranges insertObject:shifted atIndex:i + 1];
952  // If it's negative, it needs to be added properly later.
953  else if (shifted.location < 0)
954  {
955  shifted.length = CPMaxRange(shifted);
956  shifted.location = 0;
957  }
958 
959  // We don't need to continue.
960  break;
961  }
962 
963  // Shift the range, and normalize it if the result is negative.
964  if ((range.location += aDelta) < 0)
965  {
966  _count -= range.length - CPMaxRange(range);
967  range.length = CPMaxRange(range);
968  range.location = 0;
969  }
970  }
971 
972  // We need to add the shifted ranges if the delta is negative.
973  if (aDelta < 0)
974  {
975  var j = i + 1,
976  count = _ranges.length,
977  shifts = [];
978 
979  for (; j < count; ++j)
980  {
981  [shifts addObject:_ranges[j]];
982  _count -= _ranges[j].length;
983  }
984 
985  if ((j = i + 1) < count)
986  {
987  [_ranges removeObjectsInRange:CPMakeRange(j, count - j)];
988 
989  for (j = 0, count = shifts.length; j < count; ++j)
990  [self addIndexesInRange:shifts[j]];
991  }
992 
993  if (shifted.location != CPNotFound)
994  [self addIndexesInRange:shifted];
995  }
996 }
997 
998 @end
999 
1000 var CPIndexSetCountKey = @"CPIndexSetCountKey",
1001  CPIndexSetRangeStringsKey = @"CPIndexSetRangeStringsKey";
1002 
1003 @implementation CPIndexSet (CPCoding)
1004 
1011 - (id)initWithCoder:(CPCoder)aCoder
1012 {
1013  self = [super init];
1014 
1015  if (self)
1016  {
1017  _count = [aCoder decodeIntForKey:CPIndexSetCountKey];
1018  _ranges = [];
1019 
1020  var rangeStrings = [aCoder decodeObjectForKey:CPIndexSetRangeStringsKey],
1021  index = 0,
1022  count = rangeStrings.length;
1023 
1024  for (; index < count; ++index)
1025  _ranges.push(CPRangeFromString(rangeStrings[index]));
1026  }
1027 
1028  return self;
1029 }
1030 
1036 - (void)encodeWithCoder:(CPCoder)aCoder
1037 {
1038  [aCoder encodeInt:_count forKey:CPIndexSetCountKey];
1039 
1040  var index = 0,
1041  count = _ranges.length,
1042  rangeStrings = [];
1043 
1044  for (; index < count; ++index)
1045  rangeStrings[index] = CPStringFromRange(_ranges[index]);
1046 
1047  [aCoder encodeObject:rangeStrings forKey:CPIndexSetRangeStringsKey];
1048 }
1049 
1050 @end
1051 
1052 @implementation CPIndexSet (CPCopying)
1053 
1060 - (id)copy
1061 {
1062  return [[[self class] alloc] initWithIndexSet:self];
1063 }
1064 
1071 - (id)mutableCopy
1072 {
1073  return [[[self class] alloc] initWithIndexSet:self];
1074 }
1075 
1076 @end
1077 
1087 {
1088  id __doxygen__;
1089 }
1090 
1091 @end
1092 
1093 var positionOfIndex = function(ranges, anIndex)
1094 {
1095  var low = 0,
1096  high = ranges.length - 1;
1097 
1098  while (low <= high)
1099  {
1100  var middle = FLOOR(low + (high - low) / 2),
1101  range = ranges[middle];
1102 
1103  if (anIndex < range.location)
1104  high = middle - 1;
1105 
1106  else if (anIndex >= CPMaxRange(range))
1107  low = middle + 1;
1108 
1109  else
1110  return middle;
1111  }
1112 
1113  return CPNotFound;
1114 };
1115 
1116 var assumedPositionOfIndex = function(ranges, anIndex)
1117 {
1118  var count = ranges.length;
1119 
1120  if (count <= 0)
1121  return CPNotFound;
1122 
1123  var low = 0,
1124  high = count * 2;
1125 
1126  while (low <= high)
1127  {
1128  var middle = FLOOR(low + (high - low) / 2),
1129  position = middle / 2,
1130  positionFLOOR = FLOOR(position);
1131 
1132  if (position === positionFLOOR)
1133  {
1134  if (positionFLOOR - 1 >= 0 && anIndex < CPMaxRange(ranges[positionFLOOR - 1]))
1135  high = middle - 1;
1136 
1137  else if (positionFLOOR < count && anIndex >= ranges[positionFLOOR].location)
1138  low = middle + 1;
1139 
1140  else
1141  return positionFLOOR - 0.5;
1142  }
1143  else
1144  {
1145  var range = ranges[positionFLOOR];
1146 
1147  if (anIndex < range.location)
1148  high = middle - 1;
1149 
1150  else if (anIndex >= CPMaxRange(range))
1151  low = middle + 1;
1152 
1153  else
1154  return positionFLOOR;
1155  }
1156  }
1157 
1158  return CPNotFound;
1159 };
1160 
1161 /*
1162 new old method
1163 X + (id)indexSet;
1164 X + (id)indexSetWithIndex:(unsigned int)value;
1165 X + (id)indexSetWithIndexesInRange:(NSRange)range;
1166 X X - (id)init;
1167 X X - (id)initWithIndex:(unsigned int)value;
1168 X X - (id)initWithIndexesInRange:(NSRange)range; // designated initializer
1169 X X - (id)initWithIndexSet:(NSIndexSet *)indexSet; // designated initializer
1170 X - (BOOL)isEqualToIndexSet:(NSIndexSet *)indexSet;
1171 X X - (unsigned int)count;
1172 X X - (unsigned int)firstIndex;
1173 X X - (unsigned int)lastIndex;
1174 X X - (unsigned int)indexGreaterThanIndex:(unsigned int)value;
1175 X X - (unsigned int)indexLessThanIndex:(unsigned int)value;
1176 X X - (unsigned int)indexGreaterThanOrEqualToIndex:(unsigned int)value;
1177 X X - (unsigned int)indexLessThanOrEqualToIndex:(unsigned int)value;
1178 X - (unsigned int)getIndexes:(unsigned int *)indexBuffer maxCount:(unsigned int)bufferSize inIndexRange:(NSRangePointer)range;
1179 X X - (BOOL)containsIndex:(unsigned int)value;
1180 X X - (BOOL)containsIndexesInRange:(NSRange)range;
1181 X X - (BOOL)containsIndexes:(NSIndexSet *)indexSet;
1182 X X - (BOOL)intersectsIndexesInRange:(NSRange)range;
1183 X X - (void)addIndexes:(NSIndexSet *)indexSet;
1184 X - (void)removeIndexes:(NSIndexSet *)indexSet;
1185 X X - (void)removeAllIndexes;
1186 X - (void)addIndex:(unsigned int)value;
1187 X - (void)removeIndex:(unsigned int)value;
1188 X - (void)addIndexesInRange:(NSRange)range;
1189 X - (void)removeIndexesInRange:(NSRange)range;
1190  - (void)shiftIndexesStartingAtIndex:(CPUInteger)index by:(int)delta;
1191 */