work.cpp 4.38 KB
Newer Older
1 2 3
/*
 * This program source code file is part of KiCad, a free EDA CAD application.
 *
4 5
 * Copyright (C) 2012 Jean-Pierre Charras, jean-pierre.charras@ujf-grenoble.fr
 * Copyright (C) 2012 SoftPLC Corporation, Dick Hollenbeck <dick@softplc.com>
6
 * Copyright (C) 2011 Wayne Stambaugh <stambaughw@verizon.net>
7 8 9 10
 *
 * Copyright (C) 1992-2012 KiCad Developers, see change_log.txt for contributors.
 *
 * First copyright (C) Randy Nevin, 1989 (see PCBCA package)
11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29
 *
 * 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
/**
 * @file work.cpp
 * @brief Automatic routing routines
 */
35

36 37
#include <fctsys.h>
#include <common.h>
38

39
#include <pcbnew.h>
40
#include <autorout.h>
41
#include <cell.h>
42 43


44 45
struct CWORK    // a unit of work is a source-target to connect
                // this is a ratsnest item in the routing matrix world
46
{
47 48 49 50 51 52 53 54 55
    int             m_FromRow;      // source row
    int             m_FromCol;      // source column
    int             m_ToRow;        // target row
    int             m_ToCol;        // target column
    RATSNEST_ITEM*  m_Ratsnest;     // Corresponding ratsnest
    int             m_NetCode;      // m_NetCode
    int             m_ApxDist;      // approximate distance
    int             m_Cost;         // cost for sort by length
    int             m_Priority;     // route priority
56 57 58

    // the function that calculates the cost of this ratsnest:
    void CalculateCost();
59 60
};

61

62 63 64
// the list of ratsnests
static std::vector <CWORK> WorkList;
static unsigned Current = 0;
65 66


67
// initialize the work list
68
void InitWork()
69
{
70 71
    WorkList.clear();
    Current = 0;
72
}
73 74 75


/* add a unit of work to the work list
76 77 78 79 80
 * Return:
 *  1 if OK
 *  0 if memory allocation failed
 */

81 82 83 84
int SetWork( int r1, int c1,
             int n_c,
             int r2, int c2,
             RATSNEST_ITEM* pt_ch, int pri )
85
{
86 87 88 89 90 91 92 93 94 95 96 97
    CWORK item;
    item.m_FromRow    = r1;
    item.m_FromCol    = c1;
    item.m_NetCode    = n_c;
    item.m_ToRow      = r2;
    item.m_ToCol      = c2;
    item.m_Ratsnest   = pt_ch;
    item.m_ApxDist    = RoutingMatrix.GetApxDist( r1, c1, r2, c2 );
    item.CalculateCost();
    item.m_Priority   = pri;
    WorkList.push_back( item );
    return 1;
98 99 100
}


101
/* fetch a unit of work from the work list */
102 103 104
void GetWork( int* r1, int* c1,
              int* n_c,
              int* r2, int* c2,
105
              RATSNEST_ITEM** pt_ch )
106
{
107
    if( Current < WorkList.size() )
108
    {
109 110 111 112 113 114 115
        *r1     = WorkList[Current].m_FromRow;
        *c1     = WorkList[Current].m_FromCol;
        *n_c    = WorkList[Current].m_NetCode;
        *r2     = WorkList[Current].m_ToRow;
        *c2     = WorkList[Current].m_ToCol;
        *pt_ch  = WorkList[Current].m_Ratsnest;
        Current++;
116
    }
117
    else    /* none left */
118
    {
119 120 121
        *r1     = *c1 = *r2 = *c2 = ILLEGAL;
        *n_c    = 0;
        *pt_ch  = NULL;
122
    }
123 124 125
}


126 127
// order the work items; shortest (low cost) first:
bool sort_by_cost( const CWORK& ref, const CWORK& item )
128
{
129 130
    if( ref.m_Priority == item.m_Priority )
        return ref.m_Cost < item.m_Cost;
131

132 133
    return ref.m_Priority >= item.m_Priority;
}
134

135 136 137
void SortWork()
{
    sort( WorkList.begin(), WorkList.end(), sort_by_cost );
138 139 140
}


141
/* Calculate the cost of a ratsnest:
142 143 144
 *   cost = (| dx | + | dy |) * disability
 *   disability = 1 if dx or dy = 0, max if | dx | # | dy |
 */
145
void CWORK::CalculateCost()
plyatov's avatar
plyatov committed
146
{
147 148
    int     dx, dy, mx, my;
    double  incl = 1.0;
149

150 151
    dx  = abs( m_ToCol - m_FromCol );
    dy  = abs( m_ToRow - m_FromRow );
152 153
    mx  = dx;
    my  = dy;
154 155 156 157 158

    if( mx < my )
    {
        mx = dy; my = dx;
    }
159

160
    if( mx )
161
        incl += (2 * (double) my / mx);
162

163
    m_Cost = (int) ( ( dx + dy ) * incl );
plyatov's avatar
plyatov committed
164
}