Index   Main   Namespaces   Classes   Hierarchy   Annotated   Files   Compound   Global   Pages  

SgSList.h

Go to the documentation of this file.
00001 //----------------------------------------------------------------------------
00002 /** @file SgSList.h
00003     Static list.
00004 */
00005 //----------------------------------------------------------------------------
00006 
00007 #ifndef SG_SLIST_H
00008 #define SG_SLIST_H
00009 
00010 #include <algorithm>
00011 
00012 //----------------------------------------------------------------------------
00013 
00014 /** Static list not using dynamic memory allocation.
00015     Elements need to have a default constructor.
00016     They should be value-types, not entity-types, because operations like
00017     Clear() do not call the destructor of the old elements immediately.
00018 */
00019 template<typename T, int SIZE>
00020 class SgSList
00021 {
00022 public:
00023     /** Const iterator */
00024     class Iterator
00025     {
00026     public:
00027         Iterator(const SgSList& list);
00028 
00029         const T& operator*() const;
00030 
00031         void operator++();
00032 
00033         operator bool() const;
00034 
00035     private:
00036         const T* m_end;
00037 
00038         const T* m_current;
00039     };
00040 
00041     /** Non-const iterator */
00042     class NonConstIterator
00043     {
00044     public:
00045         NonConstIterator(SgSList& list);
00046 
00047         T& operator*() const;
00048 
00049         void operator++();
00050 
00051         operator bool() const;
00052 
00053     private:
00054         const T* m_end;
00055 
00056         T* m_current;
00057     };
00058 
00059     SgSList();
00060 
00061     /** Construct list with one element. */
00062     explicit SgSList(const T& val);
00063 
00064     SgSList(const SgSList<T,SIZE>& list);
00065 
00066     SgSList& operator=(const SgSList& list);
00067 
00068     bool operator==(const SgSList& list) const;
00069 
00070     bool operator!=(const SgSList& list) const;
00071 
00072     T& operator[](int index);
00073 
00074     const T& operator[](int index) const;
00075 
00076     void Clear();
00077 
00078     bool Contains(const T& val) const;
00079 
00080     /** Remove first occurrence of a value.
00081         Like RemoveFirst, but more efficient and does not preserve
00082         order of remaining elements. The first occurrence of the value is
00083         replaced by the last element.
00084         @return false, if element was not found
00085     */
00086     bool Exclude(const T& val);
00087 
00088     /** PushBack value at the end of the list if it's not already in the
00089         list.
00090     */
00091     void Include(const T& val);
00092 
00093     /** Build intersection with other list.
00094         List may not contain duplicate entries.
00095     */
00096     SgSList Intersect(const SgSList<T,SIZE>& list) const;
00097 
00098     bool IsEmpty() const;
00099 
00100     T& Last();
00101 
00102     const T& Last() const;
00103 
00104     int Length() const;
00105 
00106     /** Remove the last element of the list.
00107         Does not return the last element for efficiency. To get the last
00108         element, use Last() before calling PopBack().
00109     */
00110     void PopBack();
00111 
00112     void PushBack(const T& val);
00113 
00114     /** Push back all elements of another list.
00115         Works with lists of different maximum sizes.
00116         Requires: Total resulting number of elements will fit into the target
00117         list.
00118     */
00119     template<int SIZE2>
00120     void PushBackList(const SgSList<T,SIZE2>& list);
00121 
00122     /** Remove first occurence of a value.
00123         Preserves order of remaining elements.
00124         @see Exclude
00125     */
00126     void RemoveFirst(const T& val);
00127 
00128     /** Resize list.
00129         If new length is greater than current length, then the elements
00130         at a place greater than the old length are not initialized, they are
00131         just the old elements at this place.
00132         This is necessary if elements are re-used for efficiency and will be
00133         initialized later.
00134     */
00135     void Resize(int length);
00136 
00137     bool SameElements(const SgSList& list) const;
00138 
00139     void SetTo(const T& val);
00140 
00141     void Sort();
00142 
00143 private:
00144     friend class Iterator;
00145     friend class NonConstIterator;
00146 
00147     int m_len;
00148 
00149     T m_array[SIZE];
00150 };
00151 
00152 //----------------------------------------------------------------------------
00153 
00154 template<typename T, int SIZE>
00155 inline SgSList<T,SIZE>::Iterator::Iterator(const SgSList& list)
00156     : m_end(list.m_array + list.Length()),
00157       m_current(list.m_array)
00158 {
00159 }
00160 
00161 template<typename T, int SIZE>
00162 inline const T& SgSList<T,SIZE>::Iterator::operator*() const
00163 {
00164     SG_ASSERT(*this);
00165     return *m_current;
00166 }
00167 
00168 template<typename T, int SIZE>
00169 inline void SgSList<T,SIZE>::Iterator::operator++()
00170 {
00171     ++m_current;
00172 }
00173 
00174 template<typename T, int SIZE>
00175 inline SgSList<T,SIZE>::Iterator::operator bool() const
00176 {
00177     return m_current < m_end;
00178 }
00179 
00180 template<typename T, int SIZE>
00181 inline SgSList<T,SIZE>::NonConstIterator::NonConstIterator(SgSList& list)
00182     : m_end(list.m_array + list.Length()),
00183       m_current(list.m_array)
00184 {
00185 }
00186 
00187 template<typename T, int SIZE>
00188 inline T& SgSList<T,SIZE>::NonConstIterator::operator*() const
00189 {
00190     SG_ASSERT(*this);
00191     return *m_current;
00192 }
00193 
00194 template<typename T, int SIZE>
00195 inline void SgSList<T,SIZE>::NonConstIterator::operator++()
00196 {
00197     ++m_current;
00198 }
00199 
00200 template<typename T, int SIZE>
00201 inline SgSList<T,SIZE>::NonConstIterator::operator bool() const
00202 {
00203     return m_current < m_end;
00204 }
00205 
00206 template<typename T, int SIZE>
00207 inline SgSList<T,SIZE>::SgSList()
00208     : m_len(0)
00209 {
00210 }
00211 
00212 template<typename T, int SIZE>
00213 inline SgSList<T,SIZE>::SgSList(const T& val)
00214 {
00215     SetTo(val);
00216     m_len = 1;
00217     m_array[0] = val;
00218 }
00219 
00220 template<typename T, int SIZE>
00221 inline SgSList<T,SIZE>::SgSList(const SgSList<T,SIZE>& list)
00222 {
00223     *this = list;
00224 }
00225 
00226 template<typename T, int SIZE>
00227 SgSList<T,SIZE>& SgSList<T,SIZE>::operator=(const SgSList& list)
00228 {
00229     m_len = list.m_len;
00230     T* p = m_array;
00231     const T* pp = list.m_array;
00232     for (int i = m_len; i--; ++p, ++pp)
00233         *p = *pp;
00234     return *this;
00235 }
00236 
00237 template<typename T, int SIZE>
00238 bool SgSList<T,SIZE>::operator==(const SgSList& list) const
00239 {
00240     if (m_len != list.m_len)
00241         return false;
00242     const T* p = m_array;
00243     const T* pp = list.m_array;
00244     for (int i = m_len; i--; ++p, ++pp)
00245         if (*p != *pp)
00246             return false;
00247     return true;
00248 }
00249 
00250 template<typename T, int SIZE>
00251 inline bool SgSList<T,SIZE>::operator!=(const SgSList& list) const
00252 {
00253     return ! this->operator==(list);
00254 }
00255 
00256 template<typename T, int SIZE>
00257 inline T& SgSList<T,SIZE>::operator[](int index)
00258 {
00259     SG_ASSERT(index >= 0);
00260     SG_ASSERT(index < m_len);
00261     return m_array[index];
00262 }
00263 
00264 template<typename T, int SIZE>
00265 inline const T& SgSList<T,SIZE>::operator[](int index) const
00266 {
00267     SG_ASSERT(index >= 0);
00268     SG_ASSERT(index < m_len);
00269     return m_array[index];
00270 }
00271 
00272 template<typename T, int SIZE>
00273 inline void SgSList<T,SIZE>::Clear()
00274 {
00275     m_len = 0;
00276 }
00277 
00278 template<typename T, int SIZE>
00279 bool SgSList<T,SIZE>::Contains(const T& val) const
00280 {
00281     int i;
00282     const T* t = m_array;
00283     for (i = m_len; i--; ++t)
00284         if (*t == val)
00285             return true;
00286     return false;
00287  }
00288 
00289 template<typename T, int SIZE>
00290 bool SgSList<T,SIZE>::Exclude(const T& val)
00291 {
00292     // Go backwards through list, because with game playing programs
00293     // it is more likely that a recently added element is removed first
00294     T* t = m_array + m_len - 1;
00295     for (int i = m_len; i--; --t)
00296         if (*t == val)
00297         {
00298             --m_len;
00299             if (m_len > 0)
00300                 *t = *(m_array + m_len);
00301             return true;
00302         }
00303     return false;
00304 }
00305 
00306 template<typename T, int SIZE>
00307 void SgSList<T,SIZE>::Include(const T& val)
00308 {
00309     if (! Contains(val))
00310         PushBack(val);
00311 }
00312 
00313 template<typename T, int SIZE>
00314 SgSList<T,SIZE> SgSList<T,SIZE>::Intersect(const SgSList<T,SIZE>& list)
00315     const
00316 {
00317     SgSList <T, SIZE> result;
00318     const T* t = m_array;
00319     for (int i = m_len; i--; ++t)
00320         if (list.Contains(*t))
00321         {
00322             SG_ASSERT(! result.Contains(*t));
00323             result.PushBack(*t);
00324         }
00325     return result;
00326 }
00327 
00328 template<typename T, int SIZE>
00329 inline bool SgSList<T,SIZE>::IsEmpty() const
00330 {
00331     return m_len == 0;
00332 }
00333 
00334 template<typename T, int SIZE>
00335 inline T& SgSList<T,SIZE>::Last()
00336 {
00337     SG_ASSERT(m_len > 0);
00338     return m_array[m_len - 1];
00339 }
00340 
00341 template<typename T, int SIZE>
00342 inline const T& SgSList<T,SIZE>::Last() const
00343 {
00344     SG_ASSERT(m_len > 0);
00345     return m_array[m_len - 1];
00346 }
00347 
00348 template<typename T, int SIZE>
00349 inline int SgSList<T,SIZE>::Length() const
00350 {
00351     return m_len;
00352 }
00353 
00354 template<typename T, int SIZE>
00355 inline void SgSList<T,SIZE>::PopBack()
00356 {
00357     SG_ASSERT(m_len > 0);
00358     --m_len;
00359 }
00360 
00361 template<typename T, int SIZE>
00362 inline void SgSList<T,SIZE>::PushBack(const T& val)
00363 {
00364     SG_ASSERT(m_len < SIZE);
00365     m_array[m_len++] = val;
00366 }
00367 
00368 template<typename T, int SIZE>
00369 template<int SIZE2>
00370 inline void SgSList<T,SIZE>::PushBackList(const SgSList<T,SIZE2>& list)
00371 {
00372     for (typename SgSList<T,SIZE2>::Iterator it(list); it; ++it)
00373         PushBack(*it);
00374 }
00375 
00376 template<typename T, int SIZE>
00377 void SgSList<T,SIZE>::RemoveFirst(const T& val)
00378 {
00379     int i;
00380     T* t = m_array;
00381     for (i = m_len; i--; ++t)
00382         if (*t == val)
00383         {
00384             for ( ; i--; ++t)
00385                 *t = *(t + 1);
00386             --m_len;
00387             break;
00388         }
00389 }
00390 
00391 template<typename T, int SIZE>
00392 inline void SgSList<T,SIZE>::Resize(int length)
00393 {
00394     SG_ASSERT(length >= 0);
00395     SG_ASSERT(length <= SIZE);
00396     m_len = length;
00397 }
00398 
00399 template<typename T, int SIZE>
00400 bool SgSList<T,SIZE>::SameElements(const SgSList& list) const
00401 {
00402     if (m_len != list.m_len)
00403         return false;
00404     const T* p = m_array;
00405     for (int i = m_len; i--; ++p)
00406         if (! list.Contains(*p))
00407             return false;
00408     return true;
00409 }
00410 
00411 template<typename T, int SIZE>
00412 inline void SgSList<T,SIZE>::SetTo(const T& val)
00413 {
00414     m_len = 1;
00415     m_array[0] = val;
00416 }
00417 
00418 template<typename T, int SIZE>
00419 inline void SgSList<T,SIZE>::Sort()
00420 {
00421     std::sort(m_array, m_array + m_len);
00422 }
00423 
00424 //----------------------------------------------------------------------------
00425 
00426 #endif // SG_SLIST_H


17 Jun 2010 Doxygen 1.4.7