Binary tree algorithm for 2D bin packing

I have re-implemented in C++ an algorithm already in JavaScript available here and there.

C++ code works fine, but I have memory management concerns:

1. I allocate memory with such statement as m_root = new Block(...) dangerously
2. When freeing memory with if (m_fit) { delete m_fit; m_fit = nullptr; }, exceptions are thrown

I feel like my C++ code is leaking memory, I wonder if something is noticeably wrong:

Calling the algorithm

void createBlocks(std::vector<Block> &blocks)
{
for (int i = 0; i < 100; ++i) {
float w = i * 1.1; // semi-random
float h = i * 0.9; // semi-random
float x = i - 10;  // semi-random
float y = i + 5;   // semi-random
Block block = Block(w, h, x, y);
blocks.push_back(block);
}
}

void sortDescendingInSize(std::vector<Block> &blocks)
{
std::sort(blocks.begin(), blocks.end(), [](const Block& first, const Block &second) {
float firstMaxSide  = std::max( first.m_h,  first.m_w);
float secondMaxSide = std::max(second.m_h, second.m_w);
// returns ​true if the first argument is ordered before the second
// order descending
return firstMaxSide > secondMaxSide;
});
}

void main()
{
std::vector<Block> blocks = std::vector<Block>();

createBlocks(blocks);

if (blocks.empty())
return;

sortDescendingInSize(blocks);

GrowingPacker growingPacker = GrowingPacker();
growingPacker.fit(blocks);

for (const Block &block : blocks) {
if (block.m_fit && block.m_item) {
std::cout <<
<< "w:" << block.m_w << "h:" << block.m_h
<< "fit->w:" << block.m_fit->m_w << "fit->h:" << block.m_fit->m_h
<< "fit->x:" << block.m_fit->m_x << "fit->y:" << block.m_fit->m_y;
}
}
}


Algorithm class definition

#ifndef GROWINGPACKER_H
#define GROWINGPACKER_H

#include "vector"
#include "src/pack/block.h"

class GrowingPacker
{
public:
GrowingPacker();
void fit(std::vector<Block> &blocks);

private:
Block *findNode(Block *root, float w, float h);
Block *splitNode(Block *node, float w, float h);
Block *growNode(float w, float h);
Block *growRight(float w, float h);
Block *growDown(float w, float h);

private:
Block *m_root;
};

#endif // GROWINGPACKER_H


Algorithm class implementation

#include "growingpacker.h"

GrowingPacker::GrowingPacker()
{

}

void GrowingPacker::fit(std::vector<Block> &blocks)
{
size_t len = blocks.size();
float w = len > 0 ? blocks[0].m_w : 0;
float h = len > 0 ? blocks[0].m_h : 0;
m_root = new Block(w,h, 0, 0);
for (Block &block : blocks) {
Block *node = findNode(m_root, block.m_w, block.m_h);
if (node)
block.m_fit = splitNode(node, block.m_w, block.m_h);
else
block.m_fit = growNode(block.m_w, block.m_h);
}
return;
}

Block *GrowingPacker::findNode(Block *root, float w, float h)
{
if (root->m_used) {
Block *tmp = findNode(root->m_right, w, h);
if (tmp)
return tmp;
else
return findNode(root->m_down, w, h);
} else if ( w <= root->m_w && h <= root->m_h)
return root;
else
return nullptr;
}

Block *GrowingPacker::splitNode(Block *node, float w, float h)
{
node->m_used = true;
node->m_down  = new Block(node->m_w,     node->m_h - h, node->m_x,     node->m_y + h);
node->m_right = new Block(node->m_w - w, h,             node->m_x + w, node->m_y    );
return node;
}

Block *GrowingPacker::growNode(float w, float h)
{
bool canGrowDown  = w <= m_root->m_w;
bool canGrowRight = h <= m_root->m_h;

// attempt to keep square-ish by growing right when height is much greater than width
bool shouldGrowRight = canGrowRight && m_root->m_h >= (m_root->m_w + w);
// attempt to keep square-ish by growing down  when width  is much greater than height
bool shouldGrowDown  = canGrowDown  && m_root->m_w >= (m_root->m_h + h);

if (shouldGrowRight)
return growRight(w, h);
else if (shouldGrowDown)
return growDown(w, h);
else if (canGrowRight)
return growRight(w, h);
else if (canGrowDown)
return growDown(w, h);
else
// need to ensure sensible root starting size to avoid this happening
return nullptr;
}

Block *GrowingPacker::growRight(float w, float h)
{
m_root = new Block(m_root->m_w + w
, m_root->m_h
, 0.0f
, 0.0f
, true
, m_root
, new Block(w, m_root->m_h, m_root->m_w, 0.0f)
);
Block *node = findNode(m_root, w, h);
if (node)
return splitNode(node, w, h);
else
return nullptr;
}

Block *GrowingPacker::growDown(float w, float h)
{
m_root = new Block(m_root->m_w
, m_root->m_h + h
, 0.0f
, 0.0f
, true
, new Block (m_root->m_w, h, 0.0f, m_root->m_h)
, m_root
);
Block *node = findNode(m_root, w, h);
if (node)
return splitNode(node, w, h);
else
return nullptr;
}


Block/node class definition which is used by algorithm

#ifndef BLOCK_H
#define BLOCK_H

class EditorSceneItem;

class Block
{
public:
Block();
Block(float w, float h, float x, float y);
Block(float w, float h, float x, float y,
bool used,
Block *down, Block *right);
// Copy constructor
Block(const Block &other);
// Copy assignment operator
Block & operator= ( const Block& other );
// Destructor
~Block();
// Move constructor
Block(Block&& other);
// Move assignment operator
Block& operator=(Block &&other);

private:
void freePossibleAllocatedMemory();
void releaseResourcesWithoutFreeingMemory();
void swapInto(Block& destination) const noexcept;

public:
float m_w;
float m_h;
float m_x;
float m_y;
bool m_used;
Block *m_down = nullptr;
Block *m_right = nullptr;
Block *m_fit = nullptr;
};

#endif // BLOCK_H


Block/node class implementation

#include "block.h"

Block::Block()
:
m_w(0.0f), m_h(0.0f)
, m_x(0.0f), m_y(0.0f)
, m_used(false)
, m_down(nullptr)
, m_right(nullptr)
, m_fit(nullptr)
{

}

Block::Block(float w, float h, float x, float y)
:
m_w(w), m_h(h)
, m_x(x), m_y(y)
, m_used(false)
, m_down(nullptr)
, m_right(nullptr)
, m_fit(nullptr)
{

}

Block::Block(float w, float h, float x, float y,
bool used,
Block *down, Block *right)
:
m_w(w), m_h(h)
, m_x(x), m_y(y)
, m_used(used)
, m_down(down)
, m_right(right)
, m_fit(nullptr)
{

}

Block::Block(const Block &other)
:
m_w(other.m_w), m_h(other.m_h)
, m_x(other.m_x), m_y(other.m_y)
, m_used(other.m_used)
, m_down(other.m_down)
, m_right(other.m_right)
, m_fit(other.m_fit)
{}

Block & Block::operator= ( const Block& other )
{
// Self assignment
if (&other == this)
return *this;

this->freePossibleAllocatedMemory();
other.swapInto(*this);
return *this;
}

Block::~Block()
{
freePossibleAllocatedMemory();
}

Block::Block(Block&& other)
: Block() // delegate to the default constructor
{
other.swapInto(*this);
other.releaseResourcesWithoutFreeingMemory();
}

Block& Block::operator=(Block &&other)
{
// Self assignment
if (this == &other)
return *this;

this->freePossibleAllocatedMemory();

other.swapInto(*this);
other.releaseResourcesWithoutFreeingMemory();
return *this;
}

void Block::freePossibleAllocatedMemory()
{

// ** STRANGE: an exception is thrown at following lines when freeing memory
// Exception is avoided by commenting out lines
// Exception is possibly due to bad memory management

if (m_down) {
delete m_down;
m_down = nullptr;
}
if (m_right) {
delete m_right;
m_right = nullptr;
}
if (m_fit) {
delete  m_fit;
m_fit = nullptr;
}

}

void Block::releaseResourcesWithoutFreeingMemory()
{
// Release source
m_w = 0.0f;
m_h = 0.0f;
m_x = 0.0f;
m_y = 0.0f;
m_used = false;
m_down = nullptr;
m_right = nullptr;
m_fit = nullptr;
}

void Block::swapInto(Block& destination) const noexcept
{
destination.m_w = m_w; // Don't check equality of float
destination.m_h = m_h;
destination.m_x = m_x;
destination.m_y = m_y;
if (destination.m_used != m_used)
destination.m_used = m_used;
if (destination.m_down != m_down)
destination.m_down = m_down;
if (destination.m_right != m_right)
destination.m_right = m_right;
if (destination.m_fit != m_fit)
destination.m_fit = m_fit;
}


• Instead of managing memory allocation / deallocation manually you could use smart pointers with the correct semantics you need. – πάντα ῥεῖ Jul 27 at 7:36
• "When freeing memory with if (m_fit) { delete m_fit; m_fit = nullptr; }, exceptions are thrown" Note that your question is off-topic for Code Review. Only working code is ready for review. – πάντα ῥεῖ Jul 27 at 7:57
• @πάνταῥεῖ Thanks, I edited it out. – user4838962 Jul 27 at 8:57
• Well, I am afraid editing out doesn't make that much better. Does your code throw exceptions or not? If so, it's not working properly. – πάντα ῥεῖ Jul 27 at 9:04
• Recommended read: What is The Rule of Three? – πάντα ῥεῖ Jul 27 at 9:13

As suggested by @πάνταῥεῖ I replaced all instances of Block * pointer in the code with std::shared_ptr<Block> and I feel much better regarding memory management.
• @πάνταῥεῖ Thanks. Also the exception is resolved after implementing std::shared_ptr<> =) – user4838962 Jul 27 at 11:17