23 #include "Foundation.h"
46 return [[
self alloc] init];
52 + (id)indexSetWithIndex:(
int)anIndex
54 return [[
self alloc] initWithIndex:anIndex];
61 + (id)indexSetWithIndexesInRange:(CPRange)aRange
63 return [[
self alloc] initWithIndexesInRange:aRange];
77 - (id)initWithIndex:(CPInteger)anIndex
79 if (!_IS_NUMERIC(anIndex))
91 - (id)initWithIndexesInRange:(CPRange)aRange
93 if (aRange.location < 0)
94 [
CPException raise:CPInvalidArgumentException
reason:"Range " + CPStringFromRange(aRange) + " is out of bounds."];
100 _count = MAX(0, aRange.length);
122 _count = [anIndexSet
count];
125 var otherRanges = anIndexSet._ranges,
126 otherRangesCount = otherRanges.length;
128 while (otherRangesCount--)
129 _ranges[otherRangesCount] =
CPMakeRangeCopy(otherRanges[otherRangesCount]);
137 if (
self === anObject)
140 if (!anObject || ![anObject isKindOfClass:[
CPIndexSet class]])
158 if (
self === anIndexSet)
161 var rangesCount = _ranges.length,
162 otherRanges = anIndexSet._ranges;
166 if (rangesCount !== otherRanges.length || _count !== anIndexSet._count)
169 while (rangesCount--)
170 if (!
CPEqualRanges(_ranges[rangesCount], otherRanges[rangesCount]))
178 return self === anObject ||
179 [anObject isKindOfClass:[
self class]] &&
180 [
self isEqualToIndexSet:anObject];
188 - (BOOL)containsIndex:(CPInteger)anIndex
197 - (BOOL)containsIndexesInRange:(CPRange)aRange
199 if (aRange.length <= 0)
203 if (_count < aRange.length)
213 var range = _ranges[rangeIndex];
225 var otherCount = anIndexSet._count;
231 if (_count < otherCount)
234 var otherRanges = anIndexSet._ranges,
235 otherRangesCount = otherRanges.length;
237 while (otherRangesCount--)
238 if (![
self containsIndexesInRange:otherRanges[otherRangesCount]])
249 - (BOOL)intersectsIndexesInRange:(CPRange)aRange
256 if (FLOOR(lhsRangeIndex) === lhsRangeIndex)
261 if (FLOOR(rhsRangeIndex) === rhsRangeIndex)
264 return lhsRangeIndex !== rhsRangeIndex;
279 - (CPInteger)firstIndex
282 return _ranges[0].location;
290 - (CPInteger)lastIndex
293 return CPMaxRange(_ranges[_ranges.length - 1]) - 1;
302 - (CPInteger)indexGreaterThanIndex:(CPInteger)anIndex
314 rangeIndex = CEIL(rangeIndex);
316 if (rangeIndex >= _ranges.length)
319 var range = _ranges[rangeIndex];
326 return range.location;
333 - (CPInteger)indexLessThanIndex:(CPInteger)anIndex
345 rangeIndex = FLOOR(rangeIndex);
350 var range = _ranges[rangeIndex];
364 - (CPInteger)indexGreaterThanOrEqualToIndex:(CPInteger)anIndex
373 - (CPInteger)indexLessThanOrEqualToIndex:(CPInteger)anIndex
387 - (CPInteger)getIndexes:(CPArray)anArray maxCount:(CPInteger)aMaxCount inIndexRange:(CPRange)aRange
389 if (!_count || aMaxCount === 0 || aRange && !aRange.length)
401 var firstIndex = aRange.location,
411 lastRangeIndex = _ranges.length - 1;
414 while (rangeIndex <= lastRangeIndex)
416 var range = _ranges[rangeIndex],
417 index = MAX(firstIndex, range.location),
418 maxRange = MIN(lastIndex + 1,
CPMaxRange(range));
420 for (; index < maxRange; ++index)
422 anArray[total++] = index;
424 if (total === aMaxCount)
429 aRange.location = index + 1;
430 aRange.length = lastIndex + 1 - index - 1;
452 var description = [
super description];
457 count = _ranges.length;
459 description +=
"[number of indexes: " + _count +
" (in " + count;
462 description +=
" range), indexes: (";
464 description +=
" ranges), indexes: (";
466 for (; index < count; ++index)
468 var range = _ranges[index];
470 description += range.location;
472 if (range.length > 1)
475 if (index + 1 < count)
483 description +=
"(no indexes)";
488 - (void)enumerateIndexesUsingBlock:(Function )aFunction
493 - (void)enumerateIndexesWithOptions:(CPEnumerationOptions)options usingBlock:(Function )aFunction
500 - (void)enumerateIndexesInRange:(CPRange)enumerationRange options:(CPEnumerationOptions)options usingBlock:(Function )aFunction
510 if (options & CPEnumerationReverse)
512 index = _ranges.length - 1,
519 stop = _ranges.length;
523 for (; index !== stop; index += increment)
525 var range = _ranges[index],
530 if (options & CPEnumerationReverse)
533 rangeStop = range.location - 1;
538 rangeIndex = range.location;
543 for (; rangeIndex !== rangeStop; rangeIndex += rangeIncrement)
547 aFunction(rangeIndex, @ref(shouldStop));
555 - (unsigned)indexPassingTest:(Function )aPredicate
565 - (unsigned)indexWithOptions:(CPEnumerationOptions)anOptions passingTest:(Function )aPredicate
573 - (
CPIndexSet)indexesWithOptions:(CPEnumerationOptions)anOptions passingTest:(Function )aPredicate
581 - (unsigned)indexInRange:(CPRange)aRange options:(CPEnumerationOptions)anOptions passingTest:(Function )aPredicate
591 if (anOptions & CPEnumerationReverse)
593 index = _ranges.length - 1,
600 stop = _ranges.length;
604 for (; index !== stop; index += increment)
606 var range = _ranges[index],
611 if (anOptions & CPEnumerationReverse)
614 rangeStop = range.location - 1;
619 rangeIndex = range.location;
624 for (; rangeIndex !== rangeStop; rangeIndex += rangeIncrement)
628 if (aPredicate(rangeIndex, @ref(shouldStop)))
640 - (
CPIndexSet)indexesInRange:(CPRange)aRange options:(CPEnumerationOptions)anOptions passingTest:(Function )aPredicate
650 if (anOptions & CPEnumerationReverse)
652 index = _ranges.length - 1,
659 stop = _ranges.length;
665 for (; index !== stop; index += increment)
667 var range = _ranges[index],
672 if (anOptions & CPEnumerationReverse)
675 rangeStop = range.location - 1;
680 rangeIndex = range.location;
685 for (; rangeIndex !== rangeStop; rangeIndex += rangeIncrement)
689 if (aPredicate(rangeIndex, @ref(shouldStop)))
690 [indexesPassingTest addIndex:rangeIndex];
693 return indexesPassingTest;
698 return indexesPassingTest;
710 - (void)addIndex:(CPInteger)anIndex
721 var otherRanges = anIndexSet._ranges,
722 otherRangesCount = otherRanges.length;
725 while (otherRangesCount--)
733 - (void)addIndexesInRange:(CPRange)aRange
735 if (aRange.location < 0)
736 [
CPException raise:CPInvalidArgumentException
reason:"Range " + CPStringFromRange(aRange) + " is out of bounds."];
739 if (aRange.length <= 0)
745 _count = aRange.length;
751 var rangeCount = _ranges.length,
753 lhsRangeIndexCEIL = CEIL(lhsRangeIndex);
755 if (lhsRangeIndexCEIL === lhsRangeIndex && lhsRangeIndexCEIL < rangeCount)
756 aRange =
CPUnionRange(aRange, _ranges[lhsRangeIndexCEIL]);
759 rhsRangeIndexFLOOR = FLOOR(rhsRangeIndex);
761 if (rhsRangeIndexFLOOR === rhsRangeIndex && rhsRangeIndexFLOOR >= 0)
762 aRange =
CPUnionRange(aRange, _ranges[rhsRangeIndexFLOOR]);
764 var removalCount = rhsRangeIndexFLOOR - lhsRangeIndexCEIL + 1;
766 if (removalCount === _ranges.length)
769 _count = aRange.length;
772 else if (removalCount === 1)
774 if (lhsRangeIndexCEIL < _ranges.length)
775 _count -= _ranges[lhsRangeIndexCEIL].length;
777 _count += aRange.length;
778 _ranges[lhsRangeIndexCEIL] = aRange;
783 if (removalCount > 0)
785 var removal = lhsRangeIndexCEIL,
786 lastRemoval = lhsRangeIndexCEIL + removalCount - 1;
788 for (; removal <= lastRemoval; ++removal)
789 _count -= _ranges[removal].length;
791 [_ranges removeObjectsInRange:CPMakeRange(lhsRangeIndexCEIL, removalCount)];
794 [_ranges insertObject:aRange atIndex:lhsRangeIndexCEIL];
796 _count += aRange.length;
805 - (void)removeIndex:(CPInteger)anIndex
817 var otherRanges = anIndexSet._ranges,
818 otherRangesCount = otherRanges.length;
821 while (otherRangesCount--)
828 - (void)removeAllIndexes
839 - (void)removeIndexesInRange:(CPRange)aRange
842 if (aRange.length <= 0)
849 var rangeCount = _ranges.length,
851 lhsRangeIndexCEIL = CEIL(lhsRangeIndex);
854 if (lhsRangeIndex === lhsRangeIndexCEIL && lhsRangeIndexCEIL < rangeCount)
856 var existingRange = _ranges[lhsRangeIndexCEIL];
859 if (aRange.location !== existingRange.location)
864 existingRange.length = aRange.location - existingRange.location;
867 if (maxRange < existingMaxRange)
869 _count -= aRange.length;
870 [_ranges insertObject:CPMakeRange(maxRange, existingMaxRange - maxRange) atIndex:lhsRangeIndexCEIL + 1];
876 _count -= existingMaxRange - aRange.location;
877 lhsRangeIndexCEIL += 1;
883 rhsRangeIndexFLOOR = FLOOR(rhsRangeIndex);
885 if (rhsRangeIndex === rhsRangeIndexFLOOR && rhsRangeIndexFLOOR >= 0)
888 existingRange = _ranges[rhsRangeIndexFLOOR],
891 if (maxRange !== existingMaxRange)
893 _count -= maxRange - existingRange.location;
894 rhsRangeIndexFLOOR -= 1;
896 existingRange.location = maxRange;
897 existingRange.length = existingMaxRange - maxRange;
901 var removalCount = rhsRangeIndexFLOOR - lhsRangeIndexCEIL + 1;
903 if (removalCount > 0)
905 var removal = lhsRangeIndexCEIL,
906 lastRemoval = lhsRangeIndexCEIL + removalCount - 1;
908 for (; removal <= lastRemoval; ++removal)
909 _count -= _ranges[removal].length;
911 [_ranges removeObjectsInRange:CPMakeRange(lhsRangeIndexCEIL, removalCount)];
922 - (void)shiftIndexesStartingAtIndex:(CPInteger)anIndex by:(
int)aDelta
924 if (!_count || aDelta == 0)
929 var i = _ranges.length - 1,
934 var range = _ranges[i],
937 if (anIndex >= maximum)
942 if (anIndex > range.location)
945 shifted =
CPMakeRange(anIndex + aDelta, maximum - anIndex);
946 range.length = anIndex - range.location;
951 [_ranges insertObject:shifted atIndex:i + 1];
953 else if (shifted.location < 0)
956 shifted.location = 0;
964 if ((range.location += aDelta) < 0)
976 count = _ranges.length,
979 for (; j < count; ++j)
981 [shifts addObject:_ranges[j]];
982 _count -= _ranges[j].length;
985 if ((j = i + 1) < count)
987 [_ranges removeObjectsInRange:CPMakeRange(j, count - j)];
989 for (j = 0, count = shifts.length; j < count; ++j)
1013 self = [
super init];
1017 _count = [aCoder decodeIntForKey:CPIndexSetCountKey];
1020 var rangeStrings = [aCoder decodeObjectForKey:CPIndexSetRangeStringsKey],
1022 count = rangeStrings.length;
1024 for (; index < count; ++index)
1038 [aCoder encodeInt:_count forKey:CPIndexSetCountKey];
1041 count = _ranges.length,
1044 for (; index < count; ++index)
1047 [aCoder encodeObject:rangeStrings forKey:CPIndexSetRangeStringsKey];
1062 return [[[
self class] alloc] initWithIndexSet:self];
1073 return [[[
self class] alloc] initWithIndexSet:self];
1096 high = ranges.length - 1;
1100 var middle = FLOOR(low + (high - low) / 2),
1101 range = ranges[middle];
1103 if (anIndex < range.location)
1118 var count = ranges.length;
1128 var middle = FLOOR(low + (high - low) / 2),
1129 position = middle / 2,
1130 positionFLOOR = FLOOR(position);
1132 if (position === positionFLOOR)
1134 if (positionFLOOR - 1 >= 0 && anIndex <
CPMaxRange(ranges[positionFLOOR - 1]))
1137 else if (positionFLOOR < count && anIndex >= ranges[positionFLOOR].location)
1141 return positionFLOOR - 0.5;
1145 var range = ranges[positionFLOOR];
1147 if (anIndex < range.location)
1154 return positionFLOOR;