List.h
Go to the documentation of this file.
1 /*
2  * Copyright (C) 2006-2011, SRI International (R)
3  *
4  * This program is free software: you can redistribute it and/or modify
5  * it under the terms of the GNU Lesser General Public License as published by
6  * the Free Software Foundation, either version 3 of the License, or
7  * (at your option) any later version.
8  *
9  * This program is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12  * GNU Lesser General Public License for more details.
13  *
14  * You should have received a copy of the GNU Lesser General Public License
15  * along with this program. If not, see <http://www.gnu.org/licenses/>.
16  */
17 
18 #pragma once
19 
20 #ifndef __OpenKarto_List_h__
21 #define __OpenKarto_List_h__
22 
23 #include <OpenKarto/Exception.h>
24 #include <OpenKarto/Math.h>
25 #include <OpenKarto/StringHelper.h>
26 
27 namespace karto
28 {
29 
31 
32 
36 
37  template<class T>
39 
40  template<class T>
41  class ListIterator;
42 
48  template<class T>
49  class List
50  {
51  public:
56 
61 
65  List()
66  : m_pElements(NULL)
67  {
68  Reset();
69  }
70 
76  : m_pElements(NULL)
77  {
78  Reset();
79  Resize(size);
80  }
81 
85  List(const List& rOther)
86  : m_pElements(NULL)
87  {
88  Reset();
89  Resize(rOther.m_Size);
90 
91  for (kt_size_t i = 0; i < m_Size; i++)
92  {
93  m_pElements[i] = rOther.m_pElements[i];
94  }
95  }
96 
100  virtual ~List()
101  {
102  Reset();
103  }
104 
105  public:
111  virtual void Add(const T& rValue)
112  {
113  // resize
114  if (m_Size == m_Capacity)
115  {
116  EnsureCapacity(m_Capacity * 2 + 1); // +1 in case capacity is 0
117  }
118  m_pElements[m_Size] = rValue;
119  m_Size++;
120  }
121 
126  virtual void Add(const List& rValue)
127  {
128  kt_size_t combinedSize = m_Size + rValue.m_Size;
129  if (m_Capacity < combinedSize)
130  {
131  EnsureCapacity(combinedSize);
132  }
133 
134  for (kt_size_t i = 0; i < rValue.m_Size; i++)
135  {
136  m_pElements[m_Size + i] = rValue.m_pElements[i];
137  }
138 
139  m_Size = combinedSize;
140  }
141 
148  virtual kt_bool Remove(const T& rValue)
149  {
150  for (kt_size_t i = 0; i < m_Size; i++)
151  {
152  if (m_pElements[i] == rValue)
153  {
154  RemoveAt(i);
155  return true;
156  }
157  }
158 
159  return false;
160  }
161 
166  virtual void RemoveAt(kt_size_t index)
167  {
168  if (index >= m_Size)
169  {
170  String message;
171  message.Append("Cannot remove item: invalid index: ");
172  message.Append(StringHelper::ToString(index));
173 
174  throw Exception(message);
175  }
176 
177  if (m_Size > 0)
178  {
179  // move remaining elements
180  for (kt_size_t i = index; i < m_Size - 1; i++)
181  {
182  m_pElements[i] = m_pElements[i + 1];
183  }
184 
185  // destroy last element by calling its destructor
186  m_pElements[m_Size - 1] = T();
187 
188  m_Size--;
189  }
190  }
191 
197  virtual kt_bool Contains(const T& rValue) const
198  {
199  for (kt_size_t i = 0; i < m_Size; i++)
200  {
201  if (m_pElements[i] == rValue)
202  {
203  return true;
204  }
205  }
206 
207  return false;
208  }
209 
214  inline virtual kt_size_t Size() const
215  {
216  return m_Size;
217  }
218 
223  inline virtual kt_bool IsEmpty() const
224  {
225  return m_Size == 0;
226  }
227 
231  virtual void Clear()
232  {
233  if (m_Size > 0)
234  {
235  // call destructor on each element
236  for (kt_size_t i = 0; i < m_Size; i++)
237  {
238  m_pElements[i] = T();
239  }
240  }
241 
242  m_Size = 0;
243  }
244 
250  inline virtual T& Get(kt_size_t index)
251  {
252  return (*this)[index];
253  }
254 
260  inline virtual const T& Get(kt_size_t index) const
261  {
262  return (*this)[index];
263  }
264 
270  inline T* Find(const T& rValue)
271  {
272  for (kt_size_t i = 0; i < m_Size; i++)
273  {
274  if (m_pElements[i] == rValue)
275  {
276  return &m_pElements[i];
277  }
278  }
279 
280  return NULL;
281  }
282 
288  void Set(kt_size_t index, const T& rValue)
289  {
290  if (index >= m_Size)
291  {
292  assert(false);
293  }
294 
295  m_pElements[index] = rValue;
296  }
297 
303  virtual const T& Front() const
304  {
305  if (m_Size == 0)
306  {
307  assert(false);
308  throw Exception("List is empty!");
309  }
310 
311  return Get(0);
312  }
313 
319  virtual const T& Back() const
320  {
321  if (m_Size == 0)
322  {
323  assert(false);
324  throw Exception("List is empty!");
325  }
326 
327  return Get(Size() - 1);
328  }
329 
334  virtual void Resize(kt_size_t newSize)
335  {
336  if (newSize != m_Size)
337  {
338  T* pElements = new T[newSize];
339  if (m_pElements != NULL)
340  {
341  kt_size_t smallerSize = karto::math::Minimum(newSize, m_Size);
342 
343  for (kt_size_t i = 0; i < smallerSize; i++)
344  {
345  pElements[i] = m_pElements[i];
346  }
347 
348  delete [] m_pElements;
349  }
350 
351  m_pElements = pElements;
352  m_Size = newSize;
353  m_Capacity = newSize;
354  }
355  }
356 
361  void EnsureCapacity(kt_size_t newCapacity)
362  {
363  kt_size_t oldSize = m_Size;
364  Resize(newCapacity);
365  if (newCapacity > oldSize)
366  {
367  m_Size = oldSize;
368  }
369  }
370 
380  inline kt_int32s BinarySearch(const T& rValue, kt_int32s (*f)(const T& a, const T& b))
381  {
382  assert(m_Size > 0);
383 
384  kt_int32s lo = 0;
385  kt_int32s hi = static_cast<kt_int32s>(m_Size) - 1;
386 
387  while (lo <= hi)
388  {
389  kt_int32s mid = (lo + hi) / 2;
390  kt_int32s comparison = f(m_pElements[mid], rValue);
391  if (comparison == 0)
392  {
393  return mid;
394  }
395  else if (comparison < 0)
396  {
397  lo = mid + 1;
398  }
399  else // comparison > 0
400  {
401  hi = mid - 1;
402  }
403  }
404 
405  return -1;
406  }
407 
408  public:
414  inline T& operator[](kt_size_t index)
415  {
416  if (index >= m_Size)
417  {
418  assert(false);
419  throw Exception("Out of bounds exception: " + StringHelper::ToString(index) + " (>= " + StringHelper::ToString(m_Size) + ")");
420  }
421 
422  return m_pElements[index];
423  }
424 
430  inline const T& operator[](kt_size_t index) const
431  {
432  if (index >= m_Size)
433  {
434  assert(false);
435  throw Exception("Out of bounds exception: " + StringHelper::ToString(index) + " (>= " + StringHelper::ToString(m_Size) + ")");
436  }
437 
438  return m_pElements[index];
439  }
440 
444  List& operator=(const List& rOther)
445  {
446  if (&rOther != this)
447  {
448  Reset();
449  Resize(rOther.m_Size);
450  for (kt_size_t i = 0; i < rOther.m_Size; i++)
451  {
452  m_pElements[i] = rOther.m_pElements[i];
453  }
454  }
455 
456  return *this;
457  }
458 
462  kt_bool operator==(const List& rOther) const
463  {
464  if (Size() != rOther.Size())
465  {
466  return false;
467  }
468 
469  for (kt_size_t i = 0; i < rOther.m_Size; i++)
470  {
471  if (m_pElements[i] != rOther.m_pElements[i])
472  {
473  return false;
474  }
475  }
476 
477  return true;
478  }
479 
480  private:
481  void Reset()
482  {
483  delete [] m_pElements;
484  m_pElements = NULL;
485  m_Size = 0;
486  m_Capacity = 0;
487  }
488 
489  public:
495  {
496  return ConstListIterator<T>(this);
497  }
498 
504  {
505  return ListIterator<T>(this);
506  }
507 
508  private:
512  }; // class List<T>
513 
517 
521  template<class T>
522  class ConstListIterator
523  {
524  public:
530  : m_pList(pList)
531  , m_Index(0)
532  {
533  if (pList == NULL)
534  {
535  throw Exception("Cannot create iterator: List is NULL");
536  }
537  }
538 
543  virtual kt_bool HasNext() const
544  {
545  return m_Index < m_pList->Size();
546  }
547 
552  virtual const T& Next()
553  {
554  if (m_Index < m_pList->Size())
555  {
556  m_Index++;
557  return m_pList->Get(m_Index - 1);
558  }
559 
560  throw Exception("Cannot increment iterator: No more items in iterator.");
561  }
562 
567  virtual const T& operator*() const
568  {
569  if (m_Index < m_pList->Size())
570  {
571  return m_pList->Get(m_Index);
572  }
573 
574  throw Exception("Cannot dereference iterator: No more items in iterator.");
575  }
576 
581  virtual const T* operator->() const
582  {
583  if (m_Index < m_pList->Size())
584  {
585  return &m_pList->Get(m_Index);
586  }
587 
588  throw Exception("Cannot dereference iterator: No more items in iterator.");
589  }
590 
595  virtual const T& operator++()
596  {
597  Next();
598  ConstListIterator iter = *this;
599  return *iter;
600  }
601 
606  virtual T operator++(int /*dummy*/)
607  {
608  return Next();
609  }
610 
614  virtual const ConstListIterator& operator=(const ConstListIterator& rOther)
615  {
616  m_pList = rOther.m_pList;
617  m_Index = rOther.m_Index;
618  return *this;
619  }
620 
624  virtual kt_bool operator!=(const ConstListIterator& rOther) const
625  {
626  if (m_pList != rOther.m_pList)
627  {
628  throw Exception("Iterators are not operating on the same list");
629  }
630 
631  return m_Index != rOther.m_Index;
632  }
633 
634  private:
635  const List<T>* m_pList;
637  }; // class ConstIterator<T>
638 
642 
646  template<class T>
647  class ListIterator
648  {
649  public:
655  : m_pList(pList)
656  , m_Index(0)
657  {
658  if (pList == NULL)
659  {
660  throw Exception("Cannot create iterator: List is NULL");
661  }
662  }
663 
668  virtual kt_bool HasNext() const
669  {
670  return m_Index < m_pList->Size();
671  }
672 
677  virtual T& Next()
678  {
679  if (m_Index < m_pList->Size())
680  {
681  m_Index++;
682  return m_pList->Get(m_Index - 1);
683  }
684 
685  throw Exception("Cannot increment iterator: No more items in iterator.");
686  }
687 
691  void Erase()
692  {
693  if (m_Index < m_pList->Size())
694  {
695  m_pList->RemoveAt(m_Index);
696  }
697 
698  throw Exception("Cannot erase item: No more items in iterator.");
699  }
700 
705  virtual T& operator*() const
706  {
707  if (m_Index < m_pList->Size())
708  {
709  return m_pList->Get(m_Index);
710  }
711 
712  throw Exception("Cannot dereference iterator: No more items in iterator.");
713  }
714 
719  virtual T* operator->() const
720  {
721  if (m_Index < m_pList->Size())
722  {
723  return &m_pList->Get(m_Index);
724  }
725 
726  throw Exception("Cannot dereference iterator: No more items in iterator.");
727  }
728 
733  virtual const T& operator++()
734  {
735  Next();
736  ListIterator iter = *this;
737  return *iter;
738  }
739 
744  virtual T operator++(int /*dummy*/)
745  {
746  return Next();
747  }
748 
752  virtual const ListIterator& operator=(const ListIterator& rOther)
753  {
754  m_pList = rOther.m_pList;
755  m_Index = rOther.m_Index;
756  return *this;
757  }
758 
762  virtual kt_bool operator!=(const ListIterator& rOther) const
763  {
764  if (m_pList != rOther.m_pList)
765  {
766  throw Exception("Iterators are not operating on the same list");
767  }
768 
769  return m_Index != rOther.m_Index;
770  }
771 
772  private:
775  }; // class Iterator<T>
776 
778 }
779 
780 #endif // __OpenKarto_List_h__
void Set(kt_size_t index, const T &rValue)
Definition: List.h:288
virtual kt_bool HasNext() const
Definition: List.h:543
void Append(const String &rString)
Definition: String.cpp:82
virtual kt_size_t Size() const
Definition: List.h:214
bool kt_bool
Definition: Types.h:145
virtual const T & Back() const
Definition: List.h:319
std::size_t kt_size_t
Definition: Types.h:138
virtual kt_bool HasNext() const
Definition: List.h:668
kt_size_t m_Capacity
Definition: List.h:511
T & operator[](kt_size_t index)
Definition: List.h:414
virtual const T & Front() const
Definition: List.h:303
f
virtual T & Get(kt_size_t index)
Definition: List.h:250
virtual void Resize(kt_size_t newSize)
Definition: List.h:334
const List< T > * m_pList
Definition: List.h:635
virtual T & Next()
Definition: List.h:677
const T & operator[](kt_size_t index) const
Definition: List.h:430
void Erase()
Definition: List.h:691
virtual void Add(const T &rValue)
Definition: List.h:111
T * m_pElements
Definition: List.h:509
kt_size_t m_Index
Definition: List.h:636
List()
Definition: List.h:65
virtual const T & Get(kt_size_t index) const
Definition: List.h:260
virtual kt_bool Remove(const T &rValue)
Definition: List.h:148
T * Find(const T &rValue)
Definition: List.h:270
virtual void RemoveAt(kt_size_t index)
Definition: List.h:166
virtual const T & operator*() const
Definition: List.h:567
virtual ConstListIterator< T > GetConstIterator() const
Definition: List.h:494
kt_size_t m_Size
Definition: List.h:510
void EnsureCapacity(kt_size_t newCapacity)
Definition: List.h:361
kt_bool operator==(const List &rOther) const
Definition: List.h:462
virtual const T * operator->() const
Definition: List.h:581
virtual kt_bool IsEmpty() const
Definition: List.h:223
List(kt_size_t size)
Definition: List.h:75
virtual ListIterator< T > GetIterator()
Definition: List.h:503
virtual const ListIterator & operator=(const ListIterator &rOther)
Definition: List.h:752
static String ToString(const char *value)
virtual T operator++(int)
Definition: List.h:606
virtual void Add(const List &rValue)
Definition: List.h:126
const T & Minimum(const T &value1, const T &value2)
Definition: Math.h:126
ListIterator(List< T > *pList)
Definition: List.h:654
virtual kt_bool Contains(const T &rValue) const
Definition: List.h:197
ConstListIterator< T > ConstIterator
Definition: List.h:55
int32_t kt_int32s
Definition: Types.h:106
virtual const T & Next()
Definition: List.h:552
virtual const T & operator++()
Definition: List.h:595
kt_int32s BinarySearch(const T &rValue, kt_int32s(*f)(const T &a, const T &b))
Definition: List.h:380
virtual T & operator*() const
Definition: List.h:705
virtual ~List()
Definition: List.h:100
ListIterator< T > Iterator
Definition: List.h:60
virtual kt_bool operator!=(const ListIterator &rOther) const
Definition: List.h:762
List(const List &rOther)
Definition: List.h:85
virtual T * operator->() const
Definition: List.h:719
Definition: Any.cpp:20
virtual void Clear()
Definition: List.h:231
List & operator=(const List &rOther)
Definition: List.h:444
kt_size_t m_Index
Definition: List.h:774
virtual T operator++(int)
Definition: List.h:744
virtual kt_bool operator!=(const ConstListIterator &rOther) const
Definition: List.h:624
virtual const T & operator++()
Definition: List.h:733
ConstListIterator(const List< T > *pList)
Definition: List.h:529
List< T > * m_pList
Definition: List.h:773
void Reset()
Definition: List.h:481
virtual const ConstListIterator & operator=(const ConstListIterator &rOther)
Definition: List.h:614


nav2d_karto
Author(s): Sebastian Kasperski
autogenerated on Thu Jun 6 2019 19:20:24