1 /*
2  * KiRouter - a push-and-(sometimes-)shove PCB router
3  *
4  * Copyright (C) 2013-2014 CERN
5  * Copyright (C) 2016 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_JOINT_H
23 #define __PNS_JOINT_H
24 
25 #include <vector>
26 
27 #include <math/vector2d.h>
28 
29 #include "pns_item.h"
30 #include "pns_segment.h"
31 #include "pns_itemset.h"
32 
33 namespace PNS {
34 
35 /**
36  * Class JOINT
37  *
38  * Represents a 2D point on a given set of layers and belonging to a certain
39  * net, that links together a number of board items.
40  * A hash table of joints is used by the router to follow connectivity between
41  * the items.
42  **/
43 class JOINT : public ITEM
44 {
45 public:
46     typedef ITEM_SET::ENTRIES LINKED_ITEMS;
47 
48     ///> Joints are hashed by their position, layers and net.
49     ///  Linked items are, obviously, not hashed
50     struct HASH_TAG
51     {
52         VECTOR2I pos;
53         int net;
54     };
55 
56     struct JOINT_TAG_HASH
57     {
operatorJOINT_TAG_HASH58         std::size_t operator()( const JOINT::HASH_TAG& aP ) const
59         {
60             using std::size_t;
61             using std::hash;
62             using std::string;
63 
64             return ( (hash<int>()( aP.pos.x )
65                       ^ (hash<int>()( aP.pos.y ) << 1) ) >> 1 )
66                    ^ (hash<int>()( aP.net ) << 1);
67         }
68     };
69 
JOINT()70     JOINT() :
71         ITEM( JOINT_T ), m_locked( false ) {}
72 
73     JOINT( const VECTOR2I& aPos, const LAYER_RANGE& aLayers, int aNet = -1 ) :
ITEM(JOINT_T)74         ITEM( JOINT_T )
75     {
76         m_tag.pos = aPos;
77         m_tag.net = aNet;
78         m_layers = aLayers;
79         m_locked = false;
80     }
81 
JOINT(const JOINT & aB)82     JOINT( const JOINT& aB ) :
83         ITEM( JOINT_T )
84     {
85         m_layers = aB.m_layers;
86         m_tag.pos = aB.m_tag.pos;
87         m_tag.net = aB.m_tag.net;
88         m_linkedItems = aB.m_linkedItems;
89         m_layers = aB.m_layers;
90         m_locked = aB.m_locked;
91     }
92 
Clone()93     ITEM* Clone( ) const override
94     {
95         assert( false );
96         return NULL;
97     }
98 
99     ///> Returns true if the joint is a trivial line corner, connecting two
100     /// segments of the same net, on the same layer.
IsLineCorner()101     bool IsLineCorner() const
102     {
103         if( m_linkedItems.Size() != 2 || m_linkedItems.Count( SEGMENT_T ) != 2 )
104             return false;
105 
106         SEGMENT* seg1 = static_cast<SEGMENT*>( m_linkedItems[0] );
107         SEGMENT* seg2 = static_cast<SEGMENT*>( m_linkedItems[1] );
108 
109         // joints between segments of different widths are not considered trivial.
110         return seg1->Width() == seg2->Width();
111     }
112 
IsNonFanoutVia()113     bool IsNonFanoutVia() const
114     {
115         int vias = m_linkedItems.Count( VIA_T );
116         int segs = m_linkedItems.Count( SEGMENT_T );
117 
118         return ( m_linkedItems.Size() == 3 && vias == 1 && segs == 2 );
119     }
120 
IsStitchingVia()121     bool IsStitchingVia() const
122     {
123         return ( m_linkedItems.Size() == 1 && m_linkedItems.Count( VIA_T ) == 1 );
124     }
125 
IsTraceWidthChange()126     bool IsTraceWidthChange() const
127     {
128         if( m_linkedItems.Size() != 2 )
129             return false;
130 
131         if( m_linkedItems.Count( SEGMENT_T ) != 2)
132             return false;
133 
134         SEGMENT* seg1 = static_cast<SEGMENT*>( m_linkedItems[0] );
135         SEGMENT* seg2 = static_cast<SEGMENT*>( m_linkedItems[1] );
136 
137         return seg1->Width() != seg2->Width();
138     }
139 
140     ///> Links the joint to a given board item (when it's added to the NODE)
Link(ITEM * aItem)141     void Link( ITEM* aItem )
142     {
143         if( m_linkedItems.Contains( aItem ) )
144             return;
145 
146         m_linkedItems.Add( aItem );
147     }
148 
149     ///> Unlinks a given board item from the joint (upon its removal from a NODE)
150     ///> Returns true if the joint became dangling after unlinking.
Unlink(ITEM * aItem)151     bool Unlink( ITEM* aItem )
152     {
153         m_linkedItems.Erase( aItem );
154         return m_linkedItems.Size() == 0;
155     }
156 
157     ///> For trivial joints, returns the segment adjacent to (aCurrent). For non-trival ones, returns
158     ///> NULL, indicating the end of line.
NextSegment(SEGMENT * aCurrent)159     SEGMENT* NextSegment( SEGMENT* aCurrent ) const
160     {
161         if( !IsLineCorner() )
162             return NULL;
163 
164         return static_cast<SEGMENT*>( m_linkedItems[m_linkedItems[0] == aCurrent ? 1 : 0] );
165     }
166 
Via()167     VIA* Via()
168     {
169         for( ITEM* item : m_linkedItems.Items() )
170         {
171             if( item->OfKind( VIA_T ) )
172                 return static_cast<VIA*>( item );
173         }
174 
175         return NULL;
176     }
177 
178 
179     /// trivial accessors
Tag()180     const HASH_TAG& Tag() const
181     {
182         return m_tag;
183     }
184 
Pos()185     const VECTOR2I& Pos() const
186     {
187         return m_tag.pos;
188     }
189 
Net()190     int Net() const
191     {
192         return m_tag.net;
193     }
194 
LinkList()195     const LINKED_ITEMS& LinkList() const
196     {
197         return m_linkedItems.CItems();
198     }
199 
CLinks()200     const ITEM_SET& CLinks() const
201     {
202         return m_linkedItems;
203     }
204 
Links()205     ITEM_SET& Links()
206     {
207         return m_linkedItems;
208     }
209 
210     int LinkCount( int aMask = -1 ) const
211     {
212         return m_linkedItems.Count( aMask );
213     }
214 
215     void Dump() const;
216 
217     bool operator==( const JOINT& rhs )  const
218     {
219         return m_tag.pos == rhs.m_tag.pos && m_tag.net == rhs.m_tag.net;
220     }
221 
Merge(const JOINT & aJoint)222     void Merge( const JOINT& aJoint )
223     {
224         if( !Overlaps( aJoint ) )
225             return;
226 
227         m_layers.Merge( aJoint.m_layers );
228 
229         if( aJoint.IsLocked() )
230             m_locked = true;
231 
232         for( ITEM* item : aJoint.LinkList() )
233         {
234             m_linkedItems.Add( item );
235         }
236     }
237 
Overlaps(const JOINT & rhs)238     bool Overlaps( const JOINT& rhs ) const
239     {
240         return m_tag.pos == rhs.m_tag.pos &&
241             m_tag.net == rhs.m_tag.net && m_layers.Overlaps( rhs.m_layers );
242     }
243 
244     void Lock( bool aLock = true )
245     {
246         m_locked = aLock;
247     }
248 
IsLocked()249     bool IsLocked() const
250     {
251         return m_locked;
252     }
253 
254 private:
255     ///> hash tag for unordered_multimap
256     HASH_TAG m_tag;
257 
258     ///> list of items linked to this joint
259     ITEM_SET m_linkedItems;
260 
261     ///> locked (non-movable) flag
262     bool m_locked;
263 };
264 
265 inline bool operator==( JOINT::HASH_TAG const& aP1, JOINT::HASH_TAG const& aP2 )
266 {
267     return aP1.pos == aP2.pos && aP1.net == aP2.net;
268 }
269 
270 }
271 
272 #endif    // __PNS_JOINT_H
273