tree.h

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

			while(num>0) {
				--(*this);
				--num;
			}
			return (*this);
		}
		sibling_iterator   operator+(int num) const{
			sibling_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是否指向相同的节点 ******
		bool operator==(const sibling_iterator& other) const{
			return (other.node == node);
		}

	//***************** 比较两个iterator是否指向不同的节点 ******
		bool  operator!=(const sibling_iterator& other) const{
			return (other.node != node);
		}



	//************** 其他 *************************************

		// 是否指向一个结点？
		bool is_valid() const{
			return (node != 0);
		}

		// 当前兄弟节点链表中的第一个
		tree_node *range_first() const
		{
			tree_node *tmp=parent_->first_child;
			return tmp;
		}

		// 当前兄弟节点链表中的最后一个
		tree_node *range_last() const{
			return parent_->last_child;
		}

	//************** 数据 ********************************
		tree_node *node;//指向当前节点

	private:

		//设置parent_指向node的父结点
		void set_parent_()
		{
			parent_=0;
			if(node==0) return;
			if(node->parent!=0)
				parent_=node->parent;
		}
	public:
		tree_node *parent_;//指向父节点(在iterator中没有)
	};
	//------------------------end of sibling_iterator------------------

	//------------------------continue tree----------------------------

	//********************** iterators *************************
	// begin/end of tree
	// begin() 得到的是第一棵树的树根。如果没有树，则指向head
	iterator begin() const{
		return iterator(head->next_sibling);
	}
	// end() 得到的是head
	iterator end() const{
		return iterator(head);
	}
	// begin/end of children of node
	// begin(it)得到子节点
	sibling_iterator begin(iterator pos) const{
		if(pos.node->first_child==0) {
			return end(pos);//begin(pos) == end(pos)表示没有子节点
		}
//		return pos.node->first_child;//错! comment by zychen
		return sibling_iterator(pos.node->first_child);
	}
	// pos指向的节点的最后一个子节点的后一个，node=0, parent_=pos.node
	sibling_iterator end(iterator pos) const{
		sibling_iterator ret(0);
		ret.parent_= pos.node;
		return ret;
	}

	//********************* 由当前iterator得到父，兄，弟iterator *********
	iterator parent(iterator position) const{
		assert(position.node!=0);
		return iterator(position.node->parent);
	}

	iterator previous_sibling(iterator position) const{
		assert(position.node!=0);
		return iterator(position.node->prev_sibling);
	}

	iterator next_sibling(iterator position) const{
		assert(position.node!=0);
		return iterator(position.node->next_sibling);
	}

	//******************* 树的操作例程 **********************************

	//清除所有的树。这些树的root形成以head为头的双向循环链表，其中head不存树
	void clear(){
		if(head)
			while(head->next_sibling!=head)
				erase(head->next_sibling);
	}

	// erase element at position pointed to by iterator, increment iterator
	// 删除it及其子节点，重置it
	iterator erase(iterator it){
		tree_node *cur=it.node;
		assert(cur!=head);//不允许对head进行erase操作
		iterator ret=it;
		ret.skip_children();//设置skip_children_
		++ret;
		erase_children(it);
		if(cur->prev_sibling==0) {//sibling不是循环链表？
			cur->parent->first_child=cur->next_sibling;
		}
		else {
			cur->prev_sibling->next_sibling=cur->next_sibling;
		}
		if(cur->next_sibling==0) {
			cur->parent->last_child=cur->prev_sibling;
		}
		else {
			cur->next_sibling->prev_sibling=cur->prev_sibling;
		}

		destructor(&cur->data);
		alloc_.deallocate(cur,1);
		return ret;
	}
	// erase all children of the node pointed to by iterator
	//但不删除it本身 it子节点将清空
	void erase_children(iterator it){
		tree_node *cur=it.node->first_child;
		tree_node *prev=0;

		while(cur!=0) {
			prev=cur;
			cur=cur->next_sibling;
			erase_children(prev);
			destructor(&prev->data);
			alloc_.deallocate(prev,1);
		}
		it.node->first_child=0;
		it.node->last_child=0;
	}

	// insert node as last child of node pointed to by position
	// 加入子节点(放到最后)，但数据没有给。返回这个子节点
	iterator append_child(iterator position){
		assert(position.node!=head);//不允许加入到head下

		tree_node* tmp = alloc_.allocate(1,0);
		constructor(&tmp->data);
		tmp->first_child=0;
		tmp->last_child=0;

		tmp->parent=position.node;
		if(position.node->last_child!=0) {
			position.node->last_child->next_sibling=tmp;
		}
		else {
			position.node->first_child=tmp;
		}
		tmp->prev_sibling=position.node->last_child;
		position.node->last_child=tmp;
		tmp->next_sibling=0;//可见sibling不是循环链表，first_child的prev_sibling和
						//last_child的next_sibling都是NULL
		return tmp;
	} 

	//和append_child(iterator position)基本一样
	iterator append_child(iterator position, const T& x){
		// If your program fails here you probably used 'append_child' to add the top
		// node to an empty tree. From version 1.45 the top element should be added
		// using 'insert'. See the documentation for further information, and sorry about
		// the API change.
		assert(position.node!=head);

		tree_node* tmp = alloc_.allocate(1,0);
		constructor(&tmp->data, x);
		tmp->first_child=0;
		tmp->last_child=0;

		tmp->parent=position.node;
		if(position.node->last_child!=0) {
			position.node->last_child->next_sibling=tmp;
		}
		else {
			position.node->first_child=tmp;
		}
		tmp->prev_sibling=position.node->last_child;
		position.node->last_child=tmp;
		tmp->next_sibling=0;
		return tmp;
	}

	iterator append_child(iterator position, iterator other_position){
		assert(position.node!=head);

		sibling_iterator aargh=append_child(position, value_type());
		return replace(aargh, aargh+1, other_position, sibling_iterator(other_position)+1);
	}

	// short-hand to insert topmost node in otherwise empty tree
	// 如果还没有创建任何树，使用此函数将建立一棵树
	iterator set_head(const T& x){
		assert(begin()==end());
		return insert(begin(), x);
	}

	// insert node as previous sibling of node pointed to by position
	//前插，作为position的兄弟节点
	iterator insert(iterator position, const T& x){
		//如果position.node==0怎么办？

		//构造新节点tmp
		tree_node* tmp = alloc_.allocate(1,0);
		constructor(&tmp->data, x);
		tmp->first_child=0;
		tmp->last_child=0;

		//作为posintion.node的兄节点
		tmp->parent=position.node->parent;
		tmp->next_sibling=position.node;
		tmp->prev_sibling=position.node->prev_sibling;
		position.node->prev_sibling=tmp;

		if(tmp->prev_sibling==0)
			tmp->parent->first_child=tmp;
		else
			tmp->prev_sibling->next_sibling=tmp;
		return tmp;
	}

	// insert node as previous sibling of node pointed to by position
	// position可以是最后一个子节点的后一个
	iterator insert(sibling_iterator position, const T& x){
		tree_node* tmp = alloc_.allocate(1,0);
		constructor(&tmp->data, x);
		tmp->first_child=0;
		tmp->last_child=0;

		tmp->next_sibling=position.node;
		if(position.node==0) { // iterator points to end of a subtree
			tmp->parent=position.parent_;
			tmp->prev_sibling=position.range_last();
		}
		else {
			tmp->parent=position.node->parent;
			tmp->prev_sibling=position.node->prev_sibling;
			position.node->prev_sibling=tmp;
		}

		if(tmp->prev_sibling==0)
			tmp->parent->first_child=tmp;
		else
			tmp->prev_sibling->next_sibling=tmp;
		return tmp;
	}

	// insert node (with children) pointed to by subtree as previous sibling of node pointed to by position
	iterator insert(iterator position, iterator subtree){
		// insert dummy
		iterator it=insert(position, value_type());
		// replace dummy with subtree
		return replace(it, subtree);
	}

	// insert node (with children) pointed to by subtree as previous sibling of node pointed to by position
	iterator insert(sibling_iterator position, iterator subtree){
		// insert dummy
		iterator it=insert(position, value_type());
		// replace dummy with subtree
		return replace(it, subtree);
	}

	// insert node as next sibling of node pointed to by position
	// 在position之后插入一个弟节点
	iterator insert_after(iterator position, const T& x){
		//构造新节点tmp
		tree_node* tmp = alloc_.allocate(1,0);
		constructor(&tmp->data, x);
		tmp->first_child=0;
		tmp->last_child=0;

		tmp->parent=position.node->parent;
		tmp->prev_sibling=position.node;
		tmp->next_sibling=position.node->next_sibling;
		position.node->next_sibling=tmp;

		if(tmp->next_sibling==0) {
			tmp->parent->last_child=tmp;
		}
		/////////////////////////////////////////////////
		else{//added by zychen
			tmp->next_sibling->prev_sibling = tmp;
		}
		/////////////////////////////////////////////////
		return tmp;
	}


	// replace node at 'position' with other node (keeping same children)
	// 仅仅把position指向的内容更换而已
	iterator replace(iterator position, const T& x){
		destructor(&position.node->data);
		constructor(&position.node->data, x);
		return position;
	}

	// replace node at 'position' with subtree starting at 'from' (do not erase subtree at 'from')
	iterator replace(iterator position, iterator from){
		assert(position.node!=head);//head不允许作为树根
		tree_node *current_from=from.node;
		tree_node *start_from=from.node;
		tree_node *last=from.node->next_sibling;
		tree_node *current_to  =position.node;

		// replace the node at position with head of the replacement tree at from
		erase_children(position);	
		tree_node* tmp = alloc_.allocate(1,0);
		constructor(&tmp->data, (*from));
		tmp->first_child=0;
		tmp->last_child=0;
		if(current_to->prev_sibling==0) {
			current_to->parent->first_child=tmp;
		}
		else {
			current_to->prev_sibling->next_sibling=tmp;
		}
		tmp->prev_sibling=current_to->prev_sibling;
		if(current_to->next_sibling==0) {
			current_to->parent->last_child=tmp;
		}
		else {
			current_to->next_sibling->prev_sibling=tmp;
		}
		tmp->next_sibling=current_to->next_sibling;
		tmp->parent=current_to->parent;
		destructor(&current_to->data);
		alloc_.deallocate(current_to,1);
		current_to=tmp;

		iterator toit=tmp;

		// copy all children
		do{
			assert(current_from!=0);
			if(current_from->first_child != 0) {
				current_from=current_from->first_child;
				toit=append_child(toit, current_from->data);
			}
			else {
				while(current_from->next_sibling==0 && current_from!=start_from) {
					current_from=current_from->parent;
					toit=parent(toit);
					assert(current_from!=0);
				}
				current_from=current_from->next_sibling;
				if(current_from!=last) {