#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_N		400000
#define MAX_K_RANGE	200
#define MAX_RANGELIMITS	1000

typedef struct {
	long long mink;
	long long maxk;
} krange_t;

typedef struct {
	int 		used;
	long long	maxk;
	int         rangeCount;
	krange_t	kRange[MAX_K_RANGE];
} range_t;

typedef struct {
	int minn;
	int maxn;
	long long maxk;
} rangelimit_t;


int sortRange(const void *a, const void *b);
void  mergeRanges();
void  buildRangelimit();
void  populateRangeLimit();
void  printRangeLimit();

range_t 		rangeList[MAX_N];
rangelimit_t	rangelimit[MAX_RANGELIMITS];

void main() {
	FILE *in;
	
	char buffer[600], *c1, *c2, *c3, *c4, *c5;
	int  n, minn, maxn;
	long long mink, maxk;
	int  count = 0, i, rl;

	in = fopen("completed.csv", "r");
	if (!in)
		exit(0);
	
	memset(rangeList, 0, sizeof(rangeList));
	
	while (fgets(buffer, sizeof(buffer), in) > 0) {
		c1 = c2 = c3 = c4 = c5 = 0;
		
		c1 = strchr(buffer, ',');
		if (c1) c2 = strchr(c1+1, ',');
		if (c2) c3 = strchr(c2+1, ',');
		if (c3) c4 = strchr(c3+1, ',');
		if (c4) c5 = strchr(c4+1, ',');
		
		if (!c5) {
		   printf("bad line %s\n", buffer);
		   exit(0);
		}
		
		if (strstr(c5+1, "ecm"))
			continue;
		
		*c1 = *c2 = *c3 = *c4 = *c5 = 0;
		
		minn = atol(c1+1);
		maxn = atol(c2+1);
		mink = atoll(c3+1);
		maxk = atoll(c4+1);

		
		for (n=minn; n<=maxn; n++) {
			if (n < 12 || n >= 200000) continue;
		
			if (rangeList[n].used == 0) {
				rangeList[n].kRange[0].mink = 1;
				rangeList[n].kRange[0].maxk = 1;
				rangeList[n].rangeCount++;
			}
			
			rangeList[n].used = 1;		
			i = rangeList[n].rangeCount;
			
			if (i == MAX_K_RANGE) {
				printf("Ran out of space for %d %lld %lld\n", n, mink, maxk);
				exit(0);
			}

			rangeList[n].kRange[i].mink = mink;
			rangeList[n].kRange[i].maxk = maxk;
			rangeList[n].rangeCount++;
			
			count++;
		}
	}

	fclose(in);
	
	printf("read %d ranges\n", count);

	mergeRanges();

	buildRangelimit();
	
	populateRangeLimit();
	
	printRangeLimit();
}

int sortRange(const void *a, const void *b) {
	krange_t *kr1 = (krange_t *) a;
	krange_t *kr2 = (krange_t *) b;

	// Ensure that rows with mink = 0 are sorted to the bottom
	if (kr1->mink == 0 && kr2->mink == 0)
		return 0;
	
	if (kr1->mink == 0) return 1;
	if (kr2->mink == 0) return -1;
	
	if (kr1->mink == kr2->mink) {
		if (kr1->maxk > kr2->maxk)
			return 1;
		
		if (kr1->maxk < kr2->maxk)
			return -1;
		
		return 0;
	}

	if (kr1->mink > kr2->mink)
		return 1;
	
	if (kr1->mink < kr2->mink)
		return -1;
	
	return 0;
}

void mergeRanges() {
	int i, n, count, ncount = 0;
	int isMerged, mergeType1Count = 0, mergeType2Count = 0;
	int count1, count2;
	
	for (n=0; n<MAX_N; n++) {
		if (rangeList[n].used == 0)
			continue;

		isMerged = 1;
		while (isMerged) {
			isMerged = 0;
			
			qsort(rangeList[n].kRange, rangeList[n].rangeCount, sizeof(krange_t), sortRange);
			
			count = 0;
			for (i=0; i<rangeList[n].rangeCount; i++)
				if (rangeList[n].kRange[i].mink > 0)
					count++;
				
			rangeList[n].rangeCount = count;
			
			for (i=0; i<rangeList[n].rangeCount-1; i++) {
				if (rangeList[n].kRange[i].mink == 0)
					continue;
					
			
				// If this range and the next range have the same mink, merge them.
				if (rangeList[n].kRange[i].mink == rangeList[n].kRange[i+1].mink) {
					// Use whichever maxk is larger
					if (rangeList[n].kRange[i].maxk < rangeList[n].kRange[i+1].maxk)
						rangeList[n].kRange[i].maxk = rangeList[n].kRange[i+1].maxk;
				
					rangeList[n].kRange[i+1].mink = 0;
					mergeType1Count++;
					isMerged = 1;
				}
			}
			
			if (isMerged)
				continue;
			
			for (i=0; i<rangeList[n].rangeCount-1; i++) {
				if (rangeList[n].kRange[i].mink == 0)
					continue;

				// If the next range starts before the current range ends, merge them		
				if (rangeList[n].kRange[i].maxk >= rangeList[n].kRange[i+1].mink) {
					// Use whichever maxk is larger
					if (rangeList[n].kRange[i].maxk < rangeList[n].kRange[i+1].maxk)
						rangeList[n].kRange[i].maxk = rangeList[n].kRange[i+1].maxk;
					
					rangeList[n].kRange[i+1].mink = 0;
					mergeType2Count++;
					isMerged = 1;
				}
			}
		}
	}
	
	printf("%d ranges were merged due to same min k\n",  mergeType1Count);
	printf("%d ranges were merged due to overlapping k ranges\n",  mergeType2Count);
	
	count1 = count2 = 0;
	for (n=0; n<MAX_N; n++) {
		if (rangeList[n].used == 0)
			continue;
			
		ncount++;
		count1 += rangeList[n].rangeCount;
		for (i=0; i<MAX_K_RANGE; i++) {
			if (rangeList[n].kRange[i].mink == 0) 
				continue;
			
			// In addition to counting, fill in the maxk for this n
			count2++;
			rangeList[n].maxk = rangeList[n].kRange[i].maxk;
		}
	}
	
	if (count1 != count2) {
		printf("foobar %d != %d\n", count1, count2);
		exit(0);
	}
	
	printf("%d n and %d k ranges to process\n",  ncount, count1);
	
	// Once we got this far, we know that none of the k ranges will overlap.
	for (n=0; n<MAX_N; n++) {
		if (rangeList[n].used == 0)
			continue;
		
		for (i=0; i<rangeList[n].rangeCount-1; i++)
			if (rangeList[n].kRange[i+1].mink < rangeList[n].kRange[i].maxk)
				printf("gap type 1:  %d %lld %lld\n", n, rangeList[n].kRange[i].maxk, rangeList[n].kRange[i+1].mink);
	}
}

void populateRangeLimit() {
	int isApplied, rl, n;
	
	for (n=0; n<MAX_N; n++) {
		if (rangeList[n].used == 0)
			continue;
		
		isApplied = 0;
		for (rl=0; rl<1000; rl++)
			if (n >= rangelimit[rl].minn && n <= rangelimit[rl].maxn) {
				isApplied = 1;
				if (rangeList[n].maxk > rangelimit[rl].maxk)
					rangelimit[rl].maxk = rangeList[n].maxk;
				break;
			}
		
		if (!isApplied)
			printf("Couldn't find %d in rangelimit\n", n);
	}
}

void printRangeLimit() {
	int n, rl;
	FILE *gaps;
	
	gaps = fopen("gaps.txt", "w");
	
	for (rl=0; rl<1000; rl++) {
		if (rangelimit[rl].maxk == 0)
			break;
		
		if (rangelimit[rl].minn == rangelimit[rl].maxn)
			printf("%d %lld\n", rangelimit[rl].minn, rangelimit[rl].maxk);
		else
			printf("%d-%d %lld\n", rangelimit[rl].minn, rangelimit[rl].maxn, rangelimit[rl].maxk);
		
		for (n=rangelimit[rl].minn; n<=rangelimit[rl].maxn; n++)
			if (rangeList[n].maxk < rangelimit[rl].maxk)
				fprintf(gaps, "gap type 2:  %d %lld %lld\n", n, rangeList[n].maxk, rangelimit[rl].maxk);
	}
	
	fclose(gaps);
}

void buildRangelimit() {
	int i = 12;
	int rl = 0;
	
	memset(rangelimit, 0, MAX_RANGELIMITS*sizeof(rangelimit_t));
	
	while (i < 100) {
		rangelimit[rl].minn = i;
		rangelimit[rl].maxn = i;
		rangelimit[rl].maxk = 0;
		rl++;
		i++;
	}
	
	while (i < 1000) {
		rangelimit[rl].minn = i;
		rangelimit[rl].maxn = i + 9;
		rangelimit[rl].maxk = 0;
		rl++;
		i += 10;
	}
	
	while (i < 10000) {
		rangelimit[rl].minn = i;
		rangelimit[rl].maxn = i + 99;
		rangelimit[rl].maxk = 0;
		rl++;
		i += 100;
	}
	
	while (i < 100000) {
		rangelimit[rl].minn = i;
		rangelimit[rl].maxn = i + 999;
		rangelimit[rl].maxk = 0;
		rl++;
		i += 1000;
	}
	
	while (i < 1000000) {
		rangelimit[rl].minn = i;
		rangelimit[rl].maxn = i + 9999;
		rangelimit[rl].maxk = 0;
		rl++;
		i += 10000;
	}
}