/*******************************************************************

Part of the Fritzing project - http://fritzing.org
Copyright (c) 2007-2019 Fritzing

Fritzing 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
(at your option) any later version.


Fritzing 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 Fritzing.  If not, see <http://www.gnu.org/licenses/>.

********************************************************************/


// with lots of suggestions from http://cc.ee.ntu.edu.tw/~ywchang/Courses/PD/unit6.pdf
// and some help from http://workbench.lafayette.edu/~nestorj/cadapplets/MazeApplet/src/
// more (unused) suggestions at http://embedded.eecs.berkeley.edu/Alumni/pinhong/ee244/4-routing.PDF

// TODO:
//
//      jumper placement must be away from vias and vv
//          how to create test case
//
//      test if source touches target
//
//      add max cycles to settings dialog?
//
//      figure out what is taking so long once the router is creating traces
//          change connection is calling ratsnestconnect for every pair and calls collectEqualPotential
//
//      net reordering/rip-up-and-reroute
//          is there a better way than move back by one?
//
//      raster back to vector
//          curve-fitting? use a bezier?  http://kobus.ca/seminars/ugrad/NM5_curve_s02.pdf
//
//      dynamic cost function based on distance to any target point?
//
//      allow multiple routes to reach GridTarget--eliminate all queued GridPoints with greater cost
//
//      what happens with expanded schematic frame?
//

#include "mazerouter.h"
#include "../../sketch/pcbsketchwidget.h"
#include "../../debugdialog.h"
#include "../../items/virtualwire.h"
#include "../../items/tracewire.h"
#include "../../items/jumperitem.h"
#include "../../items/symbolpaletteitem.h"
#include "../../items/via.h"
#include "../../items/resizableboard.h"
#include "../../utils/graphicsutils.h"
#include "../../utils/graphutils.h"
#include "../../utils/textutils.h"
#include "../../utils/folderutils.h"
#include "../../connectors/connectoritem.h"
#include "../../items/moduleidnames.h"
#include "../../processeventblocker.h"
#include "../../svg/groundplanegenerator.h"
#include "../../svg/svgfilesplitter.h"
#include "../../fsvgrenderer.h"
#include "../drc.h"
#include "../../connectors/svgidlayer.h"

#include <QApplication>
#include <QMessageBox>
#include <QSettings>

#include <qmath.h>
#include <limits>

//////////////////////////////////////

static constexpr int OptimizeFactor = 2;

//static int routeNumber = 0;

static QString CancelledMessage;

static constexpr int DefaultMaxCycles = 100;

static constexpr GridValue GridBoardObstacle = std::numeric_limits<GridValue>::max();
static constexpr GridValue GridPartObstacle = GridBoardObstacle - 1;
static constexpr GridValue GridSource = GridBoardObstacle - 2;
static constexpr GridValue GridTarget = GridBoardObstacle - 3;
static constexpr GridValue GridAvoid = GridBoardObstacle - 4;
static constexpr GridValue GridTempObstacle = GridBoardObstacle - 5;
static constexpr GridValue GridSourceFlag = (GridBoardObstacle / 2) + 1;

static constexpr uint Layer1Cost = 100;
static constexpr uint CrossLayerCost = 100;
static constexpr uint ViaCost = 2000;
static constexpr uint AvoidCost = 7;

static constexpr uchar GridPointDone = 1;
static constexpr uchar GridPointStepYPlus = 2;
static constexpr uchar GridPointStepYMinus = 4;
static constexpr uchar GridPointStepXPlus = 8;
static constexpr uchar GridPointStepXMinus = 16;
static constexpr uchar GridPointStepStart = 32;
static constexpr uchar GridPointJumperLeft = 64;
static constexpr uchar GridPointJumperRight = 128;
//static constexpr uchar GridPointNorth = 2;
//static constexpr uchar GridPointEast = 4;
//static constexpr uchar GridPointSouth = 8;
//static constexpr uchar GridPointWest = 16;

static constexpr uchar JumperStart = 1;
static constexpr uchar JumperEnd = 2;
static constexpr uchar JumperLeft = 4;
static constexpr uchar JumperRight = 8;

static constexpr double MinTraceManhattanLength = 0.1;  // pixels

////////////////////////////////////////////////////////////////////

QPointF getStepPoint(QPointF p, uchar flags, double gridPixels) {
	if ((flags & GridPointStepXPlus) != 0) {
		p.setX(p.x() + (gridPixels / 2));
		return p;
	}
	if ((flags & GridPointStepXMinus) != 0) {
		p.setX(p.x() - (gridPixels / 2));
		return p;
	}
	if ((flags & GridPointStepYPlus) != 0) {
		p.setY(p.y() + (gridPixels / 2));
		return p;
	}
	p.setY(p.y() - (gridPixels / 2));
	return p;
}

uchar getStepFlag(GridPoint & gp1, GridPoint & gp2) {
	if (gp1.y == gp2.y) {
		double avg = (gp1.x + gp2.x) / 2.0;
		return (avg > gp1.x) ? GridPointStepXPlus : GridPointStepXMinus;
	}

	double avg = (gp1.y + gp2.y) / 2.0;
	return (avg > gp1.y) ? GridPointStepYPlus : GridPointStepYMinus;

}

QPointF getPixelCenter(GridPoint & gp, QPointF & topLeft, double gridPixels) {
	return QPointF((gp.x * gridPixels) + topLeft.x() + (gridPixels / 2), (gp.y * gridPixels) + topLeft.y() + (gridPixels / 2));
}

uint getColor(GridValue val) {
	if (val == GridBoardObstacle) return 0xff000000;
	else if (val == GridPartObstacle) return 0xff404040;
	else if (val == 0) return 0;
	else if (val == GridSource) return 0xff00ff00;
	else if (val == GridTarget) return 0xffff0000;
	else if (val == GridAvoid) return 0xff808080;
	else if (val == GridTempObstacle) return 0xff00ffff;
	else if (val & GridSourceFlag) return 0xff60d060;
	else return 0xffff6060;
}

void fastCopy(QImage * from, QImage * to) {
	uchar * fromBits = from->scanLine(0);
	uchar * toBits = to->scanLine(0);
	long bytes = from->bytesPerLine() * from->height();
	memcpy(toBits, fromBits, bytes);
}

bool atLeast(const QPointF & p1, const QPointF & p2) {
	return (qAbs(p1.x() - p2.x()) >= MinTraceManhattanLength) || (qAbs(p1.y() - p2.y()) >= MinTraceManhattanLength);
}

void printOrder(const QString & msg, QList<int> & order) {
	QString string(msg);
	Q_FOREACH (int i, order) {
		string += " " + QString::number(i);
	}
	DebugDialog::debug(string);
}

QString getPartID(const QDomElement & element) {
	QString partID = element.attribute("partID");
	if (!partID.isEmpty()) return partID;

	QDomNode parent = element.parentNode();
	if (parent.isNull()) return "";

	return getPartID(parent.toElement());
}

bool idsMatch(const QDomElement & element, QMultiHash<QString, QString> & partIDs) {
	QString partID = getPartID(element);
	QStringList IDs = partIDs.values(partID);
	if (IDs.count() == 0) return false;

	QDomElement tempElement = element;
	while (tempElement.attribute("partID").isEmpty()) {
		QString id = tempElement.attribute("id");
		if (!id.isEmpty() && IDs.contains(id)) return true;

		tempElement = tempElement.parentNode().toElement();
	}

	return false;
}

bool byPinsWithin(Net * n1, Net * n2)
{
	if (n1->pinsWithin < n2->pinsWithin) return true;
	if (n1->pinsWithin > n2->pinsWithin) return false;

	return n1->net->count() < n2->net->count();
}

bool byOrder(Trace & t1, Trace & t2) {
	return (t1.order < t2.order);
}

/*
inline double initialCost(QPoint p1, QPoint p2) {
    //return qAbs(p1.x() - p2.x()) + qAbs(p1.y() - p2.y());
    return qSqrt(GraphicsUtils::distanceSqd(p1, p2));
}
*/

inline double distanceCost(const QPoint & p1, const QPoint & p2) {
	return GraphicsUtils::distanceSqd(p1, p2);
}

inline double manhattanCost(const QPoint & p1, const QPoint & p2) {
	return qMax(qAbs(p1.x() - p2.x()), qAbs(p1.y() - p2.y()));
}

inline int gridPointInt(Grid * grid, GridPoint & gp) {
	return (gp.z * grid->x * grid->y) + (gp.y * grid->x) + gp.x;
}

bool jumperWillFit(GridPoint & gridPoint, const Grid * grid, int halfSize) {
	for (int z = 0; z < grid->z; z++) {
		for (int y = -halfSize; y <= halfSize; y++) {
			int py = gridPoint.y + y;
			if (py < 0) return false;
			if (py >= grid->y) return false;

			for (int x = -halfSize; x <= halfSize; x++) {
				int px = x + gridPoint.x;
				if (px < 0) return false;
				if (px >= grid->x) return false;

				GridValue val = grid->at(px, py, z);
				if (val == GridPartObstacle || val == GridBoardObstacle || val == GridSource || val == GridTarget || val == GridAvoid|| val == GridTempObstacle) return false;
			}
		}
	}

	return true;
}

bool schematicJumperWillFitAux(GridPoint & gridPoint, const Grid * grid, int halfSize, int xl, int xr) {
	int underCount = 0;
	for (int y = -halfSize; y <= halfSize; y++) {
		if (y < 0) return false;
		if (y >= grid->y) return false;

		for (int x = xl; x <= xr; x++) {
			if (x < 0) return false;
			if (x >= grid->x) return false;

			GridValue val = grid->at(gridPoint.x + x, gridPoint.y + y, 0);
			if (val == GridPartObstacle || val == GridBoardObstacle || val == GridSource || val == GridTarget || val == GridAvoid|| val == GridTempObstacle) {
				return false;
			}

			if (val < gridPoint.baseCost) {
				if (++underCount > xr - xl) return false;
			}
		}
	}

	return true;
}

bool schematicJumperWillFit(GridPoint & gridPoint, const Grid * grid, int halfSize)
{
	if (schematicJumperWillFitAux(gridPoint, grid, halfSize, -(halfSize * 2), 0)) {
		gridPoint.flags |= GridPointJumperLeft;
		return true;
	}
	if (schematicJumperWillFitAux(gridPoint, grid, halfSize, 0, halfSize * 2)) {
		gridPoint.flags |= GridPointJumperRight;
		return true;
	}

	return false;
}

void initMarkers(Markers & markers, bool pcbType) {
	markers.outID = DRC::NotNet;
	markers.inTerminalID = pcbType ? DRC::AlsoNet : DRC::Net;
	markers.inSvgID = DRC::Net;
	markers.inSvgAndID = pcbType ? DRC::Net : DRC::AlsoNet;
	markers.inNoID = DRC::Net;
}

////////////////////////////////////////////////////////////////////

bool GridPoint::operator<(const GridPoint& other) const {
	// make sure lower cost is first
	return qCost > other.qCost;
}
////////////////////////////////////////////////////////////////////

Grid::Grid(int sx, int sy, int sz) :
	data(new GridValue[sx * sy * sz]()), // initialize to zero
	x(sx), y(sy), z(sz) { }

GridValue Grid::at(int sx, int sy, int sz) const {
    Q_ASSERT (sx < x);
    Q_ASSERT (sy < y);
    Q_ASSERT (sz < z);
	return *(data + (sz * y * x) + (sy * x) + sx);
}

void Grid::setAt(int sx, int sy, int sz, GridValue value) {
    Q_ASSERT (sx < x);
    Q_ASSERT (sy < y);
    Q_ASSERT (sz < z);
	*(data + (sz * y * x) + (sy * x) + sx) = value;
}

QList<QPoint> Grid::init(int sx, int sy, int sz, int width, int height, const QImage & image, GridValue value, bool collectPoints) {
	QList<QPoint> points;
	const uchar * bits1 = image.constScanLine(0);
	int bytesPerLine = image.bytesPerLine();
	for (int iy = sy; iy < sy + height; iy++) {
		int offset = iy * bytesPerLine;
		for (int ix = sx; ix < sx + width; ix++) {
			int byteOffset = (ix >> 3) + offset;
			uchar mask = DRC::BitTable[ix & 7];

			//if (routeNumber > 40) {
			//    DebugDialog::debug(QString("image %1 %2, %3").arg(image.width()).arg(image.height()).arg(image.isNull()));
			//    DebugDialog::debug(QString("init point %1 %2 %3").arg(ix).arg(iy).arg(sz));
			//    DebugDialog::debug(QString("init grid %1 %2 %3, %4").arg(x).arg(y).arg(z).arg((long) data, 0, 16));
			//}
			if ((*(bits1 + byteOffset)) & mask) continue;

			//if (routeNumber > 40) DebugDialog::debug("after mask");

			setAt(ix, iy, sz, value);
			//if (routeNumber > 40)
			//    DebugDialog::debug("set");
			if (collectPoints) {
				points.append(QPoint(ix, iy));
			}
		}
	}

	return points;
}


QList<QPoint> Grid::init4(int sx, int sy, int sz, int width, int height, const QImage * image, GridValue value, bool collectPoints) {
	// pixels are 4 x 4 bits
	QList<QPoint> points;
	const uchar * bits1 = image->constScanLine(0);
	int bytesPerLine = image->bytesPerLine();
	for (int iy = sy; iy < sy + height; iy++) {
		int offset = iy * bytesPerLine * 4;
		for (int ix = sx; ix < sx + width; ix++) {
			int byteOffset = (ix >> 1) + offset;
			uchar mask = ix & 1 ? 0x0f : 0xf0;

			if ((*(bits1 + byteOffset) & mask) != mask) ;
			else if ((*(bits1 + byteOffset + bytesPerLine) & mask) != mask) ;
			else if ((*(bits1 + byteOffset + bytesPerLine + bytesPerLine) & mask) != mask) ;
			else if ((*(bits1 + byteOffset + bytesPerLine + bytesPerLine + bytesPerLine) & mask) != mask) ;
			else continue;  // "pixel" is all white

			setAt(ix, iy, sz, value);
			if (collectPoints) {
				points.append(QPoint(ix, iy));
			}
		}
	}

	return points;
}

void Grid::copy(int fromIndex, int toIndex) {
	memcpy(((uchar *) data) + toIndex * x * y * sizeof(GridValue), ((uchar *) data) + fromIndex * x * y * sizeof(GridValue), x * y * sizeof(GridValue));
}

void Grid::clear() {
	// memset can be very dangerous, clear out memory this way
	std::fill_n(data, x * y * z, 0);
}

Grid::~Grid() {
	if (data) {
		delete [] data;
		data = nullptr;
	}
}

////////////////////////////////////////////////////////////////////


void Score::setOrdering(const NetOrdering & _ordering) {
	reorderNet = -1;
	if (ordering.order.count() > 0) {
		bool remove = false;
		for (int i = 0; i < ordering.order.count(); i++) {
			if (!remove && (ordering.order.at(i) == _ordering.order.at(i))) continue;

			remove = true;
			int netIndex = ordering.order.at(i);
			traces.remove(netIndex);
			int c = routedCount.value(netIndex);
			routedCount.remove(netIndex);
			totalRoutedCount -= c;
			c = viaCount.value(netIndex);
			viaCount.remove(netIndex);
			totalViaCount -= c;
		}
	}
	ordering = _ordering;
	//printOrder("new  ", ordering.order);
}

////////////////////////////////////////////////////////////////////

static constexpr long IDs[] = { 1452191, 9781580, 9781600, 9781620, 9781640, 9781660, 9781680, 9781700 };

void ConnectionThing::add(ConnectorItem * s, ConnectorItem * d) {
	//if (hasID(s) || hasID(d)) {
	//    s->debugInfo("addc");
	//    d->debugInfo("\t");
	//}

	sd.insert(s, d);
	sd.insert(d, s);
}

void ConnectionThing::remove(ConnectorItem * s) {
	//if (hasID(s)) {
	//    s->debugInfo("remc");
	//}
	sd.remove(s);
}

void ConnectionThing::remove(ConnectorItem * s, ConnectorItem * d) {
	//if (hasID(s) || hasID(d)) {
	//    s->debugInfo("remc");
	//    d->debugInfo("\t");
	//}
	sd.remove(s, d);
	sd.remove(d, s);
}

bool ConnectionThing::multi(ConnectorItem * s) {
	//if (hasID(s)) {
	//    s->debugInfo("mulc");
	//}
	return sd.values(s).count() > 1;
}

QList<ConnectorItem *> ConnectionThing::values(ConnectorItem * s) {
	//if (hasID(s)) {
	//    s->debugInfo("valc");
	//}
	QList<ConnectorItem *> result;
	Q_FOREACH (ConnectorItem * d, sd.values(s)) {
		if (d == nullptr) continue;
		if (sd.values(d).count() == 0) continue;
		result << d;
		//if (hasID(s)) d->debugInfo("\t");
	}
	return result;
}

////////////////////////////////////////////////////////////////////

MazeRouter::MazeRouter(PCBSketchWidget * sketchWidget, QGraphicsItem * board, bool adjustIf) :
    Autorouter(sketchWidget),
    m_keepoutMils(0.0),
    m_keepoutGrid(0.0),
    m_keepoutGridInt(0),
    m_halfGridViaSize(0),
    m_halfGridJumperSize(0),
    m_gridPixels(0.0),
    m_standardWireWidth(0.0),
    m_boardImage(nullptr),
    m_spareImage(nullptr),
    m_spareImage2(nullptr),
    m_temporaryBoard(false),
    m_costFunction(nullptr),
    m_jumperWillFitFunction(nullptr),
    m_grid(nullptr),
    m_cleanupCount(0),
    m_netLabelIndex(-1),
    m_commandCount(0)
{

	CancelledMessage = tr("Autorouter was cancelled.");

	QSettings settings;
	m_maxCycles = settings.value(MaxCyclesName, DefaultMaxCycles).toInt();

	m_bothSidesNow = sketchWidget->routeBothSides();
	m_pcbType = sketchWidget->autorouteTypePCB();
	m_board = board;

	if (m_board) {
		m_maxRect = m_board->sceneBoundingRect();
	}
	else {
		QRectF itemsBoundingRect;
		Q_FOREACH(QGraphicsItem *item,  m_sketchWidget->scene()->items()) {
			if (!item->isVisible()) continue;

			itemsBoundingRect |= item->sceneBoundingRect();
		}
		m_maxRect = itemsBoundingRect;  // itemsBoundingRect is not reliable.  m_sketchWidget->scene()->itemsBoundingRect();
		if (adjustIf) {
			m_maxRect.adjust(-m_maxRect.width() / 2, -m_maxRect.height() / 2, m_maxRect.width() / 2, m_maxRect.height() / 2);
		}
		m_board = new QGraphicsRectItem(m_maxRect);
		m_board->setVisible(false);
		m_sketchWidget->scene()->addItem(m_board);
		m_temporaryBoard = true;
	}

	m_standardWireWidth = m_sketchWidget->getAutorouterTraceWidth();

	/*
	// for debugging leave the last result hanging around
	QList<QGraphicsPixmapItem *> pixmapItems;
	foreach (QGraphicsItem * item, m_sketchWidget->scene()->items()) {
	    QGraphicsPixmapItem * pixmapItem = dynamic_cast<QGraphicsPixmapItem *>(item);
	    if (pixmapItem) pixmapItems << pixmapItem;
	}
	foreach (QGraphicsPixmapItem * pixmapItem, pixmapItems) {
	    delete pixmapItem;
	}
	*/

	ViewGeometry vg;
	vg.setWireFlags(m_sketchWidget->getTraceFlag());
	ViewLayer::ViewLayerID bottom = sketchWidget->getWireViewLayerID(vg, ViewLayer::NewBottom);
	m_viewLayerIDs << bottom;
	if  (m_bothSidesNow) {
		ViewLayer::ViewLayerID top = sketchWidget->getWireViewLayerID(vg, ViewLayer::NewTop);
		m_viewLayerIDs.append(top);
	}
}

MazeRouter::~MazeRouter()
{
    /// @todo replace explicit deletes with std::shared_ptr and std::unique_ptr
    /// where it makes sense.
	Q_FOREACH (QDomDocument * doc, m_masterDocs) {
		delete doc;
	}
	if (m_displayItem[0]) {
		delete m_displayItem[0];
	}
	if (m_displayItem[1]) {
		delete m_displayItem[1];
	}
	if (m_displayImage[0]) {
		delete m_displayImage[0];
	}
	if (m_displayImage[1]) {
		delete m_displayImage[1];
	}
	if (m_temporaryBoard && m_board != nullptr) {
		delete m_board;
	}
	if (m_grid) {
		delete m_grid;
	}
	if (m_boardImage) {
		delete m_boardImage;
	}
	if (m_spareImage) {
		delete m_spareImage;
	}
	if (m_spareImage2) {
		delete m_spareImage2;
	}
}

void MazeRouter::start()
{
	if (m_pcbType) {
		if (!m_board) {
			QMessageBox::warning(nullptr, QObject::tr("Fritzing"), QObject::tr("Cannot autoroute: no board (or multiple boards) found"));
			return;
		}
		m_jumperWillFitFunction = jumperWillFit;
		m_costFunction = distanceCost;
		m_traceColors[0] = 0xa0F28A00;
		m_traceColors[1] = 0xa0FFCB33;
	}
	else {
		m_jumperWillFitFunction = schematicJumperWillFit;
		m_costFunction = manhattanCost;
		m_traceColors[0] = m_traceColors[1] = 0xa0303030;
	}

	m_keepoutPixels = m_sketchWidget->getKeepout();			// 15 mils space (in pixels)
	m_gridPixels = qMax(m_standardWireWidth, m_keepoutPixels);
	m_keepoutMils = m_keepoutPixels * GraphicsUtils::StandardFritzingDPI / GraphicsUtils::SVGDPI;
	m_keepoutGrid = m_keepoutPixels / m_gridPixels;
	m_keepoutGridInt = qCeil(m_keepoutGrid);

	double ringThickness, holeSize;
	m_sketchWidget->getViaSize(ringThickness, holeSize);
	auto gridViaSize = qCeil((ringThickness + ringThickness + holeSize + m_keepoutPixels + m_keepoutPixels) / m_gridPixels);
	m_halfGridViaSize = gridViaSize / 2;

	QSizeF jumperSize = m_sketchWidget->jumperItemSize();
	auto gridJumperSize = qCeil((qMax(jumperSize.width(), jumperSize.height()) + m_keepoutPixels  + m_keepoutPixels) / m_gridPixels);
	m_halfGridJumperSize = gridJumperSize / 2;

	Q_EMIT setMaximumProgress(m_maxCycles);
	Q_EMIT setProgressMessage("");
	Q_EMIT setCycleMessage("round 1 of:");
	Q_EMIT setCycleCount(m_maxCycles);

	m_sketchWidget->ensureTraceLayersVisible();

	QHash<ConnectorItem *, int> indexer;
	m_sketchWidget->collectAllNets(indexer, m_allPartConnectorItems, false, m_bothSidesNow, false);

	removeOffBoardAnd(m_pcbType, true, m_bothSidesNow);

	if (m_allPartConnectorItems.count() == 0) {
		QString message = m_pcbType ?  QObject::tr("No connections (on the PCB) to route.") : QObject::tr("No connections to route.");
		QMessageBox::information(nullptr, QObject::tr("Fritzing"), message);
		Autorouter::cleanUpNets();
		return;
	}

	auto *parentCommand = new QUndoCommand("Autoroute");
    /// @todo can have leaks if ctors of these commands changes
	new CleanUpWiresCommand(m_sketchWidget, CleanUpWiresCommand::UndoOnly, parentCommand);
	new CleanUpRatsnestsCommand(m_sketchWidget, CleanUpWiresCommand::UndoOnly, parentCommand);

	initUndo(parentCommand);

	NetList netList;
	auto totalToRoute = 0;
	for (auto i = 0; i < m_allPartConnectorItems.count(); i++) {
		auto *net = new Net;
		net->net = m_allPartConnectorItems[i];

		//foreach (ConnectorItem * connectorItem, *(net->net)) {
		//    connectorItem->debugInfo("all parts");
		//}

		QList<ConnectorItem *> todo;
		todo.append(*(net->net));
		while (todo.count() > 0) {
			auto *first = todo.takeFirst();
			QList<ConnectorItem *> equi;
			equi.append(first);
			ConnectorItem::collectEqualPotential(equi, m_bothSidesNow, (ViewGeometry::RatsnestFlag | ViewGeometry::NormalFlag | ViewGeometry::PCBTraceFlag | ViewGeometry::SchematicTraceFlag) ^ m_sketchWidget->getTraceFlag());
            Q_FOREACH (ConnectorItem * equ, equi) {
                todo.removeOne(equ);
                //equ->debugInfo("equi");
            }
			net->subnets.append(equi);
		}

		if (net->subnets.count() < 2) {
			// net is already routed
			continue;
		}

		net->pinsWithin = findPinsWithin(net->net);
		netList.nets << net;
		totalToRoute += net->net->count() - 1;
	}

    std::sort(netList.nets.begin(), netList.nets.end(), byPinsWithin);
	NetOrdering initialOrdering;
	auto ix = 0;
	Q_FOREACH (Net * net, netList.nets) {
		// id is the same as the order in netList
		initialOrdering.order << ix;
		net->id = ix++;
	}

	if (m_bothSidesNow) {
		Q_EMIT wantBothVisible();
	}

	ProcessEventBlocker::processEvents(); // to keep the app  from freezing
	if (m_cancelled || m_stopTracing) {
		restoreOriginalState(parentCommand);
		cleanUpNets(netList);
		return;
	}

	QSizeF gridSize(m_maxRect.width() / m_gridPixels, m_maxRect.height() / m_gridPixels);
	QSize boardImageSize(qCeil(gridSize.width()), qCeil(gridSize.height()));
	m_grid = new Grid(boardImageSize.width(), boardImageSize.height(), m_bothSidesNow ? 2 : 1);
	if (!m_grid->data) {
		QMessageBox::information(nullptr, QObject::tr("Fritzing"), "Out of memory--unable to proceed");
		restoreOriginalState(parentCommand);
		cleanUpNets(netList);
		return;
	}

	m_boardImage = new QImage(boardImageSize.width() * 4, boardImageSize.height() * 4, QImage::Format_Mono);
	m_spareImage = new QImage(boardImageSize.width() * 4, boardImageSize.height() * 4, QImage::Format_Mono);
	if (m_temporaryBoard) {
		m_boardImage->fill(0xffffffff);
	}
	else {
		m_boardImage->fill(0);
		QRectF r4(QPointF(0, 0), gridSize * 4);
		makeBoard(m_boardImage, m_keepoutGrid * 4, r4);
	}
	GraphicsUtils::drawBorder(m_boardImage, 4);

	ProcessEventBlocker::processEvents(); // to keep the app  from freezing
	if (m_cancelled || m_stopTracing) {
		restoreOriginalState(parentCommand);
		cleanUpNets(netList);
		return;
	}
    /// @todo perfect candidate for std::unique_ptr<QImage[]>
	m_displayImage[0] = new QImage(boardImageSize, QImage::Format_ARGB32);
	m_displayImage[0]->fill(0);
	m_displayImage[1] = new QImage(boardImageSize, QImage::Format_ARGB32);
	m_displayImage[1]->fill(0);

	QString message;
	auto gotMasters = makeMasters(message);
	if (m_cancelled || m_stopTracing || !gotMasters) {
		restoreOriginalState(parentCommand);
		cleanUpNets(netList);
		return;
	}

	QList<NetOrdering> allOrderings;
	allOrderings << initialOrdering;
	Score bestScore;
	Score currentScore;
	auto run = 0;
	for (; run < m_maxCycles && run < allOrderings.count(); run++) {
		QString msg= tr("best so far: %1 of %2 routed").arg(bestScore.totalRoutedCount).arg(totalToRoute);
		if (m_pcbType) {
			msg +=  tr(" with %n vias", "", bestScore.totalViaCount);
		}
		Q_EMIT setProgressMessage(msg);
		Q_EMIT setCycleMessage(tr("round %1 of:").arg(run + 1));
		Q_EMIT setProgressValue(run);
		ProcessEventBlocker::processEvents();
		currentScore.setOrdering(allOrderings.at(run));
		currentScore.anyUnrouted = false;
		routeNets(netList, false, currentScore, gridSize, allOrderings);
		if (bestScore.ordering.order.count() == 0) {
			bestScore = currentScore;
		}
		else {
			if (currentScore.totalRoutedCount > bestScore.totalRoutedCount) {
				bestScore = currentScore;
			}
			else if (currentScore.totalRoutedCount == bestScore.totalRoutedCount && currentScore.totalViaCount < bestScore.totalViaCount) {
				bestScore = currentScore;
			}
		}
		if (m_cancelled || bestScore.anyUnrouted == false || m_stopTracing) break;
	}

	Q_EMIT disableButtons();

	//DebugDialog::debug("done running");


	if (m_cancelled) {
		doCancel(parentCommand);
		return;
	}

	if (m_stopTracing) {
		QString msg = tr("Routing stopped!");
		msg += " ";
		if (m_useBest) msg += tr("Use best so far...");
		Q_EMIT setProgressMessage(msg);
		if (m_useBest) {
			routeNets(netList, true, bestScore, gridSize, allOrderings);
		}
	}
	else if (!bestScore.anyUnrouted) {
		Q_EMIT setProgressMessage(tr("Routing complete!"));
		Q_EMIT setProgressValue(m_maxCycles);
	}
	else {
		Q_EMIT setCycleMessage(tr("round %1 of:").arg(run));
		QString msg;
		if (run < m_maxCycles) msg = tr("Routing unsuccessful; stopping at round %1.").arg(run);
		else msg = tr("Routing reached maximum round %1.").arg(m_maxCycles);
		msg += " ";
		msg += tr("Use best so far...");
		Q_EMIT setProgressMessage(msg);
		printOrder("best ", bestScore.ordering.order);
		routeNets(netList, true, bestScore, gridSize, allOrderings);
		Q_EMIT setProgressValue(m_maxCycles);
	}
	ProcessEventBlocker::processEvents();

	if (m_grid) {
		delete m_grid;
		m_grid = nullptr;
	}
	if (m_boardImage) {
		delete m_boardImage;
		m_boardImage = nullptr;
	}
	if (m_spareImage) {
		delete m_spareImage;
		m_spareImage = nullptr;
	}

	m_boardImage = new QImage(m_maxRect.width() * OptimizeFactor, m_maxRect.height() * OptimizeFactor, QImage::Format_Mono);
	m_spareImage = new QImage(m_maxRect.width() * OptimizeFactor, m_maxRect.height() * OptimizeFactor, QImage::Format_Mono);
	m_spareImage2 = new QImage(m_maxRect.width() * OptimizeFactor, m_maxRect.height() * OptimizeFactor, QImage::Format_Mono);

	if (m_temporaryBoard) {
		m_boardImage->fill(0xffffffff);
	}
	else {
		m_boardImage->fill(0);
		QRectF r2(0, 0, m_boardImage->width(), m_boardImage->height());
		makeBoard(m_boardImage, m_keepoutPixels * 2, r2);
	}
	GraphicsUtils::drawBorder(m_boardImage, 2);

	createTraces(netList, bestScore, parentCommand);

	cleanUpNets(netList);
    /// @todo leaks can occur if not careful
	new CleanUpRatsnestsCommand(m_sketchWidget, CleanUpWiresCommand::RedoOnly, parentCommand);
	new CleanUpWiresCommand(m_sketchWidget, CleanUpWiresCommand::RedoOnly, parentCommand);

	m_sketchWidget->blockUI(true);
	m_commandCount = BaseCommand::totalChildCount(parentCommand);
	Q_EMIT setMaximumProgress(m_commandCount);
	Q_EMIT setProgressMessage2(tr("Preparing undo..."));
	if (m_displayItem[0]) {
		m_displayItem[0]->setVisible(false);
	}
	if (m_displayItem[1]) {
		m_displayItem[1]->setVisible(false);
	}
	ProcessEventBlocker::processEvents();
	m_cleanupCount = 0;
	m_sketchWidget->pushCommand(parentCommand, this);
	m_sketchWidget->blockUI(false);
	m_sketchWidget->repaint();
	DebugDialog::debug("\n\n\nautorouting complete\n\n\n");

}

int MazeRouter::findPinsWithin(QList<ConnectorItem *> * net) {
	auto count = 0;
	QRectF r;
	Q_FOREACH (ConnectorItem * connectorItem, *net) {
		r |= connectorItem->sceneBoundingRect();
	}

	Q_FOREACH (QGraphicsItem * item, m_sketchWidget->scene()->items(r)) {
		auto *connectorItem = dynamic_cast<ConnectorItem *>(item);
		if (!connectorItem) continue;

		if (net->contains(connectorItem)) continue;

		count++;
	}

	return count;
}

bool MazeRouter::makeBoard(QImage * boardImage, double keepoutGrid, const QRectF & renderRect) {
	LayerList viewLayerIDs;
	viewLayerIDs << ViewLayer::Board;
	RenderThing renderThing;
	renderThing.printerScale = GraphicsUtils::SVGDPI;
	renderThing.blackOnly = true;
	renderThing.dpi = GraphicsUtils::StandardFritzingDPI;
	renderThing.hideTerminalPoints = true;
	renderThing.selectedItems = renderThing.renderBlocker = false;
	QString boardSvg = m_sketchWidget->renderToSVG(renderThing, m_board, viewLayerIDs);
	if (boardSvg.isEmpty()) {
		return false;
	}

	QByteArray boardByteArray;
	QString tempColor("#ffffff");
	QStringList exceptions;
	exceptions << "none" << "";
	if (!SvgFileSplitter::changeColors(boardSvg, tempColor, exceptions, boardByteArray)) {
		return false;
	}

	QSvgRenderer renderer(boardByteArray);
	QPainter painter;
	painter.begin(boardImage);
	painter.setRenderHint(QPainter::Antialiasing, false);
	renderer.render(&painter, renderRect);
	painter.end();

	// board should be white, borders should be black

#ifndef QT_NO_DEBUG
	//boardImage->save(FolderUtils::getUserDataStorePath("") + "/mazeMakeBoard.png");
#endif

	// extend it given that the board image is * 4
	DRC::extendBorder(keepoutGrid, boardImage);

#ifndef QT_NO_DEBUG
	//boardImage->save(FolderUtils::getUserDataStorePath("") + "/mazeMakeBoard2.png");
#endif

	return true;
}

bool MazeRouter::makeMasters(QString & message) {
	QList<ViewLayer::ViewLayerPlacement> layerSpecs;
	layerSpecs << ViewLayer::NewBottom;
	if (m_bothSidesNow) layerSpecs << ViewLayer::NewTop;

	Q_FOREACH (ViewLayer::ViewLayerPlacement viewLayerPlacement, layerSpecs) {
		auto viewLayerIDs = m_sketchWidget->routingLayers(viewLayerPlacement);
		RenderThing renderThing;
		renderThing.printerScale = GraphicsUtils::SVGDPI;
		renderThing.blackOnly = true;
		renderThing.dpi = GraphicsUtils::StandardFritzingDPI;
		renderThing.hideTerminalPoints = renderThing.selectedItems = renderThing.renderBlocker = false;
		auto master = m_sketchWidget->renderToSVG(renderThing, m_board, viewLayerIDs);
		if (master.isEmpty()) {
			continue;
		}

		auto * masterDoc = new QDomDocument();
		m_masterDocs.insert(viewLayerPlacement, masterDoc);

		QString errorStr;
		int errorLine = 0;
		int errorColumn = 0;
		if (!masterDoc->setContent(master, &errorStr, &errorLine, &errorColumn)) {
			message = tr("Unexpected SVG rendering failure--contact fritzing.org");
			return false;
		}

		ProcessEventBlocker::processEvents();
		if (m_cancelled) {
			message = CancelledMessage;
			return false;
		}

		QDomElement root = masterDoc->documentElement();
		SvgFileSplitter::forceStrokeWidth(root, 2 * m_keepoutMils, "#000000", true, true);
		//QString forDebugging = masterDoc->toByteArray();
		//DebugDialog::debug("master " + forDebugging);
	}

	return true;
}

bool MazeRouter::routeNets(NetList & netList, bool makeJumper, Score & currentScore, const QSizeF gridSize, QList<NetOrdering> & allOrderings)
{
	RouteThing routeThing;
	routeThing.netElements[0] = NetElements();
	routeThing.netElements[1] = NetElements();
	routeThing.r = QRectF(QPointF(0, 0), gridSize);
	routeThing.r4 = QRectF(QPointF(0, 0), gridSize * 4);
	routeThing.layerSpecs << ViewLayer::NewBottom;
	if (m_bothSidesNow) routeThing.layerSpecs << ViewLayer::NewTop;

	auto result = true;

	initTraceDisplay();
	auto previousTraces = false;
	Q_FOREACH (int netIndex, currentScore.ordering.order) {
		if (m_cancelled || m_stopTracing) {
			return false;
		}

		auto *net = netList.nets.at(netIndex);
		/*
		DebugDialog::debug(QString("routing net %1, subnets %2, traces %3, routed %4")
		    .arg(netIndex)
		    .arg(net->subnets.count())
		    .arg(currentScore.traces.values(netIndex).count())
		    .arg(currentScore.routedCount.value(netIndex))
		    );
		*/

		if (currentScore.routedCount.value(netIndex) == net->subnets.count() - 1) {
			// this net was fully routed in a previous run
			Q_FOREACH (Trace trace, currentScore.traces.values(netIndex)) {
				displayTrace(trace);
			}
			previousTraces = true;
			continue;
		}

		if (previousTraces) {
			updateDisplay(0);
			if (m_bothSidesNow) updateDisplay(1);
		}

		if (currentScore.routedCount.value(netIndex) > 0) {
			// should only be here when makeJumpers = true
			// remove the set of routed traces for this net--the net was not completely routed
			// we didn't get all the way through before
			currentScore.totalRoutedCount -= currentScore.routedCount.value(netIndex);
			currentScore.routedCount.insert(netIndex, 0);
			currentScore.totalViaCount -= currentScore.viaCount.value(netIndex);
			currentScore.viaCount.insert(netIndex, 0);
			currentScore.traces.remove(netIndex);
		}

		//foreach (ConnectorItem * connectorItem, *(net->net)) {
		//    if (connectorItem->attachedTo()->layerKinChief()->id() == 12407630) {
		//        connectorItem->debugInfo("what");
		//        break;
		//    }
		//}

		QList< QList<ConnectorItem *> > subnets;
		Q_FOREACH (QList<ConnectorItem *> subnet, net->subnets) {
			QList<ConnectorItem *> copy(subnet);
			subnets.append(copy);
		}

		//DebugDialog::debug("find nearest pair");

		findNearestPair(subnets, routeThing.nearest);
		auto ip = routeThing.nearest.ic->sceneAdjustedTerminalPoint(nullptr) - m_maxRect.topLeft();
		routeThing.gridSourcePoint = QPoint(ip.x() / m_gridPixels, ip.y() / m_gridPixels);
		auto jp = routeThing.nearest.jc->sceneAdjustedTerminalPoint(nullptr) - m_maxRect.topLeft();
		routeThing.gridTargetPoint = QPoint(jp.x() / m_gridPixels, jp.y() / m_gridPixels);

		m_grid->clear();
		m_grid->init4(0, 0, 0, m_grid->x, m_grid->y, m_boardImage, GridBoardObstacle, false);
		if (m_bothSidesNow) {
			m_grid->copy(0, 1);
		}

		QList<Trace> traces = currentScore.traces.values();
		if (m_pcbType) {
			traceObstacles(traces, netIndex, m_grid, m_keepoutGridInt);
		}
		else {
			traceAvoids(traces, netIndex, routeThing);
		}

		Q_FOREACH (ViewLayer::ViewLayerPlacement viewLayerPlacement, routeThing.layerSpecs) {
			int z = viewLayerPlacement == ViewLayer::NewBottom ? 0 : 1;

			QDomDocument * masterDoc = m_masterDocs.value(viewLayerPlacement);

			//QString before = masterDoc->toString();

			Markers markers;
			initMarkers(markers, m_pcbType);
			DRC::splitNetPrep(masterDoc, *(net->net), markers, routeThing.netElements[z].net, routeThing.netElements[z].alsoNet, routeThing.netElements[z].notNet, true);
			Q_FOREACH (QDomElement element, routeThing.netElements[z].net) {
				element.setTagName("g");
			}
			Q_FOREACH (QDomElement element, routeThing.netElements[z].alsoNet) {
				element.setTagName("g");
			}

			//QString after = masterDoc->toString();

			//DebugDialog::debug("obstacles from board");
			m_spareImage->fill(0xffffffff);
			ItemBase::renderOne(masterDoc, m_spareImage, routeThing.r4);
#ifndef QT_NO_DEBUG
			//m_spareImage->save(FolderUtils::getUserDataStorePath("") + QString("/obstacles%1_%2.png").arg(netIndex, 2, 10, QChar('0')).arg(viewLayerPlacement));
#endif
			m_grid->init4(0, 0, z, m_grid->x, m_grid->y, m_spareImage, GridPartObstacle, false);
			//DebugDialog::debug("obstacles from board done");

			prepSourceAndTarget(masterDoc, routeThing, subnets, z, viewLayerPlacement);
		}

		//updateDisplay(m_grid, 0);
		//if (m_bothSidesNow) updateDisplay(m_grid, 1);

		//DebugDialog::debug(QString("before route one %1").arg(netIndex));
		routeThing.unrouted = false;
		if (!routeOne(makeJumper, currentScore, netIndex, routeThing, allOrderings)) {
			result = false;
		}
		//DebugDialog::debug(QString("after route one %1 %2").arg(netIndex).arg(result));

		while (result && subnets.count() > 2) {

			/*
			DebugDialog::debug(QString("\nnearest %1 %2").arg(routeThing.nearest.i).arg(routeThing.nearest.j));
			routeThing.nearest.ic->debugInfo("\ti");
			routeThing.nearest.jc->debugInfo("\tj");

			int ix = 0;
			foreach (QList<ConnectorItem *> subnet, subnets) {
			    foreach(ConnectorItem * connectorItem, subnet) {
			        connectorItem->debugInfo(QString::number(ix));
			    }
			    ix++;
			}
			*/

			result = routeNext(makeJumper, routeThing, subnets, currentScore, netIndex, allOrderings);
		}

		routeThing.netElements[0].net.clear();
		routeThing.netElements[0].notNet.clear();
		routeThing.netElements[0].alsoNet.clear();
		routeThing.netElements[1].net.clear();
		routeThing.netElements[1].notNet.clear();
		routeThing.netElements[1].alsoNet.clear();
		routeThing.sourceQ = std::priority_queue<GridPoint>();
		routeThing.targetQ = std::priority_queue<GridPoint>();

		if (!result) break;
	}

	return result;
}

bool MazeRouter::routeOne(bool makeJumper, Score & currentScore, int netIndex, RouteThing & routeThing, QList<NetOrdering> & allOrderings) {

	//DebugDialog::debug("start route()");
	Trace newTrace;
	auto viaCount = 0;
	routeThing.bestDistanceToSource = routeThing.bestDistanceToTarget = std::numeric_limits<double>::max();
	//DebugDialog::debug(QString("jumper d %1, %2").arg(routeThing.bestDistanceToSource).arg(routeThing.bestDistanceToTarget));

	newTrace.gridPoints = route(routeThing, viaCount);
	if (m_cancelled || m_stopTracing) {
		return false;
	}

	//DebugDialog::debug("after route()");


	if (newTrace.gridPoints.count() == 0) {
		if (makeJumper) {
			routeJumper(netIndex, routeThing, currentScore);
		}
		else {
			routeThing.unrouted = true;
			if (currentScore.reorderNet < 0) {
				for (int i = 0; i < currentScore.ordering.order.count(); i++) {
					if (currentScore.ordering.order.at(i) == netIndex) {
						if (moveBack(currentScore, i, allOrderings)) {
							currentScore.reorderNet = netIndex;
						}
						break;
					}
				}
			}

			currentScore.anyUnrouted = true;
			if (currentScore.reorderNet >= 0) {
				// rip up and reroute unless this net is already the first one on the list
				return false;
			}
			// unable to move the 0th net so keep going
		}
	}
	else {
		insertTrace(newTrace, netIndex, currentScore, viaCount, true);
		updateDisplay(0);
		if (m_bothSidesNow) updateDisplay(1);
	}

	//DebugDialog::debug("end routeOne()");


	return true;
}

bool MazeRouter::routeNext(bool makeJumper, RouteThing & routeThing, QList< QList<ConnectorItem *> > & subnets, Score & currentScore, int netIndex, QList<NetOrdering> & allOrderings)
{
	auto result = true;

	QList<ConnectorItem *> combined;
	if (routeThing.unrouted) {
		if (routeThing.nearest.i < routeThing.nearest.j) {
			subnets.removeAt(routeThing.nearest.j);
			combined = subnets.takeAt(routeThing.nearest.i);
		}
		else {
			combined = subnets.takeAt(routeThing.nearest.i);
			subnets.removeAt(routeThing.nearest.j);
		}
	}
	else {
		combined.append(subnets.at(routeThing.nearest.i));
		combined.append(subnets.at(routeThing.nearest.j));
		if (routeThing.nearest.i < routeThing.nearest.j) {
			subnets.removeAt(routeThing.nearest.j);
			subnets.removeAt(routeThing.nearest.i);
		}
		else {
			subnets.removeAt(routeThing.nearest.i);
			subnets.removeAt(routeThing.nearest.j);
		}
	}
	subnets.prepend(combined);
	routeThing.nearest.i = 0;
	routeThing.nearest.j = -1;
	routeThing.nearest.distance = std::numeric_limits<double>::max();
	findNearestPair(subnets, 0, combined, routeThing.nearest);
	auto ip = routeThing.nearest.ic->sceneAdjustedTerminalPoint(nullptr) - m_maxRect.topLeft();
	routeThing.gridSourcePoint = QPoint(ip.x() / m_gridPixels, ip.y() / m_gridPixels);
	auto jp = routeThing.nearest.jc->sceneAdjustedTerminalPoint(nullptr) - m_maxRect.topLeft();
	routeThing.gridTargetPoint = QPoint(jp.x() / m_gridPixels, jp.y() / m_gridPixels);

	routeThing.sourceQ = std::priority_queue<GridPoint>();
	routeThing.targetQ = std::priority_queue<GridPoint>();

	if (!m_pcbType) {
		QList<Trace> traces = currentScore.traces.values();
		traceAvoids(traces, netIndex, routeThing);
	}

	Q_FOREACH (ViewLayer::ViewLayerPlacement viewLayerPlacement, routeThing.layerSpecs) {
		int z = viewLayerPlacement == ViewLayer::NewBottom ? 0 : 1;
		QDomDocument * masterDoc = m_masterDocs.value(viewLayerPlacement);
		prepSourceAndTarget(masterDoc, routeThing, subnets, z, viewLayerPlacement);
	}

	// redraw traces from this net
	Q_FOREACH (Trace trace, currentScore.traces.values(netIndex)) {
		Q_FOREACH (GridPoint gridPoint, trace.gridPoints) {
			m_grid->setAt(gridPoint.x, gridPoint.y, gridPoint.z, GridSource);
			gridPoint.qCost = gridPoint.baseCost = /* initialCost(QPoint(gridPoint.x, gridPoint.y), routeThing.gridTarget) + */ 0;
			gridPoint.flags = 0;
			//DebugDialog::debug(QString("pushing trace %1 %2 %3, %4, %5").arg(gridPoint.x).arg(gridPoint.y).arg(gridPoint.z).arg(gridPoint.qCost).arg(routeThing.pq.size()));
			routeThing.sourceQ.push(gridPoint);
		}
	}

	//updateDisplay(m_grid, 0);
	//if (m_bothSidesNow) updateDisplay(m_grid, 1);

	routeThing.unrouted = false;
	result = routeOne(makeJumper, currentScore, netIndex, routeThing, allOrderings);

	return result;
}

bool MazeRouter::moveBack(Score & currentScore, int index, QList<NetOrdering> & allOrderings) {
	if (index == 0) {
		return false;  // nowhere to move back to
	}

	QList<int> order(currentScore.ordering.order);
	//printOrder("start", order);
	int netIndex = order.takeAt(index);
	//printOrder("minus", order);
	for (int i = index - 1; i >= 0; i--) {
		bool done = true;
		order.insert(i, netIndex);
		//printOrder("plus ", order);
		Q_FOREACH (NetOrdering ordering, allOrderings) {
			bool gotOne = true;
			for (int j = 0; j < order.count(); j++) {
				if (order.at(j) != ordering.order.at(j)) {
					gotOne = false;
					break;
				}
			}
			if (gotOne) {
				done = false;
				break;
			}
		}
		if (done == true) {
			NetOrdering newOrdering;
			newOrdering.order = order;
			allOrderings.append(newOrdering);
			//printOrder("done ", newOrdering.order);

			/*
			const static int watch[] = { 0, 1, 2, 3, 6, 12, 14, 4, 5, 7, 8, 9, 10, 11, 13, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64 };
			// {0, 1, 2, 4, 3, 12, 6, 14, 5, 7, 8, 9, 10, 11, 13, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64};

			bool matches = true;
			for (int i = 0; i < order.count(); i++) {
			    if (order.at(i) != watch[i]) {
			        matches = false;
			        break;
			    }
			}
			if (matches) {
			    DebugDialog::debug("order matches");
			}
			*/
			return true;
		}
		order.removeAt(i);
	}

	return false;
}

void MazeRouter::prepSourceAndTarget(QDomDocument * masterDoc, RouteThing & routeThing, QList< QList<ConnectorItem *> > & subnets, int z, ViewLayer::ViewLayerPlacement viewLayerPlacement)
{
	Q_FOREACH (QDomElement element, routeThing.netElements[z].notNet) {
		element.setTagName("g");
	}
	Q_FOREACH (QDomElement element, routeThing.netElements[z].alsoNet) {
		element.setTagName("g");
	}

	//QString debug = masterDoc->toString(4);

	Q_FOREACH (QDomElement element, routeThing.netElements[z].net) {
		// QString str;
		// QTextStream stream(&str);
		// element.save(stream, 0);
		// DebugDialog::debug(str);
		SvgFileSplitter::forceStrokeWidth(element, -2 * m_keepoutMils, "#000000", false, false);
	}

	QList<ConnectorItem *> li = subnets.at(routeThing.nearest.i);
	QList<QPoint> sourcePoints = renderSource(masterDoc, z, viewLayerPlacement, m_grid, routeThing.netElements[z].net, li, GridSource, true, routeThing.r4);

	Q_FOREACH (QPoint p, sourcePoints) {
		GridPoint gridPoint(p, z);
		gridPoint.qCost = gridPoint.baseCost = /* initialCost(p, routeThing.gridTarget) + */ 0;
		//DebugDialog::debug(QString("pushing source %1 %2 %3, %4, %5").arg(gridPoint.x).arg(gridPoint.y).arg(gridPoint.z).arg(gridPoint.qCost).arg(routeThing.pq.size()));
		routeThing.sourceQ.push(gridPoint);
	}

	QList<ConnectorItem *> lj = subnets.at(routeThing.nearest.j);
	QList<QPoint> targetPoints = renderSource(masterDoc, z, viewLayerPlacement, m_grid, routeThing.netElements[z].net, lj, GridTarget, true, routeThing.r4);
	Q_FOREACH (QPoint p, targetPoints) {
		GridPoint gridPoint(p, z);
		gridPoint.qCost = gridPoint.baseCost = /* initialCost(p, routeThing.gridTarget) + */ 0;
		//DebugDialog::debug(QString("pushing source %1 %2 %3, %4, %5").arg(gridPoint.x).arg(gridPoint.y).arg(gridPoint.z).arg(gridPoint.qCost).arg(routeThing.pq.size()));
		routeThing.targetQ.push(gridPoint);
	}

	Q_FOREACH (QDomElement element, routeThing.netElements[z].net) {
		SvgFileSplitter::forceStrokeWidth(element, 2 * m_keepoutMils, "#000000", false, false);
	}

	// restore masterdoc
	Q_FOREACH (QDomElement element, routeThing.netElements[z].net) {
		element.setTagName(element.attribute("former"));
		element.removeAttribute("net");
	}
	Q_FOREACH (QDomElement element, routeThing.netElements[z].notNet) {
		element.setTagName(element.attribute("former"));
		element.removeAttribute("net");
	}
	Q_FOREACH (QDomElement element, routeThing.netElements[z].alsoNet) {
		element.setTagName(element.attribute("former"));
		element.removeAttribute("net");
	}
}

void MazeRouter::findNearestPair(QList< QList<ConnectorItem *> > & subnets, Nearest & nearest) {
	nearest.distance = std::numeric_limits<double>::max();
	nearest.i = nearest.j = -1;
	nearest.ic = nearest.jc = nullptr;
	for (int i = 0; i < subnets.count() - 1; i++) {
		QList<ConnectorItem *> inet = subnets.at(i);
		findNearestPair(subnets, i, inet, nearest);
	}
}

void MazeRouter::findNearestPair(QList< QList<ConnectorItem *> > & subnets, int inetix, QList<ConnectorItem *> & inet, Nearest & nearest) {
	for (int j = inetix + 1; j < subnets.count(); j++) {
		QList<ConnectorItem *> jnet = subnets.at(j);
		Q_FOREACH (ConnectorItem * ic, inet) {
			QPointF ip = ic->sceneAdjustedTerminalPoint(nullptr);
			ConnectorItem * icc = ic->getCrossLayerConnectorItem();
			Q_FOREACH (ConnectorItem * jc, jnet) {
				ConnectorItem * jcc = jc->getCrossLayerConnectorItem();
				if (jc == ic || jcc == ic) continue;

				QPointF jp = jc->sceneAdjustedTerminalPoint(nullptr);
				double d = qSqrt(GraphicsUtils::distanceSqd(ip, jp)) / m_gridPixels;
				if (ic->attachedToViewLayerID() != jc->attachedToViewLayerID()) {
					if (jcc != nullptr || icc != nullptr) {
						// may not need a via
						d += CrossLayerCost;
					}
					else {
						// requires at least one via
						d += ViaCost;
					}
				}
				else {
					if (jcc != nullptr && icc != nullptr && ic->attachedToViewLayerID() == ViewLayer::Copper1) {
						// route on the bottom when possible
						d += Layer1Cost;
					}
				}
				if (d < nearest.distance) {
					nearest.distance = d;
					nearest.i = inetix;
					nearest.j = j;
					nearest.ic = ic;
					nearest.jc = jc;
				}
			}
		}
	}
}

QList<QPoint> MazeRouter::renderSource(QDomDocument * masterDoc, int z, ViewLayer::ViewLayerPlacement viewLayerPlacement, Grid * grid, QList<QDomElement> & netElements, QList<ConnectorItem *> & subnet, GridValue value, bool clearElements, const QRectF & renderRect) {
	if (clearElements) {
		Q_FOREACH (QDomElement element, netElements) {
			element.setTagName("g");
		}
	}

	m_spareImage->fill(0xffffffff);
	QMultiHash<QString, QString> partIDs;
	QMultiHash<QString, QString> terminalIDs;
	QList<ConnectorItem *> terminalPoints;
	QRectF itemsBoundingRect;
	Q_FOREACH (ConnectorItem * connectorItem, subnet) {
		ItemBase * itemBase = connectorItem->attachedTo();
		SvgIdLayer * svgIdLayer = connectorItem->connector()->fullPinInfo(itemBase->viewID(), itemBase->viewLayerID());
		partIDs.insert(QString::number(itemBase->id()), svgIdLayer->m_svgId);
		if (!svgIdLayer->m_terminalId.isEmpty()) {
			terminalIDs.insert(QString::number(itemBase->id()), svgIdLayer->m_terminalId);
			terminalPoints << connectorItem;
		}
		itemsBoundingRect |= connectorItem->sceneBoundingRect();
	}
	Q_FOREACH (QDomElement element, netElements) {
		if (idsMatch(element, partIDs)) {
			element.setTagName(element.attribute("former"));
		}
		else if (idsMatch(element, terminalIDs)) {
			element.setTagName(element.attribute("former"));
		}
	}

	if (!m_maxRect.contains(itemsBoundingRect)) {
		qWarning("autorouter: m_maxRect does not contain itemsBoundingRect");
		// Don't allow memory corruption
		itemsBoundingRect = m_maxRect;
	}
	int x1 = qFloor((itemsBoundingRect.left() - m_maxRect.left()) / m_gridPixels);
	int y1 = qFloor((itemsBoundingRect.top() - m_maxRect.top()) / m_gridPixels);
	int x2 = qCeil((itemsBoundingRect.right() - m_maxRect.left()) / m_gridPixels);
	int y2 = qCeil((itemsBoundingRect.bottom() - m_maxRect.top()) / m_gridPixels);

	ItemBase::renderOne(masterDoc, m_spareImage, renderRect);
#ifndef QT_NO_DEBUG
	//static int rsi = 0;
	//m_spareImage->save(FolderUtils::getUserDataStorePath("") + QString("/rendersource%1_%2.png").arg(rsi++,3,10,QChar('0')).arg(z));
#endif
	QList<QPoint> points = grid->init4(x1, y1, z, x2 - x1, y2 - y1, m_spareImage, value, true);



	// terminal point hack (mostly for schematic view)
	Q_FOREACH (ConnectorItem * connectorItem, terminalPoints) {
		if (ViewLayer::specFromID(connectorItem->attachedTo()->viewLayerID()) != viewLayerPlacement) {
			continue;
		}

		QPointF p = connectorItem->sceneAdjustedTerminalPoint(nullptr);
		QRectF r = connectorItem->attachedTo()->sceneBoundingRect().adjusted(-m_keepoutPixels, -m_keepoutPixels, m_keepoutPixels, m_keepoutPixels);
		QPointF closest(p.x(), r.top());
		double d = qAbs(p.y() - r.top());
		int dx = 0;
		int dy = -1;
		if (qAbs(p.y() - r.bottom()) < d) {
			d = qAbs(p.y() - r.bottom());
			closest = QPointF(p.x(), r.bottom());
			dy = 1;
			dx = 0;
		}
		if (qAbs(p.x() - r.left()) < d) {
			d = qAbs(p.x() - r.left());
			closest = QPointF(r.left(), p.y());
			dx = -1;
			dy = 0;
		}
		if (qAbs(p.x() - r.right()) < d) {
			closest = QPointF(r.right(), p.y());
			dy = 0;
			dx = 1;
		}

		double y1, y2, x1, x2;
		double yp = (p.y() - m_maxRect.top()) / m_gridPixels;
		double xp = (p.x() - m_maxRect.left()) / m_gridPixels;
		double yc = (closest.y() - m_maxRect.top()) / m_gridPixels;
		double xc = (closest.x() - m_maxRect.left()) / m_gridPixels;
		if (closest.x() == p.x()) {
			x1 = x2 = qRound((p.x() - m_maxRect.left()) / m_gridPixels);
			y1 = (yp < yc) ? qFloor(yp) : qCeil(yp);
			y2 = (yp < yc) ? qCeil(yc) : qFloor(yc);
			if (y2 < y1) {
				double temp = y2;
				y2 = y1;
				y1 = temp;
			}
		}
		else {
			y1 = y2 = qRound((p.y() - m_maxRect.top()) / m_gridPixels);
			x1 = (xp < xc) ? qFloor(xp) : qCeil(xp);
			x2 = (xp < xc) ? qCeil(xc) : qFloor(xc);
			if (x2 < x1) {
				double temp = x2;
				x2 = x1;
				x1 = temp;
			}
		}

		int xo = qRound(xc);
		int yo = qRound(yc);
		// remove obstacles we can draw through
		while (true) {
			xo += dx;
			yo += dy;
			if (grid->at(xo, yo, z) != GridAvoid) break;

			grid->setAt(xo, yo, z, 0);
		}

		for (int iy = y1; iy <= y2; iy++) {
			for (int ix = x1; ix <= x2; ix++) {
				GridValue val = grid->at(ix, iy, z);
				if (val == GridPartObstacle || val == GridAvoid) {
					// make an empty path up to the source point
					grid->setAt(ix, iy, z, 0);
				}
			}
		}
		int xr = qRound(xp);
		int yr = qRound(yp);
		if (grid->at(xr, yr, z) != GridBoardObstacle) {
			grid->setAt(xr, yr, z, value);
			points << QPoint(xr, yr);
		}

	}

	return points;
}

QList<GridPoint> MazeRouter::route(RouteThing & routeThing, int & viaCount)
{
	//DebugDialog::debug(QString("start route() %1").arg(routeNumber++));
	viaCount = 0;
	GridPoint done;
	bool result = false;
	while (!routeThing.sourceQ.empty() && !routeThing.targetQ.empty()) {
		GridPoint gp = routeThing.sourceQ.top();
		GridPoint gpt = routeThing.targetQ.top();
		if (gpt.qCost < gp.qCost) {
			gp = gpt;
			routeThing.targetQ.pop();
			routeThing.targetValue = GridSource;
			routeThing.sourceValue = GridTarget;
		}
		else {
			routeThing.sourceQ.pop();
			routeThing.targetValue = GridTarget;
			routeThing.sourceValue = GridSource;
		}

		if (gp.flags & GridPointDone) {
			done = gp;
			result = true;
			break;
		}

		expand(gp, routeThing);
		if (m_cancelled || m_stopTracing) {
			break;
		}
	}

	//DebugDialog::debug(QString("routing result %1").arg(result));

	QList<GridPoint> points;
	if (!result) {
		//updateDisplay(m_grid, 0);
		//DebugDialog::debug(QString("done routing no points"));
		return points;
	}
	done.baseCost = std::numeric_limits<GridValue>::max();  // make sure this is the largest value for either traceback
	QList<GridPoint> sourcePoints = traceBack(done, m_grid, viaCount, GridTarget, GridSource);      // trace back to source
	QList<GridPoint> targetPoints = traceBack(done, m_grid, viaCount, GridSource, GridTarget);      // trace back to target
	if (sourcePoints.count() == 0 || targetPoints.count() == 0) {
		DebugDialog::debug("traceback zero points");
		return points;
	}
	else {
		targetPoints.takeFirst();           // redundant point
		Q_FOREACH (GridPoint gp, targetPoints) points.prepend(gp);
		points.append(sourcePoints);
	}

	clearExpansion(m_grid);

	//DebugDialog::debug(QString("done with route() %1").arg(points.count()));

	return points;
}

QList<GridPoint> MazeRouter::traceBack(GridPoint gridPoint, Grid * grid, int & viaCount, GridValue sourceValue, GridValue targetValue) {
	//DebugDialog::debug(QString("traceback %1 %2 %3").arg(gridPoint.x).arg(gridPoint.y).arg(gridPoint.z));
	QList<GridPoint> points;
	points << gridPoint;
	while (true) {
		if (gridPoint.baseCost == targetValue) {
			// done
			break;
		}

		// can only be one neighbor with lower value
		GridPoint next = traceBackOne(gridPoint, grid, -1, 0, 0, sourceValue, targetValue);
		if (next.baseCost == GridBoardObstacle) {
			next = traceBackOne(gridPoint, grid, 1, 0, 0, sourceValue, targetValue);
			if (next.baseCost == GridBoardObstacle) {
				next = traceBackOne(gridPoint, grid, 0, -1, 0, sourceValue, targetValue);
				if (next.baseCost == GridBoardObstacle) {
					next = traceBackOne(gridPoint, grid, 0, 1, 0, sourceValue, targetValue);
					if (next.baseCost == GridBoardObstacle) {
						next = traceBackOne(gridPoint, grid, 0, 0, -1, sourceValue, targetValue);
						if (next.baseCost == GridBoardObstacle) {
							next = traceBackOne(gridPoint, grid, 0, 0, 1, sourceValue, targetValue);
							if (next.baseCost == GridBoardObstacle) {
								// traceback failed--is this possible?
								points.clear();
								break;
							}
						}
					}
				}
			}
		}

		//if (grid->at(next.x - 1, next.y, next.z) != GridObstacle) next.flags |= GridPointWest;
		//if (grid->at(next.x + 1, next.y, next.z) != GridObstacle) next.flags |= GridPointEast;
		//if (grid->at(next.x, next.y - 1, next.z) != GridObstacle) next.flags |= GridPointNorth;
		//if (grid->at(next.x, next.y + 1, next.z) != GridObstacle) next.flags |= GridPointSouth;
		points << next;
		if (next.z != gridPoint.z) viaCount++;
		gridPoint = next;
	}

	/*
	QString costs("costs ");
	foreach (GridPoint gridPoint, points) {
	    costs += QString::number(gridPoint.baseCost) + " ";
	}
	DebugDialog::debug(costs);
	*/

	return points;
}

GridPoint MazeRouter::traceBackOne(GridPoint & gridPoint, Grid * grid, int dx, int dy, int dz, GridValue sourceValue, GridValue targetValue) {
	GridPoint next;
	next.baseCost = GridBoardObstacle;

	next.x = gridPoint.x + dx;
	if (next.x < 0 || next.x >= grid->x) {
		return next;
	}

	next.y = gridPoint.y + dy;
	if (next.y < 0 || next.y >= grid->y) {
		return next;
	}

	next.z = gridPoint.z + dz;
	if (next.z < 0 || next.z >= grid->z) {
		return next;
	}

	GridValue nextval = grid->at(next.x, next.y, next.z);
	if (nextval == GridBoardObstacle || nextval == GridPartObstacle || nextval == sourceValue || nextval == 0 || nextval == GridTempObstacle) return next;
	if (nextval == targetValue) {
		// done!
		next.baseCost = targetValue;
		return next;
	}

	if (targetValue == GridSource) {
		if ((nextval & GridSourceFlag) == 0) return next;
		nextval ^= GridSourceFlag;
	}
	else {
		if (nextval & GridSourceFlag) return next;
	}

	if (nextval < gridPoint.baseCost) {
		next.baseCost = nextval;
	}
	return next;
}

void MazeRouter::expand(GridPoint & gridPoint, RouteThing & routeThing)
{
	//static bool debugit = false;
	//if (routeNumber > 41 && routeThing.pq.size() > 8200) debugit = true;

	//if (debugit) {
	//    DebugDialog::debug(QString("expand %1 %2 %3, %4").arg(gridPoint.x).arg(gridPoint.y).arg(gridPoint.z).arg(routeThing.pq.size()));
	//}
	if (gridPoint.x > 0) expandOne(gridPoint, routeThing, -1, 0, 0, false);
	if (gridPoint.x < m_grid->x - 1) expandOne(gridPoint, routeThing, 1, 0, 0, false);
	if (gridPoint.y > 0) expandOne(gridPoint, routeThing, 0, -1, 0, false);
	if (gridPoint.y < m_grid->y - 1) expandOne(gridPoint, routeThing, 0, 1, 0, false);
	if (m_bothSidesNow) {
		if (gridPoint.z > 0) expandOne(gridPoint, routeThing, 0, 0, -1, true);
		if (gridPoint.z < m_grid->z - 1) expandOne(gridPoint, routeThing, 0, 0, 1, true);
	}
	//if (debugit) {
	//    DebugDialog::debug("expand done");
	//}
}

void MazeRouter::expandOne(GridPoint & gridPoint, RouteThing & routeThing, int dx, int dy, int dz, bool crossLayer) {
	GridPoint next;
	next.x = gridPoint.x + dx;
	next.y = gridPoint.y + dy;
	next.z = gridPoint.z + dz;

	//DebugDialog::debug(QString("expand one %1,%2,%3 cl:%4").arg(next.x).arg(next.y).arg(next.z).arg(crossLayer));

	bool writeable = false;
	bool avoid = false;
	GridValue nextval = m_grid->at(next.x, next.y, next.z);
	if (nextval == GridPartObstacle || nextval == GridBoardObstacle || nextval == routeThing.sourceValue || nextval == GridTempObstacle) {
		//DebugDialog::debug("exit expand one");
		return;
	}

	if (nextval == routeThing.targetValue) {
		//DebugDialog::debug("found grid target");
		next.flags |= GridPointDone;
	}
	else if (nextval == 0) {
		writeable = true;
	}
	else if (nextval == GridAvoid) {
		bool contains = true;
		for (int i = 1; i <= 3; i++) {
			if (!routeThing.avoids.contains(((next.y - (i * dy)) * m_grid->x) + next.x - (i * dx))) {
				contains = false;
				break;
			}
		}

		if (contains) {
			// do not allow more than 3 in a row in the same direction?
			return;
		}
		avoid = writeable = true;
		if (dx == 0) {
			if (m_grid->at(next.x - 1, next.y, next.z) == GridAvoid) {
				m_grid->setAt(next.x - 1, next.y, next.z, GridTempObstacle);
			}
			if (m_grid->at(next.x + 1, next.y, next.z) == GridAvoid) {
				m_grid->setAt(next.x + 1, next.y, next.z, GridTempObstacle);
			}
		}
		else {
			if (m_grid->at(next.x, next.y - 1, next.z) == GridAvoid) {
				m_grid->setAt(next.x, next.y - 1, next.z, GridTempObstacle);
			}
			if (m_grid->at(next.x, next.y + 1, next.z) == GridAvoid) {
				m_grid->setAt(next.x, next.y + 1, next.z, GridTempObstacle);
			}
		}
	}
	else {
		// already been here: see if source and target expansions have intersected
		if (routeThing.sourceValue == GridSource) {
			if (nextval & GridSourceFlag) return;

			next.flags |= GridPointDone;
		}
		else {
			if ((nextval & GridSourceFlag) == 0) return;

			next.flags |= GridPointDone;
		}
	}

	// any way to skip viaWillFit or put it off until actually needed?
	if (crossLayer) {
		if (!viaWillFit(next, m_grid)) return;

		// only way to cross layers is with a via
		//QPointF center = getPixelCenter(next, m_maxRect.topLeft(), m_gridPixels);
		//DebugDialog::debug(QString("via will fit %1,%2,%3 %4,%5").arg(next.x).arg(next.y).arg(next.z).arg(center.x()).arg(center.y()));
	}

	next.baseCost = gridPoint.baseCost;
	if (crossLayer) {
		next.baseCost += ViaCost;
	}
	else if (avoid) {
		next.baseCost += AvoidCost;
	}
	next.baseCost++;


	/*
	int increment = 5;
	// assume because of obstacles around the board that we can never be off grid from (next.x, next.y)
	switch(grid->at(next.x - 1, next.y, next.z)) {
	    case GridObstacle:
	    case GridSource:
	    case GridTarget:
	        increment--;
	    default:
	        break;
	}
	switch(grid->at(next.x + 1, next.y, next.z)) {
	    case GridObstacle:
	    case GridSource:
	    case GridTarget:
	        increment--;
	    default:
	        break;
	}
	switch(grid->at(next.x, next.y - 1, next.z)) {
	    case GridObstacle:
	    case GridSource:
	    case GridTarget:
	        increment--;
	    default:
	        break;
	}
	switch(grid->at(next.x, next.y + 1, next.z)) {
	    case GridObstacle:
	    case GridSource:
	    case GridTarget:
	        increment--;
	    default:
	        break;
	}
	next.cost += increment;
	*/


	if (nextval == routeThing.targetValue) {
		next.qCost = next.baseCost;
	}
	else {
		double d = (m_costFunction)(QPoint(next.x, next.y), (routeThing.sourceValue == GridSource) ? routeThing.gridTargetPoint : routeThing.gridSourcePoint);
		next.qCost = next.baseCost + d;
		if (routeThing.sourceValue == GridSource) {
			if (d < routeThing.bestDistanceToTarget) {
				//DebugDialog::debug(QString("best d target %1, %2,%3").arg(d).arg(next.x).arg(next.y));
				routeThing.bestDistanceToTarget = d;
				routeThing.bestLocationToTarget = next;
			}
		}
		else {
			if (d < routeThing.bestDistanceToSource) {
				//DebugDialog::debug(QString("best d source %1, %2,%3").arg(d).arg(next.x).arg(next.y));
				routeThing.bestDistanceToSource = d;
				routeThing.bestLocationToSource = next;
			}
		}
	}

	// can think about pushing multiple points here
	//DebugDialog::debug(QString("pushing next %1 %2 %3, %4, %5").arg(gridPoint.x).arg(gridPoint.y).arg(gridPoint.z).arg(gridPoint.qCost).arg(routeThing.pq.size()));
	if (routeThing.sourceValue == GridSource) routeThing.sourceQ.push(next);
	else routeThing.targetQ.push(next);

	if (writeable) {
		GridValue flag = (routeThing.sourceValue == GridSource) ? GridSourceFlag : 0;
		m_grid->setAt(next.x, next.y, next.z, next.baseCost | flag);
	}

	//DebugDialog::debug("done expand one");


	//if (routeThing.searchForJumper) {
	//    updateDisplay(next);
	//}
}

bool MazeRouter::viaWillFit(GridPoint & gridPoint, Grid * grid) {
	for (int y = -m_halfGridViaSize; y <= m_halfGridViaSize; y++) {
		int py = y + gridPoint.y;
		if (py < 0) return false;
		if (py >= grid->y) return false;

		for (int x = -m_halfGridViaSize; x <= m_halfGridViaSize; x++) {
			int px = x + gridPoint.x;
			if (px < 0) return false;
			if (px >= grid->x) return false;

			for (int z = 0; z < grid->z; z++) {
				GridValue val = grid->at(px, py, z);
				if (val == GridPartObstacle || val == GridBoardObstacle || val == GridSource || val == GridTarget || val == GridTempObstacle || val == GridAvoid) return false;
			}
		}
	}
	return true;
}

void MazeRouter::updateDisplay(int iz) {
	QPixmap pixmap = QPixmap::fromImage(*m_displayImage[iz]);
	if (m_displayItem[iz] == nullptr) {
		m_displayItem[iz] = new QGraphicsPixmapItem(pixmap);
		m_displayItem[iz]->setFlag(QGraphicsItem::ItemIsSelectable, false);
		m_displayItem[iz]->setFlag(QGraphicsItem::ItemIsMovable, false);
		//m_displayItem[iz]->setPos(iz == 1 ? m_maxRect.topLeft() : m_maxRect.topRight());
		m_displayItem[iz]->setPos(m_maxRect.topLeft());
		m_sketchWidget->scene()->addItem(m_displayItem[iz]);
		m_displayItem[iz]->setZValue(5000);
		//m_displayItem[iz]->setZValue(m_sketchWidget->viewLayers().value(iz == 0 ? ViewLayer::Copper0 : ViewLayer::Copper1)->nextZ());
		m_displayItem[iz]->setScale(m_gridPixels);   // m_maxRect.width() / m_displayImage[iz]->width()
		m_displayItem[iz]->setVisible(true);
	}
	else {
		m_displayItem[iz]->setPixmap(pixmap);
	}
	ProcessEventBlocker::processEvents();
}

void MazeRouter::updateDisplay(Grid * grid, int iz) {
	m_displayImage[iz]->fill(0);
	for (int y = 0; y < grid->y; y++) {
		for (int x = 0; x < grid->x; x++) {
			uint color = getColor(grid->at(x, y, iz));
			if (color) m_displayImage[iz]->setPixel(x, y, color);
		}
	}

	updateDisplay(iz);
}

void MazeRouter::updateDisplay(GridPoint & gridPoint) {
	//static int counter = 0;
	//if (counter++ % 2 == 0) {
	uint color = getColor(m_grid->at(gridPoint.x, gridPoint.y, gridPoint.z));
	if (color) {
		m_displayImage[gridPoint.z]->setPixel(gridPoint.x, gridPoint.y, color);
		updateDisplay(gridPoint.z);
	}
	//}
}

void MazeRouter::clearExpansion(Grid * grid) {
	// TODO: keep a list of expansion points instead?

	for (int z = 0; z < grid->z; z++) {
		for (int y = 0; y < grid->y; y++) {
			for (int x = 0; x < grid->x; x++) {
				GridValue val = grid->at(x, y, z);
				if (val == 0 || val == GridPartObstacle || val == GridBoardObstacle) ;
				else grid->setAt(x, y, z, 0);
			}
		}
	}
}

void MazeRouter::initTraceDisplay() {
	m_displayImage[0]->fill(0);
	m_displayImage[1]->fill(0);
}

void MazeRouter::displayTrace(Trace & trace) {
	if (trace.gridPoints.count() == 0) {
		DebugDialog::debug("trace with no points");
		return;
	}

	int lastz = trace.gridPoints.at(0).z;
	Q_FOREACH (GridPoint gridPoint, trace.gridPoints) {
		if (gridPoint.z != lastz) {
			for (int y = -m_halfGridViaSize; y <= m_halfGridViaSize; y++) {
				for (int x = -m_halfGridViaSize; x <= m_halfGridViaSize; x++) {
					m_displayImage[1]->setPixel(x + gridPoint.x, y + gridPoint.y, 0x80ff0000);
				}
			}
			lastz = gridPoint.z;
		}
		else {
			m_displayImage[lastz]->setPixel(gridPoint.x, gridPoint.y, m_traceColors[lastz]);
		}
	}

	if (trace.flags) {
		GridPoint gridPoint = trace.gridPoints.first();
		int xl, xr;
		if (trace.flags & JumperLeft) {
			xl = -(m_halfGridJumperSize * 2);
			xr = 0;
		}
		else if (trace.flags & JumperRight) {
			xl = 0;
			xr = m_halfGridJumperSize * 2;
		}
		else {
			xl = -m_halfGridJumperSize;
			xr = m_halfGridJumperSize;
		}
		for (int y = -m_halfGridJumperSize; y <= m_halfGridJumperSize; y++) {
			for (int x = xl; x <= xr; x++) {
				m_displayImage[0]->setPixel(x + gridPoint.x, y + gridPoint.y, 0x800000ff);
			}
		}
	}
}

void MazeRouter::traceObstacles(QList<Trace> & traces, int netIndex, Grid * grid, int ikeepout) {
	// treat traces from previous nets as obstacles
	Q_FOREACH (Trace trace, traces) {
		if (trace.netIndex == netIndex) continue;

		int lastZ = trace.gridPoints.at(0).z;
		Q_FOREACH (GridPoint gridPoint, trace.gridPoints) {
			if (gridPoint.z != lastZ) {
				for (int y = -m_halfGridViaSize; y <= m_halfGridViaSize; y++) {
					for (int x = -m_halfGridViaSize; x <= m_halfGridViaSize; x++) {
						grid->setAt(gridPoint.x + x, gridPoint.y + y, 0, GridBoardObstacle);
						grid->setAt(gridPoint.x + x, gridPoint.y + y, 1, GridBoardObstacle);
					}
				}
				lastZ = gridPoint.z;
			}
			else {
				for (int y = -ikeepout; y <= ikeepout; y++) {
					for (int x = -ikeepout; x <= ikeepout; x++) {
						grid->setAt(gridPoint.x + x, gridPoint.y + y, gridPoint.z, GridBoardObstacle);
					}
				}
			}

		}

		if (trace.flags) {
			GridPoint gridPoint = trace.gridPoints.first();
			// jumper is always centered in this case
			for (int y = -m_halfGridJumperSize; y <= m_halfGridJumperSize; y++) {
				for (int x = -m_halfGridJumperSize; x <= m_halfGridJumperSize; x++) {
					grid->setAt(gridPoint.x + x, gridPoint.y + y, 0, GridBoardObstacle);
					if (m_bothSidesNow) {
						grid->setAt(gridPoint.x + x, gridPoint.y + y, 1, GridBoardObstacle);
					}
				}
			}
		}
	}
}

void MazeRouter::traceAvoids(QList<Trace> & traces, int netIndex, RouteThing & routeThing) {
	// treat traces from previous nets as semi-obstacles
	routeThing.avoids.clear();
	Q_FOREACH (Trace trace, traces) {
		if (trace.netIndex == netIndex) continue;

		Q_FOREACH (GridPoint gridPoint, trace.gridPoints) {
			for (int y = -m_keepoutGridInt; y <= m_keepoutGridInt; y++) {
				for (int x = -m_keepoutGridInt; x <= m_keepoutGridInt; x++) {
					GridValue val = m_grid->at(gridPoint.x + x, gridPoint.y + y, 0);
					if (val == GridPartObstacle || val == GridBoardObstacle || val == GridSource || val == GridTarget) continue;

					m_grid->setAt(gridPoint.x + x, gridPoint.y + y, 0, GridAvoid);
					routeThing.avoids.insert(((gridPoint.y + y) * m_grid->x) + x + gridPoint.x);
				}
			}
		}

		if (trace.flags) {
			GridPoint gridPoint = trace.gridPoints.first();
			int xl, xr;
			if (gridPoint.flags & GridPointJumperLeft) {
				xl = -(m_halfGridJumperSize * 2);
				xr = 0;
			}
			else {
				xl = 0;
				xr = m_halfGridJumperSize * 2;
			}

			for (int y = -m_halfGridJumperSize; y <= m_halfGridJumperSize; y++) {
				for (int x = xl; x <= xr; x++) {
					m_grid->setAt(gridPoint.x + x, gridPoint.y + y, 0, GridBoardObstacle);
				}
			}
		}
	}
}

void MazeRouter::cleanUpNets(NetList & netList) {
	Q_FOREACH(Net * net, netList.nets) {
		delete net;
	}
	netList.nets.clear();
	Autorouter::cleanUpNets();
}

void MazeRouter::createTraces(NetList & netList, Score & bestScore, QUndoCommand * parentCommand) {
	QMultiHash<int, Via *> allVias;
	QMultiHash<int, JumperItem *> allJumperItems;
	QMultiHash<int, SymbolPaletteItem *> allNetLabels;
	QMultiHash<int, QList< QPointer<TraceWire> > > allBundles;

	ConnectionThing connectionThing;

	Q_EMIT setMaximumProgress(bestScore.ordering.order.count() * 2);
	Q_EMIT setProgressMessage2(tr("Optimizing traces..."));

	int progress = 0;
	Q_FOREACH (int netIndex, bestScore.ordering.order) {
		Q_EMIT setProgressValue(progress++);
		//DebugDialog::debug(QString("tracing net %1").arg(netIndex));
		QList<Trace> traces = bestScore.traces.values(netIndex);
		std::sort(traces.begin(), traces.end(), byOrder);

		TraceThing traceThing;
		traceThing.jumperItem = nullptr;
		traceThing.netLabel = nullptr;
		traceThing.topLeft = m_maxRect.topLeft();
		int newTraceIndex = 0;

		Net * net = netList.nets.at(netIndex);

		for (int tix = 0; tix < traces.count(); tix++) {
			Trace trace = traces.at(tix);
			QList<GridPoint> gridPoints = trace.gridPoints;
			// TODO: nicer curve-fitting
			removeColinear(gridPoints);
			removeSteps(gridPoints);

			if (trace.flags & JumperStart) {
				Trace trace2 = traces.at(tix + 1);
				traceThing.nextTraceStart = trace2.gridPoints.first();
			}

			createTrace(trace, gridPoints, traceThing, connectionThing, net);
			QList< QPointer<TraceWire> > bundle;
			if (traceThing.newTraces.count() > newTraceIndex) {
				ViewLayer::ViewLayerID viewLayerID = traceThing.newTraces.at(newTraceIndex)->viewLayerID();
				for (; newTraceIndex < traceThing.newTraces.count(); newTraceIndex++) {
					TraceWire * traceWire = traceThing.newTraces.at(newTraceIndex);
					if (traceWire->viewLayerID() != viewLayerID) {
						allBundles.insert(netIndex, bundle);
						bundle.clear();
						viewLayerID = traceWire->viewLayerID();
					}
					bundle << traceWire;
				}
			}
			else {
				DebugDialog::debug("create trace failed");
			}
			allBundles.insert(netIndex, bundle);
		}
		Q_FOREACH (SymbolPaletteItem * netLabel, traceThing.newNetLabels) {
			allNetLabels.insert(netIndex, netLabel);
		}
		Q_FOREACH (Via * via, traceThing.newVias) {
			allVias.insert(netIndex, via);
		}
		Q_FOREACH (JumperItem * jumperItem, traceThing.newJumperItems) {
			allJumperItems.insert(netIndex, jumperItem);
		}
	}

	//DebugDialog::debug("before optimize");
	optimizeTraces(bestScore.ordering.order, allBundles, allVias, allJumperItems, allNetLabels, netList, connectionThing);
	//DebugDialog::debug("after optimize");

	Q_FOREACH (SymbolPaletteItem * netLabel, allNetLabels) {
		addNetLabelToUndo(netLabel, parentCommand);
	}
	Q_FOREACH (Via * via, allVias) {
		addViaToUndo(via, parentCommand);
	}
	Q_FOREACH (JumperItem * jumperItem, allJumperItems) {
		addJumperToUndo(jumperItem, parentCommand);
	}

	Q_FOREACH (QList< QPointer<TraceWire> > bundle, allBundles) {
		Q_FOREACH (TraceWire * traceWire, bundle) {
			addWireToUndo(traceWire, parentCommand);
		}
	}

	Q_FOREACH (ConnectorItem * source, connectionThing.sd.uniqueKeys()) {
		Q_FOREACH (ConnectorItem * dest, connectionThing.values(source)) {
			addConnectionToUndo(source, dest, parentCommand);
		}
	}

	QList<ModelPart *> modelParts;
	Q_FOREACH (QList< QPointer<TraceWire> > bundle, allBundles) {
		Q_FOREACH (TraceWire * traceWire, bundle) {
			if (traceWire) {
				modelParts << traceWire->modelPart();
				delete traceWire;
			}
		}
	}

	Q_FOREACH (Via * via, allVias.values()) {
		via->removeLayerKin();
		modelParts << via->modelPart();
		delete via;
	}
	Q_FOREACH (JumperItem * jumperItem, allJumperItems.values()) {
		jumperItem->removeLayerKin();
		modelParts << jumperItem->modelPart();
		delete jumperItem;
	}
	Q_FOREACH (SymbolPaletteItem * netLabel, allNetLabels.values()) {
		modelParts << netLabel->modelPart();
		delete netLabel;
	}
	Q_FOREACH (ModelPart * modelPart, modelParts) {
		modelPart->setParent(nullptr);
		delete modelPart;
	}

	DebugDialog::debug("create traces complete");
}

void MazeRouter::createTrace(Trace & trace, QList<GridPoint> & gridPoints, TraceThing & traceThing, ConnectionThing & connectionThing, Net * net)
{
	//DebugDialog::debug(QString("create trace net:%1").arg(net->id));
	if (trace.flags & JumperStart) {
		if (m_pcbType) {
			long newID = ItemBase::getNextID();
			ViewGeometry viewGeometry;
			ItemBase * itemBase = m_sketchWidget->addItem(m_sketchWidget->referenceModel()->retrieveModelPart(ModuleIDNames::JumperModuleIDName),
			                      ViewLayer::NewTop, BaseCommand::SingleView, viewGeometry, newID, -1, nullptr);

			traceThing.jumperItem = dynamic_cast<JumperItem *>(itemBase);
			traceThing.jumperItem->setAutoroutable(true);
			m_sketchWidget->scene()->addItem(traceThing.jumperItem);
			QPointF c1 = getPixelCenter(trace.gridPoints.first(), traceThing.topLeft, m_gridPixels);
			QPointF c2 = getPixelCenter(traceThing.nextTraceStart, traceThing.topLeft, m_gridPixels);
			traceThing.jumperItem->resize(c1, c2);
			traceThing.newJumperItems << traceThing.jumperItem;
		}
		else {
			traceThing.netLabel = makeNetLabel(trace.gridPoints.first(), nullptr, trace.flags);
			traceThing.newNetLabels << traceThing.netLabel;
		}
	}
	else if (trace.flags & JumperEnd) {
		if (m_pcbType) {
			// keep the jumperItem we have from JumperStart
		}
		else {
			traceThing.netLabel = makeNetLabel(trace.gridPoints.first(), traceThing.netLabel, trace.flags);
			traceThing.newNetLabels << traceThing.netLabel;
		}
	}
	else traceThing.jumperItem = nullptr;

	bool onTraceS, onTraceD;
	QPointF traceAnchorS, traceAnchorD;
	ConnectorItem * sourceConnectorItem = nullptr;
	if (traceThing.jumperItem) {
		onTraceS = onTraceD = false;
		sourceConnectorItem = (trace.flags & JumperStart) ? traceThing.jumperItem->connector0() : traceThing.jumperItem->connector1();
	}
	else if (traceThing.netLabel) {
		sourceConnectorItem = traceThing.netLabel->connector0();
	}
	else {
		sourceConnectorItem = findAnchor(gridPoints.first(), traceThing, net, traceAnchorS, onTraceS, nullptr);
	}
	if (sourceConnectorItem == nullptr) {
		DebugDialog::debug("missing source connector");
		return;
	}

	ConnectorItem * destConnectorItem = findAnchor(gridPoints.last(), traceThing, net, traceAnchorD, onTraceD, sourceConnectorItem);
	if (destConnectorItem == nullptr) {

		/*
		GridPoint gp = gridPoints.last();
		for (int x = gp.x - 5; x < gp.x + 5; x++) {
		    m_displayImage[gp.z]->setPixel(x, gp.y, 0xff000000);
		}
		for (int y = gp.y - 5; y < gp.y + 5; y++) {
		    m_displayImage[gp.z]->setPixel(gp.x, y, 0xff000000);
		}
		updateDisplay(gp.z);
		*/

		DebugDialog::debug("missing dest connector");
		return;
	}

	//if (sourceConnectorItem->attachedTo() == destConnectorItem->attachedTo()) {
	//    sourceConnectorItem->debugInfo("source");
	//    destConnectorItem->debugInfo("dest");
	//}

	QPointF sourcePoint = sourceConnectorItem->sceneAdjustedTerminalPoint(nullptr);
	QPointF destPoint = destConnectorItem->sceneAdjustedTerminalPoint(nullptr);

	bool skipFirst = false;
	bool skipLast = false;

	GridPoint gp = gridPoints.last();
	QPointF center = getPixelCenter(gp, traceThing.topLeft, m_gridPixels);
	if (!atLeast(center, destPoint)) {
		// don't need this last point
		skipLast = true;
	}

	gp = gridPoints.first();
	center = getPixelCenter(gp, traceThing.topLeft, m_gridPixels);
	if (!atLeast(center, sourcePoint)) {
		skipFirst = true;
	}

	// convert grid-based points to normal svg-space points and add the inbetween points necessitated by removeSteps()
	QList<PointZ> newPoints;
	for (int i = 0; i < gridPoints.count(); i++) {
		GridPoint gp1 = gridPoints.at(i);
		QPointF c1 = getPixelCenter(gp1, traceThing.topLeft, m_gridPixels);
		PointZ v1(c1, gp1.z);
		newPoints << v1;
		if ((gp1.flags & GridPointStepStart) == 0) continue;

		GridPoint gp2 = gridPoints.at(i + 1);
		QPointF c2 = getPixelCenter(gp2, traceThing.topLeft, m_gridPixels);

		QPointF p = getStepPoint(c1, gp1.flags, m_gridPixels);
		PointZ v2(p, gp1.z);
		newPoints << v2;

		QPointF q = getStepPoint(c2, gp2.flags, m_gridPixels);
		PointZ v3(q, gp2.z);
		newPoints << v3;

		//DebugDialog::debug(QString("remove2 %1,%2 %3,%4").arg(c1.x()).arg(c1.y()).arg(p.x()).arg(p.y()));
		//DebugDialog::debug(QString("\t%1,%2 %3,%4").arg(q.x()).arg(q.y()).arg(c2.x()).arg(c2.y()));

	}

	if (skipLast) {
		newPoints.takeLast();
	}
	PointZ point = newPoints.takeFirst();
	if (skipFirst) {
		point = newPoints.takeFirst();
	}

	int lastz = point.z;
	ConnectorItem * nextSource = nullptr;
	if (onTraceS) {
		if (!atLeast(sourcePoint, traceAnchorS)) {
			onTraceS = false;
		}
		else if (atLeast(point.p, traceAnchorS)) {
			onTraceS = false;
		}
	}
	if (onTraceS) {
		TraceWire * traceWire1 = drawOneTrace(sourcePoint, traceAnchorS, m_standardWireWidth, lastz == 0 ? ViewLayer::NewBottom : ViewLayer::NewTop);
		connectionThing.add(sourceConnectorItem, traceWire1->connector0());
		traceThing.newTraces << traceWire1;

		TraceWire* traceWire2 = drawOneTrace(traceAnchorS, point.p, m_standardWireWidth, lastz == 0 ? ViewLayer::NewBottom : ViewLayer::NewTop);
		connectionThing.add(traceWire1->connector1(), traceWire2->connector0());
		nextSource = traceWire2->connector1();
		traceThing.newTraces << traceWire2;
	}
	else {
		TraceWire * traceWire = drawOneTrace(sourcePoint, point.p, m_standardWireWidth, lastz == 0 ? ViewLayer::NewBottom : ViewLayer::NewTop);
		connectionThing.add(sourceConnectorItem, traceWire->connector0());
		nextSource = traceWire->connector1();
		traceThing.newTraces << traceWire;
	}

	Q_FOREACH (PointZ newPoint, newPoints) {
		if (newPoint.z == lastz) {
			TraceWire * traceWire = drawOneTrace(point.p, newPoint.p, m_standardWireWidth, lastz == 0 ? ViewLayer::NewBottom : ViewLayer::NewTop);
			connectionThing.add(nextSource, traceWire->connector0());
			nextSource = traceWire->connector1();
			traceThing.newTraces << traceWire;
		}
		else {
			long newID = ItemBase::getNextID();
			ViewGeometry viewGeometry;
			double ringThickness, holeSize;
			m_sketchWidget->getViaSize(ringThickness, holeSize);
			double halfVia = (ringThickness + ringThickness + holeSize) / 2;

			viewGeometry.setLoc(QPointF(newPoint.p.x() - halfVia - Hole::OffsetPixels, newPoint.p.y() - halfVia - Hole::OffsetPixels));
			ItemBase * itemBase = m_sketchWidget->addItem(m_sketchWidget->referenceModel()->retrieveModelPart(ModuleIDNames::ViaModuleIDName),
			                      ViewLayer::NewTop, BaseCommand::SingleView, viewGeometry, newID, -1, nullptr);

			//DebugDialog::debug(QString("back from adding via %1").arg((long) itemBase, 0, 16));
			Via * via = qobject_cast<Via *>(itemBase);
			via->setAutoroutable(true);
			via->setHoleSize(QString("%1in,%2in") .arg(holeSize / GraphicsUtils::SVGDPI) .arg(ringThickness / GraphicsUtils::SVGDPI), false);

			connectionThing.add(nextSource, via->connectorItem());
			nextSource = via->connectorItem();
			traceThing.newVias << via;
			lastz = newPoint.z;
		}
		point = newPoint;
	}
	if (onTraceD) {
		if (!atLeast(destPoint, traceAnchorD)) {
			onTraceD = false;
		}
		else if (!atLeast(point.p, traceAnchorD)) {
			onTraceD = false;
		}
	}
	if (onTraceD) {
		TraceWire * traceWire1 = drawOneTrace(point.p, traceAnchorD, m_standardWireWidth, lastz == 0 ? ViewLayer::NewBottom : ViewLayer::NewTop);
		connectionThing.add(nextSource, traceWire1->connector0());
		traceThing.newTraces << traceWire1;

		TraceWire * traceWire2 = drawOneTrace(traceAnchorD, destPoint, m_standardWireWidth, lastz == 0 ? ViewLayer::NewBottom : ViewLayer::NewTop);
		connectionThing.add(traceWire1->connector1(), traceWire2->connector0());
		connectionThing.add(traceWire2->connector1(), destConnectorItem);
		traceThing.newTraces << traceWire2;
	}
	else {
		TraceWire * traceWire = drawOneTrace(point.p, destPoint, m_standardWireWidth, lastz == 0 ? ViewLayer::NewBottom : ViewLayer::NewTop);
		connectionThing.add(nextSource, traceWire->connector0());
		connectionThing.add(traceWire->connector1(), destConnectorItem);
		traceThing.newTraces << traceWire;
	}
}

ConnectorItem * MazeRouter::findAnchor(GridPoint gp, TraceThing & traceThing, Net * net, QPointF & p, bool & onTrace, ConnectorItem * already)
{
	QRectF gridRect(gp.x * m_gridPixels + traceThing.topLeft.x(), gp.y * m_gridPixels + traceThing.topLeft.y(), m_gridPixels, m_gridPixels);
	ConnectorItem * connectorItem = findAnchor(gp, gridRect, traceThing, net, p, onTrace, already);

	if (connectorItem != nullptr) {
		//if (connectorItem->attachedToID() == 9781620) {
		//    connectorItem->debugInfo("9781620");
		//}

		if (connectorItem->attachedToItemType() != ModelPart::Wire) {
			return connectorItem;
		}

		// otherwise keep looking
	}

	gridRect.adjust(-m_gridPixels, -m_gridPixels, m_gridPixels, m_gridPixels);
	return findAnchor(gp, gridRect, traceThing, net, p, onTrace, already);
}

ConnectorItem * MazeRouter::findAnchor(GridPoint gp, const QRectF & gridRect, TraceThing & traceThing, Net * net, QPointF & p, bool & onTrace, ConnectorItem * already)
{
	ConnectorItem * alreadyCross = nullptr;
	if (already != nullptr) alreadyCross = already->getCrossLayerConnectorItem();
	QList<TraceWire *> traceWires;
	QList<ConnectorItem *> traceConnectorItems;
	Q_FOREACH (QGraphicsItem * item, m_sketchWidget->scene()->items(gridRect)) {
		auto * connectorItem = dynamic_cast<ConnectorItem *>(item);
		if (connectorItem) {
			if (!connectorItem->attachedTo()->isEverVisible()) continue;
			if (connectorItem == already) continue;
			if (connectorItem == alreadyCross) continue;

			if (already != nullptr && connectorItem->attachedTo() == already->attachedTo()) {
				ConnectorItem * cross = connectorItem->getCrossLayerConnectorItem();
				if (cross != nullptr) {
					if (cross == already) continue;
					if (cross == alreadyCross) continue;
				}
			}

			//connectorItem->debugInfo("candidate");

			bool isCandidate =
			    (gp.z == 0 && m_sketchWidget->attachedToBottomLayer(connectorItem)) ||
			    (gp.z == 1 && m_sketchWidget->attachedToTopLayer(connectorItem))
			    ;
			if (!isCandidate) continue;

			bool traceConnector = false;
			if (net->net->contains(connectorItem)) ;
			else {
				auto * traceWire = qobject_cast<TraceWire *>(connectorItem->attachedTo());
				if (traceWire == nullptr) {
					Via * via = qobject_cast<Via *>(connectorItem->attachedTo()->layerKinChief());
					if (via == nullptr) isCandidate = false;
					else isCandidate = traceThing.newVias.contains(via);
				}
				else {
					traceConnector = isCandidate = traceThing.newTraces.contains(traceWire);
				}
			}
			if (!isCandidate) continue;

			if (traceConnector) {
				traceConnectorItems << connectorItem;
				continue;
			}
			else {
				//if (traceConnectorItems.count() > 0) {
				//    connectorItem->debugInfo("chose not trace");
				//}
				onTrace = false;
				p = connectorItem->sceneAdjustedTerminalPoint(nullptr);
				return connectorItem;
			}
		}

		auto * traceWire = dynamic_cast<TraceWire *>(item);
		if (traceWire == nullptr) continue;
		if (!traceWire->isEverVisible()) continue;

		// only do traces if no connectorItem is found
		traceWires.append(traceWire);
	}

	if (traceConnectorItems.count() > 0) {
		//if (traceConnectorItems.count() > 1) {
		//    foreach (ConnectorItem * connectorItem, traceConnectorItems) {
		//        connectorItem->debugInfo("on trace");
		//    }
		//}
		onTrace = false;
		ConnectorItem * connectorItem = traceConnectorItems.takeLast();
		p = connectorItem->sceneAdjustedTerminalPoint(nullptr);
		return connectorItem;
	}

	Q_FOREACH (TraceWire * traceWire, traceWires) {
		//traceWire->debugInfo("trace candidate");
		bool isCandidate = (gp.z == 0 && m_sketchWidget->attachedToBottomLayer(traceWire->connector0()))
		                   || (gp.z == 1 && m_sketchWidget->attachedToTopLayer(traceWire->connector0()));
		if (!isCandidate) continue;

		if (traceThing.newTraces.contains(traceWire)) ;
		else if (net->net->contains(traceWire->connector0())) ;
		else continue;

		onTrace = true;
		QPointF center = gridRect.center();
		QPointF p0 = traceWire->connector0()->sceneAdjustedTerminalPoint(nullptr);
		QPointF p1 = traceWire->connector1()->sceneAdjustedTerminalPoint(nullptr);
		double d0 = GraphicsUtils::distanceSqd(p0, center);
		double d1 = GraphicsUtils::distanceSqd(p1, center);
		double dx, dy, distanceSegment;
		bool atEndpoint = false;
		GraphicsUtils::distanceFromLine(center.x(), center.y(), p0.x(), p0.y(), p1.x(), p1.y(), dx, dy, distanceSegment, atEndpoint);
		if (atEndpoint) {
			DebugDialog::debug("at endpoint shouldn't happen");
		}
		p.setX(dx);
		p.setY(dy);
		if (d0 <= d1) {
			return traceWire->connector0();
		}
		else {
			return traceWire->connector1();
		}
	}

	DebugDialog::debug("overlap not found");
	return nullptr;
}

void MazeRouter::removeColinear(QList<GridPoint> & gridPoints) {
	// eliminate redundant colinear points
	int ix = 0;
	while (ix < gridPoints.count() - 2) {
		GridPoint p1 = gridPoints[ix];
		GridPoint p2 = gridPoints[ix + 1];
		if (p1.z == p2.z) {
			GridPoint p3 = gridPoints[ix + 2];
			if (p2.z == p3.z) {
				if (p1.x == p2.x && p2.x == p3.x) {
					gridPoints.removeAt(ix + 1);
					continue;
				}
				else if (p1.y == p2.y && p2.y == p3.y) {
					gridPoints.removeAt(ix + 1);
					continue;
				}
			}
		}
		ix++;
	}
}

void MazeRouter::removeSteps(QList<GridPoint> & gridPoints) {
	// eliminate 45 degree runs
	for (int ix = 0; ix < gridPoints.count() - 2; ix++) {
		removeStep(ix, gridPoints);
	}
}

void MazeRouter::removeStep(int ix, QList<GridPoint> & gridPoints) {
	GridPoint p1 = gridPoints[ix];
	GridPoint p2 = gridPoints[ix + 1];
	if (p1.z != p2.z) return;

	GridPoint p3 = gridPoints[ix + 2];
	if (p2.z != p3.z) return;

	int dx1 = p2.x - p1.x;
	int dy1 = p2.y - p1.y;
	if ((qAbs(dx1) == 1 && dy1 == 0) || (dx1 == 0 && qAbs(dy1) == 1)) ;
	else return;

	int dx2 = p3.x - p2.x;
	int dy2 = p3.y - p2.y;
	bool step = false;
	if (dx1 == 0) {
		step = (dy2 == 0 && qAbs(dx2) == 1);
	}
	else {
		step = (dx2 == 0 && qAbs(dy2) == 1);
	}
	if (!step) return;

	int count = 1;
	int flag = 0;
	for (int jx = ix + 3; jx < gridPoints.count(); jx++, flag++) {
		GridPoint p4 = gridPoints[jx];
		int dx3 = p4.x - p3.x;
		int dy3 = p4.y - p3.y;
		if (flag % 2 == 0) {
			if (dx3 == dx1 && dy3 == dy1) {
				count++;
			}
			else break;
		}
		else {
			if (dx3 == dx2 && dy3 == dy2) {
				count++;
			}
			else break;
		}
		p2 = p3;
		p3 = p4;
	}

	gridPoints[ix].flags = getStepFlag(gridPoints[ix], gridPoints[ix + 1]) | GridPointStepStart;
	int jx = ix + count + 1;
	gridPoints[jx].flags = getStepFlag(gridPoints[jx], gridPoints[jx - 1]);

	/*
	QPointF topLeft = m_maxRect.topLeft();
	DebugDialog::debug(QString("removing %1").arg(count));
	for (int i = 0; i < count + 2; i++) {
	    QPointF p = getPixelCenter(gridPoints[ix + i], topLeft, m_gridPixels);
	    DebugDialog::debug(QString("\t%1,%2 %3,%4").arg(gridPoints[ix + i].x).arg(gridPoints[ix + i].y).arg(p.x()).arg(p.y()));
	}
	*/

	while (--count >= 0) {
		gridPoints.removeAt(ix + 1);
	}

}

void MazeRouter::addConnectionToUndo(ConnectorItem * from, ConnectorItem * to, QUndoCommand * parentCommand)
{
	if (from == nullptr || to == nullptr) return;

	auto * ccc = new ChangeConnectionCommand(m_sketchWidget, BaseCommand::CrossView,
	        from->attachedToID(), from->connectorSharedID(),
	        to->attachedToID(), to->connectorSharedID(),
	        ViewLayer::specFromID(from->attachedToViewLayerID()),
	        true, parentCommand);
	ccc->setUpdateConnections(false);
}

void MazeRouter::addViaToUndo(Via * via, QUndoCommand * parentCommand) {
	new AddItemCommand(m_sketchWidget, BaseCommand::CrossView, ModuleIDNames::ViaModuleIDName, via->viewLayerPlacement(), via->getViewGeometry(), via->id(), false, -1, parentCommand);
	new SetPropCommand(m_sketchWidget, via->id(), "hole size", via->holeSize(), via->holeSize(), true, parentCommand);
	new CheckStickyCommand(m_sketchWidget, BaseCommand::SingleView, via->id(), false, CheckStickyCommand::RemoveOnly, parentCommand);
}

void MazeRouter::addJumperToUndo(JumperItem * jumperItem, QUndoCommand * parentCommand) {
	jumperItem->saveParams();
	QPointF pos, c0, c1;
	jumperItem->getParams(pos, c0, c1);

	new AddItemCommand(m_sketchWidget, BaseCommand::CrossView, ModuleIDNames::JumperModuleIDName, jumperItem->viewLayerPlacement(), jumperItem->getViewGeometry(), jumperItem->id(), false, -1, parentCommand);
	new ResizeJumperItemCommand(m_sketchWidget, jumperItem->id(), pos, c0, c1, pos, c0, c1, parentCommand);
	new CheckStickyCommand(m_sketchWidget, BaseCommand::SingleView, jumperItem->id(), false, CheckStickyCommand::RemoveOnly, parentCommand);
}

void MazeRouter::addNetLabelToUndo(SymbolPaletteItem * netLabel, QUndoCommand * parentCommand) {
	new AddItemCommand(m_sketchWidget, BaseCommand::CrossView, netLabel->moduleID(), netLabel->viewLayerPlacement(), netLabel->getViewGeometry(), netLabel->id(), false, -1, parentCommand);
	new SetPropCommand(m_sketchWidget, netLabel->id(), "label", netLabel->getLabel(), netLabel->getLabel(), true, parentCommand);
}

void MazeRouter::insertTrace(Trace & newTrace, int netIndex, Score & currentScore, int viaCount, bool incRouted) {
	if (newTrace.gridPoints.count() == 0) {
		DebugDialog::debug("trace with no points");
		return;
	}

	//DebugDialog::debug(QString("insert trace %1").arg(newTrace.gridPoints.count()));

	newTrace.netIndex = netIndex;
	newTrace.order = currentScore.traces.values(netIndex).count();
	currentScore.traces.insert(netIndex, newTrace);
	if (incRouted) {
		currentScore.routedCount.insert(netIndex, currentScore.routedCount.value(netIndex) + 1);
		currentScore.totalRoutedCount++;
	}
	currentScore.viaCount.insert(netIndex, currentScore.viaCount.value(netIndex, 0) + viaCount);
	currentScore.totalViaCount += viaCount;
	displayTrace(newTrace);

	//DebugDialog::debug(QString("done insert trace"));

}

void MazeRouter::incCommandProgress() {
	Q_EMIT setProgressValue(m_cleanupCount++);

	int modulo = m_commandCount / 100;
	if (modulo > 0 && m_cleanupCount % modulo == 0) {
		ProcessEventBlocker::processEvents();
	}
	//DebugDialog::debug(QString("cleanup:%1, cc:%2").arg(m_cleanupCount).arg(m_commandCount));
}

void MazeRouter::setMaxCycles(int maxCycles)
{
	Autorouter::setMaxCycles(maxCycles);
	Q_EMIT setMaximumProgress(maxCycles);
}

SymbolPaletteItem * MazeRouter::makeNetLabel(GridPoint & center, SymbolPaletteItem * pairedNetLabel, uchar traceFlags) {
	// flags & JumperLeft means position the netlabel to the left of center, the netlabel points right

	if (m_netLabelIndex < 0) {
		m_netLabelIndex = 0;
		Q_FOREACH (QGraphicsItem * item, m_sketchWidget->scene()->items()) {
			auto * netLabel = dynamic_cast<SymbolPaletteItem *>(item);
			if (netLabel == nullptr || !netLabel->isOnlyNetLabel()) continue;

			bool ok;
			int ix = netLabel->getLabel().toInt(&ok);
			if (ok && ix > m_netLabelIndex) m_netLabelIndex = ix;
		}
	}

	if (pairedNetLabel == nullptr) {
		m_netLabelIndex++;
	}

	long newID = ItemBase::getNextID();
	ViewGeometry viewGeometry;
	ItemBase * itemBase = m_sketchWidget->addItem(m_sketchWidget->referenceModel()->retrieveModelPart(traceFlags & JumperLeft ? ModuleIDNames::NetLabelModuleIDName : ModuleIDNames::LeftNetLabelModuleIDName),
	                      ViewLayer::NewBottom, BaseCommand::SingleView, viewGeometry, newID, -1, nullptr);

	auto * netLabel = dynamic_cast<SymbolPaletteItem *>(itemBase);
	netLabel->setAutoroutable(true);
	netLabel->setLabel(QString::number(m_netLabelIndex));
	QPointF tl = m_maxRect.topLeft();
	QPointF c1 = getPixelCenter(center, tl, m_gridPixels);
	QSizeF size = netLabel->boundingRect().size();
	int x = c1.x();
	if (traceFlags & JumperLeft) {
		x -= size.width();
	}
	netLabel->setPos(x, c1.y() - (size.height() / 2));
	//DebugDialog::debug(QString("ix:%1 tl:%2 %3,%4").arg(m_netLabelIndex).arg(traceFlags).arg(x).arg(c1.y() - (size.height() / 2)));
	netLabel->saveGeometry();
	return netLabel;
}

void MazeRouter::routeJumper(int netIndex, RouteThing & routeThing, Score & currentScore)
{
	if (routeThing.bestDistanceToTarget == std::numeric_limits<double>::max() || routeThing.bestDistanceToSource == std::numeric_limits<double>::max()) {
		// never got started on this route
		return;
	}

	//DebugDialog::debug(QString("route jumper %1, %2").arg(routeThing.bestDistanceToSource).arg(routeThing.bestDistanceToTarget));

	//updateDisplay(0);
	//if (m_bothSidesNow) updateDisplay(1);

	bool routeBothEnds = true;
	Trace sourceTrace;
	if (!m_pcbType) {
		//  is there already a net label on this net?

		// TODO: which subnet has the jumper?
		Q_FOREACH (Trace trace, currentScore.traces.values(netIndex)) {
			if (trace.flags & JumperStart) {
				sourceTrace = trace;
				routeBothEnds = false;
				break;
			}
		}
	}

	//updateDisplay(m_grid, 0);
	//if (m_bothSidesNow) updateDisplay(m_grid, 1);

	GridPoint gp1 = lookForJumper(routeThing.bestLocationToTarget, GridSource, routeThing.gridTargetPoint);
	if (gp1.baseCost == GridBoardObstacle) return;

	GridPoint gp2 = lookForJumper(routeThing.bestLocationToSource, GridTarget, routeThing.gridSourcePoint);
	if (gp2.baseCost == GridBoardObstacle) return;

	int sourceViaCount = 0;
	if (routeBothEnds) {
		sourceTrace.flags = JumperStart;
		if (gp1.flags & GridPointJumperLeft) sourceTrace.flags |= JumperLeft;
		else if (gp1.flags & GridPointJumperRight) sourceTrace.flags |= JumperRight;
		sourceTrace.gridPoints = traceBack(gp1, m_grid, sourceViaCount, GridTarget, GridSource);   // trace back to source
	}

	Trace destTrace;
	destTrace.flags = JumperEnd;
	if (gp2.flags & GridPointJumperLeft) destTrace.flags |= JumperLeft;
	else if (gp2.flags & GridPointJumperRight) destTrace.flags |= JumperRight;
	int targetViaCount = 0;
	destTrace.gridPoints = traceBack(gp2, m_grid, targetViaCount, GridSource, GridTarget);          // trace back to target

	if (routeBothEnds) {
		insertTrace(sourceTrace, netIndex, currentScore, sourceViaCount, false);
	}
	insertTrace(destTrace, netIndex, currentScore, targetViaCount, true);
	updateDisplay(0);
	if (m_bothSidesNow) updateDisplay(1);

	clearExpansion(m_grid);
}

GridPoint MazeRouter::lookForJumper(GridPoint initial, GridValue targetValue, QPoint targetLocation) {
	QSet<int> already;
	std::priority_queue<GridPoint> pq;
	initial.qCost = 0;
	pq.push(initial);
	already.insert(gridPointInt(m_grid, initial));
	while (!pq.empty()) {
		GridPoint gp = pq.top();
		pq.pop();

		gp.baseCost = m_grid->at(gp.x, gp.y, gp.z);

		/*
		GridValue bc = gp.baseCost;
		if (targetValue == GridSource) bc ^= GridSourceFlag;
		bc *= 3;
		if (bc > 255) bc = 255;
		m_displayImage[gp.z]->setPixel(gp.x, gp.y, 0xff000000 | (bc << 16) | (bc << 8) | bc);
		updateDisplay(gp.z);
		*/

		if ((*m_jumperWillFitFunction)(gp, m_grid, m_halfGridJumperSize)) {
			if (targetValue == GridSource) gp.baseCost ^= GridSourceFlag;

			//m_displayImage[gp.z]->setPixel(gp.x, gp.y, 0xff0000ff);
			//updateDisplay(gp.z);
			//updateDisplay(gp.z);

			//QPointF p = getPixelCenter(gp, m_maxRect.topLeft(), m_gridPixels);
			//DebugDialog::debug(QString("jumper location %1").arg(gp.flags), p);

			return gp;
		}

		if (gp.x > 0) expandOneJ(gp, pq, -1, 0, 0, targetValue, targetLocation, already);
		if (gp.x < m_grid->x - 1) expandOneJ(gp, pq, 1, 0, 0, targetValue, targetLocation, already);
		if (gp.y > 0) expandOneJ(gp, pq, 0, -1, 0, targetValue, targetLocation, already);
		if (gp.y < m_grid->y - 1) expandOneJ(gp, pq, 0, 1, 0, targetValue, targetLocation, already);
		if (m_bothSidesNow) {
			if (gp.z > 0) expandOneJ(gp, pq, 0, 0, -1, targetValue, targetLocation, already);
			if (gp.z < m_grid->z - 1) expandOneJ(gp, pq, 0, 0, 1, targetValue, targetLocation, already);
		}
	}

	GridPoint failed;
	failed.baseCost = GridBoardObstacle;
	return failed;
}

void MazeRouter::expandOneJ(GridPoint & gridPoint, std::priority_queue<GridPoint> & pq, int dx, int dy, int dz, GridValue targetValue, QPoint targetLocation, QSet<int> & already)
{
	GridPoint next;
	next.x = gridPoint.x + dx;
	next.y = gridPoint.y + dy;
	next.z = gridPoint.z + dz;
	int gpi = gridPointInt(m_grid, next);
	if (already.contains(gpi)) return;

	already.insert(gpi);
	GridValue nextval = m_grid->at(next.x, next.y, next.z);
	if (nextval == GridPartObstacle || nextval == GridBoardObstacle || nextval == GridSource || nextval == GridTempObstacle || nextval == GridTarget || nextval == GridAvoid) return;
	else if (nextval == 0) return;
	else {
		// already been here: see if it's the right expansion
		if (targetValue == GridSource) {
			if ((nextval & GridSourceFlag) == 0) return;
		}
		else {
			if (nextval & GridSourceFlag) return;
		}
	}

	double d = (m_costFunction)(QPoint(next.x, next.y), targetLocation);
	next.qCost = d;
	next.baseCost = 0;

	//DebugDialog::debug(QString("pushing next %1 %2 %3, %4, %5").arg(gridPoint.x).arg(gridPoint.y).arg(gridPoint.z).arg(gridPoint.qCost).arg(routeThing.pq.size()));
	pq.push(next);
}

void MazeRouter::removeOffBoardAnd(bool isPCBType, bool removeSingletons, bool bothSides) {
	QRectF boardRect;
	if (m_board) boardRect = m_board->sceneBoundingRect();
	// remove any vias or jumperItems that will be deleted, also remove off-board items
	for (int i = m_allPartConnectorItems.count() - 1; i >= 0; i--) {
		QList<ConnectorItem *> * connectorItems = m_allPartConnectorItems.at(i);
		if (removeSingletons) {
			if (connectorItems->count() < 2) {
				connectorItems->clear();
			}
			else if (connectorItems->count() == 2) {
				if (connectorItems->at(0) == connectorItems->at(1)->getCrossLayerConnectorItem()) {
					connectorItems->clear();
				}
			}
		}
		for (int j = connectorItems->count() - 1; j >= 0; j--) {
			ConnectorItem * connectorItem = connectorItems->at(j);
			//connectorItem->debugInfo("pci");
			bool doRemove = false;
			if (connectorItem->attachedToItemType() == ModelPart::Via) {
				Via * via = qobject_cast<Via *>(connectorItem->attachedTo()->layerKinChief());
				doRemove = via->getAutoroutable();
			}
			else if (connectorItem->attachedToItemType() == ModelPart::Jumper) {
				auto * jumperItem = qobject_cast<JumperItem *>(connectorItem->attachedTo()->layerKinChief());
				doRemove = jumperItem->getAutoroutable();
			}
			else if (connectorItem->attachedToItemType() == ModelPart::Symbol) {
				auto * netLabel = qobject_cast<SymbolPaletteItem *>(connectorItem->attachedTo()->layerKinChief());
				doRemove = netLabel->getAutoroutable() && netLabel->isOnlyNetLabel();
			}
			if (!bothSides && connectorItem->attachedToViewLayerID() == ViewLayer::Copper1) doRemove = true;
			if (!doRemove && isPCBType) {
				if (!boardRect.contains(connectorItem->sceneBoundingRect())) {
					doRemove = true;
				}
			}
			if (doRemove) {
				connectorItems->removeAt(j);
			}
		}
		if (connectorItems->count() == 0) {
			m_allPartConnectorItems.removeAt(i);
			delete connectorItems;
		}
	}
}

void MazeRouter::optimizeTraces(QList<int> & order, QMultiHash<int, QList< QPointer<TraceWire> > > & bundles,
                                QMultiHash<int, Via *> & vias, QMultiHash<int, JumperItem *> & jumperItems, QMultiHash<int, SymbolPaletteItem *> & netLabels,
                                NetList & netList, ConnectionThing & connectionThing)
{
	QList<ViewLayer::ViewLayerPlacement> layerSpecs;
	layerSpecs << ViewLayer::NewBottom;
	if (m_bothSidesNow) layerSpecs << ViewLayer::NewTop;
	QRectF r2(0, 0, m_boardImage->width(), m_boardImage->height());
	QPointF topLeft = m_maxRect.topLeft();

	//QList<int> order2(order);
	//order2.append(order);

	int progress = order.count();

	Q_FOREACH (int netIndex, order) {
		Q_EMIT setProgressValue(progress++);
		Net * net = netList.nets.at(netIndex);
		Q_FOREACH (ViewLayer::ViewLayerPlacement layerSpec, layerSpecs) {
			fastCopy(m_boardImage, m_spareImage);

			QDomDocument * masterDoc = m_masterDocs.value(layerSpec);
			//QString before = masterDoc->toString();
			Markers markers;
			initMarkers(markers, m_pcbType);
			NetElements netElements;
			DRC::splitNetPrep(masterDoc, *(net->net), markers, netElements.net, netElements.alsoNet, netElements.notNet, true);
			Q_FOREACH (QDomElement element, netElements.net) {
				element.setTagName("g");
			}
			Q_FOREACH (QDomElement element, netElements.alsoNet) {
				element.setTagName("g");
			}

			ItemBase::renderOne(masterDoc, m_spareImage, r2);

			//QString after = masterDoc->toString();

			Q_FOREACH (QDomElement element, netElements.net) {
				element.setTagName(element.attribute("former"));
				element.removeAttribute("net");
			}
			Q_FOREACH (QDomElement element, netElements.alsoNet) {
				element.setTagName(element.attribute("former"));
				element.removeAttribute("net");
			}
			Q_FOREACH (QDomElement element, netElements.notNet) {
				element.removeAttribute("net");
			}

			QPainter painter;
			painter.begin(m_spareImage);
			QPen pen = painter.pen();
			pen.setColor(0xff000000);

			QBrush brush(QColor(0xff000000));
			painter.setBrush(brush);
			Q_FOREACH (int otherIndex, order) {
				if (otherIndex == netIndex) continue;

				Q_FOREACH(QList< QPointer<TraceWire> > bundle, bundles.values(otherIndex)) {
					if (bundle.count() == 0) continue;
					if (ViewLayer::specFromID(bundle.at(0)->viewLayerID()) != layerSpec) continue;

					pen.setWidthF((bundle.at(0)->wireWidth() + m_keepoutPixels + m_keepoutPixels) * OptimizeFactor);
					painter.setPen(pen);
					Q_FOREACH (TraceWire * traceWire, bundle) {
						if (traceWire == nullptr) continue;

						QPointF p1 = (traceWire->connector0()->sceneAdjustedTerminalPoint(nullptr) - topLeft) * OptimizeFactor;
						QPointF p2 = (traceWire->connector1()->sceneAdjustedTerminalPoint(nullptr) - topLeft) * OptimizeFactor;
						painter.drawLine(p1, p2);
					}
				}

				painter.setPen(Qt::NoPen);

				Q_FOREACH (Via * via, vias.values(otherIndex)) {
					QPointF p = (via->connectorItem()->sceneAdjustedTerminalPoint(nullptr) - topLeft) * OptimizeFactor;
					double rad = ((via->connectorItem()->sceneBoundingRect().width() / 2) + m_keepoutPixels) * OptimizeFactor;
					painter.drawEllipse(p, rad, rad);
				}
				Q_FOREACH (JumperItem * jumperItem, jumperItems.values(otherIndex)) {
					QPointF p = (jumperItem->connector0()->sceneAdjustedTerminalPoint(nullptr) - topLeft) * OptimizeFactor;
					double rad = ((jumperItem->connector0()->sceneBoundingRect().width() / 2) + m_keepoutPixels) * OptimizeFactor;
					painter.drawEllipse(p, rad, rad);
					p = (jumperItem->connector1()->sceneAdjustedTerminalPoint(nullptr) - topLeft) * OptimizeFactor;
					painter.drawEllipse(p, rad, rad);
				}
				Q_FOREACH (SymbolPaletteItem * netLabel, netLabels.values(otherIndex)) {
					QRectF r = netLabel->sceneBoundingRect();
					painter.drawRect((r.left() - topLeft.x() - m_keepoutPixels) * OptimizeFactor,
					                 (r.top() - topLeft.y() - m_keepoutPixels) * OptimizeFactor,
					                 (r.width() + m_keepoutPixels) * OptimizeFactor,
					                 (r.height() + m_keepoutPixels) * OptimizeFactor);
				}
			}

			Q_FOREACH (SymbolPaletteItem * netLabel, netLabels.values(netIndex)) {
				QRectF r = netLabel->sceneBoundingRect();
				painter.drawRect((r.left() - topLeft.x() - m_keepoutPixels) * OptimizeFactor,
				                 (r.top() - topLeft.y() - m_keepoutPixels) * OptimizeFactor,
				                 (r.width() + m_keepoutPixels) * OptimizeFactor,
				                 (r.height() + m_keepoutPixels) * OptimizeFactor);
			}

			painter.end();

#ifndef QT_NO_DEBUG
			//m_spareImage->save(FolderUtils::getUserDataStorePath("") + QString("/optimizeObstacles%1_%2.png").arg(netIndex, 2, 10, QChar('0')).arg(layerSpec));
#endif

			// finally test all combinations of each bundle
			//      identify traces in bundles with source and dest that cannot be deleted
			//      remove source/dest (delete and keep QPointers?)
			//          schematic view must replace with two 90-degree lines

			Q_FOREACH(QList< QPointer<TraceWire> > bundle, bundles.values(netIndex)) {
				if (bundle.count() == 0) continue;

				for (int i = bundle.count() - 1; i >= 0; i--) {
					TraceWire * traceWire = bundle.at(i);
					if (traceWire == nullptr) bundle.removeAt(i);
				}

				if (ViewLayer::specFromID(bundle.at(0)->viewLayerID()) != layerSpec) {
					// all wires in a single bundle are in the same layer
					continue;
				}

				/*
				QList<ConnectorItem *> tos = connectionThing.values(bundle.first()->connector0());
				foreach (ConnectorItem * to, tos) {
				    if (to->attachedToItemType() == ModelPart::Via) {
				        to->debugInfo("start hooked to via");
				    }
				}
				tos = connectionThing.values(bundle.last()->connector1());
				foreach (ConnectorItem * to, tos) {
				    if (to->attachedToItemType() == ModelPart::Via) {
				        to->debugInfo("end hooked to via");
				    }
				}
				*/

				QVector<QPointF> points(bundle.count() + 1, QPointF(0, 0));
				QVector<bool> splits(bundle.count() + 1, false);
				int index = 0;
				Q_FOREACH (TraceWire * traceWire, bundle) {
					if (connectionThing.multi(traceWire->connector0())) splits.replace(index, true);
					points.replace(index, traceWire->connector0()->sceneAdjustedTerminalPoint(nullptr));
					index++;
					if (connectionThing.multi(traceWire->connector1())) splits.replace(index, true);
					points.replace(index, traceWire->connector1()->sceneAdjustedTerminalPoint(nullptr));
				}

				splits.replace(0, false);
				splits.replace(splits.count() - 1, true);

				QList<QPointF> pointsSoFar;
				QList<TraceWire *> bundleSoFar;
				int startIndex = 0;
				for (int pix = 0; pix < points.count(); pix++) {
					pointsSoFar << points.at(pix);
					if (pix < points.count() - 1) {
						bundleSoFar << bundle.at(pix);
					}
					if (splits.at(pix)) {
						reducePoints(pointsSoFar, topLeft, bundleSoFar, startIndex, pix, connectionThing, netIndex, layerSpec);
						pointsSoFar.clear();
						bundleSoFar.clear();
						pointsSoFar << points.at(pix);
						if (pix < points.count() - 1) bundleSoFar << bundle.at(pix);
						startIndex = pix;
					}
				}
			}
		}
	}
}

void MazeRouter::reducePoints(QList<QPointF> & points, QPointF topLeft, QList<TraceWire *> & bundle, int startIndex, int endIndex, ConnectionThing & connectionThing, int netIndex, ViewLayer::ViewLayerPlacement layerSpec) {
	Q_UNUSED(netIndex);
	Q_UNUSED(layerSpec);
#ifndef QT_NO_DEBUG
	//int inc = 0;
#endif
	double width = bundle.at(0)->wireWidth() * OptimizeFactor;
	for (int separation = endIndex - startIndex; separation > 1; separation--) {
		for (int ix = 0; ix < points.count() - separation; ix++) {
			QPointF p1 = (points.at(ix) - topLeft) * OptimizeFactor;
			QPointF p2 = (points.at(ix + separation) - topLeft) * OptimizeFactor;
			double minX = qMax(0.0, qMin(p1.x(), p2.x()) - width);
			double minY = qMax(0.0, qMin(p1.y(), p2.y()) - width);
			double maxX = qMin(m_spareImage2->width() - 1.0, qMax(p1.x(), p2.x()) + width);
			double maxY = qMin(m_spareImage2->height() - 1.0, qMax(p1.y(), p2.y()) + width);
			int corners = 1;
			if (!m_pcbType) {
				if (qAbs(p1.x() - p2.x()) >= 1 && qAbs(p1.y() - p2.y()) >= 1) {
					corners = 2;
					if (separation == 2) continue;   // since we already have two lines, do nothing
				}
			}
			for (int corner = 0; corner < corners; corner++) {
				m_spareImage2->fill(0xffffffff);
				QPainter painter;
				painter.begin(m_spareImage2);
				QPen pen = painter.pen();
				pen.setColor(0xff000000);
				pen.setWidthF(width);
				painter.setPen(pen);
				if (corners == 1) {
					painter.drawLine(p1, p2);
				}
				else {
					if (corner == 0) {
						// vertical then horizontal
						painter.drawLine(p1.x(), p1.y(), p1.x(), p2.y());
						painter.drawLine(p1.x(), p2.y(), p2.x(), p2.y());
					}
					else {
						// horizontal then vertical
						painter.drawLine(p1.x(), p1.y(), p2.x(), p1.y());
						painter.drawLine(p2.x(), p1.y(), p2.x(), p2.y());
					}
				}
				painter.end();
#ifndef QT_NO_DEBUG
				//m_spareImage2->save(FolderUtils::getUserDataStorePath("") + QString("/optimizeTrace%1_%2_%3.png").arg(netIndex,2,10,QChar('0')).arg(layerSpec).arg(inc++,3,10,QChar('0')));
#endif

				bool overlaps = false;
				for (int y = minY; y <= maxY && !overlaps; y++) {
					for (int x = minX; x <= maxX && !overlaps; x++) {
						if (m_spareImage->pixel(x, y) == 0xffffffff) continue;
						if (m_spareImage2->pixel(x, y) == 0xffffffff) continue;
						overlaps = true;
					}
				}

				if (overlaps) continue;

				TraceWire * traceWire = bundle.at(ix);
				TraceWire * last = bundle.at(ix + separation - 1);
				TraceWire * next = bundle.at(ix + 1);
				QList<ConnectorItem *> newDests = connectionThing.values(last->connector1());
				QPointF unop_p2 = (p2 / OptimizeFactor) + topLeft;
				if (corners == 2) {
					TraceWire * afterNext = bundle.at(ix + 2);
					QPointF middle;
					if (corner == 0) {
						middle.setX(p1.x());
						middle.setY(p2.y());
					}
					else {
						middle.setX(p2.x());
						middle.setY(p1.y());
					}
					middle = (middle / OptimizeFactor) + topLeft;
					traceWire->setLineAnd(QLineF(QPointF(0, 0), middle - traceWire->pos()), traceWire->pos(), true);
					traceWire->saveGeometry();
					traceWire->update();
					next->setLineAnd(QLineF(QPointF(0, 0), unop_p2 - middle), middle, true);
					next->saveGeometry();
					next->update();
					Q_FOREACH (ConnectorItem * newDest, newDests) {
						connectionThing.add(next->connector1(), newDest);
					}
					connectionThing.remove(next->connector1(), afterNext->connector0());
					for (int i = 1; i < separation - 1; i++) {
						TraceWire * tw = bundle.takeAt(ix + 2);
						connectionThing.remove(tw->connector0());
						connectionThing.remove(tw->connector1());
						ModelPart * modelPart = tw->modelPart();
						delete tw;
						modelPart->setParent(nullptr);
						delete modelPart;
						points.removeAt(ix + 2);
					}
					points.replace(ix + 1, middle);
				}
				else {
					traceWire->setLineAnd(QLineF(QPointF(0, 0), unop_p2 - traceWire->pos()), traceWire->pos(), true);
					traceWire->saveGeometry();
					traceWire->update();
					Q_FOREACH (ConnectorItem * newDest, newDests) {
						connectionThing.add(traceWire->connector1(), newDest);
					}
					connectionThing.remove(traceWire->connector1(), next->connector0());
					for (int i = 0; i < separation - 1; i++) {
						auto *tw = bundle.takeAt(ix + 1);
						connectionThing.remove(tw->connector0());
						connectionThing.remove(tw->connector1());
						auto *modelPart = tw->modelPart();
						delete tw;
						modelPart->setParent(nullptr);
						delete modelPart;
						points.removeAt(ix + 1);
					}
				}
				break;
			}
		}
	}
}
