nux-0.9.46

NuxCore/DataStruct/NList.h

Go to the documentation of this file.
00001 /*
00002  * Copyright 2010 Inalogic® Inc.
00003  *
00004  * This program is free software: you can redistribute it and/or modify it
00005  * under the terms of the GNU Lesser General Public License, as
00006  * published by the  Free Software Foundation; either version 2.1 or 3.0
00007  * of the License.
00008  *
00009  * This program is distributed in the hope that it will be useful, but
00010  * WITHOUT ANY WARRANTY; without even the implied warranties of
00011  * MERCHANTABILITY, SATISFACTORY QUALITY or FITNESS FOR A PARTICULAR
00012  * PURPOSE.  See the applicable version of the GNU Lesser General Public
00013  * License for more details.
00014  *
00015  * You should have received a copy of both the GNU Lesser General Public
00016  * License along with this program. If not, see <http://www.gnu.org/licenses/>
00017  *
00018  * Authored by: Jay Taoko <jay.taoko_AT_gmail_DOT_com>
00019  *
00020  */
00021 
00022 
00023 #ifndef NLIST_H
00024 #define NLIST_H
00025 
00026 NAMESPACE_BEGIN
00027 
00028 // This list requires that element T has a and object of type NListNoDyn::Node
00029 // This list will not do any dynamic allocation for the Node.
00030 
00031 
00032 template<typename T>
00033 class NListNoDyn
00034 {
00035 public:
00036   class Node
00037   {
00038   public:
00039     Node()
00040     {
00041       Clear();
00042     }
00043 
00044     ~Node()
00045     {
00046       nuxAssert (!IsLinked() );
00047     }
00048 
00049     void Clear()
00050     {
00051       m_Next = m_Prev = 0;
00052     }
00053 
00054     bool IsLinked() const
00055     {
00056       return (m_Prev || m_Next);
00057     }
00058 
00059     T *m_Next;
00060     T *m_Prev;
00061   };
00062 
00063   NListNoDyn()
00064     :   m_Head (0)
00065     ,   m_Tail (0)
00066   {
00067   }
00068 
00069   T *m_Head;
00070   T *m_Tail;
00071 
00072   inline void PushFront (T &NewNode)
00073   {
00074     nuxAssert (!NewNode.m_Node.IsLinked() );
00075 
00076     if (Find (NewNode) )
00077       return;
00078 
00079     NewNode.m_Node.m_Prev = 0;
00080     NewNode.m_Node.m_Next = m_Head;
00081 
00082     if (m_Head)
00083     {
00084       m_Head->m_Node.m_Prev = &NewNode;
00085       m_Head = &NewNode;
00086     }
00087     else
00088     {
00089       m_Head = &NewNode;
00090       m_Tail = &NewNode;
00091     }
00092   }
00093 
00094   inline void PushBack (T &NewNode)
00095   {
00096     nuxAssert (!NewNode.m_Node.IsLinked() );
00097 
00098     if (Find (NewNode) )
00099       return;
00100 
00101     NewNode.m_Node.m_Prev = m_Tail;
00102     NewNode.m_Node.m_Next = 0;
00103 
00104     if (m_Tail)
00105     {
00106       m_Tail->m_Node.m_Next = &NewNode;
00107       m_Tail = &NewNode;
00108     }
00109     else
00110     {
00111       m_Head = &NewNode;
00112       m_Tail = &NewNode;
00113     }
00114   }
00115 
00116   inline T *PopFront()
00117   {
00118     T *poped = m_Head;
00119 
00120     if (m_Head)
00121     {
00122       m_Head = m_Head->m_Node.m_Next;
00123 
00124       if (m_Head)
00125         m_Head->m_Node.m_Prev = 0;
00126       else
00127         m_Tail = 0;
00128 
00129       poped->m_Node.Clear();
00130     }
00131 
00132     return poped;
00133   }
00134 
00135   inline T *PopBack()
00136   {
00137     T *poped = m_Tail;
00138 
00139     if (m_Tail)
00140     {
00141       m_Tail = m_Tail->m_Node.m_Prev;
00142 
00143       if (m_Tail)
00144         m_Tail->m_Node.m_Next = 0;
00145       else
00146         m_Head = 0;
00147 
00148       poped->m_Node.Clear();
00149     }
00150 
00151     return poped;
00152   }
00153 
00154   inline bool Find (const T &ToFind)
00155   {
00156     T *pIndex = m_Head;
00157 
00158     while (pIndex && (pIndex != &ToFind) )
00159       pIndex = pIndex->m_Node.m_Next;
00160 
00161     return (pIndex != 0);
00162   }
00163 
00164   inline void Remove (T &OldNode)
00165   {
00166     if (!Find (OldNode) )
00167       return;
00168 
00169     // If OldNode have a previous node, her next pointer must point to OldNode next pointer.
00170     // Else, OldNode is the Head, and her next pointer must be the new Head.
00171     if (OldNode.m_Node.m_Prev)
00172       OldNode.m_Node.m_Prev->m_Node.m_Next = OldNode.m_Node.m_Next;
00173     else
00174     {
00175       m_Head = OldNode.m_Node.m_Next;
00176 
00177       if (m_Head)
00178         m_Head->m_Node.m_Prev = 0;
00179       else
00180         m_Tail = 0;
00181     }
00182 
00183     // If, OldNode have a next node, her previous pointer must point to OldNode previous pointer.
00184     // Else, OldNode is the Tail, and her previous pointer must be the new Tail.
00185     if (OldNode.m_Node.m_Next)
00186       OldNode.m_Node.m_Next->m_Node.m_Prev = OldNode.m_Node.m_Prev;
00187     else
00188     {
00189       m_Tail = OldNode.m_Node.m_Prev;
00190 
00191       if (m_Tail)
00192         m_Tail->m_Node.m_Next = 0;
00193       else
00194         m_Head = 0;
00195     }
00196 
00197     OldNode.m_Node.Clear();
00198   }
00199 
00200   inline void Clear (void)
00201   {
00202     while (PopFront() )
00203     {
00204 
00205     }
00206   }
00207 
00208   inline unsigned Size (void) const
00209   {
00210     unsigned int Result = 0;
00211     T  *pIndex = m_Head;
00212 
00213     while (pIndex)
00214     {
00215       pIndex = pIndex->m_Node.m_Next;
00216       ++Result;
00217     }
00218 
00219     return Result;
00220   }
00221 
00222   inline bool IsEmpty() const
00223   {
00224     return (m_Head == 0);
00225   }
00226 
00227   T *Front (void) const
00228   {
00229     return m_Head;
00230   }
00231   T *Back (void) const
00232   {
00233     return m_Tail;
00234   }
00235 
00237 
00240   class DIterator
00241   {
00242   public:
00243 
00244     NListNoDyn *m_pList;
00245     T *m_pIndex;
00247     inline DIterator (NListNoDyn &List)
00248     {
00249       m_pList = &List;
00250       Begin();
00251     }
00252 
00253     inline DIterator  &operator -- ()
00254     {
00255       nuxAssert (m_pIndex);
00256       m_pIndex = m_pIndex->m_Node.m_pPrev;
00257       return *this;
00258     }
00259 
00260     inline DIterator   operator -- (int)
00261     {
00262       nuxAssert (m_pIndex);
00263       DIterator Backup (*this);
00264       --*this;
00265       return Backup;
00266     }
00267 
00268     inline DIterator  &operator -= (int cnt)
00269     {
00270       nuxAssert (m_pIndex);
00271 
00272       if (cnt < 0)
00273         cnt = -cnt;
00274 
00275       while (cnt && m_pIndex)
00276       {
00277         m_pIndex = m_pIndex->m_Node.m_pPrev;
00278         cnt--;
00279       }
00280 
00281       return *this;
00282     }
00283 
00284     inline DIterator &operator ++ ()
00285     {
00286       nuxAssert (this->m_pIndex);
00287       this->m_pIndex = this->m_pIndex->m_Node.m_Next;
00288       return *this;
00289     }
00290 
00291     inline DIterator operator ++ (int)
00292     {
00293       nuxAssert (m_pIndex);
00294       DIterator Backup (*this);
00295       ++*this;
00296       return Backup;
00297     }
00298 
00299     inline DIterator &operator += (int cnt)
00300     {
00301       nuxAssert (m_pIndex);
00302 
00303       if (cnt < 0)
00304         cnt = -cnt;
00305 
00306       while (cnt && m_pIndex)
00307       {
00308         m_pIndex = m_pIndex->m_Node.m_Next;
00309         cnt--;
00310       }
00311 
00312       return *this;
00313     }
00314 
00315     inline bool operator == (const DIterator &Other) const
00316     {
00317       return m_pIndex == Other.m_pIndex;
00318     }
00319 
00320     inline bool FindForward (const T &ToFind)
00321     {
00322       while (!Empty() && (m_pIndex != &ToFind) )
00323       {
00324         ++ (*this);
00325       }
00326 
00327       return (!Empty() );
00328     }
00329 
00330     inline bool FindReverse (const T &ToFind)
00331     {
00332       while (!Empty() && (m_pIndex != &ToFind) )
00333       {
00334         -- (*this);
00335       }
00336 
00337       return (!Empty() );
00338     }
00339 
00341 
00346     T *RemoveCurrent (void)
00347     {
00348       nuxAssert (m_pIndex);
00349       T *pTmp = m_pIndex;
00350       ++ (*this);
00351       ( (NListNoDyn *) m_pList)->Remove (*pTmp);
00352       return (pTmp);
00353     }
00354 
00355     inline void Begin (void)
00356     {
00357       m_pIndex = m_pList->Front();
00358     }
00359 
00360     inline void End (void)
00361     {
00362       m_pIndex = m_pList->Back();
00363     }
00364 
00365     inline bool Empty (void) const
00366     {
00367       return (m_pIndex == 0);
00368     }
00369 
00370     inline T *operator* (void) const
00371     {
00372       return m_pIndex;
00373     }
00374 
00375     inline T *Current (void) const
00376     {
00377       return m_pIndex;
00378     }
00379 
00380   }; // class DIterator
00381 };
00382 
00383 NAMESPACE_END
00384 
00385 #define INL_NLISTNODYN_NODE(T) NListNoDyn<T>::Node m_Node;
00386 
00387 #endif // NLIST_H