Построение выпуклой оболочки в режиме реального времени / Source / RandomizeNode

#include "stdafx.h"
#include <stdlib.h>
#include <stdio.h>
#include "TPoint.h"
#include <time.h>
#include <limits.h>

namespace RandomTree
{

template<class T> class RandomizeSearchTree;


/** Шаблон - узел рандомизированного дерева */

template<class T>
class RandomizeNode
{

	typedef RandomizeNode<T> t_Node;

private:
	RandomizeNode *p_parent;	//указатель на родителя

	RandomizeNode *p_lchild;	//указатель на левое поддерево
	RandomizeNode *p_rchild;	//  		   правое

	RandomizeNode *p_next;	//указатель на левое поддерево
	RandomizeNode *p_prev;	//  		   правое
	
	T *val;						//значение узла
	double m_dPriority;			//приоритет узла
	
	void rotateRight(void);		//правый поворот узла
	void rotateLeft(void);		//левый поворот узла

public:

	RandomizeNode(T *v, double k);
	RandomizeNode(T *v);
	RandomizeNode();
	~RandomizeNode();
	
    RandomizeNode *lchild(void);
	RandomizeNode *rchild(void);
	T *getVal();
	void setVal(T* ttt)
	{	val=ttt;}
	RandomizeNode *next(void);
	RandomizeNode *prev(void);

	RandomizeNode *parent(void);	//получить указатель на РОДИТЕЛЯ

	RandomizeNode *minimum(void);	//получить мин. элемент		

	void bubbleUp(RandomizeNode<T>** koren);		//поднять узел вверх
	void bubbleDown(RandomizeNode<T>** koren);      //опустить узел вниз
	double priority(void);			//получить ПРИОРИТЕТ
   
	RandomizeNode<T> *insertInList(RandomizeNode<T> *b);
	void insertInSortList(RandomizeNode<T> *b);
	RandomizeNode<T> *removeNodeOfList(void);
	void removeNodeOfSortList(RandomizeNode<T> *b);
	void replaceNodeInList(RandomizeNode<T> *b);


    friend class RandomizeSearchTree<T>;
};

//конструктор
template<class T>
RandomizeNode<T>::RandomizeNode(T *v, double priority/*int seed*/)
{
	m_dPriority = priority;//(rand()%32767) / 32767.0;
	val = new T(*v);
	p_lchild = p_rchild = p_parent = NULL;
	p_next = this;
	p_prev = this;
}

template<class T>
RandomizeNode<T>::RandomizeNode(T *v)
{
//	CTime t;	
//	srand((unsigned)t.GetTime());
//	srand((unsigned)time(NULL) );
//	double t1 = (rand()%32767)/(32767.0);
//	srand (clock());
//	double t2 = (rand()%32767)/(32767.0);
//	if (t1 > (1 - t2))
//		m_dPriority = (t1 + t2) - 1;
//	else 
//		m_dPriority = t1 + t2;//(double) rand()/((double) RAND_MAX+1.0);//(rand()%RAND_MAX+1) / RAND_MAX;//(double(rand())/RAND_MAX);
	m_dPriority = (rand()%32767)/(32767.0);
	val = new T(*v);
	p_lchild = p_rchild = p_parent = NULL;
	p_next = this;
	p_prev = this;
}

template<class T>
RandomizeNode<T>::RandomizeNode()
{
	m_dPriority = 0.0;
	val = NULL;
	p_lchild = p_rchild = p_parent = NULL;
	p_next = NULL;
	p_prev = NULL;
}

template<class T> RandomizeNode<T>::~RandomizeNode()
{
	p_lchild = p_rchild = p_parent = NULL;
}

template<class T> T *RandomizeNode<T>::getVal(void)
{
	return val;
}


//правый поворот узла
template<class T> void RandomizeNode<T>::rotateRight(void)
{
	RandomizeNode<T> *y, *x, *p;

	y = this;
	x = y->lchild();
	p = y->parent();

    y->p_lchild = x->rchild();

	if (y->lchild() != NULL)
		y->lchild()->p_parent = y;
	if (p != NULL)
	{
		if (p->rchild() == y)
			p->p_rchild = x;
		else
			p->p_lchild = x;
	}
	x->p_parent = p;
	x->p_rchild = y;
	y->p_parent = x;
	
}


//левый поворот узла
template<class T> void RandomizeNode<T>::rotateLeft(void)
{
	RandomizeNode<T> *x, *y, *p;
	
	x = this;
	y = x -> rchild();
	p = x -> parent();

	x->p_rchild = y->lchild();

	if (x->rchild() != NULL)
		x->rchild()->p_parent = x;
	if (p != NULL)
	{
		if (p->lchild() == x)
			p->p_lchild = y;
		else
			if (p->p_rchild == x)
			p->p_rchild = y;
	}
	y->p_parent = p;
	y->p_lchild = x;
	x->p_parent = y;

}


//поднять узел
template<class T>  void RandomizeNode<T>::bubbleUp(RandomizeNode<T>** koren)
{
	RandomizeNode<T> *p, *cur;
	
	cur = this;
	p = parent();
	
	if (p != NULL)
	{
		if (priority() > p->priority())
		{
			if (p->lchild() == this)
			{
				if (cur == *koren)
					*koren = p->lchild(); 
				p->rotateRight();
			}
			else
			{
				if (cur == *koren)
					*koren = p->rchild();
				p->rotateLeft();
			}
			bubbleUp(koren);
		}
	}
	else
		if (p == NULL)
			*koren = cur;
}


template<class T> void RandomizeNode<T>::bubbleDown(RandomizeNode<T>** koren)
{
	if ((lchild() == NULL) && (rchild() != NULL))
	{
		if (*koren == this)
			*koren = rchild();
		this->rotateLeft();
	}
	else
	if ((rchild() == NULL) && (lchild() != NULL))
	{
		if (*koren == this)
			*koren = lchild();
		this->rotateRight();
	}
	else
	if ((rchild() != NULL) && (lchild() != NULL))
	{
		if (lchild()->priority() < rchild()->priority())
		{
			if (*koren == this)
				*koren = rchild();
			this->rotateLeft();
		}
		else
		{
			if (*koren == this)
				*koren = lchild();
			this->rotateRight();
		}
	}
	if ((lchild() != NULL) || (rchild() != NULL))
	{	
		bubbleDown(koren);
	}
}





/*********************    Функции GET  УЗЛА  *********************/



template<class T> RandomizeNode<T> *RandomizeNode<T>::rchild(void)
{
	return p_rchild;
}


template<class T> RandomizeNode<T> *RandomizeNode<T>::lchild(void)
{
	return p_lchild;
}


template<class T> RandomizeNode<T> *RandomizeNode<T>::next(void)
{
	return p_next;
}


template<class T> RandomizeNode<T> *RandomizeNode<T>::prev(void)
{
	return p_prev;
}


template<class T> RandomizeNode<T> *RandomizeNode<T>::parent(void)
{
	return p_parent;
}


template<class T> double RandomizeNode<T>::priority(void)
{
	return m_dPriority;
}


template<class T> RandomizeNode<T> *RandomizeNode<T>::minimum(void)
{
	RandomizeNode<T> *m=this;
	if (m)
	{
		while (m->lchild())
		{
			m=m->lchild();
		}
	}
	return m;
}

template<class T> RandomizeNode<T> *RandomizeNode<T>::insertInList(RandomizeNode<T> *b)
{
	RandomizeNode<T> *c = p_next;
	b->p_next = c;
	b->p_prev = this;
	p_next = b;
	c->p_prev = b;

	return b;
}

template<class T> void RandomizeNode<T>::insertInSortList(RandomizeNode<T> *b)
{
	RandomizeNode<T> *c = minimum();
	if (c->getVal() > b->getVal())
	{
		b->p_next = c;
		b->p_prev = c->p_prev;
		c->p_prev = b;
	}
	else
	{
		while (b->getVal() > c->getVal())
		{
			if ( c->getVal() != minimum()->getVal())
				break;
			c = c->p_next;
		}
		b->p_next = c;
		b->p_prev = c->p_prev;
		c->p_prev = b;
	}
}

template<class T> RandomizeNode<T> *RandomizeNode<T>::removeNodeOfList(void)
{
	p_prev->p_next = p_next;
	p_next->p_prev = p_prev;
	p_next = p_prev = this;
	
	return this;
}


template<class T> void RandomizeNode<T>::removeNodeOfSortList(RandomizeNode<T> *b)
{
	RandomizeNode<T> *c = minimum();
	while (c->getVal() != b->getVal())
		c = c->p_next;
	c->removeNodeOfList();
}

template<class T> void RandomizeNode<T>::replaceNodeInList(RandomizeNode<T> *b)
{
	RandomizeNode<T> *c = minimum();
	RandomizeNode<T> *min = minimum();
	do
	{
		c = c->p_next;
		if ((*min->getVal()) > (*c->getVal()))
			min = c;
	} while (c != minimum());
	c = min;
	while ((*c->getVal()) < (*b->getVal()))
		c = c->p_next;
	RandomizeNode<T> *tmp = b;
	b->p_prev->p_next = b->p_next;
	b->p_prev = c->p_prev;
	b->p_next = c;
	c->p_prev->p_next = b;
	c->p_prev = b;
}

}