/**
 * @class cUniversTools
 * file name: cUniversTools.cpp
 * @author Betti Oesterholz
 * @date 12.01.2005
 * @mail webmaster@bernd-oesterholz.name
 *
 * System: C++
 *
 * This class represents a basic univers.
 * Copyright (C) @c GPL3 2008  Betti Oesterholz
 *
 * 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 3 of the License, or
 * 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, see <http://www.gnu.org/licenses/>.
 *
 */
/*
History:
22.12.2007  Oesterholz  bugfix: in unionPointLists() an if poiL2.empty() had blockt the for loop
23.12.2007  Oesterholz  Test in intersectionPointLists, intersectionPointListsIsEmpty and 
			   getPointsNotInPointLists agains names of the points and not ther pointer
30.12.2007  Oesterholz  in intersectionPointListsIsEmpty() reference parameters insted of pointers are given
*/


#include "algorithm"
#include "cUniversTools.h"


/**
 * unions of two point lists
 * doesn't copy univers points (copies just the pointers)
 * @param liPoints1 the first point list to union
 * @param liPoints2 the secound point list to union
 * @return the unioned point list, a list which includes the points of 
 *		both input lists liPoints1 and liPoints2
 */
list<cPoint*> cUniversTools::unionPointLists (list<cPoint*> liPoints1,
	list<cPoint*> liPoints2 ) const{
	
	liPoints1.sort(&cPoint::lower);
	liPoints2.sort(&cPoint::lower);
	list<cPoint*> unionL;
	list<cPoint*>::iterator itr2=liPoints2.begin();
	
	if ( liPoints2.empty() ){
	
		return liPoints1;
	}
	if ( liPoints1.empty() ){
	
		return liPoints2;
	}
	for ( list<cPoint*>::iterator itr1=liPoints1.begin() ;
			itr1!=liPoints1.end() ; itr1++){
			
		if ( itr2!=liPoints2.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==liPoints2.end() ){
					break;
				}
			}
			//now the actual point of list 1 is eqal or lower as the actual of list 2
			if ( itr2!=liPoints2.end() ){
				if ( ((*itr1)->name)==((*itr2)->name) ){
					itr2++;//the point is in both, insert it just ones
				}
			}
		}
		unionL.push_back( *itr1 );
	}
	//copy remaining points of the secound list
	while( itr2!=liPoints2.end() ){
		unionL.push_back( *itr2 );
		itr2++;
	}
	return unionL;
}

/**
 * intersec two point lists
 * doesn't copy univers points (copies just the pointers)
 * @param liPoints1 the first point list to intersec
 * @param liPoints2 the secound point list to intersec
 * @return the interseced point list, a list which includes just the
 *		points of which are in both input lists liPoints1 and liPoints2
 */
list<cPoint*> cUniversTools::intersectionPointLists (list<cPoint*> &liPoints1,
		list<cPoint*> &liPoints2 ) const{
	
	list<cPoint*> intersecL;
	if ( liPoints1.empty() || liPoints2.empty() ){
		/*intersection is empty*/
		return intersecL;
	}
	liPoints1.sort( &cPoint::lower );
	liPoints2.sort( &cPoint::lower );
	list<cPoint*>::iterator itr2=liPoints2.begin();
	for ( list<cPoint*>::iterator itr1=liPoints1.begin() ;
			itr1!=liPoints1.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==liPoints2.end() ){
				return intersecL;
			}
		}
		//now the actual point of list 1 is eqal or lower as the actual of list 2
		if( (*itr1)->name==(*itr2)->name ){//the point is in both
			intersecL.push_back( *itr1 );
			itr2++;
			if ( itr2==liPoints2.end() ){
				return intersecL;
			}
		}
	}
	return intersecL;
}

/**
 * checks if the intersection of two point lists is empty
 * @param liPoints1 the first point list to intersec
 * @param liPoints2 the secound point list to intersec
 * @return true if the intersection of the input lists liPoints1 and 
 *		liPoints2 would be empty, else false
 */
bool cUniversTools::intersectionPointListsIsEmpty( list<cPoint*> &liPoints1,
		list<cPoint*> &liPoints2 ) const{
	
	if ( liPoints1.empty() || liPoints2.empty() ){
		/*intersection is empty*/
		return true;
	}
	liPoints1.sort( &cPoint::lower );
	liPoints2.sort( &cPoint::lower );
	list<cPoint*>::iterator itr2=liPoints2.begin();
	for ( list<cPoint*>::iterator itr1=liPoints1.begin() ;
			itr1!=liPoints1.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==liPoints2.end() ){
				return true;
			}
		}
		//now the actual point of list 1 is eqal or lower as the actual of list 2
		if( (*itr1)->name==(*itr2)->name ){
			return false;//the point is in both -> intersection not empty
		}
	}
	return true;
}

/**
 * get the points of the point list liPoints1 that are not in the point 
 * list liPoints2
 * doesn't copy univers points (copies just the pointers)
 * @param liPoints1 the first point list to get the points from
 * @param liPoints2 the secound point list of points not to return
 * @return the list of the points which are in the list liPoints1 but not
 *		in the list liPoints2
 */
list<cPoint*> cUniversTools::getPointsNotInPointLists( 
		list<cPoint*> &liPoints1, list<cPoint*> &liPoints2 ) const{
		
	liPoints1.sort( &cPoint::lower );
	liPoints2.sort( &cPoint::lower );
	list<cPoint*> intersecNL;
	list<cPoint*>::iterator itr2=liPoints2.begin();
	
	for ( list<cPoint*>::iterator itr1=liPoints1.begin() ; itr1!=liPoints1.end() ; itr1++ ){
		
		while( (itr2!=liPoints2.end()) && ((*itr2)->lower( (*itr2), (*itr1) )) ){
			//move forward on list 2 till the actual point of list 1 ist eqal or greater
			itr2++;
			if ( itr2==liPoints2.end() ){
				break;//no more points to exclude
			}
		}

		//now the actual point of liPoints1 is eqal or lower as the actual of liPoints2
		if( (itr2==liPoints2.end()) || ((*itr1)->name!=(*itr2)->name) ){
			//insert the remaining points which are in liPoints1 but not in liPoints2
			intersecNL.push_back( *itr1 );
		}
		
	}
	return intersecNL;
}

/**
 * prints the values of the given univers structur to the given output
 * stream, if it exists
 * @param ostream the outputstream to print the univers to
 * @param universStructur the univers structur to print
 * @return 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
 */
bool cUniversTools::printUniverseStructur(ostream* ostream, list<cPoint*> &universStructur) const{
	if( ostream==NULL ){
		return false;
	}
	universStructur.sort( &cPoint::lower );
	
	//convert and output the univers to a output form
	(*ostream)<<(unsigned long)universStructur.size()<<"."<<endl;
	for ( list<cPoint*>::iterator itr=universStructur.begin() ; itr!=universStructur.end() ; itr++){
		(*ostream)<<(*itr)->name<<";";
		for ( list<cPoint*>::iterator itr1=(*itr)->pPoint.begin() ;
				itr1!=(*itr)->pPoint.end() ; itr1++){
					(*ostream)<<","<<(*itr1)->name;
			}
		(*ostream)<<";";
		for ( list<cPoint*>::iterator itr1=(*itr)->nPoint.begin() ;
				itr1!=(*itr)->nPoint.end() ; itr1++ ){
			(*ostream)<<","<<(*itr1)->name;
		}
		(*ostream)<<"."<<endl;
	}
	return true;
}

/**
 * find the points in the univers with the names of the numbers in the
 * given list and return the list of pointers to them (doesn't copy the
 * points), if they exists
 * @param listOfPointNames a list of integer names of the points to find
 * @return a list of pionters to the points found
 */
list<cPoint*> cUniversTools::findPoints( list<unsigned long> &listOfPointNames ){
	list<cPoint*> founded;
	if ( univers.empty() ){
		return founded;//nothing to find
	}
	//with sorted list the finding will become linear
	listOfPointNames.sort();
	univers.sort( &cPoint::lower );
	list<cPoint*>::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++;//skip wrong ponts in univers
		}
		if ( uItr==univers.end() ){
			break;//all points of univers checked
		}
		while( (((*uItr)->name) > (*itr) ) && ( itr!=listOfPointNames.end()) ){
			itr++;//skip points of the given list not in the univers
		}
		if ( itr==listOfPointNames.end() ){
			break;// all points of given list checked
		}
		if ( ((*uItr)->name)==(*itr) ){
			//if names are equal (->point found) insert point
			founded.push_back( *uItr );
		}
	}
	return founded;
}

/**
 * get all neigbours in the univers of the point orgin till the distantce;
 * doesn't copy univers points (copies just the pointers);
 * negativ and positiv distances are treated equal
 * @param orgin the original point to get the neibours from
 * @param distance the distance till wich to get the neibours
 * @return a list of pointers to the neibours till distance distance of the
 *		orgin point
 */
list<cPoint*> cUniversTools::getNeigbours( cPoint* orgin, const unsigned int distance ){
	list<cPoint*> neibours;
	list<cPoint*> neibi;//neibours with distance i
	list<cPoint*> 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<distance ; i++ ){
		for ( list<cPoint*>::iterator itr=neibi.begin() ; itr!=neibi.end() ; itr++ ){
			//for all conections to the Point transfer conected points to the part
			for ( list<cPoint*>::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 in neigbours and next neigbours
					(*itr1)->tmpValue=tmpValue;
					neibours.push_back( *itr1 );
					neibni.push_back( *itr1 );
				}
			}
			for ( list<cPoint*>::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;
}

/**
 * get all neigbours in the univers of the point orgin with the minimum
 * distantce to the point;
 * doesn't copy univers points(copies just the pointers);
 * negativ and positiv distances are treated equal;
 * @param orgin the original point to get the neibours from 
 * @param distance the distance till wich to get the neibours
 * @return a list of pointers to the neibours with the distance to the orgin point
 */
list<cPoint*> cUniversTools::getMinNeigbours( cPoint* orgin, const unsigned int distance ){
	list<cPoint*> neibours;
	list<cPoint*> neibi;//neibours with distance i
	list<cPoint*> 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<distance ; i++ ){
		for ( list<cPoint*>::iterator itr=neibi.begin() ; itr!=neibi.end() ; itr++ ){
			//for all conections to the Point transfer conected points to the part
			for ( list<cPoint*>::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<cPoint*>::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;
}

/**
 * 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 connected
 * @param pPoint1 a iterator of the univers to a point in the univers
 * @param pPoint2 a iterator of the univers to a point in the univers
 * @return the minimal (number of) distance betwean pPoint1 and pPoint2
 */
long cUniversTools::getDistance(cPoint* pPoint1, cPoint* pPoint2)
{
	if( pPoint1==pPoint2 ){
		return 0;//the points are the same point -> distance 0
	}
	
	list<cPoint*>* neib_tmp;//temporal list pointer
	//actual neibors
	list<cPoint*>* neib_ac=new list<cPoint*>;//neibours with distance i; border at distance i
	list<cPoint*>* neib_ac_n=new list<cPoint*>;//new neibours at distance i+1
	//neibours of the other point
	neib_ac->push_back( pPoint1 );
	list<cPoint*>::iterator itr;
	list<cPoint*>::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 ){
					/*if the Point is not in the neigbour lists, insert it in 
					next neigbours*/
					if( (*itr1)==pPoint2 ){
						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){
					/*if the Point is not in the neigbour lists, insert it in 
					next neigbours*/
					if( (*itr1)==pPoint2 ){
						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; //better??: numeric_limits<unsigned long>::infinity();
}


/**
 * This method gets the minimal distance in the univers (number af negativ
 * and positiv distnaces betwean) betwean the given point poi1 and the 
 * given points.
 * The point poi1 is given as iterator of the univers and the points as
 * a iteratorlist of iterators of the univers.
 * Negativ and positiv distances are treated equal.
 *
 * @param poi1 the iterator to the destination point
 * @param points a itoratorlist of the points in the univers to which the
 * 	minimal distance should be evalued
 * @return the minimal distance of the points of the list as a list of
 * 	pairs of points and distances, if a distance is -1 the point is not
 * 	conected to the destination point
 */
list<pair<cPoint*,long> > cUniversTools::getDistanceToPoints(cPoint* poi1,
		list<cPoint*> &points){
	list< pair<cPoint*,long> > result;
	if( points.empty()) {
		return result;// no points to evalue the distance to
	}
	
	list< pair<cPoint*,long> >::iterator itrR;
	list<cPoint*>::iterator itr;
	list<cPoint*>::iterator itr1;
	pair<cPoint*,long> tmpP;//temporal pair
	unsigned int founded=0;//how much points have been founded
	list<cPoint*> inters;//temporal list
	
	//initialisize result
	for ( itr=points.begin() ; itr!=points.end() ; itr++ ){
		tmpP.first=(*itr);
		tmpP.second=-1;
		result.push_back( tmpP );
	}
	
	list<cPoint*>* neib_ac=new list<cPoint*>;//neibours with distance i; border at distance i
	neib_ac->push_back( poi1 );
	if( !intersectionPointListsIsEmpty( *neib_ac, points ) ){
		//find the points with 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() ){
		//all points found -> no more point should be founded
		return result;
	}
	list<cPoint*>* neib_ac_n=new list<cPoint*>;//new neibours at distance i+1
	list<cPoint*>* 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 with 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() ){
			//all points found -> no more point should be founded
			break;
		}
		if( neib_ac_n->empty() ){
			//the whool part of the univers has been searched -> nothing more can be found
			break;
		}
		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 cUniversTools::getUniversPartSize(cPoint* 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<cPoint*>* neib_tmp;//tomporal list pointer
//actual neibors
list<cPoint*>* neib_ac=new list<cPoint*>;//neibours with distance i; border at distance i
list<cPoint*>* neib_ac_n=new list<cPoint*>;//new neibours at distance i+1
neib_ac->push_back(orgin);
list<cPoint*>::iterator itr;
list<cPoint*>::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<cPoint*> cUniversTools::getSurface(list<cPoint*> &poiL)
/*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<cPoint*> surface;
unsigned long minName=0;
poiL.sort(&cPoint::lower);
/*mark the points of the area poiL, so it is easier to check wich points are in the area poiL*/
if ( tmpValue>=+4294967000U ) {nullTMPValues();}
tmpValue++;
for ( list<cPoint*>::iterator itr=poiL.begin() ; itr!=poiL.end() ; itr++ )
	{(*itr)->tmpValue=tmpValue;}
/*get the surface*/
for ( list<cPoint*>::iterator itr=poiL.begin() ; itr!=poiL.end() ; itr++ )
{/*check for every point if it's in the surface of poiL, means if it has a neibour outside that is not in poiL*/
	for ( list<cPoint*>::iterator itr1=(*itr)->pPoint.begin() ; itr1!=(*itr)->pPoint.end() ; itr1++ )
	{
		if ( (*itr1)->tmpValue != tmpValue )
		{//if the itr1 Point is not in the point list poiL or the surface( because the surface is part of poiL)
			surface.push_back(*itr);
			minName=(*itr)->name;
			break;
		}
	}
	if ( minName != (*itr)->name ){/*if the point is not added to the surface allready*/
		for ( list<cPoint*>::iterator itr1=(*itr)->nPoint.begin() ; itr1 != (*itr)->nPoint.end() ; itr1++ )
		{//get right point
			if( (*itr1)->tmpValue != tmpValue )
			{//if the itr1 Point is not in the point list poiL or the surface( because the surface is part of poiL)
				surface.push_back(*itr);
				break;
			}
		}
	}
}
return surface;
}



list<cPoint*> cUniversTools::makeGrid(cPoint* 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<cPoint*> inters , surface , area , grid;
if(outComent)
	{cout<<"grid size : "<<flush;}
grid.push_back(sPoi);
//generates the secound point
inters=getMinNeigbours(sPoi,dist);

if(inters.empty())
{//no more points to add to the grid
	return grid;
}

grid.push_back(*(inters.begin()));
list<cPoint*>::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()) )
{
	if(outComent)
		{cout<<grid.size()<<"; "<<flush;}
	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);
	}
}
if(outComent)
	{cout<<endl;}
return grid;
}

unsigned long cUniversTools::getNumberOfPosDistances(list<cPoint*> &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<cPoint*>::iterator itr=area.begin();itr!=area.end();itr++)
	{(*itr)->tmpValue=tmpValue;}
for (list<cPoint*>::iterator itr=area.begin();itr!=area.end();itr++)
{
	for (list<cPoint*>::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 cUniversTools::getNumberOfNegDistances(list<cPoint*> &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<cPoint*>::iterator itr=area.begin();itr!=area.end();itr++)
	{(*itr)->tmpValue=tmpValue;}
for (list<cPoint*>::iterator itr=area.begin();itr!=area.end();itr++)
{
	for (list<cPoint*>::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
}













