Добавил:
Studfiles2
Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз:
Предмет:
Файл:Построение выпуклой оболочки в режиме реального времени / Source / RandomizeSearchTree
.cpp#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 = ⪙
}
//опрератор преобразования типа в 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