I'm trying to create a tree. My very first requirement is that the objects within a tree level are ordered by its insertion order.
As a first attempt I used stl vector class:
#include <vector>
#include <iostream>
#include <string>
class Node;
typedef std::vector<Node> NodeList;
class Node
{
public:
Node(const std::string& name, int val=0): name_(name), value_(val), list_() {}
Node(const Node& nd): name_(nd.name_), value_(nd.value_), list_(nd.list_) {}
Node& operator=(const Node& nd)
{
name_ = nd.name_;
value_ = nd.value_;
list_ = nd.list_;
return *this;
}
const std::string& name(void) const {return name_;}
NodeList& list(void) {return list_;}
const NodeList& list(void) const {return list_;}
int value(void) const {return value_;}
void value(int val) {value_ = val;}
private:
std::string name_;
int value_;
NodeList list_;
};
std::ostream& operator<<(std::ostream& os, const Node& nd)
{
os << nd.name() << "=\"" << nd.value() << "\"";
return os;
}
std::ostream& operator<<(std::ostream& os, const NodeList& ndlst)
{
for(NodeList::const_iterator it = ndlst.begin(); it < ndlst.end(); it++)
{
os << ' ' << *it;
}
return os;
}
int main()
{
std::cout << "Creating a little tree..." << std::endl;
Node a("ROOT", 1);
a.list().push_back(Node("LEVEL1_1", 21));
a.list().push_back(Node("LEVEL1_2", 22));
a.list().push_back(Node("LEVEL1_3", 23));
a.list().push_back(Node("LEVEL1_4", 24));
a.list().at(2).list().push_back(Node("LEVEL2_1", 231));
std::cout << "Done. Now let's see some values." << std::endl;
std::cout << "root: " << a.value() << ", root->node2: "
<< a.list().at(1).value()
<< ", root->node3->node1: "
<< a.list().at(2).list().at(0).value()
<< std::endl;
std::cout << "Ok, now let's use our '<<' operators." << std::endl;
std::cout << a << std::endl;
std::cout << a.list() << std::endl;
return 0;
}
This little program compiles OK and executes as expected.
As a step further, I would like to add the capability to access objects in a tree level by its name, so I tryed using boost multi index so I modified the Node class as follows:
class Node;
struct Name{};
typedef boost::multi_index::multi_index_container<
Node,
boost::multi_index::indexed_by<
boost::multi_index::random_access<>,
boost::multi_index::hashed_non_unique<
boost::multi_index::tag<Name>,
boost::multi_index::const_mem_fun<Node, const std::string&, &Node::name>
>
>
> NodeList;
class Node
{
public:
Node(const std::string& name, int val=0): name_(name), value_(val), list_() {}
Node(const Node& nd): name_(nd.name_), value_(nd.value_), list_(nd.list_) {}
Node& operator=(const Node& nd)
{
name_ = nd.name_;
value_ = nd.value_;
list_ = nd.list_;
return *this;
}
const std::string& name(void) const {return name_;}
int value(void) const {return value_;}
void value(int val) {value_ = val;}
NodeList& list(void) {return list_;}
const NodeList& list(void) const {return list_;}
private:
std::string name_;
int value_;
NodeList list_;
};
But it does not compile at all. Using gnu g++ version 4.6.1 the very first error is
tree.cpp:19:65: error: incomplete type 'Node' used in nested name specifier
Can someone help me solve this mutual dependence?
Thank you very much.
Best regards
Thanks to James Hopkin, I have the program partially working:
#include <boost/multi_index_container.hpp>
#include <boost/multi_index/random_access_index.hpp>
#include <boost/multi_index/hashed_index.hpp>
#include <boost/multi_index/identity.hpp>
#include <boost/multi_index/global_fun.hpp>
#include <iostream>
#include <string>
class Node;
struct Name{};
const std::string& getNodeName(const Node& nd);
typedef boost::multi_index::multi_index_container<
Node,
boost::multi_index::indexed_by<
boost::multi_index::random_access<>,
boost::multi_index::hashed_non_unique<
boost::multi_index::tag<Name>,
boost::multi_index::global_fun<const Node&, const std::string&, &getNodeName>
>
>
> NodeList;
class Node
{
public:
Node(const std::string& name, int val=0): name_(name), value_(val), list_(new NodeList) {}
Node(const Node& nd): name_(nd.name_), value_(nd.value_), list_(new NodeList(*nd.list_)) {}
virtual ~Node() {delete list_;}
Node& operator=(const Node& nd)
{
name_ = nd.name_;
value_ = nd.value_;
*list_ = *nd.list_;
return *this;
}
const std::string& name(void) const {return name_;}
int value(void) const {return value_;}
void value(int val) {value_ = val;}
NodeList& list(void) {return *list_;}
const NodeList& list(void) const {return *list_;}
friend const std::string& getNodeName(const Node& nd);
private:
std::string name_;
int value_;
NodeList* list_;
};
const std::string& getNodeName(const Node& nd)
{
return nd.name_;
}
std::ostream& operator<<(std::ostream& os, const Node& nd)
{
os << nd.name() << "=\"" << nd.value() << "\"";
return os;
}
std::ostream& operator<<(std::ostream& os, const NodeList& ndlst)
{
for(NodeList::const_iterator it = ndlst.begin(); it < ndlst.end(); it++)
{
const Node& nd = *it;
os << ' ' << nd;
}
return os;
}
int main()
{
std::cout << "Creating a little tree..." << std::endl;
Node a("ROOT", 1);
a.list().push_back(Node("LEVEL1_1", 21));
a.list().push_back(Node("LEVEL1_2", 22));
a.list().push_back(Node("LEVEL1_3", 23));
a.list().push_back(Node("LEVEL1_4", 24));
// a.list().at(2).list().push_back(Node("LEVEL2_1", 231)); // First call to "at()" returns a read-only iterador so I can't append elements to its pointed object.
std::cout << "Done. Now let's see some values." << std::endl;
std::cout << "root: " << a.value() << ", root->node2: "
<< a.list().at(1).value() << std::endl;
/* << ", root->node3->node1: " << a.list().at(2).list().at(0).value()
<< std::endl; */
std::cout << "Ok, now let's use our '<<' operators." << std::endl;
std::cout << a << std::endl;
std::cout << a.list() << std::endl;
return 0;
}
Now I must work in the replace/modify methods in order to add elements to the objects retrieved by multi-index itrerators.
Thank you very much.
It looks like the use of
Node::name
in the typedef is causing that error. Maybe you could create a non-member function to access aNode
's name and use that instead.