tree.h

CAN__组建现场总线系统设计技术(光盘)

/* 

   $Id: tree_msvc.hh,v 1.3 2002/05/28 11:53:25 t16 Exp $

	STL-like templated tree class.
	Copyright (C) 2001  Kasper Peeters <[e-mail]>

   Microsoft VC version by Jason Avinger, see 

      http://www.damtp.cam.ac.uk/user/kp229/tree/

   for the original.

	This program is free software; you can redistribute it and/or modify
	it under the terms of the GNU General Public License as published by
	the Free Software Foundation; version 2.
	
	This program is distributed in the hope that it will be useful,
	but WITHOUT ANY WARRANTY; without even the implied warranty of
	MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
	GNU General Public License for more details.
	
	You should have received a copy of the GNU General Public License
	along with this program; if not, write to the Free Software
	Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
	
*/
// it++ 没有定义。只定义了 ++it
#ifndef tree_hh_
#define tree_hh_

#include <cassert>
#include <memory>
#include <stdexcept>
#include <iterator>
#include <set>

#ifdef _MSC_VER // MSVC does not have HP style construct/destroy 

//p指向的T1型变量的值赋为val
template <class T1, class T2>
inline void constructor(T1* p, T2& val) 
{
	new ((void *) p) T1(val);
	/*
	 * new 作用
	 *  if(p) *p = T1(val);
	 */
}

template <class T1>
inline void constructor(T1* p) 
{
	new ((void *) p) T1;
}

template <class T1>
inline void destructor(T1* p)
{
	p->~T1();
}
#else
	#define constructor std::construct
	#define destructor  std::destroy
#endif

//节点
template<class T>
struct tree_node_ {
	tree_node_<T> *parent;//父节点
	tree_node_<T> *first_child, *last_child;//子节点
	tree_node_<T> *prev_sibling, *next_sibling;//兄弟节点
	T data;//数据
};

template <class T, class tree_node_allocator = std::allocator<tree_node_<T> > >
class tree
{
protected:
	typedef tree_node_<T> tree_node;
public:
	typedef T value_type;

	class iterator;
	class sibling_iterator;//两种iterator

	//******************* 构造和析构函数 ***********************
//structor & destructor
	tree(){
		head_initialise_();
	}
	~tree(){
		clear();
		alloc_.deallocate(head,1);
	}
	tree(const tree<T, tree_node_allocator>& other){
		head_initialise_();
		copy_(other);
	}
//
	void operator=(const tree<T, tree_node_allocator>& other){
		copy_(other);
	}
	//*********************************************************

	//--------------------------class iterator------------------------
	class iterator
	{ 
	public:
		typedef T                          value_type;
		typedef T*                         pointer;
		typedef T&                         reference;
		typedef size_t                     size_type;
		typedef ptrdiff_t                  difference_type;
		typedef std::bidirectional_iterator_tag iterator_category;

	//*********** 构造函数和析构函数 *************************************
		//不指向任何节点
		iterator(): node(0), skip_current_children_(false){
		}

		//node指向tn
		iterator(tree_node *tn): node(tn), skip_current_children_(false){
		}

		//指向other.node
		//如果node==0，则...
		iterator(const sibling_iterator& other):
			node(other.node), skip_current_children_(false){
			if(node==0) {//这种情况的发生是由于
				node=other.range_last();
				skip_children();
				increment_();
			}
		}

	//********** 位移操作 ************************************************
		//只要存在树，就不会出错，也就是说 this->node != 0
		//因此不要企图使用 it!=0 来作为遍历结束条件，一定要用 it!=end()
		iterator&  operator++(void){
			if(!increment_()) {//如果失败，node一定会是0的，不用再赋值了
				node=0;
			}
			return *this;
		}

		//向前
		iterator&  operator--(void){
			if(!decrement_()) {
				node=0;
			}
			return *this;
		}

		iterator&  operator+=(unsigned int num){
			while(num>0) {
				++(*this);
				--num;
			}
			return (*this);
		}

		iterator&  operator-=(unsigned int num){
			while(num>0) {
				--(*this);
				--num;
			}
			return (*this);
		}

		iterator   operator+(int num) const{
			iterator ret(*this);
			while(num>0) {
				++ret;
				--num;
			}
			return ret;
		}
	//********************* 获取数据 ***********************************
		//获取的是引用
		T&  operator*(void) const{
			return node->data;
		}

		//获取的是指针
		T*  operator->(void) const{
			return &(node->data);
		}

	//********************* 两个iterator关系 ***********************
		// 两个iterator是否指向相同的节点?
		bool  operator==(const iterator& other) const{
			if(other.node==node) return true;
			else return false;
		}

		// 两个iterator是否指向不同的节点？
		bool  operator!=(const iterator& other) const{
			if(other.node!=node) return true;
			else return false;
		}


		//返回子节点。如果不存在子节点，则ret.node == 0
		sibling_iterator begin() const{
			sibling_iterator ret(node->first_child);
			ret.parent_=node;
			return ret;
		}

		//构造一个不指向节点的iterator
		sibling_iterator end() const{
			sibling_iterator ret(0);
			ret.parent_=node;
			return ret;
		}

	//******************** 其他 ********************************
		// do not iterate over children of this node
		void skip_children(){
			skip_current_children_=true;
		}

		//iterator是否指向树节点？
		bool is_valid() const{
			if(node==0) return false;
			else return true;
		}

		//直接子节点的个数
		unsigned int number_of_children() const{
			tree_node *pos=node->first_child;
			if(pos==0) return 0;
			
			unsigned int ret=1;
			while(pos!=node->last_child) {
				++ret;
				pos=pos->next_sibling;
			}
			return ret;
		}

	//********************** 封装的数据 ********************
		tree_node *node;//指向树节点


	private:
		//如果有下一个节点，则返回true，并且node指向它
		//何时才返回false?只有当head==0
		//skip_current_children_作用：
		//  为false时，如果有子节点，则指向子节点;如果有兄弟节点，则为兄弟节点;否则回溯
		//  为true时，肯定不访问子节点
		// 有一个问题：
		//    设skip_current_children == false
		//              head<---->root1<---->root2<---->head
		//							/\
		//						   /  \
		//						  a    b
		//	  node当前值指向b，则执行后node指向root2
		//	  再执行一次将指向head!!!!
		//
		bool increment_(){//这个函数执行后,skip_current_children==false
			assert(node!=0);
			//如果不跳过子节点并且存在子节点，则指向第一个子节点
			if(!skip_current_children_ && node->first_child) {
				node=node->first_child;
				return true;
			}
			else{
				skip_current_children_=false;
				while(!node->next_sibling){//没有兄弟节点，回溯
					node=node->parent;
					if(node==0)
						return false;
				}
				node=node->next_sibling;//由于是pre-order，优先访问本节点，再访问子节点
				return true;
			}
		}

		bool decrement_(){
			assert(node!=0);
			//若是树根
			if(node->parent==0) {
				if(node->last_child==0)
					node=node->prev_sibling;
				while(node->last_child)
					node=node->last_child;
				if(!node) return false;
			}
			//不是树根
			else {
				//如果存在前趋
				if(node->prev_sibling) {
					if(node->prev_sibling->last_child) {
						node=node->prev_sibling->last_child;
					}
					else {
						node=node->prev_sibling;
					}
				}
				//不存在前趋
				else {
					node=node->parent;
					if(node==0)
						return false;
				}
			}
			return true;
		}

		bool skip_current_children_;
	};
	//---------------------end of class iterator------------------

	//--------------------sibling_iterator------------------------

	/******************
	*对于 sibling_iterator，node==0是正常的
	*
	******************/
	class sibling_iterator
	{
		friend class tree<T, tree_node_allocator>;
//		friend class tree<T, tree_node_allocator>::iterator;
	public:
		typedef T                          value_type;
		typedef T*                         pointer;
		typedef T&                         reference;
		typedef size_t                     size_type;
		typedef ptrdiff_t                  difference_type;
		typedef std::bidirectional_iterator_tag iterator_category;

	//************** 构造和析构函数 ******************************
		//不指向任何节点
		sibling_iterator(): node(0), parent_(0){
		}

		//指向 tn，并且设置parent_指向tn的父节点
		sibling_iterator(tree_node *tn): node(tn){
			set_parent_();
		}

		//将other的值拷贝过来
		sibling_iterator(const sibling_iterator& other):
			node(other.node), parent_(other.parent_){
		}

		sibling_iterator(const iterator& other): node(other.node){
			set_parent_();
		}

	//************** 位移操作 ************************************
		//如果已到最后一个兄弟节点的后面，这移不了
		sibling_iterator&  operator++(void){
			if(node)
				node=node->next_sibling;
			return *this;
		}

		//如果已到最前一个兄弟节点的前面，移不了
		sibling_iterator&  operator--(void){
			if(node)
				node=node->prev_sibling;
		/*  comment by zychen
			else{
				assert(parent_);//也就是说head的兄弟节点...
				node=parent_->last_child;
			}
		*/
			return *this;
		}

		sibling_iterator&  operator+=(unsigned int num){
			while(num>0) {
				++(*this);
				--num;
			}
			return (*this);
		}

		sibling_iterator&  operator-=(unsigned int num){