pns_index.h 6.19 KB
Newer Older
1 2 3 4 5
/*
 * KiRouter - a push-and-(sometimes-)shove PCB router
 *
 * Copyright (C) 2013  CERN
 * Author: Tomasz Wlostowski <tomasz.wlostowski@cern.ch>
6
 *
7 8 9 10
 * 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 3 of the License, or (at your
 * option) any later version.
11
 *
12 13 14 15
 * 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.
16
 *
17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39
 * You should have received a copy of the GNU General Public License along
 * with this program.  If not, see <http://www.gnu.or/licenses/>.
 */

#ifndef __PNS_INDEX_H
#define __PNS_INDEX_H

#include <boost/foreach.hpp>
#include <boost/range/adaptor/map.hpp>

#include <list>
#include <geometry/shape_index.h>

#include "pns_item.h"

/**
 * Class PNS_INDEX
 *
 * Custom spatial index, holding our board items and allowing for very fast searches. Items
 * are assigned to separate R-Tree subundices depending on their type and spanned layers, reducing
 * overlap and improving search time.
 **/

40 41
class PNS_INDEX
{
42
public:
43 44 45
    typedef std::list<PNS_ITEM*>            NetItemsList;
    typedef SHAPE_INDEX<PNS_ITEM*>          ItemShapeIndex;
    typedef boost::unordered_set<PNS_ITEM*> ItemSet;
46

47 48
    PNS_INDEX();
    ~PNS_INDEX();
49

50 51 52
    void Add( PNS_ITEM* aItem );
    void Remove( PNS_ITEM* aItem );
    void Replace( PNS_ITEM* aOldItem, PNS_ITEM* aNewItem );
53

54 55
    template<class Visitor>
    int Query( const PNS_ITEM* aItem, int aMinDistance, Visitor& v );
56

57 58
    template<class Visitor>
    int Query( const SHAPE* aShape, int aMinDistance, Visitor& v );
59

60
    void Clear();
61

62
    NetItemsList* GetItemsForNet( int aNet );
63

64 65
    ItemSet::iterator begin() { return m_allItems.begin(); }
    ItemSet::iterator end() { return m_allItems.end(); }
66

67 68 69 70
    bool Contains( PNS_ITEM* aItem ) const
    {
        return m_allItems.find( aItem ) != m_allItems.end();
    }
71

72
    int Size() const { return m_allItems.size(); }
73

74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90
private:
    static const int    MaxSubIndices   = 64;
    static const int    SI_Multilayer   = 2;
    static const int    SI_SegDiagonal  = 0;
    static const int    SI_SegStraight  = 1;
    static const int    SI_Traces   = 3;
    static const int    SI_PadsTop  = 0;
    static const int    SI_PadsBottom = 1;

    template <class Visitor>
    int querySingle( int index, const SHAPE* aShape, int aMinDistance, Visitor& v );

    ItemShapeIndex* getSubindex( const PNS_ITEM* aItem );

    ItemShapeIndex* m_subIndices[MaxSubIndices];
    std::map<int, NetItemsList> m_netMap;
    ItemSet m_allItems;
91 92
};

93

94 95
PNS_INDEX::PNS_INDEX()
{
96
    memset( m_subIndices, 0, sizeof( m_subIndices ) );
97 98
}

99 100

PNS_INDEX::ItemShapeIndex* PNS_INDEX::getSubindex( const PNS_ITEM* aItem )
101
{
102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138
    int idx_n = -1;

    const PNS_LAYERSET l = aItem->GetLayers();

    switch( aItem->GetKind() )
    {
    case PNS_ITEM::VIA:
        idx_n = SI_Multilayer;
        break;

    case PNS_ITEM::SOLID:
        {
            if( l.IsMultilayer() )
                idx_n = SI_Multilayer;
            else if( l.Start() == 0 ) // fixme: use kicad layer codes
                idx_n = SI_PadsTop;
            else if( l.Start() == 15 )
                idx_n = SI_PadsBottom;

            break;
        }

    case PNS_ITEM::SEGMENT:
    case PNS_ITEM::LINE:
        idx_n = SI_Traces + 2 * l.Start() + SI_SegStraight;
        break;

    default:
        break;
    }

    assert( idx_n >= 0 && idx_n < MaxSubIndices );

    if( !m_subIndices[idx_n] )
        m_subIndices[idx_n] = new ItemShapeIndex;

    return m_subIndices[idx_n];
139 140
}

141 142

void PNS_INDEX::Add( PNS_ITEM* aItem )
143
{
144 145 146 147 148 149 150 151 152 153
    ItemShapeIndex* idx = getSubindex( aItem );

    idx->Add( aItem );
    m_allItems.insert( aItem );
    int net = aItem->GetNet();

    if( net >= 0 )
    {
        m_netMap[net].push_back( aItem );
    }
154 155
}

156 157

void PNS_INDEX::Remove( PNS_ITEM* aItem )
158
{
159 160 161 162 163 164 165 166 167
    ItemShapeIndex* idx = getSubindex( aItem );

    idx->Remove( aItem );
    m_allItems.erase( aItem );

    int net = aItem->GetNet();

    if( net >= 0 && m_netMap.find( net ) != m_netMap.end() )
        m_netMap[net].remove( aItem );
168 169
}

170 171

void PNS_INDEX::Replace( PNS_ITEM* aOldItem, PNS_ITEM* aNewItem )
172
{
173 174
    Remove( aOldItem );
    Add( aNewItem );
175 176
}

177

178
template<class Visitor>
179 180 181 182 183 184 185 186
int PNS_INDEX::querySingle( int index, const SHAPE* aShape, int aMinDistance, Visitor& v )
{
    if( !m_subIndices[index] )
        return 0;

    return m_subIndices[index]->Query( aShape, aMinDistance, v, false );
}

187 188

template<class Visitor>
189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220
int PNS_INDEX::Query( const PNS_ITEM* aItem, int aMinDistance, Visitor& v )
{
    const SHAPE* shape = aItem->GetShape();
    int total = 0;

    total += querySingle( SI_Multilayer, shape, aMinDistance, v );

    const PNS_LAYERSET layers = aItem->GetLayers();

    if( layers.IsMultilayer() )
    {
        total += querySingle( SI_PadsTop, shape, aMinDistance, v );
        total += querySingle( SI_PadsBottom, shape, aMinDistance, v );

        for( int i = layers.Start(); i <= layers.End(); ++i )
            total += querySingle( SI_Traces + 2 * i + SI_SegStraight, shape, aMinDistance, v );
    }
    else
    {
        int l = layers.Start();

        if( l == 0 )
            total += querySingle( SI_PadsTop, shape, aMinDistance, v );
        else if( l == 15 )
            total += querySingle( SI_PadsBottom, shape, aMinDistance, v );

        total += querySingle(  SI_Traces + 2 * l + SI_SegStraight, shape, aMinDistance, v );
    }

    return total;
}

221 222

template<class Visitor>
223 224 225 226 227 228 229 230 231 232 233
int PNS_INDEX::Query( const SHAPE* aShape, int aMinDistance, Visitor& v )
{
    int total = 0;

    for( int i = 0; i < MaxSubIndices; i++ )
        total += querySingle( i, aShape, aMinDistance, v );

    return total;
}


234 235
void PNS_INDEX::Clear()
{
236 237 238 239 240 241 242 243 244
    for( int i = 0; i < MaxSubIndices; ++i )
    {
        ItemShapeIndex* idx = m_subIndices[i];

        if( idx )
            delete idx;

        m_subIndices[i] = NULL;
    }
245 246
}

247

248 249
PNS_INDEX::~PNS_INDEX()
{
250
    Clear();
251 252
}

253 254

PNS_INDEX::NetItemsList* PNS_INDEX::GetItemsForNet( int aNet )
255
{
256 257 258 259
    if( m_netMap.find( aNet ) == m_netMap.end() )
        return NULL;

    return &m_netMap[aNet];
260 261 262
}

#endif