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 <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 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 
154  bool m_filter;
155 
158 
159  friend class MULTIVECTOR;
160  };
161 
164  typename ITEM_PTR_VECTOR::iterator> ITERATOR;
166  typedef ITERATOR_BASE<const T, const MULTIVECTOR<T, FIRST_TYPE_VAL, LAST_TYPE_VAL>,
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 
194  ITERATOR end( int aType = UNDEFINED_TYPE )
195  {
196  int bucket = ( aType != UNDEFINED_TYPE ) ? aType : last();
197  return ITERATOR( this, operator[]( bucket ).end(), bucket, aType );
198  }
199 
200  CONST_ITERATOR begin( int aType = UNDEFINED_TYPE ) const
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( "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( "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 
296 private:
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 */
CONST_ITERATOR end(int aType=UNDEFINED_TYPE) const
Definition: multivector.h:206
CONST_ITERATOR begin(int aType=UNDEFINED_TYPE) const
Definition: multivector.h:200
const ITEM_PTR_VECTOR & operator[](int aType) const
Definition: multivector.h:278
ITERATOR begin(int aType=UNDEFINED_TYPE)
Definition: multivector.h:188
ITEM_PTR_VECTOR m_data[TYPES_COUNT]
Definition: multivector.h:320
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)
Assures the iterator is in a valid state.
Definition: multivector.h:116
bool m_filter
Type of the currently iterated items.
Definition: multivector.h:154
static constexpr int TYPES_COUNT
Definition: multivector.h:294
void clear(int aType=UNDEFINED_TYPE)
Definition: multivector.h:212
void unique()
Remove duplicate elements in list.
Definition: multivector.h:256
Multivector container type.
Definition: multivector.h:45
void sort()
Definition: multivector.h:247
bool empty(int aType=UNDEFINED_TYPE) const
Definition: multivector.h:242
static constexpr int LAST_TYPE
Definition: multivector.h:293
ITERATOR end(int aType=UNDEFINED_TYPE)
Definition: multivector.h:194
ITERATOR_BASE & operator++()
Definition: multivector.h:83
static constexpr int FIRST_TYPE
Definition: multivector.h:292
static constexpr int UNDEFINED_TYPE
Type value to indicate no specific type.
Definition: multivector.h:52
void push_back(T *aItem)
Definition: multivector.h:174
ITEM_TYPE & operator *()
Definition: multivector.h:73
Generic implementation of a flat const/non-const iterator over contained items.The non-const iterator...
Definition: multivector.h:70
ITEM_CONTAINER * m_parent
Iterator for one of the ptr_vector containers stored in the array.
Definition: multivector.h:148
ITERATOR erase(const ITERATOR &aIterator)
Definition: multivector.h:179
ITERATOR_BASE< T, MULTIVECTOR< T, FIRST_TYPE_VAL, LAST_TYPE_VAL >, typename ITEM_PTR_VECTOR::iterator > ITERATOR
The const iterator.
Definition: multivector.h:164
ITEM_TYPE * operator->()
Definition: multivector.h:78
ITEM_CONTAINER_IT m_it
Flag indicating whether type filtering is enabled.
Definition: multivector.h:151
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
Definition: multivector.h:167
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 & operator[](int aType)
Definition: multivector.h:265
void validate()
Wrapped container.
Definition: multivector.h:124
size_t size(int aType=UNDEFINED_TYPE) const
Definition: multivector.h:225