xcommon.h

符合移动协议的见空系统,很有使用简直,希望多下载

		//balanced as appropriate child of q
		//  if (rebal_direc>0)
		if (rebal_direc<0)
		{
			// insert new node as left child
			parent_ptr->left_childptr = new_ptr;
		}
		else
		{
			// insert new node as right child
			parent_ptr->right_childptr = new_ptr;
		}

		// Now adjust balance factors of all
		// in the search path from 'root' to
		// the parent node, parent_ptr.
		// By AVL property, all nodes on the
		// search path from most recent node and
		// and parent node must have 0 balance
		// factors, and change to -1 or +1.
		// factors, and change to -1 or +1.
		// rebal_dir = -1 => new data has been
		// inserted in right subtree of most_recent_ptr.
		// rebal_dir = +1 => new data has been
		// inserted in left subtree of most_recent_ptr.

		
		
		if (new_data.compare(most_recent_ptr->data)>0)
		{
			curr_ptr = most_recent_ptr->right_childptr;
			rebal_direc = -1;
		}
		else
		{
			curr_ptr = most_recent_ptr->left_childptr;
			rebal_direc = +1;
		}

		most_recent_child_ptr = curr_ptr;
		while (curr_ptr != new_ptr)
		{
			if(new_data.compare(curr_ptr->data)>0)
			{
				// hight of right is increased by 1
				curr_ptr->bal_fact = -1;
				curr_ptr = curr_ptr->right_childptr;
			}
			else
			{
				// hight of left is increased by 1
				curr_ptr->bal_fact = +1;
				curr_ptr = curr_ptr->left_childptr;
			}			
		}
		// need to check if the balance of
		// the tree is alright
		unbal_flag = 1;
		if (most_recent_ptr->bal_fact == 0)
		{
			// tree is not unbalanced
			most_recent_ptr->bal_fact = rebal_direc;
			unbal_flag = 0;
		}
		if ( (most_recent_ptr->bal_fact + rebal_direc) == 0 )
		{
			// tree is not unbalanced
			most_recent_ptr->bal_fact = 0;
			unbal_flag = 0;
		}
		if (unbal_flag == 1)
		{
			// Tree is unbalanced. determine
			// rotation direction, and rotate.
			if (rebal_direc == +1)
			{
				// left subtree is imbalanced
				// Rotate left
				if (most_recent_child_ptr->bal_fact == +1)
				{
					most_recent_ptr->left_childptr = most_recent_child_ptr->right_childptr;
					most_recent_child_ptr->right_childptr = most_recent_ptr;
					most_recent_ptr->bal_fact = 0;
					most_recent_child_ptr->bal_fact = 0;
				}
				else
				{
					new_root_ptr = most_recent_child_ptr->right_childptr;
					most_recent_child_ptr->right_childptr = new_root_ptr->left_childptr;
					most_recent_ptr->left_childptr = new_root_ptr->right_childptr;
					new_root_ptr->left_childptr = most_recent_child_ptr;
					new_root_ptr->right_childptr = most_recent_ptr;
					switch (new_root_ptr->bal_fact)
					{
					case +1:
						most_recent_ptr->bal_fact = -1;
						most_recent_child_ptr->bal_fact = 0;
						break;
					case -1:
						most_recent_child_ptr->bal_fact = 1;
						most_recent_ptr->bal_fact = 0;
						break;
					case 0:
						most_recent_child_ptr->bal_fact = 0;
						most_recent_ptr->bal_fact = 0;
						break;
					}// end of the switch statement
					new_root_ptr->bal_fact = 0;
					most_recent_child_ptr = new_root_ptr;
				}
			}
			else
			{
				// right substree is unbalanced
				if (most_recent_child_ptr->bal_fact == -1)
				{
					most_recent_ptr->right_childptr = most_recent_child_ptr->left_childptr;
					most_recent_child_ptr->left_childptr = most_recent_ptr;
					most_recent_ptr->bal_fact = 0;
					most_recent_child_ptr->bal_fact = 0;
				}
				else
				{
					new_root_ptr = most_recent_child_ptr->left_childptr;
					most_recent_child_ptr->left_childptr = new_root_ptr->right_childptr;
					most_recent_ptr->right_childptr = new_root_ptr->left_childptr;
					new_root_ptr->right_childptr = most_recent_child_ptr;
					new_root_ptr->left_childptr = most_recent_ptr;
					switch (new_root_ptr->bal_fact)
					{
					case -1:            // Should be -1
						most_recent_ptr->bal_fact = 1;
						most_recent_child_ptr->bal_fact = 0;
						break;
					case +1:            // Should be +1
						most_recent_child_ptr->bal_fact = -1;
						most_recent_ptr->bal_fact = 0;
						break;
					case 0:
						most_recent_child_ptr->bal_fact = 0;
						most_recent_ptr->bal_fact = 0;
						break;
					}
					new_root_ptr->bal_fact = 0;
					most_recent_child_ptr = new_root_ptr;
				}// end of the else
			}  // end of the if rebal_direc = -1

			if (most_recents_parent_ptr == NULL)
			{
				root_ptr = most_recent_child_ptr;
			}
			else
			{
				if (most_recent_ptr == most_recents_parent_ptr->left_childptr)
				{
					most_recents_parent_ptr->left_childptr = most_recent_child_ptr;
				}
				else
				{
					if (most_recent_ptr == most_recents_parent_ptr->right_childptr)
					{
						most_recents_parent_ptr->right_childptr = most_recent_child_ptr;
					}
				}
			}
		} // end of if unbalanced
 }
 return &(new_ptr->data);
}

template <class T> inline void BBT2<T>::copy_to(BBT2<T> &tree)
{
	T *dp;
	BBT2<T> traverse(*this);
	while(dp=traverse.get_next_node())
		tree.add_node(*dp);
}

template <class T> inline void BBT2<T>::move_to(BBT2<T> &tree)
{
	tree.root_ptr=root_ptr;
	tree.TOTAL_NODE_NUM=TOTAL_NODE_NUM;
	root_ptr = NULL;
	TOTAL_NODE_NUM = 0;
}

template <class T> T *BBT2<T>::search_node(T &srch_key)
{
	NODE_PTR  srch_ptr =root_ptr;
	int fcmp;
	while(srch_ptr)
	{
	   
	   if((fcmp=srch_key.compare(srch_ptr->data))==0)
			return &(srch_ptr->data);
	   if(fcmp<0)
			srch_ptr=srch_ptr->left_childptr;
	   else
			srch_ptr=srch_ptr->right_childptr;
	}
	return NULL;
}
template <class T> inline void BBT2<T>::traverse_and_empty(void (*f)(T&))
{
	traverse_Preorder_and_delete(f,root_ptr);
	root_ptr=NULL;
	TOTAL_NODE_NUM = 0;
}
template <class T> void BBT2<T>::traverse_Preorder_and_delete(void (*f)(T&),NODE_PTR  tree_ptr)
{
	NODE_PTR p;
	if (tree_ptr != NULL)
	{
		traverse_Preorder_and_delete(f,tree_ptr->left_childptr);
		f(tree_ptr->data);
		p=tree_ptr->right_childptr;
		delete tree_ptr;
		traverse_Preorder_and_delete(f,p);
	}
}

template <class T> inline void BBT2<T>::traverse(void (*f)(T&),int order)
{
	switch(order)
	{
    case PREORDER:
		traverse_Preorder(f,root_ptr);
		break;
    case INORDER:
		traverse_Inorder(f,root_ptr);
		break;
    case POSTORDER:
		traverse_Postorder(f,root_ptr);
		break;
	}
}

template <class T> void BBT2<T>::traverse_Preorder(void (*f)(T&),NODE_PTR  tree_ptr)
{
	if (tree_ptr != NULL)
	{
		traverse_Preorder(f,tree_ptr->left_childptr);
		f(tree_ptr->data);
		traverse_Preorder(f,tree_ptr->right_childptr);
	}
}
template <class T> void BBT2<T>::traverse_Inorder(void (*f)(T&),NODE_PTR  tree_ptr)
{
	if (tree_ptr != NULL)
	{
		f(tree_ptr->data);
		traverse_Preorder(f,tree_ptr->left_childptr);
		traverse_Preorder(f,tree_ptr->right_childptr);
	}
}
template <class T> void BBT2<T>::traverse_Postorder(void (*f)(T&),NODE_PTR  tree_ptr)
{
	if (tree_ptr != NULL)
	{
		traverse_Postorder(f,tree_ptr->right_childptr);
		f(tree_ptr->data);
		traverse_Postorder(f,tree_ptr->left_childptr);
	}
}


template<class T>
class Stack
{
public :
	Stack(int MaxStackSize = 10);
	~Stack() {delete [] stack;}
	bool IsEmpty() const {return top == -1;}
	bool IsFull() const {return top == MaxTop;}
	T Top() const;
	Stack<T>& Push(const T& x);
	T Pop();
private :
	int top;
	int MaxTop;
	T *stack;
};
template<class T>
Stack<T>::Stack(int MaxStackSize)
{
	MaxTop = MaxStackSize - 1;
	stack = new T[MaxStackSize];
	top = -1;
}
template<class T>
T Stack<T>::Top() const
{
	if (IsEmpty()) throw OutOfBounds();
	else return stack[top];
}
template<class T>
Stack<T>& Stack<T>::Push(const T& x)
{
	if(IsFull()) throw NoMem();
	stack[++top] = x;
	return *this;
}
template<class T>
T Stack<T>::Pop()
{
	if (IsEmpty()) throw OutOfBounds();
	else
		return stack[top--];
}

class CPair
{
public:
	char key;
	char *src;	
	char *dst;	
	int len;
	CReplaceTree  *next;
	int m_iCount;
public:
	void Merge(CPair& t){}
	CPair(){next=NULL;key = 0;src=NULL;dst=NULL;len=0;m_iCount=0;}
	//CPair(char Chr);
	~CPair()
	{
        if(src)
        {
            delete []src;
            src = NULL;
        }
        if(dst)
        {
            delete []dst;
            dst = NULL;
        }
		if(next)
        {
			delete next;//next->empty();
            next = NULL;
        }
	}
	int compare(CPair& des);
	void  OutputToFile(FILE *fp)
	{
	        fprintf(fp,"%s\t%dn",key,m_iCount);
	}
	CPair& CPair::operator =(CPair & s);
};
void    AddNode(CReplaceTree *tree,const char *p,int len,const char *des);
int     Replace(char *szLine,char *szOutLine,CReplaceTree* srchTree);
int     Replace(char *szLine,CReplaceTree* srchTree);
CPair   *Search(CReplaceTree *tree,char *p);
int     BuildPairTree(CReplaceTree *tree,PTRMAP* pSource);





template <class Type> class  List;
template <class Type> class  ListNode
{
	friend class List <Type>;
public:
	ListNode();
	ListNode(Type &item);
	ListNode <Type> *NextNode(){return link;}
	void InsertAfter (ListNode<Type> *p);
	ListNode <Type> *GetNode(Type &item,ListNode <Type> *next);
	ListNode <Type> *RemoveAfter();
private:
	Type data;
	ListNode <Type> *link;
};
template <class Type> class List
{
	public:
		List(Type &value){
			last = first= new ListNode <Type> (value);
		}
		List(){};
		~List();
		void MakeEmpty();
		int Length() const;
		ListNode <Type> *Find(Type value);
		ListNode <Type> *Find(int i);
		int Insert (Type &value,int i);
		Type *Remove(int i);
		Type *Get(int i);
	public:
		ListNode <Type> *first ,*last;
};
template <class Type> ListNode <Type>::ListNode():link(NULL){}
template <class Type> ListNode <Type>::ListNode(Type &item):data(item),link(NULL){}
template <class Type> void ListNode <Type>::InsertAfter(ListNode <Type> *p)
{
	p->link = link; 
	link = p;
}
template <class Type> ListNode <Type> *ListNode <Type>::GetNode(Type &item,ListNode <Type> *next=NULL)
{
	ListNode <Type> *newnode= new ListNode <Type> (item);
	newnode->link = next;
	return newnode;
}
template <class Type> ListNode <Type> *ListNode <Type>::RemoveAfter()
{
	ListNode <Type> *tempptr = link;
	if(link == NULL) return NULL;
	link = tempptr->link;
	return tempptr;
}
template <class Type> List <Type>::~List()
{
	MakeEmpty();
	delete first;
}
template <class Type> void List <Type>::MakeEmpty()
{
	ListNode <Type> *q;
	while(first->link!=NULL)
	{
		q = first->link;
		first->link = q->link;
		delete q;
	}
	last = first;
}
template <class Type> int List <Type>::Length() const
{
	ListNode <Type> *p= first->link;
	int count =0;
	while(p!=NULL)
	{
		p = p->link;
		count++;
	}
	return count;
}
template <class Type> ListNode <Type> *List <Type>::Find(Type value)
{
	ListNode <Type> *p = first->link;
	while(p!=NULL&&p->data!=value) 
		p=p->link;
	return p;
}
template <class Type>
ListNode<Type> *List <Type>::Find(int i)
{
	if(i<-1) return NULL;
	if(i==-1) return first;
	ListNode <Type> *p = first->link;
	int j=0;
	while(p!=NULL &&j<i)
	{
		p = p->link;
		j++;
	}
	return p;
}
template <class Type> int List <Type>::Insert(Type &value,int i)
{
	ListNode <Type> *p = Find(i-1);
	if(p==NULL) return 0;
	ListNode <Type> *newnode = p->GetNode(value,p->link);
	if(p->link==NULL) last = newnode;
	p->link = newnode;
	return 1;
}
template <class Type> Type *List<Type>::Remove(int i)
{
	ListNode <Type> *p = Find(i-1),*q;
	if(p==NULL || p->link==NULL) return NULL);
	q = p->link;
	p->link = q->link;
	Type value = new Type(q->data);
	if(q==last) last = p;
	delete q;
	return &value;
}
template <class Type> Type *List <Type>::Get(int i)
{
	ListNode <Type> *p = Find(i);
	if(p==NULL||p==first)
		return NULL;
	else
		return &p->data;
}
int		OpenAll(CWorkFile *wk,...);
int		CloseAll(CWorkFile *wk...);
int ForceAlign(char *lpszBuf,int cnt);
int CleanHeadTailSpace(char *InLine);
int MarkCount(char *str, char *mark);
bool Is_WholeNumber(char *str, bool bSign, bool bDot);

// Creator: Andreas J鋑er
//          Ortsstr. Nr. 2
//        D-07407 Geitersdorf
//
// Last updated: 15. November 1998
// e-mail: [e-mail]
//
// 
// Copyright and author: 
// Andreas J鋑er: [e-mail]
// 
// You may handle this code to others only when you do not delete these
// copyright-lines.
// These source files may not be copied except by permission of the author.
// These source files may not be included in source or compiled form as any
// part of a commercial distribution except by permission of the
// author. 
// These files may be used freely for internal corporate use.
// These files may also may be used freely by students for 
// educational purposes.
// No warranty or guarrantee of fitness can be made to these files.
//
// 
// have fun!
//
// Updates:
// 
// * 15.11.1998 - Some fixes in Delete()- and RestructureDelete()-
//                routines which could make the tree inconsistent
//                and result in a GPF (after lots of Insert- and 
//                Delete-operations)
//              - Rename Level() -> GetLevel()
//              - new methods GetDepth() and NodesInTree() for 
//                CAVLTree class
//              - new (debug) function CheckBalances()
//              - Draw() function only in Visual C++ environment
//                (not Borland) for portability
//              - updated sample project
//
////////////////////////////////////////////////////////////////
// Note:                                                      //
// there must be a function T::Compare(T&)                    //
// or the function Compare of teh Template-Klasse             //
// CAVLNode<T> has to be overridden.                          //
////////////////////////////////////////////////////////////////

////////////////////////////////////////////////////////////////
// Vorbemerkungen:                                            //
// Es mu