KiCad PCB EDA Suite
sch_rtree.h
Go to the documentation of this file.
1 /*
2  * This program source code file is part of KiCad, a free EDA CAD application.
3  *
4  * Copyright (C) 2019-2021 KiCad Developers, see AUTHORS.txt for contributors.
5  * Copyright (C) 2020 CERN
6  *
7  * This program is free software; you can redistribute it and/or
8  * modify it under the terms of the GNU General Public License
9  * as published by the Free Software Foundation; either version 3
10  * of the License, or (at your option) any later version.
11  *
12  * This program is distributed in the hope that it will be useful,
13  * but WITHOUT ANY WARRANTY; without even the implied warranty of
14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15  * GNU General Public License for more details.
16  *
17  * You should have received a copy of the GNU General Public License
18  * along with this program; if not, you may find one here:
19  * http://www.gnu.org/licenses/old-licenses/gpl-3.0.html
20  * or you may search the http://www.gnu.org website for the version 3 license,
21  * or you may write to the Free Software Foundation, Inc.,
22  * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA
23  */
24 
25 #ifndef EESCHEMA_SCH_RTREE_H_
26 #define EESCHEMA_SCH_RTREE_H_
27 
28 #include <core/typeinfo.h>
29 #include <eda_rect.h>
30 #include <sch_item.h>
31 #include <set>
32 #include <vector>
33 
34 #include <geometry/rtree.h>
35 
40 class EE_RTREE
41 {
42 private:
43  using ee_rtree = RTree<SCH_ITEM*, int, 3, double>;
44 
45 public:
47  {
48  this->m_tree = new ee_rtree();
49  m_count = 0;
50  }
51 
53  {
54  delete this->m_tree;
55  }
56 
60  void insert( SCH_ITEM* aItem )
61  {
62  const EDA_RECT& bbox = aItem->GetBoundingBox();
63  const int type = int( aItem->Type() );
64  const int mmin[3] = { type, bbox.GetX(), bbox.GetY() };
65  const int mmax[3] = { type, bbox.GetRight(), bbox.GetBottom() };
66 
67  m_tree->Insert( mmin, mmax, aItem );
68  m_count++;
69  }
70 
75  bool remove( SCH_ITEM* aItem )
76  {
77  // First, attempt to remove the item using its given BBox
78  const EDA_RECT& bbox = aItem->GetBoundingBox();
79  const int type = int( aItem->Type() );
80  const int mmin[3] = { type, bbox.GetX(), bbox.GetY() };
81  const int mmax[3] = { type, bbox.GetRight(), bbox.GetBottom() };
82 
83  // If we are not successful ( true == not found ), then we expand
84  // the search to the full tree
85  if( m_tree->Remove( mmin, mmax, aItem ) )
86  {
87  // N.B. We must search the whole tree for the pointer to remove
88  // because the item may have been moved before we have the chance to
89  // delete it from the tree
90  const int mmin2[3] = { INT_MIN, INT_MIN, INT_MIN };
91  const int mmax2[3] = { INT_MAX, INT_MAX, INT_MAX };
92 
93  if( m_tree->Remove( mmin2, mmax2, aItem ) )
94  return false;
95  }
96 
97  m_count--;
98  return true;
99  }
100 
104  void clear()
105  {
106  m_tree->RemoveAll();
107  m_count = 0;
108  }
109 
118  bool contains( const SCH_ITEM* aItem, bool aRobust = false ) const
119  {
120  const EDA_RECT& bbox = aItem->GetBoundingBox();
121  const int type = int( aItem->Type() );
122  const int mmin[3] = { type, bbox.GetX(), bbox.GetY() };
123  const int mmax[3] = { type, bbox.GetRight(), bbox.GetBottom() };
124  bool found = false;
125 
126  auto search = [&found, &aItem]( const SCH_ITEM* aSearchItem ) {
127  if( aSearchItem == aItem )
128  {
129  found = true;
130  return false;
131  }
132 
133  return true;
134  };
135 
136  m_tree->Search( mmin, mmax, search );
137 
138  if( !found && aRobust )
139  {
140  // N.B. We must search the whole tree for the pointer to remove
141  // because the item may have been moved. We do not expand the item
142  // type search as this should not change.
143 
144  const int mmin2[3] = { type, INT_MIN, INT_MIN };
145  const int mmax2[3] = { type, INT_MAX, INT_MAX };
146 
147  m_tree->Search( mmin2, mmax2, search );
148  }
149 
150  return found;
151  }
152 
158  size_t size() const
159  {
160  return m_count;
161  }
162 
163  bool empty() const
164  {
165  return m_count == 0;
166  }
167 
168  using iterator = typename ee_rtree::Iterator;
169 
178  struct EE_TYPE
179  {
180  EE_TYPE( ee_rtree* aTree, KICAD_T aType ) : type_tree( aTree )
181  {
182  KICAD_T type = BaseType( aType );
183 
184  if( type == SCH_LOCATE_ANY_T )
185  m_rect = { { INT_MIN, INT_MIN, INT_MIN }, { INT_MAX, INT_MAX, INT_MAX } };
186  else
187  m_rect = { { type, INT_MIN, INT_MIN }, { type, INT_MAX, INT_MAX } };
188  };
189 
190  EE_TYPE( ee_rtree* aTree, KICAD_T aType, const EDA_RECT aRect ) : type_tree( aTree )
191  {
192  KICAD_T type = BaseType( aType );
193 
194  if( type == SCH_LOCATE_ANY_T )
195  m_rect = { { INT_MIN, aRect.GetX(), aRect.GetY() },
196  { INT_MAX, aRect.GetRight(), aRect.GetBottom() } };
197  else
198  m_rect = { { type, aRect.GetX(), aRect.GetY() },
199  { type, aRect.GetRight(), aRect.GetBottom() } };
200  };
201 
202  ee_rtree::Rect m_rect;
204 
206  {
207  return type_tree->begin( m_rect );
208  }
209 
211  {
212  return type_tree->end( m_rect );
213  }
214  };
215 
216  EE_TYPE OfType( KICAD_T aType ) const
217  {
218  return EE_TYPE( m_tree, aType );
219  }
220 
221  EE_TYPE Overlapping( const EDA_RECT& aRect ) const
222  {
223  return EE_TYPE( m_tree, SCH_LOCATE_ANY_T, aRect );
224  }
225 
226  EE_TYPE Overlapping( const wxPoint& aPoint, int aAccuracy = 0 ) const
227  {
228  EDA_RECT rect( aPoint, wxSize( 0, 0 ) );
229  rect.Inflate( aAccuracy );
230  return EE_TYPE( m_tree, SCH_LOCATE_ANY_T, rect );
231  }
232 
233  EE_TYPE Overlapping( KICAD_T aType, const wxPoint& aPoint, int aAccuracy = 0 ) const
234  {
235  EDA_RECT rect( aPoint, wxSize( 0, 0 ) );
236  rect.Inflate( aAccuracy );
237  return EE_TYPE( m_tree, aType, rect );
238  }
239 
240  EE_TYPE Overlapping( KICAD_T aType, const EDA_RECT& aRect ) const
241  {
242  return EE_TYPE( m_tree, aType, aRect );
243  }
244 
255  {
256  return m_tree->begin();
257  }
258 
264  {
265  return m_tree->end();
266  }
267 
268 
269  const iterator begin() const
270  {
271  return m_tree->begin();
272  }
273 
274  const iterator end() const
275  {
276  return m_tree->end();
277  }
278 
279 
280 private:
282  size_t m_count;
283 };
284 
285 
286 #endif /* EESCHEMA_SCH_RTREE_H_ */
bool empty() const
Definition: sch_rtree.h:163
EE_TYPE OfType(KICAD_T aType) const
Definition: sch_rtree.h:216
void insert(SCH_ITEM *aItem)
Insert an item into the tree.
Definition: sch_rtree.h:60
typename ee_rtree::Iterator iterator
Definition: sch_rtree.h:168
const iterator begin() const
Definition: sch_rtree.h:269
int GetX() const
Definition: eda_rect.h:98
constexpr KICAD_T BaseType(const KICAD_T aType)
Return the underlying type of the given type.
Definition: typeinfo.h:235
size_t size() const
Return the number of items in the tree.
Definition: sch_rtree.h:158
Implements an R-tree for fast spatial and type indexing of schematic items.
Definition: sch_rtree.h:40
EE_TYPE Overlapping(const wxPoint &aPoint, int aAccuracy=0) const
Definition: sch_rtree.h:226
KICAD_T
The set of class identification values stored in EDA_ITEM::m_structType.
Definition: typeinfo.h:77
EE_TYPE(ee_rtree *aTree, KICAD_T aType, const EDA_RECT aRect)
Definition: sch_rtree.h:190
int GetBottom() const
Definition: eda_rect.h:114
bool remove(SCH_ITEM *aItem)
Remove an item from the tree.
Definition: sch_rtree.h:75
ee_rtree * m_tree
Definition: sch_rtree.h:281
iterator end()
Returns a read/write iterator that points to one past the last element in the EE_RTREE.
Definition: sch_rtree.h:263
int GetRight() const
Definition: eda_rect.h:111
EE_TYPE(ee_rtree *aTree, KICAD_T aType)
Definition: sch_rtree.h:180
const iterator end() const
Definition: sch_rtree.h:274
RTree< SCH_ITEM *, int, 3, double > ee_rtree
Definition: sch_rtree.h:43
iterator end()
Definition: sch_rtree.h:210
~EE_RTREE()
Definition: sch_rtree.h:52
ee_rtree * type_tree
Definition: sch_rtree.h:203
EE_TYPE Overlapping(const EDA_RECT &aRect) const
Definition: sch_rtree.h:221
ee_rtree::Rect m_rect
Definition: sch_rtree.h:200
bool contains(const SCH_ITEM *aItem, bool aRobust=false) const
Determine if a given item exists in the tree.
Definition: sch_rtree.h:118
iterator begin()
Definition: sch_rtree.h:205
EE_TYPE Overlapping(KICAD_T aType, const wxPoint &aPoint, int aAccuracy=0) const
Definition: sch_rtree.h:233
iterator begin()
Returns a read/write iterator that points to the first element in the EE_RTREE N.B.
Definition: sch_rtree.h:254
size_t m_count
Definition: sch_rtree.h:282
The EE_TYPE struct provides a type-specific auto-range iterator to the RTree.
Definition: sch_rtree.h:178
Handle the component boundary box.
Definition: eda_rect.h:42
int GetY() const
Definition: eda_rect.h:99
EE_RTREE()
Definition: sch_rtree.h:46
virtual const EDA_RECT GetBoundingBox() const
Return the orthogonal bounding box of this object for display purposes.
Definition: eda_item.cpp:75
Base class for any item which can be embedded within the SCHEMATIC container class,...
Definition: sch_item.h:193
void clear()
Remove all items from the RTree.
Definition: sch_rtree.h:104
EDA_RECT & Inflate(wxCoord dx, wxCoord dy)
Inflate the rectangle horizontally by dx and vertically by dy.
Definition: eda_rect.cpp:364
KICAD_T Type() const
Returns the type of object.
Definition: eda_item.h:113
EE_TYPE Overlapping(KICAD_T aType, const EDA_RECT &aRect) const
Definition: sch_rtree.h:240