/* 

   $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 <k.peeters@damtp.cam.ac.uk>

   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

//節(jié)點(diǎn)
template<class T>
struct tree_node_ {
	tree_node_<T> *parent;//父節(jié)點(diǎn)
	tree_node_<T> *first_child, *last_child;//子節(jié)點(diǎn)
	tree_node_<T> *prev_sibling, *next_sibling;//兄弟節(jié)點(diǎn)
	T data;//數(shù)據(jù)
};

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

	//******************* 構(gòu)造和析構(gòu)函數(shù) ***********************
//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;

	//*********** 構(gòu)造函數(shù)和析構(gòu)函數(shù) *************************************
		//不指向任何節(jié)點(diǎn)
		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) {//這種情況的發(fā)生是由于
				node=other.range_last();
				skip_children();
				increment_();
			}
		}

	//********** 位移操作 ************************************************
		//只要存在樹，就不會(huì)出錯(cuò)，也就是說 this->node != 0
		//因此不要企圖使用 it!=0 來(lái)作為遍歷結(jié)束條件，一定要用 it!=end()
		iterator&  operator++(void){
			if(!increment_()) {//如果失敗，node一定會(huì)是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;
		}
	//********************* 獲取數(shù)據(jù) ***********************************
		//獲取的是引用
		T&  operator*(void) const{
			return node->data;
		}

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

	//********************* 兩個(gè)iterator關(guān)系 ***********************
		// 兩個(gè)iterator是否指向相同的節(jié)點(diǎn)?
		bool  operator==(const iterator& other) const{
			if(other.node==node) return true;
			else return false;
		}

		// 兩個(gè)iterator是否指向不同的節(jié)點(diǎn)？
		bool  operator!=(const iterator& other) const{
			if(other.node!=node) return true;
			else return false;
		}


		//返回子節(jié)點(diǎn)。如果不存在子節(jié)點(diǎn)，則ret.node == 0
		sibling_iterator begin() const{
			sibling_iterator ret(node->first_child);
			ret.parent_=node;
			return ret;
		}

		//構(gòu)造一個(gè)不指向節(jié)點(diǎn)的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是否指向樹節(jié)點(diǎn)？
		bool is_valid() const{
			if(node==0) return false;
			else return true;
		}

		//直接子節(jié)點(diǎn)的個(gè)數(shù)
		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;
		}

	//********************** 封裝的數(shù)據(jù) ********************
		tree_node *node;//指向樹節(jié)點(diǎn)


	private:
		//如果有下一個(gè)節(jié)點(diǎn)，則返回true，并且node指向它
		//何時(shí)才返回false?只有當(dāng)head==0
		//skip_current_children_作用：
		//  為false時(shí)，如果有子節(jié)點(diǎn)，則指向子節(jié)點(diǎn);如果有兄弟節(jié)點(diǎn)，則為兄弟節(jié)點(diǎn);否則回溯
		//  為true時(shí)，肯定不訪問子節(jié)點(diǎn)
		// 有一個(gè)問題：
		//    設(shè)skip_current_children == false
		//              head<---->root1<---->root2<---->head
		//							/\
		//						   /  \
		//						  a    b
		//	  node當(dāng)前值指向b，則執(zhí)行后node指向root2
		//	  再執(zhí)行一次將指向head!!!!
		//
		bool increment_(){//這個(gè)函數(shù)執(zhí)行后,skip_current_children==false
			assert(node!=0);
			//如果不跳過子節(jié)點(diǎn)并且存在子節(jié)點(diǎn)，則指向第一個(gè)子節(jié)點(diǎn)
			if(!skip_current_children_ && node->first_child) {
				node=node->first_child;
				return true;
			}
			else{
				skip_current_children_=false;
				while(!node->next_sibling){//沒有兄弟節(jié)點(diǎn)，回溯
					node=node->parent;
					if(node==0)
						return false;
				}
				node=node->next_sibling;//由于是pre-order，優(yōu)先訪問本節(jié)點(diǎn)，再訪問子節(jié)點(diǎn)
				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------------------------

	/******************
	*對(duì)于 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;

	//************** 構(gòu)造和析構(gòu)函數(shù) ******************************
		//不指向任何節(jié)點(diǎn)
		sibling_iterator(): node(0), parent_(0){
		}

		//指向 tn，并且設(shè)置parent_指向tn的父節(jié)點(diǎn)
		sibling_iterator(tree_node *tn): node(tn){
			set_parent_();
		}

		//將other的值拷貝過來(lái)
		sibling_iterator(const sibling_iterator& other):
			node(other.node), parent_(other.parent_){
		}

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

	//************** 位移操作 ************************************
		//如果已到最后一個(gè)兄弟節(jié)點(diǎn)的后面，這移不了
		sibling_iterator&  operator++(void){
			if(node)
				node=node->next_sibling;
			return *this;
		}

		//如果已到最前一個(gè)兄弟節(jié)點(diǎn)的前面，移不了
		sibling_iterator&  operator--(void){
			if(node)
				node=node->prev_sibling;
		/*  comment by zychen
			else{
				assert(parent_);//也就是說head的兄弟節(jié)點(diǎn)...
				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){