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