#include "PreCompile.h"
#include "TreeNode.h"
#include "FTBitmapChar.h"
TreeNode::TreeNode(int x, int y, int width, int height)
{
m_x = x;
m_y = y;
m_width = width;
m_height = height;
m_pLeaf1 = NULL;
m_pLeaf2 = NULL;
}
TreeNode::~TreeNode()
{
if (m_pLeaf1) delete m_pLeaf1;
if (m_pLeaf2) delete m_pLeaf2;
}
void TreeNode::CreateBranches(FTBitmapChar* pFTBitmapChar)
{
int dx = m_width - pFTBitmapChar->GetWidth();
int dy = m_height - pFTBitmapChar->GetHeight();
// we split to give one very small leaf and one very big one
// because it allows more efficent use of space
// if you don't do this, the bottom right corner never gets used
if (dx < dy)
{
// split so the top is cut in half and the rest is one big rect below
m_pLeaf1 = new TreeNode(m_x + pFTBitmapChar->GetWidth(), m_y,
m_width - pFTBitmapChar->GetWidth(),
pFTBitmapChar->GetHeight());
m_pLeaf2 = new TreeNode(m_x, m_y + pFTBitmapChar->GetHeight(),
m_width, m_height - pFTBitmapChar->GetHeight());
}
else
{
// m_pLeaf1 = left (cut in half)
m_pLeaf1 = new TreeNode(m_x, m_y + pFTBitmapChar->GetHeight(),
pFTBitmapChar->GetWidth(), m_height - pFTBitmapChar->GetHeight());
// m_pLeaf2 = right (not cut)
m_pLeaf2 = new TreeNode(m_x + pFTBitmapChar->GetWidth(), m_y,
m_width - pFTBitmapChar->GetWidth(), m_height);
}
}
bool TreeNode::Add(FTBitmapChar* pFTBitmapChar)
{
if (pFTBitmapChar->IsEmpty()) return true;
if (IsEmpty())
{
if (Fits(pFTBitmapChar))
{
CreateBranches(pFTBitmapChar);
pFTBitmapChar->SetXY(m_x, m_y);
return true;
}
return false;
}
if (m_pLeaf1->Add(pFTBitmapChar))
{
return true;
}
if (m_pLeaf2->Add(pFTBitmapChar))
{
return true;
}
return false;
}
bool TreeNode::Fits(FTBitmapChar* pFTBitmapChar)
{
return pFTBitmapChar->GetWidth() <= m_width && pFTBitmapChar->GetHeight() <= m_height;
}