textdiagram.cpp

TabBars的开源源码

	else
		nHorz = -1; // 'to' is to the left of 'from'

	// vert
	if (ptFrom.y == ptTo.y)
		nVert = 0; // 'to' is aligned with 'from'

	else if (ptFrom.y < ptTo.y)
		nVert = 1; // 'to' is below 'from'

	else
		nVert = -1; // 'to' is above 'from'
}

BOOL CTextDiagram::PickStartPoint(const CTDConnection& conn, int nIncrement, CPoint& ptStart, int nIgnoreConn) const
{
	CRect rFrom;
	
	if (!GetRect(conn.RectFrom(), rFrom))
		return FALSE;

	BOOL bHorz = FALSE;

	// determine start point
	int nSideFrom = conn.SideFrom();

	switch (nSideFrom)
	{
	case RECT_LEFT:
	case RECT_RIGHT:
		{
			ptStart.x = (nSideFrom == RECT_LEFT) ? rFrom.left : rFrom.right;
			ptStart.y = rFrom.top + 1;

			while(nIncrement--)
				ptStart.y++;

			if (ptStart.y >= rFrom.bottom)
				return FALSE;

			int nIntersect = IntersectConn(ptStart, TRUE);

			return (nIntersect == -1 || nIntersect == nIgnoreConn) ? 1 : -1;
		}
		break;

	case RECT_TOP:
	case RECT_BOTTOM:
		{
			ptStart.y = (nSideFrom == RECT_TOP) ? rFrom.top : rFrom.bottom;
			ptStart.x = rFrom.left + 1;

			while(nIncrement--)
				ptStart.x++;

			if (ptStart.x >= rFrom.right)
				return FALSE;

			int nIntersect = IntersectConn(ptStart, FALSE);

			return (nIntersect == -1 || nIntersect == nIgnoreConn) ? 1 : -1;
		}
		break;
	}

	return 0;
}

int CTextDiagram::BuildPath(CTDConnection& conn, int nIgnoreConn)
{
	if (conn.RectFrom() == conn.RectTo())
		return FALSE;
	
	CRect rFrom, rTo;
	
	if (!GetRect(conn.RectFrom(), rFrom) || !GetRect(conn.RectTo(), rTo))
		return FALSE;

	// reset
	conn.ResetSegments();

	// to get the best results we try every point on the start side
	// and take to shortest route as our solution
	CTDConnection connMin;
	int nIncrement = 0;
	CPoint ptFrom;
	int nPick = 0;

	while (nPick = PickStartPoint(conn, nIncrement, ptFrom, nIgnoreConn))
	{
		if (nPick == -1) // already taken
		{
			nIncrement++;
			continue;
		}

		CTDConnection connTemp(conn);
		
		connTemp.SetStartPos(ptFrom);
		BOOL bCanBacktrack = FALSE; // always false for first segment
		BOOL bBlueYonder = FALSE; // indicates whether the last change of dir was due to 'blue yonder'

		int nIteration = 0; // for catching infinite loops

		int nHorzRect, nVertRect;
		GetRelationship(rFrom, rTo, nHorzRect, nVertRect);

		// build the path
		// note: we can stop any path as soon as we exceed the current shortest path
		while (IntersectRect(connTemp.GetEndPos()) != connTemp.RectTo() && 
				nIteration < MAXITERATIONS &&
				(!connMin.GetLength() || connTemp.GetLength() < connMin.GetLength()))
		{
			// start of a new segment
			int nCurSegment = 0;
			BOOL bSegmentDone = FALSE;

			// cache our current relationship
			int nHorzOrg, nVertOrg;
			GetRelationship(connTemp.GetEndPos(), rTo, nHorzOrg, nVertOrg);

			// refresh current relationship
			while (!bSegmentDone && nIteration < MAXITERATIONS)
			{
				nIteration++;

				// refresh current relationship
				CPoint ptEnd = connTemp.GetEndPos(nCurSegment);

				int nHorz, nVert;
				GetRelationship(ptEnd, rTo, nHorz, nVert);

				// special case: start of segment
				if (!nCurSegment)
				{
					// start of first segment
					if (connTemp.GetStartPos() == ptEnd)
					{
						// always move at least one char in the direction we are pointing
						switch (connTemp.SideFrom())
						{
						case RECT_LEFT:
						case RECT_TOP:
							nCurSegment--;
							break;

						case RECT_RIGHT:
						case RECT_BOTTOM:
							nCurSegment++;
							break;

						default:
							ASSERT(0);
						}
					}
					else // start of subsequent segment
					{
						// select new direction
						int nPrevDir = connTemp.GetEndDirection();

						switch (nPrevDir)
						{
						case CONN_UP:
						case CONN_DOWN:
							if (nHorz)
								nCurSegment = nHorz;
							else
							{
								// look more closely at the rect relationship
								nCurSegment = nHorzRect ? nHorzRect : 1;
							}
							break;
							
						case CONN_RIGHT:
						case CONN_LEFT:
							if (nVert)
								nCurSegment = nVert;
							else
							{
								// look more closely at the rect relationship
								nCurSegment = nVertRect ? nVertRect : 1;
							}
							break;
						}
					}

					continue;
				}
				// special case: make sure we're *not* pointing off into the wide blue yonder
				else
				{
					int nDir = connTemp.GetEndDirection(nCurSegment);
					
					if ((nDir == CONN_LEFT && nHorz == 1) || 
						(nDir == CONN_UP && nVert == 1) ||
						(nDir == CONN_RIGHT && nHorz == -1) || 
						(nDir == CONN_DOWN && nVert == -1))
					{
						bBlueYonder = TRUE;
						bSegmentDone = TRUE;
						connTemp.AddSegment(nCurSegment);
						continue;
					}
				}

				// else continue to move in same direction until we hit something
				// or we intersect vertically or horizontally with nRectTo
				int nDir = connTemp.GetEndDirection(nCurSegment);
				
				// 1. check if we've arrived
				if (IntersectRect(ptEnd) == connTemp.RectTo())
				{
					bBlueYonder = FALSE;
					bSegmentDone = TRUE;
					connTemp.AddSegment(nCurSegment);
					continue;
				}
				
				// 2. hit another rect or run off the page?
				if (ptEnd.x < 0 || ptEnd.y < 0 || PtInRect(ptEnd.x, ptEnd.y))
				{
					bSegmentDone = TRUE;
					
					if (bCanBacktrack) // backtrack to last segment, move on and try again
					{
						connTemp.IncrementLastSegment();
					}
					else
					{
						CTDConnection::Decrement(nCurSegment);
						connTemp.AddSegment(nCurSegment);
					}
					
					bBlueYonder = FALSE;
					continue;
				}
				
				// 3. hit another conn?
				// note: although the code following is the same as for hitting a rect
				// we do it separately as its more efficient to do the rect check first
				int nConn = IntersectConn(ptEnd, nDir == CONN_LEFT || nDir == CONN_RIGHT);
				
				if (nConn != -1 && nConn != nIgnoreConn)
				{
					bSegmentDone = TRUE;
					
					if (bCanBacktrack || bBlueYonder) // backtrack to last segment, move on and try again
					{
						connTemp.IncrementLastSegment();
					}
					else
					{
						bBlueYonder = FALSE;

						CTDConnection::Decrement(nCurSegment);
						connTemp.AddSegment(nCurSegment);
					}
				}
				// 4. horz intersect with target rect?
				else if (!nHorz && (nHorz != nHorzOrg || nDir == CONN_LEFT || nDir == CONN_RIGHT))
				{
					ASSERT (nHorz != nVert); // can't be both
					
					bCanBacktrack = TRUE;
					bSegmentDone = TRUE;
					bBlueYonder = FALSE;
					
					connTemp.AddSegment(nCurSegment);
				}
				// 5. vert intersect with target rect?
				else if (!nVert && (nVert != nVertOrg || nDir == CONN_UP || nDir == CONN_DOWN)) 
				{
					ASSERT (nHorz != nVert); // can't be both
					
					bCanBacktrack = TRUE;
					bSegmentDone = TRUE;
					bBlueYonder = FALSE;
					
					connTemp.AddSegment(nCurSegment);
				}
				// 6. just keep going
				else
				{
					CTDConnection::Increment(nCurSegment);
				}
			}
		}

		// update min length if the connection is valid
		if (nIteration < MAXITERATIONS)
		{
			// cleanup any unexpected backtracks
			CleanupBacktracks(connTemp);

			// make sure we still end up at the target rect
			if (IntersectRect(connTemp.GetEndPos()) == connTemp.RectTo())
			{
				// test for shortest
				if (connTemp.GetLength() && (!connMin.GetLength() || connTemp.GetLength() < connMin.GetLength()))
					connMin = connTemp;
			}
		}

		// next try
		nIncrement++;
	}

	// pick the shortest route
	conn = connMin;

	return conn.GetLength();
}

void CTextDiagram::CleanupBacktracks(CTDConnection& conn)
{
	CTDConnection temp(conn);
	conn.ResetSegments();
	
	for (int nSeg = 0; nSeg < temp.NumSegments(); nSeg++)
	{
		int nSegment = temp.Segment(nSeg);
		
		// if the next (nSeg + 1) segment is zero
		// then aggregate this with the one after that
		// and omit the zero item
		if (nSeg < temp.NumSegments() - 1 && temp.Segment(nSeg + 1) == 0)
		{
			if (nSeg < temp.NumSegments() - 2)
			{
				nSegment += temp.Segment(nSeg + 2);
				nSeg++;
			}
			
			nSeg++;
		}
		
		conn.AddSegment(nSegment);
	}
}

void CTextDiagram::TraceDiagram(const CStringArray& diagram)
{
#ifdef _DEBUG
	TRACE ("\n");

	for (int nLine = 0; nLine < diagram.GetSize(); nLine++)
		TRACE("%s\n", diagram[nLine]);

	TRACE ("\n");
#endif
}

BOOL CTextDiagram::VerifyDiagram() const
{
	// to verify:
	// 1. get the current diagram as text
	// 2. load it into a temp diagram
	// 3. compare the diagram ro ourselves
	CString sDiagram;
	GetDiagram(sDiagram, FALSE);

	CTextDiagram dgmTemp(sDiagram);

	if (!(*this == dgmTemp))
	{
		TRACE(sDiagram);
		dgmTemp.TraceDiagram();
		return FALSE;
	}

	return TRUE;
}

void CTextDiagram::TraceDiagram() const
{
#ifdef _DEBUG
	CStringArray diagram;

	BuildDiagram(diagram);
	TraceDiagram(diagram);
#endif
}

BOOL CTextDiagram::operator==(const CTextDiagram& diagram) const
{
	if (m_aRects.GetSize() != diagram.m_aRects.GetSize())
		return FALSE;

	if (m_aConns.GetSize() != diagram.m_aConns.GetSize())
		return FALSE;

	// rects can be in any order
	for (int nRect = 0; nRect < m_aRects.GetSize(); nRect++)
	{
		if (diagram.FindRect(m_aRects[nRect]) == -1)
			return FALSE;
	}

	// conns can be in any order
	for (int nConn = 0; nConn < m_aConns.GetSize(); nConn++)
	{
		CRect rFrom, rTo;
		const CTDConnection& conn = m_aConns[nConn];

		GetRect(conn.RectFrom(), rFrom);
		GetRect(conn.RectTo(), rTo);

		if (diagram.FindConn(rFrom, rTo) == -1)
			return FALSE;
	}

	return TRUE;
}

int CTextDiagram::FindRect(LPCRECT pRect) const
{
	ASSERT (pRect);

	if (!pRect)
		return -1;

	for (int nRect = 0; nRect < m_aRects.GetSize(); nRect++)
	{
		if (m_aRects[nRect].EqualRect(pRect))
			return nRect;
	}

	return -1;
}

int CTextDiagram::FindConn(LPCRECT pFrom, LPCRECT pTo) const
{
	ASSERT (pFrom && pTo);

	if (!(pFrom && pTo))
		return -1;

	for (int nConn = 0; nConn < m_aConns.GetSize(); nConn++)
	{
		CRect rFrom, rTo;
		const CTDConnection& conn = m_aConns[nConn];

		GetRect(conn.RectFrom(), rFrom);
		GetRect(conn.RectTo(), rTo);

		if (rFrom.EqualRect(pFrom) && rTo.EqualRect(pTo))
			return nConn;
	}

	return -1;
}

const CTextDiagram& CTextDiagram::operator=(const CTextDiagram& diagram)
{
	m_aRects.Copy(diagram.m_aRects);
	m_aConns.Copy(diagram.m_aConns);
	m_size = diagram.m_size;

	return *this;
}

void CTextDiagram::RecalcSize()
{
	CRect rSize(0, 0, 0, 0);

	for (int nRect = 0; nRect < m_aRects.GetSize(); nRect++)
	{
		rSize |= m_aRects[nRect];
	}

	for (int nConn = 0; nConn < m_aConns.GetSize(); nConn++)
	{
		rSize |= m_aConns[nConn].GetBoundingRect();
	}

	m_size.cx = rSize.right;
	m_size.cy = rSize.bottom;
}

BOOL CTextDiagram::CanAddConnection(const CTDRect& rect, int nSide)
{
	int nX, nY;

	switch (nSide)
	{
	case RECT_LEFT:
		for (nY = rect.top; nY <= rect.bottom; nY++)
		{
			if (!PtInConn(rect.left, nY, TRUE))
				return TRUE;
		}
		break;

	case RECT_RIGHT:
		for (nY = rect.top; nY <= rect.bottom; nY++)
		{
			if (!PtInConn(rect.right, nY, TRUE))
				return TRUE;
		}
		break;

	case RECT_TOP:
		for (nX = rect.left; nX <= rect.right; nX++)
		{
			if (!PtInConn(nX, rect.top, FALSE))
				return TRUE;
		}
		break;

	case RECT_BOTTOM:
		for (nX = rect.left; nX <= rect.right; nX++)
		{
			if (!PtInConn(nX, rect.bottom, FALSE))
				return TRUE;
		}
		break;
	}

	return FALSE;
}

int CTextDiagram::NewRect()
{
	// work our way out from the origin in rings until we find a spot
	int nNewRect = -1;
	int nRadius = 1;

	while (nNewRect == -1)
	{
		for (int nY = 1; nY <= nRadius && nNewRect == -1; nY++)
		{
			for (int nX = 1; nX <= nRadius && nNewRect == -1; nX++)
				nNewRect = AddRect(CRect(nX, nY, nX + 5, nY + 3));
		}

		nRadius++;
	}

	return nNewRect;
}

BOOL CTextDiagram::IntersectConn(const CRect& rect) const
{
	// the simplest though probably not the most efficient approach
	// simply to check every point in the rect
	for (int nX = rect.left; nX <= rect.right; nX++)
	{
		for (int nY = rect.top; nY <= rect.bottom; nY++)
		{
			if (PtInConn(nX, nY, TRUE) || PtInConn(nX, nY, FALSE))
				return TRUE;
		}
	}

	return FALSE;
}