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 KiCad Developers, see AUTHORS.txt for contributors.
6  *
7  * @author Maciej Suminski <maciej.suminski@cern.ch>
8  * @author Bernhard Stegmaier <stegmaier@sw-systems.de>
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 
44 template<typename T, int FIRST_TYPE_VAL, int LAST_TYPE_VAL>
46 {
47 public:
52  static constexpr int UNDEFINED_TYPE = 0;
53  static_assert( FIRST_TYPE_VAL > UNDEFINED_TYPE,
54  "FIRST_TYPE_VAL has to be greater than UNDEFINED_TYPE" );
55  static_assert( FIRST_TYPE_VAL < LAST_TYPE_VAL,
56  "FIRST_TYPE_VAL has to 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:
117  ITERATOR_BASE( ITEM_CONTAINER* aItems, ITEM_CONTAINER_IT aIt,
118  int aBucket, int aType = UNDEFINED_TYPE )
119  : m_parent( aItems ), m_it( aIt ), m_curType( aBucket )
120  {
121  m_filter = ( aType != UNDEFINED_TYPE );
122  }
123 
125  void validate()
126  {
127  // for all-items iterators (unfiltered): check if this is the end of the
128  // current type container, if so switch to the next non-empty container
129  if( !m_filter && m_it == (*m_parent)[ m_curType ].end() )
130  {
131  // switch to the next type (look for a not empty container)
132  int nextType = m_curType;
133 
134  do
135  ++nextType;
136  while( ( nextType <= LAST_TYPE ) && (*m_parent)[ nextType ].empty() );
137 
138  // there is another not empty container, so make the iterator point to it,
139  // otherwise it means the iterator points to the last item
140  if( nextType <= LAST_TYPE )
141  {
142  m_curType = nextType;
143  m_it = (*m_parent)[ m_curType ].begin();
144  }
145  }
146  }
147 
149  ITEM_CONTAINER* m_parent;
150 
152  ITEM_CONTAINER_IT m_it;
153 
155  bool m_filter;
156 
159 
160  friend class MULTIVECTOR;
161  };
162 
165  typename ITEM_PTR_VECTOR::iterator> ITERATOR;
167  typedef ITERATOR_BASE<const T, const MULTIVECTOR<T, FIRST_TYPE_VAL, LAST_TYPE_VAL>,
168  typename ITEM_PTR_VECTOR::const_iterator> CONST_ITERATOR;
169 
170 
172  {
173  }
174 
175  void push_back( T* aItem )
176  {
177  operator[]( aItem->Type() ).push_back( aItem );
178  }
179 
180  ITERATOR erase( const ITERATOR& aIterator )
181  {
182  ITERATOR it( aIterator );
183  it.m_it = (*aIterator.m_parent)[ aIterator.m_curType ].erase( aIterator.m_it );
184  it.validate();
185 
186  return it;
187  }
188 
190  {
191  int bucket = ( aType != UNDEFINED_TYPE ) ? aType : first();
192  return ITERATOR( this, operator[]( bucket ).begin(), bucket, aType );
193  }
194 
195  ITERATOR end( int aType = UNDEFINED_TYPE )
196  {
197  int bucket = ( aType != UNDEFINED_TYPE ) ? aType : last();
198  return ITERATOR( this, operator[]( bucket ).end(), bucket, aType );
199  }
200 
201  CONST_ITERATOR begin( int aType = UNDEFINED_TYPE ) const
202  {
203  int bucket = ( aType != UNDEFINED_TYPE ) ? aType : first();
204  return CONST_ITERATOR( this, operator[]( bucket ).begin(), bucket, aType );
205  }
206 
207  CONST_ITERATOR end( int aType = UNDEFINED_TYPE ) const
208  {
209  int bucket = ( aType != UNDEFINED_TYPE ) ? aType : last();
210  return CONST_ITERATOR( this, operator[]( bucket ).end(), bucket, aType );
211  }
212 
213  void clear( int aType = UNDEFINED_TYPE )
214  {
215  if( aType != UNDEFINED_TYPE )
216  {
217  operator[]( aType ).clear();
218  }
219  else
220  {
221  for( int i = 0; i < TYPES_COUNT; ++i)
222  m_data[ i ].clear();
223  }
224  }
225 
226  size_t size( int aType = UNDEFINED_TYPE ) const
227  {
228  if( aType != UNDEFINED_TYPE )
229  {
230  return operator[]( aType ).size();
231  }
232  else
233  {
234  size_t cnt = 0;
235 
236  for( int i = 0; i < TYPES_COUNT; ++i)
237  cnt += m_data[ i ].size();
238 
239  return cnt;
240  }
241  }
242 
243  bool empty( int aType = UNDEFINED_TYPE )
244  {
245  return ( size( aType ) == 0 );
246  }
247 
248  void sort()
249  {
250  for( int i = 0; i < TYPES_COUNT; ++i )
251  m_data[ i ].sort();
252  }
253 
257  void unique()
258  {
259  for( int i = 0; i < TYPES_COUNT; ++i )
260  {
261  if( m_data[ i ].size() > 1 )
262  m_data[ i ].unique();
263  }
264  }
265 
267  {
268  if( ( aType < FIRST_TYPE ) || ( aType > LAST_TYPE ) )
269  {
270  wxFAIL_MSG( "Attempted access to type not within MULTIVECTOR" );
271 
272  // return type is a reference so we have to return something...
273  aType = FIRST_TYPE;
274  }
275 
276  return m_data[ aType - FIRST_TYPE ];
277  }
278 
279  const ITEM_PTR_VECTOR& operator[]( int aType ) const
280  {
281  if( ( aType < FIRST_TYPE ) || ( aType > LAST_TYPE ) )
282  {
283  wxFAIL_MSG( "Attempted access to type not within MULTIVECTOR" );
284 
285  // return type is a reference so we have to return something...
286  aType = FIRST_TYPE;
287  }
288 
289  return m_data[ aType - FIRST_TYPE ];
290  }
291 
292  // Range of valid types handled by the iterator
293  static constexpr int FIRST_TYPE = FIRST_TYPE_VAL;
294  static constexpr int LAST_TYPE = LAST_TYPE_VAL;
295  static constexpr int TYPES_COUNT = LAST_TYPE - FIRST_TYPE + 1;
296 
297 private:
299  int first() const
300  {
301  int i = 0;
302 
303  while( ( i < TYPES_COUNT ) && ( m_data[ i ].empty() ) )
304  ++i;
305 
306  return ( i == TYPES_COUNT ) ? FIRST_TYPE : FIRST_TYPE + i;
307  }
308 
310  int last() const
311  {
312  int i = TYPES_COUNT - 1;
313 
314  while( ( i >= 0 ) && ( m_data[ i ].empty() ) )
315  --i;
316 
317  return ( i < 0 ) ? FIRST_TYPE : FIRST_TYPE + i;
318  }
319 
322 };
323 
324 #endif /* MULTIVECTOR_H */
CONST_ITERATOR end(int aType=UNDEFINED_TYPE) const
Definition: multivector.h:207
CONST_ITERATOR begin(int aType=UNDEFINED_TYPE) const
Definition: multivector.h:201
const ITEM_PTR_VECTOR & operator[](int aType) const
Definition: multivector.h:279
ITERATOR begin(int aType=UNDEFINED_TYPE)
Definition: multivector.h:189
ITEM_PTR_VECTOR m_data[TYPES_COUNT]
Contained items by type
Definition: multivector.h:321
bool operator!=(const ITERATOR_BASE &aOther) const
Definition: multivector.h:93
ITERATOR_BASE(ITEM_CONTAINER *aItems, ITEM_CONTAINER_IT aIt, int aBucket, int aType=UNDEFINED_TYPE)
Constructor.
Definition: multivector.h:117
bool m_filter
Flag indicating whether type filtering is enabled
Definition: multivector.h:155
bool empty(int aType=UNDEFINED_TYPE)
Definition: multivector.h:243
static constexpr int TYPES_COUNT
Definition: multivector.h:295
void clear(int aType=UNDEFINED_TYPE)
Definition: multivector.h:213
void unique()
Remove duplicate elements in list.
Definition: multivector.h:257
Multivector container type.
Definition: multivector.h:45
void sort()
Definition: multivector.h:248
static constexpr int LAST_TYPE
Definition: multivector.h:294
ITERATOR end(int aType=UNDEFINED_TYPE)
Definition: multivector.h:195
ITERATOR_BASE & operator++()
Definition: multivector.h:83
static constexpr int FIRST_TYPE
Definition: multivector.h:293
static constexpr int UNDEFINED_TYPE
Type value to indicate no specific type.
Definition: multivector.h:52
void push_back(T *aItem)
Definition: multivector.h:175
ITEM_TYPE & operator *()
Definition: multivector.h:73
Generic implementation of a flat const/non-const iterator over contained items.
Definition: multivector.h:70
ITEM_CONTAINER * m_parent
Wrapped container
Definition: multivector.h:149
ITERATOR erase(const ITERATOR &aIterator)
Definition: multivector.h:180
int m_curType
Type of the currently iterated items
Definition: multivector.h:158
ITERATOR_BASE< T, MULTIVECTOR< T, FIRST_TYPE_VAL, LAST_TYPE_VAL >, typename ITEM_PTR_VECTOR::iterator > ITERATOR
The non-const iterator
Definition: multivector.h:165
ITEM_TYPE * operator->()
Definition: multivector.h:78
ITEM_CONTAINER_IT m_it
Iterator for one of the ptr_vector containers stored in the array
Definition: multivector.h:152
boost::ptr_vector< T > ITEM_PTR_VECTOR
Helper for defining a list of library draw object pointers.
Definition: multivector.h:54
ITERATOR_BASE< const T, const MULTIVECTOR< T, FIRST_TYPE_VAL, LAST_TYPE_VAL >, typename ITEM_PTR_VECTOR::const_iterator > CONST_ITERATOR
The const iterator
Definition: multivector.h:168
int last() const
Get last non-empty type or first type if all are empty.
Definition: multivector.h:310
int first() const
Get first non-empty type or first type if all are empty.
Definition: multivector.h:299
ITEM_PTR_VECTOR & operator[](int aType)
Definition: multivector.h:266
void validate()
Assures the iterator is in a valid state.
Definition: multivector.h:125
size_t size(int aType=UNDEFINED_TYPE) const
Definition: multivector.h:226