00001 00017 #ifndef _NTREE_H 00018 #define _NTREE_H 00019 00020 #include <map> 00021 #include <set> 00022 #include <vector> 00023 00024 namespace ace { 00025 00029 typedef size_t tree_size_t; 00035 typedef std::vector<tree_size_t> subtree_t; 00040 typedef std::set<tree_size_t> childs_t; 00049 typedef std::multimap<tree_size_t, subtree_t> mapped_subtrees_t; 00050 00057 class NTreeNode { 00058 private: 00061 tree_size_t _index; 00064 tree_size_t _parent; 00067 childs_t _childs; 00068 public: 00071 NTreeNode(void): _index(0), _parent(0), _childs() {} 00076 NTreeNode(tree_size_t index, tree_size_t parent): _index(index), _parent(parent), _childs() {} 00079 void add_child(tree_size_t child_index) { _childs.insert(child_index); } 00082 inline size_t count_childs(void) const throw() { return _childs.size(); } 00085 const childs_t& get_childs(void) const throw() { return _childs; } 00088 inline tree_size_t index(void) const throw() { return _index; } 00092 inline bool is_abstract(void) const throw() { return _index == 0; } 00095 inline bool is_leaf(void) const throw() { return _childs.empty(); } 00098 inline bool is_root(void) const throw() { return _parent == 0; } 00101 inline tree_size_t parent(void) const throw() { return _parent; } 00102 }; 00103 00109 inline bool operator<(const NTreeNode& lhs, const NTreeNode& rhs) { 00110 return lhs.index() < rhs.index(); 00111 } 00112 00120 typedef std::vector<NTreeNode> ntree_t; 00121 00130 void extract_subtrees(ntree_t& nodes, tree_size_t subtree_size, mapped_subtrees_t& results); 00131 00132 } // namespace ace 00133 00134 #endif
1.5.6