Диаметр множества / src / DiameterCont

/********************************************************************************************
	File:    DiameterCont.h

	Program: Диаметр множества									Compiler: MSVS 6.0
	Version: 1.04(29.04.2003)									Started : 29.04.2003

	Author : Antipina Svetlana     / Антипина Светлана
             Lushenkov Vassiliy    / Лушенков Василий
			 Skorodumov Ivan	   / Скородумов Иван

	Содержание:
	~~~~~~~~~~
	•_TDiameterCont   | Класс диаметра множества
	
*********************************************************************************************/

#ifndef _DiameterCont_H
#define _DiameterCont_H
#include <math.h>

//STL
#include <list>
#include <iterator>
#include <algorithm>
#include <xmemory>
#include <memory>
#include <iostream.h>
#include <fstream.h>

#include "Node.h"

namespace DiameterProject{

	namespace DiameterError{

		class ECommonDiameterError{
		public:
			const char* p;
			ECommonDiameterError(const char* q) {p=q;}
		};

		class EInvalidNodeID : public ECommonDiameterError 
		{
		public:
			EInvalidNodeID(const char* q) : ECommonDiameterError(q) {};
		};
		class EInvalidNodeXY : public ECommonDiameterError 
		{
		public:
			EInvalidNodeXY(const char* q) : ECommonDiameterError(q) {};
		};
		class EInvalidInsert : public ECommonDiameterError 
		{
		public:
			EInvalidInsert(const char* q) : ECommonDiameterError(q) {};
		};
		class EInvalidDelete : public ECommonDiameterError 
		{
		public:
			EInvalidDelete(const char* q) : ECommonDiameterError(q) {};
		};
		class EInvalidCH : public ECommonDiameterError 
		{
		public:
			EInvalidCH(const char* q) : ECommonDiameterError(q) {};
		};

	}


template<class T> class DiameterAlloc : public std::allocator<T>
{
public:
    typedef T* pointer;
    typedef T value_type;
	typedef T& reference;
	typedef size_t size_type;
	typedef ptrdiff_t difference_type;
	typedef const T* const_pointer;
	typedef const T& const_reference;

	void construct(pointer p, value_type s)
	{
		*p=s;
//		AfxMessageBox("Element Created");
	}

	void destroy(pointer p)
	{
		if (p!=0) p->~pointer();
//		AfxMessageBox("Element Deleted");
	}

};

template <
		  class T,
		  class A = DiameterAlloc<T>,
		  class Cont = std::list<T,A>,
		  class Iter = Cont::iterator
		 >
class DiameterIterator : public std::iterator_traits<Iter>
{

public:
	Iter curr;
	Cont* c;

	bool operator !=(DiameterIterator &citer){return curr != citer.curr;}

	bool operator ==(DiameterIterator &citer){return curr == citer.curr;}

	DiameterIterator(Cont& x,Iter p):c(&x), curr(p) {}

	T& operator* () const
		{return *curr;}

	T* operator-> () const
		{return &*curr;}

	DiameterIterator& operator ++() //++ptr
	{
		++curr;
		return *this;
	}

	DiameterIterator& operator ++(int) //ptr++
	{
		DiameterIterator tmp = *this;
		++curr;
		return tmp;
	}

	DiameterIterator& operator --() //--ptr
	{
		--curr;
		return *this;
	}

	DiameterIterator& operator --(int) //ptr--
	{
		DiameterIterator tmp = *this;
		--curr;
		return tmp;
	}
};


template <class T, class A = DiameterAlloc<T>, class C = std::list<T,A> > 
class TDiameterCont : public C
{
	public:
		typedef DiameterIterator<T> iterator;

		TDiameterCont(): C() {}

		bool empty()  {return C::empty();}

		long size() {return C::size();}

		iterator begin() 
			{return iterator(*this,C::begin());}

		iterator end() 
			{return iterator(*this,C::end());}


		// Возвращает первую вершину, имеющую заданный ID
		T GetByID(const int ID) throw (DiameterError::EInvalidNodeID)
		{
			iterator p = begin();
			while(p != end())
			{   
				if ((*p)->GetID() == ID) return (*p);
				++p;
			}
			throw DiameterError::EInvalidNodeID("Неправильно задан идентификатор!");
		}

		// Возвращает первую вершину, лежащую в е-окрестности заданной точки
		T GetByXY(const int x, const int y, const double e) throw (DiameterError::EInvalidNodeXY)
		{
			// Написать по аналогии с GetByID
			iterator p = begin();
			while(p != end())
			{   
				int x1=(*p)->GetXCoord();
				int y1=(*p)->GetYCoord();
				if ((fabs(x-x1)<=e)&&(fabs(y-y1)<=e)) return (*p);
				++p;
			}
			throw DiameterError::EInvalidNodeXY("Неправильно заданы координаты!");
			//return 0;
		}

		void Insert(const T&  value ) throw (DiameterError::EInvalidInsert)
		{
			try{
				UnMakeCH();
				push_front(value);
		  		return;
			}catch(...)
			{
				throw DiameterError::EInvalidInsert("Ошибка при добавлении вершины!");
			}
		}

		void DeleteByID(const int ID) throw (DiameterError::EInvalidDelete)
		{
			try{
				UnMakeCH();
				iterator p = begin();
				while (p != end())
				{
					if ((*p)->GetID() == ID)
					{
						T tmp=(*p);
						erase(p.curr);
						delete (tmp);
						break;
					}
					++p;
				}
			}catch(...)
			{
				throw DiameterError::EInvalidDelete("Ошибка при удалении вершины!");
			}
		}

		void ClearDiameterCont() throw (DiameterError::EInvalidDelete)
		{
			try{
				UnMakeCH();
				iterator p = begin();
				while (p != end())
				{
					T tmp=(*p);
					iterator p1=p;
					++p;
					erase(p1.curr);
					if (tmp!=0) delete (tmp);
				}
			}catch(...)
			{
				throw DiameterError::EInvalidDelete("Ошибка при очистке контейнера!");
			}
		}

		float GetDistance (const T p1, const T p2)
		{
			float x=(p1->GetXCoord())-(p2->GetXCoord());
			float y=(p1->GetYCoord())-(p2->GetYCoord());
			x=x*x;y=y*y;
			return (sqrt(x+y));
		}

		void ScaleAll(const float xScale, const float yScale)
		{
			iterator p = begin();
			float tmp=0;
			while (p != end())
			{
				tmp=(*p)->GetXCoord()*xScale;//if (tmp>xMax) tmp=xMax;
				(*p)->SetXCoord(tmp);
				tmp=(*p)->GetYCoord()*yScale;//if (tmp>yMax) tmp=yMax;
				(*p)->SetYCoord(tmp);
				++p;
			}
		}

		~TDiameterCont(){ClearDiameterCont();}

		void UnMakeCH()
		{
			iterator p = begin();
			while (p != end())
			{
				(*p)->SetRight(0);(*p)->SetLeft(0);
				++p;
			}
		}

		void MakeCH() throw (DiameterError::EInvalidCH) //построение выпуклой оболочки
		{
			try{
				UnMakeCH();
				//Джарвис
				if (C::size()>2)
				{
					T MinPoint=0;
					T MaxPoint=0;
					iterator p = begin();
					MinPoint=(*p);MaxPoint=(*p);
					++p;
					while (p != end())
					{
						if ((*p)->GetYCoord() < MinPoint->GetYCoord())
						{
							MinPoint=(*p);
						}else if ((*p)->GetYCoord() == MinPoint->GetYCoord())
						{
							if ((*p)->GetXCoord() < MinPoint->GetXCoord())
							{
								MinPoint=(*p);
							}
						}
						if ((*p)->GetYCoord() > MaxPoint->GetYCoord())
						{
							MaxPoint=(*p);
						}else if ((*p)->GetYCoord() == MaxPoint->GetYCoord())
						{
							if ((*p)->GetXCoord() > MaxPoint->GetXCoord())
							{
								MaxPoint=(*p);
							}
						}
						++p;
					}//end of while
					// from minimun to maximum
					T iTempPoint1=0;
					T iTempPoint2=0;
					iTempPoint1=MinPoint;
					
					p=begin();
					iterator t=begin();
					iterator t1=begin();++t1;
					float n1,n2;
					while(iTempPoint1!=MaxPoint) {
						// init point 2
						if(iTempPoint1!=(*t)) 
							iTempPoint2=(*t);
						else
							iTempPoint2=(*t1);
						// look for second point
						for(p=begin();p!=end();++p) {
							if((*p)!=iTempPoint1) {
								n1 = (iTempPoint2->GetXCoord()-iTempPoint1->GetXCoord())*((*p)->GetYCoord()-iTempPoint1->GetYCoord());
								n2 = ((*p)->GetXCoord()-iTempPoint1->GetXCoord())*(iTempPoint2->GetYCoord()-iTempPoint1->GetYCoord());
								if(n1>n2)
									iTempPoint2=(*p);
							}

						}
						// set line from 1 to 2
						iTempPoint1->SetRight(iTempPoint2);
						iTempPoint2->SetLeft(iTempPoint1);
						// set p1 to p2
						iTempPoint1=iTempPoint2;
					}//end of while
					// from maximum to minimun
					while(iTempPoint1!=MinPoint) {
						// init point 2
						if(iTempPoint1!=(*t)) 
							iTempPoint2=(*t);
						else
							iTempPoint2=(*t1);
						//  look for second point
						for(p=begin();p!=end();++p) {
							if((*p)!=iTempPoint1) {
								n1 = (iTempPoint2->GetXCoord()-iTempPoint1->GetXCoord())*((*p)->GetYCoord()-iTempPoint1->GetYCoord());
								n2 = ((*p)->GetXCoord()-iTempPoint1->GetXCoord())*(iTempPoint2->GetYCoord()-iTempPoint1->GetYCoord());
								if(n1>n2)
									iTempPoint2=(*p);
							}

						}
						// set line from 1 to 2
						iTempPoint1->SetRight(iTempPoint2);
						iTempPoint2->SetLeft(iTempPoint1);
						// set p1 to p2
						iTempPoint1=iTempPoint2;
					}//end of while
					
				}
			}catch(...)
			{
				throw DiameterError::EInvalidCH("Ошибка при поиске выпуклой оболочки!");
			}
		}

};

template <class T>
  std::ostream& operator << (std::ostream& os,TDiameterCont<T>& aNet)
{
	TDiameterCont<T>::iterator p = aNet.begin();
    while (p != aNet.end())
    {
		os<<"[Node]\n";
		//os<<"   ID       = " << (*p)->GetID() <<"\n";
		os<<"   X        = " << (*p)->GetXCoord() <<"\n";
		os<<"   Y        = " << (*p)->GetYCoord() <<"\n";
		os<<"   Name     = " << (*p)->GetName() <<"\n";
        ++p;
    }
	return os;
}

template <class T>
  std::istream& operator >> (std::istream& is,TDiameterCont<T>& aNet)
{
	boolean IsReadP = false;
	int EqPos=0;
	CString cline;
	std::string tmp;
	CString LeftPart;
	CString RightPart;
	T Node;

	while ((is) && (cline != "end"))
	{
		std::getline(is,tmp);
		cline = tmp.c_str();
		
		cline.TrimLeft();
		cline.TrimRight();

		if (cline == "[Node]")
		{
			IsReadP = true;
			Node = new(TNode);
			aNet.Insert(Node);			
		}
		else
		{
			EqPos = cline.Find('=');
			LeftPart = cline.Left(EqPos);
			RightPart = cline.Right(cline.GetLength()-EqPos-1);
			LeftPart.TrimLeft();
			LeftPart.TrimRight();
			RightPart.TrimLeft();
			RightPart.TrimRight();
			if (LeftPart == "X")
			{
				Node->SetXCoord(atof(RightPart));
			}
			if (LeftPart == "Y")
			{
				Node->SetYCoord(atof(RightPart));
			}
			if (LeftPart == "ID")
			{
				//Node->SetID(atoi(RightPart));
			}
			if (LeftPart == "Name")
			{
				Node->SetName(RightPart);
			}
		}
	}
	return is;
}


};//namespace
#endif