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  EDA_RECT bbox = aItem->GetBoundingBox();
63 
64  // Inflate a bit for safety, selection shadows, etc.
65  bbox.Inflate( aItem->GetPenWidth() );
66 
67  const int type = int( aItem->Type() );
68  const int mmin[3] = { type, bbox.GetX(), bbox.GetY() };
69  const int mmax[3] = { type, bbox.GetRight(), bbox.GetBottom() };
70 
71  m_tree->Insert( mmin, mmax, aItem );
72  m_count++;
73  }
74 
79  bool remove( SCH_ITEM* aItem )
80  {
81  // First, attempt to remove the item using its given BBox
82  EDA_RECT bbox = aItem->GetBoundingBox();
83 
84  // Inflate a bit for safety, selection shadows, etc.
85  bbox.Inflate( aItem->GetPenWidth() );
86 
87  const int type = int( aItem->Type() );
88  const int mmin[3] = { type, bbox.GetX(), bbox.GetY() };
89  const int mmax[3] = { type, bbox.GetRight(), bbox.GetBottom() };
90 
91  // If we are not successful ( true == not found ), then we expand
92  // the search to the full tree
93  if( m_tree->Remove( mmin, mmax, aItem ) )
94  {
95  // N.B. We must search the whole tree for the pointer to remove
96  // because the item may have been moved before we have the chance to
97  // delete it from the tree
98  const int mmin2[3] = { INT_MIN, INT_MIN, INT_MIN };
99  const int mmax2[3] = { INT_MAX, INT_MAX, INT_MAX };
100 
101  if( m_tree->Remove( mmin2, mmax2, aItem ) )
102  return false;
103  }
104 
105  m_count--;
106  return true;
107  }
108 
112  void clear()
113  {
114  m_tree->RemoveAll();
115  m_count = 0;
116  }
117 
126  bool contains( const SCH_ITEM* aItem, bool aRobust = false ) const
127  {
128  EDA_RECT bbox = aItem->GetBoundingBox();
129 
130  // Inflate a bit for safety, selection shadows, etc.
131  bbox.Inflate( aItem->GetPenWidth() );
132 
133  const int type = int( aItem->Type() );
134  const int mmin[3] = { type, bbox.GetX(), bbox.GetY() };
135  const int mmax[3] = { type, bbox.GetRight(), bbox.GetBottom() };
136  bool found = false;
137 
138  auto search =
139  [&found, &aItem]( const SCH_ITEM* aSearchItem )
140  {
141  if( aSearchItem == aItem )
142  {
143  found = true;
144  return false;
145  }
146 
147  return true;
148  };
149 
150  m_tree->Search( mmin, mmax, search );
151 
152  if( !found && aRobust )
153  {
154  // N.B. We must search the whole tree for the pointer to remove
155  // because the item may have been moved. We do not expand the item
156  // type search as this should not change.
157 
158  const int mmin2[3] = { type, INT_MIN, INT_MIN };
159  const int mmax2[3] = { type, INT_MAX, INT_MAX };
160 
161  m_tree->Search( mmin2, mmax2, search );
162  }
163 
164  return found;
165  }
166 
172  size_t size() const
173  {
174  return m_count;
175  }
176 
177  bool empty() const
178  {
179  return m_count == 0;
180  }
181 
182  using iterator = typename ee_rtree::Iterator;
183 
192  struct EE_TYPE
193  {
194  EE_TYPE( ee_rtree* aTree, KICAD_T aType ) : type_tree( aTree )
195  {
196  KICAD_T type = BaseType( aType );
197 
198  if( type == SCH_LOCATE_ANY_T )
199  m_rect = { { INT_MIN, INT_MIN, INT_MIN }, { INT_MAX, INT_MAX, INT_MAX } };
200  else
201  m_rect = { { type, INT_MIN, INT_MIN }, { type, INT_MAX, INT_MAX } };
202  };
203 
204  EE_TYPE( ee_rtree* aTree, KICAD_T aType, const EDA_RECT aRect ) : type_tree( aTree )
205  {
206  KICAD_T type = BaseType( aType );
207 
208  if( type == SCH_LOCATE_ANY_T )
209  m_rect = { { INT_MIN, aRect.GetX(), aRect.GetY() },
210  { INT_MAX, aRect.GetRight(), aRect.GetBottom() } };
211  else
212  m_rect = { { type, aRect.GetX(), aRect.GetY() },
213  { type, aRect.GetRight(), aRect.GetBottom() } };
214  };
215 
216  ee_rtree::Rect m_rect;
218 
220  {
221  return type_tree->begin( m_rect );
222  }
223 
225  {
226  return type_tree->end( m_rect );
227  }
228  };
229 
230  EE_TYPE OfType( KICAD_T aType ) const
231  {
232  return EE_TYPE( m_tree, aType );
233  }
234 
235  EE_TYPE Overlapping( const EDA_RECT& aRect ) const
236  {
237  return EE_TYPE( m_tree, SCH_LOCATE_ANY_T, aRect );
238  }
239 
240  EE_TYPE Overlapping( const wxPoint& aPoint, int aAccuracy = 0 ) const
241  {
242  EDA_RECT rect( aPoint, wxSize( 0, 0 ) );
243  rect.Inflate( aAccuracy );
244  return EE_TYPE( m_tree, SCH_LOCATE_ANY_T, rect );
245  }
246 
247  EE_TYPE Overlapping( KICAD_T aType, const wxPoint& aPoint, int aAccuracy = 0 ) const
248  {
249  EDA_RECT rect( aPoint, wxSize( 0, 0 ) );
250  rect.Inflate( aAccuracy );
251  return EE_TYPE( m_tree, aType, rect );
252  }
253 
254  EE_TYPE Overlapping( KICAD_T aType, const EDA_RECT& aRect ) const
255  {
256  return EE_TYPE( m_tree, aType, aRect );
257  }
258 
269  {
270  return m_tree->begin();
271  }
272 
278  {
279  return m_tree->end();
280  }
281 
282 
283  const iterator begin() const
284  {
285  return m_tree->begin();
286  }
287 
288  const iterator end() const
289  {
290  return m_tree->end();
291  }
292 
293 
294 private:
296  size_t m_count;
297 };
298 
299 
300 #endif /* EESCHEMA_SCH_RTREE_H_ */
bool empty() const
Definition: sch_rtree.h:177
EE_TYPE OfType(KICAD_T aType) const
Definition: sch_rtree.h:230
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:182
const iterator begin() const
Definition: sch_rtree.h:283
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:231
size_t size() const
Return the number of items in the tree.
Definition: sch_rtree.h:172
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:240
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:204
int GetBottom() const
Definition: eda_rect.h:114
bool remove(SCH_ITEM *aItem)
Remove an item from the tree.
Definition: sch_rtree.h:79
ee_rtree * m_tree
Definition: sch_rtree.h:295
iterator end()
Returns a read/write iterator that points to one past the last element in the EE_RTREE.
Definition: sch_rtree.h:277
int GetRight() const
Definition: eda_rect.h:111
EE_TYPE(ee_rtree *aTree, KICAD_T aType)
Definition: sch_rtree.h:194
const iterator end() const
Definition: sch_rtree.h:288
RTree< SCH_ITEM *, int, 3, double > ee_rtree
Definition: sch_rtree.h:43
iterator end()
Definition: sch_rtree.h:224
~EE_RTREE()
Definition: sch_rtree.h:52
ee_rtree * type_tree
Definition: sch_rtree.h:217
virtual int GetPenWidth() const
Definition: sch_item.h:276
EE_TYPE Overlapping(const EDA_RECT &aRect) const
Definition: sch_rtree.h:235
ee_rtree::Rect m_rect
Definition: sch_rtree.h:214
bool contains(const SCH_ITEM *aItem, bool aRobust=false) const
Determine if a given item exists in the tree.
Definition: sch_rtree.h:126
iterator begin()
Definition: sch_rtree.h:219
EE_TYPE Overlapping(KICAD_T aType, const wxPoint &aPoint, int aAccuracy=0) const
Definition: sch_rtree.h:247
iterator begin()
Returns a read/write iterator that points to the first element in the EE_RTREE N.B.
Definition: sch_rtree.h:268
size_t m_count
Definition: sch_rtree.h:296
The EE_TYPE struct provides a type-specific auto-range iterator to the RTree.
Definition: sch_rtree.h:192
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:182
void clear()
Remove all items from the RTree.
Definition: sch_rtree.h:112
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:112
EE_TYPE Overlapping(KICAD_T aType, const EDA_RECT &aRect) const
Definition: sch_rtree.h:254