#include<iostream>
#include<vector>
#include<algorithm>
#include<fstream>
#include<list>
#include<cmath>

using namespace std;

class Erro {};
class BocadoMemoria
{
	int offset;
	int size;
public:
	BocadoMemoria (int off, int len): offset(off), size(len) {}
	friend class GestorMemoria;
};
class GestorMemoria
{
	list<BocadoMemoria> ramLivre;
public:
	GestorMemoria (int RAM_Size)
	{ramLivre.push_back(BocadoMemoria(0, RAM_Size));}

	void imprimeMemoriaLivre (ostream& os) 
	{ 	
		for (list<BocadoMemoria>::iterator it = ramLivre.begin(); it != ramLivre.end(); it++) 
		{
			os <<"(" << (*it).offset << ";" << (*it).size << ") ";
		}
		os << endl;
	}

	BocadoMemoria pedidoDeMemoria (int size);
	BocadoMemoria encontraMaiorBocadoLivre ();
	void libertaMemoria (BocadoMemoria chunk);
};

BocadoMemoria GestorMemoria::pedidoDeMemoria (int size)
{
	for (list<BocadoMemoria>::iterator it = ramLivre.begin(); it != ramLivre.end(); it++) 
	{
		if (it->size >= size)
		{
			BocadoMemoria bc (it->offset, size);
			it->size -= size;
			it->offset += size;
			if (it->size == 0)
				ramLivre.erase(it);
			return bc;
		}
	}	
	throw Erro();
}

BocadoMemoria GestorMemoria::encontraMaiorBocadoLivre ()
{
	BocadoMemoria bc (0,0); 
	for (list<BocadoMemoria>::iterator it = ramLivre.begin(); it != ramLivre.end(); it++) 
	{
		if (it->size >= bc.size)
		{
			bc = *it;
		}
	}
	return bc;
}

void GestorMemoria::libertaMemoria (BocadoMemoria chunk)
{
	list<BocadoMemoria>::iterator it;
	for (it = ramLivre.begin(); it != ramLivre.end(); it++) 
	{
		if ( (it->offset) >= (chunk.offset+chunk.size) )
			break; // inserir antes deste
	}	
	if (it == ramLivre.end()  || it->offset != (chunk.offset+chunk.size))
		it = ramLivre.insert(it, chunk);
	else
	{ // fundir os dois
		it->offset = chunk.offset;
		it->size += chunk.size;
	}
	// falta tentar fundir com o anterior
	if (it == ramLivre.begin())
		return;
	list<BocadoMemoria>::iterator previous_it = it;
	previous_it --;
	if (previous_it -> offset + previous_it->size == it->offset)
	{	// funde
		previous_it->size += it->size;
		ramLivre.erase(it);
	}
}	

int main ()
{
	GestorMemoria gm (1024*4); // 4K RAM
	gm.imprimeMemoriaLivre(cout);

	BocadoMemoria bm1 = gm.pedidoDeMemoria(1024);
	BocadoMemoria bm2 = gm.pedidoDeMemoria(512);
	gm.imprimeMemoriaLivre(cout);
	gm.libertaMemoria(bm1);
	gm.imprimeMemoriaLivre(cout);
	BocadoMemoria bm3 = gm.pedidoDeMemoria(2560);
	gm.imprimeMemoriaLivre(cout);
	gm.libertaMemoria(bm2);
	gm.imprimeMemoriaLivre(cout);
	gm.libertaMemoria(bm3);
	gm.imprimeMemoriaLivre(cout);
}