//
//  KMRangeArray.m
//  KMLogView
//
//  Created by 堀 昌樹 on 12/05/09.
//  Copyright (c) 2012年 __MyCompanyName__. All rights reserved.
//

#import "KMRangeArray.h"

struct _KMRange;
typedef struct _KMRange KMRange;

struct _KMRange {
	KMRange *prev;
	KMRange *next;
	NSUInteger length;
};

typedef KMRange *KMRangePointer;


KMRangePointer rangeAtIndex(KMRangePointer origin, NSInteger offset);

@implementation KMRangeArray
{
	KMRangePointer ranges;
	KMRangePointer lastRange;
}

- (void)dealloc
{
	KMRangePointer p = ranges;
	while(ranges) {
		p = ranges->next;
		NSZoneFree([self zone], ranges);
		ranges = p;
	}
	
	[super dealloc];
}
- (NSRange)rangeAtIndex:(NSInteger)index
{
	NSRange result = {NSNotFound, 0};
	NSUInteger location = 0;
	KMRangePointer range = ranges;
	for(NSInteger i = 0; i < index; i++) {
		if(range == NULL) {
			[NSException raise:NSRangeException format:@"Range has few indexes."];
			return result;
		}
		location += range->length;
		range = range->next;
	}
	result.location = location;
	result.length = range->length;
	return result;
}
- (NSIndexSet *)indexSetInRange:(NSRange)range
{
	NSMutableIndexSet *result = [NSMutableIndexSet indexSet];
	NSRange aRange;
	NSInteger index = 0;
	NSUInteger location = 0;
	KMRangePointer p = ranges;
	while(p) {
		aRange = NSMakeRange(location, p->length);
		if(NSIntersectionRange(range, aRange).length != 0) {
			[result addIndex:index];
		}
		index++;
		location += p->length;
		p = p->next;
	}
	return result;
}
- (NSInteger)firstIndexInRange:(NSRange)range
{
	NSInteger result = 0;
	NSUInteger location = 0;
	KMRangePointer aRange = ranges;
	while(aRange) {
		if(NSIntersectionRange(range, NSMakeRange(location, aRange->length)).length != 0) {
			return result;
		}
		result++;
		location += aRange->length;
		aRange = aRange->next;
	}
	return NSNotFound;
}

- (void)appendRangeWithLength:(NSUInteger)length
{
	KMRangePointer newRange = NSZoneMalloc([self zone], sizeof(KMRange));
	newRange->length = length;
	if(!ranges) {
		newRange->next = newRange->prev = NULL;
		ranges = lastRange = newRange;
		return;
	}

	lastRange->next = newRange;
	newRange->prev = lastRange;
	newRange->next = NULL;
	lastRange = newRange;
}
- (void)insertRangeWithLenght:(NSUInteger)length atIndex:(NSInteger)index
{
	KMRangePointer target = rangeAtIndex(ranges, index);
	if(!target) {
		[NSException raise:NSRangeException format:@"bounds index"];
		return;
	}
	KMRangePointer newRange = NSZoneMalloc([self zone], sizeof(KMRange));
	newRange->length = length;
	target->prev->next = newRange;
	newRange->prev = target->prev;
	newRange->next = target;
	target->prev = newRange;
}
- (void)removeAtIndex:(NSInteger)index
{
	KMRangePointer target = rangeAtIndex(ranges, index);
	if(!target) {
		[NSException raise:NSRangeException format:@"bounds index"];
		return;
	}
	
	if(target == lastRange) {
		lastRange->prev->next = NULL;
		NSZoneFree([self zone], target);
		return;
	}
	if(target == ranges) {
		if(target->next) {
			ranges = ranges->next;
		}
		NSZoneFree([self zone], target);
		return;
	}
	
	target->prev->next = target->next;
	target->next->prev = target->prev;
	NSZoneFree([self zone], target);
}

- (id)description
{
	KMRangePointer p = ranges;
	NSInteger i = 0;
	NSUInteger location = 0;
	NSMutableString *result = [NSMutableString stringWithString:@"(\n"];
	while(p) {
		[result appendFormat:@"[%ld]: {%ld, %ld}\n", i, location, p->length];
		i++;
		location += p->length;
		p = p->next;
	}
	[result appendString:@")\n"];
	return result;
}

KMRangePointer rangeAtIndex(KMRangePointer origin, NSInteger offset)
{
	while(offset != 0 && origin && origin->next) {
		origin = origin->next;
		offset--;
	}
	
	return offset != 0 ? NULL : origin;
}
@end
