I need algorithm which splits big static sized rectangle to small ones. A perfect implementation for me look like this:
struct RECT
{
int l,t,r,b;
};
class BigRect
{
public:
// width and height of big rect
BigRect( unsigned width, unsigned height );
// returns -1 if rect cannot be allocated, otherwise returns id of found rect
int GetRect( unsigned width, unsigned height, RECT &out );
// returns allocated rect to big rectangle
void FreeRect( int id );
};
void test()
{
BigRect r( 10, 10 );
RECT out;
r.GetRect( 4, 4, out ); // rect found ({0,0,4,4} for example), returns 1
r.GetRect( 5, 5, out ); // rect found ({4,0,9,5} for example), returns 2
r.GetRect( 6, 6, out ); // no place found for rect, returns -1
r.FreeRect( 2 ); // add {4,0,9,5} back to rect
r.GetRect( 6, 6, out ); // rect found (4,0,10,6)
}
So I need algorithm for GetRect and FreeRect methods. Any ideas and links would be appreciated.