1/** Implementation for NSIndexSet, NSMutableIndexSet for GNUStep
2   Copyright (C) 2004 Free Software Foundation, Inc.
3
4   Written by:  Richard Frith-Macdonald <rfm@gnu.org>
5   Created: Feb 2004
6
7   This file is part of the GNUstep Base Library.
8
9   This library is free software; you can redistribute it and/or
10   modify it under the terms of the GNU Lesser General Public
11   License as published by the Free Software Foundation; either
12   version 2 of the License, or (at your option) any later version.
13
14   This library is distributed in the hope that it will be useful,
15   but WITHOUT ANY WARRANTY; without even the implied warranty of
16   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
17   Lesser General Public License for more details.
18
19   You should have received a copy of the GNU Lesser General Public
20   License along with this library; if not, write to the Free
21   Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
22   Boston, MA 02110 USA.
23
24   */
25
26#import "common.h"
27#define	EXPOSE_NSIndexSet_IVARS	1
28#import "Foundation/NSCoder.h"
29#import "Foundation/NSData.h"
30#import	"Foundation/NSIndexSet.h"
31#import	"Foundation/NSException.h"
32#import "GSDispatch.h"
33
34#define	GSI_ARRAY_TYPE	NSRange
35
36#define	GSI_ARRAY_NO_RELEASE	1
37#define	GSI_ARRAY_NO_RETAIN	1
38
39#include "GNUstepBase/GSIArray.h"
40
41#define	_array	((GSIArray)(self->_data))
42#define	_other	((GSIArray)(aSet->_data))
43
44#ifdef	SANITY_CHECKS
45static void sanity(GSIArray array)
46{
47  if (array != 0)
48
49    {
50      NSUInteger	c = GSIArrayCount(array);
51      NSUInteger	i;
52      NSUInteger	last = 0;
53
54      for (i = 0; i < c; i++)
55	{
56	  NSRange	r = GSIArrayItemAtIndex(array, i).ext;
57
58	  if (i > 0)
59	    {
60	      NSCAssert(r.location > last, @"Overlap or touching ranges");
61	    }
62	  else
63	    {
64	      NSCAssert(r.location >= last, @"Overlap ranges");
65	    }
66	  NSCAssert(NSMaxRange(r) > r.location, @"Bad range length");
67	  last = NSMaxRange(r);
68	}
69    }
70}
71#define	SANITY()	sanity(_array)
72#else
73#define	SANITY()
74#endif
75
76/*
77 * Returns the position in the array at which the index should be inserted.
78 * This may be the position of a range containing the index if it is already
79 * present, otherwise it is the position of the first range containing an
80 * index greater than the argument (or a position beyond the end of the
81 * array).
82 */
83static NSUInteger posForIndex(GSIArray array, NSUInteger index)
84{
85  NSUInteger	upper = GSIArrayCount(array);
86  NSUInteger	lower = 0;
87  NSUInteger	pos;
88
89  /*
90   *	Binary search for an item equal to the one to be inserted.
91   */
92  for (pos = upper/2; upper != lower; pos = (upper+lower)/2)
93    {
94      NSRange	r = GSIArrayItemAtIndex(array, pos).ext;
95
96      if (index < r.location)
97        {
98          upper = pos;
99        }
100      else if (index > NSMaxRange(r))
101        {
102          lower = pos + 1;
103        }
104      else
105        {
106          break;
107        }
108    }
109  /*
110   * Now skip past any item containing no values as high as the index.
111   */
112  while (pos < GSIArrayCount(array)
113    && index >= NSMaxRange(GSIArrayItemAtIndex(array, pos).ext))
114    {
115      pos++;
116    }
117  return pos;
118}
119
120@implementation	NSIndexSet
121+ (id) indexSet
122{
123  id	o = [self allocWithZone: NSDefaultMallocZone()];
124
125  o = [o init];
126  return AUTORELEASE(o);
127}
128
129+ (id) indexSetWithIndex: (NSUInteger)anIndex
130{
131  id	o = [self allocWithZone: NSDefaultMallocZone()];
132
133  o = [o initWithIndex: anIndex];
134  return AUTORELEASE(o);
135}
136
137+ (id) indexSetWithIndexesInRange: (NSRange)aRange
138{
139  id	o = [self allocWithZone: NSDefaultMallocZone()];
140
141  o = [o initWithIndexesInRange: aRange];
142  return AUTORELEASE(o);
143}
144
145- (BOOL) containsIndex: (NSUInteger)anIndex
146{
147  NSUInteger	pos;
148  NSRange	r;
149
150  if (_array == 0 || GSIArrayCount(_array) == 0
151    || (pos = posForIndex(_array, anIndex)) >= GSIArrayCount(_array))
152    {
153      return NO;
154    }
155  r = GSIArrayItemAtIndex(_array, pos).ext;
156  return NSLocationInRange(anIndex, r);
157}
158
159- (BOOL) containsIndexes: (NSIndexSet*)aSet
160{
161  NSUInteger	count = _other ? GSIArrayCount(_other) : 0;
162
163  if (count > 0)
164    {
165      NSUInteger	i;
166
167      for (i = 0; i < count; i++)
168	{
169	  NSRange	r = GSIArrayItemAtIndex(_other, i).ext;
170
171	  if ([self containsIndexesInRange: r] == NO)
172	    {
173	      return NO;
174	    }
175	}
176    }
177  return YES;
178}
179
180- (BOOL) containsIndexesInRange: (NSRange)aRange
181{
182  NSUInteger	pos;
183  NSRange	r;
184
185  if (NSNotFound - aRange.length < aRange.location)
186    {
187      [NSException raise: NSInvalidArgumentException
188		  format: @"[%@-%@]: Bad range",
189        NSStringFromClass([self class]), NSStringFromSelector(_cmd)];
190    }
191  if (_array == 0 || GSIArrayCount(_array) == 0
192    || (pos = posForIndex(_array, aRange.location)) >= GSIArrayCount(_array))
193    {
194      return NO;	// Empty ... contains no indexes.
195    }
196  if (aRange.length == 0)
197    {
198      return YES;	// No indexes needed.
199    }
200  r = GSIArrayItemAtIndex(_array, pos).ext;
201  if (NSLocationInRange(aRange.location, r)
202    && NSLocationInRange(NSMaxRange(aRange)-1, r))
203    {
204      return YES;
205    }
206  return NO;
207}
208
209- (id) copyWithZone: (NSZone*)aZone
210{
211  if (NSShouldRetainWithZone(self, aZone))
212    {
213      return RETAIN(self);
214    }
215  else
216    {
217      NSIndexSet	*c = [NSIndexSet allocWithZone: aZone];
218
219      return [c initWithIndexSet: self];
220    }
221}
222
223- (NSUInteger) count
224{
225  if (_array == 0 || GSIArrayCount(_array) == 0)
226    {
227      return 0;
228    }
229  else
230    {
231      NSUInteger	count = GSIArrayCount(_array);
232      NSUInteger	total = 0;
233      NSUInteger	i = 0;
234
235      while (i < count)
236	{
237	  total += GSIArrayItemAtIndex(_array, i).ext.length;
238	  i++;
239	}
240      return total;
241    }
242}
243
244- (NSUInteger) countOfIndexesInRange: (NSRange)range
245{
246  if (_array == 0 || GSIArrayCount(_array) == 0)
247    {
248      return 0;
249    }
250  else
251    {
252      NSUInteger	count = GSIArrayCount(_array);
253      NSUInteger	total = 0;
254      NSUInteger	i = 0;
255
256      while (i < count)
257	{
258	  NSRange	r = GSIArrayItemAtIndex(_array, i).ext;
259
260          r = NSIntersectionRange(r, range);
261	  total += r.length;
262	  i++;
263	}
264      return total;
265    }
266}
267
268- (void) dealloc
269{
270  if (_array != 0)
271    {
272      GSIArrayClear(_array);
273      NSZoneFree([self zone], _array);
274      _data = 0;
275    }
276  [super dealloc];
277}
278
279- (NSString*) description
280{
281  NSMutableString	*m;
282  NSUInteger		c = (_array == 0) ? 0 : GSIArrayCount(_array);
283  NSUInteger		i;
284
285  if (c == 0)
286    {
287      return [NSString stringWithFormat: @"%@(no indexes)",
288        [super description]];
289    }
290  m = [NSMutableString stringWithFormat:
291    @"%@[number of indexes: %"PRIuPTR" (in %"PRIuPTR" ranges), indexes:",
292    [super description], [self count], c];
293  for (i = 0; i < c; i++)
294    {
295      NSRange	r = GSIArrayItemAtIndex(_array, i).ext;
296
297      if (r.length > 1)
298        {
299          [m appendFormat: @" (%"PRIuPTR"-%"PRIuPTR")",
300	    r.location, NSMaxRange(r) - 1];
301	}
302      else
303        {
304          [m appendFormat: @" %"PRIuPTR, r.location];
305	}
306    }
307  [m appendString: @"]"];
308  return m;
309}
310
311- (void) encodeWithCoder: (NSCoder*)aCoder
312{
313  NSUInteger rangeCount = 0;
314
315  if (_array != 0)
316    {
317      rangeCount = GSIArrayCount(_array);
318    }
319
320  if ([aCoder allowsKeyedCoding])
321    {
322      [aCoder encodeInt: rangeCount forKey: @"NSRangeCount"];
323    }
324  else
325    {
326      [aCoder encodeValueOfObjCType: @encode(NSUInteger)
327                                 at: &rangeCount];
328    }
329
330  if (rangeCount == 0)
331    {
332      // Do nothing
333    }
334  else if (rangeCount == 1)
335    {
336      NSRange	r;
337
338      r = GSIArrayItemAtIndex(_array, 0).ext;
339      if ([aCoder allowsKeyedCoding])
340        {
341          [aCoder encodeInt: r.location forKey: @"NSLocation"];
342          [aCoder encodeInt: r.length forKey: @"NSLength"];
343        }
344      else
345        {
346          [aCoder encodeValueOfObjCType: @encode(NSUInteger)
347                                     at: &r.location];
348          [aCoder encodeValueOfObjCType: @encode(NSUInteger)
349                                     at: &r.length];
350        }
351    }
352  else
353    {
354      NSMutableData     *m = [NSMutableData dataWithCapacity: rangeCount*2];
355      NSUInteger          i;
356
357      for (i = 0; i < rangeCount; i++)
358        {
359          NSRange	r;
360          NSUInteger    v;
361          uint8_t       b;
362
363          r = GSIArrayItemAtIndex(_array, i).ext;
364          v = r.location;
365          do
366            {
367              if (v > 0x7f)
368                {
369                  b = (v & 0x7f) | 0x80;
370                }
371              else
372                {
373                  b = v;
374                }
375              v >>= 7;
376              [m appendBytes: &b length: 1];
377            }
378          while (v > 0);
379          v = r.length;
380          do
381            {
382              if (v > 0x7f)
383                {
384                  b = (v & 0x7f) | 0x80;
385                }
386              else
387                {
388                  b = v;
389                }
390              v >>= 7;
391              [m appendBytes: &b length: 1];
392            }
393          while (v > 0);
394        }
395      if ([aCoder allowsKeyedCoding])
396        {
397          [aCoder encodeObject: m forKey: @"NSRangeData"];
398        }
399      else
400        {
401          [aCoder encodeObject: m];
402        }
403    }
404}
405
406- (NSUInteger) firstIndex
407{
408  if (_array == 0 || GSIArrayCount(_array) == 0)
409    {
410      return NSNotFound;
411    }
412  return GSIArrayItemAtIndex(_array, 0).ext.location;
413}
414
415- (NSUInteger) getIndexes: (NSUInteger*)aBuffer
416                 maxCount: (NSUInteger)aCount
417             inIndexRange: (NSRangePointer)aRange
418{
419  NSUInteger	pos;
420  NSUInteger	i = 0;
421  NSRange	r;
422  NSRange	fullRange;
423
424  if (aBuffer == 0)
425    {
426      [NSException raise: NSInvalidArgumentException
427		  format: @"[%@-%@]: nul pointer argument",
428        NSStringFromClass([self class]), NSStringFromSelector(_cmd)];
429    }
430  if (aRange == 0)
431    {
432      fullRange = (NSRange){0, NSNotFound};
433      aRange = &fullRange;
434    }
435  else if (NSNotFound - aRange->length < aRange->location)
436    {
437      [NSException raise: NSInvalidArgumentException
438		  format: @"[%@-%@]: Bad range",
439        NSStringFromClass([self class]), NSStringFromSelector(_cmd)];
440    }
441  if (_array == 0 || GSIArrayCount(_array) == 0
442    || (pos = posForIndex(_array, aRange->location)) >= GSIArrayCount(_array))
443    {
444      *aRange = NSMakeRange(NSMaxRange(*aRange), 0);
445      return 0;
446    }
447
448  while (aRange->length > 0 && i < aCount && pos < GSIArrayCount(_array))
449    {
450      r = GSIArrayItemAtIndex(_array, pos).ext;
451      if (aRange->location < r.location)
452	{
453	  NSUInteger	skip = r.location - aRange->location;
454
455	  if (skip > aRange->length)
456	    {
457	      skip = aRange->length;
458	    }
459	  aRange->location += skip;
460	  aRange->length -= skip;
461	}
462      if (NSLocationInRange(aRange->location, r))
463	{
464	  while (aRange->length > 0 && i < aCount
465	    && aRange->location < NSMaxRange(r))
466	    {
467	      aBuffer[i++] = aRange->location++;
468	      aRange->length--;
469	    }
470	}
471      else
472	{
473	}
474      pos++;
475    }
476  return i;
477}
478
479- (NSUInteger) hash
480{
481  return [self count];
482}
483
484- (NSUInteger) indexGreaterThanIndex: (NSUInteger)anIndex
485{
486  NSUInteger	pos;
487  NSRange	r;
488
489  if (anIndex++ == NSNotFound)
490    {
491      return NSNotFound;
492    }
493  if (_array == 0 || GSIArrayCount(_array) == 0
494    || (pos = posForIndex(_array, anIndex)) >= GSIArrayCount(_array))
495    {
496      return NSNotFound;
497    }
498  r = GSIArrayItemAtIndex(_array, pos).ext;
499  if (NSLocationInRange(anIndex, r))
500    {
501      return anIndex;
502    }
503  return r.location;
504}
505
506- (NSUInteger) indexGreaterThanOrEqualToIndex: (NSUInteger)anIndex
507{
508  NSUInteger	pos;
509  NSRange	r;
510
511  if (anIndex == NSNotFound)
512    {
513      return NSNotFound;
514    }
515  if (_array == 0 || GSIArrayCount(_array) == 0
516    || (pos = posForIndex(_array, anIndex)) >= GSIArrayCount(_array))
517    {
518      return NSNotFound;
519    }
520  r = GSIArrayItemAtIndex(_array, pos).ext;
521  if (NSLocationInRange(anIndex, r))
522    {
523      return anIndex;
524    }
525  return r.location;
526}
527
528- (NSUInteger) indexLessThanIndex: (NSUInteger)anIndex
529{
530  NSUInteger	pos;
531  NSRange	r;
532
533  if (anIndex-- == 0)
534    {
535      return NSNotFound;
536    }
537  if (_array == 0 || GSIArrayCount(_array) == 0
538    || (pos = posForIndex(_array, anIndex)) >= GSIArrayCount(_array))
539    {
540      return NSNotFound;
541    }
542  r = GSIArrayItemAtIndex(_array, pos).ext;
543  if (NSLocationInRange(anIndex, r))
544    {
545      return anIndex;
546    }
547  if (pos-- == 0)
548    {
549      return NSNotFound;
550    }
551  r = GSIArrayItemAtIndex(_array, pos).ext;
552  return NSMaxRange(r) - 1;
553}
554
555- (NSUInteger) indexLessThanOrEqualToIndex: (NSUInteger)anIndex
556{
557  NSUInteger	pos;
558  NSRange	r;
559
560  if (_array == 0 || GSIArrayCount(_array) == 0
561    || (pos = posForIndex(_array, anIndex)) >= GSIArrayCount(_array))
562    {
563      return NSNotFound;
564    }
565  r = GSIArrayItemAtIndex(_array, pos).ext;
566  if (NSLocationInRange(anIndex, r))
567    {
568      return anIndex;
569    }
570  if (pos-- == 0)
571    {
572      return NSNotFound;
573    }
574  r = GSIArrayItemAtIndex(_array, pos).ext;
575  return NSMaxRange(r) - 1;
576}
577
578- (id) init
579{
580  return self;
581}
582
583- (id) initWithCoder: (NSCoder*)aCoder
584{
585  NSUInteger rangeCount = 0;
586
587  if ([aCoder allowsKeyedCoding])
588    {
589      if ([aCoder containsValueForKey: @"NSRangeCount"])
590        {
591          rangeCount = [aCoder decodeIntForKey: @"NSRangeCount"];
592        }
593    }
594  else
595    {
596      [aCoder decodeValueOfObjCType: @encode(NSUInteger)
597                                 at: &rangeCount];
598    }
599
600  if (rangeCount == 0)
601    {
602      // Do nothing
603    }
604  else if (rangeCount == 1)
605    {
606      NSUInteger len = 0;
607      NSUInteger loc = 0;
608
609      if ([aCoder allowsKeyedCoding])
610        {
611          if ([aCoder containsValueForKey: @"NSLocation"])
612            {
613              loc = [aCoder decodeIntForKey: @"NSLocation"];
614            }
615          if ([aCoder containsValueForKey: @"NSLength"])
616            {
617              len = [aCoder decodeIntForKey: @"NSLength"];
618            }
619        }
620      else
621        {
622          [aCoder decodeValueOfObjCType: @encode(NSUInteger)
623                                     at: &loc];
624          [aCoder decodeValueOfObjCType: @encode(NSUInteger)
625                                     at: &len];
626        }
627      self = [self initWithIndexesInRange: NSMakeRange(loc, len)];
628    }
629  else
630    {
631      NSMutableIndexSet *other = [NSMutableIndexSet new];
632      NSData            *data = nil;
633      const uint8_t     *bytes;
634      NSUInteger        length;
635      NSUInteger        index = 0;
636
637      if ([aCoder allowsKeyedCoding])
638        {
639          if ([aCoder containsValueForKey: @"NSRangeData"])
640            {
641              data = [aCoder decodeObjectForKey: @"NSRangeData"];
642            }
643        }
644      else
645        {
646          data = [aCoder decodeObject];
647        }
648      bytes = (const uint8_t*)[data bytes];
649      length = [data length];
650      while (index < length)
651        {
652          NSRange       range;
653          NSUInteger    offset;
654          NSUInteger    value;
655          NSUInteger    next;
656
657          for (offset = 0; index + offset < length; offset++)
658            {
659              if (bytes[index + offset] < 0x80)
660                {
661                  break;
662                }
663            }
664          NSAssert(index + offset < length && bytes[index + offset] < 0x80,
665            NSInternalInconsistencyException);
666          next = index + offset + 1;
667          value = bytes[index + offset];
668          while (offset-- > 0)
669            {
670              value <<= 7;
671              value += (bytes[index + offset] & 0x7f);
672            }
673          range.location = value;
674          index  = next;
675          for (offset = 0; index + offset < length; offset++)
676            {
677              if (bytes[index + offset] < 0x80)
678                {
679                  break;
680                }
681            }
682          NSAssert(index + offset < length && bytes[index + offset] < 0x80,
683            NSInternalInconsistencyException);
684          next = index + offset + 1;
685          value = bytes[index + offset];
686          while (offset-- > 0)
687            {
688              value <<= 7;
689              value += (bytes[index + offset] & 0x7f);
690            }
691          range.length = value;
692          index = next;
693          [other addIndexesInRange: range];
694        }
695      self = [self initWithIndexSet: other];
696      RELEASE(other);
697      /*
698        FIXME:
699        NSLog(@"Decoded count %d, data %@", rangeCount, data);
700        This is a very strange format:
701
702        5 + 6 + 9 gives <05020901>
703        5 + 6 + 23 gives <05021701>
704        155 + 156 + 223 gives <9b0102df 0101>
705       */
706    }
707
708  return self;
709}
710
711- (id) initWithIndex: (NSUInteger)anIndex
712{
713  if (anIndex == NSNotFound)
714    {
715      DESTROY(self);	// NSNotFound is not legal
716    }
717  else
718    {
719      self = [self initWithIndexesInRange: NSMakeRange(anIndex, 1)];
720    }
721  return self;
722}
723
724- (id) initWithIndexesInRange: (NSRange)aRange
725{
726  if (aRange.length > 0)
727    {
728      if (NSMaxRange(aRange) == NSNotFound)
729	{
730	  DESTROY(self);	// NSNotFound is not legal
731	}
732      else
733	{
734	  _data = (GSIArray)NSZoneMalloc([self zone], sizeof(GSIArray_t));
735	  GSIArrayInitWithZoneAndCapacity(_array, [self zone], 1);
736	  GSIArrayAddItem(_array, (GSIArrayItem)aRange);
737	}
738    }
739  return self;
740}
741
742- (id) initWithIndexSet: (NSIndexSet*)aSet
743{
744  if (aSet == nil || [aSet isKindOfClass: [NSIndexSet class]] == NO)
745    {
746      DESTROY(self);
747    }
748  else
749    {
750      NSUInteger count = _other ? GSIArrayCount(_other) : 0;
751
752      if (count > 0)
753	{
754	  NSUInteger i;
755
756	  _data = (GSIArray)NSZoneMalloc([self zone], sizeof(GSIArray_t));
757	  GSIArrayInitWithZoneAndCapacity(_array, [self zone], count);
758	  for (i = 0; i < count; i++)
759	    {
760	      GSIArrayAddItem(_array, GSIArrayItemAtIndex(_other, i));
761	    }
762	}
763    }
764  return self;
765}
766
767- (BOOL) intersectsIndexesInRange: (NSRange)aRange
768{
769  NSUInteger	p1;
770  NSUInteger	p2;
771
772  if (NSNotFound - aRange.length < aRange.location)
773    {
774      [NSException raise: NSInvalidArgumentException
775		  format: @"[%@-%@]: Bad range",
776        NSStringFromClass([self class]), NSStringFromSelector(_cmd)];
777    }
778  if (aRange.length == 0 || _array == 0 || GSIArrayCount(_array) == 0)
779    {
780      return NO;	// Empty
781    }
782  p1 = posForIndex(_array, aRange.location);
783  p2 = posForIndex(_array, NSMaxRange(aRange) - 1);
784  if (p1 != p2)
785    {
786      return YES;
787    }
788  if (p1 >= GSIArrayCount(_array))
789    {
790      return NO;
791    }
792  if (NSLocationInRange(aRange.location, GSIArrayItemAtIndex(_array, p1).ext))
793    {
794      return YES;
795    }
796  if (NSLocationInRange(NSMaxRange(aRange)-1,
797      GSIArrayItemAtIndex(_array, p1).ext))
798    {
799      return YES;
800    }
801  return NO;
802}
803
804- (BOOL) isEqual: (id)aSet
805{
806  if ([aSet isKindOfClass: [NSIndexSet class]] == YES)
807    {
808      return [self isEqualToIndexSet: aSet];
809    }
810  return NO;
811}
812
813- (BOOL) isEqualToIndexSet: (NSIndexSet*)aSet
814{
815  NSUInteger	count = _other ? GSIArrayCount(_other) : 0;
816
817  if (count != (_array ? GSIArrayCount(_array) : 0))
818    {
819      return NO;
820    }
821  if (count > 0)
822    {
823      NSUInteger	i;
824
825      for (i = 0; i < count; i++)
826	{
827	  NSRange	rself = GSIArrayItemAtIndex(_array, i).ext;
828	  NSRange	rother = GSIArrayItemAtIndex(_other, i).ext;
829
830	  if (NSEqualRanges(rself, rother) == NO)
831	    {
832	      return NO;
833	    }
834	}
835    }
836  return YES;
837}
838
839- (NSUInteger) lastIndex
840{
841  if (_array == 0 || GSIArrayCount(_array) == 0)
842    {
843      return NSNotFound;
844    }
845  return NSMaxRange(GSIArrayItemAtIndex(_array, GSIArrayCount(_array)-1).ext)-1;
846}
847
848- (id) mutableCopyWithZone: (NSZone*)aZone
849{
850  NSMutableIndexSet	*c = [NSMutableIndexSet allocWithZone: aZone];
851
852  return [c initWithIndexSet: self];
853}
854
855
856- (void) enumerateIndexesInRange: (NSRange)range
857                         options: (NSEnumerationOptions)opts
858		      usingBlock: (GSIndexSetEnumerationBlock)aBlock
859{
860  NSUInteger    lastInRange;
861  NSUInteger    startArrayIndex;
862  NSUInteger    endArrayIndex;
863  NSUInteger    i;
864  NSUInteger    c;
865  BOOL          isReverse = opts & NSEnumerationReverse;
866  BLOCK_SCOPE BOOL      shouldStop = NO;
867
868  if ((0 == [self count]) || (NSNotFound == range.location))
869    {
870      return;
871    }
872
873  startArrayIndex = posForIndex(_array, range.location);
874  if (NSNotFound == startArrayIndex)
875    {
876      startArrayIndex = 0;
877    }
878
879  lastInRange = (NSMaxRange(range) - 1);
880  endArrayIndex = MIN(posForIndex(_array, lastInRange),
881    (GSIArrayCount(_array) - 1));
882  if (NSNotFound == endArrayIndex)
883    {
884      endArrayIndex = GSIArrayCount(_array) - 1;
885    }
886
887  if (isReverse)
888    {
889      i = endArrayIndex;
890      c = startArrayIndex;
891    }
892  else
893    {
894      i = startArrayIndex;
895      c = endArrayIndex;
896    }
897
898  GS_DISPATCH_CREATE_QUEUE_AND_GROUP_FOR_ENUMERATION(enumQueue, opts)
899  while (isReverse ? i >= c : i <= c)
900    {
901      NSRange r = GSIArrayItemAtIndex(_array, i).ext;
902      NSUInteger innerI;
903      NSUInteger innerC;
904
905      if (isReverse)
906        {
907          innerI = NSMaxRange(r) - 1;
908          innerC = r.location;
909        }
910      else
911        {
912          innerI = r.location;
913          innerC = NSMaxRange(r) - 1;
914        }
915      while (isReverse ? innerI >= innerC : innerI <= innerC)
916        {
917          if ((innerI <= lastInRange) && (innerI >= range.location))
918            {
919              GS_DISPATCH_SUBMIT_BLOCK(enumQueueGroup, enumQueue,
920                if (shouldStop == NO) {, },
921                aBlock, innerI, &shouldStop);
922            }
923          if (shouldStop)
924            {
925              break;
926            }
927          if (isReverse)
928            {
929              if (0 == innerI)
930                {
931                  break;
932                }
933              innerI--;
934            }
935          else
936            {
937              innerI++;
938            }
939        }
940
941      if (shouldStop)
942        {
943          break;
944        }
945      if (isReverse)
946        {
947          if (0 == i)
948            {
949              break;
950            }
951          i--;
952        }
953      else
954        {
955          i++;
956        }
957    }
958  GS_DISPATCH_TEARDOWN_QUEUE_AND_GROUP_FOR_ENUMERATION(enumQueue, opts)
959
960}
961
962- (void) enumerateIndexesWithOptions: (NSEnumerationOptions)opts
963		          usingBlock: (GSIndexSetEnumerationBlock)aBlock
964{
965  NSUInteger    firstIndex;
966  NSUInteger    lastIndex;
967  NSRange       range;
968
969  firstIndex = [self firstIndex];
970  if (NSNotFound == firstIndex)
971    {
972      return;
973    }
974
975  lastIndex = [self lastIndex];
976  range = NSMakeRange(firstIndex, ((lastIndex - firstIndex) + 1));
977
978  [self enumerateIndexesInRange: range
979                        options: opts
980                     usingBlock: aBlock];
981}
982
983- (void) enumerateIndexesUsingBlock: (GSIndexSetEnumerationBlock)aBlock
984{
985  [self enumerateIndexesWithOptions: 0
986                         usingBlock: aBlock];
987}
988@end
989
990
991@implementation	NSMutableIndexSet
992
993#undef	_other
994#define	_other	((GSIArray)(((NSMutableIndexSet*)aSet)->_data))
995
996- (void) addIndex: (NSUInteger)anIndex
997{
998  [self addIndexesInRange: NSMakeRange(anIndex, 1)];
999}
1000
1001- (void) addIndexes: (NSIndexSet*)aSet
1002{
1003  NSUInteger	count = _other ? GSIArrayCount(_other) : 0;
1004
1005  if (count > 0)
1006    {
1007      NSUInteger	i;
1008
1009      for (i = 0; i < count; i++)
1010	{
1011	  NSRange	r = GSIArrayItemAtIndex(_other, i).ext;
1012
1013	  [self addIndexesInRange: r];
1014	}
1015    }
1016}
1017
1018- (void) addIndexesInRange: (NSRange)aRange
1019{
1020  NSUInteger	pos;
1021
1022  if (NSNotFound - aRange.length < aRange.location)
1023    {
1024      [NSException raise: NSInvalidArgumentException
1025		  format: @"[%@-%@]: Bad range",
1026        NSStringFromClass([self class]), NSStringFromSelector(_cmd)];
1027    }
1028  if (aRange.length == 0)
1029    {
1030      return;
1031    }
1032  if (_array == 0)
1033    {
1034      _data = (GSIArray)NSZoneMalloc([self zone], sizeof(GSIArray_t));
1035      GSIArrayInitWithZoneAndCapacity(_array, [self zone], 1);
1036    }
1037
1038  pos = posForIndex(_array, aRange.location);
1039  if (pos >= GSIArrayCount(_array))
1040    {
1041      /*
1042       * The start of the range to add lies beyond the existing
1043       * ranges, so we can simply append it.
1044       */
1045      GSIArrayAddItem(_array, (GSIArrayItem)aRange);
1046    }
1047  else
1048    {
1049      NSRange	r = GSIArrayItemAtIndex(_array, pos).ext;
1050
1051      if (NSLocationInRange(aRange.location, r))
1052	{
1053	  pos++;
1054	}
1055      GSIArrayInsertItem(_array, (GSIArrayItem)aRange, pos);
1056    }
1057
1058  /*
1059   * Combine with the preceding ranges if possible.
1060   */
1061  while (pos > 0)
1062    {
1063      NSRange	r = GSIArrayItemAtIndex(_array, pos-1).ext;
1064
1065      if (NSMaxRange(r) < aRange.location)
1066	{
1067	  break;
1068	}
1069      if (NSMaxRange(r) >= NSMaxRange(aRange))
1070        {
1071          GSIArrayRemoveItemAtIndex(_array, pos--);
1072	}
1073      else
1074        {
1075          r.length += (NSMaxRange(aRange) - NSMaxRange(r));
1076          GSIArrayRemoveItemAtIndex(_array, pos--);
1077          GSIArraySetItemAtIndex(_array, (GSIArrayItem)r, pos);
1078	}
1079    }
1080
1081  /*
1082   * Combine with any following ranges where possible.
1083   */
1084  while (pos + 1 < GSIArrayCount(_array))
1085    {
1086      NSRange	r = GSIArrayItemAtIndex(_array, pos+1).ext;
1087
1088      if (NSMaxRange(aRange) < r.location)
1089	{
1090	  break;
1091	}
1092      GSIArrayRemoveItemAtIndex(_array, pos + 1);
1093      if (NSMaxRange(r) > NSMaxRange(aRange))
1094	{
1095	  int	offset = NSMaxRange(r) - NSMaxRange(aRange);
1096
1097	  r = GSIArrayItemAtIndex(_array, pos).ext;
1098	  r.length += offset;
1099	  GSIArraySetItemAtIndex(_array, (GSIArrayItem)r, pos);
1100	}
1101    }
1102  SANITY();
1103}
1104
1105- (id) copyWithZone: (NSZone*)aZone
1106{
1107  NSIndexSet	*c = [NSIndexSet allocWithZone: aZone];
1108
1109  return [c initWithIndexSet: self];
1110}
1111
1112- (void) removeAllIndexes
1113{
1114  if (_array != 0)
1115    {
1116      GSIArrayRemoveAllItems(_array);
1117    }
1118}
1119
1120- (void) removeIndex: (NSUInteger)anIndex
1121{
1122  [self removeIndexesInRange: NSMakeRange(anIndex, 1)];
1123}
1124
1125- (void) removeIndexes: (NSIndexSet*)aSet
1126{
1127  NSUInteger	count = _other ? GSIArrayCount(_other) : 0;
1128
1129  if (count > 0)
1130    {
1131      NSUInteger	i;
1132
1133      for (i = 0; i < count; i++)
1134	{
1135	  NSRange	r = GSIArrayItemAtIndex(_other, i).ext;
1136
1137	  [self removeIndexesInRange: r];
1138	}
1139    }
1140}
1141
1142- (void) removeIndexesInRange: (NSRange)aRange
1143{
1144  NSUInteger	pos;
1145  NSRange	r;
1146
1147  if (NSNotFound - aRange.length < aRange.location)
1148    {
1149      [NSException raise: NSInvalidArgumentException
1150		  format: @"[%@-%@]: Bad range",
1151        NSStringFromClass([self class]), NSStringFromSelector(_cmd)];
1152    }
1153  if (aRange.length == 0 || _array == 0
1154    || (pos = posForIndex(_array, aRange.location)) >= GSIArrayCount(_array))
1155    {
1156      return;	// Already empty
1157    }
1158
1159  r = GSIArrayItemAtIndex(_array, pos).ext;
1160  if (r.location <= aRange.location)
1161    {
1162      if (r.location == aRange.location)
1163        {
1164   	  if (NSMaxRange(r) <= NSMaxRange(aRange))
1165	    {
1166	      /*
1167	       * Found range is entirely within range to remove,
1168	       * leaving next range to check at current position.
1169	       */
1170	      GSIArrayRemoveItemAtIndex(_array, pos);
1171	    }
1172	  else
1173	    {
1174	      /*
1175	       * Range to remove is entirely within found range and
1176	       * overlaps the start of the found range ... shrink it
1177	       * and then we are finished.
1178	       */
1179	      r.location += aRange.length;
1180	      r.length -= aRange.length;
1181	      GSIArraySetItemAtIndex(_array, (GSIArrayItem)r, pos);
1182	      pos++;
1183	    }
1184	}
1185      else
1186	{
1187   	  if (NSMaxRange(r) <= NSMaxRange(aRange))
1188	    {
1189	      /*
1190	       * Range to remove overlaps the end of the found range.
1191	       * May also overlap next range ... so shorten found
1192	       * range and move on.
1193	       */
1194	      r.length = aRange.location - r.location;
1195	      GSIArraySetItemAtIndex(_array, (GSIArrayItem)r, pos);
1196	      pos++;
1197	    }
1198	  else
1199	    {
1200	      NSRange	next = r;
1201
1202	      /*
1203	       * Range to remove is entirely within found range and
1204	       * overlaps the middle of the found range ... split it.
1205	       * Then we are finished.
1206	       */
1207	      next.location = NSMaxRange(aRange);
1208	      next.length = NSMaxRange(r) - next.location;
1209	      r.length = aRange.location - r.location;
1210	      GSIArraySetItemAtIndex(_array, (GSIArrayItem)r, pos);
1211	      pos++;
1212	      GSIArrayInsertItem(_array, (GSIArrayItem)next, pos);
1213	      pos++;
1214	    }
1215	}
1216    }
1217
1218  /*
1219   * At this point we are guaranteed that, if there is a range at pos,
1220   * it does not start before aRange.location
1221   */
1222  while (pos < GSIArrayCount(_array))
1223    {
1224      NSRange	r = GSIArrayItemAtIndex(_array, pos).ext;
1225
1226      if (NSMaxRange(r) <= NSMaxRange(aRange))
1227	{
1228	  /*
1229	   * Found range is entirely within range to remove ...
1230	   * delete it.
1231	   */
1232	  GSIArrayRemoveItemAtIndex(_array, pos);
1233	}
1234      else
1235	{
1236	  if (r.location < NSMaxRange(aRange))
1237	    {
1238	      /*
1239	       * Range to remove overlaps start of found range ...
1240	       * shorten it.
1241	       */
1242	      r.length = NSMaxRange(r) - NSMaxRange(aRange);
1243	      r.location = NSMaxRange(aRange);
1244	      GSIArraySetItemAtIndex(_array, (GSIArrayItem)r, pos);
1245	    }
1246	  /*
1247	   * Found range extends beyond range to remove ... finished.
1248	   */
1249	  break;
1250	}
1251    }
1252  SANITY();
1253}
1254
1255- (void) shiftIndexesStartingAtIndex: (NSUInteger)anIndex by: (NSInteger)amount
1256{
1257  if (amount != 0 && _array != 0 && GSIArrayCount(_array) > 0)
1258    {
1259      NSUInteger	c;
1260      NSUInteger	pos;
1261
1262      if (amount > 0)
1263	{
1264	  c = GSIArrayCount(_array);
1265	  pos = posForIndex(_array, anIndex);
1266
1267	  if (pos < c)
1268	    {
1269	      NSRange	r = GSIArrayItemAtIndex(_array, pos).ext;
1270
1271	      /*
1272	       * If anIndex is within an existing range, we split
1273	       * that range so we have one starting at anIndex.
1274	       */
1275	      if (r.location < anIndex)
1276		{
1277		  NSRange	t;
1278
1279		  /*
1280		   * Split the range.
1281		   */
1282		  t = NSMakeRange(r.location, anIndex - r.location);
1283		  GSIArrayInsertItem(_array, (GSIArrayItem)t, pos);
1284		  c++;
1285		  r.length = NSMaxRange(r) - anIndex;
1286		  r.location = anIndex;
1287		  GSIArraySetItemAtIndex(_array, (GSIArrayItem)r, ++pos);
1288		}
1289
1290	      /*
1291	       * Shift all higher ranges to the right.
1292	       */
1293	      while (c > pos)
1294		{
1295		  NSRange	r = GSIArrayItemAtIndex(_array, --c).ext;
1296
1297		  if (NSNotFound - amount <= r.location)
1298		    {
1299		      GSIArrayRemoveItemAtIndex(_array, c);
1300		    }
1301		  else if (NSNotFound - amount < NSMaxRange(r))
1302		    {
1303		      r.location += amount;
1304		      r.length = NSNotFound - r.location;
1305		      GSIArraySetItemAtIndex(_array, (GSIArrayItem)r, c);
1306		    }
1307		  else
1308		    {
1309		      r.location += amount;
1310		      GSIArraySetItemAtIndex(_array, (GSIArrayItem)r, c);
1311		    }
1312		}
1313	    }
1314	}
1315      else
1316	{
1317	  amount = -amount;
1318
1319	  /*
1320	   * Delete range which will be overwritten.
1321	   */
1322	  if (amount >= anIndex)
1323	    {
1324	      [self removeIndexesInRange: NSMakeRange(0, anIndex)];
1325	    }
1326	  else
1327	    {
1328	      [self removeIndexesInRange:
1329		NSMakeRange(anIndex - amount, amount)];
1330	    }
1331	  pos = posForIndex(_array, anIndex);
1332
1333	  /*
1334	   * Now shift everything left into the hole we made.
1335	   */
1336	  c = GSIArrayCount(_array);
1337	  while (c > pos)
1338	    {
1339	      NSRange	r = GSIArrayItemAtIndex(_array, --c).ext;
1340
1341	      if (NSMaxRange(r) <= amount)
1342		{
1343		  GSIArrayRemoveItemAtIndex(_array, c);
1344		}
1345	      else if (r.location <= amount)
1346		{
1347		  r.length += (r.location - amount);
1348		  r.location = 0;
1349		  GSIArraySetItemAtIndex(_array, (GSIArrayItem)r, c);
1350		}
1351	      else
1352		{
1353		  r.location -= amount;
1354		  GSIArraySetItemAtIndex(_array, (GSIArrayItem)r, c);
1355		}
1356	    }
1357	  if (pos > 0)
1358	    {
1359	      c = GSIArrayCount(_array);
1360	      if (pos < c)
1361		{
1362		  NSRange	r0 = GSIArrayItemAtIndex(_array, pos - 1).ext;
1363		  NSRange	r1 = GSIArrayItemAtIndex(_array, pos).ext;
1364
1365	          if (NSMaxRange(r0) == r1.location)
1366		    {
1367		      r0.length += r1.length;
1368		      GSIArraySetItemAtIndex(_array, (GSIArrayItem)r0, pos - 1);
1369		      GSIArrayRemoveItemAtIndex(_array, pos);
1370		    }
1371		}
1372	    }
1373	}
1374    }
1375  SANITY();
1376}
1377
1378@end
1379
1380@implementation	NSIndexSet (NSCharacterSet)
1381/* Extra method to let NSCharacterSet play with index sets more efficiently.
1382 */
1383- (NSUInteger) _gapGreaterThanIndex: (NSUInteger)anIndex
1384{
1385  NSUInteger	pos;
1386  NSRange	r;
1387
1388  if (anIndex++ == NSNotFound)
1389    {
1390      return NSNotFound;
1391    }
1392  if (_array == 0 || GSIArrayCount(_array) == 0)
1393    {
1394      return NSNotFound;
1395    }
1396
1397  if ((pos = posForIndex(_array, anIndex)) >= GSIArrayCount(_array))
1398    {
1399      r = GSIArrayItemAtIndex(_array, pos-1).ext;
1400      if (anIndex > NSMaxRange(r))
1401        {
1402          return NSNotFound;
1403	}
1404      return anIndex;	// anIndex is the gap after the last index.
1405    }
1406  r = GSIArrayItemAtIndex(_array, pos).ext;
1407  if (r.location > anIndex)
1408    {
1409      return anIndex;	// anIndex is in a gap between index ranges.
1410    }
1411  return NSMaxRange(r);	// Return start of gap after the index range.
1412}
1413
1414@end
1415
1416/* A subclass used to access a pre-generated table of information on the
1417 * stack or in other non-heap allocated memory.
1418 */
1419@interface	_GSStaticIndexSet : NSIndexSet
1420@end
1421
1422@implementation	_GSStaticIndexSet
1423- (void) dealloc
1424{
1425  if (_array != 0)
1426    {
1427      /* Free the array without freeing its static content.
1428       */
1429      NSZoneFree([self zone], _array);
1430      _data = 0;
1431    }
1432  [super dealloc];
1433}
1434
1435- (id) _initWithBytes: (const void*)bytes length: (NSUInteger)length
1436{
1437  NSAssert(length % sizeof(GSIArrayItem) == 0, NSInvalidArgumentException);
1438  NSAssert(length % __alignof__(GSIArrayItem) == 0, NSInvalidArgumentException);
1439  length /= sizeof(NSRange);
1440  _data = NSZoneMalloc([self zone], sizeof(GSIArray_t));
1441  _array->ptr = (GSIArrayItem*)bytes;
1442  _array->count = length;
1443  _array->cap = length;
1444  _array->old = length;
1445  _array->zone = 0;
1446  return self;
1447}
1448
1449- (id) init
1450{
1451  return [self _initWithBytes: 0 length: 0];
1452}
1453@end
1454
1455