KiCad PCB EDA Suite
multivector.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 2017 CERN
5 * Copyright (C) 2020-2021 KiCad Developers, see AUTHORS.txt for contributors.
6 *
7 * @author Maciej Suminski <[email protected]>
8 * @author Bernhard Stegmaier <[email protected]>
9 *
10 * This program is free software; you can redistribute it and/or
11 * modify it under the terms of the GNU General Public License
12 * as published by the Free Software Foundation; either version 2
13 * of the License, or (at your option) any later version.
14 *
15 * This program is distributed in the hope that it will be useful,
16 * but WITHOUT ANY WARRANTY; without even the implied warranty of
17 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
18 * GNU General Public License for more details.
19 *
20 * You should have received a copy of the GNU General Public License
21 * along with this program; if not, you may find one here:
22 * http://www.gnu.org/licenses/old-licenses/gpl-2.0.html
23 * or you may search the http://www.gnu.org website for the version 2 license,
24 * or you may write to the Free Software Foundation, Inc.,
25 * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA
26 */
27
28#ifndef MULTIVECTOR_H
29#define MULTIVECTOR_H
30
31#include <boost/ptr_container/ptr_vector.hpp>
32#include <stdexcept>
33
44template<typename T, int FIRST_TYPE_VAL, int LAST_TYPE_VAL>
46{
47public:
52 static constexpr int UNDEFINED_TYPE = 0;
53 static_assert( FIRST_TYPE_VAL > UNDEFINED_TYPE,
54 "FIRST_TYPE_VAL must be greater than UNDEFINED_TYPE" );
55 static_assert( FIRST_TYPE_VAL < LAST_TYPE_VAL,
56 "FIRST_TYPE_VAL must be greater than LAST_TYPE_VAL" );
57
64 typedef boost::ptr_vector<T> ITEM_PTR_VECTOR;
65
69 template<typename ITEM_TYPE, typename ITEM_CONTAINER, typename ITEM_CONTAINER_IT>
71 {
72 public:
73 ITEM_TYPE& operator*()
74 {
75 return *m_it;
76 }
77
78 ITEM_TYPE* operator->()
79 {
80 return &( *m_it );
81 }
82
84 {
85 if( m_it != (*m_parent)[ m_curType ].end() )
86 ++m_it;
87
88 validate();
89
90 return *this;
91 }
92
93 bool operator!=( const ITERATOR_BASE& aOther ) const
94 {
95 if( aOther.m_parent != m_parent )
96 return true;
97
98 if( aOther.m_filter != m_filter )
99 return true;
100
101 if( aOther.m_curType != m_curType )
102 return true;
103
104 return aOther.m_it != m_it;
105 }
106
107 protected:
116 ITERATOR_BASE( ITEM_CONTAINER* aItems, ITEM_CONTAINER_IT aIt,
117 int aBucket, int aType = UNDEFINED_TYPE )
118 : m_parent( aItems ), m_it( aIt ), m_curType( aBucket )
119 {
120 m_filter = ( aType != UNDEFINED_TYPE );
121 }
122
124 void validate()
125 {
126 // for all-items iterators (unfiltered): check if this is the end of the
127 // current type container, if so switch to the next non-empty container
128 if( !m_filter && m_it == (*m_parent)[ m_curType ].end() )
129 {
130 // switch to the next type (look for a not empty container)
131 int nextType = m_curType;
132
133 do
134 ++nextType;
135 while( ( nextType <= LAST_TYPE ) && (*m_parent)[ nextType ].empty() );
136
137 // there is another not empty container, so make the iterator point to it,
138 // otherwise it means the iterator points to the last item
139 if( nextType <= LAST_TYPE )
140 {
141 m_curType = nextType;
142 m_it = (*m_parent)[ m_curType ].begin();
143 }
144 }
145 }
146
148 ITEM_CONTAINER* m_parent;
149
151 ITEM_CONTAINER_IT m_it;
152
155
158
159 friend class MULTIVECTOR;
160 };
161
164 typename ITEM_PTR_VECTOR::iterator> ITERATOR;
167 typename ITEM_PTR_VECTOR::const_iterator> CONST_ITERATOR;
168
169
171 {
172 }
173
174 void push_back( T* aItem )
175 {
176 operator[]( aItem->Type() ).push_back( aItem );
177 }
178
179 ITERATOR erase( const ITERATOR& aIterator )
180 {
181 ITERATOR it( aIterator );
182 it.m_it = (*aIterator.m_parent)[ aIterator.m_curType ].erase( aIterator.m_it );
183 it.validate();
184
185 return it;
186 }
187
189 {
190 int bucket = ( aType != UNDEFINED_TYPE ) ? aType : first();
191 return ITERATOR( this, operator[]( bucket ).begin(), bucket, aType );
192 }
193
195 {
196 int bucket = ( aType != UNDEFINED_TYPE ) ? aType : last();
197 return ITERATOR( this, operator[]( bucket ).end(), bucket, aType );
198 }
199
201 {
202 int bucket = ( aType != UNDEFINED_TYPE ) ? aType : first();
203 return CONST_ITERATOR( this, operator[]( bucket ).begin(), bucket, aType );
204 }
205
206 CONST_ITERATOR end( int aType = UNDEFINED_TYPE ) const
207 {
208 int bucket = ( aType != UNDEFINED_TYPE ) ? aType : last();
209 return CONST_ITERATOR( this, operator[]( bucket ).end(), bucket, aType );
210 }
211
212 void clear( int aType = UNDEFINED_TYPE )
213 {
214 if( aType != UNDEFINED_TYPE )
215 {
216 operator[]( aType ).clear();
217 }
218 else
219 {
220 for( int i = 0; i < TYPES_COUNT; ++i)
221 m_data[ i ].clear();
222 }
223 }
224
225 size_t size( int aType = UNDEFINED_TYPE ) const
226 {
227 if( aType != UNDEFINED_TYPE )
228 {
229 return operator[]( aType ).size();
230 }
231 else
232 {
233 size_t cnt = 0;
234
235 for( int i = 0; i < TYPES_COUNT; ++i)
236 cnt += m_data[ i ].size();
237
238 return cnt;
239 }
240 }
241
242 bool empty( int aType = UNDEFINED_TYPE ) const
243 {
244 return ( size( aType ) == 0 );
245 }
246
247 void sort()
248 {
249 for( int i = 0; i < TYPES_COUNT; ++i )
250 m_data[ i ].sort();
251 }
252
256 void unique()
257 {
258 for( int i = 0; i < TYPES_COUNT; ++i )
259 {
260 if( m_data[ i ].size() > 1 )
261 m_data[ i ].unique();
262 }
263 }
264
266 {
267 if( ( aType < FIRST_TYPE ) || ( aType > LAST_TYPE ) )
268 {
269 wxFAIL_MSG( wxT( "Attempted access to type not within MULTIVECTOR" ) );
270
271 // return type is a reference so we have to return something...
272 aType = FIRST_TYPE;
273 }
274
275 return m_data[ aType - FIRST_TYPE ];
276 }
277
278 const ITEM_PTR_VECTOR& operator[]( int aType ) const
279 {
280 if( ( aType < FIRST_TYPE ) || ( aType > LAST_TYPE ) )
281 {
282 wxFAIL_MSG( wxT( "Attempted access to type not within MULTIVECTOR" ) );
283
284 // return type is a reference so we have to return something...
285 aType = FIRST_TYPE;
286 }
287
288 return m_data[ aType - FIRST_TYPE ];
289 }
290
291 // Range of valid types handled by the iterator
292 static constexpr int FIRST_TYPE = FIRST_TYPE_VAL;
293 static constexpr int LAST_TYPE = LAST_TYPE_VAL;
294 static constexpr int TYPES_COUNT = LAST_TYPE - FIRST_TYPE + 1;
295
296private:
298 int first() const
299 {
300 int i = 0;
301
302 while( ( i < TYPES_COUNT ) && ( m_data[ i ].empty() ) )
303 ++i;
304
305 return ( i == TYPES_COUNT ) ? FIRST_TYPE : FIRST_TYPE + i;
306 }
307
309 int last() const
310 {
311 int i = TYPES_COUNT - 1;
312
313 while( ( i >= 0 ) && ( m_data[ i ].empty() ) )
314 --i;
315
316 return ( i < 0 ) ? FIRST_TYPE : FIRST_TYPE + i;
317 }
318
321};
322
323#endif /* MULTIVECTOR_H */
Generic implementation of a flat const/non-const iterator over contained items.The non-const iterator...
Definition: multivector.h:71
ITERATOR_BASE(ITEM_CONTAINER *aItems, ITEM_CONTAINER_IT aIt, int aBucket, int aType=UNDEFINED_TYPE)
Assures the iterator is in a valid state.
Definition: multivector.h:116
ITEM_CONTAINER_IT m_it
Flag indicating whether type filtering is enabled.
Definition: multivector.h:151
ITEM_TYPE * operator->()
Definition: multivector.h:78
void validate()
Wrapped container.
Definition: multivector.h:124
bool m_filter
Type of the currently iterated items.
Definition: multivector.h:154
bool operator!=(const ITERATOR_BASE &aOther) const
Definition: multivector.h:93
ITEM_CONTAINER * m_parent
Iterator for one of the ptr_vector containers stored in the array.
Definition: multivector.h:148
ITERATOR_BASE & operator++()
Definition: multivector.h:83
Multivector container type.
Definition: multivector.h:46
size_t size(int aType=UNDEFINED_TYPE) const
Definition: multivector.h:225
CONST_ITERATOR begin(int aType=UNDEFINED_TYPE) const
Definition: multivector.h:200
void sort()
Definition: multivector.h:247
bool empty(int aType=UNDEFINED_TYPE) const
Definition: multivector.h:242
static constexpr int FIRST_TYPE
Definition: multivector.h:292
ITERATOR_BASE< const T, const MULTIVECTOR< T, FIRST_TYPE_VAL, LAST_TYPE_VAL >, typename ITEM_PTR_VECTOR::const_iterator > CONST_ITERATOR
Definition: multivector.h:167
ITEM_PTR_VECTOR & operator[](int aType)
Definition: multivector.h:265
const ITEM_PTR_VECTOR & operator[](int aType) const
Definition: multivector.h:278
CONST_ITERATOR end(int aType=UNDEFINED_TYPE) const
Definition: multivector.h:206
void unique()
Remove duplicate elements in list.
Definition: multivector.h:256
void push_back(T *aItem)
Definition: multivector.h:174
ITERATOR_BASE< T, MULTIVECTOR< T, FIRST_TYPE_VAL, LAST_TYPE_VAL >, typename ITEM_PTR_VECTOR::iterator > ITERATOR
The const iterator.
Definition: multivector.h:164
ITERATOR end(int aType=UNDEFINED_TYPE)
Definition: multivector.h:194
int last() const
Contained items by type.
Definition: multivector.h:309
int first() const
< Get first non-empty type or first type if all are empty.
Definition: multivector.h:298
ITEM_PTR_VECTOR m_data[TYPES_COUNT]
Definition: multivector.h:320
void clear(int aType=UNDEFINED_TYPE)
Definition: multivector.h:212
static constexpr int LAST_TYPE
Definition: multivector.h:293
static constexpr int UNDEFINED_TYPE
Type value to indicate no specific type.
Definition: multivector.h:52
ITERATOR erase(const ITERATOR &aIterator)
Definition: multivector.h:179
boost::ptr_vector< T > ITEM_PTR_VECTOR
Helper for defining a list of library draw object pointers.
Definition: multivector.h:64
ITERATOR begin(int aType=UNDEFINED_TYPE)
Definition: multivector.h:188
static constexpr int TYPES_COUNT
Definition: multivector.h:294