KiCad PCB EDA Suite
test_sch_rtree.cpp
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) 2020 KiCad Developers, see AUTHORS.TXT for contributors.
5  *
6  * This program is free software; you can redistribute it and/or
7  * modify it under the terms of the GNU General Public License
8  * as published by the Free Software Foundation; either version 3
9  * of the License, or (at your option) any later version.
10  *
11  * This program is distributed in the hope that it will be useful,
12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14  * GNU General Public License for more details.
15  *
16  * You should have received a copy of the GNU General Public License
17  * along with this program; if not, you may find one here:
18  * http://www.gnu.org/licenses/old-licenses/gpl-3.0.html
19  * or you may search the http://www.gnu.org website for the version 3 license,
20  * or you may write to the Free Software Foundation, Inc.,
21  * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA
22  */
23 
29 #include <convert_to_biu.h>
30 #include <ignore.h>
31 #include <sch_junction.h>
32 #include <sch_no_connect.h>
34 
35 // Code under test
36 #include <sch_rtree.h>
37 
38 #include "uuid_test_utils.h"
39 
41 
43 {
44 public:
46  {
47  }
48 
50 };
51 
52 
56 BOOST_FIXTURE_TEST_SUITE( SchRtree, TEST_SCH_RTREE_FIXTURE )
57 
58 
59 
63 {
64  BOOST_CHECK_EQUAL( m_tree.empty(), true );
65 
66  int count = 0;
67  for( auto item : m_tree )
68  {
69  ignore_unused( item );
70  count++;
71  }
72 
73  BOOST_CHECK_EQUAL( count, 0 );
74 
75  for( int type = 0; type <= MAX_STRUCT_TYPE_ID; type++ )
76  {
77  count = 0;
78  for( auto item : m_tree.OfType( KICAD_T( type ) ) )
79  {
80  ignore_unused( item );
81  count++;
82  }
83 
84  BOOST_CHECK_EQUAL( count, 0 );
85  }
86 
87  EDA_RECT bbox;
88 
89  for( int type = 0; type <= MAX_STRUCT_TYPE_ID; type++ )
90  {
91  count = 0;
92  for( auto item : m_tree.Overlapping( SCH_JUNCTION_T, bbox ) )
93  {
94  ignore_unused( item );
95  count++;
96  }
97 
98  BOOST_CHECK_EQUAL( count, 0 );
99  }
100 }
101 
103 {
104  for( int i = 0; i < 100; i++ )
105  {
106  SCH_JUNCTION* junction =
107  new SCH_JUNCTION( wxPoint( Mils2iu( 100 ) * i, Mils2iu( 100 ) * i ) );
108  m_tree.insert( junction );
109  }
110 
111  int count = 0;
112 
113  for( auto item : m_tree.OfType( SCH_JUNCTION_T ) )
114  {
115  ignore_unused( item );
116  count++;
117  }
118 
119  BOOST_CHECK_EQUAL( count, 100 );
120 
121  count = 0;
122  for( auto item : m_tree.OfType( SCH_NO_CONNECT_T ) )
123  {
124  ignore_unused( item );
125  count++;
126  }
127 
128  BOOST_CHECK_EQUAL( count, 0 );
129 
130  EDA_RECT small_bbox( wxPoint( -1, -1 ), wxSize( Mils2iu( 2 ), Mils2iu( 2 ) ) );
131  EDA_RECT med_bbox( wxPoint( 0, 0 ), wxSize( Mils2iu( 100 ), Mils2iu( 100 ) ) );
132  EDA_RECT big_bbox( wxPoint( 0, 0 ), wxSize( Mils2iu( 5000 ), Mils2iu( 5000 ) ) );
133 
134  count = 0;
135  for( auto item : m_tree.Overlapping( small_bbox ) )
136  {
137  BOOST_CHECK( small_bbox.Intersects( item->GetBoundingBox() ) );
138  count++;
139  }
140 
141  BOOST_CHECK_EQUAL( count, 1 );
142 
143  count = 0;
144  for( auto item : m_tree.Overlapping( SCH_JUNCTION_T, small_bbox ) )
145  {
146  BOOST_CHECK( small_bbox.Intersects( item->GetBoundingBox() ) );
147  count++;
148  }
149 
150  BOOST_CHECK_EQUAL( count, 1 );
151 
152  count = 0;
153  for( auto item : m_tree.Overlapping( SCH_NO_CONNECT_T, small_bbox ) )
154  {
155  BOOST_CHECK( small_bbox.Intersects( item->GetBoundingBox() ) );
156  count++;
157  }
158 
159  BOOST_CHECK_EQUAL( count, 0 );
160 
161  count = 0;
162  for( auto item : m_tree.Overlapping( med_bbox ) )
163  {
164  BOOST_CHECK( med_bbox.Intersects( item->GetBoundingBox() ) );
165  count++;
166  }
167 
168  BOOST_CHECK_EQUAL( count, 2 );
169 
170  count = 0;
171  for( auto item : m_tree.Overlapping( big_bbox ) )
172  {
173  BOOST_CHECK( big_bbox.Intersects( item->GetBoundingBox() ) );
174  count++;
175  }
176 
177  BOOST_CHECK_EQUAL( count, 51 );
178 
179  for( SCH_ITEM* item : m_tree )
180  delete item;
181 }
182 
183 BOOST_AUTO_TEST_CASE( MixedElements )
184 {
185  for( int i = 0; i < 100; i++ )
186  {
187  int x_sign = ( i % 2 == 0 ) ? -1 : 1;
188  int y_sign = ( i % 3 == 0 ) ? -1 : 1;
189 
190  SCH_JUNCTION* junction = new SCH_JUNCTION(
191  wxPoint( Mils2iu( 100 ) * i * x_sign, Mils2iu( 100 ) * i * y_sign ) );
192  m_tree.insert( junction );
193 
194  SCH_NO_CONNECT* nc = new SCH_NO_CONNECT(
195  wxPoint( Mils2iu( 150 ) * i * y_sign, Mils2iu( 150 ) * i * x_sign ) );
196  m_tree.insert( nc );
197  }
198 
199  int count = 0;
200 
201  for( auto item : m_tree.OfType( SCH_JUNCTION_T ) )
202  {
203  ignore_unused( item );
204  count++;
205  }
206 
207  BOOST_CHECK_EQUAL( count, 100 );
208 
209  count = 0;
210  for( auto item : m_tree.OfType( SCH_NO_CONNECT_T ) )
211  {
212  ignore_unused( item );
213  count++;
214  }
215 
216  BOOST_CHECK_EQUAL( count, 100 );
217 
218  EDA_RECT small_bbox( wxPoint( -1, -1 ), wxSize( Mils2iu( 2 ), Mils2iu( 2 ) ) );
219 
220  count = 0;
221  for( auto item : m_tree.Overlapping( small_bbox ) )
222  {
223  BOOST_CHECK( small_bbox.Intersects( item->GetBoundingBox() ) );
224  count++;
225  }
226 
227  BOOST_CHECK_EQUAL( count, 2 );
228 
229  count = 0;
230  for( auto item : m_tree.Overlapping( SCH_JUNCTION_T, small_bbox ) )
231  {
232  BOOST_CHECK( small_bbox.Intersects( item->GetBoundingBox() ) );
233  count++;
234  }
235 
236  BOOST_CHECK_EQUAL( count, 1 );
237 
238  count = 0;
239  for( auto item : m_tree.Overlapping( SCH_NO_CONNECT_T, small_bbox ) )
240  {
241  BOOST_CHECK( small_bbox.Intersects( item->GetBoundingBox() ) );
242  count++;
243  }
244 
245  BOOST_CHECK_EQUAL( count, 1 );
246 
247  for( SCH_ITEM* item : m_tree )
248  delete item;
249 }
250 
251 // This tests the case where the tree has no branches but we want to iterator over a subset
252 // where the first case may or may not match
253 BOOST_AUTO_TEST_CASE( SingleElementTree )
254 {
255  SCH_JUNCTION* junction = new SCH_JUNCTION( wxPoint( Mils2iu( 100 ), Mils2iu( 100 ) ) );
256  m_tree.insert( junction );
257 
258  SCH_NO_CONNECT* nc = new SCH_NO_CONNECT( wxPoint( Mils2iu( 150 ), Mils2iu( 150 ) ) );
259  m_tree.insert( nc );
260 
261  int count = 0;
262 
263  for( auto item : m_tree.OfType( SCH_JUNCTION_T ) )
264  {
265  ignore_unused( item );
266  count++;
267  }
268 
269  BOOST_CHECK_EQUAL( count, 1 );
270 
271  count = 0;
272  for( auto item : m_tree.OfType( SCH_NO_CONNECT_T ) )
273  {
274  ignore_unused( item );
275  count++;
276  }
277 
278  BOOST_CHECK_EQUAL( count, 1 );
279 
280  for( SCH_ITEM* item : m_tree )
281  delete item;
282 }
283 
284 BOOST_AUTO_TEST_SUITE_END()
BOOST_AUTO_TEST_CASE(Default)
Declare the test suite.
Implements an R-tree for fast spatial and type indexing of schematic items.
Definition: sch_rtree.h:40
KICAD_T
The set of class identification values stored in EDA_ITEM::m_structType.
Definition: typeinfo.h:77
BOOST_CHECK(v2.Cross(v1)==1)
Handle the component boundary box.
Definition: eda_rect.h:42
void ignore_unused(const T &)
Definition: ignore.h:24
bool Intersects(const EDA_RECT &aRect) const
Test for a common area between rectangles.
Definition: eda_rect.cpp:150
Base class for any item which can be embedded within the SCHEMATIC container class,...
Definition: sch_item.h:182
Test utilities for timestamps.