//////////////////////////////////////////////////////////////////////
//
// class name:
// tree
// description:
// tree template used to express tree-liked data structure.
// For example, a list of directories name and relations can
// be stored in tree template.
// Here is a sample to enumerate each member in tree:
// for (tree<int>::iterator e = tre.begin(); e != tre.end(); ++e)
// {
// *e = 0;
// }
// The class tree<int>::iterator is a pointer which point to
// nodes in tree. It has GetParent(), GetFirstSub(), GetNextBrother()
// fucntions to visit its neighbors.
// author:
// sproll
// date:
// 07-02-09
//
//////////////////////////////////////////////////////////////////////
#pragma once
template <typename T>
class tree
{
public:
class iterator;
private:
class node;
public:
class iterator
{
public:
iterator() : m_pnode(NULL) {};
iterator(node* pnode) : m_pnode(pnode) {};
iterator(const iterator& copy) :
m_pnode(copy.m_pnode) {};
~iterator() {};
//check if point to a valid tree node
bool valid() {return m_pnode != NULL && m_pnode != 0xFFFFFFFF;};
//check if has parent node
bool HasParent() {return m_pnode->m_pParent != NULL;};
//get parent node
iterator GetParent() {return m_pnode->m_pParent;};
//check if has sub node
bool HasSub() {return m_pnode->m_pSub != NULL;};
//get first sub node
iterator GetFirstSub() {return m_pnode->m_pSub;};
//check if has brother node
bool HasBrother() {return m_pnode->m_pNext != NULL;};
//get next brother node
iterator GetNextBrother() {return m_pnode->m_pNext;};
bool operator==(const iterator& right) {return m_pnode == right.m_pnode;};
bool operator!=(const iterator& right) {return m_pnode != right.m_pnode;};
iterator& operator=(const iterator& right) {m_pnode = right.m_pnode; return *this;};
T& operator*() {return m_pnode->m_value;};
T* operator->() {return &(m_pnode->m_value);};
iterator& operator++()
{
if (m_pnode && (int)m_pnode != 0xFFFFFFFF ) //if pointer to valid node and not to the end
{
if (m_pnode->m_pSub)
{
m_pnode = m_pnode->m_pSub;
}
else if (m_pnode->m_pNext)
{
m_pnode = m_pnode->m_pNext;
}
else
{
node* pnode = m_pnode;
while (pnode->m_pParent)
{
if (pnode->m_pParent->m_pNext)
{
m_pnode = pnode->m_pParent->m_pNext;
goto LineOut;
}
else
{
pnode = pnode->m_pParent;
}
}
m_pnode = (node*)0xFFFFFFFF; //point to end
}
}
LineOut:
return *this;
};
iterator operator++(int) {iterator tmp = *this; ++(*this); return tmp;};
friend class tree<T>;
private:
node* m_pnode;
};
tree() : m_proot(NULL) {};
tree(const T value) : m_proot(new node) {m_proot->m_value = value;};
tree(iterator pnt) : m_proot(NULL) {m_proot = pnt.m_pnode->clone(NULL);};
tree(const tree<T>& copy) {copy.m_proot? m_proot = copy.m_proot->clone(NULL) : m_proot = NULL;};
~tree() {clear();};
tree<T>& operator=(const tree<T>& copy)
{
if (*this != copy)
{
clear();
copy.m_proot? m_proot = copy.m_proot->clone(NULL) : m_proot = NULL;
}
return *this;
};
bool operator==(const tree<T>& copy) {return m_proot == copy.m_proot;};
bool operator!=(const tree<T>& copy) {return m_proot != copy.m_proot;};
//get first node of tree (it's the root node)
iterator begin() {return m_proot? iterator(m_proot) : end();};
//get end of tree (it's not the same as the last node, it's invalid node)
iterator end() {return iterator((node*)0xFFFFFFFF);};
//clear the tree and release resource
void clear()
{
if (m_proot)
{
m_proot->del();
m_proot = NULL;
}
};
//check if empty
bool empty() {return m_proot == NULL;};
//get total number of nodes
int size()
{
int _size = 0;
for (iterator count = begin(); count != end(); ++count)
{
++_size;
}
return _size;
};
//swap two trees
void swap(tree<T>& other)
{
node* tmp = other.m_proot;
other.m_proot = m_proot;
m_proot = tmp;
};
//insert sub node to a tree of specified parent node, the sub node is added to the last of its parent
iterator insert(T& value, iterator where)
{
if (where == end())
{
m_proot = new node;
m_proot->m_value = value;
return m_proot;
}
else
{
return where.m_pnode->insert(value);
}
};
//erase node and its sub node
void erase(iterator where)
{
if (where != end())
{
where.m_pnode->del();
if (where == begin())
{
m_proot = NULL;
}
}
};
private:
struct node
{
public:
node() :
m_pParent(NULL),
m_pNext(NULL),
m_pSub(NULL),
m_value(T())
{};
node(const node& copy) :
m_pParent(copy.m_pParent),
m_pNext(copy.m_pNext),
m_pSub(copy.m_pSub),
m_value(copy.m_value)
{};
~node(){};
node& operator=(const node& right)
{
m_pParent = right.m_pParent;
m_pNext = right.m_pNext;
m_pSub = right.m_pSub;
m_value = right.m_value;
};
node* insert(T& value)
{
node* pnode = new node;
pnode->m_pParent = this;
pnode->m_value = value;
node* pbrother = m_pSub;
if (pbrother)
{
do
{
if (pbrother->m_pNext == NULL)
{
pbrother->m_pNext = pnode;
break;
}
else
{
pbrother = pbrother->m_pNext;
}
}while (true);
}
else
{
m_pSub = pnode;
}
return pnode;
};
void del()
{
if (m_pParent)
{
if (m_pParent->m_pSub == this)
{
m_pParent->m_pSub = m_pNext;
}
else
{
node* pnode = m_pParent->m_pSub;
do
{
if (pnode->m_pNext == this)
{
pnode->m_pNext = m_pNext;
break;
}
else
{
pnode = pnode->m_pNext;
}
}while (true);
}
}
while (m_pSub)
{
m_pSub->del();
}
delete this;
};
node* clone(node* pParent)
{
node* copy = new node;
copy->m_pParent = pParent;
if (m_pNext)
{
copy->m_pNext = m_pNext->clone(pParent);
}
if (m_pSub)
{
copy->m_pSub = m_pSub->clone(copy);
}
return copy;
};
node* m_pParent; //parent node
node* m_pNext; //next brother node
node* m_pSub; //sub node
T m_value; //node value
};
node* m_proot;
};