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
160
161
162
163
164
|
/*
* This program source code file is part of KiCad, a free EDA CAD application.
*
* Copyright (C) 2012 Jean-Pierre Charras, jean-pierre.charras@ujf-grenoble.fr
* Copyright (C) 2012 SoftPLC Corporation, Dick Hollenbeck <dick@softplc.com>
* Copyright (C) 2011 Wayne Stambaugh <stambaughw@verizon.net>
*
* Copyright (C) 1992-2012 KiCad Developers, see change_log.txt for contributors.
*
* First copyright (C) Randy Nevin, 1989 (see PCBCA package)
*
* This program is free software; you can redistribute it and/or
* modify it under the terms of the GNU General Public License
* as published by the Free Software Foundation; either version 2
* of the License, or (at your option) any later version.
*
* 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, you may find one here:
* http://www.gnu.org/licenses/old-licenses/gpl-2.0.html
* or you may search the http://www.gnu.org website for the version 2 license,
* or you may write to the Free Software Foundation, Inc.,
* 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA
*/
/**
* @file work.cpp
* @brief Automatic routing routines
*/
#include <fctsys.h>
#include <common.h>
#include <pcbnew.h>
#include <autorout.h>
#include <cell.h>
struct CWORK // a unit of work is a source-target to connect
// this is a ratsnest item in the routing matrix world
{
int m_FromRow; // source row
int m_FromCol; // source column
int m_ToRow; // target row
int m_ToCol; // target column
RATSNEST_ITEM* m_Ratsnest; // Corresponding ratsnest
int m_NetCode; // m_NetCode
int m_ApxDist; // approximate distance
int m_Cost; // cost for sort by length
int m_Priority; // route priority
// the function that calculates the cost of this ratsnest:
void CalculateCost();
};
// the list of ratsnests
static std::vector <CWORK> WorkList;
static unsigned Current = 0;
// initialize the work list
void InitWork()
{
WorkList.clear();
Current = 0;
}
/* add a unit of work to the work list
* :
* 1 if OK
* 0 if memory allocation failed
*/
int SetWork( int r1, int c1,
int n_c,
int r2, int c2,
RATSNEST_ITEM* pt_ch, int pri )
{
CWORK item;
item.m_FromRow = r1;
item.m_FromCol = c1;
item.m_NetCode = n_c;
item.m_ToRow = r2;
item.m_ToCol = c2;
item.m_Ratsnest = pt_ch;
item.m_ApxDist = RoutingMatrix.GetApxDist( r1, c1, r2, c2 );
item.CalculateCost();
item.m_Priority = pri;
WorkList.push_back( item );
return 1;
}
/* fetch a unit of work from the work list */
void GetWork( int* r1, int* c1,
int* n_c,
int* r2, int* c2,
RATSNEST_ITEM** pt_ch )
{
if( Current < WorkList.size() )
{
*r1 = WorkList[Current].m_FromRow;
*c1 = WorkList[Current].m_FromCol;
*n_c = WorkList[Current].m_NetCode;
*r2 = WorkList[Current].m_ToRow;
*c2 = WorkList[Current].m_ToCol;
*pt_ch = WorkList[Current].m_Ratsnest;
Current++;
}
else /* none left */
{
*r1 = *c1 = *r2 = *c2 = ILLEGAL;
*n_c = 0;
*pt_ch = NULL;
}
}
// order the work items; shortest (low cost) first:
bool sort_by_cost( const CWORK& ref, const CWORK& item )
{
if( ref.m_Priority == item.m_Priority )
return ref.m_Cost < item.m_Cost;
return ref.m_Priority >= item.m_Priority;
}
void SortWork()
{
sort( WorkList.begin(), WorkList.end(), sort_by_cost );
}
/* Calculate the cost of a ratsnest:
* cost = (| dx | + | dy |) * disability
* disability = 1 if dx or dy = 0, max if | dx | # | dy |
*/
void CWORK::CalculateCost()
{
int dx, dy, mx, my;
double incl = 1.0;
dx = abs( m_ToCol - m_FromCol );
dy = abs( m_ToRow - m_FromRow );
mx = dx;
my = dy;
if( mx < my )
{
mx = dy; my = dx;
}
if( mx )
incl += (2 * (double) my / mx);
m_Cost = (int) ( ( dx + dy ) * incl );
}
|
