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