/*File Name: UniversTools.cpp
  Author: Bernd Österholz ; Date: 12.01.2005
  System: C++


  Copyright (C) 2004  Bernd Österholz

  This program is free software; you can redistribute it and/or modify
  it under the terms of the GNU General Public License as published by
  the Free Software Foundation; either version 2, June 1991, of the License, or
  (at your option) any later version.

  This program is distributed in the hope that it will be useful,
  but WITHOUT ANY WARRANTY; without even the implied warranty of
  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  GNU General Public License for more details.

  You should have received a copy of the GNU General Public License
  along with this program; if not, write to the Free Software
  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA

 This file contains tools for the univers.
*/


#include "UniversTools.h"


list<TPoint*> UniversTools::unionPointLists(list<TPoint*> poiL1, list<TPoint*> poiL2) const
/*unions two point lists
doesn't copy univers points(copies just the pointers)
pre: the two point lists to union
post:the unioned point list*/
{
poiL1.sort(&TPoint::lower);
poiL2.sort(&TPoint::lower);
list<TPoint*> unionL;
list<TPoint*>::iterator itr2=poiL2.begin();
for (list<TPoint*>::iterator itr1=poiL1.begin();itr1!=poiL1.end();itr1++)
{
	if (itr2!=poiL2.end())
	{
		while ((*itr2)->lower((*itr2),(*itr1)))
		{//move forward on list 2 till the actual point of list 1 ist eqal or greater
			unionL.push_back(*itr2);
			itr2++;
			if (itr2==poiL2.end()){break;}
		}//now the actual point of list 1 is eqal or lower as the actual of list 2
		if (itr2!=poiL2.end()) if ((*itr1)==(*itr2)){itr2++;}//the point is in both, insert it just ones
	}
	unionL.push_back(*itr1);
}
while(itr2!=poiL2.end())
{//copy rest point of the secound list
	unionL.push_back(*itr2);
	itr2++;
}
return unionL;
}

list<TPoint*> UniversTools::intersectionPointLists(list<TPoint*> &poiL1, list<TPoint*> &poiL2) const
/*intersec two point lists
doesn't copy univers points(copies just the pointers)
pre: the two point lists to intersec
post:the interseced point list*/
{
poiL1.sort(&TPoint::lower);
poiL2.sort(&TPoint::lower);
list<TPoint*> intersecL;
list<TPoint*>::iterator itr2=poiL2.begin();
for (list<TPoint*>::iterator itr1=poiL1.begin();itr1!=poiL1.end();itr1++)
{
	while((*itr2)->lower((*itr2),(*itr1)))
	{//move forward on list 2 till the actual point of list 1 ist eqal or greater
		itr2++;
		if (itr2==poiL2.end()){return intersecL;}
	}
	//now the actual point of list 1 is eqal or lower as the actual of list 2
	if((*itr1)==(*itr2)){//the point is in both
		intersecL.push_back(*itr1);
		itr2++;
		if (itr2==poiL2.end()){return intersecL;}
	}
}
return intersecL;
}

bool UniversTools::intersectionPointListsIsEmpty(list<TPoint*>* poiL1,list<TPoint*>* poiL2) const
/*checks if the intersection of the two point lists is empty
pre: the two point to check the intersection of
post:true if the intersection would be empty, else false*/
{
poiL1->sort(&TPoint::lower);
poiL2->sort(&TPoint::lower);
list<TPoint*>::iterator itr2=poiL2->begin();
for (list<TPoint*>::iterator itr1=poiL1->begin();itr1!=poiL1->end();itr1++)
{
	while((*itr2)->lower((*itr2),(*itr1)))
	{//move forward on list 2 till the actual point of list 1 ist eqal or greater
		itr2++;
		if (itr2==poiL2->end()){return true;}
	}
	//now the actual point of list 1 is eqal or lower as the actual of list 2
	if((*itr1)==(*itr2)){return false;}//the point is in both
}
return true;
}

list<TPoint*> UniversTools::getPointsNotInPointLists(list<TPoint*> &poiL1, list<TPoint*> &poiL2) const
/*get the points of the point list poiL1 that are not in the point list poiL2
doesn't copy univers points(copies just the pointers)
pre: the two point lists
post:the point list of points that are in poiL1 but not in poiL2*/
{
poiL1.sort(&TPoint::lower);
poiL2.sort(&TPoint::lower);
list<TPoint*> intersecNL;
list<TPoint*>::iterator itr2=poiL2.begin();
for (list<TPoint*>::iterator itr1=poiL1.begin();itr1!=poiL1.end();itr1++)
{
	if (itr2!=poiL2.end())
	{
		while((*itr2)->lower((*itr2),(*itr1)))
		{//move forward on list 2 till the actual point of list 1 ist eqal or greater
			itr2++;
			if (itr2==poiL2.end()){break;}
		}
	}
	//now the actual point of list 1 is eqal or lower as the actual of list 2
	if((*itr1)!=(*itr2))//the point is in poiL1 but not in poiL2
		{intersecNL.push_back(*itr1);}
}
return intersecNL;
}

bool UniversTools::printUniverseStructur(ostream* ostream, list<TPoint*> &struc) const
/*prints the values of the given univers structur to the given output
stream, if it exists
pre: the outputstream ostream to print the univers to and the univers
	structur struc to print
post: if the stream exists true and the given structur univers in the stream
	ostream in a readebel form(integer numbers seperated by ",",";" and "."),
	false else*/
{
if(ostream==NULL){return false;}
struc.sort(&TPoint::lower);
//convert and output the univers to a output form
(*ostream)<<(unsigned long)struc.size()<<"."<<endl;
for (list<TPoint*>::iterator itr=struc.begin();itr!=struc.end();itr++)
{
	(*ostream)<<(*itr)->name<<";";
	for (list<TPoint*>::iterator itr1=(*itr)->pPoint.begin();itr1!=(*itr)->pPoint.end();itr1++)
		{(*ostream)<<","<<(*itr1)->name;}
	(*ostream)<<";";
	for (list<TPoint*>::iterator itr1=(*itr)->nPoint.begin();itr1!=(*itr)->nPoint.end();itr1++)
		{(*ostream)<<","<<(*itr1)->name;}
	(*ostream)<<"."<<endl;
}
return true;
}

list<TPoint*> UniversTools::findPoints(list<unsigned long> &listOfPointNames)
/*find the points with the names of the numbers in the given list and
return a list of pointers to them(doesn't copy the points), if they
exists
pre: a list of integer names of the points to find
post: a pionter list to the points found*/
{
list<TPoint*> founded;
if (univers.empty()){return founded;}
//with sorted list the finding will become linear
listOfPointNames.sort();
univers.sort(&TPoint::lower);
list<TPoint*>::iterator uItr=univers.begin();
for(list<unsigned long>::iterator itr=listOfPointNames.begin();itr!=listOfPointNames.end();itr++)
{
	//move up in uItr and itr till both are equal
	while((((*uItr)->name)<(*itr))&&(uItr!=univers.end())){uItr++;}
	if (uItr==univers.end()){break;}
	while((((*uItr)->name)>(*itr))&&(itr!=listOfPointNames.end())){itr++;}
	if (itr==listOfPointNames.end()){break;}
	if (((*uItr)->name)==(*itr))//if names are equal insert point
		{founded.push_back(*uItr);}
}
return founded;
}

list<TPoint*> UniversTools::getNeigbours(TPoint* orgin, const unsigned int dist)
/*get all neigbours in the univers of the point orgin till the distantce dist
doesn't copy univers points(copies just the pointers)
negativ and positiv distances are treated equal
pre: the original orgin point to get the neibours from and the distance till
	wich to get the neibours
post: a list of pointers to the neibours till distance dist of the orgin point*/
{
list<TPoint*> neibours;
list<TPoint*> neibi;//neibours with distance i
list<TPoint*> neibni;//neibours with distance i+1
neibours.push_back(orgin);
neibi.push_back(orgin);
if(tmpValue>=+4294967000U){nullTMPValues();}
tmpValue++;
orgin->tmpValue=tmpValue;
for(unsigned int i=0;i<dist;i++)
{
	for (list<TPoint*>::iterator itr=neibi.begin();itr!=neibi.end();itr++)
	{//for all conections to the Point transfer conected points to the part
		for (list<TPoint*>::iterator itr1=(*itr)->pPoint.begin();itr1!=(*itr)->pPoint.end();itr1++)
		{
			if((*itr1)->tmpValue!=tmpValue)
			{//if the Point is not in the neigbour list, insert it ain neigbours and next neigbours
				(*itr1)->tmpValue=tmpValue;
				neibours.push_back(*itr1);
				neibni.push_back(*itr1);
			}
		}
		for (list<TPoint*>::iterator itr1=(*itr)->nPoint.begin();itr1!=(*itr)->nPoint.end();itr1++)
		{//get right point
			if((*itr1)->tmpValue!=tmpValue)
			{//if the Point is not in the neigbour list, insert it ain neigbours and next neigbours
				(*itr1)->tmpValue=tmpValue;
				neibours.push_back(*itr1);
				neibni.push_back(*itr1);
			}
		}
	}
	neibi=neibni;
	neibni.clear();
}
return neibours;
}

list<TPoint*> UniversTools::getMinNeigbours(TPoint* orgin, const unsigned int dist)
/*get all neigbours in the univers of the point orgin with the minimum
distantce dist to the point; doesn't copy univers points(copies just the
pointers); negativ and positiv distances are treated equal;
pre: the original orgin point to get the neibours from and the distance till
	wich to get the neibours
post: a list of pointers to the neibours with the distance dist to the orgin point*/
{
list<TPoint*> neibours;
list<TPoint*> neibi;//neibours with distance i
list<TPoint*> neibni;//neibours with distance i+1
neibours.push_back(orgin);
neibi.push_back(orgin);
if(tmpValue>=+4294967000U){nullTMPValues();}
tmpValue++;
for(unsigned int i=0;i<dist;i++)
{
	for (list<TPoint*>::iterator itr=neibi.begin();itr!=neibi.end();itr++)
	{//for all conections to the Point transfer conected points to the part
		for (list<TPoint*>::iterator itr1=(*itr)->pPoint.begin();itr1!=(*itr)->pPoint.end();itr1++)
		{
			if((*itr1)->tmpValue!=tmpValue)
			{//if the Point is not in the neigbour list, insert it ain neigbours and next neigbours
				(*itr1)->tmpValue=tmpValue;
				neibours.push_back(*itr1);
				neibni.push_back(*itr1);
			}
		}
		for (list<TPoint*>::iterator itr1=(*itr)->nPoint.begin();itr1!=(*itr)->nPoint.end();itr1++)
		{//get right point
			if((*itr1)->tmpValue!=tmpValue)
			{//if the Point is not in the neigbour list, insert it ain neigbours and next neigbours
				(*itr1)->tmpValue=tmpValue;
				neibours.push_back(*itr1);
				neibni.push_back(*itr1);
			}
		}
	}
	neibi=neibni;
	neibni.clear();
}
return neibi;
}

long UniversTools::getDistance(TPoint* poi1, TPoint* poi2)
/*gets the minimal distance (number af negativ and positiv distnaces betwean) betwean
two Points in the univers; the points are given as iterators of the univers
; negativ and positiv distances are treated equal; if the distance is -1
the points are not conected
pre: two iterators of the univers to two points in the univers
post: the minimal distance of the points*/
{
if(poi1==poi2) {return 0;}
list<TPoint*>* neib_tmp;//temporal list pointer
//actual neibors
list<TPoint*>* neib_ac=new list<TPoint*>;//neibours with distance i; border at distance i
list<TPoint*>* neib_ac_n=new list<TPoint*>;//new neibours at distance i+1
//neibours of the other point
neib_ac->push_back(poi1);
list<TPoint*>::iterator itr;
list<TPoint*>::iterator itr1;
if(tmpValue>=+4294967000U){nullTMPValues();}
tmpValue++;
for(unsigned long distance=1;;distance++)
{
	for (itr=neib_ac->begin();itr!=neib_ac->end();itr++)
	{//for all conections to the Point transfer conected points to the part
		for (itr1=(*itr)->pPoint.begin();itr1!=(*itr)->pPoint.end();itr1++)
		{
			if((*itr1)->tmpValue!=tmpValue)//not in new i+1
			{//if the Point is not in the neigbour lists, insert it in next neigbours
				if((*itr1)==poi2){
					delete neib_ac;delete neib_ac_n;
					return distance;
				}
				(*itr1)->tmpValue=tmpValue;
				neib_ac_n->push_back(*itr1);
			}
		}
		for (itr1=(*itr)->nPoint.begin();itr1!=(*itr)->nPoint.end();itr1++)
		{//get right point
			if((*itr1)->tmpValue!=tmpValue)//not in new i+1
			{//if the Point is not in the neigbour lists, insert it in next neigbours
				if((*itr1)==poi2){
					delete neib_ac;delete neib_ac_n;
					return distance;
				}
				(*itr1)->tmpValue=tmpValue;
				neib_ac_n->push_back(*itr1);
			}
		}
	}
	if (neib_ac_n->empty()){//if the neibours don't grow anymore stop
		delete neib_ac;delete neib_ac_n;
		return -1;
	}
	neib_tmp=neib_ac;
	neib_ac=neib_ac_n;
	neib_ac_n=neib_tmp;
	neib_ac_n->clear();
}
delete neib_ac;delete neib_ac_n;
return -1; //??numeric_limits<unsigned long>::infinity();
}


list<pair<TPoint*,long> > UniversTools::getDistanceToPoints(TPoint* poi1, list<TPoint*> &points)
/*gets the minimal distance(number af negativ and positiv distnaces betwean) betwean
the Point and the points of the point list in the univers;
the point is given as iterator of the univers and the the points as a
iteratorlist of iterators of the univers
; negativ and positiv distances are treated equal
pre: a iterator and a itorator list of the univers for the points in the
	univers
post: the minimal distance of the points as a list of pairs of points and
	distances, if the distance is -1 the points are not conected*/
{
list<pair<TPoint*,long> > result;
if((points.empty())) {return result;}
list<pair<TPoint*,long> >::iterator itrR;
list<TPoint*>::iterator itr;
list<TPoint*>::iterator itr1;
pair<TPoint*,long> tmpP;//temporal pair
unsigned int founded=0;//how much points have been founded
list<TPoint*> inters;//temporal list
for (itr=points.begin();itr!=points.end();itr++){//initialisize result
	tmpP.first=(*itr);
	tmpP.second=-1;
	result.push_back(tmpP);
}
list<TPoint*>* neib_ac=new list<TPoint*>;//neibours with distance i; border at distance i
neib_ac->push_back(poi1);
if(!intersectionPointListsIsEmpty(neib_ac,&points))
{//find the points wit 0 distance
	inters=intersectionPointLists((*neib_ac),points);
	founded+=inters.size();
	for (itr=inters.begin();itr!=inters.end();itr++){
		tmpP.first=(*itr);
		tmpP.second=-1;
		itrR=find(result.begin(),result.end(),tmpP);
		itrR->second=0;
	}
}
if (founded==result.size()){return result;}//if no more point should be founded
list<TPoint*>* neib_ac_n=new list<TPoint*>;//new neibours at distance i+1
list<TPoint*>* neib_tmp;//new neibours at distance i+1
if(tmpValue>=+4294967000U){nullTMPValues();}
tmpValue++;
for(unsigned long distance=1;;distance++)
{
	for (itr=neib_ac->begin();itr!=neib_ac->end();itr++)
	{//for all conections to the Point transfer conected points to the part
		for (itr1=(*itr)->pPoint.begin();itr1!=(*itr)->pPoint.end();itr1++)
		{
			if((*itr1)->tmpValue!=tmpValue)//not in new i+1
			{//if the Point is not in the neigbour lists, insert it in next neigbours
				(*itr1)->tmpValue=tmpValue;
				neib_ac_n->push_back(*itr1);
			}
		}
		for (itr1=(*itr)->nPoint.begin();itr1!=(*itr)->nPoint.end();itr1++)
		{//get right point
			if((*itr1)->tmpValue!=tmpValue)//not in new i+1
			{//if the Point is not in the neigbour lists, insert it in next neigbours
				(*itr1)->tmpValue=tmpValue;
				neib_ac_n->push_back(*itr1);
			}
		}
	}
	if(!intersectionPointListsIsEmpty(neib_ac_n,&points))
	{//find the points wit the actual distance
		inters=intersectionPointLists((*neib_ac_n),points);
		founded+=inters.size();
		for (itr=inters.begin();itr!=inters.end();itr++){
			tmpP.first=(*itr);
			tmpP.second=-1;
			itrR=find(result.begin(),result.end(),tmpP);
			itrR->second=distance;
		}
	}
	if (founded>=result.size()){//if no more point should be founded
		delete neib_ac;delete neib_ac_n;
		return result;
	}
	neib_tmp=neib_ac;
	neib_ac=neib_ac_n;
	neib_ac_n=neib_tmp;
	neib_ac_n->clear();
}
delete neib_ac;delete neib_ac_n;
return result; //??numeric_limits<unsigned long>::infinity();

}




unsigned int UniversTools::getUniversPartSize(TPoint* orgin)
/*get the size of the Part univers in wich the Point orgin is to the point orgin,
	this means the greatest minimal distance to a point in the part univers
pre: the original orgin point to get the univers size to
post: the greatest minimal distance a point has to the given orgin point*/
{
list<TPoint*>* neib_tmp;//tomporal list pointer
//actual neibors
list<TPoint*>* neib_ac=new list<TPoint*>;//neibours with distance i; border at distance i
list<TPoint*>* neib_ac_n=new list<TPoint*>;//new neibours at distance i+1
neib_ac->push_back(orgin);
list<TPoint*>::iterator itr;
list<TPoint*>::iterator itr1;
if(tmpValue>=+4294967000U){nullTMPValues();}
tmpValue++;
for(unsigned long distance=0;;distance++)
{//i=distance-1
	for (itr=neib_ac->begin();itr!=neib_ac->end();itr++)
	{//for all conections to the Point transfer conected points to the part
		for (itr1=(*itr)->pPoint.begin();itr1!=(*itr)->pPoint.end();itr1++)
		{
			if((*itr1)->tmpValue!=tmpValue)//not in new i+1
			{//if the Point is not in the neigbour lists, insert it in next neigbours
				(*itr1)->tmpValue=tmpValue;
				neib_ac_n->push_back(*itr1);
			}
		}
		for (itr1=(*itr)->nPoint.begin();itr1!=(*itr)->nPoint.end();itr1++)
		{//get right point
			if((*itr1)->tmpValue!=tmpValue)//not in new i+1
			{//if the Point is not in the neigbour lists, insert it in next neigbours
				(*itr1)->tmpValue=tmpValue;
				neib_ac_n->push_back(*itr1);
			}
		}
	}
	if (neib_ac_n->empty()){//if the neibours don't grow anymore stop
		delete neib_ac;delete neib_ac_n;
		return distance;
	}
	neib_tmp=neib_ac;
	neib_ac=neib_ac_n;
	neib_ac_n=neib_tmp;
	neib_ac_n->clear();
}
delete neib_ac;delete neib_ac_n;
return 0;
}

list<TPoint*> UniversTools::getSurface(list<TPoint*> &poiL) const
/*gets the surface; the points of the given point list poiL that have
neigbours not in the point list poiL
doesn't copy univers points(copies just the pointers)
pre: point list of wich to find the surface
post: the surface of the given point list poiL*/
{
list<TPoint*> surface;
poiL.sort(&TPoint::lower);
unsigned long minName=0;
for (list<TPoint*>::iterator itr=poiL.begin();itr!=poiL.end();itr++)
{
	for (list<TPoint*>::iterator itr1=(*itr)->pPoint.begin();itr1!=(*itr)->pPoint.end();itr1++)
	{
		if((find(poiL.begin(),poiL.end(),(*itr1))==poiL.end())&&((*itr)->name>minName))
		{//if the itr Point is not in the point list poiL ore the surface
			surface.push_back(*itr);
			minName=(*itr)->name;
			break;
		}
	}
	if(minName!=(*itr)->name){
		for (list<TPoint*>::iterator itr1=(*itr)->nPoint.begin();itr1!=(*itr)->nPoint.end();itr1++)
		{//get right point
			if((find(poiL.begin(),poiL.end(),(*itr1))==poiL.end()))
			{//if the itr Point is not in the point list poiL ore the surface
				surface.push_back(*itr);
				break;
			}
		}
	}
}
return surface;
}



list<TPoint*> UniversTools::makeGrid(TPoint* sPoi, const unsigned int dist, const unsigned int number)
/*makes a grid of number nodes(if possible else less) with the startpoint
sPoi and the minimum distance of dist betwean the points in this univers
the grid is in its distances betwean the points not optimal(minimal)
; negativ and positiv distances are treated equal
pre: the startpoint sPoi for the grid as a pointer to a point of this
	univers, the number of points the grid should have and the minimum
	distance dist betwean them
post: the points of the grid*/
{
/*The points in the actual grid build a area(room) with a surface.
All new grid points are in that surface.*/
list<TPoint*> inters,surface,area,grid;
//generates the secound point
inters=getMinNeigbours(sPoi,dist);
grid.push_back(sPoi);
grid.push_back(*(inters.begin()));
list<TPoint*>::iterator acP=grid.begin();
area=unionPointLists(getNeigbours(sPoi,dist),getNeigbours((*(inters.begin())),dist));
surface=getSurface(area);
//generate rest points
while ((grid.size()<number)&&(!surface.empty())&&(acP!=grid.end()))
{
	inters=getMinNeigbours((*acP),dist);
	inters=intersectionPointLists(inters,surface);
	if(inters.empty()){//go to the next grid point, if no new points ca be found for the actual point
		acP++;
	}else{
		grid.push_back(*(inters.begin()));
		area=unionPointLists(area,getNeigbours(*(inters.begin()),dist));
		surface=getSurface(area);
	}
}
return grid;
}

unsigned long UniversTools::getNumberOfPosDistances(list<TPoint*> &area)
/*returns the number of the positv distances betwean the points in the
given area of this univers
pre: the area to evalue the positiv distances of
post:  the number of positiv distances betwean the points of the area*/
{
unsigned long pDistances=0;
if(tmpValue>=+4294967000U){nullTMPValues();}
tmpValue++;
for (list<TPoint*>::iterator itr=area.begin();itr!=area.end();itr++)
	{(*itr)->tmpValue=tmpValue;}
for (list<TPoint*>::iterator itr=area.begin();itr!=area.end();itr++)
{
	for (list<TPoint*>::iterator itr1=(*itr)->pPoint.begin();itr1!=(*itr)->pPoint.end();itr1++)
	{//for every neibour that is in the area add a distance
		if ((*itr)->tmpValue==tmpValue)
			{pDistances++;}
	}
}
return pDistances/2;//distances are counted double
}

unsigned long UniversTools::getNumberOfNegDistances(list<TPoint*> &area)
/*returns the number of the negativ distances betwean the points in the
given area of this univers
pre: the area to evalue the negativ distances of
post: the number of negativ distances betwean the points of the area*/
{
unsigned long nDistances=0;
if(tmpValue>=+4294967000U){nullTMPValues();}
tmpValue++;
for (list<TPoint*>::iterator itr=area.begin();itr!=area.end();itr++)
	{(*itr)->tmpValue=tmpValue;}
for (list<TPoint*>::iterator itr=area.begin();itr!=area.end();itr++)
{
	for (list<TPoint*>::iterator itr1=(*itr)->nPoint.begin();itr1!=(*itr)->nPoint.end();itr1++)
	{//for every neibour that is in the area add a distance
		if((*itr)->tmpValue==tmpValue)
			{nDistances++;}
	}
}
return nDistances/2;//distances are counted double
}













