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