assignment of template descendant

[John87Connor]

hi everyone, i'd like to implement a "node tree": a node can have multiple children, but only 1 (or no) parent. besides the node hierarchy, each node has additional data inherited from its "ancestor" (in class hierarchy, not node hierarchy)

this is what i have now:

#pragma once

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


template<typename T>
class CNode : public T
{
public:

	CNode() { m_id = NewID(); }
	virtual ~CNode() {}

	int ID() const { return m_id; }

	CNode<T>* Root() {
		CNode<T>* root = Me();
		while (root->Parent() != nullptr)
			root = root->Parent();
		return root;
	}

	CNode<T>* Parent() { return m_parent; }

	CNode<T>* Me() { return this; }

	std::vector<CNode<T>*> Siblings() {
		if (m_parent == nullptr)
			return {};
		return m_parent->Children();
	}

	std::vector<CNode<T>*> Children() {
		std::vector<CNode<T>*> children;
		for (auto& child : m_children)
			children.push_back(&child);
		return children;
	}

	CNode<T>* AddSibling() { 
		if (m_parent == nullptr)
			return nullptr;
		return m_parent->AddChild();
	}

	CNode<T>* AddChild() {
		m_children.push_back({});
		m_children.back().m_parent = this;
		RecursionResetParent(Root());
		return &m_children.back();
	}

	CNode<T>* FindNode(int ID) {
		return RecursionIsNodeFound(Root(), ID);
	}

	void Print() {
		RecursionPrint(Root(), "", 0);
	}

private:

	CNode<T>* m_parent = nullptr;
	std::vector<CNode<T>> m_children;
	int m_id = 0;

	static int NewID() {
		static int id = 0;
		return id++;
	}

	static void RecursionResetParent(CNode<T>* node)
	{
		auto children = node->Children();
		for (auto& child : children)
		{
			child->m_parent = node;
			RecursionResetParent(child);
		}
	}

	static CNode<T>* RecursionIsNodeFound(CNode<T>* node, int ID)
	{
		if (node == nullptr)
			return nullptr;

		if (node->ID() == ID)
			return node->Me();

		auto children = node->Children();
		for (auto& child : children)
		{
			CNode<T>* found = RecursionIsNodeFound(child, ID);
			if (found != nullptr)
				return found;
		}

		return nullptr;
	}

	static void RecursionPrint(CNode<T>* node, const std::string& leftdistance, unsigned int generation)
	{
		std::cout << leftdistance << "--> Generation: " << generation << " ID = " << node->ID() << std::endl;

		auto children = node->Children();
		for (auto& child : children)
			RecursionPrint(child, leftdistance + "\t", generation + 1);
	}

};

question:
how can i copy a node? i mean the inherited data (= template parameter) each node contains ?

i plan to add another "CNode<T>* AddChild(const CNode<T>* other)" from which i recursively copy the nodes. but each node has to be uniquely identifyable, so the "int m_id" member must not be copied but newly generated for the receiving tree.

i appreciate any advice ! :-)

[dhayden]

Line 27. This isn't necessary. Any code that can call the Me() method on an instance can just that instance directly. Put another way, if node->Me() is better than node, then isn't node->Me()->Me() even better? How about node->Me()->Me()->Me()?

Line 29 & 35: the vector is only valid until the next call that modifies the vector of children. That might be okay, but I thought I'd point it out. You might want to store the children as a vector of pointers instead of a vector of instances.

Line 51. This is necessary because you're storing the items as a vector of instances instead of pointers. So another good reason to store a vector of pointers.

Line 56: I'd have this find the ID within the current node's descendants. If someone wants to find the node within the entire tree then let them call the function on the root node.

Line 60: Same comment as for line 56.

Line 69 & 13: Hmm. What happens when you copy a node? The copy will have the same ID as the source. Is that what you want? It's fine when copying the vector of children, but is it always the right thing? Yet another reason to store a vector of pointers to nodes.

Line 74: Why have a static method that takes a pointer to an instance? Why not just make this an ordinary method with no parameter?

Line 76: Why go to the trouble to create a vector of pointers? Why not make line 77:
for (auto &child : m_children) and make matching changes to lines 77 & 78?

Line 84: Make this an ordinary method instead of static:
CNode<T>* RecursionIsNodeFound(int ID)

how can i copy a node? i mean the inherited data (= template parameter) each node contains ?

If you store a vector of pointers instead of a vector of instances then you can make a copy constructor that will create a new ID instead of copying the old one.

[John87Connor]

thank you !

i first thought about storing pointers instead of instances, but then i tried to avoid that because of possible memory leaks, but .. ok, here i am with the new version:

#pragma once

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


template<typename T>
class CNode : public T
{
public:

	CNode() { m_id = NewID(); }

	virtual ~CNode() {
		for (auto& child : m_children)
			delete child;
		m_children.clear();
	}

	int ID() const { return m_id; }

	CNode<T>* Root() {
		CNode<T>* root = this;
		while (root->Parent() != nullptr)
			root = root->Parent();
		return root;
	}

	CNode<T>* Parent() { return m_parent; }

	std::vector<CNode<T>*> Siblings() {
		if (m_parent == nullptr)
			return {};
		return m_parent->Children();
	}

	std::vector<CNode<T>*> Children() {
		return m_children;
	}

	CNode<T>* AddSibling() { 
		if (m_parent == nullptr)
			return nullptr;
		return m_parent->AddChild();
	}

	CNode<T>* AddChild() {
		m_children.push_back(new CNode<T>);
		m_children.back()->m_parent = this;
		return m_children.back();
	}

	CNode<T>* FindNode(int ID) {
		if (m_id == ID)
			return this;

		for (auto& child : m_children)
		{
			CNode<T>* found = child->FindNode(ID);
			if (found != nullptr)
				return found;
		}

		return nullptr;
	}

	void Print(const std::string& leftdistance, unsigned int generation) {
		std::cout << leftdistance << "--> Generation: " << generation << " ID = " << m_id << std::endl;

		for (auto& child : m_children)
			child->Print(leftdistance + "\t", generation + 1);
	}

private:

	CNode<T>* m_parent = nullptr;
	std::vector<CNode<T>*> m_children;
	int m_id = 0;

	static int NewID() {
		static int id = 0;
		return id++;
	}

};

question 1:
is it a "good" idea to inherit from "T" (template parameter) ?
in case T has not a virtual destructor, if i remember it correctly then the only destructor that will be called is the "base"'s destructor (since there is no v-table entry, right ?)
or should i just add a member:
"public T NodeData;"

question 2:
copying or assigning doesnt make much sense (imho), so i think i'll delete copy constructor and assignment op. but assuming that i still inherit from T, and i want to implement another function:

CNode<T>* AddChild(const CNode<T>* anothertree);

how (what syntax) can i assign the "node content" that a node inherits from T ? is that even possible ?

[John87Connor]

tried to implement it like this, put this doesnt compile:

CNode<T>* AddChild(const CNode<T>* other) {
		if (other == nullptr)
			return nullptr;

		/* do not copy any node from this tree */
		if (Root()->FindNode(other->ID()))
			return nullptr;

		auto node = AddChild();
		node::T = other::T;
		return node;
}

what doesnt work is that line:
node::T = other::T;

how can i fix that ?

[MikeyBoy]

If it doesn't compile, then your compiler will be reporting an error message that gives information about what the problem is.

I know it's fun to have secrets, but on this occasion, sharing that particular information might prove to be more productive in helping us to help you.

[mbozzi]

is it a "good" idea to inherit from "T" (template parameter) ?

The most obvious failure case is that you can no longer handle types marked final

[John87Connor]

i solved it, i just removed the template T as base class and added a public member "T Data;", thank you though.