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