#include <vector>
#include <string>
#include <iostream>

using namespace std;

//------------------------------------------------------
//	"bibliotecke" funkcije
unsigned lib_SirinaTeksta( string tekst, string fontname, unsigned size );
unsigned lib_VisinaTeksta( string tekst, string fontname, unsigned size );

//------------------------------------------------------
class Element
{
public:
	Element( unsigned s, unsigned v )
		: _Sirina(s), _Visina(v)
		{}
	unsigned Sirina() const
		{ return _Sirina; }
	unsigned Visina() const
		{ return _Visina; }
protected:
	unsigned _Sirina;
	unsigned _Visina;
};

//------------------------------------------------------
class Rec : public Element
{
public:
	Rec( string tekst, string font, unsigned velFonta )
		: Element(
			lib_SirinaTeksta( tekst + " ", font, velFonta ),
			lib_VisinaTeksta( tekst + " ", font, velFonta )
			),
		  _Tekst( tekst ),
		  _Font( font ),
		  _VelFonta( velFonta )
		{}
private:
	string _Tekst;
	string _Font;
	unsigned _VelFonta;
};

//------------------------------------------------------
class Red : public Element
{
public:
	Red( unsigned maxSirina )
		: Element( 0, 1 ), 
		  _MaxSirina( maxSirina )
		{}
	// stavljamo u red sto vise elemenata niza (koliko stane a bar jedan)
	// pri cemu pocinjemo od elementa el[prvi]
	// i vracamo indeks prvog elementa koji nije stao u red
	// (pretpostavljamo da je prvi < el.size())
	unsigned PopuniRed( const vector<const Element*> el, unsigned prvi )
		{
		unsigned sledeci = prvi;
		do Dodaj( el[sledeci++] );
		while(
			sledeci < el.size()
			&& el[sledeci]->Sirina() <= _MaxSirina - Sirina()
			);
		return sledeci;
		}		
	//	dodajemo element za koji pretpostavljamo da ima mesta
	void Dodaj( const Element* e )
		{
		_Elementi.push_back( e );
		_Sirina += e->Sirina();
		_Visina = max( _Visina, e->Visina() );
		}
private:
	unsigned 				_MaxSirina;
	vector<const Element*>	_Elementi;
};

//------------------------------------------------------
class Strana : public Element
{
public:
	Strana( unsigned maxSirina, unsigned maxVisina )
		: Element( 0, 0 ), 
		  _MaxSirina( maxSirina ),
		  _MaxVisina( maxVisina )
		{}
	~Strana()
		{
		for( unsigned i=0; i<_Redovi.size(); i++ )
			delete _Redovi[i];
		}
	// stavljamo na stranu red sto vise redova (koliko stane, a bar jedan)
	// pri cemu pocinjemo od reda redovi[prvi]
	// i vracamo indeks prvog reda koji nije stao na stranu
	// (pretpostavljamo da je prvi < redovi.size())
	unsigned PopuniStranu( const vector<const Red*> redovi, unsigned prvi )
		{
		unsigned sledeci = prvi;
		do Dodaj( redovi[sledeci++] );
		while(
			sledeci < redovi.size()
			&& redovi[sledeci]->Visina() <= _MaxVisina - Visina()
			);
		return sledeci;
		}		
	//	dodajemo red za koji pretpostavljamo da ima mesta
	void Dodaj( const Red* r )
		{
		_Redovi.push_back( r );
		_Visina += r->Visina();
		_Sirina = max( _Sirina, r->Sirina() );
		}
	const vector<const Red*>& Redovi()
		{ return _Redovi; }	

private:
	//	zabranimo kopiranje
	Strana( const Strana& );
	Strana& operator = ( const Strana& );

	unsigned 			_MaxSirina;
	unsigned 			_MaxVisina;
	vector<const Red*>	_Redovi;
};

//------------------------------------------------------
class PrelomljenTekst
{
public:
	PrelomljenTekst( 
		unsigned maxSirStrane, 
		unsigned maxVisStrane,
		const vector<const Element*>& tekst
		)
		{
		vector<const Red*> redovi;
		for( unsigned sledeci = 0; sledeci < tekst.size(); ){
			Red* r = new Red( maxSirStrane );
			sledeci = r->PopuniRed( tekst, sledeci );
			redovi.push_back(r);
			};
	
		for( unsigned sledeci = 0; sledeci < redovi.size(); ){
			Strana* s = new Strana( maxSirStrane, maxVisStrane );
			sledeci = s->PopuniStranu( redovi, sledeci );
			_Strane.push_back(s);
			};
		}
		
	~PrelomljenTekst()
		{
		for( unsigned i=0; i<_Strane.size(); i++ )
			delete _Strane[i];
		}
		
	const vector<const Strana*>& Strane()
		{ return _Strane; }	
		
private:
	//	zabranimo kopiranje
	PrelomljenTekst( const PrelomljenTekst& );
	PrelomljenTekst& operator = ( const PrelomljenTekst& );
	
	vector<const Strana*> _Strane;
};

//------------------------------------------------------
// probna implementacija
unsigned lib_SirinaTeksta( string tekst, string fontname, unsigned size )
	{ return tekst.length() * size; }
unsigned lib_VisinaTeksta( string tekst, string fontname, unsigned size )
	{ return size * 2; }

//------------------------------------------------------
main()
{
	vector<const Element*> tekst;
	tekst.push_back( new Rec( "prva", "arial", 10 ));
	tekst.push_back( new Rec( "druga", "arial", 8 ));
	tekst.push_back( new Rec( "treca", "arial", 12 ));
	tekst.push_back( new Rec( "cetvrta", "arial", 6 ));
	tekst.push_back( new Rec( "treca", "arial", 12 ));
	tekst.push_back( new Rec( "cetvrta", "arial", 6 ));
	tekst.push_back( new Rec( "treca", "arial", 12 ));
	tekst.push_back( new Rec( "cetvrta", "arial", 6 ));
	tekst.push_back( new Rec( "treca", "arial", 12 ));
	tekst.push_back( new Rec( "cetvrta", "arial", 6 ));
	tekst.push_back( new Rec( "treca", "arial", 12 ));
	tekst.push_back( new Rec( "cetvrta", "arial", 6 ));
	tekst.push_back( new Rec( "treca", "arial", 12 ));
	tekst.push_back( new Rec( "cetvrta", "arial", 6 ));
	tekst.push_back( new Rec( "treca", "arial", 12 ));
	tekst.push_back( new Rec( "cetvrta", "arial", 6 ));
	
	PrelomljenTekst prelom( 120, 70, tekst );
	cout << "Prelomljen tekst ima " << prelom.Strane().size() << " strana." << endl;
	for( unsigned i=0; i<prelom.Strane().size(); i++ ){
		cout << "Strana " << (i+1) << " ima dimenzije "
			 << prelom.Strane()[i]->Sirina() << " " 
			 << prelom.Strane()[i]->Visina() << endl;
		cout << "Ima " << prelom.Strane()[i]->Redovi().size() << " redova." << endl;
		for( unsigned j=0; j<prelom.Strane()[i]->Redovi().size(); j++ ){
			cout << "Red " << (j+1) << " ima dimenzije "
				 << prelom.Strane()[i]->Redovi()[j]->Sirina() 
				 << " " << prelom.Strane()[i]->Redovi()[j]->Visina() << endl;
			}
		}
		
	return 0;
}
