KiCad PCB EDA Suite
All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Modules Pages Concepts
from_to_cache.cpp
Go to the documentation of this file.
1/*
2 * This program source code file is part of KiCad, a free EDA CAD application.
3 *
4 * Copyright (C) 2004-2022 KiCad Developers.
5 *
6 * This program is free software: you can redistribute it and/or modify it
7 * under the terms of the GNU General Public License as published by the
8 * Free Software Foundation, either version 3 of the License, or (at your
9 * option) any later version.
10 *
11 * This program is distributed in the hope that it will be useful, but
12 * WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 * General Public License for more details.
15 *
16 * You should have received a copy of the GNU General Public License along
17 * with this program. If not, see <http://www.gnu.org/licenses/>.
18 */
19
20#include <cstdio>
21#include <memory>
22#include <reporter.h>
23#include <board.h>
24#include <string_utils.h>
25
26#include <pcbexpr_evaluator.h>
27
30
32
34{
35 m_ftEndpoints.clear();
36
37 for( FOOTPRINT* footprint : m_board->Footprints() )
38 {
39 for( PAD* pad : footprint->Pads() )
40 {
41 FT_ENDPOINT ent;
42 ent.name = footprint->GetReference() + wxT( "-" ) + pad->GetNumber();
43 ent.parent = pad;
44 m_ftEndpoints.push_back( ent );
45 ent.name = footprint->GetReference();
46 ent.parent = pad;
47 m_ftEndpoints.push_back( ent );
48 }
49 }
50}
51
52
54 PS_OK = 0,
56 PS_NO_PATH = -2
57};
58
59
60static bool isVertexVisited( CN_ITEM* v, const std::vector<CN_ITEM*>& path )
61{
62 for( CN_ITEM* u : path )
63 {
64 if ( u == v )
65 return true;
66 }
67
68 return false;
69}
70
71
72static PATH_STATUS uniquePathBetweenNodes( CN_ITEM* u, CN_ITEM* v, std::vector<CN_ITEM*>& outPath )
73{
74 using Path = std::vector<CN_ITEM*>;
75 std::deque<Path> Q;
76
77 Path pInit;
78 bool pathFound = false;
79 pInit.push_back( u );
80 Q.push_back( pInit );
81
82 while( Q.size() )
83 {
84 Path path = Q.front();
85 Q.pop_front();
86 CN_ITEM* last = path.back();
87
88 if( last == v )
89 {
90 outPath = path;
91
92 if( pathFound )
93 return PS_MULTIPLE_PATHS;
94
95 pathFound = true;
96 }
97
98 for( CN_ITEM* ci : last->ConnectedItems() )
99 {
100 bool vertexVisited = isVertexVisited( ci, path );
101
102 for( std::vector<CN_ITEM*>& p : Q )
103 if( isVertexVisited( ci, p ) )
104 {
105 vertexVisited = true;
106 break;
107 }
108
109 if( !vertexVisited )
110 {
111 Path newpath( path );
112 newpath.push_back( ci );
113 Q.push_back( newpath );
114 }
115 }
116 }
117
118 return pathFound ? PS_OK : PS_NO_PATH;
119};
120
121
122int FROM_TO_CACHE::cacheFromToPaths( const wxString& aFrom, const wxString& aTo )
123{
124 std::vector<FT_PATH> paths;
125 std::shared_ptr<CONNECTIVITY_DATA> connectivity = m_board->GetConnectivity();
126 std::shared_ptr<CN_CONNECTIVITY_ALGO> cnAlgo = connectivity->GetConnectivityAlgo();
127
128 for( FT_ENDPOINT& endpoint : m_ftEndpoints )
129 {
130 if( WildCompareString( aFrom, endpoint.name, false ) )
131 {
132 FT_PATH p;
133 p.net = endpoint.parent->GetNetCode();
134 p.from = endpoint.parent;
135 p.to = nullptr;
136 paths.push_back(p);
137 }
138 }
139
140 for( FT_PATH& path : paths )
141 {
142 int count = 0;
143
144 wxString fromName = path.from->GetParentFootprint()->GetReference()
145 + wxT( "-" ) + path.from->GetNumber();
146
147 auto padCandidates = connectivity->GetConnectedItems( path.from,
148 { PCB_PAD_T, PCB_ARC_T, PCB_VIA_T,
149 PCB_TRACE_T } );
150 PAD* toPad = nullptr;
151
152 for( BOARD_CONNECTED_ITEM* pitem : padCandidates )
153 {
154 if( pitem == path.from )
155 continue;
156
157 if( pitem->Type() != PCB_PAD_T )
158 continue;
159
160 const PAD *pad = static_cast<const PAD*>( pitem );
161
162 wxString toName = pad->GetParentFootprint()->GetReference()
163 + wxT( "-" ) + pad->GetNumber();
164
165 for( const FT_ENDPOINT& endpoint : m_ftEndpoints )
166 {
167 if( pad == endpoint.parent )
168 {
169 if( WildCompareString( aTo, endpoint.name, false ) )
170 {
171 count++;
172 toPad = endpoint.parent;
173
174 path.to = toPad;
175 path.fromName = fromName;
176 path.toName = toName;
177 path.fromWildcard = aFrom;
178 path.toWildcard = aTo;
179
180 if( count >= 2 )
181 {
182 // fixme: report this somewhere?
183 path.to = nullptr;
184 }
185 }
186 }
187 }
188 }
189 }
190
191 int newPaths = 0;
192
193 for( FT_PATH& path : paths )
194 {
195 if( !path.from || !path.to )
196 continue;
197
198 CN_ITEM* cnFrom = cnAlgo->ItemEntry( path.from ).GetItems().front();
199 CN_ITEM* cnTo = cnAlgo->ItemEntry( path.to ).GetItems().front();
200 std::vector<CN_ITEM*> upath;
201
202 auto result = uniquePathBetweenNodes( cnFrom, cnTo, upath );
203
204 if( result == PS_OK )
205 path.isUnique = true;
206 else
207 path.isUnique = false;
208
209 if( result == PS_NO_PATH )
210 continue;
211
212 for( const auto item : upath )
213 {
214 path.pathItems.insert( item->Parent() );
215 }
216
217 m_ftPaths.push_back(path);
218 newPaths++;
219 }
220
221 // reportAux( _("Cached %d paths\n"), newPaths );
222
223 return newPaths;
224}
225
226bool FROM_TO_CACHE::IsOnFromToPath( BOARD_CONNECTED_ITEM* aItem, const wxString& aFrom, const wxString& aTo )
227{
228 int nFromTosFound = 0;
229
230 if( !m_board )
231 return false;
232
233 for( int attempt = 0; attempt < 2; attempt++ )
234 {
235 // item already belongs to path
236 for( FT_PATH& ftPath : m_ftPaths )
237 {
238 if( aFrom == ftPath.fromWildcard && aTo == ftPath.toWildcard )
239 {
240 nFromTosFound++;
241
242 if( ftPath.pathItems.count( aItem ) )
243 return true;
244 }
245 }
246
247 if( !nFromTosFound )
248 cacheFromToPaths( aFrom, aTo );
249 else
250 return false;
251 }
252
253 return false;
254}
255
256
258{
259 m_board = aBoard;
261 m_ftPaths.clear();
262}
263
264
265FROM_TO_CACHE::FT_PATH* FROM_TO_CACHE::QueryFromToPath( const std::set<BOARD_CONNECTED_ITEM*>& aItems )
266{
267 for( FT_PATH& ftPath : m_ftPaths )
268 {
269 if ( ftPath.pathItems == aItems )
270 return &ftPath;
271 }
272
273 return nullptr;
274}
A base class derived from BOARD_ITEM for items that can be connected and have a net,...
Information pertinent to a Pcbnew printed circuit board.
Definition: board.h:290
const FOOTPRINTS & Footprints() const
Definition: board.h:331
std::shared_ptr< CONNECTIVITY_DATA > GetConnectivity() const
Return a list of missing connections between components/tracks.
Definition: board.h:475
CN_ITEM represents a BOARD_CONNETED_ITEM in the connectivity system (ie: a pad, track/arc/via,...
const std::vector< CN_ITEM * > & ConnectedItems() const
int cacheFromToPaths(const wxString &aFrom, const wxString &aTo)
std::vector< FT_PATH > m_ftPaths
Definition: from_to_cache.h:69
FT_PATH * QueryFromToPath(const std::set< BOARD_CONNECTED_ITEM * > &aItems)
bool IsOnFromToPath(BOARD_CONNECTED_ITEM *aItem, const wxString &aFrom, const wxString &aTo)
std::vector< FT_ENDPOINT > m_ftEndpoints
Definition: from_to_cache.h:68
BOARD * m_board
Definition: from_to_cache.h:71
void buildEndpointList()
void Rebuild(BOARD *aBoard)
Definition: pad.h:54
PATH_STATUS
@ PS_OK
@ PS_MULTIPLE_PATHS
@ PS_NO_PATH
static bool isVertexVisited(CN_ITEM *v, const std::vector< CN_ITEM * > &path)
static PATH_STATUS uniquePathBetweenNodes(CN_ITEM *u, CN_ITEM *v, std::vector< CN_ITEM * > &outPath)
bool WildCompareString(const wxString &pattern, const wxString &string_to_tst, bool case_sensitive)
Compare a string against wild card (* and ?) pattern using the usual rules.
@ PCB_PAD_T
class PAD, a pad in a footprint
Definition: typeinfo.h:87