1  //
   2  //  NSOrderedSet.m
   3  //  CoreFoundation
   4  //
   5  //  Copyright (c) 2014 Apportable. All rights reserved.
   6  //
   7  
   8  #import <Foundation/NSOrderedSet.h>
   9  
  10  #import <Foundation/NSArray.h>
  11  #import <Foundation/NSEnumerator.h>
  12  #import <Foundation/NSSet.h>
  13  #import <Foundation/NSIndexSet.h>
  14  #import <Foundation/NSLocale.h>
  15  
  16  #import <objc/message.h>
  17  
  18  #import "CFBasicHash.h"
  19  #import "ForFoundationOnly.h"
  20  
  21  #import "CFSortFunctions.h"
  22  #import "NSBasicHash.h"
  23  #import "NSFastEnumerationEnumerator.h"
  24  #import "NSObjectInternal.h"
  25  
  26  @interface __NSPlaceholderOrderedSet : NSMutableOrderedSet
  27  + (id)mutablePlaceholder;
  28  + (id)immutablePlaceholder;
  29  @end
  30  
  31  @interface __NSOrderedSetI : NSOrderedSet {
  32      unsigned int _used:26;
  33      unsigned int _szidx:6;
  34  }
  35  + (id)__new:(const id *)addr :(NSUInteger)count :(BOOL)tbd;
  36  @end
  37  
  38  @interface __NSOrderedSetM : NSMutableOrderedSet
  39  {
  40      NSUInteger _used;
  41      CFBasicHashRef _set;
  42      NSMutableArray *_array;
  43  }
  44  + (id)__new:(const id *)addr :(NSUInteger)count :(BOOL)tbd;
  45  @end
  46  
  47  @interface __NSOrderedSetArrayProxy : NSArray
  48  {
  49      NSOrderedSet *_orderedSet;
  50  }
  51  - (id)initWithOrderedSet:(NSOrderedSet *)orderedSet;
  52  @end
  53  
  54  @interface __NSOrderedSetSetProxy : NSSet
  55  {
  56      NSOrderedSet *_orderedSet;
  57  }
  58  - (id)initWithOrderedSet:(NSOrderedSet *)orderedSet;
  59  @end
  60  
  61  @interface __NSOrderedSetReversed : NSOrderedSet
  62  {
  63      NSOrderedSet *_orderedSet;
  64      NSUInteger _cnt;
  65  }
  66  @end
  67  
  68  @interface __NSOrderedSetReverseEnumerator : NSEnumerator
  69  {
  70      NSOrderedSet *_obj;
  71      NSUInteger _idx;
  72  }
  73  - (id)initWithObject:(id)object;
  74  @end
  75  
  76  @interface NSMutableArray ()
  77  - (void)_mutate;
  78  @end
  79  
  80  @interface NSSet ()
  81  - (void)getObjects:(id *)objects count:(NSUInteger)count;
  82  @end
  83  
  84  #define STACK_BUFFER_SIZE 256
  85  
  86  @implementation NSOrderedSet
  87  
  88  + (id)allocWithZone:(NSZone *)zone
  89  {
  90      if (self == [NSOrderedSet class])
  91      {
  92          return [__NSPlaceholderOrderedSet immutablePlaceholder];
  93      }
  94      else if (self == [NSMutableOrderedSet class])
  95      {
  96          return [__NSPlaceholderOrderedSet mutablePlaceholder];
  97      }
  98      else
  99      {
 100          return [super allocWithZone:zone];
 101      }
 102  }
 103  
 104  + (BOOL)supportsSecureCoding
 105  {
 106      return YES;
 107  }
 108  
 109  + (id)orderedSet
 110  {
 111      return [[[self alloc] initWithObjects:NULL count:0] autorelease];
 112  }
 113  
 114  + (id)orderedSetWithObject:(id)object
 115  {
 116      return [[[self alloc] initWithObjects:&object count:1] autorelease];
 117  }
 118  
 119  + (id)orderedSetWithObjects:(const id [])objects count:(NSUInteger)count
 120  {
 121      return [[[self alloc] initWithObjects:objects count:count] autorelease];
 122  }
 123  
 124  + (id)orderedSetWithObjects:(id)firstObj, ... NS_REQUIRES_NIL_TERMINATION
 125  {
 126      NSUInteger argCount = 1;
 127  
 128      va_list args;
 129      va_list copy;
 130  
 131      va_start(args, firstObj);
 132      va_copy(copy, args);
 133  
 134      while (va_arg(args, id) != nil)
 135      {
 136          argCount++;
 137      }
 138  
 139      va_end(args);
 140  
 141      id *objects = malloc(argCount * sizeof(id));
 142  
 143      if (objects == NULL)
 144      {
 145          [NSException raise:NSMallocException format:@"Could not allocate buffer"];
 146          return nil;
 147      }
 148  
 149      objects[0] = firstObj;
 150  
 151      for (NSUInteger idx = 1; idx < argCount; idx++)
 152      {
 153          objects[idx] = va_arg(copy, id);
 154      }
 155  
 156      va_end(copy);
 157  
 158      NSOrderedSet *orderedSet = [[[self alloc] initWithObjects:objects count:argCount] autorelease];
 159  
 160      free(objects);
 161  
 162      return orderedSet;
 163  }
 164  
 165  + (id)orderedSetWithOrderedSet:(NSOrderedSet *)orderedSet
 166  {
 167      NSRange range = NSMakeRange(0, [orderedSet count]);
 168      return [[[self alloc] initWithOrderedSet:orderedSet range:range copyItems:NO] autorelease];
 169  }
 170  
 171  + (id)orderedSetWithOrderedSet:(NSOrderedSet *)orderedSet range:(NSRange)range copyItems:(BOOL)copyItems
 172  {
 173      return [[[self alloc] initWithOrderedSet:orderedSet range:range copyItems:copyItems] autorelease];
 174  }
 175  
 176  + (id)orderedSetWithArray:(NSArray *)array
 177  {
 178      NSRange range = NSMakeRange(0, [array count]);
 179      return [[[self alloc] initWithArray:array range:range copyItems:NO] autorelease];
 180  }
 181  
 182  + (id)orderedSetWithArray:(NSArray *)array range:(NSRange)range copyItems:(BOOL)copyItems
 183  {
 184      return [[[self alloc] initWithArray:array range:range copyItems:copyItems] autorelease];
 185  }
 186  
 187  + (id)orderedSetWithSet:(NSSet *)set
 188  {
 189      return [[[self alloc] initWithSet:set copyItems:NO] autorelease];
 190  }
 191  
 192  + (id)orderedSetWithSet:(NSSet *)set copyItems:(BOOL)copyItems
 193  {
 194      return [[[self alloc] initWithSet:set copyItems:copyItems] autorelease];
 195  }
 196  
 197  + (id)orderedSetWithOrderedSet:(NSOrderedSet *)orderedSet copyItems:(BOOL)copyItems
 198  {
 199      return [[[self alloc] initWithOrderedSet:orderedSet copyItems:copyItems] autorelease];
 200  }
 201  
 202  + (id)orderedSetWithOrderedSet:(NSOrderedSet *)orderedSet range:(NSRange)range
 203  {
 204      return [[[self alloc] initWithOrderedSet:orderedSet range:range copyItems:NO] autorelease];
 205  }
 206  
 207  + (id)orderedSetWithArray:(NSArray *)array copyItems:(BOOL)copyItems
 208  {
 209      return [[[self alloc] initWithArray:array copyItems:copyItems] autorelease];
 210  }
 211  
 212  + (id)orderedSetWithArray:(NSArray *)array range:(NSRange)range
 213  {
 214      return [[[self alloc] initWithArray:array range:range copyItems:NO] autorelease];
 215  }
 216  
 217  + (id)newOrderedSetWithObjects:(const id *)objects count:(NSUInteger)count
 218  {
 219      if (self == [__NSOrderedSetI class])
 220      {
 221          return [[__NSOrderedSetI class] __new:objects :count :NO];
 222      }
 223  
 224      if (self == [__NSOrderedSetM class])
 225      {
 226          return [[__NSOrderedSetM class] __new:objects :count :NO];
 227      }
 228  
 229      NSRequestConcreteImplementation();
 230      return nil;
 231  }
 232  
 233  - (id)initWithObject:(id)object
 234  {
 235      return [self initWithObjects:&object count:1];
 236  }
 237  
 238  - (id)initWithObjects:(const id [])objects count:(NSUInteger)count
 239  {
 240      NSRequestConcreteImplementation();
 241      return nil;
 242  }
 243  
 244  - (id)initWithObjects:(id)firstObj, ... NS_REQUIRES_NIL_TERMINATION
 245  {
 246      NSUInteger argCount = 1;
 247  
 248      va_list args;
 249      va_list copy;
 250  
 251      va_start(args, firstObj);
 252      va_copy(copy, args);
 253  
 254      while (va_arg(args, id) != nil)
 255      {
 256          argCount++;
 257      }
 258  
 259      va_end(args);
 260  
 261      id *objects = malloc(argCount * sizeof(id));
 262  
 263      if (objects == NULL)
 264      {
 265          [NSException raise:NSMallocException format:@"Could not allocate buffer"];
 266          return nil;
 267      }
 268  
 269      objects[0] = firstObj;
 270  
 271      for (NSUInteger idx = 1; idx < argCount; idx++)
 272      {
 273          objects[idx] = va_arg(copy, id);
 274      }
 275  
 276      va_end(copy);
 277  
 278      self = [self initWithObjects:objects count:argCount];
 279  
 280      free(objects);
 281  
 282      return self;
 283  }
 284  
 285  - (id)initWithOrderedSet:(NSOrderedSet *)orderedSet
 286  {
 287      NSRange range = NSMakeRange(0, [orderedSet count]);
 288      return [self initWithOrderedSet:orderedSet range:range copyItems:NO];
 289  }
 290  
 291  - (id)initWithOrderedSet:(NSOrderedSet *)orderedSet copyItems:(BOOL)copyItems
 292  {
 293      NSRange range = NSMakeRange(0, [orderedSet count]);
 294      return [self initWithOrderedSet:orderedSet range:range copyItems:copyItems];
 295  }
 296  
 297  - (id)initWithOrderedSet:(NSOrderedSet *)orderedSet range:(NSRange)range
 298  {
 299      return [self initWithOrderedSet:orderedSet range:range copyItems:NO];
 300  }
 301  
 302  - (id)initWithOrderedSet:(NSOrderedSet *)orderedSet range:(NSRange)range copyItems:(BOOL)copyItems
 303  {
 304      if (NSMaxRange(range) > [orderedSet count])
 305      {
 306          [self release];
 307          [NSException raise:NSRangeException format:@"Range out of bounds for ordered set"];
 308          return nil;
 309      }
 310  
 311      if (orderedSet == nil && range.length > 0)
 312      {
 313          [self release];
 314          [NSException raise:NSInvalidArgumentException format:@"Cannot init ordered set with nonzero range and nil ordered set"];
 315          return nil;
 316      }
 317  
 318      if (range.length == 0)
 319      {
 320          return [self initWithObjects:NULL count:0];
 321      }
 322  
 323      id *objects = malloc(range.length * sizeof(id));
 324      if (objects == NULL)
 325      {
 326          [self release];
 327          [NSException raise:NSMallocException format:@"Failed to allocate buffer"];
 328          return nil;
 329      }
 330  
 331      [orderedSet getObjects:objects range:range];
 332  
 333      if (copyItems)
 334      {
 335          for (NSUInteger idx = 0; idx < range.length; idx++)
 336          {
 337              objects[idx] = [objects[idx] copy];
 338          }
 339      }
 340  
 341      self = [self initWithObjects:objects count:range.length];
 342  
 343      if (copyItems)
 344      {
 345          for (NSUInteger idx = 0; idx < range.length; idx++)
 346          {
 347              [objects[idx] release];
 348          }
 349      }
 350  
 351      free(objects);
 352  
 353      return self;
 354  }
 355  
 356  - (id)initWithArray:(NSArray *)array
 357  {
 358      NSRange range = NSMakeRange(0, [array count]);
 359      return [self initWithArray:array range:range copyItems:NO];
 360  }
 361  
 362  - (id)initWithArray:(NSArray *)array copyItems:(BOOL)copyItems
 363  {
 364      NSRange range = NSMakeRange(0, [array count]);
 365      return [self initWithArray:array range:range copyItems:copyItems];
 366  }
 367  
 368  - (id)initWithArray:(NSArray *)array range:(NSRange)range
 369  {
 370      return [self initWithArray:array range:range copyItems:NO];
 371  }
 372  
 373  - (id)initWithArray:(NSArray *)array range:(NSRange)range copyItems:(BOOL)copyItems
 374  {
 375      if (NSMaxRange(range) > [array count])
 376      {
 377          [self release];
 378          [NSException raise:NSRangeException format:@"Range out of bounds for ordered set"];
 379          return nil;
 380      }
 381  
 382      if (array == nil && range.length > 0)
 383      {
 384          [self release];
 385          [NSException raise:NSInvalidArgumentException format:@"Cannot init ordered set with nonzero range and nil ordered set"];
 386          return nil;
 387      }
 388  
 389      if (range.length == 0)
 390      {
 391          return [self initWithObjects:NULL count:0];
 392      }
 393  
 394      id *objects = malloc(range.length * sizeof(id));
 395  
 396      if (objects == NULL)
 397      {
 398          [self release];
 399          [NSException raise:NSMallocException format:@"Failed to allocate buffer"];
 400          return nil;
 401      }
 402  
 403      [array getObjects:objects range:range];
 404  
 405      if (copyItems)
 406      {
 407          for (NSUInteger idx = 0; idx < range.length; idx++)
 408          {
 409              objects[idx] = [objects[idx] copy];
 410          }
 411      }
 412  
 413      self = [self initWithObjects:objects count:range.length];
 414  
 415      if (copyItems)
 416      {
 417          for (NSUInteger idx = 0; idx < range.length; idx++)
 418          {
 419              [objects[idx] release];
 420          }
 421      }
 422  
 423      free(objects);
 424  
 425      return self;
 426  }
 427  
 428  - (id)initWithSet:(NSSet *)set
 429  {
 430      return [self initWithSet:set copyItems:NO];
 431  }
 432  
 433  - (id)initWithSet:(NSSet *)set copyItems:(BOOL)copyItems
 434  {
 435      if (set == nil)
 436      {
 437          return [self initWithObjects:NULL count:0];
 438      }
 439  
 440      NSUInteger count = [set count];
 441  
 442      if (count == 0)
 443      {
 444          return [self initWithObjects:NULL count:0];
 445      }
 446  
 447      id *objects = malloc(count * sizeof(id));
 448  
 449      if (objects == NULL)
 450      {
 451          [self release];
 452          [NSException raise:NSMallocException format:@"Failed to allocate buffer"];
 453          return nil;
 454      }
 455  
 456      [set getObjects:objects count:count];
 457  
 458      if (copyItems)
 459      {
 460          for (NSUInteger idx = 0; idx < count; idx++)
 461          {
 462              objects[idx] = [objects[idx] copy];
 463          }
 464      }
 465  
 466      self = [self initWithObjects:objects count:count];
 467  
 468      if (copyItems)
 469      {
 470          for (NSUInteger idx = 0; idx < count; idx++)
 471          {
 472              [objects[idx] release];
 473          }
 474      }
 475  
 476      free(objects);
 477  
 478      return self;
 479  }
 480  
 481  - (NSUInteger)count
 482  {
 483      NSRequestConcreteImplementation();
 484      return 0;
 485  }
 486  
 487  - (id)objectAtIndex:(NSUInteger)idx
 488  {
 489      NSRequestConcreteImplementation();
 490      return nil;
 491  }
 492  
 493  - (NSUInteger)indexOfObject:(id)object
 494  {
 495      NSRequestConcreteImplementation();
 496      return 0;
 497  }
 498  
 499  - (Class)classForCoder
 500  {
 501      return [NSOrderedSet class];
 502  }
 503  
 504  - (id)initWithCoder:(NSCoder *)decoder
 505  {
 506      if (![decoder allowsKeyedCoding])
 507      {
 508          [self release];
 509          [NSException raise:NSInvalidArgumentException format:@"Cannot init ordered set with non keyed coder"];
 510          return nil;
 511      }
 512  
 513      NSUInteger capacity = 256;
 514      id *objects = malloc(capacity * sizeof(id));
 515  
 516      if (objects == NULL)
 517      {
 518          [self release];
 519          [NSException raise:NSMallocException format:@"Could not allocate buffer"];
 520          return nil;
 521      }
 522  
 523      unsigned int idx = 0;
 524  
 525      while (YES)
 526      {
 527          if (idx == capacity)
 528          {
 529              capacity *= 2;
 530              id *newObjects = realloc(objects, capacity * sizeof(id));
 531  
 532              if (newObjects == NULL)
 533              {
 534                  for (unsigned int i = 0; i < idx; i++)
 535                  {
 536                      [objects[i] release];
 537                  }
 538  
 539                  free(objects);
 540                  [self release];
 541                  [NSException raise:NSMallocException format:@"Could not allocate buffer"];
 542                  return nil;
 543              }
 544  
 545              objects = newObjects;
 546          }
 547  
 548          CFStringRef key = CFStringCreateWithFormat(kCFAllocatorDefault, NULL, CFSTR("NS.object.%u"), idx);
 549          id obj = [decoder decodeObjectForKey:(NSString *)key];
 550          CFRelease(key);
 551  
 552          if (obj == nil)
 553          {
 554              break;
 555          }
 556  
 557          objects[idx] = obj;
 558          idx++;
 559      };
 560  
 561      [self initWithObjects:objects count:idx];
 562  
 563      free(objects);
 564  
 565      return self;
 566  }
 567  
 568  - (void)encodeWithCoder:(NSCoder *)coder
 569  {
 570      if (![coder allowsKeyedCoding])
 571      {
 572          [NSException raise:NSInvalidArgumentException format:@"Cannot encode ordered set with non keyed coder"];
 573          return;
 574      }
 575  
 576      unsigned int idx = 0;
 577  
 578      for (id object in self)
 579      {
 580          CFStringRef key = CFStringCreateWithFormat(kCFAllocatorDefault, NULL, CFSTR("NS.object.%u"), idx);
 581          [coder encodeObject:object forKey:(NSString *)key];
 582          CFRelease(key);
 583          idx++;
 584      }
 585  }
 586  
 587  - (id)mutableCopyWithZone:(NSZone *)zone
 588  {
 589      NSRange range = NSMakeRange(0, [self count]);
 590      return [[NSMutableOrderedSet alloc] initWithOrderedSet:self range:range copyItems:NO];
 591  }
 592  
 593  - (id)copyWithZone:(NSZone *)zone
 594  {
 595      NSRange range = NSMakeRange(0, [self count]);
 596      return [[NSOrderedSet alloc] initWithOrderedSet:self range:range copyItems:NO];
 597  }
 598  
 599  - (id)objectsPassingTest:(BOOL (^)(id obj, NSUInteger idx, BOOL *stop))test
 600  {
 601      if (test == nil)
 602      {
 603          [NSException raise:NSInvalidArgumentException format:@"Nil test"];
 604          return nil;
 605      }
 606  
 607      NSIndexSet *passingIndexes = [self indexesOfObjectsPassingTest:test];
 608      NSArray *objects = [self objectsAtIndexes:passingIndexes];
 609  
 610      return [NSOrderedSet orderedSetWithArray:objects];
 611  }
 612  
 613  - (id)objectsWithOptions:(NSEnumerationOptions)options passingTest:(BOOL (^)(id obj, NSUInteger idx, BOOL *stop))test
 614  {
 615      if (test == nil)
 616      {
 617          [NSException raise:NSInvalidArgumentException format:@"Test cannot be nil"];
 618          return nil;
 619      }
 620  
 621      NSIndexSet *passingIndexes = [self indexesOfObjectsWithOptions:options passingTest:test];
 622      NSArray *objects = [self objectsAtIndexes:passingIndexes];
 623  
 624      return [NSOrderedSet orderedSetWithArray:objects];
 625  }
 626  
 627  - (id)objectsAtIndexes:(NSIndexSet *)indexes options:(NSEnumerationOptions)options passingTest:(BOOL (^)(id obj, NSUInteger idx, BOOL *stop))test
 628  {
 629      if (test == nil)
 630      {
 631          [NSException raise:NSInvalidArgumentException format:@"Test cannot be nil"];
 632          return nil;
 633      }
 634  
 635      if (indexes == nil)
 636      {
 637          [NSException raise:NSInvalidArgumentException format:@"Indexes cannot be nil"];
 638          return nil;
 639      }
 640  
 641      NSIndexSet *passingIndexes = [self indexesOfObjectsAtIndexes:indexes options:options passingTest:test];
 642      NSArray *objects = [self objectsAtIndexes:passingIndexes];
 643  
 644      return [NSOrderedSet orderedSetWithArray:objects];
 645  }
 646  
 647  - (id)objectPassingTest:(BOOL (^)(id obj, NSUInteger idx, BOOL *stop))test
 648  {
 649      if (test == nil)
 650      {
 651          [NSException raise:NSInvalidArgumentException format:@"Test cannot be nil"];
 652          return nil;
 653      }
 654  
 655      return [self objectWithOptions:0 passingTest:test];
 656  }
 657  
 658  - (id)objectWithOptions:(NSEnumerationOptions)options passingTest:(BOOL (^)(id obj, NSUInteger idx, BOOL *stop))test
 659  {
 660      if (test == nil)
 661      {
 662          [NSException raise:NSInvalidArgumentException format:@"Test cannot be nil"];
 663          return nil;
 664      }
 665  
 666      NSUInteger idx = [self indexOfObjectWithOptions:options passingTest:test];
 667  
 668      if (idx == NSNotFound)
 669      {
 670          return nil;
 671      }
 672  
 673      return [self objectAtIndex:idx];
 674  }
 675  
 676  - (id)objectAtIndexes:(NSIndexSet *)indexes options:(NSEnumerationOptions)options passingTest:(BOOL (^)(id obj, NSUInteger idx, BOOL *stop))test
 677  {
 678      if (test == nil)
 679      {
 680          [NSException raise:NSInvalidArgumentException format:@"Test cannot be nil"];
 681          return nil;
 682      }
 683  
 684      if (indexes == nil)
 685      {
 686          [NSException raise:NSInvalidArgumentException format:@"Indexes cannot be nil"];
 687          return nil;
 688      }
 689  
 690      NSUInteger idx = [self indexOfObjectAtIndexes:indexes options:options passingTest:test];
 691  
 692      if (idx == NSNotFound)
 693      {
 694          return nil;
 695      }
 696  
 697      return [self objectAtIndex:idx];
 698  }
 699  
 700  - (BOOL)isEqual:(id)other
 701  {
 702      if (self == other)
 703      {
 704          return YES;
 705      }
 706      else if ([other isNSOrderedSet__])
 707      {
 708          return [self isEqualToOrderedSet:(NSOrderedSet *)other];
 709      }
 710      else
 711      {
 712          return NO;
 713      }
 714  }
 715  
 716  - (NSUInteger)indexOfObject:(id)object inRange:(NSRange)range
 717  {
 718      if (NSMaxRange(range) > [self count])
 719      {
 720          [NSException raise:NSRangeException format:@"Range out of bounds for ordered set"];
 721          return 0;
 722      }
 723  
 724      NSUInteger idx = [self indexOfObject:object];
 725  
 726      return NSLocationInRange(idx, range);
 727  }
 728  
 729  - (NSUInteger)hash
 730  {
 731      return [self count];
 732  }
 733  
 734  - (void)getObjects:(id *)addr
 735  {
 736      if (addr == NULL)
 737      {
 738          [NSException raise:NSInvalidArgumentException format:@"Cannot place objects from ordered set into NULL array"];
 739          return;
 740      }
 741  
 742      NSRange range = NSMakeRange(0, [self count]);
 743      return [self getObjects:addr range:range];
 744  }
 745  
 746  - (void)getObjects:(id __unsafe_unretained [])objects range:(NSRange)range
 747  {
 748      if (objects == NULL && range.length > 0)
 749      {
 750          [NSException raise:NSInvalidArgumentException format:@"Range out of bounds of NULL array"];
 751          return;
 752      }
 753  
 754      if (NSMaxRange(range) > [self count])
 755      {
 756          [NSException raise:NSRangeException format:@"Range out of bounds of ordered set"];
 757          return;
 758      }
 759  
 760      if (range.length == 0)
 761      {
 762          return;
 763      }
 764  
 765      for (NSUInteger idx = 0; idx < range.length; idx++)
 766      {
 767          objects[idx] = [self objectAtIndex:(idx + range.location)];
 768      }
 769  }
 770  
 771  - (NSUInteger)countForObject:(id)object
 772  {
 773      NSUInteger idx = [self indexOfObject:object];
 774      if (idx == NSNotFound)
 775      {
 776          return 0;
 777      }
 778      else
 779      {
 780          return 1;
 781      }
 782  }
 783  
 784  - (NSUInteger)countForObject:(id)object inRange:(NSRange)range
 785  {
 786      if (NSMaxRange(range) > [self count])
 787      {
 788          [NSException raise:NSRangeException format:@"Range out of bounds for ordered set"];
 789          return NO;
 790      }
 791  
 792      NSUInteger idx = [self indexOfObject:object inRange:range];
 793  
 794      if (idx == NSNotFound)
 795      {
 796          return 0;
 797      }
 798      else
 799      {
 800          return 1;
 801      }
 802  }
 803  
 804  - (NSUInteger)countByEnumeratingWithState:(NSFastEnumerationState *)state objects:(id *)objects count:(NSUInteger)count
 805  {
 806      if (state->state == -1)
 807      {
 808          return 0;
 809      }
 810  
 811      if (state->state == 0)
 812      {
 813          state->mutationsPtr = &state->extra[0];
 814          state->extra[0] = [self count];
 815      }
 816  
 817      state->itemsPtr = objects;
 818  
 819      NSUInteger returnedLength = MIN(state->extra[0] - state->state, count);
 820      if (returnedLength != 0)
 821      {
 822          [self getObjects:objects range:NSMakeRange(state->state, returnedLength)];
 823      }
 824  
 825      if (state->state + returnedLength >= state->extra[0])
 826      {
 827          state->state = -1;
 828      }
 829      else
 830      {
 831          state->state += returnedLength;
 832      }
 833  
 834      return returnedLength;
 835  }
 836  
 837  - (BOOL)containsObject:(id)object
 838  {
 839      NSUInteger idx = [self indexOfObject:object];
 840  
 841      return idx != NSNotFound;
 842  }
 843  
 844  - (BOOL)containsObject:(id)object inRange:(NSRange)range
 845  {
 846      if (NSMaxRange(range) > [self count])
 847      {
 848          [NSException raise:NSRangeException format:@"Range out of bounds for ordered set"];
 849          return NO;
 850      }
 851  
 852      NSUInteger idx = [self indexOfObject:object inRange:range];
 853  
 854      return idx != NSNotFound;
 855  }
 856  
 857  - (NSArray *)allObjects
 858  {
 859      NSUInteger count = [self count];
 860  
 861      if (count == 0)
 862      {
 863          return [NSArray array];
 864      }
 865  
 866      id *objects = malloc(count * sizeof(id));
 867  
 868      if (objects == NULL)
 869      {
 870          [NSException raise:NSMallocException format:@"Failed to allocate buffer"];
 871          return nil;
 872      }
 873  
 874      NSRange range = NSMakeRange(0, count);
 875      [self getObjects:objects range:range];
 876  
 877      NSArray *array = [NSArray arrayWithObjects:objects count:count];
 878  
 879      free(objects);
 880  
 881      return array;
 882  }
 883  
 884  - (BOOL)isNSOrderedSet__
 885  {
 886      return YES;
 887  }
 888  
 889  - (NSArray *)objectsAtIndexes:(NSIndexSet *)indexes
 890  {
 891      if (indexes == nil)
 892      {
 893          [NSException raise:NSInvalidArgumentException format:@"Indexes cannot be nil"];
 894          return nil;
 895      }
 896  
 897      NSUInteger count = [indexes count];
 898  
 899      if (count == 0)
 900      {
 901          return [NSArray array];
 902      }
 903  
 904      if ([indexes lastIndex] >= [self count])
 905      {
 906          [NSException raise:NSInvalidArgumentException format:@"Indexes out of bounds of ordered set"];
 907          return nil;
 908      }
 909  
 910      id *objects = malloc(count * sizeof(id));
 911      if (objects == NULL)
 912      {
 913          [NSException raise:NSMallocException format:@"Failed to allocate buffer"];
 914          return nil;
 915      }
 916  
 917      __block id *currentObjectPtr = objects;
 918      [indexes enumerateRangesUsingBlock:^(NSRange range, BOOL *stop) {
 919          [self getObjects:currentObjectPtr range:range];
 920          currentObjectPtr += range.length;
 921      }];
 922  
 923      NSArray *array = [NSArray arrayWithObjects:objects count:count];
 924  
 925      free(objects);
 926  
 927      return array;
 928  }
 929  
 930  - (id)firstObject
 931  {
 932      if (self.count == 0)
 933      {
 934          return nil;
 935      }
 936  
 937      return [self objectAtIndex:0];
 938  }
 939  
 940  - (id)lastObject
 941  {
 942      NSUInteger count = self.count;
 943  
 944      if (count == 0)
 945      {
 946          return nil;
 947      }
 948  
 949      return [self objectAtIndex:count - 1];
 950  }
 951  
 952  - (BOOL)isEqualToOrderedSet:(NSOrderedSet *)other
 953  {
 954      if ([self count] != [other count])
 955      {
 956          return NO;
 957      }
 958  
 959      if ([self count] == 0)
 960      {
 961          return YES;
 962      }
 963  
 964      NSUInteger idx = 0;
 965      for (id obj in self)
 966      {
 967          id otherObj = [other objectAtIndex:idx];
 968          if (obj != otherObj && ![obj isEqual:otherObj])
 969          {
 970              return NO;
 971          }
 972          idx++;
 973      }
 974  
 975      return YES;
 976  }
 977  
 978  - (BOOL)intersectsOrderedSet:(NSOrderedSet *)other
 979  {
 980      for (id obj in self)
 981      {
 982          if ([other containsObject:obj])
 983          {
 984              return YES;
 985          }
 986      }
 987  
 988      return NO;
 989  }
 990  
 991  - (BOOL)intersectsSet:(NSSet *)set
 992  {
 993      for (id obj in self)
 994      {
 995          if ([set containsObject:obj])
 996          {
 997              return YES;
 998          }
 999      }
1000  
1001      return NO;
1002  }
1003  
1004  - (BOOL)isSubsetOfOrderedSet:(NSOrderedSet *)other
1005  {
1006      for (id obj in self)
1007      {
1008          if (![other containsObject:obj])
1009          {
1010              return NO;
1011          }
1012      }
1013  
1014      return YES;
1015  }
1016  
1017  - (BOOL)isSubsetOfSet:(NSSet *)set
1018  {
1019      for (id obj in self)
1020      {
1021          if (![set containsObject:obj])
1022          {
1023              return NO;
1024          }
1025      }
1026  
1027      return YES;
1028  }
1029  
1030  - (id)objectAtIndexedSubscript:(NSUInteger)idx
1031  {
1032      return [self objectAtIndex:idx];
1033  }
1034  
1035  - (NSEnumerator *)objectEnumerator
1036  {
1037      return [[[__NSFastEnumerationEnumerator alloc] initWithObject:self] autorelease];
1038  }
1039  
1040  - (NSEnumerator *)reverseObjectEnumerator
1041  {
1042      return [[[__NSOrderedSetReverseEnumerator alloc] initWithObject:self] autorelease];
1043  }
1044  
1045  - (NSOrderedSet *)reversedOrderedSet
1046  {
1047      return [[[__NSOrderedSetReversed alloc] initWithOrderedSet:self] autorelease];
1048  }
1049  
1050  - (NSArray *)array
1051  {
1052      return [[[__NSOrderedSetArrayProxy alloc] initWithOrderedSet:self] autorelease];
1053  }
1054  
1055  - (NSSet *)set
1056  {
1057      return [[[__NSOrderedSetSetProxy alloc] initWithOrderedSet:self] autorelease];
1058  }
1059  
1060  - (void)enumerateObjectsUsingBlock:(void (^)(id obj, NSUInteger idx, BOOL *stop))block
1061  {
1062      [self enumerateObjectsWithOptions:0 usingBlock:block];
1063  }
1064  
1065  - (void)enumerateObjectsWithOptions:(NSEnumerationOptions)opts usingBlock:(void (^)(id obj, NSUInteger idx, BOOL *stop))block
1066  {
1067      NSUInteger len = [self count];
1068      if (opts & NSEnumerationConcurrent)
1069      {
1070          __block BOOL stop = NO;
1071  
1072          if (opts & NSEnumerationReverse)
1073          {
1074              dispatch_apply(len, dispatch_get_global_queue(DISPATCH_QUEUE_PRIORITY_DEFAULT, 0), ^(size_t iter){
1075                  if (!stop)
1076                  {
1077                      NSUInteger i = len - 1 - iter;
1078                      block([self objectAtIndex:i], i, &stop);
1079                  }
1080              });
1081          }
1082          else
1083          {
1084              dispatch_apply(len, dispatch_get_global_queue(DISPATCH_QUEUE_PRIORITY_DEFAULT, 0), ^(size_t iter){
1085                  if (!stop)
1086                  {
1087                      block([self objectAtIndex:iter], iter, &stop);
1088                  }
1089              });
1090          }
1091          return;
1092      }
1093      if (opts & NSEnumerationReverse)
1094      {
1095          for (int i = len - 1; i >= 0; i--)
1096          {
1097              BOOL stop = NO;
1098              block([self objectAtIndex:i], i, &stop);
1099  
1100              if (stop)
1101              {
1102                  return;
1103              }
1104          }
1105      }
1106      else
1107      {
1108          NSUInteger i = 0;
1109  
1110          for (id obj in self)
1111          {
1112              BOOL stop = NO;
1113              block(obj, i++, &stop);
1114  
1115              if (stop)
1116              {
1117                  return;
1118              }
1119          }
1120      }
1121  }
1122  
1123  - (void)enumerateObjectsAtIndexes:(NSIndexSet *)s options:(NSEnumerationOptions)opts usingBlock:(void (^)(id obj, NSUInteger idx, BOOL *stop))block
1124  {
1125      if (block == nil)
1126      {
1127          [NSException raise:NSInvalidArgumentException format:@"block is nil"];
1128          return;
1129      }
1130  
1131      [s enumerateIndexesWithOptions:opts usingBlock:^(NSUInteger idx, BOOL *stop) {
1132          block([self objectAtIndex:idx], idx, stop);
1133      }];
1134  }
1135  
1136  - (NSUInteger)indexOfObjectPassingTest:(BOOL (^)(id obj, NSUInteger idx, BOOL *stop))predicate
1137  {
1138      return [self indexOfObjectWithOptions:0 passingTest:predicate];
1139  }
1140  
1141  - (NSUInteger)indexOfObjectWithOptions:(NSEnumerationOptions)opts passingTest:(BOOL (^)(id obj, NSUInteger idx, BOOL *stop))predicate
1142  {
1143      NSUInteger len = [self count];
1144      __block NSUInteger found = NSNotFound;
1145      if (opts & NSEnumerationConcurrent)
1146      {
1147          __block BOOL stop = NO;
1148  
1149          if (opts & NSEnumerationReverse)
1150          {
1151              dispatch_apply(len, dispatch_get_global_queue(DISPATCH_QUEUE_PRIORITY_DEFAULT, 0), ^(size_t iter){
1152                  if (!stop)
1153                  {
1154                      NSUInteger i = len - 1 - iter;
1155  
1156                      if (predicate([self objectAtIndex:i], i, &stop))
1157                      {
1158                          stop = YES;
1159                          found = i;
1160                      }
1161                  }
1162              });
1163          }
1164          else
1165          {
1166              dispatch_apply(len, dispatch_get_global_queue(DISPATCH_QUEUE_PRIORITY_DEFAULT, 0), ^(size_t iter){
1167                  if (!stop)
1168                  {
1169                      if(predicate([self objectAtIndex:iter], iter, &stop))
1170                      {
1171                          stop = YES;
1172                          found = iter;
1173                      }
1174                  }
1175              });
1176          }
1177      }
1178      if (opts & NSEnumerationReverse)
1179      {
1180          for (int i = len - 1; i >= 0; i--)
1181          {
1182              BOOL stop = NO;
1183  
1184              if (predicate([self objectAtIndex:i], i, &stop))
1185              {
1186                  stop = YES;
1187                  found = i;
1188              }
1189              if (stop)
1190              {
1191                  break;
1192              }
1193          }
1194      }
1195      else
1196      {
1197          NSUInteger i = 0;
1198  
1199          for (id obj in self)
1200          {
1201              BOOL stop = NO;
1202  
1203              if (predicate(obj, i++, &stop))
1204              {
1205                  stop = YES;
1206                  found = i;
1207              }
1208              if (stop)
1209              {
1210                  break;
1211              }
1212          }
1213      }
1214      return found;
1215  }
1216  
1217  - (NSUInteger)indexOfObjectAtIndexes:(NSIndexSet *)s options:(NSEnumerationOptions)opts passingTest:(BOOL (^)(id obj, NSUInteger idx, BOOL *stop))predicate
1218  {
1219      __block NSUInteger found = NSNotFound;
1220      [s enumerateIndexesWithOptions:opts usingBlock:^(NSUInteger idx, BOOL *stop) {
1221          if (predicate([self objectAtIndex:idx], idx, stop))
1222          {
1223              found = idx;
1224          }
1225      }];
1226      return found;
1227  }
1228  
1229  - (NSIndexSet *)indexesOfObjectsPassingTest:(BOOL (^)(id obj, NSUInteger idx, BOOL *stop))predicate
1230  {
1231      NSObject *indexSet = [[objc_getClass("NSMutableIndexSet") alloc] init];
1232      NSUInteger len = [self count];
1233      BOOL stop = NO;
1234      for (NSUInteger i = 0; i < len; i++)
1235      {
1236          if (predicate([self objectAtIndex:i], i, &stop))
1237          {
1238              ((void (*)(id, SEL, NSUInteger))objc_msgSend)(indexSet, @selector(addIndex:), i);
1239          }
1240          if (stop)
1241          {
1242              break;
1243          }
1244      }
1245      return (NSIndexSet *)[indexSet autorelease];
1246  }
1247  
1248  - (NSIndexSet *)indexesOfObjectsWithOptions:(NSEnumerationOptions)opts passingTest:(BOOL (^)(id obj, NSUInteger idx, BOOL *stop))predicate
1249  {
1250      NSObject *indices = [[objc_getClass("NSMutableIndexSet") alloc] init];
1251      NSUInteger len = [self count];
1252  
1253      if (opts & NSEnumerationConcurrent)
1254      {
1255          __block BOOL stop = NO;
1256  
1257          if (opts & NSEnumerationReverse)
1258          {
1259              dispatch_apply(len, dispatch_get_global_queue(DISPATCH_QUEUE_PRIORITY_DEFAULT, 0), ^(size_t iter){
1260                  if (!stop)
1261                  {
1262                      NSUInteger i = len - 1 - iter;
1263  
1264                      if (predicate([self objectAtIndex:i], i, &stop))
1265                      {
1266                          ((void (*)(id, SEL, NSUInteger))objc_msgSend)(indices, @selector(addIndex:), i);
1267                      }
1268                  }
1269              });
1270          }
1271          else
1272          {
1273              dispatch_apply(len, dispatch_get_global_queue(DISPATCH_QUEUE_PRIORITY_DEFAULT, 0), ^(size_t iter){
1274                  if (!stop)
1275                  {
1276                      if(predicate([self objectAtIndex:iter], iter, &stop))
1277                      {
1278                          ((void (*)(id, SEL, NSUInteger))objc_msgSend)(indices, @selector(addIndex:), iter);
1279                      }
1280                  }
1281              });
1282          }
1283      }
1284      if (opts & NSEnumerationReverse)
1285      {
1286          for (int i = len - 1; i >= 0; i--)
1287          {
1288              BOOL stop = NO;
1289  
1290              if (predicate([self objectAtIndex:i], i, &stop))
1291              {
1292                  ((void (*)(id, SEL, NSUInteger))objc_msgSend)(indices, @selector(addIndex:), i);
1293              }
1294              if (stop)
1295              {
1296                  break;
1297              }
1298          }
1299      }
1300      else
1301      {
1302          NSUInteger i = 0;
1303          for (id obj in self)
1304          {
1305              BOOL stop = NO;
1306  
1307              if (predicate(obj, i++, &stop))
1308              {
1309                  ((void (*)(id, SEL, NSUInteger))objc_msgSend)(indices, @selector(addIndex:), i);
1310              }
1311              if (stop)
1312              {
1313                  break;
1314              }
1315          }
1316      }
1317      return (NSIndexSet *)[indices autorelease];
1318  }
1319  
1320  - (NSIndexSet *)indexesOfObjectsAtIndexes:(NSIndexSet *)s options:(NSEnumerationOptions)opts passingTest:(BOOL (^)(id obj, NSUInteger idx, BOOL *stop))predicate
1321  {
1322      NSObject *indices = [[objc_getClass("NSMutableIndexSet") alloc] init];
1323      [s enumerateIndexesWithOptions:opts usingBlock:^(NSUInteger idx, BOOL *stop) {
1324          if (predicate([self objectAtIndex:idx], idx, stop))
1325          {
1326              ((void (*)(id, SEL, NSUInteger))objc_msgSend)(indices, @selector(addIndex:), idx);
1327          }
1328      }];
1329      return (NSIndexSet *)[indices autorelease];
1330  }
1331  
1332  - (NSUInteger)indexOfObject:(id)obj inSortedRange:(NSRange)r options:(NSBinarySearchingOptions)opts usingComparator:(NSComparator)comparator
1333  {
1334      NSUInteger minIndex = r.location;
1335      NSUInteger midIndex = ceil(r.length / 2.0) + r.location;
1336      NSUInteger maxIndex = NSMaxRange(r);
1337      id min = [self objectAtIndex:minIndex];
1338      id mid = min;
1339  
1340      if (r.length > 2)
1341      {
1342          mid = [self objectAtIndex:midIndex];
1343      }
1344  
1345      NSComparisonResult result = comparator(mid, obj);
1346  
1347      switch (result)
1348      {
1349          case NSOrderedAscending:
1350              if ((opts & NSBinarySearchingInsertionIndex) && midIndex == maxIndex)
1351              {
1352                  return maxIndex + 1;
1353              }
1354              else if (midIndex == maxIndex)
1355              {
1356                  return NSNotFound;
1357              }
1358              else
1359              {
1360                  return [self indexOfObject:obj inSortedRange:NSMakeRange(midIndex, maxIndex - minIndex) options:opts usingComparator:comparator];
1361              }
1362              break;
1363          case NSOrderedDescending:
1364              if ((opts & NSBinarySearchingInsertionIndex) && midIndex == minIndex)
1365              {
1366                  return minIndex;
1367              }
1368              else if (midIndex == minIndex)
1369              {
1370                  return NSNotFound;
1371              }
1372              else
1373              {
1374                  return [self indexOfObject:obj inSortedRange:NSMakeRange(minIndex, midIndex - minIndex) options:opts usingComparator:comparator];
1375              }
1376          case NSOrderedSame:
1377              if (opts & NSBinarySearchingFirstEqual)
1378              {
1379                  for (NSUInteger idx = midIndex; idx > 0; idx--)
1380                  {
1381                      mid = [self objectAtIndex:idx];
1382                      result = comparator(mid, obj);
1383  
1384                      if (result != NSOrderedSame)
1385                      {
1386                          return idx + 1;
1387                      }
1388                  }
1389                  return NSNotFound; // this is likely an error
1390              }
1391              else if (opts & NSBinarySearchingLastEqual)
1392              {
1393                  for (NSUInteger idx = midIndex; idx < [self count]; idx++)
1394                  {
1395                      mid = [self objectAtIndex:idx];
1396                      result = comparator(mid, obj);
1397  
1398                      if (result != NSOrderedSame)
1399                      {
1400                          return idx - 1;
1401                      }
1402                  }
1403                  return NSNotFound; // also likely to be an error
1404              }
1405              else
1406              {
1407                  return midIndex;
1408              }
1409              break;
1410      }
1411      return NSNotFound;
1412  }
1413  
1414  - (NSArray *)sortedArrayFromRange:(NSRange)range options:(NSSortOptions)opts usingComparator:(NSComparator)cmptr
1415  {
1416      if (cmptr == nil)
1417      {
1418          [self doesNotRecognizeSelector:_cmd];
1419          CFStringRef format = CFStringCreateWithFormat(kCFAllocatorDefault, NULL, CFSTR("-[%s <null selector>] unrecognized selector 0x%x"), object_getClassName(self), self);
1420          [NSException raise:NSInvalidArgumentException format:(NSString *)format];
1421          CFRelease(format);
1422          return nil;
1423      }
1424  
1425      NSUInteger count = range.length;
1426      id objects[STACK_BUFFER_SIZE] = {0};
1427      CFIndex indices[STACK_BUFFER_SIZE] = {0};
1428      id *objs = &objects[0];
1429      CFIndex *indexes = &indices[0];
1430  
1431      if (count > STACK_BUFFER_SIZE)
1432      {
1433          objs = malloc(sizeof(id) * count);
1434  
1435          if (objs == NULL)
1436          {
1437              CFStringRef reason = CFStringCreateWithFormat(kCFAllocatorDefault, NULL, CFSTR("unable to allocate space to store %d objects"), count);
1438              @throw [NSException exceptionWithName:NSMallocException reason:(NSString *)reason userInfo:nil];
1439              CFRelease(reason);
1440              return nil;
1441          }
1442          indexes = malloc(sizeof(CFIndex) * count);
1443          if (indexes == NULL)
1444          {
1445              free(objects);
1446              CFStringRef reason = CFStringCreateWithFormat(kCFAllocatorDefault, NULL, CFSTR("unable to allocate space to store %d indices"), count);
1447              @throw [NSException exceptionWithName:NSMallocException reason:(NSString *)reason userInfo:nil];
1448              CFRelease(reason);
1449              return nil;
1450          }
1451      }
1452  
1453      [self getObjects:objs range:range];
1454      CFSortIndexes(indexes, count, opts, ^(CFIndex i1, CFIndex i2) {
1455          return (CFComparisonResult)cmptr(objs[i1], objs[i2]);
1456      });
1457      assert(sizeof(id) == sizeof(CFIndex));
1458  
1459      for (int i = 0; i < count; i++)
1460      {
1461          indexes[i] = (CFIndex)objs[indexes[i]]; // re-use indexes allocation
1462      }
1463  
1464      if (objs != objects)
1465      {
1466          free(objs);
1467      }
1468  
1469      // Note: the indexes is reused as an object store.
1470      NSArray *arr = [[NSArray alloc] initWithObjects:(id *)indexes count:count];
1471  
1472      if (indices != indexes)
1473      {
1474          free(indexes);
1475      }
1476  
1477      return [arr autorelease];
1478  }
1479  
1480  - (NSArray *)sortedArrayUsingComparator:(NSComparator)comparator
1481  {
1482      return [self sortedArrayWithOptions:NSSortStable usingComparator:comparator];
1483  }
1484  
1485  - (NSArray *)sortedArrayWithOptions:(NSSortOptions)opts usingComparator:(NSComparator)comparator
1486  {
1487      return [self sortedArrayFromRange:NSMakeRange(0, [self count]) options:opts usingComparator:comparator];
1488  }
1489  
1490  - (NSString *)description
1491  {
1492      return [self descriptionWithLocale:nil indent:0];
1493  }
1494  
1495  - (NSString *)descriptionWithLocale:(NSLocale *)locale
1496  {
1497      return [self descriptionWithLocale:locale indent:0];
1498  }
1499  
1500  - (NSString *)descriptionWithLocale:(NSLocale *)locale indent:(NSUInteger)level
1501  {
1502      CFMutableStringRef description = CFStringCreateMutable(kCFAllocatorDefault, 0);
1503      CFStringAppendFormat(description, NULL, CFSTR("%*s{(\n"), (int)level * strlen(INDENT), "");
1504  
1505      NSUInteger count = [self count];
1506      NSUInteger idx = 1;
1507  
1508      for (id obj in self)
1509      {
1510          NSString *objDescription = nil;
1511          if ([obj respondsToSelector:@selector(descriptionWithLocale:indent:)])
1512          {
1513              objDescription = [obj descriptionWithLocale:locale indent:(level + 1)];
1514          }
1515          else if ([obj respondsToSelector:@selector(descriptionWithLocale:)])
1516          {
1517              objDescription = [obj descriptionWithLocale:locale];
1518          }
1519          else
1520          {
1521              objDescription = [obj description];
1522          }
1523  
1524          CFStringRef format;
1525  
1526          if (idx == count)
1527          {
1528              format = CFSTR("%*s%@\n");
1529          }
1530          else
1531          {
1532              format = CFSTR("%*s%@,\n");
1533          }
1534  
1535          CFStringAppendFormat(description, NULL, format, ((int)level + 1) * strlen(INDENT), "", objDescription);
1536  
1537          idx++;
1538      }
1539  
1540      CFStringAppendFormat(description, NULL, CFSTR("%*s)}"), (int)level * strlen(INDENT), "");
1541  
1542      CFStringRef desc = CFStringCreateCopy(kCFAllocatorDefault, description);
1543      CFRelease(description);
1544      return [(NSString *)desc autorelease];
1545  }
1546  
1547  @end
1548  
1549  @implementation NSMutableOrderedSet
1550  
1551  + (id)orderedSetWithCapacity:(NSUInteger)capacity
1552  {
1553      return [[[self alloc] initWithCapacity:capacity] autorelease];
1554  }
1555  
1556  - (id)initWithCapacity:(NSUInteger)capacity
1557  {
1558      NSRequestConcreteImplementation();
1559      return nil;
1560  }
1561  
1562  - (id)initWithObjects:(const id *)objects count:(NSUInteger)count
1563  {
1564      if (objects == NULL && count > 0)
1565      {
1566          [self release];
1567          [NSException raise:NSInvalidArgumentException format:@"Cannot init ordered set with NULL array of and nonzero count"];
1568          return nil;
1569      }
1570  
1571      for (NSUInteger idx = 0; idx < count; idx++)
1572      {
1573          if (objects[idx] == nil)
1574          {
1575              [self release];
1576              [NSException raise:NSInvalidArgumentException format:@"Cannot init ordered set with nil"];
1577              return nil;
1578          }
1579      }
1580  
1581      self = [self initWithCapacity:count];
1582      if (self != nil)
1583      {
1584          [self insertObjects:objects count:count atIndex:0];
1585      }
1586  
1587      return self;
1588  }
1589  
1590  - (Class)classForCoder
1591  {
1592      return [NSMutableOrderedSet class];
1593  }
1594  
1595  - (void)addObject:(id)object
1596  {
1597      if (object == nil)
1598      {
1599          [NSException raise:NSInvalidArgumentException format:@"Cannot add nil to orderded set"];
1600          return;
1601      }
1602  
1603      [self _mutate];
1604      [self insertObject:object atIndex:[self count]];
1605  }
1606  
1607  - (void)addObjects:(const id [])objects count:(NSUInteger)count
1608  {
1609      if (objects == NULL && count > 0)
1610      {
1611          [NSException raise:NSInvalidArgumentException format:@"Cannot add NULL array of objects with nonzero count to ordered set"];
1612          return;
1613      }
1614  
1615      for (NSUInteger idx = 0; idx < count; idx++)
1616      {
1617          id object = objects[idx];
1618          if (object == nil)
1619          {
1620              [NSException raise:NSInvalidArgumentException format:@"Cannot add nil to ordered set"];
1621              return;
1622          }
1623      }
1624  
1625      [self _mutate];
1626      [self insertObjects:objects count:count atIndex:[self count]];
1627  }
1628  
1629  - (void)addObjectsFromSet:(NSSet *)set
1630  {
1631      [self _mutate];
1632      [self insertObjectsFromSet:set atIndex:[self count]];
1633  }
1634  
1635  - (void)addObjectsFromOrderedSet:(NSOrderedSet *)orderedSet
1636  {
1637      NSRange range = NSMakeRange(0, [orderedSet count]);
1638      [self _mutate];
1639      [self insertObjectsFromOrderedSet:orderedSet range:range atIndex:[self count]];
1640  }
1641  
1642  - (void)addObjectsFromOrderedSet:(NSOrderedSet *)orderedSet range:(NSRange)range
1643  {
1644      if (NSMaxRange(range) > [orderedSet count])
1645      {
1646          [NSException raise:NSRangeException format:@"Range out of bounds of ordered set"];
1647          return;
1648      }
1649  
1650      [self _mutate];
1651      [self insertObjectsFromOrderedSet:orderedSet range:range atIndex:[self count]];
1652  }
1653  
1654  - (void)addObjectsFromArray:(NSArray *)array
1655  {
1656      NSRange range = NSMakeRange(0, [array count]);
1657      [self _mutate];
1658      [self insertObjectsFromArray:array range:range atIndex:[self count]];
1659  }
1660  
1661  - (void)addObjectsFromArray:(NSArray *)array range:(NSRange)range
1662  {
1663      if (NSMaxRange(range) > [array count])
1664      {
1665          [NSException raise:NSRangeException format:@"Range out of bounds of array"];
1666          return;
1667      }
1668  
1669      [self _mutate];
1670      [self insertObjectsFromArray:array range:range atIndex:[self count]];
1671  }
1672  
1673  - (void)exchangeObjectAtIndex:(NSUInteger)idx1 withObjectAtIndex:(NSUInteger)idx2
1674  {
1675      NSUInteger count = [self count];
1676  
1677      if (idx1 >= count || idx2 >= count)
1678      {
1679          [NSException raise:NSInvalidArgumentException format:@"Index out of bounds of ordered set"];
1680          return;
1681      }
1682  
1683      id obj1 = [[self objectAtIndex:idx1] retain];
1684      id obj2 = [[self objectAtIndex:idx2] retain];
1685  
1686      [self _mutate];
1687  
1688      [self removeObjectAtIndex:idx1];
1689      [self insertObject:obj2 atIndex:idx1];
1690  
1691      [self removeObjectAtIndex:idx2];
1692      [self insertObject:obj1 atIndex:idx2];
1693  
1694      [obj1 release];
1695      [obj2 release];
1696  }
1697  
1698  - (void)moveObjectsAtIndexes:(NSIndexSet *)indexes toIndex:(NSUInteger)idx
1699  {
1700      NSUInteger count = [self count];
1701  
1702      if (idx >= count)
1703      {
1704          [NSException raise:NSInvalidArgumentException format:@"Index out of bounds of ordered set"];
1705          return;
1706      }
1707  
1708      NSUInteger idxCount = [indexes count];
1709  
1710      if (idxCount == 0)
1711      {
1712          return;
1713      }
1714  
1715      if ([indexes lastIndex] >= count)
1716      {
1717          [NSException raise:NSInvalidArgumentException format:@"Indexes out of bounds of ordered set"];
1718          return;
1719      }
1720  
1721      NSArray *array = [self objectsAtIndexes:indexes];
1722  
1723      [self _mutate];
1724      [self removeObjectsAtIndexes:indexes];
1725  
1726      id *objects = malloc(idxCount * sizeof(id));
1727      if (objects == NULL)
1728      {
1729          [NSException raise:NSMallocException format:@"Could not allocate buffer"];
1730          return;
1731      }
1732  
1733      NSRange range = NSMakeRange(0, idxCount);
1734      [array getObjects:objects range:range];
1735      [self insertObjects:objects count:idxCount atIndex:idx];
1736  
1737      free(objects);
1738  }
1739  
1740  - (void)setObject:(id)object
1741  {
1742      if (object == nil)
1743      {
1744          [NSException raise:NSInvalidArgumentException format:@"Cannot add nil to orderded set"];
1745          return;
1746      }
1747  
1748      NSUInteger idx = [self indexOfObject:object];
1749      if (idx == NSNotFound)
1750      {
1751          [NSException raise:NSInvalidArgumentException format:@"Object not in ordered set"];
1752          return;
1753      }
1754  
1755      [self _mutate];
1756      [self replaceObjectAtIndex:idx withObject:object];
1757  }
1758  
1759  - (void)setObject:(id)object atIndex:(NSUInteger)idx
1760  {
1761      if (object == nil)
1762      {
1763          [NSException raise:NSInvalidArgumentException format:@"Cannot add nil to orderded set"];
1764          return;
1765      }
1766  
1767      NSUInteger count = [self count];
1768  
1769      if (idx >= count)
1770      {
1771          [NSException raise:NSInvalidArgumentException format:@"Index out of bounds of ordered set"];
1772          return;
1773      }
1774  
1775      [self _mutate];
1776  
1777      if (idx == count)
1778      {
1779          [self insertObject:object atIndex:idx];
1780      }
1781      else
1782      {
1783          [self replaceObjectAtIndex:idx withObject:object];
1784      }
1785  }
1786  
1787  - (void)setObject:(id)object atIndexedSubscript:(NSUInteger)idx
1788  {
1789      [self setObject:object atIndex:idx];
1790  }
1791  
1792  - (void)setSet:(NSSet *)set
1793  {
1794      [self _mutate];
1795      [self removeAllObjects];
1796      [self insertObjectsFromSet:set atIndex:0];
1797  }
1798  
1799  - (void)setOrderedSet:(NSOrderedSet *)orderedSet
1800  {
1801      [self _mutate];
1802      [self removeAllObjects];
1803      [self insertObjectsFromOrderedSet:orderedSet atIndex:0];
1804  }
1805  
1806  - (void)setArray:(NSArray *)array
1807  {
1808      [self _mutate];
1809      [self removeAllObjects];
1810      [self insertObjectsFromArray:array atIndex:0];
1811  }
1812  
1813  - (void)removeObjectAtIndex:(NSUInteger)idx
1814  {
1815      NSRequestConcreteImplementation();
1816  }
1817  
1818  - (void)removeObjectsInRange:(NSRange)range
1819  {
1820      NSUInteger maxRange = NSMaxRange(range);
1821  
1822      if (maxRange > [self count])
1823      {
1824          [NSException raise:NSRangeException format:@"Range out of bounds of ordered set"];
1825          return;
1826      }
1827  
1828      if (maxRange == 0)
1829      {
1830          return;
1831      }
1832  
1833      [self _mutate];
1834  
1835      NSUInteger idx = range.location;
1836  
1837      for (NSUInteger i = 0; i < range.length; i++)
1838      {
1839          [self removeObjectAtIndex:idx];
1840      }
1841  }
1842  
1843  - (void)removeObjectsAtIndexes:(NSIndexSet *)indexes
1844  {
1845      if (indexes == nil)
1846      {
1847          [NSException raise:NSInvalidArgumentException format:@"Index set cannot be nil"];
1848          return;
1849      }
1850  
1851      NSUInteger count = [indexes count];
1852  
1853      if (count > 0 && [indexes lastIndex] >= [self count])
1854      {
1855          [NSException raise:NSInvalidArgumentException format:@"Index set out of bounds of ordered set"];
1856          return;
1857      }
1858  
1859      if (count == 0)
1860      {
1861          return;
1862      }
1863  
1864      [self _mutate];
1865  
1866      [indexes enumerateRangesWithOptions:NSEnumerationReverse usingBlock:^(NSRange range, BOOL *stop) {
1867          [self removeObjectsInRange:range];
1868      }];
1869  }
1870  
1871  - (void)removeAllObjects
1872  {
1873      NSUInteger count = [self count];
1874  
1875      if (count == 0)
1876      {
1877          return;
1878      }
1879  
1880      [self _mutate];
1881  
1882      for (NSUInteger idx = count; idx > 0; idx--)
1883      {
1884          [self removeObjectAtIndex:idx - 1];
1885      }
1886  }
1887  
1888  - (void)removeObject:(id)object
1889  {
1890      NSUInteger idx = [self indexOfObject:object];
1891  
1892      if (idx == NSNotFound)
1893      {
1894          return;
1895      }
1896  
1897      [self _mutate];
1898  
1899      [self removeObjectAtIndex:idx];
1900  }
1901  
1902  - (void)removeObject:(id)object inRange:(NSRange)range
1903  {
1904      if (NSMaxRange(range) > [self count])
1905      {
1906          [NSException raise:NSRangeException format:@"Range out of bounds of ordered set"];
1907          return;
1908      }
1909  
1910      NSUInteger idx = [self indexOfObject:object inRange:range];
1911  
1912      if (idx == NSNotFound)
1913      {
1914          return;
1915      }
1916  
1917      [self _mutate];
1918  
1919      [self removeObjectAtIndex:idx];
1920  }
1921  
1922  - (void)removeObjectsInArray:(NSArray *)array
1923  {
1924      if ([array count] == 0)
1925      {
1926          return;
1927      }
1928  
1929      [self _mutate];
1930  
1931      for (id object in array)
1932      {
1933          NSUInteger idx = [self indexOfObject:object];
1934          if (idx != NSNotFound)
1935          {
1936              [self removeObjectAtIndex:idx];
1937          }
1938      }
1939  }
1940  
1941  - (void)removeObjectsInArray:(NSArray *)array range:(NSRange)arrayRange
1942  {
1943      NSUInteger arrayCount = [array count];
1944  
1945      if (NSMaxRange(arrayRange) > arrayCount)
1946      {
1947          [NSException raise:NSRangeException format:@"Range out of bounds of array"];
1948          return;
1949      }
1950  
1951      if (arrayCount == 0)
1952      {
1953          return;
1954      }
1955  
1956      [self _mutate];
1957  
1958      for (NSUInteger arrayIdx = arrayRange.length; arrayIdx < NSMaxRange(arrayRange); arrayIdx++)
1959      {
1960          id obj = [array objectAtIndex:arrayIdx];
1961          NSUInteger idx = [self indexOfObject:obj];
1962          if (idx != NSNotFound)
1963          {
1964              [self removeObjectAtIndex:idx];
1965          }
1966      }
1967  }
1968  
1969  - (void)removeObjectsInRange:(NSRange)range inArray:(NSArray *)array
1970  {
1971      if (NSMaxRange(range) > [self count])
1972      {
1973          [NSException raise:NSRangeException format:@"Range out of bounds of ordered set"];
1974          return;
1975      }
1976  
1977      if ([array count] == 0)
1978      {
1979          return;
1980      }
1981  
1982      [self _mutate];
1983  
1984      for (id object in array)
1985      {
1986          NSUInteger idx = [self indexOfObject:object inRange:range];
1987          if (idx != NSNotFound)
1988          {
1989              [self removeObjectAtIndex:idx];
1990          }
1991      }
1992  }
1993  
1994  - (void)removeObjectsInRange:(NSRange)range inArray:(NSArray *)array range:(NSRange)arrayRange
1995  {
1996      if (NSMaxRange(range) > [self count])
1997      {
1998          [NSException raise:NSRangeException format:@"Range out of bounds of ordered set"];
1999          return;
2000      }
2001  
2002      NSUInteger arrayCount = [array count];
2003  
2004      if (NSMaxRange(arrayRange) > arrayCount)
2005      {
2006          [NSException raise:NSRangeException format:@"Range out of bounds of array"];
2007          return;
2008      }
2009  
2010      if (arrayCount == 0)
2011      {
2012          return;
2013      }
2014  
2015      [self _mutate];
2016  
2017      for (NSUInteger arrayIdx = arrayRange.length; arrayIdx < NSMaxRange(arrayRange); arrayIdx++)
2018      {
2019          id obj = [array objectAtIndex:arrayIdx];
2020          NSUInteger idx = [self indexOfObject:obj inRange:range];
2021          if (idx != NSNotFound)
2022          {
2023              [self removeObjectAtIndex:idx];
2024          }
2025      }
2026  }
2027  
2028  - (void)removeObjectsInSet:(NSSet *)set
2029  {
2030      if ([set count] == 0)
2031      {
2032          return;
2033      }
2034  
2035      [self _mutate];
2036  
2037      for (id object in set)
2038      {
2039          NSUInteger idx = [self indexOfObject:object];
2040          if (idx != NSNotFound)
2041          {
2042              [self removeObjectAtIndex:idx];
2043          }
2044      }
2045  }
2046  
2047  - (void)removeObjectsInRange:(NSRange)range inSet:(NSSet *)set
2048  {
2049      if (NSMaxRange(range) > [self count])
2050      {
2051          [NSException raise:NSRangeException format:@"Range out of bounds of ordered set"];
2052          return;
2053      }
2054  
2055      if (range.length == 0)
2056      {
2057          return;
2058      }
2059  
2060      for (id object in set)
2061      {
2062          NSUInteger idx = [self indexOfObject:object inRange:range];
2063          if (idx != NSNotFound)
2064          {
2065              [self removeObjectAtIndex:idx];
2066          }
2067      }
2068  }
2069  
2070  - (void)removeObjectsInOrderedSet:(NSOrderedSet *)orderedSet
2071  {
2072      if ([orderedSet count] == 0)
2073      {
2074          return;
2075      }
2076  
2077      [self _mutate];
2078  
2079      for (id object in orderedSet)
2080      {
2081          NSUInteger idx = [self indexOfObject:object];
2082          if (idx != NSNotFound)
2083          {
2084              [self removeObjectAtIndex:idx];
2085          }
2086      }
2087  }
2088  
2089  - (void)removeObjectsInOrderedSet:(NSOrderedSet *)orderedSet range:(NSRange)orderedSetRange
2090  {
2091      NSUInteger orderedSetCount = [orderedSet count];
2092  
2093      if (NSMaxRange(orderedSetRange) > orderedSetCount)
2094      {
2095          [NSException raise:NSRangeException format:@"Range out of bounds of ordered set"];
2096          return;
2097      }
2098  
2099      if (orderedSetCount == 0)
2100      {
2101          return;
2102      }
2103  
2104      [self _mutate];
2105  
2106      for (NSUInteger orderedSetIdx = orderedSetRange.length; orderedSetIdx < NSMaxRange(orderedSetRange); orderedSetIdx++)
2107      {
2108          id obj = [orderedSet objectAtIndex:orderedSetIdx];
2109          NSUInteger idx = [self indexOfObject:obj];
2110          if (idx != NSNotFound)
2111          {
2112              [self removeObjectAtIndex:idx];
2113          }
2114      }
2115  }
2116  
2117  - (void)removeObjectsInRange:(NSRange)range inOrderedSet:(NSOrderedSet *)orderedSet
2118  {
2119      if (NSMaxRange(range) > [self count])
2120      {
2121          [NSException raise:NSRangeException format:@"Range out of bounds of ordered set"];
2122          return;
2123      }
2124  
2125      if ([orderedSet count] == 0)
2126      {
2127          return;
2128      }
2129  
2130      [self _mutate];
2131  
2132      for (id obj in orderedSet)
2133      {
2134          NSUInteger idx = [self indexOfObject:obj inRange:range];
2135          if (idx != NSNotFound)
2136          {
2137              [self removeObjectAtIndex:idx];
2138          }
2139      }
2140  }
2141  
2142  - (void)removeObjectsInRange:(NSRange)range inOrderedSet:(NSOrderedSet *)orderedSet range:(NSRange)orderedSetRange
2143  {
2144      if (NSMaxRange(range) > [self count])
2145      {
2146          [NSException raise:NSRangeException format:@"Range out of bounds of ordered set"];
2147          return;
2148      }
2149  
2150      NSUInteger orderedSetCount = [orderedSet count];
2151  
2152      if (NSMaxRange(orderedSetRange) > orderedSetCount)
2153      {
2154          [NSException raise:NSRangeException format:@"Range out of bounds of ordered set"];
2155          return;
2156      }
2157  
2158      if (orderedSetCount == 0)
2159      {
2160          return;
2161      }
2162  
2163      [self _mutate];
2164  
2165      for (NSUInteger orderedSetIdx = orderedSetRange.length; orderedSetIdx < NSMaxRange(orderedSetRange); orderedSetIdx++)
2166      {
2167          id obj = [orderedSet objectAtIndex:orderedSetIdx];
2168          NSUInteger idx = [self indexOfObject:obj inRange:range];
2169          if (idx != NSNotFound)
2170          {
2171              [self removeObjectAtIndex:idx];
2172          }
2173      }
2174  }
2175  
2176  - (void)removeFirstObject
2177  {
2178      if ([self count] == 0)
2179      {
2180          return;
2181      }
2182  
2183      [self removeObjectAtIndex:0];
2184  }
2185  
2186  - (void)removeLastObject
2187  {
2188      NSUInteger count = [self count];
2189  
2190      if (count == 0)
2191      {
2192          return;
2193      }
2194  
2195      [self removeObjectAtIndex:count - 1];
2196  }
2197  
2198  - (void)removeObjectsPassingTest:(BOOL (^)(id obj, NSUInteger idx, BOOL *stop))test
2199  {
2200      if (test == nil)
2201      {
2202          [NSException raise:NSInvalidArgumentException format:@"Test block cannot be nil"];
2203          return;
2204      }
2205  
2206      [self removeObjectsWithOptions:0 passingTest:test];
2207  }
2208  
2209  - (void)removeObjectsWithOptions:(NSEnumerationOptions)options passingTest:(BOOL (^)(id obj, NSUInteger idx, BOOL *stop))test
2210  {
2211  #warning TODO
2212      DEBUG_BREAK();
2213  }
2214  
2215  - (void)removeObjectsAtIndexes:(NSIndexSet *)indexes options:(NSEnumerationOptions)options passingTest:(BOOL (^)(id obj, NSUInteger idx, BOOL *stop))test
2216  {
2217      if (test == nil)
2218      {
2219          [NSException raise:NSInvalidArgumentException format:@"Test block cannot be nil"];
2220          return;
2221      }
2222  
2223  #warning TODO
2224      DEBUG_BREAK();
2225  }
2226  
2227  - (void)intersectOrderedSet:(NSOrderedSet *)orderedSet
2228  {
2229      id *objectsToRemove = malloc([self count] * sizeof(id));
2230      if (objectsToRemove == NULL)
2231      {
2232          [NSException raise:NSMallocException format:@"Could not allocate buffer"];
2233          return;
2234      }
2235  
2236      NSUInteger removalCount = 0;
2237  
2238      for (id obj in self)
2239      {
2240          if (![orderedSet containsObject:obj])
2241          {
2242              objectsToRemove[removalCount++] = obj;
2243          }
2244      }
2245  
2246      [self _mutate];
2247  
2248      for (NSUInteger idx = removalCount; idx > 0; idx--)
2249      {
2250          [self removeObjectAtIndex:idx - 1];
2251      }
2252  
2253      free(objectsToRemove);
2254  }
2255  
2256  - (void)minusOrderedSet:(NSOrderedSet *)orderedSet
2257  {
2258      [self _mutate];
2259  
2260      for (id obj in orderedSet)
2261      {
2262          [self removeObject:obj];
2263      }
2264  }
2265  
2266  - (void)unionOrderedSet:(NSOrderedSet *)orderedSet
2267  {
2268      [self _mutate];
2269  
2270      for (id obj in orderedSet)
2271      {
2272          [self addObject:obj];
2273      }
2274  }
2275  
2276  - (void)intersectSet:(NSSet *)set
2277  {
2278      id *objectsToRemove = malloc([self count] * sizeof(id));
2279  
2280      if (objectsToRemove == NULL)
2281      {
2282          [NSException raise:NSMallocException format:@"Could not allocate buffer"];
2283          return;
2284      }
2285  
2286      NSUInteger removalCount = 0;
2287  
2288      for (id obj in self)
2289      {
2290          if (![set containsObject:obj])
2291          {
2292              objectsToRemove[removalCount++] = obj;
2293          }
2294      }
2295  
2296      [self _mutate];
2297  
2298      for (NSUInteger idx = removalCount; idx > 0; idx--)
2299      {
2300          [self removeObjectAtIndex:idx - 1];
2301      }
2302  
2303      free(objectsToRemove);
2304  }
2305  
2306  - (void)minusSet:(NSSet *)set
2307  {
2308      [self _mutate];
2309  
2310      for (id obj in set)
2311      {
2312          [self removeObject:obj];
2313      }
2314  }
2315  
2316  - (void)unionSet:(NSSet *)set
2317  {
2318      [self _mutate];
2319  
2320      for (id obj in set)
2321      {
2322          [self addObject:obj];
2323      }
2324  }
2325  
2326  #if NS_BLOCKS_AVAILABLE
2327  
2328  - (void)sortUsingComparator:(NSComparator)comparator
2329  {
2330      if (comparator == nil)
2331      {
2332          [NSException raise:NSInvalidArgumentException format:@"Comparator cannot be nil"];
2333          return;
2334      }
2335  
2336      NSRange range = NSMakeRange(0, [self count]);
2337      [self sortRange:range options:0 usingComparator:comparator];
2338  }
2339  
2340  - (void)sortWithOptions:(NSSortOptions)options usingComparator:(NSComparator)comparator
2341  {
2342      if (comparator == nil)
2343      {
2344          [NSException raise:NSInvalidArgumentException format:@"Comparator cannot be nil"];
2345          return;
2346      }
2347  
2348      NSRange range = NSMakeRange(0, [self count]);
2349      [self sortRange:range options:options usingComparator:comparator];
2350  }
2351  
2352  - (void)sortRange:(NSRange)range options:(NSSortOptions)options usingComparator:(NSComparator)comparator
2353  {
2354      if (comparator == nil)
2355      {
2356          [NSException raise:NSInvalidArgumentException format:@"Comparator cannot be nil"];
2357          return;
2358      }
2359  
2360      NSUInteger count = [self count];
2361  
2362      if (NSMaxRange(range) > count)
2363      {
2364          [NSException raise:NSInvalidArgumentException format:@"Range out of bounds of ordered set"];
2365          return;
2366      }
2367  
2368      if (range.length == 0)
2369      {
2370          return;
2371      }
2372  
2373      CFIndex *indexes = malloc(range.length * sizeof(*indexes));
2374  
2375      if (indexes == NULL)
2376      {
2377          [NSException raise:NSMallocException format:@"Could not allocate buffer"];
2378          return;
2379      }
2380  
2381      id *objects = malloc(range.length * sizeof(id));
2382  
2383      if (objects == NULL)
2384      {
2385          free(indexes);
2386          [NSException raise:NSMallocException format:@"Could not allocate buffer"];
2387          return;
2388      }
2389  
2390      [self getObjects:objects range:range];
2391  
2392      CFSortIndexes(indexes, range.length, options, ^(CFIndex idx1, CFIndex idx2) {
2393          return (CFComparisonResult)comparator(objects[idx1], objects[idx2]);
2394      });
2395      
2396      assert(sizeof(id) == sizeof(CFIndex));
2397      
2398      for (int i = 0; i < count; i++)
2399      {
2400          indexes[i] = (CFIndex)objects[indexes[i]]; // re-use indexes allocation
2401      }
2402      
2403      [self replaceObjectsInRange:range withObjects:(id*)indexes count:range.length];
2404  
2405      free(indexes);
2406      free(objects);
2407  }
2408  
2409  #endif // NS_BLOCK_AVAILABLE
2410  
2411  - (void)rollObjectsInRange:(NSRange)range by:(NSInteger)rollAmount
2412  {
2413      if (NSMaxRange(range) > [self count])
2414      {
2415          [NSException raise:NSRangeException format:@"Range out of bounds of ordered set"];
2416          return;
2417      }
2418  
2419      if (range.length == 0)
2420      {
2421          return;
2422      }
2423  
2424      rollAmount %= range.length;
2425  
2426      if (rollAmount == 0)
2427      {
2428          return;
2429      }
2430  
2431      id *objects = malloc(range.length * sizeof(id));
2432  
2433      if (objects == NULL)
2434      {
2435          [NSException raise:NSMallocException format:@"Could not allocate buffer"];
2436          return;
2437      }
2438  
2439      NSRange leftRange = NSMakeRange(range.location, range.length - rollAmount);
2440      NSRange rightRange = NSMakeRange(NSMaxRange(leftRange), rollAmount);
2441  
2442      id *rightObjects = objects;
2443      id *leftObjects = objects + rightRange.length;
2444  
2445      [self getObjects:leftObjects range:leftRange];
2446      [self getObjects:rightObjects range:rightRange];
2447  
2448      [self _mutate];
2449  
2450      [self removeObjectsInRange:range];
2451      [self insertObjects:objects count:range.length atIndex:range.location];
2452  
2453      for (NSUInteger idx = 0; idx < range.length; idx++)
2454      {
2455          [objects[idx] release];
2456      }
2457  
2458      free(objects);
2459  }
2460  
2461  - (void)replaceObjectAtIndex:(NSUInteger)idx withObject:(id)object
2462  {
2463      NSRequestConcreteImplementation();
2464  }
2465  
2466  - (void)replaceObject:(id)object
2467  {
2468      if (object == nil)
2469      {
2470          [NSException raise:NSInvalidArgumentException format:@"Cannot add nil to ordered set"];
2471          return;
2472      }
2473  
2474      NSUInteger idx = [self indexOfObject:object];
2475  
2476      if (idx == NSNotFound)
2477      {
2478          return;
2479      }
2480  
2481      [self _mutate];
2482  
2483      [self replaceObjectAtIndex:idx withObject:object];
2484  }
2485  
2486  - (void)replaceObject:(id)object inRange:(NSRange)range
2487  {
2488      if (object == nil)
2489      {
2490          [NSException raise:NSInvalidArgumentException format:@"Cannot add nil to ordered set"];
2491          return;
2492      }
2493  
2494      if (NSMaxRange(range) > [self count])
2495      {
2496          [NSException raise:NSRangeException format:@"Range out of bounds of ordered set"];
2497          return;
2498      }
2499  
2500      NSUInteger idx = [self indexOfObject:object inRange:range];
2501  
2502      if (idx == NSNotFound)
2503      {
2504          return;
2505      }
2506  
2507      [self _mutate];
2508  
2509      [self replaceObjectAtIndex:idx withObject:object];
2510  }
2511  
2512  - (void)replaceObjectsInRange:(NSRange)range withObjects:(const id [])objects count:(NSUInteger)count
2513  {
2514      if (objects == NULL && count > 0)
2515      {
2516          [NSException raise:NSInvalidArgumentException format:@"Cannot insert NULL objects with nonzero count into ordered set"];
2517          return;
2518      }
2519  
2520      if (NSMaxRange(range) > [self count])
2521      {
2522          [NSException raise:NSRangeException format:@"Range out of bounds of ordered set"];
2523          return;
2524      }
2525  
2526      if (count == 0 && range.length == 0)
2527      {
2528          return;
2529      }
2530  
2531      for (NSUInteger idx = 0; idx < count; idx++)
2532      {
2533          if (objects[idx] == nil)
2534          {
2535              [NSException raise:NSInvalidArgumentException format:@"Cannot insert nil into ordered set"];
2536              return;
2537          }
2538      }
2539  
2540      for (NSUInteger idx = 0; idx < count; idx++)
2541      {
2542          [objects[idx] retain];
2543      }
2544  
2545      [self _mutate];
2546  
2547      [self removeObjectsInRange:range];
2548      [self insertObjects:objects count:count atIndex:range.location];
2549  
2550      for (NSUInteger idx = 0; idx < count; idx++)
2551      {
2552          [objects[idx] release];
2553      }
2554  }
2555  
2556  - (void)replaceObjectsAtIndexes:(NSIndexSet *)indexes withObjects:(NSArray *)objectArray
2557  {
2558      NSUInteger indexCount = [indexes count];
2559  
2560      if (indexCount != [objectArray count])
2561      {
2562          [NSException raise:NSInvalidArgumentException format:@"Different numbers of indexes and objects"];
2563          return;
2564      }
2565  
2566      if (indexCount == 0)
2567      {
2568          return;
2569      }
2570  
2571      if ([indexes lastIndex] >= [self count])
2572      {
2573          [NSException raise:NSRangeException format:@"Range out of bounds of ordered set"];
2574          return;
2575      }
2576  
2577      id *objects = malloc(indexCount * sizeof(id));
2578      if (objects == NULL)
2579      {
2580          [NSException raise:NSMallocException format:@"Could not allocate buffer"];
2581          return;
2582      }
2583  
2584      [objectArray getObjects:objects range:NSMakeRange(0, indexCount)];
2585  
2586      for (NSUInteger idx = 0; idx < indexCount; idx++)
2587      {
2588          if (objects[idx] == nil)
2589          {
2590              free(objects);
2591              [NSException raise:NSInvalidArgumentException format:@"Cannot add nil to ordered set"];
2592              return;
2593          }
2594      }
2595  
2596      for (NSUInteger idx = 0; idx < indexCount; idx++)
2597      {
2598          [objects[idx] retain];
2599      }
2600  
2601      [self _mutate];
2602  
2603      [indexes enumerateRangesWithOptions:NSEnumerationReverse usingBlock:^(NSRange range, BOOL *stop) {
2604          [self removeObjectsInRange:range];
2605      }];
2606  
2607      __block id *currentObjectPtr = objects;
2608      [indexes enumerateRangesUsingBlock:^(NSRange range, BOOL *stop) {
2609          [self insertObjects:currentObjectPtr count:range.length atIndex:range.location];
2610          currentObjectPtr += range.length;
2611      }];
2612  
2613      for (NSUInteger idx = 0; idx < indexCount; idx++)
2614      {
2615          [objects[idx] release];
2616      }
2617  
2618      free(objects);
2619  }
2620  
2621  - (void)replaceObjectsInRange:(NSRange)range withObjectsFromSet:(NSSet *)set
2622  {
2623      if (NSMaxRange(range) > [self count])
2624      {
2625          [NSException raise:NSRangeException format:@"Range out of bounds of ordered set"];
2626          return;
2627      }
2628  
2629      NSUInteger setCount = [set count];
2630  
2631      if (range.length == 0 && setCount == 0)
2632      {
2633          return;
2634      }
2635  
2636      id *objects = malloc(setCount * sizeof(id));
2637      if (objects == NULL)
2638      {
2639          [NSException raise:NSMallocException format:@"Failed to allocate buffer"];
2640          return;
2641      }
2642  
2643      [set getObjects:objects count:setCount];
2644  
2645      [self _mutate];
2646      [self replaceObjectsInRange:range withObjects:objects count:setCount];
2647  
2648      free(objects);
2649  }
2650  
2651  - (void)replaceObjectsInRange:(NSRange)range withObjectsFromOrderedSet:(NSOrderedSet *)orderedSet
2652  {
2653      if (NSMaxRange(range) > [self count])
2654      {
2655          [NSException raise:NSRangeException format:@"Range out of bounds of ordered set"];
2656          return;
2657      }
2658  
2659      NSUInteger orderedSetCount = [orderedSet count];
2660  
2661      if (range.length == 0 && orderedSetCount == 0)
2662      {
2663          return;
2664      }
2665  
2666      id *objects = malloc(orderedSetCount * sizeof(id));
2667      if (objects == NULL)
2668      {
2669          [NSException raise:NSMallocException format:@"Failed to allocate buffer"];
2670          return;
2671      }
2672  
2673      [orderedSet getObjects:objects range:NSMakeRange(0, orderedSetCount)];
2674  
2675      [self _mutate];
2676      [self replaceObjectsInRange:range withObjects:objects count:orderedSetCount];
2677  
2678      free(objects);
2679  }
2680  
2681  - (void)replaceObjectsInRange:(NSRange)range withObjectsFromOrderedSet:(NSOrderedSet *)orderedSet range:(NSRange)newRange
2682  {
2683      if (NSMaxRange(range) > [self count])
2684      {
2685          [NSException raise:NSRangeException format:@"Range out of bounds of ordered set"];
2686          return;
2687      }
2688  
2689      NSUInteger orderedSetCount = [orderedSet count];
2690  
2691      if (NSMaxRange(newRange) > orderedSetCount)
2692      {
2693          [NSException raise:NSRangeException format:@"Range out of bounds of ordered set"];
2694          return;
2695      }
2696  
2697      if (range.length == 0 && orderedSetCount == 0)
2698      {
2699          return;
2700      }
2701  
2702      id *objects = malloc(orderedSetCount * sizeof(id));
2703      if (objects == NULL)
2704      {
2705          [NSException raise:NSMallocException format:@"Failed to allocate buffer"];
2706          return;
2707      }
2708  
2709      [orderedSet getObjects:objects range:newRange];
2710  
2711      [self _mutate];
2712      [self replaceObjectsInRange:range withObjects:objects count:orderedSetCount];
2713  
2714      free(objects);
2715  }
2716  
2717  - (void)replaceObjectsInRange:(NSRange)range withObjectsFromArray:(NSArray *)array
2718  {
2719      if (NSMaxRange(range) > [self count])
2720      {
2721          [NSException raise:NSRangeException format:@"Range out of bounds of ordered set"];
2722          return;
2723      }
2724  
2725      NSUInteger arrayCount = [array count];
2726  
2727      if (range.length == 0 && arrayCount == 0)
2728      {
2729          return;
2730      }
2731  
2732      id *objects = malloc(arrayCount * sizeof(id));
2733      if (objects == NULL)
2734      {
2735          [NSException raise:NSMallocException format:@"Failed to allocate buffer"];
2736          return;
2737      }
2738  
2739      [array getObjects:objects range:NSMakeRange(0, arrayCount)];
2740  
2741      [self _mutate];
2742      [self replaceObjectsInRange:range withObjects:objects count:arrayCount];
2743  
2744      free(objects);
2745  }
2746  
2747  - (void)replaceObjectsInRange:(NSRange)range withObjectsFromArray:(NSArray *)array range:(NSRange)newRange
2748  {
2749      if (NSMaxRange(range) > [self count])
2750      {
2751          [NSException raise:NSRangeException format:@"Range out of bounds of ordered set"];
2752          return;
2753      }
2754  
2755      NSUInteger arrayCount = [array count];
2756  
2757      if (NSMaxRange(newRange) > arrayCount)
2758      {
2759          [NSException raise:NSRangeException format:@"Range out of bounds of array"];
2760          return;
2761      }
2762  
2763      if (range.length == 0 && arrayCount == 0)
2764      {
2765          return;
2766      }
2767  
2768      id *objects = malloc(arrayCount * sizeof(id));
2769      if (objects == NULL)
2770      {
2771          [NSException raise:NSMallocException format:@"Failed to allocate buffer"];
2772          return;
2773      }
2774  
2775      [array getObjects:objects range:newRange];
2776  
2777      [self _mutate];
2778      [self replaceObjectsInRange:range withObjects:objects count:arrayCount];
2779  
2780      free(objects);
2781  }
2782  
2783  - (void)insertObject:(id)object atIndex:(NSUInteger)idx
2784  {
2785      NSRequestConcreteImplementation();
2786  }
2787  
2788  - (void)insertObjects:(NSArray *)array atIndexes:(NSIndexSet *)indexes
2789  {
2790      if (indexes == nil)
2791      {
2792          [NSException raise:NSInvalidArgumentException format:@"Index set cannot be nil"];
2793          return;
2794      }
2795  
2796      NSUInteger indexCount = [indexes count];
2797      NSUInteger arrayCount = [array count];
2798  
2799      if (indexCount > 0 && [indexes lastIndex] >= ([self count] + indexCount))
2800      {
2801          [NSException raise:NSInvalidArgumentException format:@"Index set out of bounds of ordered set"];
2802          return;
2803      }
2804  
2805      if (indexCount != arrayCount)
2806      {
2807          [NSException raise:NSInvalidArgumentException format:@"Differing numbers of indexes and array elements"];
2808          return;
2809      }
2810  
2811      if (arrayCount == 0)
2812      {
2813          return;
2814      }
2815  
2816      id *objects = malloc(arrayCount * sizeof(id));
2817  
2818      if (objects == NULL)
2819      {
2820          [NSException raise:NSMallocException format:@"Failed to allocate buffer"];
2821          return;
2822      }
2823  
2824      NSRange range = NSMakeRange(0, arrayCount);
2825      [array getObjects:objects range:range];
2826  
2827      [self _mutate];
2828  
2829      __block id *currentObjectPtr = objects;
2830      [indexes enumerateRangesUsingBlock:^(NSRange range, BOOL *stop) {
2831          [self insertObjects:currentObjectPtr count:range.length atIndex:range.location];
2832          currentObjectPtr += range.length;
2833      }];
2834      
2835      free(objects);
2836  }
2837  
2838  - (void)insertObjectsFromSet:(NSSet *)set atIndex:(NSUInteger)idx
2839  {
2840      if (idx > [self count])
2841      {
2842          [NSException raise:NSInvalidArgumentException format:@"Index out of bounds of ordered set"];
2843          return;
2844      }
2845  
2846      NSUInteger count = [set count];
2847  
2848      if (count == 0)
2849      {
2850          return;
2851      }
2852  
2853      id *objects = malloc(count * sizeof(id));
2854  
2855      if (objects == NULL)
2856      {
2857          [NSException raise:NSMallocException format:@"Failed to allocate buffer"];
2858          return;
2859      }
2860  
2861      [set getObjects:objects count:count];
2862  
2863      [self _mutate];
2864      [self insertObjects:objects count:count atIndex:idx];
2865  
2866      free(objects);
2867  }
2868  
2869  - (void)insertObjectsFromOrderedSet:(NSOrderedSet *)orderedSet atIndex:(NSUInteger)idx
2870  {
2871      if (idx > [self count])
2872      {
2873          [NSException raise:NSInvalidArgumentException format:@"Index out of bounds of ordered set"];
2874          return;
2875      }
2876  
2877      NSUInteger count = [orderedSet count];
2878  
2879      if (count == 0)
2880      {
2881          return;
2882      }
2883  
2884      id *objects = malloc(count * sizeof(id));
2885  
2886      if (objects == NULL)
2887      {
2888          [NSException raise:NSMallocException format:@"Failed to allocate buffer"];
2889          return;
2890      }
2891  
2892      NSRange range = NSMakeRange(0, count);
2893      [orderedSet getObjects:objects range:range];
2894  
2895      [self _mutate];
2896      [self insertObjects:objects count:count atIndex:idx];
2897  
2898      free(objects);
2899  }
2900  
2901  - (void)insertObjectsFromOrderedSet:(NSOrderedSet *)orderedSet range:(NSRange)range atIndex:(NSUInteger)idx
2902  {
2903      if (idx > [self count])
2904      {
2905          [NSException raise:NSInvalidArgumentException format:@"Index out of bounds of ordered set"];
2906          return;
2907      }
2908  
2909      NSUInteger count = [orderedSet count];
2910  
2911      if (count == 0)
2912      {
2913          return;
2914      }
2915  
2916      id *objects = malloc(count * sizeof(id));
2917  
2918      if (objects == NULL)
2919      {
2920          [NSException raise:NSMallocException format:@"Failed to allocate buffer"];
2921          return;
2922      }
2923  
2924      [orderedSet getObjects:objects range:range];
2925  
2926      [self _mutate];
2927      [self insertObjects:objects count:count atIndex:idx];
2928  
2929      free(objects);
2930  }
2931  
2932  - (void)insertObjectsFromArray:(NSArray *)array atIndex:(NSUInteger)idx
2933  {
2934      if (idx > [self count])
2935      {
2936          [NSException raise:NSInvalidArgumentException format:@"Index out of bounds of ordered set"];
2937          return;
2938      }
2939  
2940      NSUInteger count = [array count];
2941  
2942      if (count == 0)
2943      {
2944          return;
2945      }
2946  
2947      id *objects = malloc(count * sizeof(id));
2948  
2949      if (objects == NULL)
2950      {
2951          [NSException raise:NSMallocException format:@"Failed to allocate buffer"];
2952          return;
2953      }
2954  
2955      NSRange range = NSMakeRange(0, count);
2956      [array getObjects:objects range:range];
2957  
2958      [self _mutate];
2959      [self insertObjects:objects count:count atIndex:idx];
2960  
2961      free(objects);
2962  }
2963  
2964  - (void)insertObjectsFromArray:(NSArray *)array range:(NSRange)range atIndex:(NSUInteger)idx
2965  {
2966      if (idx > [self count])
2967      {
2968          [NSException raise:NSInvalidArgumentException format:@"Index out of bounds of ordered set"];
2969          return;
2970      }
2971  
2972      NSUInteger count = [array count];
2973  
2974      if (count == 0)
2975      {
2976          return;
2977      }
2978  
2979      id *objects = malloc(count * sizeof(id));
2980  
2981      if (objects == NULL)
2982      {
2983          [NSException raise:NSMallocException format:@"Failed to allocate buffer"];
2984          return;
2985      }
2986  
2987      [array getObjects:objects range:range];
2988  
2989      [self _mutate];
2990      [self insertObjects:objects count:count atIndex:idx];
2991  
2992      free(objects);
2993  }
2994  
2995  - (void)insertObjects:(const id *)objects count:(NSUInteger)count atIndex:(NSUInteger)idx
2996  {
2997      if (objects == NULL && count > 0)
2998      {
2999          [NSException raise:NSInvalidArgumentException format:@"Cannot insert NULL objects with nonzero count into ordered set"];
3000          return;
3001      }
3002  
3003      if (idx > [self count])
3004      {
3005          [NSException raise:NSInvalidArgumentException format:@"Index out of bounds of ordered set"];
3006          return;
3007      }
3008  
3009      if (count == 0)
3010      {
3011          return;
3012      }
3013  
3014      [self _mutate];
3015      NSUInteger countBeforeLoop = [self count];
3016      for (NSUInteger objIdx = 0; objIdx < count; objIdx++)
3017      {
3018          id obj = objects[objIdx];
3019          if (obj == nil)
3020          {
3021              [NSException raise:NSInvalidArgumentException format:@"Cannot insert nil into ordered set"];
3022              return;
3023          }
3024          NSUInteger index = idx + [self count] - countBeforeLoop;
3025          [self insertObject:obj atIndex:index];
3026      }
3027  }
3028  
3029  - (void)_mutate
3030  {
3031  }
3032  
3033  @end
3034  
3035  @implementation __NSPlaceholderOrderedSet
3036  
3037  static __NSPlaceholderOrderedSet *immutablePlaceholder = nil;
3038  static __NSPlaceholderOrderedSet *mutablePlaceholder = nil;
3039  
3040  + (id)immutablePlaceholder
3041  {
3042      static dispatch_once_t once = 0L;
3043      dispatch_once(&once, ^{
3044          immutablePlaceholder = [__NSPlaceholderOrderedSet allocWithZone:nil];
3045      });
3046      return immutablePlaceholder;
3047  }
3048  
3049  + (id)mutablePlaceholder
3050  {
3051      static dispatch_once_t once = 0L;
3052      dispatch_once(&once, ^{
3053          mutablePlaceholder = [__NSPlaceholderOrderedSet allocWithZone:nil];
3054      });
3055      return mutablePlaceholder;
3056  }
3057  
3058  - (id)init
3059  {
3060      if (self == immutablePlaceholder)
3061      {
3062          return [self initWithObjects:NULL count:0];
3063      }
3064      else if (self == mutablePlaceholder)
3065      {
3066          return [self initWithCapacity:0];
3067      }
3068      else
3069      {
3070          DEBUG_BREAK();
3071          return nil;
3072      }
3073  }
3074  
3075  - (id)initWithCapacity:(NSUInteger)capacity
3076  {
3077      if (self != mutablePlaceholder)
3078      {
3079          DEBUG_BREAK();
3080          return nil;
3081      }
3082  
3083      NSCapacityCheck(capacity, 0x40000000, @"Please rethink the size of the capacity of the ordered set you are creating: %d seems a bit excessive", capacity);
3084      return (__NSPlaceholderOrderedSet *)[__NSOrderedSetM __new:NULL :capacity :NO];
3085  }
3086  
3087  - (id)initWithObjects:(const id *)objects count:(NSUInteger)count
3088  {
3089      if (self != immutablePlaceholder && self != mutablePlaceholder)
3090      {
3091          [self release];
3092          [NSException raise:NSInvalidArgumentException format:@"Cannot reinit ordered set"];
3093          return nil;
3094      }
3095  
3096      if (objects == NULL && count > 0)
3097      {
3098          [self release];
3099          [NSException raise:NSInvalidArgumentException format:@"Cannot init ordered set with NULL objects and nonzero count"];
3100          return nil;
3101      }
3102  
3103      for (NSUInteger idx = 0; idx < count; idx++)
3104      {
3105          id obj = objects[idx];
3106          if (obj == nil)
3107          {
3108              [self release];
3109              [NSException raise:NSInvalidArgumentException format:@"Cannot init ordered set with nil object"];
3110              return nil;
3111          }
3112          [obj retain];
3113      }
3114  
3115      if (self == immutablePlaceholder)
3116      {
3117          if (count == 0)
3118          {
3119              static __NSOrderedSetI *__NSOrderedSetI0 = nil;
3120              static dispatch_once_t once = 0L;
3121              dispatch_once(&once, ^{
3122                  __NSOrderedSetI0 = [__NSOrderedSetI __new:NULL :0 :NO];
3123              });
3124              return (__NSPlaceholderOrderedSet *)[__NSOrderedSetI0 retain];
3125          }
3126          else
3127          {
3128              return (__NSPlaceholderOrderedSet *)[__NSOrderedSetI __new:objects :count :NO];
3129          }
3130      }
3131      else
3132      {
3133          return (__NSPlaceholderOrderedSet *)[__NSOrderedSetM __new:objects :count :NO];
3134      }
3135  }
3136  
3137  SINGLETON_RR()
3138  
3139  - (void)replaceObjectAtIndex:(NSUInteger)idx withObject:(id)object
3140  {
3141      [NSException raise:NSInvalidArgumentException format:@"Message sent to uninitialized ordered set"];
3142      return;
3143  }
3144  
3145  - (void)removeObjectAtIndex:(NSUInteger)idx
3146  {
3147      [NSException raise:NSInvalidArgumentException format:@"Message sent to uninitialized ordered set"];
3148      return;
3149  }
3150  
3151  - (void)insertObject:(id)object atIndex:(NSUInteger)idx
3152  {
3153      [NSException raise:NSInvalidArgumentException format:@"Message sent to uninitialized ordered set"];
3154      return;
3155  }
3156  
3157  - (id)objectAtIndex:(NSUInteger)idx
3158  {
3159      [NSException raise:NSInvalidArgumentException format:@"Message sent to uninitialized ordered set"];
3160      return nil;
3161  }
3162  
3163  - (NSUInteger)indexOfObject:(id)object
3164  {
3165      [NSException raise:NSInvalidArgumentException format:@"Message sent to uninitialized ordered set"];
3166      return 0;
3167  }
3168  
3169  - (NSUInteger)count
3170  {
3171      [NSException raise:NSInvalidArgumentException format:@"Message sent to uninitialized ordered set"];
3172      return 0;
3173  }
3174  
3175  @end
3176  
3177  @implementation __NSOrderedSetI
3178  
3179  // Use the same capacities and sizes as CFBasicHash.c
3180  
3181  
3182  + (id)allocWithZone:(NSZone *)zone
3183  {
3184      return (__NSOrderedSetI *)[__NSPlaceholderOrderedSet allocWithZone:zone];
3185  }
3186  
3187  + (id)__new:(const id *)objects :(NSUInteger)count :(BOOL)tbd
3188  {
3189      NSUInteger sizeIdx = 0;
3190      NSUInteger primeSize = 0;
3191  
3192      id *uniqueObjects = NSBasicHashAllocate(count, 2 * sizeof(id), &primeSize, &sizeIdx, NO);
3193  
3194      if (uniqueObjects == NULL)
3195      {
3196          [NSException raise:NSMallocException format:@"Failed to allocate buffer"];
3197          return nil;
3198      }
3199  
3200      NSUInteger *uniqueIndexes = (NSUInteger *)uniqueObjects + primeSize;
3201  
3202      NSUInteger uniqueCount = 0;
3203  
3204      for (NSUInteger idx = 0; idx < count; idx++)
3205      {
3206          id obj = objects[idx];
3207          NSUInteger hash = [obj hash];
3208          NSUInteger bucket = hash % primeSize;
3209  
3210          if (uniqueIndexes[bucket] == 0)
3211          {
3212              uniqueIndexes[bucket] = idx + 1;
3213              uniqueObjects[uniqueCount++] = obj;
3214              continue;
3215          }
3216  
3217          BOOL unique = YES;
3218          for (NSUInteger uniqueIdx = 0; uniqueIdx < uniqueCount; uniqueIdx++)
3219          {
3220              id uniqueObj = uniqueObjects[uniqueIdx];
3221  
3222              if (uniqueObj == nil)
3223              {
3224                  continue;
3225              }
3226  
3227              if (obj == uniqueObj || (hash == [uniqueObj hash] && [obj isEqual:uniqueObj]))
3228              {
3229                  unique = NO;
3230                  break;
3231              }
3232          }
3233  
3234          if (unique)
3235          {
3236              uniqueObjects[uniqueCount++] = obj;
3237          }
3238      }
3239  
3240      size_t extraBytes = uniqueCount * sizeof(id) + primeSize * sizeof(NSUInteger);
3241      __NSOrderedSetI *orderedSet = ___CFAllocateObject2(self, extraBytes);
3242  
3243      id *indexedIvarObjects = object_getIndexedIvars(orderedSet);
3244      memmove(indexedIvarObjects, uniqueObjects, uniqueCount * sizeof(id));
3245  
3246      NSUInteger *indexedIvarIndexes = (NSUInteger *)indexedIvarObjects + uniqueCount;
3247      memmove(indexedIvarIndexes, uniqueIndexes, primeSize * sizeof(NSUInteger));
3248  
3249      orderedSet->_used = uniqueCount;
3250      orderedSet->_szidx = sizeIdx;
3251  
3252      NSBasicHashDeallocate(uniqueObjects);
3253  
3254      return orderedSet;
3255  }
3256  
3257  + (BOOL)automaticallyNotifiesObserversForKey:(NSString *)key
3258  {
3259      return NO;
3260  }
3261  
3262  - (void)dealloc
3263  {
3264      if (self == (__NSOrderedSetI *)immutablePlaceholder)
3265      {
3266          DEBUG_BREAK();
3267          [super dealloc];
3268      }
3269  
3270      id *objects = object_getIndexedIvars(self);
3271  
3272      NSUInteger count = [self count];
3273  
3274      for (NSUInteger idx = 0; idx < count; idx++)
3275      {
3276          CFRelease(objects[idx]);
3277      }
3278  
3279      [super dealloc];
3280  }
3281  
3282  - (id)copyWithZone:(NSZone *)zone
3283  {
3284      return [self retain];
3285  }
3286  
3287  - (void)enumerateObjectsWithOptions:(NSEnumerationOptions)options usingBlock:(void (^)(id obj, NSUInteger idx, BOOL *stop))block
3288  {
3289      if (block == nil)
3290      {
3291          [NSException raise:NSInvalidArgumentException format:@"Block must not be nil"];
3292          return;
3293      }
3294  
3295      NSUInteger count = [self count];
3296      id *objects = object_getIndexedIvars(self);
3297  
3298      if ((options & NSEnumerationConcurrent) != 0)
3299      {
3300          __block BOOL stop = NO;
3301  
3302          dispatch_queue_t queue = dispatch_get_global_queue(DISPATCH_QUEUE_PRIORITY_DEFAULT, 0);
3303  
3304          void (^dispatchBlock)(size_t);
3305  
3306          if ((options & NSEnumerationReverse) != 0)
3307          {
3308              dispatchBlock = ^(size_t iter) {
3309                  if (!stop)
3310                  {
3311                      NSUInteger idx = count - iter - 1;
3312                      id obj = objects[idx];
3313                      block(obj, idx, &stop);
3314                  }
3315              };
3316          }
3317          else
3318          {
3319              dispatchBlock = ^(size_t idx) {
3320                  if (!stop)
3321                  {
3322                      id obj = objects[idx];
3323                      block(obj, idx, &stop);
3324                  }
3325              };
3326          }
3327  
3328          dispatch_apply(count, queue, dispatchBlock);
3329      }
3330      else
3331      {
3332          BOOL stop = NO;
3333          if ((options & NSEnumerationReverse) != 0)
3334          {
3335              for (NSUInteger idx = count; idx > 0; idx--)
3336              {
3337                  if (stop)
3338                  {
3339                      return;
3340                  }
3341                  block(objects[idx - 1], idx - 1, &stop);
3342              }
3343          }
3344          else
3345          {
3346              for (NSUInteger idx = 0; idx < count; idx++)
3347              {
3348                  if (stop)
3349                  {
3350                      return;
3351                  }
3352                  block(objects[idx], idx, &stop);
3353              }
3354          }
3355      }
3356  }
3357  
3358  - (NSUInteger)countByEnumeratingWithState:(NSFastEnumerationState *)state objects:(id *)objects count:(NSUInteger)count
3359  {
3360      if (objects == NULL && count != 0)
3361      {
3362          [NSException raise:NSInvalidArgumentException format:@"Cannot enumerate into NULL buffer of nonzero length"];
3363          return 0;
3364      }
3365      
3366      if (state->state != 0)
3367      {
3368          return 0;
3369      }
3370      
3371      static const unsigned long const_mu = 1;
3372      state->mutationsPtr = (unsigned long *)&const_mu;
3373      state->state = -1;
3374      state->itemsPtr = object_getIndexedIvars(self);
3375  
3376      return _used;
3377  }
3378  
3379  - (void)getObjects:(id *)objects range:(NSRange)range
3380  {
3381      if (objects == NULL && range.length > 0)
3382      {
3383          [NSException raise:NSInvalidArgumentException format:@"Cannot place objects into NULL array"];
3384          return;
3385      }
3386  
3387      if (NSMaxRange(range) > [self count])
3388      {
3389          [NSException raise:NSRangeException format:@"Range exceeds bounds of ordered set"];
3390          return;
3391      }
3392  
3393      id *currentObjects = object_getIndexedIvars(self);
3394      memmove(objects, currentObjects + range.location, range.length * sizeof(id));
3395  }
3396  
3397  - (id)objectAtIndex:(NSUInteger)idx
3398  {
3399      if (idx >= [self count])
3400      {
3401          [NSException raise:NSRangeException format:@"Index out of bounds of ordered set"];
3402          return nil;
3403      }
3404  
3405      id *objects = object_getIndexedIvars(self);
3406      return objects[idx];
3407  }
3408  
3409  - (NSUInteger)indexOfObject:(id)object
3410  {
3411      if (object == nil)
3412      {
3413          return NSNotFound;
3414      }
3415  
3416      NSUInteger count = [self count];
3417  
3418      id *objects = object_getIndexedIvars(self);
3419      NSUInteger *indexes = (NSUInteger *)objects + count;
3420      NSUInteger hash = [object hash];
3421      NSUInteger bucket = hash % __NSBasicHashIPrimes[_szidx];
3422  
3423      NSUInteger possibleIdx = indexes[bucket];
3424  
3425      if (possibleIdx == 0)
3426      {
3427          return NSNotFound;
3428      }
3429  
3430      id possibleObject = objects[possibleIdx - 1];
3431  
3432      if (possibleObject == object || ([possibleObject hash] == hash && [possibleObject isEqual:object]))
3433      {
3434          return possibleIdx - 1;
3435      }
3436  
3437      NSUInteger foundIdx = NSNotFound;
3438  
3439      for (NSUInteger idx = 0; idx < count; idx++)
3440      {
3441          id obj = objects[idx];
3442          
3443          if (obj == nil)
3444          {
3445              continue;
3446          }
3447  
3448          if (obj == object || ([obj hash] == hash && [obj isEqual:object]))
3449          {
3450              foundIdx = idx;
3451              break;
3452          }
3453      }
3454  
3455      return foundIdx;
3456  }
3457  
3458  - (NSUInteger)count
3459  {
3460      return _used;
3461  }
3462  
3463  @end
3464  
3465  @implementation __NSOrderedSetM
3466  
3467  static Boolean __NSOrderedSetMEquateKeys(uintptr_t coll_key1, uintptr_t stack_key2)
3468  {
3469      if (coll_key1 == stack_key2)
3470      {
3471          return true;
3472      }
3473      return [(id)coll_key1 isEqual:(id)stack_key2] != NO;
3474  }
3475  
3476  static CFHashCode __NSOrderedSetMHashKey(uintptr_t stack_key)
3477  {
3478      return [(id)stack_key hash];
3479  }
3480  
3481  static uintptr_t __NSOrderedSetMRetainValue(CFAllocatorRef allocator, uintptr_t stack_value)
3482  {
3483      return stack_value;
3484  }
3485  
3486  static void __NSOrderedSetMReleaseValue(CFAllocatorRef allocator, uintptr_t stack_value)
3487  {
3488  }
3489  
3490  static uintptr_t __NSOrderedSetMGetIndirectKey(uintptr_t coll_value)
3491  {
3492      return coll_value;
3493  }
3494  
3495  static CFBasicHashCallbacks __NSOrderedSetMCallbacks = {
3496      .equateKeys = &__NSOrderedSetMEquateKeys,
3497      .hashKey = &__NSOrderedSetMHashKey,
3498      .retainValue = &__NSOrderedSetMRetainValue,
3499      .releaseValue = &__NSOrderedSetMReleaseValue,
3500      .getIndirectKey = &__NSOrderedSetMGetIndirectKey,
3501  };
3502  
3503  + (id)__new:(const id *)addr :(NSUInteger)count :(BOOL)cfRelease
3504  {
3505      __NSOrderedSetM *orderedSet = ___CFAllocateObject2(self, 0);
3506  
3507      CFOptionFlags flags = kCFBasicHashIndirectKeys | kCFBasicHashExponentialHashing;
3508      orderedSet->_set = CFBasicHashCreate(kCFAllocatorDefault, flags, &__NSOrderedSetMCallbacks);
3509      orderedSet->_array = [[NSMutableArray alloc] initWithCapacity:count];
3510      orderedSet->_used = 0;
3511  
3512      if (addr == NULL || count == 0)
3513      {
3514          return orderedSet;
3515      }
3516  
3517      for (NSUInteger idx = 0; idx < count; idx++)
3518      {
3519          const id object = addr[idx];
3520          CFBasicHashBucket bucket = CFBasicHashFindBucket(orderedSet->_set, (uintptr_t)object);
3521          if (bucket.count != 0)
3522          {
3523              continue;
3524          }
3525  
3526          orderedSet->_used++;
3527  
3528          CFBasicHashAddValue(orderedSet->_set, (uintptr_t)object, (uintptr_t)object);
3529  
3530          [orderedSet->_array _mutate];
3531          [orderedSet->_array addObject:object];
3532  
3533          if (cfRelease)
3534          {
3535              CFRelease(object);
3536          }
3537      }
3538  
3539      return orderedSet;
3540  }
3541  
3542  + (id)allocWithZone:(NSZone *)zone
3543  {
3544      return (__NSOrderedSetM *)[__NSPlaceholderOrderedSet allocWithZone:zone];
3545  }
3546  
3547  + (BOOL)automaticallyNotifiesObserversForKey:(NSString *)key
3548  {
3549      return NO;
3550  }
3551  
3552  - (void)dealloc
3553  {
3554      if (self == (__NSOrderedSetM *)mutablePlaceholder)
3555      {
3556          DEBUG_BREAK();
3557          [super dealloc];
3558      }
3559  
3560      if (_set != NULL)
3561      {
3562          CFRelease(_set);
3563      }
3564      if (_array != nil)
3565      {
3566          [_array release];
3567      }
3568  
3569      [super dealloc];
3570  }
3571  
3572  - (void)setObject:(id)object atIndex:(NSUInteger)idx
3573  {
3574      if (object == nil)
3575      {
3576          [NSException raise:NSInvalidArgumentException format:@"Cannot set to nil object in ordered set"];
3577          return;
3578      }
3579  
3580      if (idx > _used)
3581      {
3582          [NSException raise:NSRangeException format:@"Index out of range of ordered set"];
3583          return;
3584      }
3585  
3586      CFBasicHashBucket bucket = CFBasicHashFindBucket(_set, (uintptr_t)object);
3587      if (bucket.count != 0)
3588      {
3589          return;
3590      }
3591  
3592      if (idx == _used)
3593      {
3594          _used++;
3595  
3596          CFBasicHashAddValue(_set, (uintptr_t)object, (uintptr_t)object);
3597  
3598          [_array _mutate];
3599          [_array insertObject:object atIndex:idx];
3600      }
3601      else
3602      {
3603          id currentObject = [_array objectAtIndex:idx];
3604          CFBasicHashRemoveValue(_set, (uintptr_t)currentObject);
3605          CFBasicHashAddValue(_set, (uintptr_t)object, (uintptr_t)object);
3606  
3607          [_array _mutate];
3608          [_array replaceObjectAtIndex:idx withObject:object];
3609      }
3610  }
3611  
3612  - (void)replaceObjectAtIndex:(NSUInteger)idx withObject:(id)object
3613  {
3614      if (object == nil)
3615      {
3616          [NSException raise:NSInvalidArgumentException format:@"Cannot add nil object to ordered set"];
3617          return;
3618      }
3619  
3620      if (idx >= _used)
3621      {
3622          [NSException raise:NSRangeException format:@"Index out of range of ordered set"];
3623          return;
3624      }
3625  
3626      CFBasicHashBucket bucket = CFBasicHashFindBucket(_set, (uintptr_t)object);
3627      if (bucket.count != 0)
3628      {
3629          return;
3630      }
3631  
3632      id currentObject = [_array objectAtIndex:idx];
3633      CFBasicHashRemoveValue(_set, (uintptr_t)currentObject);
3634      CFBasicHashAddValue(_set, (uintptr_t)object, (uintptr_t)object);
3635  
3636      [_array _mutate];
3637      [_array replaceObjectAtIndex:idx withObject:object];
3638  }
3639  
3640  - (void)removeObjectAtIndex:(NSUInteger)idx
3641  {
3642      if (idx >= _used)
3643      {
3644          [NSException raise:NSRangeException format:@"Index out of range of ordered set"];
3645          return;
3646      }
3647  
3648      id object = [_array objectAtIndex:idx];
3649  
3650      _used--;
3651  
3652      CFBasicHashRemoveValue(_set, (uintptr_t)object);
3653  
3654      [_array _mutate];
3655      [_array removeObjectAtIndex:idx];
3656  }
3657  
3658  - (void)insertObject:(id)object atIndex:(NSUInteger)idx
3659  {
3660      if (object == nil)
3661      {
3662          [NSException raise:NSInvalidArgumentException format:@"Cannot add nil object to ordered set"];
3663          return;
3664      }
3665  
3666      if (idx > _used)
3667      {
3668          [NSException raise:NSRangeException format:@"Index out of range of ordered set"];
3669          return;
3670      }
3671  
3672      CFBasicHashBucket bucket = CFBasicHashFindBucket(_set, (uintptr_t)object);
3673      if (bucket.count != 0)
3674      {
3675          return;
3676      }
3677  
3678      _used++;
3679  
3680      CFBasicHashAddValue(_set, (uintptr_t)object, (uintptr_t)object);
3681  
3682      [_array _mutate];
3683      [_array insertObject:object atIndex:idx];
3684  }
3685  
3686  - (void)_mutate
3687  {
3688      [_array _mutate];
3689  }
3690  
3691  - (void)enumerateObjectsWithOptions:(NSEnumerationOptions)options usingBlock:(void (^)(id obj, NSUInteger idx, BOOL *stop))block
3692  {
3693      if (block == nil)
3694      {
3695          [NSException raise:NSInvalidArgumentException format:@"Block must not be nil"];
3696          return;
3697      }
3698  
3699      [_array enumerateObjectsWithOptions:options usingBlock:block];
3700  }
3701  
3702  - (NSUInteger)countByEnumeratingWithState:(NSFastEnumerationState *)state objects:(id *)objects count:(NSUInteger)count
3703  {
3704      if (objects == NULL && count != 0)
3705      {
3706          [NSException raise:NSInvalidArgumentException format:@"Cannot enumerate NULL objects with non-zero count"];
3707          return 0;
3708      }
3709  
3710      return [_array countByEnumeratingWithState:state objects:objects count:count];
3711  }
3712  
3713  - (void)getObjects:(id *)objects range:(NSRange)range
3714  {
3715      if (objects == NULL && range.length != 0)
3716      {
3717          [NSException raise:NSRangeException format:@"Cannot place objects into NULL array with non-zero length"];
3718          return;
3719      }
3720  
3721      if (NSMaxRange(range) > _used)
3722      {
3723          [NSException raise:NSRangeException format:@"Range out of bounds of ordered set"];
3724          return;
3725      }
3726  
3727      [_array getObjects:objects range:range];
3728  }
3729  
3730  - (id)objectAtIndex:(NSUInteger)idx
3731  {
3732      if (idx >= _used)
3733      {
3734          [NSException raise:NSRangeException format:@"Index out of range"];
3735          return nil;
3736      }
3737  
3738      return [_array objectAtIndex:idx];
3739  }
3740  
3741  - (NSUInteger)indexOfObject:(id)object
3742  {
3743      if (object == nil)
3744      {
3745          return NSNotFound;
3746      }
3747  
3748      CFBasicHashBucket bucket = CFBasicHashFindBucket(_set, (uintptr_t)object);
3749      if (bucket.count == 0)
3750      {
3751          return NSNotFound;
3752      }
3753  
3754      return [_array indexOfObjectIdenticalTo:object];
3755  }
3756  
3757  - (NSUInteger)count
3758  {
3759      return _used;
3760  }
3761  
3762  @end
3763  
3764  @implementation __NSOrderedSetArrayProxy
3765  
3766  - (id)initWithOrderedSet:(NSOrderedSet *)orderedSet
3767  {
3768      self = [super init];
3769      if (self != nil)
3770      {
3771          _orderedSet = [orderedSet retain];
3772      }
3773      return self;
3774  }
3775  
3776  - (void)dealloc
3777  {
3778      [_orderedSet release];
3779      [super dealloc];
3780  }
3781  
3782  - (id)copyWithZone:(NSZone *)zone
3783  {
3784      return [[NSArray alloc] initWithArray:self];
3785  }
3786  
3787  - (id)objectAtIndex:(NSUInteger)idx
3788  {
3789      return [_orderedSet objectAtIndex:idx];
3790  }
3791  
3792  - (NSUInteger)count
3793  {
3794      return [_orderedSet count];
3795  }
3796  
3797  @end
3798  
3799  @implementation __NSOrderedSetSetProxy
3800  
3801  - (id)initWithOrderedSet:(NSOrderedSet *)orderedSet
3802  {
3803      self = [super init];
3804      if (self != nil)
3805      {
3806          _orderedSet = [orderedSet retain];
3807      }
3808      return self;
3809  }
3810  
3811  - (void)dealloc
3812  {
3813      [_orderedSet release];
3814      [super dealloc];
3815  }
3816  
3817  - (id)copyWithZone:(NSZone *)zone
3818  {
3819      return [[NSSet alloc] initWithSet:self];
3820  }
3821  
3822  - (id)objectEnumerator
3823  {
3824      return [_orderedSet objectEnumerator];
3825  }
3826  
3827  - (id)member:(id)object
3828  {
3829      NSUInteger idx = [_orderedSet indexOfObject:object];
3830  
3831      if (idx == NSNotFound)
3832      {
3833          return nil;
3834      }
3835  
3836      return [_orderedSet objectAtIndex:idx];
3837  }
3838  
3839  - (NSUInteger)count
3840  {
3841      return [_orderedSet count];
3842  }
3843  
3844  @end
3845  
3846  @implementation __NSOrderedSetReversed
3847  
3848  - (id)initWithOrderedSet:(NSOrderedSet *)orderedSet
3849  {
3850      self = [super init];
3851      if (self != nil)
3852      {
3853          _orderedSet = [orderedSet copy];
3854          _cnt = [_orderedSet count];
3855      }
3856      return self;
3857  }
3858  
3859  - (void)dealloc
3860  {
3861      [_orderedSet release];
3862      [super dealloc];
3863  }
3864  
3865  - (id)objectAtIndex:(NSUInteger)idx
3866  {
3867      NSUInteger reversedIdx = _cnt - idx - 1;
3868      return [_orderedSet objectAtIndex:reversedIdx];
3869  }
3870  
3871  - (NSUInteger)indexOfObject:(id)object
3872  {
3873      NSUInteger idx = [_orderedSet indexOfObject:object];
3874      if (idx == NSNotFound)
3875      {
3876          return NSNotFound;
3877      }
3878      return _cnt - idx - 1;
3879  }
3880  
3881  - (NSUInteger)count
3882  {
3883      return _cnt;
3884  }
3885  
3886  @end
3887  
3888  @implementation __NSOrderedSetReverseEnumerator
3889  
3890  - (id)initWithObject:(id)object
3891  {
3892      _obj = [object retain];
3893      _idx = [_obj count];
3894      return nil;
3895  }
3896  
3897  - (void)dealloc
3898  {
3899      if (_obj != nil)
3900      {
3901          [_obj release];
3902      }
3903      [super dealloc];
3904  }
3905  
3906  - (id)nextObject
3907  {
3908      if (_obj == nil)
3909      {
3910          return nil;
3911      }
3912  
3913      if (_idx == 0)
3914      {
3915          [_obj release];
3916          _obj = nil;
3917      }
3918  
3919      _idx--;
3920  
3921      return [_obj objectAtIndex:_idx];
3922  }
3923  
3924  @end