connect.cpp 37.8 KB
Newer Older
1 2 3 4
/**
 * @file connect.cpp
 * @brief Functions to handle existing tracks in ratsnest calculations.
 */
5

6 7 8
/*
 * This program source code file is part of KiCad, a free EDA CAD application.
 *
9
 * Copyright (C) 2011 Jean-Pierre Charras, jean-pierre.charras@gipsa-lab.inpg.com
10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29
 * Copyright (C) 2004-2011 KiCad Developers, see change_log.txt for contributors.
 *
 * 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
 */

30 31 32 33 34
#include <fctsys.h>
#include <common.h>
#include <pcbcommon.h>
#include <macros.h>
#include <wxBasePcbFrame.h>
35

36 37
#include <class_track.h>
#include <class_board.h>
38

39
#include <pcbnew.h>
40

41

42 43 44
extern void Merge_SubNets_Connected_By_CopperAreas( BOARD* aPcb );
extern void Merge_SubNets_Connected_By_CopperAreas( BOARD* aPcb, int aNetcode );

Dick Hollenbeck's avatar
Dick Hollenbeck committed
45
// Local functions
46
static void RebuildTrackChain( BOARD* pcb );
47

48

jean-pierre charras's avatar
jean-pierre charras committed
49
// A helper class to handle connection points (i.e. candidates) for tracks
50 51
class CONNECTED_POINT
{
jean-pierre charras's avatar
jean-pierre charras committed
52
private:
53 54
    BOARD_CONNECTED_ITEM * m_item;  // a link to the parent item (track, via or pad)
    wxPoint m_point;                // the connection point
55

jean-pierre charras's avatar
jean-pierre charras committed
56
public:
57
    CONNECTED_POINT( TRACK * aTrack, const wxPoint & aPoint)
58
    {
59
        m_item = aTrack;
jean-pierre charras's avatar
jean-pierre charras committed
60
        m_point = aPoint;
61
    }
jean-pierre charras's avatar
jean-pierre charras committed
62

63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78
    CONNECTED_POINT( D_PAD * aPad, const wxPoint & aPoint)
    {
        m_item = aPad;
        m_point = aPoint;
    }

    TRACK * GetTrack() const
    {
        return m_item->Type() != PCB_PAD_T ? (TRACK*) m_item : NULL ;
    }

    D_PAD * GetPad() const
    {
        return m_item->Type() == PCB_PAD_T ? (D_PAD*) m_item : NULL;
    }

jean-pierre charras's avatar
jean-pierre charras committed
79
    const wxPoint & GetPoint() const { return m_point; }
80 81
};

82
// A helper class to handle connections calculations:
83 84
class CONNECTIONS
{
jean-pierre charras's avatar
jean-pierre charras committed
85 86
private:
    std::vector <TRACK*> m_connected;           // List of connected tracks/vias
87
                                                // to a given track or via
jean-pierre charras's avatar
jean-pierre charras committed
88
    std::vector <CONNECTED_POINT> m_candidates; // List of points to test
89 90
                                                // (end points of tracks or vias location )
    BOARD * m_brd;                              // the master board.
91 92
    const TRACK * m_firstTrack;                 // The first track used to build m_Candidates
    const TRACK * m_lastTrack;                  // The last track used to build m_Candidates
jean-pierre charras's avatar
jean-pierre charras committed
93
    std::vector<D_PAD*> m_sortedPads;           // list of sorted pads by X (then Y) coordinate
94 95 96 97 98

public:
    CONNECTIONS( BOARD * aBrd );
    ~CONNECTIONS() {};

jean-pierre charras's avatar
jean-pierre charras committed
99 100 101 102 103 104 105 106
    /** Function BuildPadsList
     * Fills m_sortedPads with all pads that be connected to tracks
     * pads are sorted by > then Y coordinates to allow fast binary search in list
     * @param aNetcode = net code to use to filter pads
     * if  aNetcode < 0, all pads will be put in list (default)
     */
    void BuildPadsList( int aNetcode = -1 );

107 108 109 110 111
    /**
     * @return the pads list used in connections calculations
     */
    std::vector<D_PAD*>& GetPadsList() { return m_sortedPads; }

jean-pierre charras's avatar
jean-pierre charras committed
112 113
    /**
     * Function Build_CurrNet_SubNets_Connections
114 115
     * should be called after a track change (delete or add a track):
     * Connections to pads and to tracks are recalculated
116 117 118 119 120 121 122 123
     *   If a track is deleted, the other pointers to pads do not change.
     *   When a new track is added in track list, its pointers to pads are already initialized
     * Builds the subnets inside a net (tracks from aFirstTrack to aFirstTrack).
     * subnets are clusters of pads and tracks that are connected together.
     * When all tracks are created relative to the net, there is only a cluster
     * when not tracks there are a cluster per pad
     * @param aFirstTrack = first track of the given net
     * @param aLastTrack = last track of the given net
124
     * @param aNetcode = the netcode of the given net
125
     */
126
    void Build_CurrNet_SubNets_Connections( TRACK* aFirstTrack, TRACK* aLastTrack, int aNetcode );
127

jean-pierre charras's avatar
jean-pierre charras committed
128
    /**
129
     * Function BuildTracksCandidatesList
130 131
     * Fills m_Candidates with all connecting points (track ends or via location)
     * with tracks from aBegin to aEnd.
132
     * if aEnd == NULL, uses all tracks from aBegin
133
     */
134
    void BuildTracksCandidatesList( TRACK * aBegin, TRACK * aEnd = NULL);
135

136 137 138 139 140 141 142
    /**
     * Function BuildPadsCandidatesList
     * Fills m_Candidates with all pads connecting points (pads position)
     * m_sortedPads must be built
     */
    void BuildPadsCandidatesList();

143 144 145 146 147 148 149
    /**
     * function SearchConnectedTracks
     * Fills m_Connected with tracks/vias connected to aTrack
     * @param aTrack = track or via to use as reference
     */
    int SearchConnectedTracks( const TRACK * aTrack );

jean-pierre charras's avatar
jean-pierre charras committed
150 151 152 153 154 155 156 157 158 159 160 161 162
    /**
     * Function GetConnectedTracks
     * Copy m_Connected that contains the list of tracks connected
     * calculated by SearchConnectedTracks
     * in aTrack->m_TracksConnected
     * @param aTrack = track or via to fill with connected tracks
     */
    void GetConnectedTracks(TRACK * aTrack)
    {
        aTrack->m_TracksConnected = m_connected;
    }

    /**
163
     * function SearchConnectionsPadsToIntersectingPads
jean-pierre charras's avatar
jean-pierre charras committed
164
     * Explores the list of pads and adds to m_PadsConnected member
165 166 167 168 169 170 171 172 173 174 175 176 177
     * of each pad pads connected to
     * Here, connections are due to intersecting pads, not tracks
     * m_sortedPads must be initialized
     */
    void SearchConnectionsPadsToIntersectingPads();

    /**
     * function SearchTracksConnectedToPads
     * Explores the list of pads.
     * Adds to m_PadsConnected member of each track the pad(s) connected to
     * Adds to m_TracksConnected member of each pad the track(s) connected to
     * D_PAD::m_TracksConnected is cleared before adding items
     * TRACK::m_PadsConnected is not cleared
jean-pierre charras's avatar
jean-pierre charras committed
178
     */
179
    void SearchTracksConnectedToPads();
jean-pierre charras's avatar
jean-pierre charras committed
180 181 182

    /**
     * function CollectItemsNearTo
183
     * Used by SearchTracksConnectedToPads
jean-pierre charras's avatar
jean-pierre charras committed
184 185 186 187 188 189 190 191 192
     * Fills aList with pads near to aPosition
     * near means aPosition to pad position <= aDistMax
     * @param aList = list to fill
     * @param aPosition = aPosition to use as reference
     * @param aDistMax = dist max from aPosition to a candidate to select it
     */
    void CollectItemsNearTo( std::vector<CONNECTED_POINT*>& aList,
                            const wxPoint& aPosition, int aDistMax );

193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208
    /**
     * Function Propagate_SubNets
     * Test a list of tracks, to create or propagate a sub netcode to pads and
     * segments connected together.
     * The track list must be sorted by nets, and all segments
     * from m_firstTrack to m_lastTrack have the same net.
     * When 2 items are connected (a track to a pad, or a track to an other track),
     * they are grouped in a cluster.
     * For pads, this is the .m_physical_connexion member which is a cluster identifier
     * For tracks, this is the .m_Subnet member which is a cluster identifier
     * For a given net, if all tracks are created, there is only one cluster.
     * but if not all tracks are created, there are more than one cluster,
     * and some ratsnests will be left active.
     */
    void Propagate_SubNets();

209 210
private:
    /**
211
     * function searchEntryPointInCandidatesList
212 213
     * Search an item in m_Connected connected to aPoint
     * note m_Connected containts usually more than one candidate
214
     * and searchEntryPointInCandidatesList returns an index to one of these candidates
215 216 217 218
     * Others are neightbor of the indexed item.
     * @param aPoint is the reference coordinates
     * @return the index of item found or -1 if no candidate
     */
219
    int searchEntryPointInCandidatesList( const wxPoint & aPoint);
220 221 222

    /**
     * Function Merge_SubNets
223 224 225 226 227
     * Change a subnet old value to a new value, for tracks and pads which are connected to
     * tracks from m_firstTrack to m_lastTrack and their connected pads.
     * and modify the subnet parameter (change the old value to the new value).
     * After that, 2 cluster (or subnets) are merged into only one.
     * Note: the resulting sub net value is the smallest between aOldSubNet and aNewSubNet
228 229 230 231 232 233
     * @return modification count
     * @param aOldSubNet = subnet value to modify
     * @param aNewSubNet = new subnet value for each item which have old_val as subnet value
     */
    int Merge_SubNets( int aOldSubNet, int aNewSubNet );

234 235 236 237 238 239 240 241 242 243
    /**
     * Function Merge_PadsSubNets
     * Change a subnet value to a new value, in m_sortedPads pad list
     * After that, 2 cluster (or subnets) are merged into only one.
     * Note: the resulting subnet value is the smallest between aOldSubNet et aNewSubNet
     * @return modification count
     * @param aOldSubNet = subnet value to modify
     * @param aNewSubNet = new subnet value for each item which have old_val as subnet value
     */
    int Merge_PadsSubNets( int aOldSubNet, int aNewSubNet );
244 245
};

jean-pierre charras's avatar
jean-pierre charras committed
246 247 248 249 250 251 252 253 254 255 256 257 258 259 260

CONNECTIONS::CONNECTIONS( BOARD * aBrd )
{
    m_brd = aBrd;
}


/* Fills m_sortedPads with all pads that be connected to tracks
 * pads are sorted by X coordinate ( and Y coordinates for same X value )
 * aNetcode = net code to filter pads or < 0 to put all pads in list
 */
void CONNECTIONS::BuildPadsList( int aNetcode )
{
    // Creates sorted pad list if not exists
    m_sortedPads.clear();
261 262 263 264 265 266 267 268 269 270 271 272 273 274
    m_brd->GetSortedPadListByXthenYCoord( m_sortedPads, aNetcode < 0 ? -1 : aNetcode );
}

/* Explores the list of pads and adds to m_PadsConnected member
 * of each pad pads connected to
 * Here, connections are due to intersecting pads, not tracks
 */
void CONNECTIONS::SearchConnectionsPadsToIntersectingPads()
{
    std::vector<CONNECTED_POINT*> candidates;

    BuildPadsCandidatesList();

    for( unsigned ii = 0; ii < m_sortedPads.size(); ii++ )
jean-pierre charras's avatar
jean-pierre charras committed
275
    {
276 277 278
        D_PAD * pad = m_sortedPads[ii];
        pad->m_PadsConnected.clear();
        candidates.clear();
Dick Hollenbeck's avatar
Dick Hollenbeck committed
279 280 281

        CollectItemsNearTo( candidates, pad->ReturnShapePos(), pad->GetBoundingRadius() );

282 283
        // add pads to pad.m_PadsConnected, if they are connected
        for( unsigned jj = 0; jj < candidates.size(); jj++ )
jean-pierre charras's avatar
jean-pierre charras committed
284
        {
285 286 287 288 289
            CONNECTED_POINT * item = candidates[jj];
            D_PAD * candidate_pad = item->GetPad();
            if( pad == candidate_pad )
                continue;

Dick Hollenbeck's avatar
Dick Hollenbeck committed
290
            if( (pad->GetLayerMask() & candidate_pad->GetLayerMask()) == 0 )
291 292 293 294 295
                continue;
            if( pad->HitTest( item->GetPoint() ) )
            {
                pad->m_PadsConnected.push_back( candidate_pad );
            }
jean-pierre charras's avatar
jean-pierre charras committed
296 297 298 299
        }
    }
}

300 301 302 303 304 305
/* Explores the list of pads
 * Adds to m_PadsConnected member of each track the pad(s) connected to
 * Adds to m_TracksConnected member of each pad the track(s) connected to
 * D_PAD::m_TracksConnected is cleared before adding items
 * TRACK::m_PadsConnected is not cleared
 */
306
void CONNECTIONS::SearchTracksConnectedToPads()
jean-pierre charras's avatar
jean-pierre charras committed
307 308 309 310 311 312
{
    std::vector<CONNECTED_POINT*> candidates;

    for( unsigned ii = 0; ii < m_sortedPads.size(); ii++ )
    {
        D_PAD * pad = m_sortedPads[ii];
313
        pad->m_TracksConnected.clear();
jean-pierre charras's avatar
jean-pierre charras committed
314
        candidates.clear();
315

Dick Hollenbeck's avatar
Dick Hollenbeck committed
316
        CollectItemsNearTo( candidates, pad->GetPosition(), pad->GetBoundingRadius() );
317

jean-pierre charras's avatar
jean-pierre charras committed
318 319 320
        // add this pad to track.m_PadsConnected, if it is connected
        for( unsigned jj = 0; jj < candidates.size(); jj++ )
        {
Dick Hollenbeck's avatar
Dick Hollenbeck committed
321 322 323
            CONNECTED_POINT* cp_item = candidates[jj];

            if( (pad->GetLayerMask() & cp_item->GetTrack()->ReturnMaskLayer()) == 0 )
jean-pierre charras's avatar
jean-pierre charras committed
324
                continue;
Dick Hollenbeck's avatar
Dick Hollenbeck committed
325

326
            if( pad->HitTest( cp_item->GetPoint() ) )
jean-pierre charras's avatar
jean-pierre charras committed
327
            {
328 329
                cp_item->GetTrack()->m_PadsConnected.push_back( pad );
                pad->m_TracksConnected.push_back( cp_item->GetTrack() );
jean-pierre charras's avatar
jean-pierre charras committed
330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348
            }
        }
    }
}

void CONNECTIONS::CollectItemsNearTo( std::vector<CONNECTED_POINT*>& aList,
                                       const wxPoint& aPosition, int aDistMax )
{
    /* Search items in m_Candidates that position is <= aDistMax from aPosition
     * (Rectilinear distance)
     * m_Candidates is sorted by X then Y values, so a fast binary search is used
     * to locate the "best" entry point in list
     * The best entry is a pad having its m_Pos.x == (or near) aPosition.x
     * All candidates are near this candidate in list
     * So from this entry point, a linear search is made to find all candidates
     */
    int idxmax = m_candidates.size()-1;

    int delta = m_candidates.size();
349 350

    int idx = 0;        // Starting index is the beginning of list
jean-pierre charras's avatar
jean-pierre charras committed
351 352
    while( delta )
    {
353 354
        // Calculate half size of remaining interval to test.
        // Ensure the computed value is not truncated (too small)
jean-pierre charras's avatar
jean-pierre charras committed
355 356 357 358 359 360
        if( (delta & 1) && ( delta > 1 ) )
            delta++;
        delta /= 2;

        CONNECTED_POINT& item = m_candidates[idx];

361 362 363
        int dist = item.GetPoint().x - aPosition.x;
        if( abs(dist) <= aDistMax )
        {
jean-pierre charras's avatar
jean-pierre charras committed
364
            break;   // A good entry point is found. The list can be scanned from this point.
365
        }
jean-pierre charras's avatar
jean-pierre charras committed
366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414

        else if( item.GetPoint().x < aPosition.x ) // We should search after this item
        {
            idx += delta;
            if( idx > idxmax )
                idx = idxmax;
        }
        else    // We should search before this item
        {
            idx -= delta;
            if( idx < 0 )
                idx = 0;
        }
    }

    /* Now explore the candidate list from the "best" entry point found
     * (candidate "near" aPosition.x)
     * We explore the list until abs(candidate->m_Point.x - aPosition.x) > aDistMax
     * because the list is sorted by X position (and for a given X pos, by Y pos)
     * Currently a linear search is made because the number of candidates
     * having the right X position is usually small
     */
    // search next candidates in list
    wxPoint diff;
    for( int ii = idx; ii <= idxmax; ii++ )
    {
        CONNECTED_POINT* item = &m_candidates[ii];
        diff = item->GetPoint() - aPosition;
        if( abs(diff.x) > aDistMax )
            break;    // Exit: the distance is to long, we cannot find other candidates
        if( abs(diff.y) > aDistMax )
            continue;    // the y distance is to long, but we can find other candidates
        // We have here a good candidate: add it
        aList.push_back( item );
    }
    // search previous candidates in list
    for(  int ii = idx-1; ii >=0; ii-- )
    {
        CONNECTED_POINT * item = &m_candidates[ii];
        diff = item->GetPoint() - aPosition;
        if( abs(diff.x) > aDistMax )
            break;
        if( abs(diff.y) > aDistMax )
            continue;
        // We have here a good candidate:add it
        aList.push_back( item );
    }
}

415 416 417 418 419 420 421 422 423 424 425 426 427

void CONNECTIONS::BuildPadsCandidatesList()
{
    m_candidates.clear();
    m_candidates.reserve( m_sortedPads.size() );
    for( unsigned ii = 0; ii < m_sortedPads.size(); ii++ )
    {
        D_PAD * pad = m_sortedPads[ii];
        CONNECTED_POINT candidate( pad, pad->GetPosition() );
        m_candidates.push_back( candidate );
    }
}

428 429 430 431 432 433 434
/* sort function used to sort .m_Connected by X the Y values
 * items are sorted by X coordinate value,
 * and for same X value, by Y coordinate value.
 */
static bool sortConnectedPointByXthenYCoordinates( const CONNECTED_POINT & aRef,
                                                   const CONNECTED_POINT & aTst )
{
jean-pierre charras's avatar
jean-pierre charras committed
435 436 437
    if( aRef.GetPoint().x == aTst.GetPoint().x )
        return aRef.GetPoint().y < aTst.GetPoint().y;
    return aRef.GetPoint().x < aTst.GetPoint().x;
438 439
}

440
void CONNECTIONS::BuildTracksCandidatesList( TRACK * aBegin, TRACK * aEnd)
441
{
jean-pierre charras's avatar
jean-pierre charras committed
442
    m_candidates.clear();
443

444 445
//    if( aBegin == NULL )
//        aBegin = m_brd->m_Track;
446

447
    m_firstTrack = m_lastTrack = aBegin;
448

449 450 451 452 453 454 455 456 457
    unsigned ii = 0;
    // Count candidates ( i.e. end points )
    for( const TRACK* track = aBegin; track; track = track->Next() )
    {
        if( track->Type() == PCB_VIA_T )
            ii++;
        else
            ii += 2;

458
        m_lastTrack = track;
459 460 461 462
        if( track == aEnd )
            break;
    }
    // Build candidate list
jean-pierre charras's avatar
jean-pierre charras committed
463
    m_candidates.reserve( ii );
464
    for( TRACK* track = aBegin; track; track = track->Next() )
465 466
    {
        CONNECTED_POINT candidate( track, track->m_Start);
jean-pierre charras's avatar
jean-pierre charras committed
467
        m_candidates.push_back( candidate );
468 469
        if( track->Type() != PCB_VIA_T )
        {
jean-pierre charras's avatar
jean-pierre charras committed
470 471
            CONNECTED_POINT candidate2( track, track->m_End);
            m_candidates.push_back( candidate2 );
472 473 474 475 476 477 478 479 480
        }

        if( track == aEnd )
            break;
    }

    // Sort list by increasing X coordinate,
    // and for increasing Y coordinate when items have the same X coordinate
    // So candidates to the same location are consecutive in list.
jean-pierre charras's avatar
jean-pierre charras committed
481
    sort( m_candidates.begin(), m_candidates.end(), sortConnectedPointByXthenYCoordinates );
482 483 484 485 486
}

int CONNECTIONS::SearchConnectedTracks( const TRACK * aTrack )
{
    int count = 0;
jean-pierre charras's avatar
jean-pierre charras committed
487
    m_connected.clear();
488 489 490 491 492 493 494

    int layerMask = aTrack->ReturnMaskLayer();

    // Search for connections to starting point:
    wxPoint position = aTrack->m_Start;
    for( int kk = 0; kk < 2; kk++ )
    {
495
        int idx = searchEntryPointInCandidatesList( position );
496 497 498
        if ( idx >= 0 )
        {
            // search after:
jean-pierre charras's avatar
jean-pierre charras committed
499
            for ( unsigned ii = idx; ii < m_candidates.size(); ii ++ )
500
            {
jean-pierre charras's avatar
jean-pierre charras committed
501
                if( m_candidates[ii].GetTrack() == aTrack )
502
                    continue;
jean-pierre charras's avatar
jean-pierre charras committed
503
                if( m_candidates[ii].GetPoint() != position )
504
                    break;
jean-pierre charras's avatar
jean-pierre charras committed
505 506
                if( (m_candidates[ii].GetTrack()->ReturnMaskLayer() & layerMask ) != 0 )
                    m_connected.push_back( m_candidates[ii].GetTrack() );
507 508
            }
            // search before:
509
            for ( int ii = idx-1; ii >= 0; ii -- )
510
            {
jean-pierre charras's avatar
jean-pierre charras committed
511
                if( m_candidates[ii].GetTrack() == aTrack )
512
                    continue;
jean-pierre charras's avatar
jean-pierre charras committed
513
                if( m_candidates[ii].GetPoint() != position )
514
                    break;
jean-pierre charras's avatar
jean-pierre charras committed
515 516
                if( (m_candidates[ii].GetTrack()->ReturnMaskLayer() & layerMask ) != 0 )
                    m_connected.push_back( m_candidates[ii].GetTrack() );
517 518 519 520 521 522 523 524 525 526 527 528 529
            }
        }

        // Search for connections to ending point:
        if( aTrack->Type() == PCB_VIA_T )
            break;

        position = aTrack->m_End;
    }

    return count;
}

530
int CONNECTIONS::searchEntryPointInCandidatesList( const wxPoint & aPoint)
531 532 533
{
    // Search the aPoint coordinates in m_Candidates
    // m_Candidates is sorted by X then Y values, and a fast binary search is used
jean-pierre charras's avatar
jean-pierre charras committed
534
    int idxmax = m_candidates.size()-1;
535

jean-pierre charras's avatar
jean-pierre charras committed
536
    int delta = m_candidates.size();
537 538

    int idx = 0;        // Starting index is the beginning of list
539 540
    while( delta )
    {
541 542
        // Calculate half size of remaining interval to test.
        // Ensure the computed value is not truncated (too small)
543 544 545 546
        if( (delta & 1) && ( delta > 1 ) )
            delta++;
        delta /= 2;

jean-pierre charras's avatar
jean-pierre charras committed
547 548
        CONNECTED_POINT & candidate = m_candidates[idx];
        if( candidate.GetPoint() == aPoint )   // candidate found
549 550 551 552 553
        {
            return idx;
        }

        // Not found: test the middle of the remaining sub list
jean-pierre charras's avatar
jean-pierre charras committed
554
        if( candidate.GetPoint().x == aPoint.x )   // Must search considering Y coordinate
555
        {
jean-pierre charras's avatar
jean-pierre charras committed
556
            if(candidate.GetPoint().y < aPoint.y)  // Must search after this item
557 558 559 560 561 562 563 564 565 566 567 568
            {
                idx += delta;
                if( idx > idxmax )
                    idx = idxmax;
            }
            else // Must search before this item
            {
                idx -= delta;
                if( idx < 0 )
                    idx = 0;
            }
        }
jean-pierre charras's avatar
jean-pierre charras committed
569
        else if( candidate.GetPoint().x < aPoint.x ) // Must search after this item
570 571 572 573 574 575 576 577 578 579 580 581 582 583 584
        {
            idx += delta;
            if( idx > idxmax )
                idx = idxmax;
        }
        else // Must search before this item
        {
            idx -= delta;
            if( idx < 0 )
                idx = 0;
        }
    }

    return -1;
}
585

586
/* Used after a track change (delete a track ou add a track)
587
 * Connections to pads are recalculated
588
 * Note also aFirstTrack (and aLastTrack ) can be NULL
589
 */
590
void CONNECTIONS::Build_CurrNet_SubNets_Connections( TRACK* aFirstTrack, TRACK* aLastTrack, int aNetcode )
591 592 593 594 595 596
{
    m_firstTrack = aFirstTrack;     // The first track used to build m_Candidates
    m_lastTrack = aLastTrack;       // The last track used to build m_Candidates

    // Pads subnets are expected already cleared, because this function
    // does not know the full list of pads
597
    BuildTracksCandidatesList( aFirstTrack, aLastTrack );
598
    TRACK* curr_track;
599 600 601 602 603
    for( curr_track = aFirstTrack; curr_track != NULL; curr_track = curr_track->Next() )
    {
        // Clear track subnet id (Pads subnets are cleared outside this function)
        curr_track->SetSubNet( 0 );
        curr_track->m_TracksConnected.clear();
604
        curr_track->m_PadsConnected.clear();
605 606 607

        // Update connections between tracks:
        SearchConnectedTracks( curr_track );
jean-pierre charras's avatar
jean-pierre charras committed
608
        curr_track->m_TracksConnected = m_connected;
609 610 611 612 613

        if( curr_track == aLastTrack )
            break;
    }

614 615 616
    // Update connections between tracks and pads
    BuildPadsList( aNetcode );
    SearchTracksConnectedToPads();
617

618 619 620
    // Update connections between intersecting pads (no tracks)
    SearchConnectionsPadsToIntersectingPads();

621
    // Creates sub nets (clusters) for the current net:
622 623 624 625
    Propagate_SubNets();
}


626 627 628 629 630 631 632 633 634 635 636 637 638 639 640 641 642 643 644 645 646 647 648 649 650 651 652 653 654
/**
 * Change a subnet value to a new value, in m_sortedPads pad list
 * After that, 2 cluster (or subnets) are merged into only one.
 * Note: the resulting subnet value is the smallest between aOldSubNet et aNewSubNet
 */
int CONNECTIONS::Merge_PadsSubNets( int aOldSubNet, int aNewSubNet )
{
    int    change_count = 0;

    if( aOldSubNet == aNewSubNet )
        return 0;

    if( (aOldSubNet > 0) && (aOldSubNet < aNewSubNet) )
        EXCHG( aOldSubNet, aNewSubNet );

    // Examine connections between intersecting pads
    for( unsigned ii = 0; ii < m_sortedPads.size(); ii++ )
    {
        D_PAD * curr_pad = m_sortedPads[ii];
        if( curr_pad->GetSubNet() != aOldSubNet )
            continue;

        change_count++;
        curr_pad->SetSubNet( aNewSubNet );
    }

    return change_count;
}

655 656 657 658
/*
 * Change a subnet value to a new value, for tracks and pads which are connected to.
 * The result is merging 2 clusters (or subnets) into only one cluster.
 * Note: the resultig sub net value is the smallest between aOldSubNet et aNewSubNet
659
 */
660
int CONNECTIONS::Merge_SubNets( int aOldSubNet, int aNewSubNet )
661
{
662 663
    TRACK* curr_track;
    int    change_count = 0;
664

665
    if( aOldSubNet == aNewSubNet )
666 667
        return 0;

668 669
    if( (aOldSubNet > 0) && (aOldSubNet < aNewSubNet) )
        EXCHG( aOldSubNet, aNewSubNet );
670

671
    curr_track = (TRACK*)m_firstTrack;
672

673
    for( ; curr_track != NULL; curr_track = curr_track->Next() )
674
    {
675
        if( curr_track->GetSubNet() != aOldSubNet )
676
        {
677
            if( curr_track == m_lastTrack )
678
                break;
679

680 681 682
            continue;
        }

683 684
        change_count++;
        curr_track->SetSubNet( aNewSubNet );
685

jean-pierre charras's avatar
jean-pierre charras committed
686
        for( unsigned ii = 0; ii < curr_track->m_PadsConnected.size(); ii++ )
687
        {
jean-pierre charras's avatar
jean-pierre charras committed
688 689 690
            D_PAD * pad = curr_track->m_PadsConnected[ii];
            if( pad->GetSubNet() == aOldSubNet )
                pad->SetSubNet( curr_track->GetSubNet() );
691
        }
692

693
        if( curr_track == m_lastTrack )
694 695 696
            break;
    }

697
    return change_count;
698 699
}

700

701 702 703 704 705 706 707 708
/* Test a list of track segments, to create or propagate a sub netcode to pads and
 * segments connected together.
 * The track list must be sorted by nets, and all segments
 * from m_firstTrack to m_lastTrack have the same net
 * When 2 items are connected (a track to a pad, or a track to an other track),
 * they are grouped in a cluster.
 * For pads, this is the .m_physical_connexion member which is a cluster identifier
 * For tracks, this is the .m_Subnet member which is a cluster identifier
709
 * For a given net, if all tracks are created, there is only one cluster.
710 711
 * but if not all tracks are created, there are more than one cluster,
 * and some ratsnests will be left active.
712
 */
713
void CONNECTIONS::Propagate_SubNets()
714
{
715
    int sub_netcode = 0;
716

717 718 719 720 721 722 723 724 725 726 727 728 729 730 731 732 733 734 735 736 737
    // Examine connections between intersecting pads
    for( unsigned ii = 0; ii < m_sortedPads.size(); ii++ )
    {
        D_PAD * curr_pad = m_sortedPads[ii];
        for( unsigned jj = 0; jj < curr_pad->m_PadsConnected.size(); jj++ )
        {
            D_PAD * pad = curr_pad->m_PadsConnected[jj];
            if( curr_pad->GetSubNet() )
            {
                if( pad->GetSubNet() > 0 )
                {
                    // The pad is already a cluster member, so we can merge the 2 clusters
                    Merge_PadsSubNets( pad->GetSubNet(), curr_pad->GetSubNet() );
                }
                else
                {
                    // The pad is not yet attached to a cluster,
                    // so we can add this pad to the cluster
                    pad->SetSubNet( curr_pad->GetSubNet() );
                }
            }
Dick Hollenbeck's avatar
Dick Hollenbeck committed
738
            else                              // the track segment is not attached to a cluster
739 740 741 742 743 744 745 746 747 748 749 750 751 752 753 754 755
            {
                if( pad->GetSubNet() > 0 )
                {
                    // it is connected to a pad in a cluster, merge this pad
                    curr_pad->SetSubNet( pad->GetSubNet() );
                }
                else
                {
                    // it is connected to a pad not in a cluster,
                    // so we must create a new cluster (only with the 2 pads.
                    sub_netcode++;
                    curr_pad->SetSubNet( sub_netcode );
                    pad->SetSubNet( curr_pad->GetSubNet() );
                }
            }
        }
    }
756

757 758 759 760 761 762
    sub_netcode++;
    TRACK* curr_track = (TRACK*)m_firstTrack;
    if( curr_track )
        curr_track->SetSubNet( sub_netcode );

    // Examine connections between trcaks and pads
763
    for( ; curr_track != NULL; curr_track = curr_track->Next() )
764
    {
Dick Hollenbeck's avatar
Dick Hollenbeck committed
765
        // First: handling connections to pads
jean-pierre charras's avatar
jean-pierre charras committed
766
        for( unsigned ii = 0; ii < curr_track->m_PadsConnected.size(); ii++ )
767
        {
jean-pierre charras's avatar
jean-pierre charras committed
768 769
            D_PAD * pad = curr_track->m_PadsConnected[ii];

Dick Hollenbeck's avatar
Dick Hollenbeck committed
770
            if( curr_track->GetSubNet() )        // the track segment is already a cluster member
771
            {
jean-pierre charras's avatar
jean-pierre charras committed
772
                if( pad->GetSubNet() > 0 )
773
                {
Dick Hollenbeck's avatar
Dick Hollenbeck committed
774
                    // The pad is already a cluster member, so we can merge the 2 clusters
jean-pierre charras's avatar
jean-pierre charras committed
775
                    Merge_SubNets( pad->GetSubNet(), curr_track->GetSubNet() );
776
                }
jean-pierre charras's avatar
jean-pierre charras committed
777
                else
778
                {
jean-pierre charras's avatar
jean-pierre charras committed
779 780 781 782 783
                    /* The pad is not yet attached to a cluster , so we can add this pad to
                     * the cluster */
                    pad->SetSubNet( curr_track->GetSubNet() );
                }
            }
Dick Hollenbeck's avatar
Dick Hollenbeck committed
784
            else                              // the track segment is not attached to a cluster
jean-pierre charras's avatar
jean-pierre charras committed
785 786 787
            {
                if( pad->GetSubNet() > 0 )
                {
Dick Hollenbeck's avatar
Dick Hollenbeck committed
788
                    // it is connected to a pad in a cluster, merge this track
jean-pierre charras's avatar
jean-pierre charras committed
789 790 791 792 793 794 795 796 797
                    curr_track->SetSubNet( pad->GetSubNet() );
                }
                else
                {
                    /* it is connected to a pad not in a cluster, so we must create a new
                     * cluster (only with the 2 items: the track and the pad) */
                    sub_netcode++;
                    curr_track->SetSubNet( sub_netcode );
                    pad->SetSubNet( curr_track->GetSubNet() );
798 799 800 801
                }
            }
        }

Dick Hollenbeck's avatar
Dick Hollenbeck committed
802
        // Test connections between segments
803
        for( unsigned ii = 0; ii < curr_track->m_TracksConnected.size(); ii++ )
804
        {
805 806
            BOARD_CONNECTED_ITEM* track = curr_track->m_TracksConnected[ii];
            if( curr_track->GetSubNet() )   // The current track is already a cluster member
807
            {
Dick Hollenbeck's avatar
Dick Hollenbeck committed
808
                // The other track is already a cluster member, so we can merge the 2 clusters
809
                if( track->GetSubNet() )
810
                {
811
                    Merge_SubNets( track->GetSubNet(), curr_track->GetSubNet() );
812
                }
813
                else
814
                {
815 816
                    /* The other track is not yet attached to a cluster , so we can add this
                     * other track to the cluster */
817
                    track->SetSubNet( curr_track->GetSubNet() );
818 819
                }
            }
820
            else        // the current track segment is not yet attached to a cluster
821
            {
822
                if( track->GetSubNet() )
823
                {
824 825 826
                    // The other track is already a cluster member, so we can add
                    // the current segment to the cluster
                    curr_track->SetSubNet( track->GetSubNet() );
827
                }
828
                else
829
                {
830 831
                    /* it is connected to an other segment not in a cluster, so we must
                     * create a new cluster (only with the 2 track segments) */
832
                    sub_netcode++;
833 834
                    curr_track->SetSubNet( sub_netcode );
                    track->SetSubNet( curr_track->GetSubNet() );
835 836 837
                }
            }
        }
838

839
        if( curr_track == m_lastTrack )
840 841
            break;
    }
842 843
}

844 845 846 847 848 849
/*
 * Test all connections of the board,
 * and update subnet variable of pads and tracks
 * TestForActiveLinksInRatsnest must be called after this function
 * to update active/inactive ratsnest items status
 */
850
void PCB_BASE_FRAME::TestConnections()
851
{
852
    // Clear the cluster identifier for all pads
853
    for( unsigned i = 0;  i< m_Pcb->GetPadCount();  ++i )
854
    {
855
        D_PAD* pad = m_Pcb->GetPad(i);
856 857 858

        pad->SetZoneSubNet( 0 );
        pad->SetSubNet( 0 );
859 860
    }

861
    m_Pcb->Test_Connections_To_Copper_Areas();
862

863
    // Test existing connections net by net
864 865
    // note some nets can have no tracks, and pads intersecting
    // so Build_CurrNet_SubNets_Connections must be called for each net
866
    CONNECTIONS connections( m_Pcb );
867 868
    int last_net_tested = 0;
    int current_net_code = 0;
869
    for( TRACK* track = m_Pcb->m_Track; track; )
870
    {
871
        // At this point, track is the first track of a given net
872
        current_net_code = track->GetNet();
873 874
        // Get last track of the current net
        TRACK* lastTrack = track->GetEndNetCode( current_net_code );
875

876
        if( current_net_code > 0 )  // do not spend time if net code = 0 ( dummy net )
877 878 879 880 881
        {
            // Test all previous nets having no tracks
            for( int net = last_net_tested+1; net < current_net_code; net++ )
                connections.Build_CurrNet_SubNets_Connections( NULL, NULL, net );

882
            connections.Build_CurrNet_SubNets_Connections( track, lastTrack, current_net_code );
883 884
            last_net_tested = current_net_code;
        }
885

886
        track = lastTrack->Next();    // this is now the first track of the next net
887 888
    }

889 890 891 892 893
    // Test last nets without tracks, if any
    int netsCount = m_Pcb->GetNetCount();
    for( int net = last_net_tested+1; net < netsCount; net++ )
        connections.Build_CurrNet_SubNets_Connections( NULL, NULL, net );

894
    Merge_SubNets_Connected_By_CopperAreas( m_Pcb );
895

896
    return;
897 898
}

899

900
void PCB_BASE_FRAME::TestNetConnection( wxDC* aDC, int aNetCode )
901
{
902
    wxString msg;
903

904
    if( aNetCode <= 0 ) // -1 = not existing net, 0 = dummy net
905 906
        return;

907
    if( (m_Pcb->m_Status_Pcb & LISTE_RATSNEST_ITEM_OK) == 0 )
908
        Compile_Ratsnest( aDC, true );
909

910
    // Clear the cluster identifier (subnet) of pads for this net
911
    for( unsigned i = 0; i < m_Pcb->GetPadCount(); ++i )
912
    {
913
        D_PAD* pad = m_Pcb->GetPad(i);
914
        int    pad_net_code = pad->GetNet();
915

916
        if( pad_net_code < aNetCode )
917
            continue;
918

919
        if( pad_net_code > aNetCode )
920
            break;
921

922
        pad->SetSubNet( 0 );
923 924
    }

925
    m_Pcb->Test_Connections_To_Copper_Areas( aNetCode );
926

Dick Hollenbeck's avatar
Dick Hollenbeck committed
927
    // Search for the first and the last segment relative to the given net code
928 929
    if( m_Pcb->m_Track )
    {
930 931 932 933
        CONNECTIONS connections( m_Pcb );
        TRACK* firstTrack;
        TRACK* lastTrack = NULL;
        firstTrack = m_Pcb->m_Track.GetFirst()->GetStartNetCode( aNetCode );
934

935 936
        if( firstTrack )
            lastTrack = firstTrack->GetEndNetCode( aNetCode );
937

938
        if( firstTrack && lastTrack ) // i.e. if there are segments
939
        {
940
            connections.Build_CurrNet_SubNets_Connections( firstTrack, lastTrack, firstTrack->GetNet() );
941 942
        }
    }
943

944
    Merge_SubNets_Connected_By_CopperAreas( m_Pcb, aNetCode );
945

Dick Hollenbeck's avatar
Dick Hollenbeck committed
946
    // rebuild the active ratsnest for this net
947 948 949
    DrawGeneralRatsnest( aDC, aNetCode );
    TestForActiveLinksInRatsnest( aNetCode );
    DrawGeneralRatsnest( aDC, aNetCode );
950

Dick Hollenbeck's avatar
Dick Hollenbeck committed
951
    // Display results
952 953
    int net_notconnected_count = 0;
    NETINFO_ITEM* net = m_Pcb->FindNet( aNetCode );
954
    if( net )       // Should not occur, but ...
955
    {
956 957 958 959 960 961 962 963
        for( unsigned ii = net->m_RatsnestStartIdx; ii < net->m_RatsnestEndIdx; ii++ )
        {
            if( m_Pcb->m_FullRatsnest[ii].IsActive() )
                net_notconnected_count++;
        }
        msg.Printf( wxT( "links %d nc %d  net:nc %d" ),
                    m_Pcb->GetRatsnestsCount(), m_Pcb->GetNoconnectCount(),
                    net_notconnected_count );
964
    }
965 966
    else
        msg.Printf( wxT( "net not found: netcode %d" ),aNetCode );
967

968
    SetStatusText( msg );
969
    return;
970 971 972
}


973 974 975
/* search connections between tracks and pads and propagate pad net codes to the track
 * segments.
 * Pads netcodes are assumed to be up to date.
976
 */
977
void PCB_BASE_FRAME::RecalculateAllTracksNetcode()
978
{
979
    TRACK*              curr_track;
980

981
    // Build the net info list
982 983
    GetBoard()->BuildListOfNets();

984
    // Reset variables and flags used in computation
985 986
    curr_track = m_Pcb->m_Track;
    for( ; curr_track != NULL; curr_track = curr_track->Next() )
987
    {
988
        curr_track->m_TracksConnected.clear();
jean-pierre charras's avatar
jean-pierre charras committed
989
        curr_track->m_PadsConnected.clear();
990 991
        curr_track->start = NULL;
        curr_track->end = NULL;
992 993
        curr_track->SetState( BUSY | IN_EDIT | BEGIN_ONPAD | END_ONPAD, OFF );
        curr_track->SetZoneSubNet( 0 );
994
        curr_track->SetNet( 0 );    // net code = 0 means not connected
995 996
    }

997
    // If no pad, reset pointers and netcode, and do nothing else
998
    if( m_Pcb->GetPadCount() == 0 )
999 1000
        return;

jean-pierre charras's avatar
jean-pierre charras committed
1001 1002
    CONNECTIONS connections( m_Pcb );
    connections.BuildPadsList();
1003
    connections.BuildTracksCandidatesList(m_Pcb->m_Track);
jean-pierre charras's avatar
jean-pierre charras committed
1004 1005

    // First pass: build connections between track segments and pads.
1006
    connections.SearchTracksConnectedToPads();
1007

jean-pierre charras's avatar
jean-pierre charras committed
1008 1009
    /* For tracks connected to at least one pad,
     * set the track net code to the pad netcode
1010
     */
1011 1012
    curr_track = m_Pcb->m_Track;
    for( ; curr_track != NULL; curr_track = curr_track->Next() )
1013
    {
jean-pierre charras's avatar
jean-pierre charras committed
1014 1015
        if( curr_track->m_PadsConnected.size() )
            curr_track->SetNet( curr_track->m_PadsConnected[0]->GetNet() );
1016 1017
    }

jean-pierre charras's avatar
jean-pierre charras committed
1018
    // Pass 2: build connections between track ends
1019
    for( curr_track = m_Pcb->m_Track; curr_track != NULL; curr_track = curr_track->Next() )
1020
    {
1021
        connections.SearchConnectedTracks( curr_track );
jean-pierre charras's avatar
jean-pierre charras committed
1022
        connections.GetConnectedTracks( curr_track );
1023 1024
    }

1025
    // Propagate net codes from a segment to other connected segments
jean-pierre charras's avatar
jean-pierre charras committed
1026
    bool new_pass_request = true;   // set to true if a track has its netcode changed from 0
1027 1028 1029
                                    // to a known netcode to re-evaluate netcodes
                                    // of connected items
    while( new_pass_request )
1030
    {
1031
        new_pass_request = false;
1032

1033
        for( curr_track = m_Pcb->m_Track; curr_track; curr_track = curr_track->Next() )
1034
        {
1035 1036 1037 1038
            int netcode = curr_track->GetNet();
            if( netcode == 0 )
            {   // try to find a connected item having a netcode
                for( unsigned kk = 0; kk < curr_track->m_TracksConnected.size(); kk++ )
1039
                {
1040 1041
                    int altnetcode = curr_track->m_TracksConnected[kk]->GetNet();
                    if( altnetcode )
1042
                    {
1043 1044 1045 1046
                        new_pass_request = true;
                        netcode = altnetcode;
                        curr_track->SetNet(netcode);
                        break;
1047 1048 1049
                    }
                }
            }
1050 1051 1052
            if( netcode )    // this track has a netcode
            {   // propagate this netcode to connected tracks having no netcode
                for( unsigned kk = 0; kk < curr_track->m_TracksConnected.size(); kk++ )
1053
                {
1054 1055
                    int altnetcode = curr_track->m_TracksConnected[kk]->GetNet();
                    if( altnetcode == 0 )
1056
                    {
1057 1058
                        curr_track->m_TracksConnected[kk]->SetNet(netcode);
                        new_pass_request = true;
1059 1060 1061 1062 1063 1064
                    }
                }
            }
        }
    }

Dick Hollenbeck's avatar
Dick Hollenbeck committed
1065
    // Sort the track list by net codes:
1066
    RebuildTrackChain( m_Pcb );
1067 1068
}

1069

1070 1071 1072 1073

/*
 * Function SortTracksByNetCode used in RebuildTrackChain()
 * to sort track segments by net code.
1074
 */
1075
static bool SortTracksByNetCode( const TRACK* const & ref, const TRACK* const & compare )
1076
{
1077
    return ref->GetNet() < compare->GetNet();
1078
}
1079

1080
/**
jean-pierre charras's avatar
jean-pierre charras committed
1081
 * Helper function RebuildTrackChain
1082 1083
 * rebuilds the track segment linked list in order to have a chain
 * sorted by increasing netcodes.
1084
 * @param pcb = board to rebuild
1085
 */
1086
static void RebuildTrackChain( BOARD* pcb )
1087
{
1088 1089 1090
    if( pcb->m_Track == NULL )
        return;

1091
    int item_count = pcb->m_Track.GetCount();
1092

1093 1094
    std::vector<TRACK*> trackList;
    trackList.reserve( item_count );
1095

jean-pierre charras's avatar
jean-pierre charras committed
1096
    for( int i = 0; i < item_count; ++i )
1097
        trackList.push_back( pcb->m_Track.PopFront() );
1098

1099 1100
    // the list is empty now
    wxASSERT( pcb->m_Track == NULL && pcb->m_Track.GetCount()==0 );
1101

1102
    sort( trackList.begin(), trackList.end(), SortTracksByNetCode );
1103

1104
    // add them back to the list
1105 1106
    for( int i = 0; i < item_count;  ++i )
        pcb->m_Track.PushBack( trackList[i] );
1107
}