Скачиваний:
13
Добавлен:
01.05.2014
Размер:
16.46 Кб
Скачать
#if !defined(__randomizesearchtree__)
#define __randomizesearchtree__
#endif


#include "stdafx.h"
#include "RandomizeNode.cpp"
#include <list>

namespace RandomTree
{

using namespace std;


/** Система классов исключений */
class treeException
{
	public:
	
		virtual char* get_comment() 
		{
			return "Ошибка в дереве";
		}
};

class out_of_bounds:public treeException
{	protected:
		char comment[100];
	public:
		out_of_bounds()
		{	memset(comment,0,100);}
		out_of_bounds(char *c)
		{	memset(comment,0,100);
			memcpy(comment,c,strlen(c)>(100-1)?(100-1):strlen(c));
		}
		virtual char* get_comment() 
		{
			return comment;
		}

};

class no_defined_iter:public treeException
{	protected:
		char comment[100];
	public:
		no_defined_iter()
		{	memset(comment,0,100);}
		no_defined_iter(char *c)
		{	memset(comment,0,100);
			memcpy(comment,c,strlen(c)>(100-1)?(100-1):strlen(c));
		}
		virtual char* get_comment() 
		{
			return comment;
		}


};


class out_of_memory:public treeException
{	protected:
		char comment[100];
	public:
		out_of_memory()
		{	memset(comment,0,100);}
		out_of_memory(char *c)
		{	memset(comment,0,100);
			memcpy(comment,c,strlen(c)>(100-1)?(100-1):strlen(c));
		}
		virtual char* get_comment()
		{
			return comment;
		}
};


/**************   РАНДОМИЗИРОВАННОЕ ДЕРЕВО       **************/


template <class T> class RandomizeSearchTree
{
private:
	int cmp (T *a, T *b);
	void removeRandomizeNode(RandomizeNode<T>*);	//удалить узел дерева
	RandomizeNode<T> *win;		//текущий элемнент списка
	RandomizeNode<T> *root;		//корень дерева
    RandomizeNode<T> *max;		//МАКСимальный элемент дерева
	RandomizeNode<T> *min;		//МИНимальный элемент дерева

	typedef const RandomizeSearchTree<T> t_constTree;
	typedef RandomizeSearchTree<T> t_noconstTree;
private:
	/*Шаблон итератора по дереву
		_Tree	- контейнер					
		_Node - тип возвращаемый опреатором * и -> (узел дерева)
	*/
	template<class _Tree,class _Node>
	class	tree_iterator
	{
		typedef tree_iterator<_Tree,_Node> t_iterator;
		typedef tree_iterator<t_noconstTree,_Node> t_noconst_iterator;
		typedef tree_iterator<t_constTree,_Node> t_const_iterator;
		_Tree	*p_cont_tree; //указатель на контейнер
		_Node	*cur;		  //текущий узел
		
	public:

		//конструктор по умолчанию
		tree_iterator():p_cont_tree(NULL)
		{
		}

		
		//конструктор
		tree_iterator(_Tree &t, _Node &el)
		{
			p_cont_tree = &t;
			cur = &el;
		}

		
		//опрератор преобразования типа в iter_type_const
		operator t_const_iterator()
		{
			return t_const_iterator(*p_cont_tree,cur);
		}
	

		// оператор = 
		void operator = (t_iterator& temp)	
		{	
			p_cont_tree = temp.p_cont_tree; 
			cur = temp.cur;
		}
				

		//оператор *
		_Node* operator* ()	
		{
			return cur;
		}


		// оператор ->
		_Node* operator-> () 
		{	
			return &*cur;
		}

	private:
		// получить левое поддерево
		_Node* getLeftChild()
		{
			return cur->lchild();
		}

		
		// получить правое поддерево
		_Node* getRightChild()
		{
			return cur->rchild();
		}

		// получить родителя
		_Node* getParent()
		{
			return cur->parent();
		}


		// получить левое поддерево
		_Node* getNext()
		{
			return cur->next();
		}

		
		// получить правое поддерево
		_Node* getPrev()
		{
			return cur->prev();
		}

	public:
		// переход на левое поддерево
		t_iterator& toLeft()
		{	
			if (p_cont_tree == NULL) throw no_defined_iter("Не определен итератор для дерева!");
			if (getLeftChild() == NULL) throw out_of_bounds("Попытка перейти к несуществующему узлу!");
			cur = getLeftChild();
			return *this;
		}


		// переход на правое поддерево
		t_iterator& toRight()
		{	
			if (p_cont_tree == NULL) throw no_defined_iter("Не определен итератор для дерева!");
			if (getRightChild() == NULL) throw out_of_bounds("Попытка перейти к несуществующему узлу!");
			cur = getRightChild();
			return *this;
		}


		// переход к родителю
		t_iterator& toParent()
		{	
			if (p_cont_tree == NULL) throw no_defined_iter("Не определен итератор для дерева!");
			if (getParent() == NULL) throw out_of_bounds("Попытка перейти к несуществующему узлу!");
			cur = getParent();
			return *this;
		}


		// оператор ++ 
		// переход на узел, следующий за текущим
		t_iterator& operator++()
		{	
			if (p_cont_tree == NULL) throw no_defined_iter("Не определен итератор для дерева!");
			try 
			{ 
				cur = getNext();
			}	
			catch (...)	
			{ 
				throw out_of_bounds("Попытка перейти к несуществующему узлу!");
			}
			return *this;
		}


		// оператор -- 
		// переход на узел, предыдущий текущему 
		t_iterator& operator--()
		{
			if (p_cont_tree == NULL) throw no_defined_iter("Не определен итератор для дерева!");
			try 
			{ 
				cur = getPrev();
			}	
			catch (...)	
			{ 
				throw out_of_bounds("Попытка перейти к несуществующему узлу!");
			}
			return *this;
		}
				
		bool equals (const t_iterator &t1)
		{	
			return	(cur==t1.cur &&
					 p_cont_tree==t1.p_cont_tree);
		}
	
		// оператор ==
		friend bool operator == (const t_iterator &t1,const t_iterator& t2)
		{	
			return	(t1.cur==t2.cur &&
					 t1.p_cont_tree==t2.p_cont_tree);
		}


		// оператор !=
		friend bool operator != (const t_iterator &t1,const t_iterator& t2)
		{	
			return	!(t1.cur==t2.cur &&
					  t1.p_cont_tree==t2.p_cont_tree);
		}
	};




public:

	typedef RandomizeNode<T> t_node;
	typedef RandomizeSearchTree<T> t_rst;
	//Итератор по дереву
	typedef tree_iterator<t_noconstTree,t_node> iterator;
 
	//Константный итератор по дереву
	typedef tree_iterator<t_constTree,t_node> const_iterator;

	RandomizeSearchTree();
    virtual ~RandomizeSearchTree(void);

	
//  ФУНКЦИИ
    
	RandomizeNode<T> *find_elem(T *);
	void modify();
	//вставить новый узел с приоритетом в дерево
    void insert(T *, double k, bool needModify = true);
	//вставить узел со случайным приоритетом в дерево
	void insert(T *val);
	//вставить элемент в упорядоченный список 
	void insertInList(RandomizeNode<T> *val);
	//удалить элемент из списока 
	void removeFromList(RandomizeNode<T> *val);
	void replaceNodeInList(RandomizeNode<T> *val);
	//удалить
	virtual void remove(void);
	//удалить узел
	T *remove(T *);
	//удалить все поддеревья дерева
	void deleteChildren(RandomizeNode<T> *p_rn);
	//удалить всё дерево
	void clear();

	T *next(void);
    T *prev(void);
	
	T *roundnext(void);
	T *roundprev(void);
	
	T *val(void);
    int isFirst(void);
    int isLast(void);
    int isHead(void);
    int isEmpty(void);

    T *findMin(void);
	
	RandomizeNode<T> *getWin();		//текущий элемнент списка
	RandomizeNode<T> *getRoot();	//корень дерева
    RandomizeNode<T> *getMax();		//МАКСимальный элемент дерева
	RandomizeNode<T> *getMin();		//МИНимальный элемент дерева
	
	void setWin(RandomizeNode<T> *);		//текущий элемнент списка
	void setRoot(RandomizeNode<T> *);		//корень дерева
    void setMax(RandomizeNode<T> *);		//МАКСимальный элемент дерева
	void setMin(RandomizeNode<T> *);		//МИНимальный элемент дерева

	iterator begin()
	{	
		return iterator(*this, *root->minimum());
	}
	//Возвращает константный итератор, указывающий на начало списка
	const_iterator begin() const
	{	
		return const_iterator(*this, *root->minimum());
	}
	//Возвращает итератор, указывающий на конец списка
	iterator end()
	{	
		return iterator(*this, *root->minimum()->prev());
	}
	//Возвращает константный итератор, указывающий на конец списка
	const_iterator end() const
	{	
		return const_iterator(*this, *root->minimum()->prev());
	}
	//Возвращает итератор, указывающий на нужный элемент
	iterator find(T* t)
	{	
		return iterator(*this,*find_elem(t));
	}
	//Возвращает константный итератор, указывающий на нужный элемент
	const_iterator find(const T* t) const
	{	
		return const_iterator(*this,*find_elem(t));
	}
	//Возвращает количество узлов
	int size()
	{
		int count = 0;
		iterator tmp, tek;
		if (root != NULL)
		{
			tmp = begin();
			do
			{
				count++;
				++tmp;
			} while ((*tmp)->getVal() != (*(begin()))->getVal());
		}
		return count;
	}

	int depthOfTree(RandomizeNode<T> *uz, int count, int tmp_count)
	{
		if (uz != NULL)
		{
			tmp_count++;
			if (uz->lchild() !=NULL)
				count = depthOfTree(uz->lchild(), count, tmp_count);
			if (uz->rchild() !=NULL)
				count = depthOfTree(uz->rchild(), count, tmp_count);
		}
		if (tmp_count > count)
			count = tmp_count;
		tmp_count--;
		return count;
	}

	//Возвращает глубину дерева
	int depthOfTree(RandomizeNode<T> *tt)
	{	if (!tt) return -1; 
		return depthOfTree(tt, 0, 0);
	}
};



//Конструктор
template<class T>
RandomizeSearchTree<T>::RandomizeSearchTree(/*int seed = -1*/)
{
	win = NULL;
	root = NULL;
	min = NULL;
	max = NULL;
}


//	Деструктор
template<class T>
RandomizeSearchTree<T>::~RandomizeSearchTree(void)
{
	clear();
	win = NULL;
	min = NULL;
	max = NULL;
}


//удалить все поддеревья дерева
template<class T>
void RandomizeSearchTree<T>::deleteChildren(RandomizeNode<T> *p_rn)
{	
	if (p_rn == NULL)
		return;
	if (p_rn->getVal())
		delete p_rn->getVal();

	if (p_rn->lchild())
	{
		deleteChildren(p_rn->lchild());
		delete p_rn->lchild();
	}
	if (p_rn->p_rchild)
	{
		deleteChildren(p_rn->rchild());
		delete p_rn->rchild();
	}
}


//удалить все дерево
template<class T>
void RandomizeSearchTree<T>::clear()
{
	if (root)
	{
		deleteChildren(root);
		delete root;
		root = NULL;
	    win = NULL;
  	    min = NULL;
	    max = NULL;
	}
}
	

template<class T>
int RandomizeSearchTree<T>::cmp (T *a, T *b)
{
	return (*a) < (*b) ? -1 : (*a) > (*b) ? 1 : 0;
}

// изменить структуру дерева, чтобы существовал левый сын у корня
template<class T> void RandomizeSearchTree<T>::modify()
{
	RandomizeNode<T> *ch = root->rchild();
	double pri=root->m_dPriority;
	
	if (root->rchild() != NULL  &&  root->lchild() == NULL)
	{
		root->m_dPriority = ch->m_dPriority;
		ch->m_dPriority = pri;
		ch->bubbleUp(&root);
	}
}


//Вставить новый узел со случайным приоритетом в дерево
template<class T> void RandomizeSearchTree<T>::insert(T *val)
{
	insert(val, -1.0);
}


//Вставить новый узел с приоритетом в дерево
template<class T> void RandomizeSearchTree<T>::insert(T *val, double priority, bool needModify)
{
	RandomizeNode<T> *p;
	p = getRoot();
	
	if ( p == NULL) //вставка первого элемента в дерево 
	{
		if (priority == -1.0)
			win = new RandomizeNode<T>(val);
		else
			win = new RandomizeNode<T>(val, priority);
		root = win;
		min = max = root;
		root->insertInList(win);
	}
	else			   //вставка i-ого элемента в дерево
	{
		int result = 1;
		bool flag = true;

		if (priority == -1.0)
			win = new RandomizeNode<T>(val);
		else
			win = new RandomizeNode<T>(val, priority);
		while (flag)
		{
			result = cmp(val, p->val);
			if (result<0)
			{
				if (p->lchild() == NULL)
					flag = false;
				else
					p = p->lchild();
			}
			else
				if (result>0)
				{
					if (p->rchild() == NULL)
						flag = false;
					else
						p = p->rchild();
				}
				else
					return;
		}
 
		win -> p_parent = p;
		
		if (result < 0) //вставить в ЛЕВОЕ поддерево
		{
			p->p_lchild = win;
			p->prev()->insertInList(win);
		}
		else
			if (result > 0)	//вставить в ПРАВОЕ поддерево
			{
				p->p_rchild = win;
				p->insertInList(win);
			}

		win->bubbleUp(&root);
		
		result = cmp(val, min->val);
		if ( result < 0 )
			min = win;
		
		result = cmp(val, max->val);
		if ( result > 0 )
			max = win;
		if (needModify)
			modify();	//если левое поддерево пусто, то сделать его непустым
	}
}


//Удалить
template<class T> void RandomizeSearchTree<T>::remove(void)
{
	if ( win != root )
		removeRandomizeNode(win);
}



//удалить узел дерева
template<class T> void RandomizeSearchTree<T>::removeRandomizeNode(RandomizeNode<T> *n)
{
	if (n !=NULL)
	{
		if ((n->lchild() == NULL) && (n->rchild() == NULL))
		{
			RandomizeNode<T> *p = n->parent();
			if (p->lchild() == n)
				p->p_lchild = NULL;
			else
				p->p_rchild = NULL;
			n->removeNodeOfList();

			if (win == n)
				win = n->prev();

			if (n == min)
				min = n->next();
			if (n == max)
				max = n->prev();
			if (n->val)
			{	
				delete n->val;
				n->val = NULL;
			}

			if (root == n)
				root = min = max = win = NULL;
			delete n->val;
			delete n;
			return;
		}

		n->m_dPriority = -1;
		n->bubbleDown(&root);

		RandomizeNode<T> *p = n->parent();
		if (p->lchild() == n)
			p->p_lchild = NULL;
		else
			p->p_rchild = NULL;
	
		if (win == n)
			win = n->prev();

		if (n == min)
			min = n->next();
		if (n == max)
			max = n->prev();
		if (n->val)
		{	
			delete n->val;
			n->val = NULL;
		}

		n->removeNodeOfList();
		if (n)
		{
			delete n;
			n = NULL;
		}
	}
}


//найти значение узла в дереве
template<class T> RandomizeNode<T>/*T*/ *RandomizeSearchTree<T>::find_elem(T *val)
{
	int result;

	RandomizeNode<T> *n = root;
	
	while (n)
	{
		result = cmp(val, n->getVal());
		if ( result < 0 )
			n = n->lchild();
		else 
			if ( result > 0 )
				n = n->rchild();
			else
				if (result == 0)
				{
					return n;
				}
	}
	return NULL; //такого значения узла в дереве нет
}


//удалить узел, если известно его значение
template<class T> T	*RandomizeSearchTree<T>::remove(T *val)
{

	RandomizeNode<T> *p_deleted = NULL;
	
	p_deleted = find_elem (val);
	
	if (p_deleted != NULL)
		removeRandomizeNode(p_deleted);
	return NULL;
}







/*********************    Функции GET  ДЕРЕВА  *********************/

//получить следующий
template<class T> T *RandomizeSearchTree<T>::next(void)
{
   win = win -> next();
   return win->val;
}


//получить предыдущий
template<class T> T *RandomizeSearchTree<T>::prev(void)
{
   win = win -> prev();
   return win->val;
}


template<class T> T *RandomizeSearchTree<T>::roundnext(void)
{
	if(win == max)
		return min->val;
	else
		return win -> next()->val;
   
}


template<class T> T *RandomizeSearchTree<T>::roundprev(void)
{
	if(win == min)
		return max->val;
	else
		return win -> prev()->val;
}


//получить значение
template<class T> T *RandomizeSearchTree<T>::val(void)
{
   return win->val;
}


template<class T> int RandomizeSearchTree<T>::isFirst(void)
{
	return (win == root->next()) && (root!=root->next());
}


template<class T> int RandomizeSearchTree<T>::isLast(void)
{
	return (win == root->prev()) && (root!=root->next());
}


template<class T> int RandomizeSearchTree<T>::isHead(void)
{
	return (win == root);
}


template<class T> int RandomizeSearchTree<T>::isEmpty(void)
{
	return (root == root->next() );
}


template<class T> T *RandomizeSearchTree<T>::findMin(void)
{
	win = root->next();
	return win->val;
}

template<class T> RandomizeNode<T> *RandomizeSearchTree<T>::getWin()		//текущий элемнент списка
{
	return win;
}
template<class T> RandomizeNode<T> *RandomizeSearchTree<T>::getRoot()		//корень дерева
{
	return root;
}
template<class T> RandomizeNode<T> *RandomizeSearchTree<T>::getMax()		//МАКСимальный элемент дерева
{
	return max;
}
template<class T> RandomizeNode<T> *RandomizeSearchTree<T>::getMin()		//МИНимальный элемент дерева
{
	return min;
}

template<class T> void RandomizeSearchTree<T>::setWin(RandomizeNode<T> *w)		//текущий элемнент списка
{
	win = w;
}
template<class T> void RandomizeSearchTree<T>::setRoot(RandomizeNode<T> *r)		//корень дерева
{
	root = r;
}
template<class T> void RandomizeSearchTree<T>::setMax(RandomizeNode<T> *m)		//МАКСимальный элемент дерева
{
	max = m;
}
template<class T> void RandomizeSearchTree<T>::setMin(RandomizeNode<T> *m)		//МИНимальный элемент дерева
{
	min = m;
}

template<class T> void RandomizeSearchTree<T>::insertInList(RandomizeNode<T> *val)
{
	win->insertInSortList(val);
}
template<class T> void RandomizeSearchTree<T>::removeFromList(RandomizeNode<T> *val)
{
	win->removeNodeOfSortList(val);
}
template<class T> void RandomizeSearchTree<T>::replaceNodeInList(RandomizeNode<T> *val)
{
	win->replaceNodeInList(val);
}
}
Соседние файлы в папке Source