1 /*
2  * KiRouter - a push-and-(sometimes-)shove PCB router
3  *
4  * Copyright (C) 2013-2015 CERN
5  * Copyright (C) 2016-2021 KiCad Developers, see AUTHORS.txt for contributors.
6  * Author: Tomasz Wlostowski <tomasz.wlostowski@cern.ch>
7  *
8  * This program is free software: you can redistribute it and/or modify it
9  * under the terms of the GNU General Public License as published by the
10  * Free Software Foundation, either version 3 of the License, or (at your
11  * option) any later version.
12  *
13  * This program is distributed in the hope that it will be useful, but
14  * WITHOUT ANY WARRANTY; without even the implied warranty of
15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
16  * General Public License for more details.
17  *
18  * You should have received a copy of the GNU General Public License along
19  * with this program.  If not, see <http://www.gnu.org/licenses/>.
20  */
21 
22 #ifndef __PNS_TOPOLOGY_H
23 #define __PNS_TOPOLOGY_H
24 
25 #include <vector>
26 #include <set>
27 
28 #include "pns_itemset.h"
29 
30 namespace PNS {
31 
32 class NODE;
33 class SEGMENT;
34 class JOINT;
35 class ITEM;
36 class SOLID;
37 class DIFF_PAIR;
38 
39 class TOPOLOGY
40 {
41 public:
42     typedef std::set<JOINT*> JOINT_SET;
43 
TOPOLOGY(NODE * aNode)44     TOPOLOGY( NODE* aNode ):
45         m_world( aNode ) {};
46 
~TOPOLOGY()47     ~TOPOLOGY() {};
48 
49     bool SimplifyLine( LINE *aLine );
50     ITEM* NearestUnconnectedItem( JOINT* aStart, int* aAnchor = nullptr,
51                                   int aKindMask = ITEM::ANY_T );
52     bool LeadingRatLine( const LINE* aTrack, SHAPE_LINE_CHAIN& aRatLine );
53 
54     const JOINT_SET ConnectedJoints( JOINT* aStart );
55     const ITEM_SET ConnectedItems( JOINT* aStart, int aKindMask = ITEM::ANY_T );
56     const ITEM_SET ConnectedItems( ITEM* aStart, int aKindMask = ITEM::ANY_T );
57     int64_t ShortestConnectionLength( ITEM* aFrom, ITEM* aTo );
58 
59     /**
60      * Assemble a trivial path between two joints given a starting item.
61      *
62      * @param aStart is the item to assemble from.
63      * @param aTerminalJoints will be filled with the start and end points of the assembled path.
64      * @param aFollowLockedSegments if true will assemble a path including locked segments
65      * @return a set of items in the path.
66      */
67     const ITEM_SET AssembleTrivialPath( ITEM* aStart,
68                                         std::pair<JOINT*, JOINT*>* aTerminalJoints = nullptr,
69                                         bool aFollowLockedSegments = false );
70 
71     /**
72      * Like AssembleTrivialPath, but follows the track length algorithm, which discards segments
73      * that are fully inside pads, and truncates segments that cross into a pad (adding a straight-
74      * line segment from the intersection to the pad anchor).
75      *
76      * @note When changing this, sync with BOARD::GetTrackLength()
77      *
78      * @param aStart is the item to assemble a path from.
79      * @param aStartPad will be filled with the starting pad of the path, if found.
80      * @param aEndPad will be filled with the ending pad of the path, if found.
81      * @return an item set containing all the items in the path.
82      */
83     const ITEM_SET AssembleTuningPath( ITEM* aStart, SOLID** aStartPad = nullptr,
84                                        SOLID** aEndPad = nullptr );
85 
86     const DIFF_PAIR AssembleDiffPair( SEGMENT* aStart );
87 
88     bool AssembleDiffPair( ITEM* aStart, DIFF_PAIR& aPair );
89 
90     const std::set<ITEM*> AssembleCluster( ITEM* aStart, int aLayer );
91 
92 private:
93     const int DP_PARALLELITY_THRESHOLD = 5;
94 
95     bool followTrivialPath( LINE* aLine, bool aLeft, ITEM_SET& aSet, std::set<ITEM*>& aVisited,
96                             JOINT** aTerminalJoint = nullptr );
97 
98     NODE *m_world;
99 };
100 
101 }
102 
103 #endif
104