// gcc -framework Foundation -O3 -g -o dictfind4 dictfind4.m

#import <Foundation/Foundation.h>


@interface Dict : NSObject
{
    NSArray *_wordPairs;
}
- (NSArray *)find:(NSString *)toFind;
@end

@implementation Dict
static NSInteger CaseInsensitiveCompare(id a, id b)
{
    return [a compare:b options:NSCaseInsensitiveSearch];
}
static NSInteger CaseInsensitiveComparePairs(id a, id b, void *ctx)
{
    return CaseInsensitiveCompare([a objectAtIndex:0], [b objectAtIndex:0]);
}
- (id)init
{
    if((self = [super init]))
    {
        NSString *str = [NSString stringWithContentsOfFile:@"/usr/share/dict/words"];
        NSArray *words = [str componentsSeparatedByString:@"\n"];
        NSMutableArray *pairs = [NSMutableArray array];
        for(NSString *word in words)
        {
            NSUInteger length = [word length];
            NSUInteger index;
            for(index = 0; index < length; index++)
            {
                NSArray *pair = [NSArray arrayWithObjects:
                    [word substringFromIndex:index],
                    word,
                    nil];
                [pairs addObject:pair];
            }
        }
        _wordPairs = [[pairs sortedArrayUsingFunction:CaseInsensitiveComparePairs context:NULL] copy];
    }
    return self;
}

- (void)dealloc
{
    [_wordPairs release];
    [super dealloc];
}

static CFComparisonResult FindComparator(const void *a, const void *b, void *ctx)
{
    id aobj = (id)a;
    id bobj = (id)b;
    if([aobj isKindOfClass:[NSArray class]])
        aobj = [aobj objectAtIndex:0];
    if([bobj isKindOfClass:[NSArray class]])
        bobj = [bobj objectAtIndex:0];
    NSInteger result = CaseInsensitiveCompare(aobj, bobj);
    if(result == NSOrderedSame) // force the search to the beginning of any matches
        return NSOrderedAscending;
    return result;
}

- (NSArray *)find:(NSString *)toFind
{
    NSUInteger pairsCount = [_wordPairs count];
    NSUInteger index = CFArrayBSearchValues((CFArrayRef)_wordPairs, CFRangeMake(0, pairsCount), toFind, FindComparator, NULL);
    NSMutableArray *array = [NSMutableArray array];
    for(; index < pairsCount; index++)
    {
        NSString *word = [[_wordPairs objectAtIndex:index] objectAtIndex:1];
        if([word rangeOfString:toFind options:NSCaseInsensitiveSearch].location != NSNotFound)
            [array addObject:word];
        else
            break;
    }
    return array;
}
@end

int main(int argc, char **argv)
{
    NSAutoreleasePool *outerPool = [[NSAutoreleasePool alloc] init];
    
    NSAutoreleasePool *innerPool = [[NSAutoreleasePool alloc] init];
    NSLog(@"Initializing dictionary...");
    Dict *dict = [[Dict alloc] init];
    NSLog(@"Done initializing, starting run");
    [innerPool release];
    
    NSTimeInterval start = [NSDate timeIntervalSinceReferenceDate];
    NSTimeInterval lastPrinted = start;
    unsigned counter = 0;
    while(1)
    {
        innerPool = [[NSAutoreleasePool alloc] init];
        [dict find:@"bob"];
        counter++;
        
        NSTimeInterval now = [NSDate timeIntervalSinceReferenceDate];
        if(now - lastPrinted >= 1.0)
        {
            NSLog(@"%.1f/sec", counter / (now - start));
            lastPrinted = now;
        }
        [innerPool release];
    }
    
    [dict release];
    [outerPool release];
    return 0;
}