toit=append_child(parent(toit), current_from->data);
				}
			}
		}while(current_from!=last);

		return current_to;
	}

	// replace string of siblings (plus their children) with copy of a new string (with children)
	iterator replace(sibling_iterator orig_begin, sibling_iterator orig_end, 
						  sibling_iterator new_begin,  sibling_iterator new_end){
		tree_node *orig_first=orig_begin.node;
		tree_node *new_first=new_begin.node;
		tree_node *orig_last=orig_first;
		while(++orig_begin!=orig_end)
			orig_last=orig_last->next_sibling;
		tree_node *new_last=new_first;
		while(++new_begin!=new_end)
			new_last=new_last->next_sibling;
		// insert all siblings in new_first..new_last before orig_first
		bool first=true;
		iterator ret;
		while(1==1) {
			iterator tt=insert(iterator(orig_first), new_first);
			if(first) {
				ret=tt;
				first=false;
			}
			if(new_first==new_last)
				break;
			new_first=new_first->next_sibling;
		}
		// erase old range of siblings
		bool last=false;
		tree_node *next=orig_first;
		while(1==1) {
			if(next==orig_last) 
				last=true;
			next=next->next_sibling;
			erase(orig_first);
			if(last) 
				break;
			orig_first=next;
		}
		return ret;
	}
 

	// move all children of node at 'position' to be siblings
	iterator flatten(iterator position)
	{
		if(position.node->first_child==0)
			return position;
		tree_node *tmp=position.node->first_child;
		while(tmp) {
			tmp->parent=position.node->parent;
			tmp=tmp->next_sibling;
		} 
		if(position.node->next_sibling) {
			position.node->last_child->next_sibling=position.node->next_sibling;
			position.node->next_sibling->prev_sibling=position.node->last_child;
		}
		else {
			position.node->parent->last_child=position.node->last_child;
		}
		position.node->next_sibling=position.node->first_child;
		position.node->next_sibling->prev_sibling=position.node;
		position.node->first_child=0;
		position.node->last_child=0;
		return position;
	}

	// move nodes in range to be children of 'position'
	iterator reparent(iterator position, sibling_iterator begin, sibling_iterator end)
	{
		tree_node *first=begin.node;
		tree_node *last=first;
		while(++begin!=end) {
			last=last->next_sibling;
		}
		// move subtree
		if(first->prev_sibling==0) {
			first->parent->first_child=last->next_sibling;
		}
		else {
			first->prev_sibling->next_sibling=last->next_sibling;
		}
		if(last->next_sibling==0) {
			last->parent->last_child=first->prev_sibling;
		}
		else {
			last->next_sibling->prev_sibling=first->prev_sibling;
		}
		if(position.node->first_child==0) {
			position.node->first_child=first;
			position.node->last_child=last;
			first->prev_sibling=0;
		}
		else {
			position.node->last_child->next_sibling=first;
			first->prev_sibling=position.node->last_child;
			position.node->last_child=last;
		}
		last->next_sibling=0;

		tree_node *pos=first;
		while(1==1) {
			pos->parent=position.node;
			if(pos==last) break;
			pos=pos->next_sibling;
		}
		return first;
	}

	// ditto, the range being all children of the 'from' node
	iterator reparent(iterator position, iterator from)
	{
		if(from.node->first_child==0) return position;
		return reparent(position, from.node->first_child, from.node->last_child);
	}

	// merge with other tree, creating new branches and leaves only if they are not already present
	void merge(iterator position, iterator other, bool duplicate_leaves=false)
	{
		sibling_iterator fnd;
		sibling_iterator oit=other;
		while(oit.is_valid()) {
			if((fnd=find(position.begin(), position.end(), (*other)))!=position.end()) {
				if(duplicate_leaves && other.begin()==other.end()) { // it's a leave
					append_child(position, (*other));
				}
				else {
					if(other.begin()!=other.end())
						merge(fnd, other.begin(), duplicate_leaves);
				}
			}
			else {
				insert(position.end(), oit);
			}
			++oit;
		}
	}

	// sort (std::sort only moves values of nodes, this one moves children as well)
	void sort(sibling_iterator from, sibling_iterator to, bool deep=false)
	{
		std::less<T> comp;
		sort(from, to, comp, deep);
	}

	template<class StrictWeakOrdering>
	void sort(sibling_iterator from, sibling_iterator to, StrictWeakOrdering comp, bool deep=false)
	{
		if(from==to) return;
		// make list of sorted nodes
		// CHECK: if multiset stores equivalent nodes in the order in which they
		// are inserted, then this routine should be called 'stable_sort'.
		std::multiset<tree_node *, compare_nodes<StrictWeakOrdering> > nodes;
		sibling_iterator it=from, it2=to;
		while(it != to) {
			nodes.insert(it.node);
			++it;
		}
		// reassemble
		--it2;
		tree_node *prev=from.node->prev_sibling;
		tree_node *next=it2.node->next_sibling;
		typename std::multiset<tree_node *, compare_nodes<StrictWeakOrdering> >::iterator nit=nodes.begin(), eit=nodes.end();
		if(prev==0) {
			(*nit)->parent->first_child=(*nit);
		}
		--eit;
		while(nit!=eit) {
			(*nit)->prev_sibling=prev;
			if(prev)
				prev->next_sibling=(*nit);
			prev=(*nit);
			++nit;
		}
		if(prev)
			prev->next_sibling=(*eit);
		(*eit)->next_sibling=next;
		if(next==0) {
			(*eit)->parent->last_child=next;
		}

		if(deep) {	// sort the children of each node too
			sibling_iterator bcs(*nodes.begin());
			sibling_iterator ecs(*eit);
			++ecs;
			while(bcs!=ecs) {
				sort(begin(bcs), end(bcs), comp, deep);
				++bcs;
			}
		}
	}

	// compare subtrees starting at the two iterators (compares nodes as well as tree structure)
	template<class BinaryPredicate>
	bool equal(iterator one, iterator two, iterator three, BinaryPredicate fun) const
	{
		while(one!=two && three.is_valid()) {
			if(one.number_of_children()!=three.number_of_children()) 
				return false;
			if(!fun(*one,*three))
				return false;
			++one;
			++three;
		}
		return true;
	}

	// extract a new tree formed by the range of siblings plus all their children
	tree subtree(sibling_iterator from, sibling_iterator to) const
	{
		tree tmp;
		tmp.set_head(value_type());
		tmp.replace(tmp.begin(), tmp.end(), from, to);
		return tmp;
	}
	void subtree(tree&, sibling_iterator from, sibling_iterator to) const
	{
		tree tmp;
		tmp.set_head(value_type());
		tmp.replace(tmp.begin(), tmp.end(), from, to);
	}
		
	// count the total number of nodes
	//樹中的節點總數
	int size() const{
		int i=0;
		iterator it=begin(), eit=end();
		while(it!=eit) {
			++i;
			++it;
		}
		return i;
	}

	// compute the depth to the root
	// root的深度是0
	int depth(iterator it) const{
		tree_node* pos=it.node;
		assert(pos!=0);//it必須有效
		int dep=0;
		while(pos->parent) {//root的parent是0
			pos=pos->parent;
			++dep;
		}
		return dep;
	}

	// count the number of children of node at position
	//it指向的節點的子節點的總數
	unsigned int number_of_children(iterator it) const{
		tree_node *pos=it.node->first_child;
			//如果it.node == 0，怎么辦？
		if(pos==0) return 0;
			
		unsigned int count=1;
		while(pos!=it.node->last_child) {
			++count;
			pos=pos->next_sibling;
		}
		return count;
	}

	// count the number of 'next' siblings of node at iterator
	//計算 ---"弟"---節點 的個數
	unsigned int number_of_siblings(iterator it) const
	{
		tree_node *pos=it.node;
		unsigned int ret=1;
		while(pos->next_sibling && pos->next_sibling!=head) {
			//兄弟節點是對同一個直接父節點而言的。如果計算的是樹的棵數，則要
			//加判斷 pos->next_sibling!=head
			++ret;
			pos=pos->next_sibling;
		}
		return ret;
	}

	//增加：陳真勇 2002/11/29
	//　尋找一個節點，并指向它
	iterator find(T& data,iterator start)
	{
		iterator it;
		for(it = begin(); it != end(); ++it){
			if( *it == data ) break;
		}

		return it;
	}
	//增加：陳真勇 2002/11/29
	//	是直接子節點嗎？
	bool is_child(iterator parent,iterator child)
	{
		sibling_iterator ch = parent.begin();
		for(;ch != parent.end();++ch){
			if(ch == child)
				return true;
		}
		return false;
	}

	// determine whether node at position is in the subtrees with root in the range
	// 判斷position是否在[begin,end)內
	bool  is_in_subtree(iterator position, iterator begin, iterator end) const
	{
		// FIXME: this should be optimised.
		iterator tmp=begin;
		while(tmp!=end) {
			if(tmp==position) return true;//change from it to position. by zychen
			++tmp;
		}
		return false;
	}

	// return the n-th child of the node at position
	// 返回節點position的第num個子節點數據。第一個對應num==0
	T& child(iterator position, unsigned int num) const{
		tree_node *tmp=position.node->first_child;//change from it to position. by zychen
		while(num--){
			assert(tmp!=0);
			tmp=tmp->next_sibling;
		}
		return tmp->data;
	}
private:
	tree_node_allocator alloc_;
	tree_node *head;    // head is always a dummy; if an iterator points to head it is invalid

	//初始化head節點，不放數據
	void head_initialise_(){
			head = alloc_.allocate(1,0); // MSVC does not have default second argument 
				//1 element,no hint

			head->parent=0;//沒有父節點。這樣一來，所有的樹的根節點的parent都將為0
			head->first_child=0;//沒有子節點
			head->last_child=0;
			head->prev_sibling=head;
			head->next_sibling=head;
	}

	//將other樹拷貝為當前樹
	void copy_(const tree<T,tree_node_allocator>& other){
			clear();//清除當前森林
			iterator it=other.begin(), to=begin();
			while(it!=other.end()){
				to=insert(to, (*it));
				it.skip_children();//為什么不用next_sibling?
				++it;
			}
			to=begin();
			it=other.begin();
			while(it!=other.end()){
				to=replace(to, it);
				to.skip_children();
				it.skip_children();
				++to;
				++it;
			}
	}
	template<class StrictWeakOrdering>
	class compare_nodes
	{
	public:
		bool operator()(const tree_node* a, const tree_node* b){
			static StrictWeakOrdering comp;
			return comp(a->data, b->data);
		}
	};
};

#endif

// Local variables:
// default-tab-width: 3
// End: