Added KDE3 version of ktechlab

git-svn-id: svn://anonsvn.kde.org/home/kde/branches/trinity/applications/ktechlab@1095338 283d02a7-25f6-0310-bc7c-ecb5cbfe19da

1 files changed, 537 insertions, 0 deletions

diff --git a/src/conrouter.cpp b/src/conrouter.cpp
new file mode 100644
index 0000000..2c2d6da
--- /dev/null
+++ b/src/conrouter.cpp
@@ -0,0 +1,537 @@
+/***************************************************************************
+ *   Copyright (C) 2003-2004 by David Saxton                               *
+ *   david@bluehaze.org                                                    *
+ *                                                                         *
+ *   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 of the License, or     *
+ *   (at your option) any later version.                                   *
+ ***************************************************************************/
+
+#include "conrouter.h"
+#include "icndocument.h"
+
+#include <kdebug.h>
+
+#include <assert.h>
+#include <cmath>
+
+inline static int toCanvas( int pos )
+{
+	return pos*8+4;
+}
+inline static int fromCanvas( int pos )
+{
+	return (pos-4)/8;
+}
+
+inline static QPoint toCanvas( const QPoint * const pos )
+{
+	return QPoint( toCanvas(pos->x()), toCanvas(pos->y()) );
+}
+inline static QPoint fromCanvas( const QPoint * const pos )
+{
+	return QPoint( fromCanvas(pos->x()), fromCanvas(pos->y()) );
+}
+
+inline static QPoint toCanvas( const QPoint &pos )
+{
+	return QPoint( toCanvas(pos.x()), toCanvas(pos.y()) );
+}
+inline static QPoint fromCanvas( const QPoint &pos )
+{
+	return QPoint( fromCanvas(pos.x()), fromCanvas(pos.y()) );
+}
+
+static inline int roundDouble( const double x )
+{
+	return int(std::floor(x+0.5));
+}
+
+ConRouter::ConRouter( ICNDocument *cv )
+{
+	p_icnDocument = cv;
+	m_lcx = m_lcy = 0;
+}
+
+
+ConRouter::~ConRouter()
+{
+}
+
+
+QPointList ConRouter::pointList( bool reverse ) const
+{
+	QPointList pointList;
+	
+	if (reverse)
+	{
+		bool notDone = m_cellPointList.size() > 0;
+		for ( QPointList::const_iterator it = m_cellPointList.fromLast(); notDone; --it )
+		{
+			pointList.append( toCanvas(&*it) );
+			if ( it == m_cellPointList.begin() ) notDone = false;
+		}
+	}
+	else
+	{
+		const QPointList::const_iterator end = m_cellPointList.end();
+		for ( QPointList::const_iterator it = m_cellPointList.begin(); it != end; ++it )
+		{
+			pointList.append( toCanvas(&*it) );
+		}
+	}
+	
+	return pointList;
+}
+
+
+static double qpoint_distance( const QPoint & p1, const QPoint & p2 )
+{
+	double dx = p1.x() - p2.x();
+	double dy = p1.y() - p2.y();
+	
+	return std::sqrt( dx*dx + dy*dy );
+}
+
+
+QPointListList ConRouter::splitPoints( const QPoint &pos ) const
+{
+	const QPoint split = fromCanvas(&pos);
+	
+	QValueList<QPointList> list;
+	
+	// Check that the point is in the connector points, and not at the start or end
+	bool found = false;
+	QPointList::const_iterator end = m_cellPointList.end();
+	
+	double dl[] = { 0.0, 1.1, 1.5 }; // sqrt(2) < 1.5 < sqrt(5)
+	for ( unsigned i = 0; (i < 3) && !found; ++i )
+	{
+		for ( QPointList::const_iterator it = m_cellPointList.begin(); it != end && !found; ++it )
+		{
+			if ( qpoint_distance( *it, split ) <= dl[i] && it != m_cellPointList.begin() && it != m_cellPointList.fromLast() )
+				found = true;
+		}
+	}
+	
+	QPointList first;
+	QPointList second;
+	
+	if (!found)
+	{
+		kdWarning() << "ConRouter::splitConnectorPoints: Could not find point ("<<pos.x()<<", "<<pos.y()<<") in connector points"<<endl;
+		kdWarning() << "ConRouter::splitConnectorPoints: Returning generic list"<<endl;
+		
+		first.append( toCanvas(m_cellPointList.first()) );
+		first.append(pos);
+		second.append(pos);
+		second.append( toCanvas(m_cellPointList.last()) );
+		
+		list.append(first);
+		list.append(second);
+		
+		return list;
+	}
+	
+	// Now add the points to the two lists
+	bool gotToSplit = false;
+	for ( QPointList::const_iterator it = m_cellPointList.begin(); it != end; ++it )
+	{
+		QPoint canvasPoint = toCanvas(&*it);
+		if ( *it == split )
+		{
+			gotToSplit = true;
+			first.append(canvasPoint);
+			second.prepend(canvasPoint);
+		}
+		else if (!gotToSplit)
+		{
+			first.append(canvasPoint);
+		}
+		else /*if (gotToSplit)*/
+		{
+			second.append(canvasPoint);
+		}
+	}
+	
+	list.append(first);
+	list.append(second);
+	
+	return list;
+}
+
+
+QPointListList ConRouter::dividePoints( uint n ) const
+{
+	// Divide the points up into n pieces...
+	
+	QPointList points = m_cellPointList;
+	assert( n != 0 );
+	if ( points.size() == 0 ) {
+		points += QPoint( toCanvas(m_lcx), toCanvas(m_lcy) );
+	}
+	
+	const float avgLength = float(points.size()-1)/float(n);
+	
+	QPointListList pll;
+	for ( uint i=0; i<n; ++i )
+	{
+		QPointList pl;
+		// Get the points between (pos) and (pos+avgLength)
+		const int endPos = roundDouble( avgLength*(i+1) );
+		const int startPos = roundDouble( avgLength*i );
+		const QPointList::iterator end = ++points.at(endPos);
+		for ( QPointList::iterator it = points.at(startPos); it != end; ++it )
+		{
+			pl += toCanvas(*it);
+		}
+		pll += pl;
+	}
+	return pll;
+}
+
+
+void ConRouter::checkACell( int x, int y, Cell *prev, int prevX, int prevY, int nextScore )
+{
+	if ( !p_icnDocument->isValidCellReference(x,y) ) return;
+	Cell * const c = &(*cellsPtr)[x][y];
+	if ( c->permanent ) return;
+	int newScore = nextScore + c->CIpenalty + c->Cpenalty;
+	
+	// Check for changing direction
+	if		( x != prevX && prev->prevX == prevX ) newScore += 5;
+	else if ( y != prevY && prev->prevY == prevY ) newScore += 5;
+	
+	if ( c->bestScore < newScore ) return;
+	
+	// We only want to change the previous cell if the score is different,
+	// or the score is the same but this cell allows the connector
+	// to travel in the same direction
+	
+	if ( c->bestScore == newScore &&
+		 x != prevX &&
+		 y != prevY ) return;
+	
+	c->bestScore = newScore;
+	c->prevX = prevX;
+	c->prevY = prevY;
+	
+	if ( !c->addedToLabels )
+	{
+		c->addedToLabels = true;
+		Point point;
+		point.x = x;
+		point.y = y;
+		point.prevX = prevX;
+		point.prevY = prevY;
+		TempLabelMap::iterator it = tempLabels.insert( std::make_pair(newScore,point) );
+		c->point = &it->second;
+	}
+	else
+	{
+		c->point->prevX = prevX;
+		c->point->prevY = prevY;
+	}
+}
+
+void ConRouter::checkCell( int x, int y )
+{
+	Cell * const c = &(*cellsPtr)[x][y];
+	
+	c->permanent = true;
+	const int nextScore = c->bestScore+1;
+	
+	// Check the surrounding cells (up, left, right, down)
+	if ( y > 0 )		checkACell( x, y-1, c, x, y, nextScore );
+	if ( x > 0 )		checkACell( x-1, y, c, x, y, nextScore );
+	if ( x+1 < xcells ) checkACell( x+1, y, c, x, y, nextScore );
+	if ( y+1 < ycells ) checkACell( x, y+1, c, x, y, nextScore );
+}
+
+
+bool ConRouter::needsRouting( int sx, int sy, int ex, int ey ) const
+{
+	if ( m_cellPointList.size() < 2 )
+	{
+		// Better be on the safe side...
+		return true;
+	}
+	
+	const int scx = fromCanvas(sx);
+	const int scy = fromCanvas(sy);
+	const int ecx = fromCanvas(ex);
+	const int ecy = fromCanvas(ey);
+	
+	const int psx = m_cellPointList.first().x();
+	const int psy = m_cellPointList.first().y();
+	const int pex = m_cellPointList.last().x();
+	const int pey = m_cellPointList.last().y();
+	
+	return (psx != scx || psy != scy || pex != ecx || pey != ecy ) &&
+		   (pex != scx || pey != scy || psx != ecx || psy != ecy );
+}
+
+
+void ConRouter::setRoutePoints( const QPointList &pointList )
+{
+	m_cellPointList = pointList;
+	removeDuplicatePoints();
+}
+
+
+void ConRouter::setPoints( const QPointList &pointList, bool reverse  )
+{
+	if (  pointList.size() == 0 )
+		return;
+	
+	QPointList cellPointList;
+	
+	QPoint prevCellPoint = fromCanvas(*pointList.begin());
+	cellPointList.append(prevCellPoint);
+	const QPointList::const_iterator end = pointList.end();
+	for ( QPointList::const_iterator it = pointList.begin(); it != end; ++it )
+	{
+		QPoint cellPoint = fromCanvas(*it);
+		
+		while ( prevCellPoint != cellPoint )
+		{
+			cellPointList.append(prevCellPoint);
+			
+			if		( prevCellPoint.x() < cellPoint.x() ) prevCellPoint.setX( prevCellPoint.x()+1 );
+			else if ( prevCellPoint.x() > cellPoint.x() ) prevCellPoint.setX( prevCellPoint.x()-1 );
+			if		( prevCellPoint.y() < cellPoint.y() ) prevCellPoint.setY( prevCellPoint.y()+1 );
+			else if ( prevCellPoint.y() > cellPoint.y() ) prevCellPoint.setY( prevCellPoint.y()-1 );
+		};
+		
+		prevCellPoint = cellPoint;
+	}
+	cellPointList.append(prevCellPoint);
+	
+	if (reverse)
+	{
+		m_cellPointList.clear();
+		const QPointList::iterator begin = cellPointList.begin();
+		for ( QPointList::iterator it = cellPointList.fromLast(); it != begin; --it )
+		{
+			m_cellPointList += *it;
+		}
+		m_cellPointList += *begin;
+	}
+	else {
+		m_cellPointList = cellPointList;
+	}
+	
+	removeDuplicatePoints();
+}
+
+
+void ConRouter::translateRoute( int dx, int dy )
+{
+	if ( dx == 0 && dy == 0 ) {
+		return;
+	}
+	
+	m_lcx += dx;
+	m_lcy += dy;
+	
+// 	const QPoint ds = QPoint( fromCanvas(dx), fromCanvas(dy) );
+	const QPoint ds = QPoint( dx/8, dy/8 );
+	
+	QPointList::iterator end = m_cellPointList.end();
+	for ( QPointList::iterator it = m_cellPointList.begin(); it != end; ++it )
+	{
+		(*it) += ds;
+	}
+	
+	removeDuplicatePoints();
+}
+
+
+void ConRouter::mapRoute( int sx, int sy, int ex, int ey )
+{
+	const int scx = fromCanvas(sx);
+	const int scy = fromCanvas(sy);
+	const int ecx = fromCanvas(ex);
+	const int ecy = fromCanvas(ey);
+	
+	if ( !p_icnDocument->isValidCellReference( scx, scy ) ||
+		 !p_icnDocument->isValidCellReference( ecx, ecy ) )
+	{
+		return;
+	}
+	
+	m_cellPointList.clear();
+	m_lcx = ecx;
+	m_lcy = ecy;
+	
+	
+	// First, lets try some common connector routes (which will not necesssarily
+	// be shortest, but they will be neat, and cut down on overall CPU usage)
+	// If that fails, we will resort to a shortest-route algorithm to find an
+	// appropriate route.
+	
+	// Connector configuration: Line
+	{
+		bool ok = checkLineRoute( scx, scy, ecx, ecy, 4*ICNDocument::hs_connector, 0 );
+		if (ok) {
+			return;
+		} else {
+			m_cellPointList.clear();
+		}
+	}
+	
+	// Corner 1
+	{
+		bool ok = checkLineRoute( scx, scy, ecx, ecy, 2*ICNDocument::hs_connector, 0 );
+		if (!ok) {
+			m_cellPointList.clear();
+		} else {
+			ok = checkLineRoute( scx, scy, ecx, ecy, ICNDocument::hs_connector-1, 0 );
+			if (ok) {
+				return;
+			} else {
+				m_cellPointList.clear();
+			}
+		}
+	}
+	
+	// Corner 2
+	{
+		bool ok = checkLineRoute( scx, scy, ecx, ecy, 2*ICNDocument::hs_connector, 0 );
+		if (!ok) {
+			m_cellPointList.clear();
+		} else {
+			ok = checkLineRoute( scx, scy, ecx, ecy, ICNDocument::hs_connector-1, 0 );
+			if (ok) {
+				return;
+			} else {
+				m_cellPointList.clear();
+			}
+		}
+	}
+	
+	// It seems we must resort to brute-force route-checking
+	{	
+		cellsPtr = p_icnDocument->cells();
+		cellsPtr->reset();
+	
+		xcells = p_icnDocument->canvas()->width()/8;
+		ycells = p_icnDocument->canvas()->height()/8;
+	
+		// Now to map out the shortest routes to the cells
+		Cell * const startCell = &(*cellsPtr)[ecx][ecy];
+		startCell->permanent = true;
+		startCell->bestScore = 0;
+		startCell->prevX = -1;
+		startCell->prevY = -1;
+		
+		tempLabels.clear();
+		checkCell( ecx, ecy );
+		
+		// Daniel: I changed it from a do while to a while otherwise
+		// in rare cases the iterator can end up as end().
+		while ( tempLabels.size() > 0 && !(*cellsPtr)[scx][scy].permanent )
+		{
+			TempLabelMap::iterator it = tempLabels.begin();
+			checkCell( it->second.x, it->second.y );
+			tempLabels.erase(it);
+		}
+		
+		// Now, retrace the shortest route from the endcell to get out points :)
+		int x = scx, y = scy;
+		bool ok = true;
+		do
+		{
+			m_cellPointList.append( QPoint( x, y ) );
+			int newx = (*cellsPtr)[x][y].prevX;
+			int newy = (*cellsPtr)[x][y].prevY;
+			if ( newx == x && newy == y ) {
+				ok = false;
+			}
+			x = newx;
+			y = newy;
+		}
+		while ( p_icnDocument->isValidCellReference(x,y) && x != -1 && y != -1 && ok );
+		
+		// And append the last point...
+		m_cellPointList.append( QPoint( ecx, ecy ) );
+	}
+	
+	removeDuplicatePoints();
+}
+
+
+bool ConRouter::checkLineRoute( int scx, int scy, int ecx, int ecy, int maxConScore, int maxCIScore )
+{
+	if ( (scx != ecx) && (scy != ecy) ) {
+		return false;
+	}
+	
+	const bool isHorizontal = scy == ecy;
+	
+	int start=0, end=0, x=0, y=0, dd=0;
+	if (isHorizontal)
+	{
+		dd = (scx<ecx)?1:-1;
+		start = scx;
+		end = ecx+dd;
+		y = scy;
+	}
+	else
+	{
+		dd = (scy<ecy)?1:-1;
+		start = scy;
+		end = ecy+dd;
+		x = scx;
+	}
+	
+	Cells *cells = p_icnDocument->cells();
+	
+	if (isHorizontal)
+	{
+		for ( int x = start; x!=end; x+=dd )
+		{
+			if ( std::abs((double)(x-start))>1 && std::abs((double)(x-end))>1 && ((*cells)[x][y].CIpenalty > maxCIScore || (*cells)[x][y].Cpenalty > maxConScore) )
+			{
+				return false;
+			} else {
+				m_cellPointList.append( QPoint( x, y ) );
+			}
+		}
+	}
+	else
+	{
+		for ( int y = start; y!=end; y+=dd )
+		{
+		  if ( std::abs((double)(y-start))>1 && std::abs((double)(y-end))>1 && ((*cells)[x][y].CIpenalty > maxCIScore || (*cells)[x][y].Cpenalty > maxConScore) )
+			{
+				return false;
+			} else {
+				m_cellPointList.append( QPoint( x, y ) );
+			}
+		}
+	}
+	
+	m_cellPointList.prepend( QPoint( scx, scy ) );
+	m_cellPointList.append( QPoint( ecx, ecy ) );
+	removeDuplicatePoints();
+	return true;
+}
+
+
+void ConRouter::removeDuplicatePoints()
+{
+	QPoint prev(-1,-1);
+	
+	const QPointList::iterator end = m_cellPointList.end();
+	for ( QPointList::iterator it = m_cellPointList.begin(); it != end; ++it )
+	{
+		if ( *it == prev ) {
+			*it = QPoint(-1,-1);
+		} else {
+			prev = *it;
+		}
+	}
+	m_cellPointList.remove( QPoint(-1,-1) );
+}