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
00030 @implementation CPIndexSet : CPObject
00031 {
00032 unsigned _count;
00033 unsigned _cachedRangeIndex;
00034 CPArray _ranges;
00035 }
00036
00037
00041 + (id)indexSet
00042 {
00043 return [[self alloc] init];
00044 }
00045
00049 + (id)indexSetWithIndex:(int)anIndex
00050 {
00051 return [[self alloc] initWithIndex:anIndex];
00052 }
00053
00058 + (id)indexSetWithIndexesInRange:(CPRange)aRange
00059 {
00060 return [[self alloc] initWithIndexesInRange:aRange];
00061 }
00062
00063
00064
00065 - (id)init
00066 {
00067 self = [super init];
00068
00069 if (self)
00070 {
00071 _count = 0;
00072 _ranges = [];
00073 _cachedRangeIndex = 0;
00074 }
00075
00076 return self;
00077 }
00078
00083 - (id)initWithIndex:(int)anIndex
00084 {
00085 self = [super init];
00086
00087 if (self)
00088 {
00089 _count = 1;
00090 _ranges = [CPArray arrayWithObject:CPMakeRange(anIndex, 1)];
00091 _cachedRangeIndex = 0;
00092 }
00093
00094 return self;
00095 }
00096
00102 - (id)initWithIndexesInRange:(CPRange)aRange
00103 {
00104 self = [super init];
00105
00106 if (self)
00107 {
00108 _count = aRange.length;
00109 _ranges = [CPArray arrayWithObject:aRange];
00110 _cachedRangeIndex = 0;
00111 }
00112
00113 return self;
00114 }
00115
00121 - (id)initWithIndexSet:(CPIndexSet)anIndexSet
00122 {
00123 self = [super init];
00124
00125 if (self)
00126 {
00127 _count = [anIndexSet count];
00128 _ranges = [];
00129 _cachedRangeIndex = 0;
00130
00131 var index = 0,
00132 count = anIndexSet._ranges.length;
00133
00134 for (; index < count; ++index)
00135 _ranges.push(CPCopyRange(anIndexSet._ranges[index]));
00136 }
00137
00138 return self;
00139 }
00140
00141
00147 - (BOOL)isEqualToIndexSet:(CPIndexSet)anIndexSet
00148 {
00149
00150 if (self == anIndexSet)
00151 return YES;
00152
00153 var i = 0,
00154 count = _ranges.length;
00155 otherRanges = anIndexSet._ranges;
00156
00157
00158
00159 if (count != otherRanges.length || _count != [anIndexSet count])
00160 return NO;
00161
00162 for (; i < count; ++i)
00163 if (!CPEqualRanges(_ranges[i], otherRanges[i]))
00164 return NO;
00165
00166 return YES;
00167 }
00168
00174 - (BOOL)containsIndex:(unsigned)anIndex
00175 {
00176 return [self containsIndexesInRange:CPMakeRange(anIndex, 1)];
00177 }
00178
00183 - (BOOL)containsIndexesInRange:(CPRange)aRange
00184 {
00185 if(!_count)
00186 return NO;
00187
00188 var i = SOERangeIndex(self, aRange.location),
00189 lower = aRange.location,
00190 upper = CPMaxRange(aRange),
00191 count = _ranges.length;
00192
00193
00194
00195 for(;i < count && _ranges[i].location < upper; ++i)
00196
00197 if (_ranges[i].location <= lower && CPMaxRange(_ranges[i]) >= upper)
00198 {
00199 _cachedRangeIndex = i;
00200 return YES;
00201 }
00202
00203
00204
00205 _cachedRangeIndex = i;
00206
00207 return NO;
00208 }
00209
00214 - (BOOL)containsIndexes:(CPIndexSet)anIndexSet
00215 {
00216
00217 if(![anIndexSet count])
00218 return YES;
00219
00220
00221 if(!_count)
00222 return NO;
00223
00224 var i = 0,
00225 count = _ranges.length;
00226
00227
00228 for(; i < count; ++i)
00229 if (![anIndexSet containsIndexesInRange:_ranges[i]])
00230 return NO;
00231
00232 return YES;
00233 }
00234
00240 - (BOOL)intersectsIndexesInRange:(CPRange)aRange
00241 {
00242
00243 if(!_count)
00244 return NO;
00245
00246 var i = SOERangeIndex(self, aRange.location),
00247 count = _ranges.length,
00248 upper = CPMaxRange(aRange);
00249
00250
00251
00252 for (; i < count && _ranges[i].location < upper; ++i)
00253 if(CPIntersectionRange(aRange, _ranges[i]).length)
00254 return YES;
00255
00256 return NO;
00257 }
00258
00262 - (int)count
00263 {
00264 return _count;
00265 }
00266
00267
00271 - (int)firstIndex
00272 {
00273 return _count ? _ranges[0].location : CPNotFound;
00274 }
00275
00279 - (int)lastIndex
00280 {
00281 return _count ? CPMaxRange(_ranges[_ranges.length - 1]) - 1 : CPNotFound;
00282 }
00283
00288 - (unsigned)indexGreaterThanIndex:(unsigned)anIndex
00289 {
00290 if(!_count)
00291 return CPNotFound;
00292
00293 var i = SOERangeIndex(self, anIndex++),
00294 count = _ranges.length;
00295
00296 for(; i < count && anIndex >= CPMaxRange(_ranges[i]); ++i) ;
00297
00298 if (i == count)
00299 return CPNotFound;
00300
00301 _cachedRangeIndex = i;
00302
00303 if (anIndex < _ranges[i].location)
00304 return _ranges[i].location;
00305
00306 return anIndex;
00307 }
00308
00313 - (unsigned)indexLessThanIndex:(unsigned)anIndex
00314 {
00315 if (!_count)
00316 return CPNotFound;
00317
00318 var i = GOERangeIndex(self, anIndex--);
00319
00320 for (; i >= 0 && anIndex < _ranges[i].location; --i) ;
00321
00322 if(i < 0)
00323 return CPNotFound;
00324
00325 _cachedRangeIndex = i;
00326
00327 if (CPLocationInRange(anIndex, _ranges[i]))
00328 return anIndex;
00329
00330 if (CPMaxRange(_ranges[i]) - 1 < anIndex)
00331 return CPMaxRange(_ranges[i]) - 1;
00332
00333 return CPNotFound;
00334 }
00335
00340 - (unsigned int)indexGreaterThanOrEqualToIndex:(unsigned)anIndex
00341 {
00342 return [self indexGreaterThanIndex:anIndex - 1];
00343 }
00344
00349 - (unsigned int)indexLessThanOrEqualToIndex:(unsigned)anIndex
00350 {
00351 return [self indexLessThanIndex:anIndex + 1];
00352 }
00353
00363 - (unsigned)getIndexes:(CPArray)anArray maxCount:(unsigned)aMaxCount inIndexRange:(CPRange)aRangePointer
00364 {
00365 if (!_count || aMaxCount <= 0 || aRangePointer && !aRangePointer.length)
00366 return 0;
00367
00368 var i = SOERangeIndex(self, aRangePointer? aRangePointer.location : 0),
00369 total = 0,
00370 count = _ranges.length;
00371
00372 for (; i < count; ++i)
00373 {
00374
00375 var intersection = aRangePointer ? CPIntersectionRange(_ranges[i], aRangePointer) : _ranges[i],
00376 index = intersection.location,
00377 maximum = CPMaxRange(intersection);
00378
00379 for (; index < maximum; ++index)
00380 {
00381 anArray[total++] = index;
00382
00383 if (total == aMaxCount)
00384 {
00385
00386 if (aRangePointer)
00387 {
00388 var upper = CPMaxRange(aRangePointer);
00389
00390
00391 aRangePointer.location = index + 1;
00392 aRangePointer.length = upper - index - 1;
00393 }
00394
00395 return aMaxCount;
00396 }
00397 }
00398 }
00399
00400
00401 if (aRangePointer)
00402 {
00403 aRangePointer.location = CPNotFound;
00404 aRangePointer.length = 0;
00405 }
00406
00407 return total;
00408 }
00409
00410 - (CPString)description
00411 {
00412 var desc = [super description] + " ";
00413
00414 if (_count)
00415 {
00416 desc += "[number of indexes: " + _count + " (in " + _ranges.length + " ranges), indexes: (";
00417 for (i = 0; i < _ranges.length; i++)
00418 {
00419 desc += _ranges[i].location;
00420 if (_ranges[i].length > 1) desc += "-" + (CPMaxRange(_ranges[i])-1) + ":"+_ranges[i].length+":";
00421 if (i+1 < _ranges.length) desc += " ";
00422 }
00423 desc += ")]";
00424 }
00425 else
00426 desc += "(no indexes)";
00427 return desc;
00428 }
00429
00430 @end
00431
00432 @implementation CPIndexSet(CPMutableIndexSet)
00433
00434
00439 - (void)addIndex:(unsigned)anIndex
00440 {
00441 [self addIndexesInRange:CPMakeRange(anIndex, 1)];
00442 }
00443
00448 - (void)addIndexes:(CPIndexSet)anIndexSet
00449 {
00450 var i = 0,
00451 ranges = anIndexSet._ranges,
00452 count = ranges.length;
00453
00454
00455 for(; i < count; ++i)
00456 [self addIndexesInRange:ranges[i]];
00457 }
00458
00463 - (void)addIndexesInRange:(CPRange)aRange
00464 {
00465 if (_ranges.length == 0)
00466 {
00467 _count = aRange.length;
00468
00469 return [_ranges addObject:CPCopyRange(aRange)];
00470 }
00471
00472
00473
00474
00475 var i = SOERangeIndex(self, aRange.location),
00476 count = _ranges.length,
00477 padded = CPMakeRange(aRange.location - 1, aRange.length + 2),
00478 maximum = CPMaxRange(aRange);
00479
00480
00481 if (count && CPMaxRange(_ranges[count - 1]) < aRange.location)
00482 [_ranges addObject:CPCopyRange(aRange)];
00483 else
00484 for (; i < count; ++i)
00485 {
00486
00487
00488 if (maximum < _ranges[i].location)
00489 {
00490 _count += aRange.length;
00491
00492
00493 if (i < _cachedRangeIndex) ++_cachedRangeIndex;
00494
00495 return [_ranges insertObject:CPCopyRange(aRange) atIndex:i];
00496 }
00497
00498 if (CPIntersectionRange(_ranges[i], padded).length)
00499 {
00500 var union = CPUnionRange(_ranges[i], aRange);
00501
00502
00503 if (union.length == _ranges[i].length)
00504 return;
00505
00506
00507 ++union.length;
00508
00509
00510
00511
00512
00513 var j = i;
00514
00515 for(; j < count; ++j)
00516
00517 if(CPIntersectionRange(union, _ranges[j]).length)
00518 _count -= _ranges[j].length;
00519 else
00520 break;
00521
00522
00523
00524
00525
00526 --union.length;
00527 _ranges[i] = union;
00528
00529
00530 if (j - i - 1 > 0)
00531 {
00532 var remove = CPMakeRange(i + 1, j - i - 1);
00533
00534 _ranges[i] = CPUnionRange(_ranges[i], _ranges[j - 1]);
00535 [_ranges removeObjectsInRange:remove];
00536
00537
00538 if (_cachedRangeIndex >= CPMaxRange(remove)) _cachedRangedIndex -= remove.length;
00539 else if (CPLocationInRange(_cachedRangeIndex, remove)) _cachedRangeIndex = i;
00540 }
00541
00542
00543 _count += _ranges[i].length;
00544
00545 return;
00546 }
00547 }
00548
00549 _count += aRange.length;
00550 }
00551
00552
00557 - (void)removeIndex:(unsigned int)anIndex
00558 {
00559 [self removeIndexesInRange:CPMakeRange(anIndex, 1)];
00560 }
00561
00567 - (void)removeIndexes:(CPIndexSet)anIndexSet
00568 {
00569 var i = 0,
00570 ranges = anIndexSet._ranges,
00571 count = ranges.length;
00572
00573
00574 for(; i < count; ++i)
00575 [self removeIndexesInRange:ranges[i]];
00576 }
00577
00581 - (void)removeAllIndexes
00582 {
00583 _ranges = [];
00584 _count = 0;
00585 _cachedRangeIndex = 0;
00586 }
00587
00593 - (void)removeIndexesInRange:(CPRange)aRange
00594 {
00595
00596
00597
00598 var i = SOERangeIndex(self, aRange.location),
00599 count = _ranges.length,
00600 maximum = CPMaxRange(aRange),
00601 removal = CPMakeRange(CPNotFound, 0);
00602
00603 for (; i < count; ++i)
00604 {
00605 var range = _ranges[i];
00606
00607
00608 if (maximum < range.location)
00609 break;
00610
00611 var intersection = CPIntersectionRange(range, aRange);
00612
00613
00614 if (!intersection.length)
00615 continue;
00616
00617
00618
00619 else if (intersection.length == range.length)
00620 {
00621 if (removal.location == CPNotFound)
00622 removal = CPMakeRange(i, 1);
00623 else
00624 ++removal.length;
00625 }
00626
00627
00628 else if (intersection.location > range.location && CPMaxRange(intersection) < CPMaxRange(range))
00629 {
00630 var insert = CPMakeRange(CPMaxRange(intersection), CPMaxRange(range) - CPMaxRange(intersection));
00631
00632 range.length = intersection.location - range.location;
00633
00634 _count -= intersection.length;
00635
00636 return [_ranges insertObject:insert atIndex:i + 1];
00637 }
00638
00639 else
00640 {
00641 range.length -= intersection.length;
00642
00643 if (intersection.location <= range.location)
00644 range.location += intersection.length;
00645 }
00646
00647 _count -= intersection.length;
00648 }
00649
00650 if (removal.length)
00651 [_ranges removeObjectsInRange:removal];
00652 }
00653
00654
00661 - (void)shiftIndexesStartingAtIndex:(unsigned)anIndex by:(int)aDelta
00662 {
00663 if (!_count || aDelta == 0)
00664 return;
00665
00666
00667
00668 var i = _ranges.length - 1,
00669 shifted = CPMakeRange(CPNotFound, 0);
00670
00671 for(; i >= 0; --i)
00672 {
00673 var range = _ranges[i],
00674 maximum = CPMaxRange(range);
00675
00676 if (anIndex > maximum)
00677 break;
00678
00679
00680
00681 if (anIndex > range.location && anIndex < maximum)
00682 {
00683
00684 shifted = CPMakeRange(anIndex + aDelta, maximum - anIndex);
00685 range.length = anIndex - range.location;
00686
00687
00688
00689 if (aDelta > 0)
00690 [_ranges insertObject:shifted atIndex:i + 1];
00691
00692 else if (shifted.location < 0)
00693 {
00694 shifted.length = CPMaxRange(shifted);
00695 shifted.location = 0;
00696 }
00697
00698
00699 break;
00700 }
00701
00702
00703 if ((range.location += aDelta) < 0)
00704 {
00705 range.length = CPMaxRange(range);
00706 range.location = 0;
00707 }
00708 }
00709
00710
00711 if (aDelta < 0)
00712 {
00713 var j = i + 1,
00714 count = _ranges.length,
00715 shifts = [];
00716
00717 for (; j < count; ++j)
00718 [shifts addObject:_ranges[j]];
00719
00720 if ((j = i + 1) < count)
00721 {
00722 [_ranges removeObjectsInRange:CPMakeRange(j, count - j)];
00723
00724 for (j = 0, count = shifts.length; j < count; ++j)
00725 [self addIndexesInRange:shifts[j]];
00726 }
00727
00728 if (shifted.location != CPNotFound)
00729 [self addIndexesInRange:shifted];
00730 }
00731 }
00732
00733 @end
00734
00735 var CPIndexSetCountKey = @"CPIndexSetCountKey",
00736 CPIndexSetCachedRangeIndexKey = @"CPIndexSetCachedRangeIndexKey",
00737 CPIndexSetRangeStringsKey = @"CPIndexSetRangeStringsKey";
00738
00739 @implementation CPIndexSet (CPCoding)
00740
00747 - (id)initWithCoder:(CPCoder)aCoder
00748 {
00749 self = [super init];
00750
00751 if (self)
00752 {
00753 _count = [aCoder decodeIntForKey:CPIndexSetCountKey];
00754 _cachedRangeIndex = [aCoder decodeIntForKey:CPIndexSetCachedRangeIndexKey];
00755 _ranges = [];
00756
00757 var rangeStrings = [aCoder decodeObjectForKey:CPIndexSetRangeStringsKey],
00758 index = 0,
00759 count = rangeStrings.length;
00760
00761 for (; index < count; ++index)
00762 _ranges.push(CPRangeFromString(rangeStrings[index]));
00763 }
00764
00765 return self;
00766 }
00767
00773 - (void)encodeWithCoder:(CPCoder)aCoder
00774 {
00775 [aCoder encodeInt:_count forKey:CPIndexSetCountKey];
00776 [aCoder encodeInt:_cachedRangeIndex forKey:CPIndexSetCachedRangeIndexKey];
00777
00778 var index = 0,
00779 count = _ranges.length,
00780 rangeStrings = [];
00781
00782 for (; index < count; ++index)
00783 rangeStrings[index] = CPStringFromRange(_ranges[index]);
00784
00785 [aCoder encodeObject:rangeStrings forKey:CPIndexSetRangeStringsKey];
00786 }
00787
00788 @end
00789
00790 @implementation CPIndexSet (CPCopying)
00791
00798 - (id)copy
00799 {
00800 return [[[self class] alloc] initWithIndexSet:self];
00801 }
00802
00809 - (id)mutableCopy
00810 {
00811 return [[[self class] alloc] initWithIndexSet:self];
00812 }
00813
00814 @end
00815
00821 @implementation CPMutableIndexSet : CPIndexSet
00822
00823 @end
00824
00825 var SOERangeIndex = function(anIndexSet, anIndex)
00826 {
00827 var ranges = anIndexSet._ranges,
00828 cachedRangeIndex = 0;
00829
00830 if(cachedRangeIndex < ranges.length && anIndex >= ranges[cachedRangeIndex].location)
00831 return cachedRangeIndex;
00832
00833 return 0;
00834 }
00835
00836 var GOERangeIndex = function(anIndexSet, anIndex)
00837 {
00838 var ranges = anIndexSet._ranges,
00839 cachedRangeIndex = anIndexSet._ranges.length;
00840
00841 if(cachedRangeIndex < ranges.length && anIndex <= ranges[cachedRangeIndex].location)
00842 return cachedRangeIndex;
00843
00844 return ranges.length - 1;
00845 }
00846
00847
00848
00849
00850
00851
00852
00853
00854
00855
00856
00857
00858
00859
00860
00861
00862
00863
00864
00865
00866
00867
00868
00869
00870
00871
00872
00873
00874
00875
00876
00877