I've tried to implement a function that builds a BST from the bottom up. It works by starting with an std::vector (call this nodeList) of SPnodes (my object that is equivalent to a node in a tree), doing a comparison between adjacent entries in the vector, and if the comparison yields true, it creates a new SPnode based on a criteria I've defined.
It then points m_left (left child) to one of the SPnodes in the comparison (which one is determined by another comparison function) and likewise, points m_right to the other SPnode.
It adds the newly created SPnode to a different std::vector (call this parentList), then repeats the process with the remaining SPnodes in nodeList.
The function is recursively called with parentList being passed as its argument. The parentList is then treated as the new nodeList and the steps are repeated until nodeList contains only a single SPnode.
Problem
My problem is that when I run it, I get a double free or corruption error. I'm still not completely clear on what is causing it. It seems like it has something to do with the SPnode objects in an std::vector and memory at a certain address being deallocated twice? I see from this answer that when the std::vector destructor is called, it in turn calls the destructor for all objects it contains. My ~SPnode destructor frees memory by calling delete on m_left and m_right. So when nodeList goes out of scope, how is it possible that the memory is being deallocated twice?
Apart from my understanding of the issue, I've seen several solutions that say using a custom copy constructor and overloading the assignment operator are ways to get around the problem. However, in order to deepcopy a given SPnode would I not also have to recursively deepcopy all the child SPnodes? If so, how could I do this in a simple copy constructor?
My code for the function and SPnode class is below. Note that I realize I should have used smart pointers from the start, but I didn't realize until much later that they even existed and switching everything over would be a serious pain.
Code
SPnode header:
#ifndef SPNODEOBJ_H
#define SPNODEOBJ_H
#include "IntervalObjects.h"
#include "IntervalObj.h"
#include "InVecObj.h"
#include "StandardLib.h"
// --- SPnode Class ------------------------------------------------------------
// SPnode (or Subpaving Node), is a node in a binary tree which contains a
// parameter "box" which is an InVec object, and a left and right child which
// are also SPnode objects. These SPnode objects are the resultant boxes from
// calling the expand method on m_box. This implementation allows for two
// important characteristics: there is a way to determine "where" a given box in
// a subpaving is by iterating over a node's left or right child, which in turn
// allows for greater efficiency; secondly, the tree structure gives a "history"
// of the subpaving, which allows for the determination of parent boxes.
class SPnode
{
private:
InVec m_box;
// left and right children of this SPnode object - note that these must be
// pointers in order to use them in the definition of the class, otherwise
// SPnode would reference itself in its definition
SPnode* m_left;
SPnode* m_right;
// a boolean sepcifying whether the SPnode m_box is in the given subpaving
bool m_inSP;
bool m_hasBeenIterated;
public:
SPnode(InVec box): m_box(box), m_left(NULL), m_right(NULL), m_inSP(true),
m_hasBeenIterated(false) {}
~SPnode() {delete m_left; delete m_right;}
// getters and setters
InVec getBox() const {return m_box;}
SPnode* getLeft() const {return m_left;}
SPnode* getRight() const {return m_right;}
bool getInSP() const {return m_inSP;}
bool getIterated() const {return m_hasBeenIterated;}
void setBox(const InVec box) {m_box = box;}
void setLeft(SPnode* const p_node) {m_left = p_node;}
void setRight(SPnode* const p_node) {m_right = p_node;}
void setInSP(bool truth) {m_inSP = truth;} // when this is called truth
// should only be false
void setIterated(bool truth) {m_hasBeenIterated = truth;}
bool isLeaf() const;
friend std::ostream& operator<< (std::ostream &out, const SPnode &ASP);
friend void expand(SPnode &ASP);
friend InVec lower(const InVec &box, const Interval &width, int axis);
friend InVec upper(const InVec &box, const Interval &width, int axis);
friend void mince(SPnode &ASP);
friend SPnode regularize(ImList &list, InVec box);
friend SPnode* recRegularize(std::vector<InVec> &list, SPnode &parentNode);
};
#endif
and the function in question:
// This function builds up a tree from a list of user defined boxes
SPnode listToTree (std::vector<InVec> &boxList)
{
std::vector<SPnode> nodeList;
for (auto box : boxList)
{
nodeList.push_back(SPnode(box));
}
return recListToTree(nodeList);
}
SPnode recListToTree (std::vector<SPnode> &nodeList)
{
std::cout << "nodelist size is: " << nodeList.size() << "\n";
if (nodeList.size() == 1)
{
return nodeList.at(0);
}
std::vector<SPnode> parentNodeList;
int counter = 0;
for (auto node : nodeList)
{
if (node.getIterated())
{
counter += 1;
continue;
}
if (counter + 1 == nodeList.size())
{
parentNodeList.push_back(SPnode(node.getBox()));
break;
}
if (node.getBox().isAdjacent(nodeList.at(counter + 1).getBox()))
{
SPnode newNode
(SPnode(node.getBox().combine(nodeList.at(counter + 1).getBox())));
if (lessThan(node.getBox(), nodeList.at(counter + 1).getBox()))
{
newNode.setLeft(&node);
newNode.setRight(&(nodeList.at(counter + 1)));
}
else
{
newNode.setRight(&node);
newNode.setLeft(&(nodeList.at(counter + 1)));
}
parentNodeList.push_back(newNode);
nodeList.at(counter).setIterated(true);
nodeList.at(counter + 1).setIterated(true);
counter += 1;
}
else
{
parentNodeList.push_back(SPnode(node.getBox()));
nodeList.at(counter + 1).setIterated(true);
counter += 1;
}
}
recListToTree(parentNodeList);
}
Any and all help is appreciated!
