/*

Сортировка файла построчно слияниями сортированных последовательностей. 

1й проход: Поиск возрастающих участков файла. Построение списка источников.
В случае заполнения списка источников до достижения конца файла слияние 
половины меньших по размеру источников во временный файл и подключение его
как источника. И т.д. до завершения прохода.

2й проход: Слияние в выходной файл.


*/

#define SOURCE_MAX 1024 // Максимальное количество источников, кратно степени 2
#define STRING_MAX 256 // Максимальный размер строки файла

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <assert.h>
#include <string.h>
#include <stdint.h>

// Буфер для кэширования одной строки
struct item_t {
	char data[STRING_MAX];

	bool operator < (item_t const &b) const { return memcmp(data, b.data, STRING_MAX) < 0; }

};

// Интерфейс источника последовательности
class source_t {
	item_t* first;		// Первый элемент в последовательности

public:
	source_t() : first(NULL) {}

	virtual ~source_t() {}

	// Первый элемент в очереди, NULL если пусто
	virtual const item_t* front() {
		if(first == NULL) {
			pop();
		}
		return first;
	}

	// Извлечение следующего элемента
	virtual void pop() {
		first = next();
	}

	// Считывание следующего элемента последовательности, NULL если читать нечего
	virtual item_t* next() {
		return NULL;
	}

	// Общая длина последовательности в любых попугаях, используется для сравнения размеров последовательностей
	virtual size_t size() {
		return 0;
	}
};

// Интерфейс приемника
class destination_t {
public:
	virtual ~destination_t() {}

	// Установка источника
	void source_set(source_t* src) {
		assert(src != NULL);
		// Запись всего что есть в источнике
		const item_t* i;
		while(i = src->front()) {
			write(i);
			src->pop();
		}
	}

	// Запись элемента
	virtual void write(const item_t* item) {

	}
};

// Последовательность из файла или куска файла
class file_t : public source_t, public destination_t {
	item_t item;	// Последняя прочитанная запись
	size_t offset;	// Смешение для чтения следующей строки
	size_t end;		// Конец блока
	FILE* f;		// Файл

public:
	file_t() : f(NULL), offset(0), end(0) {}

	~file_t() {
		assert(end == offset); // Прочитан не полностью
	}

	void init(FILE* f) {
		this->f = f;
	}

	// Чтение ---------------------------------------------
	void init_read(size_t offset, size_t end) {
		this->offset = offset;
		this->end = end;
	}

	// Чтение файла целиком
	void init_read() {
		offset = 0;
		fseek(f, 0, SEEK_END);
		end = ftell(f);
	}

	item_t* next() override {
		if (end <= offset) return NULL;
		if (offset != ftell(f)) {
			// Установка указателя для чтения строки
			if (fseek(f, offset, SEEK_SET) != 0) {
				assert(false); // Невозможно установить позицию в файле
			}
		}
		if (fgets(item.data, STRING_MAX, f) < 0) {
			offset = ftell(f);
			return NULL;
		}
		offset = ftell(f);
		return &item;
	}

	size_t size() override {
		if (end <= offset) return 0;
		return end - offset;
	}

	void print() {
		item_t* i;
		while(i = next()) {
			printf(i->data);
		}
	}

	// Запись ----------------------------------------------
	//void end_write(const item_t* item) {
	//	offset = 0;
	//	fseek(0, 0, SEEK_SET);
	//}

	void write(const item_t* item) override {
		fputs(item->data, f);
	}
};

// Слияние двух последовательностей, выдает общую на выходе
class triplet_t : public source_t {
	source_t* src[2] = {0};	// Источники
	size_t idx = {0};		// Индекс меньшего
	size_t num;
public:

	void init(source_t* src1, source_t* src2, size_t num) {
		assert(src1 != NULL);
		src[0] = src1;
		src[1] = src2;
		this->num = num;
	}

	// Первый элемент в очереди, NULL если пусто
	const item_t* front() override {
		assert(src[0] != NULL);
		if (src[1] == NULL || src[1]->front() == NULL) {
			idx = 0;
		} else if (src[0]->front() == NULL) {
			idx = 1;
		} else if(*src[0]->front() < *src[1]->front()) {
			idx = 0;
		} else {
			idx = 1;
		}
		return src[idx]->front();
	}

	// Извлечение следующего
	void pop() override {
		src[idx]->pop();
	}
};

// Слияние массива src в dest деревом триплетов
void triplet_store(source_t** src, size_t src_size, destination_t& dest) {
	triplet_t trp[SOURCE_MAX];
	assert(src_size != 0 || src_size >= SOURCE_MAX);
	// Инициализация первых триплетов на src_size входов
	size_t cnt = 0;
	for(size_t i = 0; i < src_size + src_size % 2; i += 2) {
		if(i < src_size - 1) {
			trp[cnt].init(src[i], src[i + 1], cnt);
		} else {
			trp[cnt].init(src[i], NULL, cnt);
		}
		cnt++;
	}
	// Инициализация остального дерева
	size_t first = 0, last = cnt;
	while(last - first > 1) {
		for (size_t i = first; i < last + (last - first) % 2; i += 2) {
			if (i < last - 1) {
				trp[cnt].init(&trp[i], &trp[i + 1], cnt);
			} else {
				trp[cnt].init(&trp[i], NULL, cnt);
			}
			cnt++;
			assert(cnt < SOURCE_MAX);
		}
		first = last;
		last = cnt;
	}
	// Сохранение
	dest.source_set(&trp[first]);
}

// Слияние
void triplet_sort(const char* file_source, const char* file_dest) {
	FILE* in = fopen(file_source, "rb");
	assert(in != NULL);
	FILE* out = fopen(file_dest, "wb");
	assert(out != NULL);
	file_t dest;
	dest.init(out);
	// Заполнение источников
	file_t fs[SOURCE_MAX];
	source_t* src[SOURCE_MAX] = {0};
	size_t start = 0;
	item_t item[2];
	size_t idx = 1;
	size_t cnt = 0; // Количество последовательностей
	if(fgets(item[0].data, STRING_MAX, in) >= 0) { // Чтение первого элемента
		for(; cnt < SOURCE_MAX; cnt++) {
			size_t end = ftell(in);
			// Вычитывание возрастающей последовательности
			while(fgets(item[idx].data, STRING_MAX, in) >= 0) {
				idx = 1 - idx;
				// Проверка возрастания, idx предыдуший элемент
				if (item[1 - idx] < item[idx]) {
					break;
				}
				end = ftell(in);
			}
			fs[cnt].init(in);
			fs[cnt].init_read(start, end);
			src[cnt] = &fs[cnt];
			start = end;
		}
		printf("cnt = %d\n", (int)cnt);
	}
	// Слияние в конечный файл
	triplet_store(src, cnt, dest);


	for (size_t i = 0; i < SOURCE_MAX; i++) {
		printf("---- %lld -----\n", (int64_t) i);
		fs[i].print();
	}
	fclose(in);
	fclose(out);
}


// Файл для сортировки можно тут взять http://services.fms.gov.ru/info-service.htm?sid=2000 1.2Гб неупорядоченного текста.
int main() {
	triplet_sort("c:/download/list_of_expired_passports.csv", "c:/download/list_of_expired_passports-sort.csv");
#ifdef _DEBUG
	printf("Press any key ...\n");
	getchar();
#endif
	return 0;
}