//////////////////////////////////////////////////////////////////////////////// // Author: Andy Rushton // Copyright: (c) Southampton University 1999-2004 // (c) Andy Rushton 2004 onwards // License: BSD License, see ../docs/license.html //////////////////////////////////////////////////////////////////////////////// #include #include namespace stlplus { //////////////////////////////////////////////////////////////////////////////// // ntree_node template class ntree_node { public: master_iterator, ntree_node > m_master; T m_data; ntree_node* m_parent; std::vector*> m_children; public: ntree_node(const ntree* owner, const T& data = T()) : m_master(owner,this), m_data(data), m_parent(0) { } void change_owner(const ntree* owner) { m_master.change_owner(owner); for (typename std::vector*>::iterator i = m_children.begin(); i != m_children.end(); i++) (*i)->change_owner(owner); } ~ntree_node(void) { m_parent = 0; for (typename std::vector*>::iterator i = m_children.begin(); i != m_children.end(); i++) delete *i; } }; template static ntree_node* ntree_copy(const ntree* new_owner, ntree_node* root) { if (!root) return 0; ntree_node* new_tree = new ntree_node(new_owner, root->m_data); for (typename std::vector*>::iterator i = root->m_children.begin(); i != root->m_children.end(); i++) { ntree_node* new_child = ntree_copy(new_owner, *i); new_tree->m_children.push_back(new_child); new_child->m_parent = new_tree; } return new_tree; } template static unsigned ntree_size(ntree_node* root) { if (!root) return 0; unsigned result = 1; for (typename std::vector*>::iterator i = root->m_children.begin(); i != root->m_children.end(); i++) result += ntree_size(*i); return result; } template static unsigned ntree_depth(ntree_node* root) { unsigned depth = 0; for (ntree_node* i = root; i; i = i->m_parent) depth++; return depth; } //////////////////////////////////////////////////////////////////////////////// // ntree_iterator // constructor to create a null iterator - you must assign a valid value to this iterator before using it template ntree_iterator::ntree_iterator(void) { } // used to create an alias of an iterator template ntree_iterator::ntree_iterator(const safe_iterator, ntree_node >& iterator) : safe_iterator,ntree_node >(iterator) { } // constructor used by ntree to create a non-null iterator template ntree_iterator::ntree_iterator(ntree_node* node) : safe_iterator,ntree_node >(node->m_master) { } // constructor used by ntree to create an end iterator template ntree_iterator::ntree_iterator(const ntree* owner) : safe_iterator,ntree_node >(owner) { } // destructor template ntree_iterator::~ntree_iterator(void) { } template typename ntree_iterator::const_iterator ntree_iterator::constify(void) const { return ntree_iterator(*this); } template typename ntree_iterator::iterator ntree_iterator::deconstify(void) const { return ntree_iterator(*this); } template bool ntree_iterator::operator == (const typename ntree_iterator::this_iterator& r) const { return this->equal(r); } template bool ntree_iterator::operator != (const typename ntree_iterator::this_iterator& r) const { return !operator==(r); } template bool ntree_iterator::operator < (const typename ntree_iterator::this_iterator& r) const { return this->compare(r) < 0; } template typename ntree_iterator::reference ntree_iterator::operator*(void) const { this->assert_valid(); return this->node()->m_data; } template typename ntree_iterator::pointer ntree_iterator::operator->(void) const { return &(operator*()); } //////////////////////////////////////////////////////////////////////////////// // ntree_prefix_iterator template ntree_prefix_iterator::ntree_prefix_iterator(void) { } template ntree_prefix_iterator::~ntree_prefix_iterator(void) { } template ntree_prefix_iterator::ntree_prefix_iterator(const ntree_iterator& i) : m_iterator(i) { // this is initialised with the root node // which is also the first node in prefix traversal order } template bool ntree_prefix_iterator::null(void) const { return m_iterator.null(); } template bool ntree_prefix_iterator::end(void) const { return m_iterator.end(); } template bool ntree_prefix_iterator::valid(void) const { return m_iterator.valid(); } template typename ntree_prefix_iterator::const_iterator ntree_prefix_iterator::constify(void) const { return ntree_prefix_iterator(m_iterator); } template typename ntree_prefix_iterator::iterator ntree_prefix_iterator::deconstify(void) const { return ntree_prefix_iterator(m_iterator); } template ntree_iterator ntree_prefix_iterator::simplify(void) const { return m_iterator; } template bool ntree_prefix_iterator::operator == (const typename ntree_prefix_iterator::this_iterator& r) const { return m_iterator == r.m_iterator; } template bool ntree_prefix_iterator::operator != (const typename ntree_prefix_iterator::this_iterator& r) const { return m_iterator != r.m_iterator; } template bool ntree_prefix_iterator::operator < (const typename ntree_prefix_iterator::this_iterator& r) const { return m_iterator < r.m_iterator; } template typename ntree_prefix_iterator::this_iterator& ntree_prefix_iterator::operator ++ (void) { // pre-increment operator // algorithm: if there are any children, visit child 0, otherwise, go to // parent and deduce which child the start node was of that parent - if // there are further children, go into the next one. Otherwise, go up the // tree and test again for further children. Return null if there are no // further nodes m_iterator.assert_valid(); ntree_node* old_node = m_iterator.node(); if (!old_node->m_children.empty()) { // simply take the first child of this node m_iterator.set(old_node->m_children[0]->m_master); } else { // this loop walks up the parent pointers // either it will walk off the top and exit or a new node will be found and the loop will exit for (;;) { // go up a level ntree_node* parent = old_node->m_parent; if (!parent) { // we've walked off the top of the tree, so return end m_iterator.set_end(); break; } else { // otherwise walk down the next child - if there is one // find which index the old node was relative to this node typename std::vector*>::iterator found = std::find(parent->m_children.begin(), parent->m_children.end(), old_node); // if this was found, then see if there is another and if so return that found++; if (found != parent->m_children.end()) { // visit the next child m_iterator.set((*found)->m_master); break; } else { // keep going up old_node = parent; } } } } return *this; } template typename ntree_prefix_iterator::this_iterator ntree_prefix_iterator::operator ++ (int) { // post-increment is defined in terms of the pre-increment ntree_prefix_iterator result(*this); ++(*this); return result; } template typename ntree_prefix_iterator::reference ntree_prefix_iterator::operator*(void) const { return m_iterator.operator*(); } template typename ntree_prefix_iterator::pointer ntree_prefix_iterator::operator->(void) const { return m_iterator.operator->(); } template const ntree_iterator& ntree_prefix_iterator::get_iterator(void) const { return m_iterator; } template ntree_iterator& ntree_prefix_iterator::get_iterator(void) { return m_iterator; } //////////////////////////////////////////////////////////////////////////////// // ntree_postfix_iterator template ntree_postfix_iterator::ntree_postfix_iterator(void) { } template ntree_postfix_iterator::~ntree_postfix_iterator(void) { } template ntree_postfix_iterator::ntree_postfix_iterator(const ntree_iterator& i) : m_iterator(i) { // this is initialised with the root node // initially traverse to the first node to be visited if (m_iterator.valid()) { ntree_node* node = m_iterator.node(); while (!node->m_children.empty()) node = node->m_children[0]; m_iterator.set(node->m_master); } } template bool ntree_postfix_iterator::null(void) const { return m_iterator.null(); } template bool ntree_postfix_iterator::end(void) const { return m_iterator.end(); } template bool ntree_postfix_iterator::valid(void) const { return m_iterator.valid(); } template typename ntree_postfix_iterator::const_iterator ntree_postfix_iterator::constify(void) const { return ntree_postfix_iterator(m_iterator); } template typename ntree_postfix_iterator::iterator ntree_postfix_iterator::deconstify(void) const { return ntree_postfix_iterator(m_iterator); } template ntree_iterator ntree_postfix_iterator::simplify(void) const { return m_iterator; } template bool ntree_postfix_iterator::operator == (const typename ntree_postfix_iterator::this_iterator& r) const { return m_iterator == r.m_iterator; } template bool ntree_postfix_iterator::operator != (const typename ntree_postfix_iterator::this_iterator& r) const { return m_iterator != r.m_iterator; } template bool ntree_postfix_iterator::operator < (const typename ntree_postfix_iterator::this_iterator& r) const { return m_iterator < r.m_iterator; } template typename ntree_postfix_iterator::this_iterator& ntree_postfix_iterator::operator ++ (void) { // pre-increment operator // algorithm: this node has been visited, therefore all children must have // already been visited. So go to parent. Return null if the parent is null. // Otherwise deduce which child the start node was of that parent - if there // are further children, go into the next one and then walk down any // subsequent first-child pointers to the bottom. Otherwise, if there are no // children then the parent node is the next in the traversal. m_iterator.assert_valid(); // go up a level ntree_node* old_node = m_iterator.node(); ntree_node* parent = old_node->m_parent; if (!parent) { // we've walked off the top of the tree, so return end m_iterator.set_end(); } else { // otherwise find which index the old node was relative to this node typename std::vector*>::iterator found = std::find(parent->m_children.begin(), parent->m_children.end(), old_node); // if this was found, then see if there is another found++; if (found != parent->m_children.end()) { // if so traverse to it and walk down the leftmost child pointers to the bottom of the new sub-tree ntree_node* new_node = *found; while (!new_node->m_children.empty()) new_node = new_node->m_children[0]; m_iterator.set(new_node->m_master); } else { // the parent's children have all been visited - so the parent is visited m_iterator.set(parent->m_master); } } return *this; } template typename ntree_postfix_iterator::this_iterator ntree_postfix_iterator::operator ++ (int) { // post-increment is defined in terms of the pre-increment ntree_postfix_iterator result(*this); ++(*this); return result; } template typename ntree_postfix_iterator::reference ntree_postfix_iterator::operator*(void) const { return m_iterator.operator*(); } template typename ntree_postfix_iterator::pointer ntree_postfix_iterator::operator->(void) const { return m_iterator.operator->(); } template const ntree_iterator& ntree_postfix_iterator::get_iterator(void) const { return m_iterator; } template ntree_iterator& ntree_postfix_iterator::get_iterator(void) { return m_iterator; } //////////////////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////////////// // ntree //////////////////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////////////// template ntree::ntree(void) : m_root(0) { } template ntree::~ntree(void) { if (m_root) delete m_root; } template ntree::ntree(const ntree& r) : m_root(0) { *this = r; } template ntree& ntree::operator=(const ntree& r) { if (m_root) delete m_root; m_root = ntree_copy(this, r.m_root); return *this; } template bool ntree::empty(void) const { return m_root == 0; } template unsigned ntree::size(void) const { return ntree_size(m_root); } template unsigned ntree::size(const typename ntree::const_iterator& i) const { i.assert_valid(this); return ntree_size(i.node()); } template unsigned ntree::size(const typename ntree::iterator& i) { i.assert_valid(this); return ntree_size(i.node()); } template unsigned ntree::depth(const typename ntree::const_iterator& i) const { i.assert_valid(this); return ntree_depth(i.node()); } template unsigned ntree::depth(const typename ntree::iterator& i) { i.assert_valid(this); return ntree_depth(i.node()); } template typename ntree::const_iterator ntree::root(void) const { if (!m_root) return ntree_iterator(this); return ntree_iterator(m_root); } template typename ntree::iterator ntree::root(void) { if (!m_root) return ntree_iterator(this); return ntree_iterator(m_root); } template unsigned ntree::children(const typename ntree::const_iterator& i) const { i.assert_valid(this); return static_cast(i.node()->m_children.size()); } template unsigned ntree::children(const typename ntree::iterator& i) { i.assert_valid(this); return static_cast(i.node()->m_children.size()); } template typename ntree::const_iterator ntree::child(const typename ntree::const_iterator& i, unsigned child) const { i.assert_valid(this); if (child >= children(i)) throw std::out_of_range("stlplus::ntree::child - child out of range"); return ntree_iterator(i.node()->m_children[child]); } template typename ntree::iterator ntree::child(const typename ntree::iterator& i, unsigned child) { i.assert_valid(this); if (child >= children(i)) throw std::out_of_range("stlplus::ntree::child - child out of range"); return ntree_iterator(i.node()->m_children[child]); } template unsigned ntree::child_offset(const typename ntree::const_iterator& root, const typename ntree::const_iterator& child) const { root.assert_valid(this); child.assert_valid(this); ntree_node* root_node = root.node(); ntree_node* child_node = child.node(); for (unsigned offset = 0; offset < static_cast(root_node->m_children.size()); ++offset) if (root_node->m_children[offset] == child_node) return offset; return static_cast(-1); } template unsigned ntree::child_offset(const typename ntree::iterator& root, const typename ntree::iterator& child) { root.assert_valid(this); child.assert_valid(this); ntree_node* root_node = root.node(); ntree_node* child_node = child.node(); for (unsigned offset = 0; offset < static_cast(root_node->m_children.size()); ++offset) if (root_node->m_children[offset] == child_node) return offset; return static_cast(-1); } template typename ntree::const_iterator ntree::parent(const typename ntree::const_iterator& i) const { i.assert_valid(this); ntree_node* parent = i.node()->m_parent; if (!parent) return ntree_iterator(this); return ntree_iterator(parent); } template typename ntree::iterator ntree::parent(const typename ntree::iterator& i) { i.assert_valid(this); ntree_node* parent = i.node()->m_parent; if (!parent) return ntree_iterator(this); return ntree_iterator(parent); } template typename ntree::const_prefix_iterator ntree::prefix_begin(void) const { return ntree_prefix_iterator(root()); } template typename ntree::prefix_iterator ntree::prefix_begin(void) { return ntree_prefix_iterator(root()); } template typename ntree::const_prefix_iterator ntree::prefix_end(void) const { return ntree_prefix_iterator(ntree_iterator(this)); } template typename ntree::prefix_iterator ntree::prefix_end(void) { return ntree_prefix_iterator(ntree_iterator(this)); } template typename ntree::const_postfix_iterator ntree::postfix_begin(void) const { return ntree_postfix_iterator(root()); } template typename ntree::postfix_iterator ntree::postfix_begin(void) { return ntree_postfix_iterator(root()); } template typename ntree::const_postfix_iterator ntree::postfix_end(void) const { return ntree_postfix_iterator(ntree_iterator(this)); } template typename ntree::postfix_iterator ntree::postfix_end(void) { return ntree_postfix_iterator(ntree_iterator(this)); } template typename ntree::iterator_vector ntree::breadth_first_traversal(void) { typename ntree::iterator_vector result; if (m_root) { // seed the traversal the the root node result.push_back(root()); // now walk through the result, appending each node's children // allow for the vector to reallocate, so don't use vector iterators for (unsigned i = 0; i < result.size(); i++) { unsigned count = children(result[i]); for (unsigned c = 0; c < count; c++) result.push_back(child(result[i], c)); } } return result; } template typename ntree::const_iterator_vector ntree::breadth_first_traversal(void) const { typename ntree::const_iterator_vector result; if (m_root) { // seed the traversal the the root node result.push_back(root()); // now walk through the result, appending each node's children // allow for the vector to reallocate, so don't use vector iterators for (unsigned i = 0; i < result.size(); i++) { unsigned count = children(result[i]); for (unsigned c = 0; c < count; c++) result.push_back(child(result[i], c)); } } return result; } template typename ntree::iterator ntree::insert(const T& data) { // insert a new node as the root erase(); m_root = new ntree_node(this,data); return ntree_iterator(m_root); } template typename ntree::iterator ntree::insert(const typename ntree::iterator& i, unsigned offset, const T& data) { // if i is the end iterator, this means insert a new root // if (i.end()) // return insert(data); // otherwise, insert a new child i.assert_valid(this); if (offset > children(i)) throw std::out_of_range("stlplus::ntree::insert - offset out of range"); ntree_node* new_node = new ntree_node(this,data); i.node()->m_children.insert(i.node()->m_children.begin()+offset,new_node); new_node->m_parent = i.node(); return ntree_iterator(new_node); } template typename ntree::iterator ntree::insert(const typename ntree::iterator& i, const T& data) { return insert(i, children(i), data); } template typename ntree::iterator ntree::append(const typename ntree::iterator& i, const T& data) { return insert(i, children(i), data); } template typename ntree::iterator ntree::insert(const ntree& tree) { // insert a whole tree as root erase(); m_root = ntree_copy(this, tree.m_root); return ntree_iterator(m_root); } template typename ntree::iterator ntree::insert(const typename ntree::iterator& i, unsigned offset, const ntree& tree) { // insert a whole tree as a child of i i.assert_valid(this); if (offset > children(i)) throw std::out_of_range("stlplus::ntree::insert - offset out of range"); ntree_node* new_node = ntree_copy(this, tree.m_root); i.node()->m_children.insert(i.node()->m_children.begin()+offset,new_node); new_node->m_parent = i.node(); return ntree_iterator(new_node); } template typename ntree::iterator ntree::insert(const typename ntree::iterator& i, const ntree& tree) { return insert(i, children(i), tree); } template typename ntree::iterator ntree::append(const typename ntree::iterator& i, const ntree& tree) { return insert(i, children(i), tree); } template typename ntree::iterator ntree::move(ntree& tree) { // insert a whole tree as root, removing it from source erase(); m_root = tree.m_root; tree.m_root = 0; if (m_root) m_root->change_owner(this); return ntree_iterator(m_root); } template typename ntree::iterator ntree::move(const typename ntree::iterator& i, unsigned offset, ntree& tree) { // insert a whole tree as a child of i i.assert_valid(this); if (offset > children(i)) throw std::out_of_range("stlplus::ntree::move - offset out of range"); ntree_node* new_node = tree.m_root; tree.m_root = 0; if (new_node) new_node->change_owner(this); i.node()->m_children.insert(i.node()->m_children.begin()+offset,new_node); new_node->m_parent = i.node(); return ntree_iterator(new_node); } template typename ntree::iterator ntree::move(const typename ntree::iterator& i, ntree& tree) { return move(i, children(i), tree); } template typename ntree::iterator ntree::push(const typename ntree::iterator& node, const T& data) { // insert a new node to replace the existing node in the tree // making the original node the child of the new node // i.e. (node) becomes (new)->(node) // afterwards, the iterator still points to the old node, now the child // returns the iterator to the new node node.assert_valid(this); ntree_node* new_node = new ntree_node(this,data); if (node.node() == m_root) { // pushing the root node m_root = new_node; new_node->m_parent = 0; } else { // pushing a sub-node *(std::find(node.node()->m_parent->m_children.begin(), node.node()->m_parent->m_children.end(), node.node())) = new_node; new_node->m_parent = node.node()->m_parent; } // link up the old node as the child of the new node new_node->m_children.insert(new_node->m_children.begin(),node.node()); node.node()->m_parent = new_node; return ntree_iterator(new_node); } template void ntree::pop(const typename ntree::iterator& parent, unsigned offset) { // inverse of push // removes the specified child of the parent node, adding its children to the parent node at the same offset parent.assert_valid(this); ntree_node* node = parent.node(); if (offset >= node->m_children.size()) throw std::out_of_range("stlplus::ntree::pop - offset out of range"); // move the grandchildren first ntree_node* child = parent.node()->m_children[offset]; while (!child->m_children.empty()) { // remove the last grandchild and insert into node just after the child to be removed ntree_node* grandchild = child->m_children[child->m_children.size()-1]; child->m_children.pop_back(); node->m_children.insert(node->m_children.begin()+offset+1, grandchild); grandchild->m_parent = node; } // now remove the child node->m_children.erase(node->m_children.begin()+offset); delete child; } template void ntree::erase(void) { // erase the whole tree erase(root()); } template void ntree::erase(const typename ntree::iterator& i) { if (!i.end()) { // erase this node and its subtree // do this by erasing this child of its parent // handle the case of erasing the root i.assert_valid(this); ntree_node* node = i.node(); if (node == m_root) { delete m_root; m_root = 0; } else { ntree_node* parent = node->m_parent; // impossible for parent to be null - should assert this typename std::vector*>::iterator found = std::find(parent->m_children.begin(), parent->m_children.end(), node); // impossible for find to fail - should assert this parent->m_children.erase(found); delete node; } } } // erase a child designated by an offset into the node's children template void ntree::erase_child(const typename ntree::iterator& i, unsigned offset) { if (offset >= children(i)) throw std::out_of_range("stlplus::ntree::erase_child - offset out of range"); // unhook from the children array ntree_node* node = i.node()->m_children[offset]; i.node()->m_children.erase(i.node()->m_children.begin() + offset); // now delete the subtree delete node; } // synonym of above template void ntree::erase(const typename ntree::iterator& i, unsigned offset) { erase_child(i, offset); } // erase all children template void ntree::erase_children(const typename ntree::iterator& i) { while(children(i) > 0) erase_child(i, 0); } template ntree ntree::subtree(void) { return subtree(root()); } template ntree ntree::subtree(const typename ntree::iterator& i) { ntree result; if (!i.end()) { i.assert_valid(this); result.m_root = ntree_copy(&result, i.node()); } return result; } template ntree ntree::subtree(const typename ntree::iterator& i, unsigned offset) { return subtree(child(i, offset)); } template ntree ntree::cut(void) { return cut(root()); } template ntree ntree::cut(const typename ntree::iterator& i) { ntree result; if (!i.end()) { i.assert_valid(this); ntree_node* node = i.node(); if (node == m_root) { result.m_root = m_root; m_root = 0; } else { ntree_node* parent = node->m_parent; // impossible for parent to be null - should assert this typename std::vector*>::iterator found = std::find(parent->m_children.begin(), parent->m_children.end(), node); // impossible for find to fail - should assert this result.m_root = *found; parent->m_children.erase(found); } if (result.m_root) { result.m_root->m_parent = 0; result.m_root->change_owner(&result); } } return result; } template ntree ntree::cut(const typename ntree::iterator& i, unsigned offset) { return cut(child(i, offset)); } template void ntree::reorder(const typename ntree::iterator& node, unsigned child_offset, unsigned new_offset) { // check preconditions node.assert_valid(this); if (child_offset >= children(node)) throw std::out_of_range("stlplus::ntree::reorder - child offset out of range"); if (new_offset >= children(node)) throw std::out_of_range("stlplus::ntree::reorder - new offset out of range"); // do nothing if the offsets are the same, i.e. move to the same place if (new_offset == child_offset) return; // perform the move // Note: this is not a swap operation, but a remove then re-insert which preserves the order of the remaining children ntree_node* node_node = node.node(); ntree_node* child_node = node_node->m_children[child_offset]; node_node->m_children.erase(node_node->m_children.begin() + child_offset); node_node->m_children.insert(node_node->m_children.begin() + new_offset, child_node); } template void ntree::swap(const typename ntree::iterator& node, unsigned child1, unsigned child2) { // check preconditions node.assert_valid(this); if (child1 >= children(node)) throw std::out_of_range("stlplus::ntree::reorder - child1 offset out of range"); if (child2 >= children(node)) throw std::out_of_range("stlplus::ntree::reorder - child2 offset out of range"); // do nothing if the offsets are the same, i.e. move to the same place if (child1 == child2) return; // perform the move ntree_node* node_node = node.node(); std::swap(node_node->m_children[child1], node_node->m_children[child2]); } //////////////////////////////////////////////////////////////////////////////// } // end namespace stlplus