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 CHANGELOG.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 <sch_junction.h>
31 #include <sch_no_connect.h>
33 
34 // Code under test
35 #include <sch_rtree.h>
36 
37 #include "uuid_test_utils.h"
38 
40 
42 {
43 public:
45  {
46  }
47 
49 };
50 
51 
55 BOOST_FIXTURE_TEST_SUITE( SchRtree, TEST_SCH_RTREE_FIXTURE )
56 
57 
58 
62 {
63  BOOST_CHECK_EQUAL( m_tree.empty(), true );
64 
65  int count = 0;
66  for( auto item : m_tree )
67  {
68  static_cast<void>( item );
69  count++;
70  }
71 
72  BOOST_CHECK_EQUAL( count, 0 );
73 
74  for( int type = 0; type <= MAX_STRUCT_TYPE_ID; type++ )
75  {
76  count = 0;
77  for( auto item : m_tree.OfType( KICAD_T( type ) ) )
78  {
79  static_cast<void>( item );
80  count++;
81  }
82 
83  BOOST_CHECK_EQUAL( count, 0 );
84  }
85 
86  EDA_RECT bbox;
87 
88  for( int type = 0; type <= MAX_STRUCT_TYPE_ID; type++ )
89  {
90  count = 0;
91  for( auto item : m_tree.Overlapping( SCH_JUNCTION_T, bbox ) )
92  {
93  static_cast<void>( item );
94  count++;
95  }
96 
97  BOOST_CHECK_EQUAL( count, 0 );
98  }
99 }
100 
102 {
103  for( int i = 0; i < 100; i++ )
104  {
105  SCH_JUNCTION* junction =
106  new SCH_JUNCTION( wxPoint( Mils2iu( 100 ) * i, Mils2iu( 100 ) * i ) );
107  m_tree.insert( junction );
108  }
109 
110  int count = 0;
111 
112  for( auto item : m_tree.OfType( SCH_JUNCTION_T ) )
113  {
114  static_cast<void>( item );
115  count++;
116  }
117 
118  BOOST_CHECK_EQUAL( count, 100 );
119 
120  count = 0;
121  for( auto item : m_tree.OfType( SCH_NO_CONNECT_T ) )
122  {
123  static_cast<void>( item );
124  count++;
125  }
126 
127  BOOST_CHECK_EQUAL( count, 0 );
128 
129  EDA_RECT small_bbox( wxPoint( -1, -1 ), wxSize( Mils2iu( 2 ), Mils2iu( 2 ) ) );
130  EDA_RECT med_bbox( wxPoint( 0, 0 ), wxSize( Mils2iu( 100 ), Mils2iu( 100 ) ) );
131  EDA_RECT big_bbox( wxPoint( 0, 0 ), wxSize( Mils2iu( 5000 ), Mils2iu( 5000 ) ) );
132 
133  count = 0;
134  for( auto item : m_tree.Overlapping( small_bbox ) )
135  {
136  BOOST_CHECK( small_bbox.Intersects( item->GetBoundingBox() ) );
137  count++;
138  }
139 
140  BOOST_CHECK_EQUAL( count, 1 );
141 
142  count = 0;
143  for( auto item : m_tree.Overlapping( SCH_JUNCTION_T, small_bbox ) )
144  {
145  BOOST_CHECK( small_bbox.Intersects( item->GetBoundingBox() ) );
146  count++;
147  }
148 
149  BOOST_CHECK_EQUAL( count, 1 );
150 
151  count = 0;
152  for( auto item : m_tree.Overlapping( SCH_NO_CONNECT_T, small_bbox ) )
153  {
154  BOOST_CHECK( small_bbox.Intersects( item->GetBoundingBox() ) );
155  count++;
156  }
157 
158  BOOST_CHECK_EQUAL( count, 0 );
159 
160  count = 0;
161  for( auto item : m_tree.Overlapping( med_bbox ) )
162  {
163  BOOST_CHECK( med_bbox.Intersects( item->GetBoundingBox() ) );
164  count++;
165  }
166 
167  BOOST_CHECK_EQUAL( count, 2 );
168 
169  count = 0;
170  for( auto item : m_tree.Overlapping( big_bbox ) )
171  {
172  BOOST_CHECK( big_bbox.Intersects( item->GetBoundingBox() ) );
173  count++;
174  }
175 
176  BOOST_CHECK_EQUAL( count, 51 );
177 
178  for( SCH_ITEM* item : m_tree )
179  delete item;
180 }
181 
182 BOOST_AUTO_TEST_CASE( MixedElements )
183 {
184  for( int i = 0; i < 100; i++ )
185  {
186  int x_sign = ( i % 2 == 0 ) ? -1 : 1;
187  int y_sign = ( i % 3 == 0 ) ? -1 : 1;
188 
189  SCH_JUNCTION* junction = new SCH_JUNCTION(
190  wxPoint( Mils2iu( 100 ) * i * x_sign, Mils2iu( 100 ) * i * y_sign ) );
191  m_tree.insert( junction );
192 
193  SCH_NO_CONNECT* nc = new SCH_NO_CONNECT(
194  wxPoint( Mils2iu( 150 ) * i * y_sign, Mils2iu( 150 ) * i * x_sign ) );
195  m_tree.insert( nc );
196  }
197 
198  int count = 0;
199 
200  for( auto item : m_tree.OfType( SCH_JUNCTION_T ) )
201  {
202  static_cast<void>( item );
203  count++;
204  }
205 
206  BOOST_CHECK_EQUAL( count, 100 );
207 
208  count = 0;
209  for( auto item : m_tree.OfType( SCH_NO_CONNECT_T ) )
210  {
211  static_cast<void>( item );
212  count++;
213  }
214 
215  BOOST_CHECK_EQUAL( count, 100 );
216 
217  EDA_RECT small_bbox( wxPoint( -1, -1 ), wxSize( Mils2iu( 2 ), Mils2iu( 2 ) ) );
218 
219  count = 0;
220  for( auto item : m_tree.Overlapping( small_bbox ) )
221  {
222  BOOST_CHECK( small_bbox.Intersects( item->GetBoundingBox() ) );
223  count++;
224  }
225 
226  BOOST_CHECK_EQUAL( count, 2 );
227 
228  count = 0;
229  for( auto item : m_tree.Overlapping( SCH_JUNCTION_T, small_bbox ) )
230  {
231  BOOST_CHECK( small_bbox.Intersects( item->GetBoundingBox() ) );
232  count++;
233  }
234 
235  BOOST_CHECK_EQUAL( count, 1 );
236 
237  count = 0;
238  for( auto item : m_tree.Overlapping( SCH_NO_CONNECT_T, small_bbox ) )
239  {
240  BOOST_CHECK( small_bbox.Intersects( item->GetBoundingBox() ) );
241  count++;
242  }
243 
244  BOOST_CHECK_EQUAL( count, 1 );
245 
246  for( SCH_ITEM* item : m_tree )
247  delete item;
248 }
249 
250 // This tests the case where the tree has no branches but we want to iterator over a subset
251 // where the first case may or may not match
252 BOOST_AUTO_TEST_CASE( SingleElementTree )
253 {
254  SCH_JUNCTION* junction = new SCH_JUNCTION( wxPoint( Mils2iu( 100 ), Mils2iu( 100 ) ) );
255  m_tree.insert( junction );
256 
257  SCH_NO_CONNECT* nc = new SCH_NO_CONNECT( wxPoint( Mils2iu( 150 ), Mils2iu( 150 ) ) );
258  m_tree.insert( nc );
259 
260  int count = 0;
261 
262  for( auto item : m_tree.OfType( SCH_JUNCTION_T ) )
263  {
264  static_cast<void>( item );
265  count++;
266  }
267 
268  BOOST_CHECK_EQUAL( count, 1 );
269 
270  count = 0;
271  for( auto item : m_tree.OfType( SCH_NO_CONNECT_T ) )
272  {
273  static_cast<void>( item );
274  count++;
275  }
276 
277  BOOST_CHECK_EQUAL( count, 1 );
278 
279  for( SCH_ITEM* item : m_tree )
280  delete item;
281 }
282 
283 BOOST_AUTO_TEST_SUITE_END()
BOOST_AUTO_TEST_CASE(Default)
Declare the test suite.
EE_RTREE - Implements an R-tree for fast spatial and type indexing of schematic items.
Definition: sch_rtree.h:41
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
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:196
Test utilities for timestamps.