#include <iostream>
#include <memory>
#include <vector>
#include <ctime>

static const uint64_t SEED = 0xDEADBEEFull;
static const size_t ROWS = 10000;
static const size_t COLS = 10000;
static const uint32_t COLORS_NUM = 3;

uint32_t LCGRand()
{
    static uint64_t seed = SEED;
    seed = seed * 6364136223846793005 + 1442695040888963407;
    return seed >> 32;
}

template <typename T>
class IntrusivePtr
{
public:
	IntrusivePtr() : ptr(nullptr) { }
	IntrusivePtr(T *raw) : ptr(raw) {
		if (ptr) ptr->AddRef();
	}
	IntrusivePtr(const IntrusivePtr& other) : ptr(other.ptr) {
		if (ptr) ptr->AddRef();
	}
	~IntrusivePtr() {
		if (ptr) ptr->Release();
	}
	IntrusivePtr & operator = (const IntrusivePtr& other) {
		T *old = ptr;
		ptr = other.ptr;
		if (ptr) ptr->AddRef();
		if (old) old->Release();
		return *this;
	}
	
	T *operator -> () {
		return ptr;
	}
	
    operator T*() {
		return ptr;
	}
	

private:
	T* ptr;
};

struct Block {
	typedef IntrusivePtr<Block> Ptr;
	
	uint32_t color;
	size_t size;
	Ptr redir;
	
	size_t ref_count;
	Block *next_free;
	
	Block() : color(0), size(0), redir(), ref_count(0), next_free(nullptr) { }
	
	static Ptr Allocate() {
		Block *item = pool;
		if (item)
			pool = item->next_free;
		else
			item = new Block();
		*item = Block();
		return item;
	}
	
	void AddRef() {
		++ref_count;
	}
	
	void Release() {
		if (!--ref_count) {
			next_free = pool;
			pool = this;
		}
	}
	
	static Block *pool;
};

Block *Block::pool = nullptr;

int main()
{
	std::vector<Block::Ptr> up_row(COLS);
	size_t max_size = 0;
	
	clock_t start = clock();
	
    for (size_t row = 0; row < ROWS; row++) {
    	Block::Ptr left;
    	
    	for (size_t col = 0; col < COLS; col++) {
    		uint32_t color = LCGRand() % COLORS_NUM;
    		
    		Block::Ptr &up = up_row[col];
    		while (up && up->redir)
    			up = up->redir;

    		Block::Ptr cur;
    		if (left && (left->color == color)) {
    			cur = left;
    			
    			if (up && (up->color == color) && (up != left)) {
    				left->size += up->size;
    				up->redir = left;
    			}
    		} else if (up && (up->color == color)) {
    			cur = up;
    		} else {
    			cur = Block::Allocate();
    			cur->color = color;
    		}
    		
    		max_size = std::max(max_size, ++cur->size);
    		left = up = cur;
    	}
    }
	
    std::cout << "Max block size: " << max_size << std::endl;
    std::cout << "Time: " << (clock() - start) / (CLOCKS_PER_SEC / 1000) << " ms" << std::endl;
    return 0;
}