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 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 
41 class EE_RTREE
42 {
43 private:
44  using ee_rtree = RTree<SCH_ITEM*, int, 3, double>;
45 
46 public:
48  {
49  this->m_tree = new ee_rtree();
50  m_count = 0;
51  }
52 
54  {
55  delete this->m_tree;
56  }
57 
62  void insert( SCH_ITEM* aItem )
63  {
64  const EDA_RECT& bbox = aItem->GetBoundingBox();
65  const int type = int( aItem->Type() );
66  const int mmin[3] = { type, bbox.GetX(), bbox.GetY() };
67  const int mmax[3] = { type, bbox.GetRight(), bbox.GetBottom() };
68 
69  m_tree->Insert( mmin, mmax, aItem );
70  m_count++;
71  }
72 
78  bool remove( SCH_ITEM* aItem )
79  {
80  // First, attempt to remove the item using its given BBox
81  const EDA_RECT& bbox = aItem->GetBoundingBox();
82  const int type = int( aItem->Type() );
83  const int mmin[3] = { type, bbox.GetX(), bbox.GetY() };
84  const int mmax[3] = { type, bbox.GetRight(), bbox.GetBottom() };
85 
86  // If we are not successful ( true == not found ), then we expand
87  // the search to the full tree
88  if( m_tree->Remove( mmin, mmax, aItem ) )
89  {
90  // N.B. We must search the whole tree for the pointer to remove
91  // because the item may have been moved before we have the chance to
92  // delete it from the tree
93  const int mmin2[3] = { INT_MIN, INT_MIN, INT_MIN };
94  const int mmax2[3] = { INT_MAX, INT_MAX, INT_MAX };
95 
96  if( m_tree->Remove( mmin2, mmax2, aItem ) )
97  return false;
98  }
99 
100  m_count--;
101  return true;
102  }
103 
108  void clear()
109  {
110  m_tree->RemoveAll();
111  m_count = 0;
112  }
113 
122  bool contains( SCH_ITEM* aItem, bool aRobust = false )
123  {
124  const EDA_RECT& bbox = aItem->GetBoundingBox();
125  const int type = int( aItem->Type() );
126  const int mmin[3] = { type, bbox.GetX(), bbox.GetY() };
127  const int mmax[3] = { type, bbox.GetRight(), bbox.GetBottom() };
128  bool found = false;
129 
130  auto search = [&found, &aItem]( const SCH_ITEM* aSearchItem ) {
131  if( aSearchItem == aItem )
132  {
133  found = true;
134  return false;
135  }
136 
137  return true;
138  };
139 
140  m_tree->Search( mmin, mmax, search );
141 
142  if( !found && aRobust )
143  {
144  // N.B. We must search the whole tree for the pointer to remove
145  // because the item may have been moved. We do not expand the item
146  // type search as this should not change.
147 
148  const int mmin2[3] = { type, INT_MIN, INT_MIN };
149  const int mmax2[3] = { type, INT_MAX, INT_MAX };
150 
151  m_tree->Search( mmin2, mmax2, search );
152  }
153 
154  return found;
155  }
156 
161  size_t size()
162  {
163  return m_count;
164  }
165 
166  bool empty()
167  {
168  return m_count == 0;
169  }
170 
171  using iterator = typename ee_rtree::Iterator;
172 
181  struct EE_TYPE
182  {
183  EE_TYPE( ee_rtree* aTree, KICAD_T aType ) : type_tree( aTree )
184  {
185  KICAD_T type = BaseType( aType );
186 
187  if( type == SCH_LOCATE_ANY_T )
188  m_rect = { { INT_MIN, INT_MIN, INT_MIN }, { INT_MAX, INT_MAX, INT_MAX } };
189  else
190  m_rect = { { type, INT_MIN, INT_MIN }, { type, INT_MAX, INT_MAX } };
191  };
192 
193  EE_TYPE( ee_rtree* aTree, KICAD_T aType, const EDA_RECT aRect ) : type_tree( aTree )
194  {
195  KICAD_T type = BaseType( aType );
196 
197  if( type == SCH_LOCATE_ANY_T )
198  m_rect = { { INT_MIN, aRect.GetX(), aRect.GetY() },
199  { INT_MAX, aRect.GetRight(), aRect.GetBottom() } };
200  else
201  m_rect = { { type, aRect.GetX(), aRect.GetY() },
202  { type, aRect.GetRight(), aRect.GetBottom() } };
203  };
204 
205  ee_rtree::Rect m_rect;
207 
209  {
210  return type_tree->begin( m_rect );
211  }
212 
214  {
215  return type_tree->end( m_rect );
216  }
217  };
218 
220  {
221  return EE_TYPE( m_tree, aType );
222  }
223 
224  EE_TYPE Overlapping( const EDA_RECT& aRect )
225  {
226  return EE_TYPE( m_tree, SCH_LOCATE_ANY_T, aRect );
227  }
228 
229  EE_TYPE Overlapping( const wxPoint& aPoint, int aAccuracy = 0 )
230  {
231  EDA_RECT rect( aPoint, wxSize( 0, 0 ) );
232  rect.Inflate( aAccuracy );
233  return EE_TYPE( m_tree, SCH_LOCATE_ANY_T, rect );
234  }
235 
236  EE_TYPE Overlapping( KICAD_T aType, const wxPoint& aPoint, int aAccuracy = 0 )
237  {
238  EDA_RECT rect( aPoint, wxSize( 0, 0 ) );
239  rect.Inflate( aAccuracy );
240  return EE_TYPE( m_tree, aType, rect );
241  }
242 
243  EE_TYPE Overlapping( KICAD_T aType, const EDA_RECT& aRect )
244  {
245  return EE_TYPE( m_tree, aType, aRect );
246  }
247 
249  {
250  return m_tree->begin();
251  }
252 
254  {
255  return m_tree->end();
256  }
257 
258 
259  const iterator begin() const
260  {
261  return m_tree->begin();
262  }
263 
264  const iterator end() const
265  {
266  return m_tree->end();
267  }
268 
269 
270 private:
272  size_t m_count;
273 };
274 
275 
276 #endif /* EESCHEMA_SCH_RTREE_H_ */
void insert(SCH_ITEM *aItem)
Function Insert() Inserts an item into the tree.
Definition: sch_rtree.h:62
typename ee_rtree::Iterator iterator
Definition: sch_rtree.h:171
const iterator begin() const
Definition: sch_rtree.h:259
bool empty()
Definition: sch_rtree.h:166
int GetX() const
Definition: eda_rect.h:111
constexpr KICAD_T BaseType(const KICAD_T aType)
Returns the underlying type of the given type.
Definition: typeinfo.h:228
EE_TYPE Overlapping(const wxPoint &aPoint, int aAccuracy=0)
Definition: sch_rtree.h:229
EE_TYPE OfType(KICAD_T aType)
Definition: sch_rtree.h:219
EE_TYPE Overlapping(const EDA_RECT &aRect)
Definition: sch_rtree.h:224
EE_TYPE Overlapping(KICAD_T aType, const wxPoint &aPoint, int aAccuracy=0)
Definition: sch_rtree.h:236
EE_TYPE Overlapping(KICAD_T aType, const EDA_RECT &aRect)
Definition: sch_rtree.h:243
EE_RTREE - Implements an R-tree for fast spatial and type indexing of schematic items.
Definition: sch_rtree.h:41
KICAD_T
Enum KICAD_T is the set of class identification values, stored in EDA_ITEM::m_StructType.
Definition: typeinfo.h:78
EE_TYPE(ee_rtree *aTree, KICAD_T aType, const EDA_RECT aRect)
Definition: sch_rtree.h:193
int GetBottom() const
Definition: eda_rect.h:124
bool contains(SCH_ITEM *aItem, bool aRobust=false)
Determine if a given item exists in the tree.
Definition: sch_rtree.h:122
bool remove(SCH_ITEM *aItem)
Function Remove() Removes an item from the tree.
Definition: sch_rtree.h:78
ee_rtree * m_tree
Definition: sch_rtree.h:271
iterator end()
Definition: sch_rtree.h:253
int GetRight() const
Definition: eda_rect.h:121
EE_TYPE(ee_rtree *aTree, KICAD_T aType)
Definition: sch_rtree.h:183
const iterator end() const
Definition: sch_rtree.h:264
size_t size()
Returns the number of items in the tree.
Definition: sch_rtree.h:161
RTree< SCH_ITEM *, int, 3, double > ee_rtree
Definition: sch_rtree.h:44
iterator end()
Definition: sch_rtree.h:213
~EE_RTREE()
Definition: sch_rtree.h:53
ee_rtree * type_tree
Definition: sch_rtree.h:206
ee_rtree::Rect m_rect
Definition: sch_rtree.h:203
iterator begin()
Definition: sch_rtree.h:208
iterator begin()
Definition: sch_rtree.h:248
size_t m_count
Definition: sch_rtree.h:272
The EE_TYPE struct provides a type-specific auto-range iterator to the RTree.
Definition: sch_rtree.h:181
EDA_RECT handles the component boundary box.
Definition: eda_rect.h:44
int GetY() const
Definition: eda_rect.h:112
EE_RTREE()
Definition: sch_rtree.h:47
virtual const EDA_RECT GetBoundingBox() const
Function GetBoundingBox returns the orthogonal, bounding box of this object for display purposes.
Definition: base_struct.cpp:97
Base class for any item which can be embedded within the SCHEMATIC container class,...
Definition: sch_item.h:187
void clear()
Function RemoveAll() Removes all items from the RTree.
Definition: sch_rtree.h:108
EDA_RECT & Inflate(wxCoord dx, wxCoord dy)
Function Inflate inflates the rectangle horizontally by dx and vertically by dy.
KICAD_T Type() const
Function Type()
Definition: base_struct.h:193