//
//  main.m
//  ArrayTest
//
//  Created by Marc Haisenko on 16.02.12.
//  Copyright (c) 2012 equinux AG. All rights reserved.
//

#import <Foundation/Foundation.h>
#import <mach/mach_time.h>

static double kMachTimeToNSFactor;

static inline uint64_t currentHostTime ()
{
	return (uint64_t)(mach_absolute_time() * kMachTimeToNSFactor);
}

BOOL initMachClock()
{
	mach_timebase_info_data_t tinfo;
	
	if (mach_timebase_info(&tinfo) != 0) {
		NSLog(@"Could not initialize the clock!");
		return NO;
	}
	
	kMachTimeToNSFactor = ((double)tinfo.numer / tinfo.denom);
	return YES;
}

uint64_t median(NSArray *sortedArray) {
    uint64_t tmp;
    NSUInteger count;
    
    count = [sortedArray count];
    
    if ((count % 2) == 1) {
        return [[sortedArray objectAtIndex:(count / 2)] unsignedLongLongValue];
    } else {
        tmp = [[sortedArray objectAtIndex:(count / 2)] unsignedLongLongValue];
        tmp += [[sortedArray objectAtIndex:(count / 2) - 1] unsignedLongLongValue];
        tmp /= 2;
        return tmp;
    }
}

void measureRandomAccess(NSArray *array, NSMutableArray *times)
{
	uint64_t startnS;
	uint64_t stopnS;
	NSUInteger sum = 0;
	NSUInteger count;
	
	count = [array count];
	
	startnS = currentHostTime();
	
	for (NSUInteger i = 0; i < count; i++) {
		[array objectAtIndex:i];
	}
	
	stopnS = currentHostTime();
	
	[times addObject:[NSNumber numberWithUnsignedLongLong:stopnS - startnS]];
}

void measureEnumerator(NSArray *array, NSMutableArray *times)
{
	uint64_t startnS;
	uint64_t stopnS;
	NSUInteger sum = 0;
	NSEnumerator *enumerator;
	NSNumber *number;
	
	startnS = currentHostTime();
	
	enumerator = [array objectEnumerator];
	while (number = [enumerator nextObject]) {
	}
	
	stopnS = currentHostTime();
	
	[times addObject:[NSNumber numberWithUnsignedLongLong:stopnS - startnS]];
}

void measureFastEnumerator(NSArray *array, NSMutableArray *times)
{
	uint64_t startnS;
	uint64_t stopnS;
	NSUInteger sum = 0;
	NSNumber *number;
	
	startnS = currentHostTime();
	
	for (number in array) {
	}
	
	stopnS = currentHostTime();
	
	[times addObject:[NSNumber numberWithUnsignedLongLong:stopnS - startnS]];
}

void measureBlockEnumerator(NSArray *array, NSMutableArray *times)
{
	uint64_t startnS;
	uint64_t stopnS;
	__block NSUInteger sum = 0;
	
	startnS = currentHostTime();

	[array enumerateObjectsUsingBlock:^(NSNumber *number, NSUInteger idx, BOOL *stop) {
	}];
	
	stopnS = currentHostTime();
	
	[times addObject:[NSNumber numberWithUnsignedLongLong:stopnS - startnS]];
}

void measureConcurrentBlockEnumerator(NSArray *array, NSMutableArray *times)
{
	uint64_t startnS;
	uint64_t stopnS;
	__block NSUInteger sum = 0;
	
	startnS = currentHostTime();

    [array
        enumerateObjectsWithOptions:NSEnumerationConcurrent
        usingBlock:^(id obj, NSUInteger idx, BOOL *stop) {
    }];
	
	stopnS = currentHostTime();
	
	[times addObject:[NSNumber numberWithUnsignedLongLong:stopnS - startnS]];
}

void printTimes(NSMutableString *output, NSString *what, NSArray *times)
{
	uint64_t total = 0;
	uint64_t min, max;
	uint64_t interval;
	NSNumber *number;
    
    times = [times sortedArrayUsingSelector:@selector(compare:)];
	
	min = [[times objectAtIndex:0] unsignedLongLongValue];
    max = [[times lastObject] unsignedLongLongValue];
	
	for (number in times) {
		interval = [number unsignedLongLongValue];
		
		total += interval;
		if (interval < min) min = interval;
		if (interval > max) max = interval;
	}
	
    [output appendFormat:@"%@: total: %llu, average: %llu, min: %llu, max: %llu\n", what, total, median(times), min, max];
}

NSArray *generateArrayMalloc(NSMutableArray *times, unsigned int numEntries) {
	id *entries;
	NSArray *result;
    uint64_t startnS;
	uint64_t stopnS;

	
	entries = malloc(sizeof(id) * numEntries);
	for (unsigned int i = 0; i < numEntries; i++) {
		entries[i] = [NSNumber numberWithUnsignedInt:i];
	}

	startnS = currentHostTime();
	result = [NSArray arrayWithObjects:entries count:numEntries];
    stopnS = currentHostTime();
    
	free(entries);
    
    [times addObject:[NSNumber numberWithUnsignedLongLong:stopnS - startnS]];
	
	return result;
}

NSArray *generateArrayMallocCombined(NSMutableArray *times, unsigned int numEntries) {
	id *entries;
	NSArray *result;
    uint64_t startnS;
	uint64_t stopnS;

	startnS = currentHostTime();
    
	entries = malloc(sizeof(id) * numEntries);
	for (unsigned int i = 0; i < numEntries; i++) {
		entries[i] = [NSNumber numberWithUnsignedInt:i];
	}

	result = [NSArray arrayWithObjects:entries count:numEntries];
	free(entries);
    
    stopnS = currentHostTime();
    
    [times addObject:[NSNumber numberWithUnsignedLongLong:stopnS - startnS]];
	
	return result;
}

NSArray *generateMutableArray(NSMutableArray *times, unsigned int numEntries) {
	NSMutableArray *result;
    uint64_t startnS;
	uint64_t stopnS;

	startnS = currentHostTime();
    
	result = [NSMutableArray array];
	for (unsigned int i = 0; i < numEntries; i++) {
		[result addObject:[NSNumber numberWithUnsignedInt:i]];
	}
    
    stopnS = currentHostTime();
	
    [times addObject:[NSNumber numberWithUnsignedLongLong:stopnS - startnS]];

	return result;
}

#define ITERATIONS 1000

#define MEASURE(function) \
    @autoreleasepool { \
        times = [NSMutableArray array]; \
        for (int i = 0; i < ITERATIONS; i++) { \
            function(array, times); \
        } \
        [run addObject:times]; \
    }


int main (int argc, const char * argv[])
{
	unsigned int elements[] = { 1, 5, 10, 50, 100, 500, 1000, 5000, 10000, 50000, 100000, 500000, 1000000 };
	NSMutableArray *results;
	NSMutableArray *run;
	NSMutableArray *times;
	NSArray *array;
    NSString *path;
    NSMutableString *output;

	@autoreleasepool {
		
		if (!initMachClock()) return 1;
		
		results = [NSMutableArray array];

        for (int elementIndex = 0; elementIndex < (sizeof(elements) / sizeof(unsigned int)); elementIndex++) {
            @autoreleasepool {
                run = [NSMutableArray array];
                [run addObject:[NSString stringWithFormat:@"malloc, %u elements", elements[elementIndex]]];
                
                times = [NSMutableArray array];
                for (int i = 0; i < ITERATIONS; i++) {
                    @autoreleasepool {
                        array = generateArrayMallocCombined(times, elements[elementIndex]);
                    }
                }
                [run addObject:times];
                
                array = generateArrayMallocCombined(nil, elements[elementIndex]);
                
                NSLog(@"%@", [run objectAtIndex:0]);
                MEASURE(measureRandomAccess);
                MEASURE(measureEnumerator);
                MEASURE(measureFastEnumerator);
                MEASURE(measureBlockEnumerator);
                MEASURE(measureConcurrentBlockEnumerator);
                [results addObject:run];
                
                run = [NSMutableArray array];
                [run addObject:[NSString stringWithFormat:@"mutable array, %u elements", elements[elementIndex]]];
                
                times = [NSMutableArray array];
                for (int i = 0; i < ITERATIONS; i++) {
                    @autoreleasepool {
                        array = generateMutableArray(times, elements[elementIndex]);
                    }
                }
                [run addObject:times];
                
                array = generateMutableArray(nil, elements[elementIndex]);
                
                NSLog(@"%@", [run objectAtIndex:0]);
                MEASURE(measureRandomAccess);
                MEASURE(measureEnumerator);
                MEASURE(measureFastEnumerator);
                MEASURE(measureBlockEnumerator);
                MEASURE(measureConcurrentBlockEnumerator);                
                [results addObject:run];
            }
        }
        
        path = [NSSearchPathForDirectoriesInDomains(NSDocumentDirectory, NSUserDomainMask, YES) objectAtIndex:0];
        path = [path stringByAppendingPathComponent:@"arrayTest.txt"];
        
        output = [NSMutableString string];
        for (NSArray *result in results) {
            printTimes(output, [NSString stringWithFormat:@"%@, generation", [result objectAtIndex:0]], [result objectAtIndex:1]);
            printTimes(output, [NSString stringWithFormat:@"%@, random access", [result objectAtIndex:0]], [result objectAtIndex:2]);
            printTimes(output, [NSString stringWithFormat:@"%@, enumerator", [result objectAtIndex:0]], [result objectAtIndex:3]);
            printTimes(output, [NSString stringWithFormat:@"%@, fast enumerator", [result objectAtIndex:0]], [result objectAtIndex:4]);
            printTimes(output, [NSString stringWithFormat:@"%@, block enumerator", [result objectAtIndex:0]], [result objectAtIndex:5]);
            printTimes(output, [NSString stringWithFormat:@"%@, concurrent block enumerator", [result objectAtIndex:0]], [result objectAtIndex:5]);
        }
        [output writeToFile:path atomically:YES encoding:NSUTF8StringEncoding error:NULL];
	}
    return 0;
}

