#ifndef _AVLTREE_
#define _AVLTREE_
#include "mavlnode.hpp"/**************************** * The AVL Tree Iterator class ***************************/template<class T>class AVLIterator{	public:		typedef AVLNode<T>* Link;		typedef AVLIterator<T> iterator;		AVLIterator();		AVLIterator(Link new_link);		virtual ~AVLIterator();		virtual Link& getIterPtr(void);		virtual bool operator==(iterator it);		virtual bool operator!=(iterator it);		virtual iterator operator++();		virtual iterator operator++(int inc);		virtual void operator--();		virtual T& operator*();	protected:		Link link;};/**************************** * The AVL Tree class ***************************/template<class T, class Compare>class AVLTree{	public:		typedef AVLNode<T>* Link;		typedef AVLIterator<T> iterator;		/* constructor and destructor */		AVLTree(void);		virtual ~AVLTree(void);		/* 		 * public methods to allow users 		 * DO "find", "change", "erase" and "insert" operations on AVL tree		 */		virtual iterator find(const T& item);        virtual iterator change(const T& item, const T& new_item);		virtual iterator insert(const T& item);		//virtual void erase(iterator itr);		virtual iterator erase(const T& item);		virtual void clear(Link link);		virtual bool empty(void);		/* get the first and last element */		virtual iterator begin(void);		virtual iterator end(void);		virtual iterator leftmost(void);		virtual iterator rightmost(void);		/* debug and validation */		virtual void print(void);		bool isAVLTree(){ return checkAVLTree(header->parent); }	protected:		Compare compare;		Link header;		unsigned node_count;	private:		/* debug and validation */		virtual bool checkAVLTree(Link root);		virtual int getHeight(Link root, int height, int& maxHeight);		virtual void printTree(Link root, int depth, char* pos);		/* insertion related CORE helper methods */		virtual iterator insertItem(const T& item, Link parent, Link& child);		virtual void insertLeaf(const T& item, Link parent, Link& child);		virtual void fixAfterInsertion(Link ancestor, Link inserted);		virtual void adjustPath(Link to, Link inserted);		virtual void adjustLeftRight(Link ancestor, Link inserted);		virtual void adjustRightLeft(Link ancestor, Link inserted);		virtual void rotateLeft(Link x);		virtual void rotateRight(Link x);		/* deletion related CORE helper methods */        virtual Link eraseNode(Link node, const T& item, bool& shorter);		virtual Link leftBalance(Link node);		virtual Link LL_rotate(Link node);		virtual Link LR_rotate(Link node);		virtual Link rightBalance(Link node);		virtual Link RL_rotate(Link node);		virtual Link RR_rotate(Link node);		//virtual void deleteLink(Link& x);		//virtual void prune(Link& x);};#endif