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 
179 BOOST_AUTO_TEST_CASE( MixedElements )
180 {
181  for( int i = 0; i < 100; i++ )
182  {
183  int x_sign = ( i % 2 == 0 ) ? -1 : 1;
184  int y_sign = ( i % 3 == 0 ) ? -1 : 1;
185 
186  SCH_JUNCTION* junction = new SCH_JUNCTION(
187  wxPoint( Mils2iu( 100 ) * i * x_sign, Mils2iu( 100 ) * i * y_sign ) );
188  m_tree.insert( junction );
189 
190  SCH_NO_CONNECT* nc = new SCH_NO_CONNECT(
191  wxPoint( Mils2iu( 150 ) * i * y_sign, Mils2iu( 150 ) * i * x_sign ) );
192  m_tree.insert( nc );
193  }
194 
195  int count = 0;
196 
197  for( auto item : m_tree.OfType( SCH_JUNCTION_T ) )
198  {
199  static_cast<void>( item );
200  count++;
201  }
202 
203  BOOST_CHECK_EQUAL( count, 100 );
204 
205  count = 0;
206  for( auto item : m_tree.OfType( SCH_NO_CONNECT_T ) )
207  {
208  static_cast<void>( item );
209  count++;
210  }
211 
212  BOOST_CHECK_EQUAL( count, 100 );
213 
214  EDA_RECT small_bbox( wxPoint( -1, -1 ), wxSize( Mils2iu( 2 ), Mils2iu( 2 ) ) );
215 
216  count = 0;
217  for( auto item : m_tree.Overlapping( small_bbox ) )
218  {
219  BOOST_CHECK( small_bbox.Intersects( item->GetBoundingBox() ) );
220  count++;
221  }
222 
223  BOOST_CHECK_EQUAL( count, 2 );
224 
225  count = 0;
226  for( auto item : m_tree.Overlapping( SCH_JUNCTION_T, small_bbox ) )
227  {
228  BOOST_CHECK( small_bbox.Intersects( item->GetBoundingBox() ) );
229  count++;
230  }
231 
232  BOOST_CHECK_EQUAL( count, 1 );
233 
234  count = 0;
235  for( auto item : m_tree.Overlapping( SCH_NO_CONNECT_T, small_bbox ) )
236  {
237  BOOST_CHECK( small_bbox.Intersects( item->GetBoundingBox() ) );
238  count++;
239  }
240 
241  BOOST_CHECK_EQUAL( count, 1 );
242 }
243 
244 // This tests the case where the tree has no branches but we want to iterator over a subset
245 // where the first case may or may not match
246 BOOST_AUTO_TEST_CASE( SingleElementTree )
247 {
248  SCH_JUNCTION* junction = new SCH_JUNCTION( wxPoint( Mils2iu( 100 ), Mils2iu( 100 ) ) );
249  m_tree.insert( junction );
250 
251  SCH_NO_CONNECT* nc = new SCH_NO_CONNECT( wxPoint( Mils2iu( 150 ), Mils2iu( 150 ) ) );
252  m_tree.insert( nc );
253 
254  int count = 0;
255 
256  for( auto item : m_tree.OfType( SCH_JUNCTION_T ) )
257  {
258  static_cast<void>( item );
259  count++;
260  }
261 
262  BOOST_CHECK_EQUAL( count, 1 );
263 
264  count = 0;
265  for( auto item : m_tree.OfType( SCH_NO_CONNECT_T ) )
266  {
267  static_cast<void>( item );
268  count++;
269  }
270 
271  BOOST_CHECK_EQUAL( count, 1 );
272 }
273 
274 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
Enum KICAD_T is the set of class identification values, stored in EDA_ITEM::m_StructType.
Definition: typeinfo.h:78
EDA_RECT handles the component boundary box.
Definition: eda_rect.h:44
bool Intersects(const EDA_RECT &aRect) const
Function Intersects tests for a common area between rectangles.
Test utilities for timestamps.