sch_rtree.h

Go to the documentation of this file.

/*
 * This program source code file is part of KiCad, a free EDA CAD application.
 *
 * Copyright The KiCad Developers, see AUTHORS.txt for contributors.
 * Copyright (C) 2020 CERN
 *
 * 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.
 *
 * 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, see <https://www.gnu.org/licenses/>.
 */
 
#ifndef EESCHEMA_SCH_RTREE_H_
#define EESCHEMA_SCH_RTREE_H_
 
#include <core/typeinfo.h>
#include <sch_item.h>
 
#include <geometry/rtree/dynamic_rtree.h>
 
#include <utility>
#include <unordered_set>

class EE_RTREE
{
private:
    using ee_rtree = KIRTREE::DYNAMIC_RTREE<SCH_ITEM*, int, 3>;
 
public:
    EE_RTREE() = default;
    EE_RTREE( const EE_RTREE& ) = delete;
    EE_RTREE& operator=( const EE_RTREE& ) = delete;
 
    EE_RTREE( EE_RTREE&& aOther ) noexcept :
            m_tree( std::move( aOther.m_tree ) ),
            m_members( std::move( aOther.m_members ) )
    {
        aOther.m_members.clear();
    }
 
    EE_RTREE& operator=( EE_RTREE&& aOther ) noexcept
    {
        if( this != &aOther )
        {
            m_tree = std::move( aOther.m_tree );
            m_members = std::move( aOther.m_members );
            aOther.m_members.clear();
        }
 
        return *this;
    }
 
    ~EE_RTREE() = default;

    void insert( SCH_ITEM* aItem )
    {
        BOX2I bbox = aItem->GetBoundingBox();
 
        // Inflate a bit for safety, selection shadows, etc.
        bbox.Inflate( aItem->GetPenWidth() );
 
        const int type    = int( aItem->Type() );
        const int mmin[3] = { type, bbox.GetX(), bbox.GetY() };
        const int mmax[3] = { type, bbox.GetRight(), bbox.GetBottom() };
 
        const auto member = m_members.insert( aItem );
 
        try
        {
            m_tree.Insert( mmin, mmax, aItem );
        }
        catch( ... )
        {
            m_members.erase( member );
            throw;
        }
    }

    bool remove( SCH_ITEM* aItem )
    {
        BOX2I bbox = aItem->GetBoundingBox();
 
        // Inflate a bit for safety, selection shadows, etc.
        bbox.Inflate( aItem->GetPenWidth() );
 
        const int type    = int( aItem->Type() );
        const int mmin[3] = { type, bbox.GetX(), bbox.GetY() };
        const int mmax[3] = { type, bbox.GetRight(), bbox.GetBottom() };
 
        // DYNAMIC_RTREE::Remove tries the provided bbox first, then falls back
        // to full-tree search if the item has moved since insertion.
        if( !m_tree.Remove( mmin, mmax, aItem ) )
            return false;
 
        const auto member = m_members.find( aItem );
        wxASSERT( member != m_members.end() );
        m_members.erase( member );
        return true;
    }

    void clear()
    {
        m_tree.RemoveAll();
        m_members.clear();
    }

    bool contains( const SCH_ITEM* aItem, bool aRobust = false ) const
    {
        if( aRobust )
            return m_members.contains( aItem );
 
        BOX2I bbox = aItem->GetBoundingBox();
 
        // Inflate a bit for safety, selection shadows, etc.
        bbox.Inflate( aItem->GetPenWidth() );
 
        const int type    = int( aItem->Type() );
        const int mmin[3] = { type, bbox.GetX(), bbox.GetY() };
        const int mmax[3] = { type, bbox.GetRight(), bbox.GetBottom() };
        bool      found   = false;
 
        auto search =
                [&found, &aItem]( const SCH_ITEM* aSearchItem )
                {
                    if( aSearchItem == aItem )
                    {
                        found = true;
                        return false;
                    }
 
                    return true;
                };
 
        m_tree.Search( mmin, mmax, search );
 
        return found;
    }

    size_t size() const
    {
        return m_members.size();
    }
 
    bool empty() const
    {
        return m_members.empty();
    }

    struct EE_TYPE
    {
        using SearchIter = typename ee_rtree::SearchIterator;
 
        EE_TYPE( const ee_rtree& aTree, KICAD_T aType )
        {
            KICAD_T type = BaseType( aType );
 
            if( type == SCH_LOCATE_ANY_T )
            {
                m_min[0] = INT_MIN; m_min[1] = INT_MIN; m_min[2] = INT_MIN;
                m_max[0] = INT_MAX; m_max[1] = INT_MAX; m_max[2] = INT_MAX;
            }
            else
            {
                m_min[0] = type; m_min[1] = INT_MIN; m_min[2] = INT_MIN;
                m_max[0] = type; m_max[1] = INT_MAX; m_max[2] = INT_MAX;
            }
 
            m_range = aTree.Overlapping( m_min, m_max );
        }
 
        EE_TYPE( const ee_rtree& aTree, KICAD_T aType, const BOX2I& aRect )
        {
            KICAD_T type = BaseType( aType );
 
            if( type == SCH_LOCATE_ANY_T )
            {
                m_min[0] = INT_MIN; m_min[1] = aRect.GetX();     m_min[2] = aRect.GetY();
                m_max[0] = INT_MAX; m_max[1] = aRect.GetRight(); m_max[2] = aRect.GetBottom();
            }
            else
            {
                m_min[0] = type; m_min[1] = aRect.GetX();     m_min[2] = aRect.GetY();
                m_max[0] = type; m_max[1] = aRect.GetRight(); m_max[2] = aRect.GetBottom();
            }
 
            m_range = aTree.Overlapping( m_min, m_max );
        }
 
        SearchIter begin() { return m_range.begin(); }
        SearchIter end() { return m_range.end(); }
 
        bool empty() { return m_range.empty(); }
 
    private:
        int m_min[3] = {};
        int m_max[3] = {};
        typename ee_rtree::SearchRange m_range{ nullptr, m_min, m_max };
    };
 
    EE_TYPE OfType( KICAD_T aType ) const
    {
        return EE_TYPE( m_tree, aType );
    }
 
    EE_TYPE Overlapping( const BOX2I& aRect ) const
    {
        return EE_TYPE( m_tree, SCH_LOCATE_ANY_T, aRect );
    }
 
    EE_TYPE Overlapping( const VECTOR2I& aPoint, int aAccuracy = 0 ) const
    {
        BOX2I rect( aPoint, VECTOR2I( 0, 0 ) );
        rect.Inflate( aAccuracy );
        return EE_TYPE( m_tree, SCH_LOCATE_ANY_T, rect );
    }
 
    EE_TYPE Overlapping( KICAD_T aType, const VECTOR2I& aPoint, int aAccuracy = 0 ) const
    {
        BOX2I rect( aPoint, VECTOR2I( 0, 0 ) );
        rect.Inflate( aAccuracy );
        return EE_TYPE( m_tree, aType, rect );
    }
 
    EE_TYPE Overlapping( KICAD_T aType, const BOX2I& aRect ) const
    {
        return EE_TYPE( m_tree, aType, aRect );
    }

    typename ee_rtree::Iterator begin() const
    {
        return m_tree.begin();
    }

    typename ee_rtree::Iterator end() const
    {
        return m_tree.end();
    }
 
 
private:
    ee_rtree m_tree;
    std::unordered_multiset<const SCH_ITEM*> m_members;
};
 
 
#endif /* EESCHEMA_SCH_RTREE_H_ */