Алгоритм Киркпатрика-Зайделя / Source / Q_T

#if !defined(Q_T_H)
#define Q_T_H

#include <stdio.h>
template <class T> class QUEUE
{
public:
struct El_Q
{
 const T *p;
 El_Q * next;
 El_Q * prev;
};
struct Tag
{
 El_Q *first;
 El_Q *last;
 El_Q *cur;
};

Tag* Q;
unsigned int c_el;
public:
//==================================
QUEUE(void)
{ c_el=0;
	Q= new Tag;
	if (Q==NULL)
	{ printf("ERROR! Not Enough memory\n");
//		getch();
		exit(1);
	 }

	Q->first=NULL;
	Q->last=NULL;
	Q->cur=NULL;	
}
//==================================
int IsEmpty(void)
{
	if ((Q->first==NULL)&&(Q->last==NULL))
	 { return 1;}
	else
	 { return 0;}
}
//==================================
int IsEnd(void)
{
	if (Q->cur==NULL)
	 { return 1;}
	else
	 { return 0;}
}
//==================================
int Push(const T* el)
{
	El_Q * E;
	E= new El_Q;
	if (E==NULL)
	{
		printf("QUEUE<T> Push:ERROR! Not Enough memory\n");
		return 1;
	}
	E->p=el;
	E->next=NULL;
	E->prev=NULL;

	if (IsEmpty())
	{
		 Q->first=E;
		 Q->cur=E;
	}
	else
	{
		(Q->last)->next=E;
		E->prev=Q->last;
	}
	Q->last=E;
	c_el+=1;
	return 0;
}

//==================================
int Push_to_Beg( T* el)
{
	El_Q * E;
	E= new El_Q;
	if (E==NULL)
	{
		printf("ERROR! Not Enough memory\n");
		return 1;
	}

	E->p=el;
	E->next=NULL;
	E->prev=NULL;
	if (IsEmpty())
	{
		 Q->cur=E;
		 Q->last=E;
	}
	else
	{
		E->next=Q->first;
		(Q->first)->prev=E;
	}
	Q->first=E;
	c_el+=1;
	return 0;
}

//==================================
T* Pop()
{
	const T *r;
	El_Q * E;
	if (!IsEmpty())
	{
	 E=Q->first;

	 if (Q->cur==Q->first)
	 { Q->cur=E->next;}
	 Q->first=E->next;
	 

	 r=E->p;
	 delete E;
	 if (Q->first==NULL)
		 { Q->last=NULL;
			 Q->cur=NULL;
		 }
	 else 
		{(Q->first)->prev=NULL;}
	 c_el-=1;
	 return (T*)r;
	}
	else
	 return NULL;
}
//==================================
const T* Pop_End()
{
	const T *r;
	El_Q * E;
	if (!IsEmpty())
	{
		E=Q->last;
		if (c_el==1)
		 { r=Pop();}
		else
		 { (Q->last)=E->prev;
			 (Q->last)->next=NULL;
			 r=E->p;
			 delete E;
		 }
		c_el-=1;
		return r;
	 }
	else
	 return NULL;
}

//==================================
const T* Go_Next()
{ const T* r=NULL;

	if (Q->cur!=NULL)
	 {
		 r=(Q->cur)->p;
		 Q->cur=(Q->cur)->next;
	 }
	return r;
}
//==================================
const T* Read()
{ const T* r=NULL;
	if (Q->cur!=NULL)
	 {
		 r=(Q->cur)->p;
	 }
	return r;
}
//==================================
void Go_Beg()
{
	Q->cur=Q->first;
}
//==================================
void Go_End()
{
	Q->cur=Q->last;
}
//==================================
void Clear(void)
{
	while (!IsEmpty())
	{
		Pop();
	}
}
//==================================
void Destroy(void)
{
	Clear();
	delete Q;
}
//==================================
int Count()
{return c_el;}
//==================================
int Array_to_Q(T* Ar,unsigned int n)
{ int i=0;
  for(i=0;i<n;i++)
    {
      Push(&Ar[i]);
    }
  return 0;
}
//==================================
~QUEUE()
{ Destroy();}
//==================================
};
#endif