List.h
Go to the documentation of this file.
00001 /*
00002  * Copyright (C) 2006-2011, SRI International (R)
00003  *
00004  * This program is free software: you can redistribute it and/or modify
00005  * it under the terms of the GNU Lesser General Public License as published by
00006  * the Free Software Foundation, either version 3 of the License, or
00007  * (at your option) any later version.
00008  *
00009  * This program is distributed in the hope that it will be useful,
00010  * but WITHOUT ANY WARRANTY; without even the implied warranty of
00011  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00012  * GNU Lesser General Public License for more details.
00013  *
00014  * You should have received a copy of the GNU Lesser General Public License
00015  * along with this program.  If not, see <http://www.gnu.org/licenses/>.
00016  */
00017 
00018 #pragma once
00019 
00020 #ifndef __OpenKarto_List_h__
00021 #define __OpenKarto_List_h__
00022 
00023 #include <OpenKarto/Exception.h>
00024 #include <OpenKarto/Math.h>
00025 #include <OpenKarto/StringHelper.h>
00026 
00027 namespace karto
00028 {
00029 
00031 
00032 
00036 
00037   template<class T>
00038   class ConstListIterator;
00039 
00040   template<class T>
00041   class ListIterator;
00042 
00048   template<class T>
00049   class List
00050   {
00051   public:
00055     typedef ConstListIterator<T> ConstIterator;
00056     
00060     typedef ListIterator<T> Iterator;
00061     
00065     List()
00066       : m_pElements(NULL)
00067     {
00068       Reset();
00069     }
00070     
00075     List(kt_size_t size)
00076       : m_pElements(NULL)
00077     {
00078       Reset();
00079       Resize(size);
00080     }
00081     
00085     List(const List& rOther)
00086       : m_pElements(NULL)
00087     {
00088       Reset();
00089       Resize(rOther.m_Size);
00090       
00091       for (kt_size_t i = 0; i < m_Size; i++)
00092       {
00093         m_pElements[i] = rOther.m_pElements[i];
00094       }
00095     }
00096     
00100     virtual ~List()
00101     {
00102       Reset();
00103     }
00104     
00105   public:
00111     virtual void Add(const T& rValue)
00112     {
00113       // resize
00114       if (m_Size == m_Capacity)
00115       {
00116         EnsureCapacity(m_Capacity * 2 + 1); // +1 in case capacity is 0
00117       }
00118       m_pElements[m_Size] = rValue;
00119       m_Size++;
00120     }
00121     
00126     virtual void Add(const List& rValue)
00127     {
00128       kt_size_t combinedSize = m_Size + rValue.m_Size;
00129       if (m_Capacity < combinedSize)
00130       {
00131         EnsureCapacity(combinedSize);    
00132       }
00133       
00134       for (kt_size_t i = 0; i < rValue.m_Size; i++)
00135       {
00136         m_pElements[m_Size + i] = rValue.m_pElements[i];
00137       }
00138       
00139       m_Size = combinedSize;
00140     }
00141     
00148     virtual kt_bool Remove(const T& rValue) 
00149     {
00150       for (kt_size_t i = 0; i < m_Size; i++)
00151       {
00152         if (m_pElements[i] == rValue)
00153         {
00154           RemoveAt(i);
00155           return true;
00156         }
00157       }
00158       
00159       return false;
00160     }
00161     
00166     virtual void RemoveAt(kt_size_t index) 
00167     {
00168       if (index >= m_Size)
00169       {
00170         String message;
00171         message.Append("Cannot remove item: invalid index: ");
00172         message.Append(StringHelper::ToString(index));
00173         
00174         throw Exception(message);
00175       }
00176       
00177       if (m_Size > 0)
00178       {
00179         // move remaining elements
00180         for (kt_size_t i = index; i < m_Size - 1; i++)
00181         {
00182           m_pElements[i] = m_pElements[i + 1];
00183         }
00184 
00185         // destroy last element by calling its destructor
00186         m_pElements[m_Size - 1] = T();
00187 
00188         m_Size--;
00189       }
00190     }
00191 
00197     virtual kt_bool Contains(const T& rValue) const
00198     {
00199       for (kt_size_t i = 0; i < m_Size; i++)
00200       {
00201         if (m_pElements[i] == rValue)
00202         {
00203           return true;
00204         }
00205       }
00206       
00207       return false;
00208     }
00209     
00214     inline virtual kt_size_t Size() const
00215     {
00216       return m_Size;
00217     }
00218     
00223     inline virtual kt_bool IsEmpty() const
00224     {
00225       return m_Size == 0;
00226     }
00227     
00231     virtual void Clear()
00232     {
00233       if (m_Size > 0)
00234       {
00235         // call destructor on each element 
00236         for (kt_size_t i = 0; i < m_Size; i++)
00237         {
00238           m_pElements[i] = T();
00239         }
00240       }
00241       
00242       m_Size = 0;
00243     }
00244     
00250     inline virtual T& Get(kt_size_t index)
00251     {
00252       return (*this)[index];
00253     }
00254     
00260     inline virtual const T& Get(kt_size_t index) const
00261     {
00262       return (*this)[index];
00263     }
00264     
00270     inline T* Find(const T& rValue) 
00271     {
00272       for (kt_size_t i = 0; i < m_Size; i++)
00273       {
00274         if (m_pElements[i] == rValue)
00275         {
00276           return &m_pElements[i];
00277         }
00278       }
00279       
00280       return NULL;
00281     }
00282     
00288     void Set(kt_size_t index, const T& rValue)
00289     {
00290       if (index >= m_Size)
00291       {
00292         assert(false); 
00293       }
00294       
00295       m_pElements[index] = rValue;
00296     }
00297     
00303     virtual const T& Front() const
00304     {
00305       if (m_Size == 0)
00306       {
00307         assert(false);
00308         throw Exception("List is empty!");
00309       }
00310       
00311       return Get(0);
00312     }
00313     
00319     virtual const T& Back() const
00320     {
00321       if (m_Size == 0)
00322       {
00323         assert(false);
00324         throw Exception("List is empty!");
00325       }
00326       
00327       return Get(Size() - 1);
00328     }
00329     
00334     virtual void Resize(kt_size_t newSize)
00335     {
00336       if (newSize != m_Size)
00337       {
00338         T* pElements = new T[newSize];
00339         if (m_pElements != NULL)
00340         {
00341           kt_size_t smallerSize = karto::math::Minimum(newSize, m_Size);
00342 
00343           for (kt_size_t i = 0; i < smallerSize; i++)
00344           {
00345             pElements[i] = m_pElements[i];
00346           }
00347 
00348           delete [] m_pElements;
00349         }
00350 
00351         m_pElements = pElements;
00352         m_Size = newSize;
00353         m_Capacity = newSize;
00354       }
00355     }
00356     
00361     void EnsureCapacity(kt_size_t newCapacity)
00362     {
00363       kt_size_t oldSize = m_Size;
00364       Resize(newCapacity);
00365       if (newCapacity > oldSize)
00366       {
00367         m_Size = oldSize;
00368       }
00369     }    
00370     
00380     inline kt_int32s BinarySearch(const T& rValue, kt_int32s (*f)(const T& a, const T& b))
00381     {
00382       assert(m_Size > 0);
00383 
00384       kt_int32s lo = 0;
00385       kt_int32s hi = static_cast<kt_int32s>(m_Size) - 1;
00386       
00387       while (lo <= hi)
00388       {
00389         kt_int32s mid = (lo + hi) / 2;
00390         kt_int32s comparison = f(m_pElements[mid], rValue);
00391         if (comparison == 0)
00392         {
00393           return mid;
00394         }
00395         else if (comparison < 0)
00396         {
00397           lo = mid + 1;
00398         }
00399         else // comparison > 0
00400         {
00401           hi = mid - 1;
00402         }
00403       }
00404       
00405       return -1;
00406     }
00407 
00408   public:
00414     inline T& operator[](kt_size_t index)
00415     {
00416       if (index >= m_Size)
00417       {
00418         assert(false); 
00419         throw Exception("Out of bounds exception: " + StringHelper::ToString(index) + " (>= " + StringHelper::ToString(m_Size) + ")");
00420       }
00421       
00422       return m_pElements[index];
00423     }
00424     
00430     inline const T& operator[](kt_size_t index) const
00431     {
00432       if (index >= m_Size)
00433       {
00434         assert(false);
00435         throw Exception("Out of bounds exception: " + StringHelper::ToString(index) + " (>= " + StringHelper::ToString(m_Size) + ")");
00436       }
00437       
00438       return m_pElements[index];
00439     }
00440     
00444     List& operator=(const List& rOther)
00445     {
00446       if (&rOther != this)
00447       {
00448         Reset();
00449         Resize(rOther.m_Size);
00450         for (kt_size_t i = 0; i < rOther.m_Size; i++)
00451         {
00452           m_pElements[i] = rOther.m_pElements[i];
00453         }
00454       }
00455       
00456       return *this;
00457     }
00458     
00462     kt_bool operator==(const List& rOther) const
00463     {
00464       if (Size() != rOther.Size())
00465       {
00466         return false;
00467       }
00468       
00469       for (kt_size_t i = 0; i < rOther.m_Size; i++)
00470       {
00471         if (m_pElements[i] != rOther.m_pElements[i])
00472         {
00473           return false;
00474         }
00475       }
00476       
00477       return true;
00478     }
00479     
00480   private:
00481     void Reset()
00482     {
00483       delete [] m_pElements;
00484       m_pElements = NULL;
00485       m_Size = 0;
00486       m_Capacity = 0;
00487     }
00488     
00489   public:
00494     virtual ConstListIterator<T> GetConstIterator() const
00495     {
00496       return ConstListIterator<T>(this);
00497     }
00498 
00503     virtual ListIterator<T> GetIterator()
00504     {
00505       return ListIterator<T>(this);
00506     }
00507     
00508   private:
00509     T* m_pElements;
00510     kt_size_t m_Size;
00511     kt_size_t m_Capacity;
00512   }; // class List<T>
00513   
00517 
00521   template<class T>
00522   class ConstListIterator
00523   {
00524   public:
00529     ConstListIterator(const List<T>* pList)
00530       : m_pList(pList)
00531       , m_Index(0)
00532     {
00533       if (pList == NULL)
00534       {
00535         throw Exception("Cannot create iterator: List is NULL");
00536       }
00537     }
00538 
00543     virtual kt_bool HasNext() const
00544     {
00545       return m_Index < m_pList->Size();
00546     }
00547     
00552     virtual const T& Next()
00553     {
00554       if (m_Index < m_pList->Size())
00555       {
00556         m_Index++;
00557         return m_pList->Get(m_Index - 1);
00558       }
00559 
00560       throw Exception("Cannot increment iterator: No more items in iterator.");
00561     }
00562     
00567     virtual const T& operator*() const
00568     {
00569       if (m_Index < m_pList->Size())
00570       {
00571         return m_pList->Get(m_Index);
00572       }
00573 
00574       throw Exception("Cannot dereference iterator: No more items in iterator.");
00575     }
00576     
00581     virtual const T* operator->() const
00582     {
00583       if (m_Index < m_pList->Size())
00584       {
00585         return &m_pList->Get(m_Index);
00586       }
00587       
00588       throw Exception("Cannot dereference iterator: No more items in iterator.");      
00589     }
00590     
00595     virtual const T& operator++()
00596     {
00597       Next();
00598       ConstListIterator iter = *this;
00599       return *iter;
00600     }
00601     
00606     virtual T operator++(int /*dummy*/)
00607     {
00608       return Next();
00609     }
00610     
00614     virtual const ConstListIterator& operator=(const ConstListIterator& rOther)
00615     {
00616       m_pList = rOther.m_pList;
00617       m_Index = rOther.m_Index;
00618       return *this;
00619     }
00620     
00624     virtual kt_bool operator!=(const ConstListIterator& rOther) const
00625     {
00626       if (m_pList != rOther.m_pList)
00627       {
00628         throw Exception("Iterators are not operating on the same list");
00629       }
00630       
00631       return m_Index != rOther.m_Index;
00632     }
00633     
00634   private:
00635     const List<T>* m_pList;
00636     kt_size_t m_Index;
00637   }; // class ConstIterator<T>
00638 
00642 
00646   template<class T>
00647   class ListIterator
00648   {
00649   public:
00654     ListIterator(List<T>* pList)
00655     : m_pList(pList)
00656     , m_Index(0)
00657     {
00658       if (pList == NULL)
00659       {
00660         throw Exception("Cannot create iterator: List is NULL");
00661       }
00662     }
00663     
00668     virtual kt_bool HasNext() const
00669     {
00670       return m_Index < m_pList->Size();
00671     }
00672     
00677     virtual T& Next()
00678     {
00679       if (m_Index < m_pList->Size())
00680       {
00681         m_Index++;
00682         return m_pList->Get(m_Index - 1);
00683       }
00684       
00685       throw Exception("Cannot increment iterator: No more items in iterator.");
00686     }
00687     
00691     void Erase()
00692     {
00693       if (m_Index < m_pList->Size())
00694       {
00695         m_pList->RemoveAt(m_Index);
00696       }
00697       
00698       throw Exception("Cannot erase item: No more items in iterator.");      
00699     }
00700     
00705     virtual T& operator*() const
00706     {
00707       if (m_Index < m_pList->Size())
00708       {
00709         return m_pList->Get(m_Index);
00710       }
00711       
00712       throw Exception("Cannot dereference iterator: No more items in iterator.");
00713     }
00714     
00719     virtual T* operator->() const
00720     {
00721       if (m_Index < m_pList->Size())
00722       {
00723         return &m_pList->Get(m_Index);
00724       }
00725       
00726       throw Exception("Cannot dereference iterator: No more items in iterator.");      
00727     }
00728     
00733     virtual const T& operator++()
00734     {
00735       Next();
00736       ListIterator iter = *this;
00737       return *iter;
00738     }
00739     
00744     virtual T operator++(int /*dummy*/)
00745     {
00746       return Next();
00747     }
00748     
00752     virtual const ListIterator& operator=(const ListIterator& rOther)
00753     {
00754       m_pList = rOther.m_pList;
00755       m_Index = rOther.m_Index;
00756       return *this;
00757     }
00758     
00762     virtual kt_bool operator!=(const ListIterator& rOther) const
00763     {
00764       if (m_pList != rOther.m_pList)
00765       {
00766         throw Exception("Iterators are not operating on the same list");
00767       }
00768       
00769       return m_Index != rOther.m_Index;
00770     }
00771     
00772   private:
00773     List<T>* m_pList;
00774     kt_size_t m_Index;
00775   }; // class Iterator<T>
00776 
00778 }
00779 
00780 #endif // __OpenKarto_List_h__


nav2d_karto
Author(s): Sebastian Kasperski
autogenerated on Sun Apr 2 2017 03:53:08