|
How to remove node by it iterator?
example:
<br />
test.cpp<br />
class test_tree<br />
{<br />
~test_tree();<br />
<br />
tree<key, TData> mytree;<br />
}<br />
...<br />
key _key2find(...);<br />
tree<key, TData*>::iterator _it_node = mytree.find(_key2find);<br />
if(_it_node != end())<br />
mytree.remove_node(_it_node);<br />
...<br />
<br />
~test_tree()<br />
{<br />
mytree.SetWalkDownRootPivot();<br />
delete mytree.SubTreeGetData();<br />
for(size_t i = 1; i < mytree.size(); i++)<br />
{<br />
mytree.SubTreeWalkDown();<br />
delete mytree.SubTreeGetData();<br />
}<br />
delete mytree;<br />
}<br />
<br />
tree.hpp<br />
...<br />
void remove_node(iterator& itr)<br />
{<br />
itr.m_Node->second->DeleteAllChildren();
delete itr.m_Node->second;
}<br />
...<br />
but test_tree destructor crashes.
I think, that node deletes not correctly.
Anton.
|
|
|
|
|
How to delete a leaf-node? for 'f'.
|
|
|
|
|
I've been looking at a similar problem myself recently (under Design Patterns, Composites and Visitors). I like the way you keep track of all nodes in the tree so that you can do fast iterations ignoring the structure of the tree. I just think it is a bit of a shame that you 2 tree-walking methods do not also use STL-like iterators. I have tried to move a step closer to this with my article and I implement a tree-walking STL iterator and a shallow STL iterator that iterates over the nodes at one level. However, I didn't implement different walk strategies for the deep iterator, nor did I implement a fast iterator. One quite neat thing in my system though was that the tree is also the node and vice versa. To iterate over a sub-tree you simply call begin from a different node.
My solution to the different walk strategies was to provide mix-ins to a separate visitor class hierarchy. This used the shallow iterators to walk the tree in different orders - but I don't think that solution is necessarily ideal. I think the perfect STL Compliant Composite Tree is out there somewhere - I'm just not sure that either of us have it yet!
Nice work anyway.
Dave_H
|
|
|
|
|
Thanks ... Actually, the one I posted here is not the final version, but nearly the same. I'm lazy to update this article.
It's failing to compiling in VS.net 2003, and I'll fix it and post it here again.
Jack Hui
|
|
|
|
|
Jack,
I suspect your compilation problem in VS.Net 2003 is to do with a breaking change between .Net 2002 and .Net 2003. In order to make the compiler standards compliant, MS had to make this particular change. Basically, any templatised type that uses the scope resolution operator has to be prefixed with the keyword typename . In the version on the site this means 2 lines have to be amended:
typename vector<TreeNode<Key,T> *>::iterator m_current;
typedef typename map<Key, TreeNode<Key,T>*>::iterator _map_it;
I'm pretty sure that the reason for this is to mean that the compiler does not have to pre-compile sections of the template prior to it actually being used.
Dave H
|
|
|
|
|
I am interested in solutions for this as well.
Have you seen
www.damtp.cam.ac.uk/user/kp229/tree/tree.hh ?
|
|
|
|
|
I've just spent a little while browsing that solution. It looks quite good, but I think there are a few weaknesses:
1) It's a container, not a composite, the same as Jack Hui's solution. The only problem with this is if the classes being put into the tree need to know about their location. This is often the case with many trees such as expression trees or similar. It doesn't mean the container isn't valid, but it does provide a different perspective. Have a look at my article at Composites and Visitors.
2) It is protected under the GPL, which because of its viral nature pretty much precludes it from being used in any of my commercial work. I do wish that people would put library code under the LGPL, because on a large number of occasions, I have had to ignore a library because it is GPL'd.
Dave
|
|
|
|
|
\tree.h(338): error C2146: syntax error : missing ';' before identifier '_map_it'
\tree.h(338): error C2146: syntax error : missing ';' before identifier '_map_it'
tree.h(338): error C2146: syntax error : missing ';' before identifier '_map_it'
tree.h(338): error C2146: syntax error : missing ';' before identifier '_map_it'
tree.h(36): error C2146: syntax error : missing ';' before identifier 'm_current'
tree.h(36): error C2146: syntax error : missing ';' before identifier 'm_current'
tree.h(36): error C2146: syntax error : missing ';' before identifier 'm_current'
tree.h(36): error C2146: syntax error : missing ';' before identifier 'm_current'
tree.h(341): error C2146: syntax error : missing ';' before identifier 'm_Node'
tree.h(341): error C2146: syntax error : missing ';' before identifier 'm_Node'
tree.h(341): error C2146: syntax error : missing ';' before identifier 'm_Node'
tree.h(341): error C2146: syntax error : missing ';' before identifier 'm_Node'
tree.h(338): error C2501: 'Tiffany::Tree_iterator<key,t>::_map_it' : missing storage-class or type specifiers
tree.h(341): error C2501: 'Tiffany::Tree_iterator<key,t>::_map_it' : missing storage-class or type specifiers
tree.h(338): error C2501: 'Tiffany::Tree_iterator<key,t>::_map_it' : missing storage-class or type specifiers
tree.h(341): error C2501: 'Tiffany::Tree_iterator<key,t>::_map_it' : missing storage-class or type specifiers
tree.h(338): error C2501: 'Tiffany::Tree_iterator<key,t>::_map_it' : missing storage-class or type specifiers
tree.h(341): error C2501: 'Tiffany::Tree_iterator<key,t>::_map_it' : missing storage-class or type specifiers
tree.h(338): error C2501: 'Tiffany::Tree_iterator<key,t>::_map_it' : missing storage-class or type specifiers
tree.h(341): error C2501: 'Tiffany::Tree_iterator<key,t>::_map_it' : missing storage-class or type specifiers
tree.h(341): error C2501: 'Tiffany::Tree_iterator<key,t>::m_Node' : missing storage-class or type specifiers
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Lad
|
|
|
|
|
Hi,
The typename keyword is required if a dependent name is to be treated as a type. This is a breaking change in the Visual C++ .NET 2003 compiler, made in order to conform to the ISO C++ standard.
In the class "TreeNode", define a new type for iterator to current child. Remember to include "typename":
template <class Key, class T> class TreeNode
{
typedef typename vector<TreeNode<Key,T> *>::iterator _point_it;
...
_point_it m_current; //holds iterator to current child processing
...
In the class "Tree_iterator", simply add "typename" in "_map_it" type definition:
template <class Key, class T>
class Tree_iterator
{
typedef typename map<Key, TreeNode<Key,T>*>::iterator _map_it;
...
|
|
|
|
|
I'm working on an unrelated project but happened to get this article in a google search. I just wanted to say thanks to the poster above for that valuable information. I have been banging my head for 6 hours to get some old VC6 code to compile in Visual Studio 8. You saved me a sleepless night. Thanks!
(Who would've thought that Microsoft would actually write an ISO compliant compiler! There is a lot of broken code out there thanks to their crappy implementations in the past)
|
|
|
|
|
#ifndef _TREE_H_
#define _TREE_H_
/* Copyright - All copyright is owned by Mr Jack Hui
Author : Jack, Hui Ho Yin
Email : jackhui@hotmail.com, jackhui@hongkong.com
Update : 27-Aug-2000, 10-Aug-2002*/
#pragma warning(disable : 4786) //debug info - name too long
#include <vector>
#include
#include <string>
#include <iostream>
// Support TEMPLATE CLASS sorted_vector
#include <algorithm>
#include <utility>
#include <functional>
using namespace std;
namespace Tiffany {
//forward declarations
template <class key,="" class="" t=""> class TreeNode;
template <class key,="" class="" t=""> class Tree;
template <class key,="" class="" t=""> class Tree_iterator;
template<class k,="" bool="" bnoduplicates="false,class" pr="std::less<K">, class A = std::allocator<k> >
class sorted_vector ;
//
template <class key,="" class="" t=""> class TreeNode {
public:
T m_data; //things stored in treenode
Key m_key; //key to locate myself
int m_level; //rootnode is of level 1
TreeNode<key,t>* m_parent; //points to node of parent
sorted_vector<treenode<key,t> *> m_children; //holds pointers for children
sorted_vector<treenode<key,t> *>::iterator m_current; //holds iterator to current child processing
Tree<key, t="">* m_LinkedTree; //whom i'm belonging to
TreeNode(Tree<key,t>* tr) : m_parent(NULL) {
m_LinkedTree = tr;
};
TreeNode(Tree<key,t>* tr, const Key key, const T x) {
m_key = key;
m_data = x;
m_LinkedTree = tr;
};
//Delete all the children of this node including all the down levels
void DeleteAllChildren() {
vector<treenode<key,t>*>::iterator pchild;
map<key, treenode<key,t="">*>::iterator itrmap;
for(pchild=m_children.begin();pchild != m_children.end();)
{
(*pchild)->DeleteAllChildren();
itrmap = m_LinkedTree->m_nodemap.find((*pchild)->m_key);
m_LinkedTree->m_nodemap.erase(itrmap);
delete *pchild;
m_children.erase(pchild);
//after removing the node, iterater is advanced
}
};
//It erases a child from a Node without delete the node, and without remove
//linking from the tree, so it can still be accessed from the tree's find().
void EraseChild(Tree_iterator<key, t=""> &itr)
{
vector<treenode<key,t>*>::iterator pchild;
map<key, treenode<key,t="">*>::iterator itrmap;
TreeNode<key,t> *pNode = itr.m_Node->second;
itrmap = m_LinkedTree->m_nodemap.find(pNode->m_key);
//erase reference from the child vector
for(pchild=m_children.begin();pchild != m_children.end(); pchild++)
{
if( (*pchild)->m_key == pNode->m_key)
{
m_children.erase(pchild);
break;
}
}
}
//Return a reference to parent node in the tree
TreeNode<key,t>& GetParent () const {
return *m_parent;
};
//returns a reference to vector to the children
const sorted_vector<treenode<key,t>*>& GetChildren () const
{
return m_children;
};
long ChildCount () const
{
return m_children.size();
};
//add a child node to this node
void AddChild (TreeNode<key,t>* child)
{
child->m_parent = this;
child->m_level = this->m_level + 1;
m_children.insert(child);
};
T GetData(void) const { return m_data; }
};
//************ End of Tree Node declaration ***************************//
//
//************ Start of Tree declaration ***************************//
//
template <class key,="" class="" t="">
class Tree {
friend class TreeNode<key, t="">;
protected:
//provide a name of the TreeNode to direct access to it
map<key, treenode<key,t="">*> m_nodemap; //a map for fast accessing TreeNode
TreeNode<key,t>* m_pTreeroot; //a pointer to root node
TreeNode<key,t>* m_WalkPivot; //Sub-tree root for walking
TreeNode<key,t>* m_WalkCurrent; //point to current node of walking
TreeNode<key,t>* m_WalkParent; //point to parent node of current node
public:
typedef Tree_iterator<key, t=""> iterator;
typedef const iterator const_iterator;
iterator begin() {
iterator _tmp;
_tmp.m_Node = m_nodemap.begin();
return _tmp;
}
iterator end() {
iterator _tmp;
_tmp.m_Node = m_nodemap.end();
return _tmp;
}
const_iterator begin() const {
iterator _tmp;
_tmp.m_Node = m_nodemap.begin();
return _tmp;
}
const_iterator end() const {
const_iterator _tmp;
_tmp.m_Node = m_nodemap.end();
return _tmp;
}
iterator find(const Key& key) {
iterator _tmp;
_tmp.m_Node = m_nodemap.find(key);
return _tmp;
}
const_iterator find(const Key& key) const {
const_iterator _tmp;
_tmp.m_Node = m_nodemap.find(key);
return _tmp;
}
Tree () : m_pTreeroot(NULL) {
//instantiate an empty tree
}
Tree (const Key nm, const T x) {
//instantiate a tree with the root node
TreeNode<key,t>* pNode;
pNode = new TreeNode<key,t>(this, nm, x);
m_nodemap.insert(map<key, treenode<key,t="">*>::value_type(nm, pNode));
m_pTreeroot = pNode;
pNode->m_level = 1;
}
~Tree() {
if (m_pTreeroot) {
m_pTreeroot->DeleteAllChildren();
delete m_pTreeroot;
}
}
//returns tree root node, or NULL for empty tree
TreeNode<key,t>& GetRoot () const {
return *m_pTreeroot;
}
iterator AddChild (iterator& parent, const Key nm, const T x) {
TreeNode<key,t>* pNew;
pNew = new TreeNode<key,t>(this, nm, x);
parent.m_Node->second->AddChild(pNew);
pair<map<key, treenode<key,t="">*>::iterator, bool> pt = m_nodemap.insert(map<key, treenode<key,t="">*>::value_type(nm, pNew));
iterator _tmp;
_tmp.m_Node = pt.first;
return _tmp;
}
//
iterator AddChild (const Key nm, const T x) {
TreeNode<key,t>* pNew;
pNew = new TreeNode<key,t>(this, nm, x);
m_pTreeroot->AddChild(pNew);
pair<map<key, treenode<key,t="">*>::iterator, bool> pt = m_nodemap.insert(map<key, treenode<key,t="">*>::value_type(nm, pNew));
iterator _tmp;
_tmp.m_Node = pt.first;
return _tmp;
}
//--- add by mry 2004
iterator AddChild (const Key parent, const Key nm, const T x) {
iterator px,_tmp;
px = find(parent);
if ( px != end())
_tmp = AddChild (px, nm, x);
return _tmp;
}
TreeNode<key,t>& SetRoot (const Key nm, const T x) {
TreeNode<key,t>* pNode;
//Èç¹ûÒѾÓÐÁ˸ù½Úµã£¬É¾³ýËùÓÐ
if (m_pTreeroot) {
m_pTreeroot->DeleteAllChildren();
delete m_pTreeroot;
}
//È»ºó´´½¨¸ù½Úµã
pNode = new TreeNode<key,t>(this, nm, x);
m_nodemap.insert(map<key, treenode<key,t="">*>::value_type(nm, pNode));
m_pTreeroot = pNode;
pNode->m_level = 1;
//·µ»Ø¸ù½Úµã
return GetRoot();
}
//end of add
void DeleteAllChildren(iterator & itr) {
itr.m_Node->second->DeleteAllChildren();
}
size_t size(void) { return m_nodemap.size(); }
//Set the sub-tree walking root and traverse to the first node
void SetPostOrderSubTreePivot(iterator& it) {
m_WalkPivot = it.m_Node->second;
m_WalkCurrent = m_WalkPivot;
m_WalkCurrent->m_current = m_WalkCurrent->m_children.begin();
while (m_WalkCurrent->m_children.size() != 0) {
m_WalkCurrent->m_current = m_WalkCurrent->m_children.begin();
m_WalkCurrent = *(m_WalkCurrent->m_children.begin());
}
if (m_WalkCurrent != m_WalkPivot) {
m_WalkParent = m_WalkCurrent->m_parent;
}
else {
m_WalkParent = m_WalkCurrent; //for the case no child in pivot
}
}
//Set the sub-tree walking root and traverse to the first node
void SetPostOrderRootPivot() {
m_WalkPivot = m_pTreeroot;
m_WalkCurrent = m_WalkPivot;
m_WalkCurrent->m_current = m_WalkCurrent->m_children.begin();
while (m_WalkCurrent->m_children.size() != 0) {
m_WalkCurrent->m_current = m_WalkCurrent->m_children.begin();
m_WalkCurrent = *(m_WalkCurrent->m_children.begin());
}
if (m_WalkCurrent != m_WalkPivot) {
m_WalkParent = m_WalkCurrent->m_parent;
}
else {
m_WalkParent = m_WalkCurrent; //for the case no child in pivot
}
}
//It sets root to be the pivot in Walk Down, first node is the first child
void SetWalkDownSubTreePivot(iterator& itr)
{
m_WalkPivot = itr.m_Node->second;
m_WalkCurrent = m_WalkPivot;
m_WalkCurrent->m_current = m_WalkCurrent->m_children.begin();
}
//It sets root to be the pivot in Walk Down, first node is the first child
void SetWalkDownRootPivot() {
m_WalkPivot = m_pTreeroot;
m_WalkCurrent = m_WalkPivot;
m_WalkCurrent->m_current = m_WalkCurrent->m_children.begin();
}
//it advances m_WalkCurrent in post-order, and returns true if a move is made
//else it returns false
bool SubTreePostOrderWalk() {
if (m_WalkCurrent == m_WalkPivot)
return false;
//if not the parent's last child, advance one node in paraent's child
//if the advanced child contains sub node, go in depth to the leftmost one
if (++m_WalkParent->m_current != m_WalkParent->m_children.end()) {
m_WalkCurrent = *(m_WalkParent->m_current);
while (m_WalkCurrent->m_children.size() != 0) {
//go down
m_WalkCurrent->m_current = m_WalkCurrent->m_children.begin();
m_WalkParent = m_WalkCurrent;
m_WalkCurrent = *(m_WalkCurrent->m_current);
}
}
else {
//if it's the last child of parent, we go up
m_WalkCurrent = m_WalkParent;
m_WalkParent = m_WalkCurrent->m_parent;
}
m_WalkParent = m_WalkCurrent->m_parent;
return true;
}
//It advance the tree in top-down style with parent first
bool SubTreeWalkDown() {
//if it has children, we go down to children
if (m_WalkCurrent->m_current != m_WalkCurrent->m_children.end()) {
m_WalkCurrent = *(m_WalkCurrent->m_current);
m_WalkParent = m_WalkCurrent->m_parent;
m_WalkParent->m_current++; //advance to next child for next iteration
m_WalkCurrent->m_current = m_WalkCurrent->m_children.begin(); //initialize to first child
}
else {
//if it's the last child of parent, we go up to the level
//which we still need processing by recurively call ourself
if (m_WalkCurrent == m_WalkPivot)
return false; //no more child
m_WalkCurrent = m_WalkCurrent->m_parent;
m_WalkParent = m_WalkCurrent->m_parent;
SubTreeWalkDown();
}
return true;
}
void DelSubTree() {
}
//It moves a tree from source to destination. After moving a tree, tree walking will be invalid.
//However iterator will still be valid. Users has to Set the new root pivot again.
void MoveSubTree(iterator& dest_parent, iterator& src)
{
TreeNode<key,t>* pSrcNode;
TreeNode<key,t>* pDestNode;
TreeNode<key,t>* pSrcNodeParent;
pSrcNode = src.m_Node->second;
pSrcNodeParent = pSrcNode->m_parent;
//remove reference from original parent
pSrcNodeParent->EraseChild(src);
//add the src sub tree to destination parent node
pDestNode = dest_parent.m_Node->second;
pDestNode->AddChild(pSrcNode);
iterator itr;
itr = find(pSrcNode->m_key);
//setting up correct level
SetWalkDownSubTreePivot(itr);
while (SubTreeWalkDown())
{
m_WalkCurrent->m_level = m_WalkCurrent->m_parent->m_level + 1;
}
}
T SubTreeGetData(void) { return m_WalkCurrent->m_data; }
T SubTreeGetLevel(void) { return m_WalkCurrent->m_level; }
}; //class Tree
//************ End of Tree declaration ***************************//
//
//Actually, the interator is just a copy of the iterator to a std::map hold in
//the tree to provide simple navigation ability.
template <class key,="" class="" t="">
class Tree_iterator
{
typedef map<key, treenode<key,t="">*>::iterator _map_it;
public:
_map_it m_Node;
T operator*() const { return (m_Node->second)->GetData(); }
Tree_iterator& operator++() {
m_Node++;
return *this;
}
Tree_iterator operator++(int) {
Tree_iterator __tmp = *this;
m_Node++;
return __tmp;
}
Tree_iterator& operator--() {
m_Node--;
return *this;
}
bool operator==(const Tree_iterator& _y) const {
return m_Node == _y.m_Node;
}
bool operator!=(const Tree_iterator& _y) const {
return m_Node != _y.m_Node;
}
}; //class Tree_iterator
// TEMPLATE CLASS sorted_vector
template<class k,="" bool="" bnoduplicates="false,class" pr="std::less<K">, class A = std::allocator<k> >
class sorted_vector
{
public:
typedef sorted_vector<k,bnoduplicates,pr,a> Myt_;
typedef std::vector<k,a> Cont;
typedef Cont::allocator_type allocator_type;
typedef Cont::size_type size_type;
typedef Cont::difference_type difference_type;
typedef Cont::reference reference;
typedef Cont::const_reference const_reference;
typedef Cont::value_type value_type;
typedef K key_type;
typedef Cont::iterator iterator;
typedef Cont::const_iterator const_iterator;
typedef Pr key_compare;
typedef Pr value_compare;
typedef Cont::const_reverse_iterator
const_reverse_iterator;
typedef Cont::reverse_iterator reverse_iterator;
typedef std::pair<iterator, iterator=""> Pairii_;
typedef std::pair<const_iterator, const_iterator=""> Paircc_;
typedef std::pair<iterator, bool=""> Pairib_;
explicit sorted_vector(const Pr& pred = Pr(),const A& al = A())
:key_compare_(pred),vec_(al){}
#if (_MSC_VER >= 1300)
template<class it="">
sorted_vector(It first, It beyond,
const Pr& pred = Pr(),const A& al = A())
:key_compare_(pred),vec_(first,beyond,al)
{stable_sort();}
#else
sorted_vector(const_iterator first, const_iterator beyond,
const Pr& pred = Pr(),const A& al = A())
:key_compare_(pred),vec_(first,beyond,al)
{stable_sort();}
#endif
sorted_vector(const Myt_& x)
: vec_(x.vec_),key_compare_(x.key_compare_)
{}
~sorted_vector() {}
Myt_& operator=(const Myt_& x) {vec_.operator=(x.vec_);
key_compare_= x.key_compare_;
return *this;}
Myt_& operator=(const Cont& x){vec_.operator=(x);
sort();return *this;}
void reserve(size_type n) {vec_.reserve(n);}
iterator begin() {return vec_.begin(); }
const_iterator begin() const {return vec_.begin(); }
iterator end() {return vec_.end();}
const_iterator end() const {return vec_.end();}
reverse_iterator rbegin() {return vec_.rbegin();}
const_reverse_iterator rbegin() const
{return vec_.rbegin();}
reverse_iterator rend() {return vec_.rend();}
const_reverse_iterator rend() const
{return vec_.rend();}
size_type size() const {return vec_.size();}
size_type max_size() const {return vec_.max_size();}
bool empty() const {return vec_.empty();}
A get_allocator() const {return vec_.get_allocator();}
const_reference at(size_type p) const {return vec_.at(p);}
reference at(size_type p) {return vec_.at(p);}
const_reference operator[](size_type p) const
{return vec_.operator[](p);}
reference operator[](size_type p) {return vec_.operator[](p);}
reference front() {return vec_.front();}
const_reference front() const {return vec_.front();}
reference back() {return vec_.back();}
const_reference back() const {return vec_.back();}
void pop_back() {vec_.pop_back();}
void assign(const_iterator first, const_iterator beyond)
{vec_.assign(first,beyond);}
void assign(size_type n, const K& x = K())
{vec_.assign(n,x);}
/*insert members*/
Pairib_ insert(const value_type& x)
{
if(bNoDuplicates){
iterator p= lower_bound(x);
if(p==end()||key_compare_(x,*p)){
return Pairib_(InsertImpl_(p,x),true);
}else{
return Pairib_(p,false);
}
}else{
iterator p= upper_bound(x);
return Pairib_(InsertImpl_(p,x),true);
}
}
iterator insert(iterator it, const value_type& x)//it is the hint
{
if(it!=end() ){
if(bNoDuplicates){
if(key_compare_(*it,x)){
if((it+1)==end()||KeyCompare_Gt_(*(it+1),x)){//use hint
return InsertImpl_(it+1,x);
}else if(KeyCompare_Geq_(*(it+1),x)){
return end();
}
}
}else{
if( KeyCompare_Leq_(*it,x)
&&((it+1)==end()||KeyCompare_Geq_(*(it+1),x))){
return InsertImpl_(it+1,x);
}
}
}
return insert(x).first;
}
#if (_MSC_VER >= 1300)
template<class it="">
void insert(It first, It beyond)
{
size_type n= std::distance(first,beyond);
reserve(size()+n);
for( ;first!=beyond;++first){
insert(*first);
}
}
#else
void insert(const_iterator first, const_iterator beyond)
{
size_type n= std::distance(first,beyond);
reserve(size()+n);
for( ;first!=beyond;++first){
insert(*first);
}
}
#endif
iterator erase(iterator p) {return vec_.erase(p);}
iterator erase(iterator first, iterator beyond)
{return vec_.erase(first,beyond);}
size_type erase(const K& key)
{
Pairii_ begEnd= equal_range(key);
size_type n= std::distance(begEnd.first,begEnd.second);
erase(begEnd.first,begEnd.second);
return n;
}
void clear() {return vec_.clear();}
bool Eq_(const Myt_& x) const
{return (size() == x.size()
&& std::equal(begin(), end(), x.begin())); }
bool Lt_(const Myt_& x) const
{return (std::lexicographical_compare(begin(), end(),
x.begin(), x.end()));}
void swap(Myt_& x)
{vec_.swap(x.vec_);std::swap(key_compare_,x.key_compare_);}
friend void swap(Myt_& x, Myt_& Y_)
{x.swap(Y_); }
key_compare key_comp() const {return key_compare_; }
value_compare value_comp() const {return (key_comp()); }
iterator find(const K& k)
{ iterator p = lower_bound(k);
return (p==end()||key_compare_(k, *p))? end():p;
}
const_iterator find(const K& k) const
{const_iterator p = lower_bound(k);
return (p==end()||key_compare_(k,*p))?end():p;}
size_type count(const K& k) const
{Paircc_ Ans_ = equal_range(k);
size_type n = std::distance(Ans_.first, Ans_.second);
return (n); }
iterator lower_bound(const K& k)
{return std::lower_bound(begin(), end(), k, key_compare_); }
const_iterator lower_bound(const K& k) const
{return std::lower_bound(begin(), end(), k, key_compare_); }
iterator upper_bound(const K& k)
{return std::upper_bound(begin(), end(), k, key_compare_); }
const_iterator upper_bound(const K& k) const
{return std::upper_bound(begin(), end(), k, key_compare_); }
Pairii_ equal_range(const K& k)
{return std::equal_range(begin(), end(), k, key_compare_); }
Paircc_ equal_range(const K& k) const
{return std::equal_range(begin(), end(), k, key_compare_); }
/*functions for use with direct std::vector-access*/
Cont& get_container()
{return vec_;}
void sort()//restore sorted order after low level access
{ std::sort(vec_.begin(),vec_.end(),key_compare_);
if( bNoDuplicates ){
vec_.erase(Unique_(),vec_.end());
}
}
void stable_sort()//restore sorted order after low level access
{ std::stable_sort(vec_.begin(),vec_.end(),key_compare_);
if( bNoDuplicates ){
erase(Unique_(),end());
}
}
protected:
iterator Unique_()
{ iterator front_= vec_.begin(),out_= vec_.end(),end_=vec_.end();
bool bCopy_= false;
for(iterator prev_; (prev_=front_)!=end_ && ++front_!=end_; ){
if( key_compare_(*prev_,*front_)){
if(bCopy_){
*out_= *front_;
out_++;
}
}else{
if(!bCopy_){out_=front_;bCopy_=true;}
}
}
return out_;
}
iterator InsertImpl_(iterator p,const value_type& x)
{return vec_.insert(p,x);}
bool KeyCompare_Leq_(const K& ty0,const K& ty1)
{return !key_compare_(ty1,ty0);}
bool KeyCompare_Geq_(const K& ty0,const K& ty1)
{return !key_compare_(ty0,ty1);}
bool KeyCompare_Gt_(const K& ty0,const K& ty1)
{return key_compare_(ty1,ty0);}
key_compare key_compare_;
Cont vec_;
};//class sorted_vector
template<class k,bool="" bnoduplicates,class="" pr,="" class="" a=""> inline
bool operator==(const sorted_vector<k, bnoduplicates,pr,a="">& x,
const sorted_vector<k, bnoduplicates,pr,a="">& Y_)
{return x.Eq_(Y_); }
template<class k,bool="" bnoduplicates,class="" pr,="" class="" a=""> inline
bool operator!=(const sorted_vector<k, bnoduplicates,pr,a="">& x,
const sorted_vector<k, bnoduplicates,pr,a="">& Y_)
{return !(x == Y_); }
template<class k,bool="" bnoduplicates,class="" pr,="" class="" a=""> inline
bool operator<(const sorted_vector<k, bnoduplicates,pr,a="">& x,
const sorted_vector<k, bnoduplicates,pr,a="">& Y_)
{return x.Lt_(Y_);}
template<class k,bool="" bnoduplicates,class="" pr,class="" a=""> inline
bool operator>(const sorted_vector<k, bnoduplicates,pr,a="">& x,
const sorted_vector<k, bnoduplicates,pr,a="">& Y_)
{return Y_ < x; }
template<class k,bool="" bnoduplicates,class="" pr,="" class="" a=""> inline
bool operator<=(const sorted_vector<k, bnoduplicates,pr,a="">& x,
const sorted_vector<k, bnoduplicates,pr,a="">& Y_)
{return !(Y_ < x); }
template<class k,="" bool="" bnoduplicates,class="" pr,class="" a=""> inline
bool operator>=(const sorted_vector<k, bnoduplicates,pr,a="">& x,
const sorted_vector<k, bnoduplicates,pr,a="">& Y_)
{return (!(x < Y_)); }
}; //namespace Tiffany
#endif //_TREE_H_
|
|
|
|
|
{
//Post Order Walk Test
Tiffany::Tree<wstring, string=""> x(L"Node 1", "Root");
Tiffany::Tree<wstring, string="">::iterator px;
Tiffany::Tree<wstring, string="">::iterator px1;
Tiffany::Tree<wstring, string="">::iterator px2;
px = x.AddChild(L"Key1","A");
px1 = x.AddChild(px, L"Key2", "1");
x.AddChild(px1, L"Key3", "a");
px2 = x.AddChild(px1, L"Key4", "b");
x.AddChild(px2, L"Key5", "I");
x.AddChild(px2, L"Key6", "II");
x.AddChild(px1, L"Key7", "c");
px1 = x.AddChild(px, L"Key8", "2");
x.AddChild(px1, L"Key9", "d");
px = x.AddChild(L"Key10","B");
px1 = x.AddChild(px, L"Key11","3");
x.AddChild(px1, L"Key12", "e");
x.AddChild(px1, L"Key13", "f");
px = x.AddChild(L"Key14", "C");
px1 = x.AddChild(px, L"Key15", "4");
x.AddChild(px1, L"Key16", "g");
px = x.begin();
for ( px = x.begin( ) ; px != x.end( ) ; px++ )
{
cout << *px << endl;
}
//mry test
px = x.find(L"Key100");
if (px == x.end())
cout << "Not find to Key100" << endl;
else
{
cout << "The element of Tree m1 with a key of Key100 is: "
<< *px << endl;
px1 = x.AddChild(px, L"Key111","3");
}
px = x.AddChild(L"Key12",L"Key141", "soleman");
if (px == x.end())
cout << "Not find to Key100" << endl;
for ( px = x.begin( ) ; px != x.end( ) ; px++ )
{
cout << *px << endl;
}
//end mry test
x.SetPostOrderRootPivot();
// x.SetSubTreePivot(px);
cout << "Data is: " << x.SubTreeGetData().c_str() << endl;
for (int i=1; i<18; i++) {
x.SubTreePostOrderWalk();
cout << "Data is: " << x.SubTreeGetData().c_str() << endl;
}
// x.PostOrderWalk();
//move from subtree [b] to under [g]
px1 = x.find(L"Key4");
px2 = x.find(L"Key16");
x.MoveSubTree(px2, px1);
x.SetWalkDownRootPivot();
cout << "After moving tree" << endl;
cout << "Data is: " << x.SubTreeGetData().c_str() << endl;
for (int j=1; j<18; j++) {
x.SubTreeWalkDown();
cout << "Data is: " << x.SubTreeGetData().c_str() << endl;
}
}
|
|
|
|
|
Is it possible(and how) to convert this to managed C++ because I'd like to make a .NET assembly?
Best regards
|
|
|
|
|
I could try to convert this to C# but my knowledges of C++ don't go this far
|
|
|
|
|
sorry, it doesn't have a C# version. For C#, you can use two Hashtable tables to do the same things.
For creating a tree structure in C#. It's quite easy.
You can create the tree nodes which contains a collection of tree nodes.
Hiya, Everybody ^^
|
|
|
|
|
How can I move subtree [b] to [g]? (in your figure)
Could you tell me the way to do it?
|
|
|
|
|
Okay, I've added a new MoveSubTree function.
You can use it as:
px1 = x.find(L"Key4");
px2 = x.find(L"Key16");
x.MoveSubTree(px2, px1);
x.SetWalkDownRootPivot();
cout << "After moving tree" << endl;
cout << "Data is: " << x.SubTreeGetData().c_str() << endl;
for (int i=1; i<17; i++) {
x.SubTreeWalkDown();
cout << "Data is: " << x.SubTreeGetData().c_str() << endl;
The new CPP file is here.
#ifndef _TREE_H_
#define _TREE_H_
#pragma warning(disable : 4786) //debug info - name too long
#include <vector>
#include <map>
#include <string>
#include <iostream>
using namespace std;
namespace Tiffany {
template <class Key, class T> class TreeNode;
template <class Key, class T> class Tree;
template <class Key, class T> class Tree_iterator;
template <class Key, class T> class TreeNode
{
friend class Tree<Key, T>;
protected:
T m_data;
Key m_key;
int m_level;
TreeNode<Key,T>* m_parent;
vector<TreeNode<Key,T> *> m_children;
vector<TreeNode<Key,T> *>::iterator m_current;
Tree<Key, T>* m_LinkedTree;
public:
TreeNode(Tree<Key,T>* tr) : m_parent(NULL) {
m_LinkedTree = tr;
};
TreeNode(Tree<Key,T>* tr, const Key key, const T x) {
m_key = key;
m_data = x;
m_LinkedTree = tr;
};
void DeleteAllChildren() {
vector<TreeNode<Key,T>*>::iterator pchild;
map<Key, TreeNode<Key,T>*>::iterator itrmap;
for(pchild=m_children.begin();pchild != m_children.end();)
{
(*pchild)->DeleteAllChildren();
itrmap = m_LinkedTree->m_nodemap.find((*pchild)->m_key);
m_LinkedTree->m_nodemap.erase(itrmap);
delete *pchild;
m_children.erase(pchild);
}
};
void EraseChild(Tree_iterator<Key, T> &itr)
{
vector<TreeNode<Key,T>*>::iterator pchild;
map<Key, TreeNode<Key,T>*>::iterator itrmap;
TreeNode<Key,T> *pNode = itr.m_Node->second;
itrmap = m_LinkedTree->m_nodemap.find(pNode->m_key);
for(pchild=m_children.begin();pchild != m_children.end(); pchild++)
{
if( (*pchild)->m_key == pNode->m_key)
{
m_children.erase(pchild);
break;
}
}
}
TreeNode<Key,T>& GetParent () const {
return *m_parent;
};
const vector<TreeNode<Key,T>*>& GetChildren () const
{
return m_children;
};
long ChildCount () const
{
return m_children.size();
};
void AddChild (TreeNode<Key,T>* child)
{
child->m_parent = this;
child->m_level = this->m_level + 1;
m_children.push_back(child);
};
T GetData(void) const { return m_data; }
};
template <class Key, class T>
class Tree {
friend class TreeNode<Key, T>;
protected:
map<Key, TreeNode<Key,T>*> m_nodemap;
TreeNode<Key,T>* m_pTreeroot;
TreeNode<Key,T>* m_WalkPivot;
TreeNode<Key,T>* m_WalkCurrent;
TreeNode<Key,T>* m_WalkParent;
public:
typedef Tree_iterator<Key, T> iterator;
typedef const iterator const_iterator;
iterator begin() {
iterator _tmp;
_tmp.m_Node = m_nodemap.begin();
return _tmp;
}
iterator end() {
iterator _tmp;
_tmp.m_Node = m_nodemap.end();
return _tmp;
}
const_iterator begin() const {
iterator _tmp;
_tmp.m_Node = m_nodemap.begin();
return _tmp;
}
const_iterator end() const {
const_iterator _tmp;
_tmp.m_Node = m_nodemap.end();
return _tmp;
}
iterator find(const Key& key) {
iterator _tmp;
_tmp.m_Node = m_nodemap.find(key);
return _tmp;
}
const_iterator find(const Key& key) const {
const_iterator _tmp;
_tmp.m_Node = m_nodemap.find(key);
return _tmp;
}
Tree () : m_pTreeroot(NULL) {
}
Tree (const Key nm, const T x) {
TreeNode<Key,T>* pNode;
pNode = new TreeNode<Key,T>(this, nm, x);
m_nodemap.insert(map<Key, TreeNode<Key,T>*>::value_type(nm, pNode));
m_pTreeroot = pNode;
pNode->m_level = 1;
}
~Tree() {
if (m_pTreeroot) {
m_pTreeroot->DeleteAllChildren();
delete m_pTreeroot;
}
}
TreeNode<Key,T>& GetRoot () const {
return *m_pTreeroot;
}
iterator AddChild (iterator& parent, const Key nm, const T x) {
TreeNode<Key,T>* pNew;
pNew = new TreeNode<Key,T>(this, nm, x);
parent.m_Node->second->AddChild(pNew);
pair<map<Key, TreeNode<Key,T>*>::iterator, bool> pt = m_nodemap.insert(map<Key, TreeNode<Key,T>*>::value_type(nm, pNew));
iterator _tmp;
_tmp.m_Node = pt.first;
return _tmp;
}
iterator AddChild (const Key nm, const T x) {
TreeNode<Key,T>* pNew;
pNew = new TreeNode<Key,T>(this, nm, x);
m_pTreeroot->AddChild(pNew);
pair<map<Key, TreeNode<Key,T>*>::iterator, bool> pt = m_nodemap.insert(map<Key, TreeNode<Key,T>*>::value_type(nm, pNew));
iterator _tmp;
_tmp.m_Node = pt.first;
return _tmp;
}
void DeleteAllChildren(iterator & itr) {
itr.m_Node->second->DeleteAllChildren();
}
size_t size(void) { return m_nodemap.size(); }
void SetPostOrderSubTreePivot(iterator& it) {
m_WalkPivot = it.m_Node->second;
m_WalkCurrent = m_WalkPivot;
m_WalkCurrent->m_current = m_WalkCurrent->m_children.begin();
while (m_WalkCurrent->m_children.size() != 0) {
m_WalkCurrent->m_current = m_WalkCurrent->m_children.begin();
m_WalkCurrent = *(m_WalkCurrent->m_children.begin());
}
if (m_WalkCurrent != m_WalkPivot) {
m_WalkParent = m_WalkCurrent->m_parent;
}
else {
m_WalkParent = m_WalkCurrent;
}
}
void SetPostOrderRootPivot() {
m_WalkPivot = m_pTreeroot;
m_WalkCurrent = m_WalkPivot;
m_WalkCurrent->m_current = m_WalkCurrent->m_children.begin();
while (m_WalkCurrent->m_children.size() != 0) {
m_WalkCurrent->m_current = m_WalkCurrent->m_children.begin();
m_WalkCurrent = *(m_WalkCurrent->m_children.begin());
}
if (m_WalkCurrent != m_WalkPivot) {
m_WalkParent = m_WalkCurrent->m_parent;
}
else {
m_WalkParent = m_WalkCurrent;
}
}
void SetWalkDownSubTreePivot(iterator& itr) {
m_WalkPivot = itr.m_Node->second;
m_WalkCurrent = m_WalkPivot;
m_WalkCurrent->m_current = m_WalkCurrent->m_children.begin();
}
void SetWalkDownRootPivot() {
m_WalkPivot = m_pTreeroot;
m_WalkCurrent = m_WalkPivot;
m_WalkCurrent->m_current = m_WalkCurrent->m_children.begin();
}
bool SubTreePostOrderWalk() {
if (m_WalkCurrent == m_WalkPivot)
return false;
if (++m_WalkParent->m_current != m_WalkParent->m_children.end()) {
m_WalkCurrent = *(m_WalkParent->m_current);
while (m_WalkCurrent->m_children.size() != 0) {
m_WalkCurrent->m_current = m_WalkCurrent->m_children.begin();
m_WalkParent = m_WalkCurrent;
m_WalkCurrent = *(m_WalkCurrent->m_current);
}
}
else {
m_WalkCurrent = m_WalkParent;
m_WalkParent = m_WalkCurrent->m_parent;
}
m_WalkParent = m_WalkCurrent->m_parent;
return true;
}
bool SubTreeWalkDown() {
if (m_WalkCurrent->m_current != m_WalkCurrent->m_children.end()) {
m_WalkCurrent = *(m_WalkCurrent->m_current);
m_WalkParent = m_WalkCurrent->m_parent;
m_WalkParent->m_current++;
m_WalkCurrent->m_current = m_WalkCurrent->m_children.begin();
}
else {
if (m_WalkCurrent == m_WalkPivot)
return false;
m_WalkCurrent = m_WalkCurrent->m_parent;
m_WalkParent = m_WalkCurrent->m_parent;
SubTreeWalkDown();
}
return true;
}
void DelSubTree() {
}
void MoveSubTree(iterator& dest_parent, iterator& src)
{
TreeNode<Key,T>* pSrcNode;
TreeNode<Key,T>* pDestNode;
TreeNode<Key,T>* pSrcNodeParent;
pSrcNode = src.m_Node->second;
pSrcNodeParent = pSrcNode->m_parent;
pSrcNodeParent->EraseChild(src);
pDestNode = dest_parent.m_Node->second;
pDestNode->AddChild(pSrcNode);
iterator itr;
itr = find(pSrcNode->m_key);
SetWalkDownSubTreePivot(itr);
while (SubTreeWalkDown())
{
m_WalkCurrent->m_level = m_WalkCurrent->m_parent->m_level + 1;
}
}
T SubTreeGetData(void) { return m_WalkCurrent->m_data; }
T SubTreeGetLevel(void) { return m_WalkCurrent->m_level; }
};
template <class Key, class T>
class Tree_iterator
{
typedef map<Key, TreeNode<Key,T>*>::iterator _map_it;
public:
_map_it m_Node;
T operator*() const { return (m_Node->second)->GetData(); }
Tree_iterator& operator++() {
m_Node++;
return *this;
}
Tree_iterator operator++(int) {
Tree_iterator __tmp = *this;
m_Node++;
return __tmp;
}
Tree_iterator& operator--() {
m_Node--;
return *this;
}
bool operator==(const Tree_iterator& _y) const {
return m_Node == _y.m_Node;
}
bool operator!=(const Tree_iterator& _y) const {
return m_Node != _y.m_Node;
}
};
};
#endif //_TREE_H_
|
|
|
|
|
the new code you posted does not compile, any chance you could post a working version of this code.
TIA
|
|
|
|
|
Here's an algorithm to generalize binary trees:
Simply add a linked list(the nodes of which are tree-nodes) as one of the members of each node. On each traversal of a treenode,traverse the nodes of it's associated linked list. It's not hard to see that each node of a treenode's associated linked list, is a subtree the parent of which is the tree node.
|
|
|
|
|
I used map to do it, so we can do quick find of an element by the key.
Jack
|
|
|
|
|