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