00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023 @import "CPRange.j"
00024 @import "CPObject.j"
00025
00026 #define _CPMaxRange(aRange) ((aRange).location + (aRange).length)
00027 #define _CPMakeRange(aLocation, aLength) { location:(aLocation), length:aLength }
00028 #define _CPMakeRangeCopy(aRange) { location:(aRange).location, length:(aRange).length }
00029
00038 @implementation CPIndexSet : CPObject
00039 {
00040 unsigned _count;
00041 CPArray _ranges;
00042 }
00043
00044
00048 + (id)indexSet
00049 {
00050 return [[self alloc] init];
00051 }
00052
00056 + (id)indexSetWithIndex:(int)anIndex
00057 {
00058 return [[self alloc] initWithIndex:anIndex];
00059 }
00060
00065 + (id)indexSetWithIndexesInRange:(CPRange)aRange
00066 {
00067 return [[self alloc] initWithIndexesInRange:aRange];
00068 }
00069
00070
00071
00072 - (id)init
00073 {
00074 return [self initWithIndexesInRange:_CPMakeRange(0, 0)];
00075 }
00076
00081 - (id)initWithIndex:(CPInteger)anIndex
00082 {
00083 return [self initWithIndexesInRange:_CPMakeRange(anIndex, 1)];
00084 }
00085
00091 - (id)initWithIndexesInRange:(CPRange)aRange
00092 {
00093 self = [super init];
00094
00095 if (self)
00096 {
00097 _count = MAX(0, aRange.length);
00098
00099 if (_count > 0)
00100 _ranges = [aRange];
00101 else
00102 _ranges = [];
00103 }
00104
00105 return self;
00106 }
00107
00113 - (id)initWithIndexSet:(CPIndexSet)anIndexSet
00114 {
00115 self = [super init];
00116
00117 if (self)
00118 {
00119 _count = [anIndexSet count];
00120 _ranges = [];
00121
00122 var otherRanges = anIndexSet._ranges,
00123 otherRangesCount = otherRanges.length;
00124
00125 while (otherRangesCount--)
00126 _ranges[otherRangesCount] = _CPMakeRangeCopy(otherRanges[otherRangesCount]);
00127 }
00128
00129 return self;
00130 }
00131
00132
00138 - (BOOL)isEqualToIndexSet:(CPIndexSet)anIndexSet
00139 {
00140 if (!anIndexSet)
00141 return NO;
00142
00143
00144 if (self === anIndexSet)
00145 return YES;
00146
00147 var rangesCount = _ranges.length,
00148 otherRanges = anIndexSet._ranges;
00149
00150
00151
00152 if (rangesCount !== otherRanges.length || _count !== anIndexSet._count)
00153 return NO;
00154
00155 while (rangesCount--)
00156 if (!CPEqualRanges(_ranges[rangesCount], otherRanges[rangesCount]))
00157 return NO;
00158
00159 return YES;
00160 }
00161
00167 - (BOOL)containsIndex:(CPInteger)anIndex
00168 {
00169 return positionOfIndex(_ranges, anIndex) !== CPNotFound;
00170 }
00171
00176 - (BOOL)containsIndexesInRange:(CPRange)aRange
00177 {
00178 if (aRange.length <= 0)
00179 return NO;
00180
00181
00182 if(_count < aRange.length)
00183 return NO;
00184
00185
00186 var rangeIndex = positionOfIndex(_ranges, aRange.location);
00187
00188
00189 if (rangeIndex === CPNotFound)
00190 return NO;
00191
00192 var range = _ranges[rangeIndex];
00193
00194
00195 return CPIntersectionRange(range, aRange).length === aRange.length;
00196 }
00197
00202 - (BOOL)containsIndexes:(CPIndexSet)anIndexSet
00203 {
00204 var otherCount = anIndexSet._count;
00205
00206 if(otherCount <= 0)
00207 return YES;
00208
00209
00210 if (_count < otherCount)
00211 return NO;
00212
00213 var otherRanges = anIndexSet._ranges,
00214 otherRangesCount = otherRanges.length;
00215
00216 while (otherRangesCount--)
00217 if (![self containsIndexesInRange:otherRanges[otherRangesCount]])
00218 return NO;
00219
00220 return YES;
00221 }
00222
00228 - (BOOL)intersectsIndexesInRange:(CPRange)aRange
00229 {
00230 if (_count <= 0)
00231 return NO;
00232
00233 var lhsRangeIndex = assumedPositionOfIndex(_ranges, aRange.location);
00234
00235 if (FLOOR(lhsRangeIndex) === lhsRangeIndex)
00236 return YES;
00237
00238 var rhsRangeIndex = assumedPositionOfIndex(_ranges, _CPMaxRange(aRange) - 1);
00239
00240 if (FLOOR(rhsRangeIndex) === rhsRangeIndex)
00241 return YES;
00242
00243 return lhsRangeIndex !== rhsRangeIndex;
00244 }
00245
00249 - (int)count
00250 {
00251 return _count;
00252 }
00253
00254
00258 - (CPInteger)firstIndex
00259 {
00260 if (_count > 0)
00261 return _ranges[0].location;
00262
00263 return CPNotFound;
00264 }
00265
00269 - (CPInteger)lastIndex
00270 {
00271 if (_count > 0)
00272 return _CPMaxRange(_ranges[_ranges.length - 1]) - 1;
00273
00274 return CPNotFound;
00275 }
00276
00281 - (CPInteger)indexGreaterThanIndex:(CPInteger)anIndex
00282 {
00283
00284 ++anIndex;
00285
00286
00287 var rangeIndex = assumedPositionOfIndex(_ranges, anIndex);
00288
00289
00290 if (rangeIndex === CPNotFound)
00291 return CPNotFound;
00292
00293 rangeIndex = CEIL(rangeIndex);
00294
00295 if (rangeIndex >= _ranges.length)
00296 return CPNotFound;
00297
00298 var range = _ranges[rangeIndex];
00299
00300
00301 if (CPLocationInRange(anIndex, range))
00302 return anIndex;
00303
00304
00305 return range.location;
00306 }
00307
00312 - (CPInteger)indexLessThanIndex:(CPInteger)anIndex
00313 {
00314
00315 --anIndex;
00316
00317
00318 var rangeIndex = assumedPositionOfIndex(_ranges, anIndex);
00319
00320
00321 if (rangeIndex === CPNotFound)
00322 return CPNotFound;
00323
00324 rangeIndex = FLOOR(rangeIndex);
00325
00326 if (rangeIndex < 0)
00327 return CPNotFound;
00328
00329 var range = _ranges[rangeIndex];
00330
00331
00332 if (CPLocationInRange(anIndex, range))
00333 return anIndex;
00334
00335
00336 return _CPMaxRange(range) - 1;
00337 }
00338
00343 - (CPInteger)indexGreaterThanOrEqualToIndex:(CPInteger)anIndex
00344 {
00345 return [self indexGreaterThanIndex:anIndex - 1];
00346 }
00347
00352 - (CPInteger)indexLessThanOrEqualToIndex:(CPInteger)anIndex
00353 {
00354 return [self indexLessThanIndex:anIndex + 1];
00355 }
00356
00366 - (CPInteger)getIndexes:(CPArray)anArray maxCount:(CPInteger)aMaxCount inIndexRange:(CPRange)aRange
00367 {
00368 if (!_count || aMaxCount === 0 || aRange && !aRange.length)
00369 {
00370 if (aRange)
00371 aRange.length = 0;
00372
00373 return 0;
00374 }
00375
00376 var total = 0;
00377
00378 if (aRange)
00379 {
00380 var firstIndex = aRange.location,
00381 lastIndex = _CPMaxRange(aRange) - 1,
00382 rangeIndex = CEIL(assumedPositionOfIndex(_ranges, firstIndex)),
00383 lastRangeIndex = FLOOR(assumedPositionOfIndex(_ranges, lastIndex));
00384 }
00385 else
00386 {
00387 var firstIndex = [self firstIndex],
00388 lastIndex = [self lastIndex],
00389 rangeIndex = 0,
00390 lastRangeIndex = _ranges.length - 1;
00391 }
00392
00393 while (rangeIndex <= lastRangeIndex)
00394 {
00395 var range = _ranges[rangeIndex],
00396 index = MAX(firstIndex, range.location),
00397 maxRange = MIN(lastIndex + 1, _CPMaxRange(range));
00398
00399 for (; index < maxRange; ++index)
00400 {
00401 anArray[total++] = index;
00402
00403 if (total === aMaxCount)
00404 {
00405
00406 if (aRange)
00407 {
00408 aRange.location = index + 1;
00409 aRange.length = lastIndex + 1 - index - 1;
00410 }
00411
00412 return aMaxCount;
00413 }
00414 }
00415
00416 ++rangeIndex;
00417 }
00418
00419
00420 if (aRange)
00421 {
00422 aRange.location = CPNotFound;
00423 aRange.length = 0;
00424 }
00425
00426 return total;
00427 }
00428
00429 - (CPString)description
00430 {
00431 var description = [super description];
00432
00433 if (_count)
00434 {
00435 var index = 0,
00436 count = _ranges.length;
00437
00438 description += "[number of indexes: " + _count + " (in " + count;
00439
00440 if (count === 1)
00441 description += " range), indexes: (";
00442 else
00443 description += " ranges), indexes: (";
00444
00445 for (; index < count; ++index)
00446 {
00447 var range = _ranges[index];
00448
00449 description += range.location;
00450
00451 if (range.length > 1)
00452 description += "-" + (CPMaxRange(range) - 1);
00453
00454 if (index + 1 < count)
00455 description += " ";
00456 }
00457
00458 description += ")]";
00459 }
00460
00461 else
00462 description += "(no indexes)";
00463
00464 return description;
00465 }
00466
00467 @end
00468
00469 @implementation CPIndexSet(CPMutableIndexSet)
00470
00471
00476 - (void)addIndex:(CPInteger)anIndex
00477 {
00478 [self addIndexesInRange:_CPMakeRange(anIndex, 1)];
00479 }
00480
00485 - (void)addIndexes:(CPIndexSet)anIndexSet
00486 {
00487 var otherRanges = anIndexSet._ranges,
00488 otherRangesCount = otherRanges.length;
00489
00490
00491 while (otherRangesCount--)
00492 [self addIndexesInRange:otherRanges[otherRangesCount]];
00493 }
00494
00499 - (void)addIndexesInRange:(CPRange)aRange
00500 {
00501
00502 if (aRange.length <= 0)
00503 return;
00504
00505
00506 if (_count <= 0)
00507 {
00508 _count = aRange.length;
00509 _ranges = [aRange];
00510
00511 return;
00512 }
00513
00514 var rangeCount = _ranges.length,
00515 lhsRangeIndex = assumedPositionOfIndex(_ranges, aRange.location - 1),
00516 lhsRangeIndexCEIL = CEIL(lhsRangeIndex);
00517
00518 if (lhsRangeIndexCEIL === lhsRangeIndex && lhsRangeIndexCEIL < rangeCount)
00519 aRange = CPUnionRange(aRange, _ranges[lhsRangeIndexCEIL]);
00520
00521 var rhsRangeIndex = assumedPositionOfIndex(_ranges, CPMaxRange(aRange)),
00522 rhsRangeIndexFLOOR = FLOOR(rhsRangeIndex);
00523
00524 if (rhsRangeIndexFLOOR === rhsRangeIndex && rhsRangeIndexFLOOR >= 0)
00525 aRange = CPUnionRange(aRange, _ranges[rhsRangeIndexFLOOR]);
00526
00527 var removalCount = rhsRangeIndexFLOOR - lhsRangeIndexCEIL + 1;
00528
00529 if (removalCount === _ranges.length)
00530 {
00531 _ranges = [aRange];
00532 _count = aRange.length;
00533 }
00534
00535 else if (removalCount === 1)
00536 {
00537 if (lhsRangeIndexCEIL < _ranges.length)
00538 _count -= _ranges[lhsRangeIndexCEIL].length;
00539
00540 _count += aRange.length;
00541 _ranges[lhsRangeIndexCEIL] = aRange;
00542 }
00543
00544 else
00545 {
00546 if (removalCount > 0)
00547 {
00548 var removal = lhsRangeIndexCEIL,
00549 lastRemoval = lhsRangeIndexCEIL + removalCount - 1;
00550
00551 for (; removal <= lastRemoval; ++removal)
00552 _count -= _ranges[removal].length;
00553
00554 [_ranges removeObjectsInRange:_CPMakeRange(lhsRangeIndexCEIL, removalCount)];
00555 }
00556
00557 [_ranges insertObject:aRange atIndex:lhsRangeIndexCEIL];
00558
00559 _count += aRange.length;
00560 }
00561 }
00562
00563
00568 - (void)removeIndex:(CPInteger)anIndex
00569 {
00570 [self removeIndexesInRange:_CPMakeRange(anIndex, 1)];
00571 }
00572
00578 - (void)removeIndexes:(CPIndexSet)anIndexSet
00579 {
00580 var otherRanges = anIndexSet._ranges,
00581 otherRangesCount = otherRanges.length;
00582
00583
00584 while (otherRangesCount--)
00585 [self removeIndexesInRange:otherRanges[otherRangesCount]];
00586 }
00587
00591 - (void)removeAllIndexes
00592 {
00593 _ranges = [];
00594 _count = 0;
00595 }
00596
00602 - (void)removeIndexesInRange:(CPRange)aRange
00603 {
00604
00605 if (aRange.length <= 0)
00606 return;
00607
00608
00609 if (_count <= 0)
00610 return;
00611
00612 var rangeCount = _ranges.length,
00613 lhsRangeIndex = assumedPositionOfIndex(_ranges, aRange.location),
00614 lhsRangeIndexCEIL = CEIL(lhsRangeIndex);
00615
00616
00617 if (lhsRangeIndex === lhsRangeIndexCEIL && lhsRangeIndexCEIL < rangeCount)
00618 {
00619 var existingRange = _ranges[lhsRangeIndexCEIL];
00620
00621
00622 if (aRange.location !== existingRange.location)
00623 {
00624 var maxRange = CPMaxRange(aRange),
00625 existingMaxRange = CPMaxRange(existingRange);
00626
00627 existingRange.length = aRange.location - existingRange.location;
00628
00629
00630 if (maxRange < existingMaxRange)
00631 {
00632 _count -= aRange.length;
00633 [_ranges insertObject:_CPMakeRange(maxRange, existingMaxRange - maxRange) atIndex:lhsRangeIndexCEIL + 1];
00634
00635 return;
00636 }
00637 else
00638 {
00639 _count -= existingMaxRange - aRange.location;
00640 lhsRangeIndexCEIL += 1;
00641 }
00642 }
00643 }
00644
00645 var rhsRangeIndex = assumedPositionOfIndex(_ranges, CPMaxRange(aRange) - 1),
00646 rhsRangeIndexFLOOR = FLOOR(rhsRangeIndex);
00647
00648 if (rhsRangeIndex === rhsRangeIndexFLOOR && rhsRangeIndexFLOOR >= 0)
00649 {
00650 var maxRange = CPMaxRange(aRange),
00651 existingRange = _ranges[rhsRangeIndexFLOOR],
00652 existingMaxRange = CPMaxRange(existingRange);
00653
00654 if (maxRange !== existingMaxRange)
00655 {
00656 _count -= maxRange - existingRange.location;
00657 rhsRangeIndexFLOOR -= 1;
00658
00659 existingRange.location = maxRange;
00660 existingRange.length = existingMaxRange - maxRange;
00661 }
00662 }
00663
00664 var removalCount = rhsRangeIndexFLOOR - lhsRangeIndexCEIL + 1;
00665
00666 if (removalCount > 0)
00667 {
00668 var removal = lhsRangeIndexCEIL,
00669 lastRemoval = lhsRangeIndexCEIL + removalCount - 1;
00670
00671 for (; removal <= lastRemoval; ++removal)
00672 _count -= _ranges[removal].length;
00673
00674 [_ranges removeObjectsInRange:_CPMakeRange(lhsRangeIndexCEIL, removalCount)];
00675 }
00676 }
00677
00678
00685 - (void)shiftIndexesStartingAtIndex:(CPInteger)anIndex by:(int)aDelta
00686 {
00687 if (!_count || aDelta == 0)
00688 return;
00689
00690
00691
00692 var i = _ranges.length - 1,
00693 shifted = CPMakeRange(CPNotFound, 0);
00694
00695 for(; i >= 0; --i)
00696 {
00697 var range = _ranges[i],
00698 maximum = CPMaxRange(range);
00699
00700 if (anIndex > maximum)
00701 break;
00702
00703
00704
00705 if (anIndex > range.location && anIndex < maximum)
00706 {
00707
00708 shifted = CPMakeRange(anIndex + aDelta, maximum - anIndex);
00709 range.length = anIndex - range.location;
00710
00711
00712
00713 if (aDelta > 0)
00714 [_ranges insertObject:shifted atIndex:i + 1];
00715
00716 else if (shifted.location < 0)
00717 {
00718 shifted.length = CPMaxRange(shifted);
00719 shifted.location = 0;
00720 }
00721
00722
00723 break;
00724 }
00725
00726
00727 if ((range.location += aDelta) < 0)
00728 {
00729 range.length = CPMaxRange(range);
00730 range.location = 0;
00731 }
00732 }
00733
00734
00735 if (aDelta < 0)
00736 {
00737 var j = i + 1,
00738 count = _ranges.length,
00739 shifts = [];
00740
00741 for (; j < count; ++j)
00742 {
00743 [shifts addObject:_ranges[j]];
00744 _count -= _ranges[j].length;
00745 }
00746
00747 if ((j = i + 1) < count)
00748 {
00749 [_ranges removeObjectsInRange:CPMakeRange(j, count - j)];
00750
00751 for (j = 0, count = shifts.length; j < count; ++j)
00752 [self addIndexesInRange:shifts[j]];
00753 }
00754
00755 if (shifted.location != CPNotFound)
00756 [self addIndexesInRange:shifted];
00757 }
00758 }
00759
00760 @end
00761
00762 var CPIndexSetCountKey = @"CPIndexSetCountKey",
00763 CPIndexSetRangeStringsKey = @"CPIndexSetRangeStringsKey";
00764
00765 @implementation CPIndexSet (CPCoding)
00766
00773 - (id)initWithCoder:(CPCoder)aCoder
00774 {
00775 self = [super init];
00776
00777 if (self)
00778 {
00779 _count = [aCoder decodeIntForKey:CPIndexSetCountKey];
00780 _ranges = [];
00781
00782 var rangeStrings = [aCoder decodeObjectForKey:CPIndexSetRangeStringsKey],
00783 index = 0,
00784 count = rangeStrings.length;
00785
00786 for (; index < count; ++index)
00787 _ranges.push(CPRangeFromString(rangeStrings[index]));
00788 }
00789
00790 return self;
00791 }
00792
00798 - (void)encodeWithCoder:(CPCoder)aCoder
00799 {
00800 [aCoder encodeInt:_count forKey:CPIndexSetCountKey];
00801
00802 var index = 0,
00803 count = _ranges.length,
00804 rangeStrings = [];
00805
00806 for (; index < count; ++index)
00807 rangeStrings[index] = CPStringFromRange(_ranges[index]);
00808
00809 [aCoder encodeObject:rangeStrings forKey:CPIndexSetRangeStringsKey];
00810 }
00811
00812 @end
00813
00814 @implementation CPIndexSet (CPCopying)
00815
00822 - (id)copy
00823 {
00824 return [[[self class] alloc] initWithIndexSet:self];
00825 }
00826
00833 - (id)mutableCopy
00834 {
00835 return [[[self class] alloc] initWithIndexSet:self];
00836 }
00837
00838 @end
00839
00848 @implementation CPMutableIndexSet : CPIndexSet
00849
00850 @end
00851
00852 var positionOfIndex = function(ranges, anIndex)
00853 {
00854 var low = 0,
00855 high = ranges.length - 1;
00856
00857 while (low <= high)
00858 {
00859 var middle = FLOOR(low + (high - low) / 2),
00860 range = ranges[middle];
00861
00862 if (anIndex < range.location)
00863 high = middle - 1;
00864
00865 else if (anIndex >= CPMaxRange(range))
00866 low = middle + 1;
00867
00868 else
00869 return middle;
00870 }
00871
00872 return CPNotFound;
00873 }
00874
00875 var assumedPositionOfIndex = function(ranges, anIndex)
00876 {
00877 var count = ranges.length;
00878
00879 if (count <= 0)
00880 return CPNotFound;
00881
00882 var low = 0,
00883 high = count * 2;
00884
00885 while (low <= high)
00886 {
00887 var middle = FLOOR(low + (high - low) / 2),
00888 position = middle / 2,
00889 positionFLOOR = FLOOR(position);
00890
00891 if (position === positionFLOOR)
00892 {
00893 if (positionFLOOR - 1 >= 0 && anIndex < CPMaxRange(ranges[positionFLOOR - 1]))
00894 high = middle - 1;
00895
00896 else if (positionFLOOR < count && anIndex >= ranges[positionFLOOR].location)
00897 low = middle + 1;
00898
00899 else
00900 return positionFLOOR - 0.5;
00901 }
00902 else
00903 {
00904 var range = ranges[positionFLOOR];
00905
00906 if (anIndex < range.location)
00907 high = middle - 1;
00908
00909 else if (anIndex >= CPMaxRange(range))
00910 low = middle + 1;
00911
00912 else
00913 return positionFLOOR;
00914 }
00915 }
00916
00917 return CPNotFound;
00918 }
00919
00920
00921
00922
00923
00924
00925
00926
00927
00928
00929
00930
00931
00932
00933
00934
00935
00936
00937
00938
00939
00940
00941
00942
00943
00944
00945
00946
00947
00948
00949
00950