24 #include "Foundation.h"
47 return [[
self alloc] init];
53 + (id)indexSetWithIndex:(
int)anIndex
62 + (id)indexSetWithIndexesInRange:(CPRange)aRange
78 - (id)initWithIndex:(CPInteger)anIndex
80 if (!_IS_NUMERIC(anIndex))
92 - (id)initWithIndexesInRange:(CPRange)aRange
98 _count = MAX(0, aRange.length);
120 _count = [anIndexSet
count];
123 var otherRanges = anIndexSet._ranges,
124 otherRangesCount = otherRanges.length;
126 while (otherRangesCount--)
127 _ranges[otherRangesCount] = _CPMakeRangeCopy(otherRanges[otherRangesCount]);
135 if (
self === anObject)
138 if (!anObject || ![anObject isKindOfClass:[
CPIndexSet class]])
156 if (
self === anIndexSet)
159 var rangesCount = _ranges.length,
160 otherRanges = anIndexSet._ranges;
164 if (rangesCount !== otherRanges.length || _count !== anIndexSet._count)
167 while (rangesCount--)
168 if (!CPEqualRanges(_ranges[rangesCount], otherRanges[rangesCount]))
176 return self === anObject ||
177 [anObject isKindOfClass:[
self class]] &&
178 [
self isEqualToIndexSet:anObject];
186 - (BOOL)containsIndex:(CPInteger)anIndex
195 - (BOOL)containsIndexesInRange:(CPRange)aRange
197 if (aRange.length <= 0)
201 if (_count < aRange.length)
211 var range = _ranges[rangeIndex];
223 var otherCount = anIndexSet._count;
229 if (_count < otherCount)
232 var otherRanges = anIndexSet._ranges,
233 otherRangesCount = otherRanges.length;
235 while (otherRangesCount--)
236 if (![
self containsIndexesInRange:otherRanges[otherRangesCount]])
247 - (BOOL)intersectsIndexesInRange:(CPRange)aRange
254 if (FLOOR(lhsRangeIndex) === lhsRangeIndex)
259 if (FLOOR(rhsRangeIndex) === rhsRangeIndex)
262 return lhsRangeIndex !== rhsRangeIndex;
277 - (CPInteger)firstIndex
280 return _ranges[0].location;
288 - (CPInteger)lastIndex
291 return _CPMaxRange(_ranges[_ranges.length - 1]) - 1;
300 - (CPInteger)indexGreaterThanIndex:(CPInteger)anIndex
312 rangeIndex = CEIL(rangeIndex);
314 if (rangeIndex >= _ranges.length)
317 var range = _ranges[rangeIndex];
320 if (_CPLocationInRange(anIndex, range))
324 return range.location;
331 - (CPInteger)indexLessThanIndex:(CPInteger)anIndex
343 rangeIndex = FLOOR(rangeIndex);
348 var range = _ranges[rangeIndex];
351 if (_CPLocationInRange(anIndex, range))
355 return _CPMaxRange(range) - 1;
362 - (CPInteger)indexGreaterThanOrEqualToIndex:(CPInteger)anIndex
371 - (CPInteger)indexLessThanOrEqualToIndex:(CPInteger)anIndex
385 - (CPInteger)getIndexes:(
CPArray)anArray maxCount:(CPInteger)aMaxCount inIndexRange:(CPRange)aRange
387 if (!_count || aMaxCount === 0 || aRange && !aRange.length)
399 var firstIndex = aRange.location,
400 lastIndex = _CPMaxRange(aRange) - 1,
409 lastRangeIndex = _ranges.length - 1;
412 while (rangeIndex <= lastRangeIndex)
414 var range = _ranges[rangeIndex],
415 index = MAX(firstIndex, range.location),
416 maxRange = MIN(lastIndex + 1, _CPMaxRange(range));
418 for (; index < maxRange; ++index)
420 anArray[total++] = index;
422 if (total === aMaxCount)
427 aRange.location = index + 1;
428 aRange.length = lastIndex + 1 - index - 1;
455 count = _ranges.length;
457 description +=
"[number of indexes: " + _count +
" (in " + count;
460 description +=
" range), indexes: (";
462 description +=
" ranges), indexes: (";
464 for (; index < count; ++index)
466 var range = _ranges[index];
468 description += range.location;
470 if (range.length > 1)
471 description +=
"-" + (CPMaxRange(range) - 1);
473 if (index + 1 < count)
481 description +=
"(no indexes)";
486 - (void)enumerateIndexesUsingBlock:(Function )aFunction
491 - (void)enumerateIndexesWithOptions:(CPEnumerationOptions)options usingBlock:(Function )aFunction
498 - (void)enumerateIndexesInRange:(CPRange)enumerationRange options:(CPEnumerationOptions)options usingBlock:(Function )aFunction
500 if (!_count || _CPEmptyRange(enumerationRange))
510 index = _ranges.length - 1,
517 stop = _ranges.length;
521 for (; index !== stop; index += increment)
523 var range = _ranges[index],
530 rangeIndex = _CPMaxRange(range) - 1;
531 rangeStop = range.location - 1;
536 rangeIndex = range.location;
537 rangeStop = _CPMaxRange(range);
541 for (; rangeIndex !== rangeStop; rangeIndex += rangeIncrement)
543 if (_CPLocationInRange(rangeIndex, enumerationRange))
545 aFunction(rangeIndex, AT_REF(shouldStop));
553 - (unsigned)indexPassingTest:(Function )aPredicate
563 - (unsigned)indexWithOptions:(CPEnumerationOptions)anOptions passingTest:(Function )aPredicate
571 - (
CPIndexSet)indexesWithOptions:(CPEnumerationOptions)anOptions passingTest:(Function )aPredicate
579 - (unsigned)indexInRange:(CPRange)aRange options:(CPEnumerationOptions)anOptions passingTest:(Function )aPredicate
581 if (!_count || _CPEmptyRange(aRange))
591 index = _ranges.length - 1,
598 stop = _ranges.length;
602 for (; index !== stop; index += increment)
604 var range = _ranges[index],
611 rangeIndex = _CPMaxRange(range) - 1;
612 rangeStop = range.location - 1;
617 rangeIndex = range.location;
618 rangeStop = _CPMaxRange(range);
622 for (; rangeIndex !== rangeStop; rangeIndex += rangeIncrement)
624 if (_CPLocationInRange(rangeIndex, aRange))
626 if (aPredicate(rangeIndex, AT_REF(shouldStop)))
638 - (
CPIndexSet)indexesInRange:(CPRange)aRange options:(CPEnumerationOptions)anOptions passingTest:(Function )aPredicate
640 if (!_count || _CPEmptyRange(aRange))
650 index = _ranges.length - 1,
657 stop = _ranges.length;
663 for (; index !== stop; index += increment)
665 var range = _ranges[index],
672 rangeIndex = _CPMaxRange(range) - 1;
673 rangeStop = range.location - 1;
678 rangeIndex = range.location;
679 rangeStop = _CPMaxRange(range);
683 for (; rangeIndex !== rangeStop; rangeIndex += rangeIncrement)
685 if (_CPLocationInRange(rangeIndex, aRange))
687 if (aPredicate(rangeIndex, AT_REF(shouldStop)))
688 [indexesPassingTest addIndex:rangeIndex];
691 return indexesPassingTest;
696 return indexesPassingTest;
708 - (void)addIndex:(CPInteger)anIndex
719 var otherRanges = anIndexSet._ranges,
720 otherRangesCount = otherRanges.length;
723 while (otherRangesCount--)
731 - (void)addIndexesInRange:(CPRange)aRange
734 if (aRange.length <= 0)
740 _count = aRange.length;
746 var rangeCount = _ranges.length,
748 lhsRangeIndexCEIL = CEIL(lhsRangeIndex);
750 if (lhsRangeIndexCEIL === lhsRangeIndex && lhsRangeIndexCEIL < rangeCount)
751 aRange = CPUnionRange(aRange, _ranges[lhsRangeIndexCEIL]);
754 rhsRangeIndexFLOOR = FLOOR(rhsRangeIndex);
756 if (rhsRangeIndexFLOOR === rhsRangeIndex && rhsRangeIndexFLOOR >= 0)
757 aRange = CPUnionRange(aRange, _ranges[rhsRangeIndexFLOOR]);
759 var removalCount = rhsRangeIndexFLOOR - lhsRangeIndexCEIL + 1;
761 if (removalCount === _ranges.length)
764 _count = aRange.length;
767 else if (removalCount === 1)
769 if (lhsRangeIndexCEIL < _ranges.length)
770 _count -= _ranges[lhsRangeIndexCEIL].length;
772 _count += aRange.length;
773 _ranges[lhsRangeIndexCEIL] = aRange;
778 if (removalCount > 0)
780 var removal = lhsRangeIndexCEIL,
781 lastRemoval = lhsRangeIndexCEIL + removalCount - 1;
783 for (; removal <= lastRemoval; ++removal)
784 _count -= _ranges[removal].length;
786 [_ranges removeObjectsInRange:_CPMakeRange(lhsRangeIndexCEIL, removalCount)];
789 [_ranges insertObject:aRange atIndex:lhsRangeIndexCEIL];
791 _count += aRange.length;
800 - (void)removeIndex:(CPInteger)anIndex
812 var otherRanges = anIndexSet._ranges,
813 otherRangesCount = otherRanges.length;
816 while (otherRangesCount--)
823 - (void)removeAllIndexes
834 - (void)removeIndexesInRange:(CPRange)aRange
837 if (aRange.length <= 0)
844 var rangeCount = _ranges.length,
846 lhsRangeIndexCEIL = CEIL(lhsRangeIndex);
849 if (lhsRangeIndex === lhsRangeIndexCEIL && lhsRangeIndexCEIL < rangeCount)
851 var existingRange = _ranges[lhsRangeIndexCEIL];
854 if (aRange.location !== existingRange.location)
856 var maxRange = _CPMaxRange(aRange),
857 existingMaxRange = _CPMaxRange(existingRange);
859 existingRange.length = aRange.location - existingRange.location;
862 if (maxRange < existingMaxRange)
864 _count -= aRange.length;
865 [_ranges insertObject:_CPMakeRange(maxRange, existingMaxRange - maxRange) atIndex:lhsRangeIndexCEIL + 1];
871 _count -= existingMaxRange - aRange.location;
872 lhsRangeIndexCEIL += 1;
878 rhsRangeIndexFLOOR = FLOOR(rhsRangeIndex);
880 if (rhsRangeIndex === rhsRangeIndexFLOOR && rhsRangeIndexFLOOR >= 0)
882 var maxRange = _CPMaxRange(aRange),
883 existingRange = _ranges[rhsRangeIndexFLOOR],
884 existingMaxRange = _CPMaxRange(existingRange);
886 if (maxRange !== existingMaxRange)
888 _count -= maxRange - existingRange.location;
889 rhsRangeIndexFLOOR -= 1;
891 existingRange.location = maxRange;
892 existingRange.length = existingMaxRange - maxRange;
896 var removalCount = rhsRangeIndexFLOOR - lhsRangeIndexCEIL + 1;
898 if (removalCount > 0)
900 var removal = lhsRangeIndexCEIL,
901 lastRemoval = lhsRangeIndexCEIL + removalCount - 1;
903 for (; removal <= lastRemoval; ++removal)
904 _count -= _ranges[removal].length;
906 [_ranges removeObjectsInRange:_CPMakeRange(lhsRangeIndexCEIL, removalCount)];
917 - (void)shiftIndexesStartingAtIndex:(CPInteger)anIndex by:(
int)aDelta
919 if (!_count || aDelta == 0)
924 var i = _ranges.length - 1,
929 var range = _ranges[i],
930 maximum = _CPMaxRange(range);
932 if (anIndex >= maximum)
937 if (anIndex > range.location)
940 shifted =
CPMakeRange(anIndex + aDelta, maximum - anIndex);
941 range.length = anIndex - range.location;
946 [_ranges insertObject:shifted atIndex:i + 1];
948 else if (shifted.location < 0)
950 shifted.length = _CPMaxRange(shifted);
951 shifted.location = 0;
959 if ((range.location += aDelta) < 0)
961 _count -= range.length - _CPMaxRange(range);
962 range.length = _CPMaxRange(range);
971 count = _ranges.length,
974 for (; j < count; ++j)
976 [shifts addObject:_ranges[j]];
977 _count -= _ranges[j].length;
980 if ((j = i + 1) < count)
982 [_ranges removeObjectsInRange:_CPMakeRange(j, count - j)];
984 for (j = 0, count = shifts.length; j < count; ++j)
1008 self = [
super init];
1012 _count = [aCoder decodeIntForKey:CPIndexSetCountKey];
1015 var rangeStrings = [aCoder decodeObjectForKey:CPIndexSetRangeStringsKey],
1017 count = rangeStrings.length;
1019 for (; index < count; ++index)
1033 [aCoder encodeInt:_count forKey:CPIndexSetCountKey];
1036 count = _ranges.length,
1039 for (; index < count; ++index)
1042 [aCoder encodeObject:rangeStrings forKey:CPIndexSetRangeStringsKey];
1057 return [[[
self class] alloc] initWithIndexSet:self];
1068 return [[[
self class] alloc] initWithIndexSet:self];
1091 high = ranges.length - 1;
1095 var middle = FLOOR(low + (high - low) / 2),
1096 range = ranges[middle];
1098 if (anIndex < range.location)
1101 else if (anIndex >= _CPMaxRange(range))
1113 var count = ranges.length;
1123 var middle = FLOOR(low + (high - low) / 2),
1124 position = middle / 2,
1125 positionFLOOR = FLOOR(position);
1127 if (position === positionFLOOR)
1129 if (positionFLOOR - 1 >= 0 && anIndex < _CPMaxRange(ranges[positionFLOOR - 1]))
1132 else if (positionFLOOR < count && anIndex >= ranges[positionFLOOR].location)
1136 return positionFLOOR - 0.5;
1140 var range = ranges[positionFLOOR];
1142 if (anIndex < range.location)
1145 else if (anIndex >= _CPMaxRange(range))
1149 return positionFLOOR;