// triplet-three

#define TRIPLET_MAX 4096 // Максимальное количество триплетов которые можно использовать

// Интерфейс источника последовательности
class source_t {
	item_t* first = { 0 };		// Первый элемент в последовательности
	bool is_init = { NULL };
public:
	int num = { 0 };

	virtual ~source_t() {}

	void clear() {
		first = NULL;
		is_init = false;
	}

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

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

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

// Возрастающая последовательность
class enumerable_t : public source_t {
	item_t* begin = { 0 }; // Первый элемент в последовательности
	item_t* end = { 0 };   // За последним

public:
	// Инициализация
	void init(item_t* begin, item_t* end) {
		assert(begin < end);
		clear();
		this->begin = begin;
		this->end = end;
	}

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

// Триплет. Слияние двух последовательностей, выдает общую на выходе
class triplet_t : public source_t {
	source_t* src_1 = { 0 };	// Источник 1 вход
	source_t* src_2 = { 0 };	// Источник 2 вход
	source_t* next_pop = { 0 };// Следующий на pop

public:
	// Подключение дочерних источников
	void init(source_t* src1, source_t* src2) {
		src_1 = src1;
		src_2 = src2;
	}

	item_t* next() override {
		// Извлечение следующего
		if (next_pop != NULL) {
			next_pop->pop();
			next_pop = NULL;
		}
		// Выбор следующего
		if (src_2->front() == NULL) {
			next_pop = src_1;
		} else if (src_1->front() == NULL) {
			next_pop = src_2;
		} else if (*src_1->front() < *src_2->front()) {
			next_pop = src_1;
		} else {
			next_pop = src_2;
		}
		return next_pop->front();
	}
};