JALSortedArray.h

// Copyright (c) 2014 James Lawton

#import <Foundation/Foundation.h>

/**
 * A mutable array that keeps itself sorted, according to a comparator.
 * This has similar guarantees to NSMutableArray. It is not thread safe.
 * Don't mutate this while enumerating.
 */
@interface JALSortedArray : NSObject <NSFastEnumeration, NSCopying>

- (instancetype)initWithComparator:(NSComparator)comparator;
- (instancetype)initWithArray:(id<NSFastEnumeration>)array comparator:(NSComparator)comparator;

@property (nonatomic, copy) NSComparator comparator;

- (id)objectAtIndex:(NSUInteger)idx;
- (id)objectAtIndexedSubscript:(NSUInteger)idx;
- (NSUInteger)count;

- (void)addObject:(id)obj;
- (void)addObjectsFromArray:(id<NSFastEnumeration>)array;

- (void)removeObject:(id)obj;
- (void)removeObjectAtIndex:(NSUInteger)idx;
- (void)removeAllObjects;

- (id)firstObject;
- (id)lastObject;

- (NSArray *)toArray;

@end

JALSortedArray.m

// Copyright (c) 2014 James Lawton

#import "JALSortedArray.h"

@interface JALSortedArray ()
@property (nonatomic, strong, readonly) NSMutableArray *backingArray;
@end

@implementation JALSortedArray

- (instancetype)initWithComparator:(NSComparator)comparator
{
    NSParameterAssert(comparator);
    self = [super init];
    if (self) {
        _comparator = [comparator copy];
        _backingArray = [NSMutableArray array];
        if (!_comparator || !_backingArray) {
            return nil;
        }
    }
    return self;
}

static id Enumerate(id<NSFastEnumeration> objects, id output)
{
    for (id obj in objects) {
        [output addObject:obj];
    }
    return output;
}

- (instancetype)initWithArray:(id<NSFastEnumeration>)array comparator:(NSComparator)comparator
{
    self = [self initWithComparator:comparator];
    if (self) {
        [self setArray:array];
    }
    return self;
}

- (instancetype)copyWithZone:(NSZone *)zone
{
    JALSortedArray *other = [[self.class alloc] initWithComparator:self.comparator];
    other->_backingArray = [self.backingArray mutableCopy];
    return other;
}

- (void)setComparator:(NSComparator)comparator
{
    NSParameterAssert(comparator);
    if (comparator && _comparator != comparator) {
        _comparator = [comparator copy];
        [self.backingArray sortUsingComparator:self.comparator];
    }
}

#pragma mark - Basics

- (id)objectAtIndex:(NSUInteger)idx
{
    return [self objectAtIndexedSubscript:idx];
}

- (id)objectAtIndexedSubscript:(NSUInteger)idx
{
    return self.backingArray[idx];
}

- (void)addObject:(id)obj
{
    NSUInteger idx = [self.backingArray
        indexOfObject:obj
        inSortedRange:NSMakeRange(0, self.backingArray.count)
        options:NSBinarySearchingInsertionIndex
        usingComparator:self.comparator];

    if (idx == NSNotFound) {
        NSAssert(NO, @"Insertion index not found.");
        idx = self.backingArray.count;
    }
    [self.backingArray insertObject:obj atIndex:idx];
}

- (void)addObjectsFromArray:(id<NSFastEnumeration>)array
{
    Enumerate(array, self);
}

- (NSUInteger)count
{
    return self.backingArray.count;
}

- (void)removeObject:(id)obj
{
    [self.backingArray removeObject:obj];
}

- (void)removeObjectAtIndex:(NSUInteger)idx
{
    [self.backingArray removeObjectAtIndex:idx];
}

- (void)removeAllObjects
{
    [self.backingArray removeAllObjects];
}

- (void)setArray:(id<NSFastEnumeration>)array
{
    [_backingArray removeAllObjects];
    Enumerate(array, _backingArray);
    [_backingArray sortUsingComparator:_comparator];
}

#pragma mark - NSFastEnumeration

- (NSUInteger)countByEnumeratingWithState:(NSFastEnumerationState *)state objects:(id __unsafe_unretained [])buffer count:(NSUInteger)len
{
    return [self.backingArray countByEnumeratingWithState:state objects:buffer count:len];
}

#pragma mark - Inessentials

- (id)firstObject
{
    return self.backingArray.firstObject;
}

- (id)lastObject
{
    return self.backingArray.lastObject;
}

- (NSArray *)toArray
{
    return [self.backingArray copy];
}

@end