nux-0.9.48
|
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