1
2
3
4
5
6
7
8
9
10
11
12
13
14
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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
|
/*
* KiRouter - a push-and-(sometimes-)shove PCB router
*
* Copyright (C) 2013-2014 CERN
* Author: Tomasz Wlostowski <tomasz.wlostowski@cern.ch>
*
* This program is free software: you can redistribute it and/or modify it
* under the terms of the GNU General Public License as published by the
* Free Software Foundation, either version 3 of the License, or (at your
* option) any later version.
*
* This program is distributed in the hope that it will be useful, but
* WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
* General Public License for more details.
*
* You should have received a copy of the GNU General Public License along
* with this program. If not, see <http://www.gnu.org/licenses/>.
*/
#ifndef __PNS_SHOVE_H
#define __PNS_SHOVE_H
#include <vector>
#include <stack>
#include "pns_optimizer.h"
#include "pns_routing_settings.h"
#include "pns_algo_base.h"
#include "pns_logger.h"
#include "range.h"
class PNS_LINE;
class PNS_NODE;
class PNS_ROUTER;
/**
* Class PNS_SHOVE
*
* The actual Push and Shove algorithm.
*/
class PNS_SHOVE : public PNS_ALGO_BASE
{
public:
enum SHOVE_STATUS
{
SH_OK = 0,
SH_NULL,
SH_INCOMPLETE,
SH_HEAD_MODIFIED,
SH_TRY_WALK
};
PNS_SHOVE( PNS_NODE* aWorld, PNS_ROUTER* aRouter );
~PNS_SHOVE();
virtual PNS_LOGGER* Logger()
{
return &m_logger;
}
SHOVE_STATUS ShoveLines( const PNS_LINE& aCurrentHead );
SHOVE_STATUS ShoveMultiLines( const PNS_ITEMSET& aHeadSet );
SHOVE_STATUS ShoveDraggingVia( PNS_VIA* aVia, const VECTOR2I& aWhere, PNS_VIA** aNewVia );
SHOVE_STATUS ProcessSingleLine( PNS_LINE& aCurrent, PNS_LINE& aObstacle,
PNS_LINE& aShoved );
void ForceClearance ( bool aEnabled, int aClearance )
{
if( aEnabled )
m_forceClearance = aClearance;
else
m_forceClearance = -1;
}
PNS_NODE* CurrentNode();
const PNS_LINE NewHead() const;
void SetInitialLine( PNS_LINE& aInitial );
private:
typedef std::vector<SHAPE_LINE_CHAIN> HULL_SET;
typedef boost::optional<PNS_LINE> OPT_LINE;
typedef std::pair<PNS_LINE, PNS_LINE> LINE_PAIR;
typedef std::vector<LINE_PAIR> LINE_PAIR_VEC;
struct SPRINGBACK_TAG
{
int64_t m_length;
int m_segments;
VECTOR2I m_p;
PNS_NODE* m_node;
PNS_ITEMSET m_headItems;
PNS_COST_ESTIMATOR m_cost;
OPT_BOX2I m_affectedArea;
};
SHOVE_STATUS processHullSet( PNS_LINE& aCurrent, PNS_LINE& aObstacle,
PNS_LINE& aShoved, const HULL_SET& hulls );
bool reduceSpringback( const PNS_ITEMSET& aHeadItems );
bool pushSpringback( PNS_NODE* aNode, const PNS_ITEMSET& aHeadItems,
const PNS_COST_ESTIMATOR& aCost, const OPT_BOX2I& aAffectedArea );
SHOVE_STATUS walkaroundLoneVia( PNS_LINE& aCurrent, PNS_LINE& aObstacle, PNS_LINE& aShoved );
bool checkBumpDirection( const PNS_LINE& aCurrent, const PNS_LINE& aShoved ) const;
SHOVE_STATUS onCollidingLine( PNS_LINE& aCurrent, PNS_LINE& aObstacle );
SHOVE_STATUS onCollidingSegment( PNS_LINE& aCurrent, PNS_SEGMENT* aObstacleSeg );
SHOVE_STATUS onCollidingSolid( PNS_LINE& aCurrent, PNS_ITEM* aObstacle );
SHOVE_STATUS onCollidingVia( PNS_ITEM* aCurrent, PNS_VIA* aObstacleVia );
SHOVE_STATUS onReverseCollidingVia( PNS_LINE& aCurrent, PNS_VIA* aObstacleVia );
SHOVE_STATUS pushVia( PNS_VIA* aVia, const VECTOR2I& aForce, int aCurrentRank, bool aDryRun = false );
OPT_BOX2I totalAffectedArea() const;
void unwindStack( PNS_SEGMENT* aSeg );
void unwindStack( PNS_ITEM* aItem );
void runOptimizer( PNS_NODE* aNode );
bool pushLine( const PNS_LINE& aL, bool aKeepCurrentOnTop = false );
void popLine();
PNS_LINE assembleLine( const PNS_SEGMENT* aSeg, int* aIndex = NULL );
void replaceItems( PNS_ITEM* aOld, PNS_ITEM* aNew );
OPT_BOX2I m_affectedAreaSum;
SHOVE_STATUS shoveIteration( int aIter );
SHOVE_STATUS shoveMainLoop();
int getClearance( const PNS_ITEM* aA, const PNS_ITEM* aB ) const;
std::vector<SPRINGBACK_TAG> m_nodeStack;
std::vector<PNS_LINE> m_lineStack;
std::vector<PNS_LINE> m_optimizerQueue;
PNS_NODE* m_root;
PNS_NODE* m_currentNode;
OPT_LINE m_newHead;
PNS_LOGGER m_logger;
PNS_VIA* m_draggedVia;
PNS_ITEMSET m_draggedViaHeadSet;
int m_iter;
int m_forceClearance;
bool m_multiLineMode;
void sanityCheck( PNS_LINE* aOld, PNS_LINE* aNew );
};
#endif // __PNS_SHOVE_H
|
