1 /*******************************************************************
2 
3 Part of the Fritzing project - http://fritzing.org
4 Copyright (c) 2007-2014 Fachhochschule Potsdam - http://fh-potsdam.de
5 
6 Fritzing is free software: you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation, either version 3 of the License, or
9 (at your option) any later version.
10 
11 Fritzing is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14 GNU General Public License for more details.
15 
16 You should have received a copy of the GNU General Public License
17 along with Fritzing.  If not, see <http://www.gnu.org/licenses/>.
18 
19 ********************************************************************
20 
21 $Revision: 6955 $:
22 $Author: irascibl@gmail.com $:
23 $Date: 2013-04-06 23:14:37 +0200 (Sa, 06. Apr 2013) $
24 
25 ********************************************************************/
26 
27 #ifndef MAZEROUTER_H
28 #define MAZEROUTER_H
29 
30 #include <QAction>
31 #include <QHash>
32 #include <QVector>
33 #include <QList>
34 #include <QSet>
35 #include <QPointF>
36 #include <QGraphicsItem>
37 #include <QLine>
38 #include <QProgressDialog>
39 #include <QUndoCommand>
40 #include <QPointer>
41 
42 #include <limits>
43 #include <queue>
44 
45 #include "../../viewgeometry.h"
46 #include "../../viewlayer.h"
47 #include "../../commands.h"
48 #include "../autorouter.h"
49 
50 typedef quint64 GridValue;
51 
52 struct GridPoint {
53     int x, y, z;
54     GridValue baseCost;
55     double qCost;
56     uchar flags;
57 
58     bool operator<(const GridPoint&) const;
59     GridPoint(QPoint, int);
60     GridPoint();
61 };
62 
63 struct PointZ {
64     QPointF p;
65     int z;
66 
PointZPointZ67     PointZ(QPointF _p, int _z) {
68         p = _p;
69         z = _z;
70     }
71 };
72 
73 struct Net {
74     QList<class ConnectorItem *>* net;
75     QList< QList<ConnectorItem *> > subnets;
76     int pinsWithin;
77     int id;
78 };
79 
80 struct NetList {
81     QList<Net *> nets;
82 };
83 
84 struct Trace {
85     int netIndex;
86     int order;
87     uchar flags;
88     QList<GridPoint> gridPoints;
89 
TraceTrace90     Trace() {
91         flags = 0;
92     }
93 };
94 
95 struct NetOrdering {
96     QList<int> order;
97 };
98 
99 struct Score {
100     NetOrdering ordering;
101     QMultiHash<int, Trace> traces;
102     QHash<int, int> routedCount;
103     QHash<int, int> viaCount;
104 	int totalRoutedCount;
105 	int totalViaCount;
106     int reorderNet;
107     bool anyUnrouted;
108 
109 	Score();
110     void setOrdering(const NetOrdering &);
111 };
112 
113 struct Nearest {
114     int i, j;
115     double distance;
116     ConnectorItem * ic;
117     ConnectorItem * jc;
118 };
119 
120 struct Grid {
121     GridValue * data;
122     int x;
123     int y;
124     int z;
125 
126     Grid(int x, int y, int layers);
127 
128     GridValue at(int x, int y, int z) const;
129     void setAt(int x, int y, int z, GridValue value);
130     QList<QPoint> init(int x, int y, int z, int width, int height, const QImage &, GridValue value, bool collectPoints);
131     QList<QPoint> init4(int x, int y, int z, int width, int height, const QImage *, GridValue value, bool collectPoints);
132     void clear();
133     void free();
134     void copy(int fromIndex, int toIndex);
135 };
136 
137 
138 struct NetElements {
139     QList<QDomElement> net;
140     QList<QDomElement> alsoNet;
141     QList<QDomElement> notNet;
142 };
143 
144 struct RouteThing {
145     QRectF r;
146     QRectF r4;
147     QList<ViewLayer::ViewLayerPlacement> layerSpecs;
148     Nearest nearest;
149     std::priority_queue<GridPoint> sourceQ;
150     std::priority_queue<GridPoint> targetQ;
151     QPoint gridSourcePoint;
152     QPoint gridTargetPoint;
153     GridValue sourceValue;
154     GridValue targetValue;
155     double bestDistanceToTarget;
156     double bestDistanceToSource;
157     GridPoint bestLocationToTarget;
158     GridPoint bestLocationToSource;
159     bool unrouted;
160     NetElements netElements[2];
161     QSet<int> avoids;
162 };
163 
164 struct TraceThing {
165     QList<TraceWire *> newTraces;
166     QList<Via *> newVias;
167     QList<JumperItem *> newJumperItems;
168     QList<SymbolPaletteItem *> newNetLabels;
169     JumperItem * jumperItem;
170     SymbolPaletteItem * netLabel;
171     QPointF topLeft;
172     GridPoint nextTraceStart;
173 };
174 
175 struct ConnectionThing {
176     QMultiHash<ConnectorItem *, QPointer<ConnectorItem> > sd;
177 
178     void add(ConnectorItem * s, ConnectorItem * d);
179     void remove(ConnectorItem * s);
180     void remove(ConnectorItem * s, ConnectorItem * d);
181     bool multi(ConnectorItem * s);
182     QList<ConnectorItem *> values(ConnectorItem * s);
183 };
184 
185 typedef bool (*JumperWillFitFunction)(GridPoint &, const Grid *, int halfSize);
186 typedef double (*CostFunction)(const QPoint & p1, const QPoint & p2);
187 
188 ////////////////////////////////////
189 
190 class MazeRouter : public Autorouter
191 {
192 	Q_OBJECT
193 
194 public:
195 	MazeRouter(class PCBSketchWidget *, QGraphicsItem * board, bool adjustIf);
196 	~MazeRouter(void);
197 
198 	void start();
199 
200 protected:
201     void setUpWidths(double width);
202     int findPinsWithin(QList<ConnectorItem *> * net);
203     bool makeBoard(QImage *, double keepout, const QRectF & r);
204     bool makeMasters(QString &);
205 	bool routeNets(NetList &, bool makeJumper, Score & currentScore, const QSizeF gridSize, QList<NetOrdering> & allOrderings);
206     bool routeOne(bool makeJumper, Score & currentScore, int netIndex, RouteThing &, QList<NetOrdering> & allOrderings);
207     void findNearestPair(QList< QList<ConnectorItem *> > & subnets, Nearest &);
208     void findNearestPair(QList< QList<ConnectorItem *> > & subnets, int i, QList<ConnectorItem *> & inet, Nearest &);
209     QList<QPoint> renderSource(QDomDocument * masterDoc, int z, ViewLayer::ViewLayerPlacement, Grid * grid, QList<QDomElement> & netElements, QList<ConnectorItem *> & subnet, GridValue value, bool clearElements, const QRectF & r);
210     QList<GridPoint> route(RouteThing &, int & viaCount);
211     void expand(GridPoint &, RouteThing &);
212     void expandOne(GridPoint &, RouteThing &, int dx, int dy, int dz, bool crossLayer);
213     bool viaWillFit(GridPoint &, Grid * grid);
214     QList<GridPoint> traceBack(GridPoint, Grid *, int & viaCount, GridValue sourceValue, GridValue targetValue);
215     GridPoint traceBackOne(GridPoint &, Grid *, int dx, int dy, int dz, GridValue sourceValue, GridValue targetValue);
216     void updateDisplay(int iz);
217     void updateDisplay(Grid *, int iz);
218     void updateDisplay(GridPoint &);
219     void clearExpansion(Grid * grid);
220     void prepSourceAndTarget(QDomDocument * masterdoc, RouteThing &, QList< QList<ConnectorItem *> > & subnets, int z, ViewLayer::ViewLayerPlacement);
221     bool moveBack(Score & currentScore, int index, QList<NetOrdering> & allOrderings);
222     void displayTrace(Trace &);
223     void initTraceDisplay();
224     void traceObstacles(QList<Trace> & traces, int netIndex, Grid * grid, int ikeepout);
225     void traceAvoids(QList<Trace> & traces, int netIndex, RouteThing & routeThing);
226     bool routeNext(bool makeJumper, RouteThing &, QList< QList<ConnectorItem *> > & subnets, Score & currentScore, int netIndex, QList<NetOrdering> & allOrderings);
227     void cleanUpNets(NetList &);
228     void createTraces(NetList & netList, Score & bestScore, QUndoCommand * parentCommand);
229     void createTrace(Trace &, QList<GridPoint> &, TraceThing &, ConnectionThing &, Net *);
230     void removeColinear(QList<GridPoint> & gridPoints);
231     void removeSteps(QList<GridPoint> & gridPoints);
232     void removeStep(int ix, QList<GridPoint> & gridPoints);
233     ConnectorItem * findAnchor(GridPoint gp, TraceThing &, Net * net, QPointF & p, bool & onTrace, ConnectorItem * already);
234     ConnectorItem * findAnchor(GridPoint gp, const QRectF &, TraceThing &, Net * net, QPointF & p, bool & onTrace, ConnectorItem * already);
235     void addConnectionToUndo(ConnectorItem * from, ConnectorItem * to, QUndoCommand * parentCommand);
236     void addViaToUndo(Via *, QUndoCommand * parentCommand);
237     void addJumperToUndo(JumperItem *, QUndoCommand * parentCommand);
238     void routeJumper(int netIndex, RouteThing &, Score & currentScore);
239     void insertTrace(Trace & newTrace, int netIndex, Score & currentScore, int viaCount, bool incRouted);
240     SymbolPaletteItem * makeNetLabel(GridPoint & center, SymbolPaletteItem * pairedNetLabel, uchar traceFlags);
241     void addNetLabelToUndo(SymbolPaletteItem * netLabel, QUndoCommand * parentCommand);
242     GridPoint lookForJumper(GridPoint initial, GridValue targetValue, QPoint targetLocation);
243     void expandOneJ(GridPoint & gridPoint, std::priority_queue<GridPoint> & pq, int dx, int dy, int dz, GridValue targetValue, QPoint targetLocation, QSet<int> & already);
244     void removeOffBoardAnd(bool isPCBType, bool removeSingletons, bool bothSides);
245     void optimizeTraces(QList<int> & order, QMultiHash<int, QList< QPointer<TraceWire> > > &, QMultiHash<int, Via *> &, QMultiHash<int, JumperItem *> &, QMultiHash<int, SymbolPaletteItem *> &, NetList &, ConnectionThing &);
246     void reducePoints(QList<QPointF> & points, QPointF topLeft, QList<TraceWire *> & bundle, int startIndex, int endIndex, ConnectionThing &, int netIndex, ViewLayer::ViewLayerPlacement);
247 
248 public slots:
249      void incCommandProgress();
250 	 void setMaxCycles(int);
251 
252 protected:
253 	LayerList m_viewLayerIDs;
254     QHash<ViewLayer::ViewLayerPlacement, QDomDocument *> m_masterDocs;
255     double m_keepoutMils;
256     double m_keepoutGrid;
257     int m_keepoutGridInt;
258     int m_halfGridViaSize;
259     int m_halfGridJumperSize;
260     double m_gridPixels;
261     double m_standardWireWidth;
262     QImage * m_displayImage[2];
263     QImage * m_boardImage;
264     QImage * m_spareImage;
265     QImage * m_spareImage2;
266     QGraphicsPixmapItem * m_displayItem[2];
267     bool m_temporaryBoard;
268     CostFunction m_costFunction;
269     JumperWillFitFunction m_jumperWillFitFunction;
270     uint m_traceColors[2];
271     Grid * m_grid;
272     int m_cleanupCount;
273     int m_netLabelIndex;
274     int m_commandCount;
275 };
276 
277 #endif
278