pns_joint.h 5.78 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
 * 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_JOINT_H
#define __PNS_JOINT_H

#include <vector>
#include <boost/functional/hash.hpp>

#include <math/vector2d.h>

#include "pns_item.h"
#include "pns_segment.h"

/**
 * Class PNS_JOINT
34
 *
35
 * Represents a 2D point on a given set of layers and belonging to a certain
36
 * net, that links together a number of board items.
37
 * A hash table of joints is used by the router to follow connectivity between
38
 * the items.
39 40 41 42
 **/
class PNS_JOINT : public PNS_ITEM
{
public:
43 44 45 46 47 48 49 50 51 52 53 54 55
    typedef std::vector<PNS_ITEM*> LinkedItems;

    ///> Joints are hashed by their position, layers and net.
    ///  Linked items are, obviously, not hashed
    struct HashTag
    {
        VECTOR2I pos;
        int net;
    };

    PNS_JOINT() :
        PNS_ITEM( JOINT ) {}

56 57
    PNS_JOINT( const VECTOR2I& aPos, const PNS_LAYERSET& aLayers,
            int aNet = -1 ) :
58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80
        PNS_ITEM( JOINT )
    {
        m_tag.pos = aPos;
        m_tag.net = aNet;
        m_layers = aLayers;
    }

    PNS_JOINT( const PNS_JOINT& b ) :
        PNS_ITEM( JOINT )
    {
        m_layers = b.m_layers;
        m_tag.pos = b.m_tag.pos;
        m_tag.net = b.m_tag.net;
        m_linkedItems = b.m_linkedItems;
        m_layers = b.m_layers;
    }

    PNS_ITEM* Clone() const
    {
        assert( false );
        return NULL;
    }

81
    ///> Returns true if the joint is a trivial line corner, connecting two
82 83 84 85 86 87
    /// segments of the same net, on the same layer.
    bool IsLineCorner() const
    {
        if( m_linkedItems.size() != 2 )
            return false;

88
        if( m_linkedItems[0]->GetKind() != SEGMENT ||
89 90 91
                m_linkedItems[1]->GetKind() != SEGMENT )
            return false;

92 93
        PNS_SEGMENT* seg1 = static_cast<PNS_SEGMENT*>( m_linkedItems[0] );
        PNS_SEGMENT* seg2 = static_cast<PNS_SEGMENT*>( m_linkedItems[1] );
94 95 96 97 98 99 100 101

        // joints between segments of different widths are not trivial.
        return seg1->GetWidth() == seg2->GetWidth();
    }

    ///> Links the joint to a given board item (when it's added to the PNS_NODE)
    void Link( PNS_ITEM* aItem )
    {
102
        LinkedItems::iterator f = std::find( m_linkedItems.begin(),
103 104 105 106 107 108 109 110 111 112 113 114
                                             m_linkedItems.end(), aItem );

        if( f != m_linkedItems.end() )
            return;

        m_linkedItems.push_back( aItem );
    }

    ///> Unlinks a given board item from the joint (upon its removal from a PNS_NODE)
    ///> Returns true if the joint became dangling after unlinking.
    bool Unlink( PNS_ITEM* aItem )
    {
115
        LinkedItems::iterator f = std::find( m_linkedItems.begin(),
116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144
                                             m_linkedItems.end(), aItem );

        if( f != m_linkedItems.end() )
            m_linkedItems.erase( f );

        return m_linkedItems.size() == 0;
    }

    ///> For trivial joints, returns the segment adjacent to (aCurrent). For non-trival ones, returns
    ///> NULL, indicating the end of line.
    PNS_SEGMENT* NextSegment( PNS_SEGMENT* aCurrent ) const
    {
        if( !IsLineCorner() )
            return NULL;

        return static_cast<PNS_SEGMENT*>( m_linkedItems[m_linkedItems[0] == aCurrent ? 1 : 0] );
    }

    /// trivial accessors
    const HashTag& GetTag() const { return m_tag; }
    const VECTOR2I& GetPos() const { return m_tag.pos; }
    int GetNet() const { return m_tag.net; }
    LinkedItems& GetLinkList() { return m_linkedItems; };

    ///> Returns the number of linked items of types listed in aMask.
    int LinkCount( int aMask = -1 ) const
    {
        int n = 0;

145
        for( LinkedItems::const_iterator i = m_linkedItems.begin();
146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168
                                         i != m_linkedItems.end(); ++i )
            if( (*i)->GetKind() & aMask )
                n++;

        return n;
    }

    void Dump() const;

    bool operator==( const PNS_JOINT& rhs )  const
    {
        return m_tag.pos == rhs.m_tag.pos && m_tag.net == rhs.m_tag.net;
    }

    void Merge( const PNS_JOINT& aJoint )
    {
        if( !Overlaps( aJoint ) )
            return;

        m_layers.Merge( aJoint.m_layers );

        // fixme: duplicate links (?)
        for( LinkedItems::const_iterator i = aJoint.m_linkedItems.begin();
169
             i != aJoint.m_linkedItems.end(); ++i )
170 171 172 173 174
            m_linkedItems.push_back( *i );
    }

    bool Overlaps( const PNS_JOINT& rhs ) const
    {
175
        return m_tag.pos == rhs.m_tag.pos &&
176 177
            m_tag.net == rhs.m_tag.net && m_layers.Overlaps( rhs.m_layers );
    }
178 179

private:
180 181
    ///> hash tag for unordered_multimap
    HashTag m_tag;
182

183 184
    ///> list of items linked to this joint
    LinkedItems m_linkedItems;
185 186 187 188
};


// hash function & comparison operator for boost::unordered_map<>
189
inline bool operator==( PNS_JOINT::HashTag const& p1,
190
                        PNS_JOINT::HashTag const& p2 )
191 192 193 194
{
    return p1.pos == p2.pos && p1.net == p2.net;
}

195 196

inline std::size_t hash_value( PNS_JOINT::HashTag const& p )
197 198
{
    std::size_t seed = 0;
199 200 201 202
    boost::hash_combine( seed, p.pos.x );
    boost::hash_combine( seed, p.pos.y );
    boost::hash_combine( seed, p.net );

203 204 205
    return seed;
}

206
#endif    // __PNS_JOINT_H