nevrax.org : docs

00001 
00007 /* Copyright, 2000 Nevrax Ltd.
00008  *
00009  * This file is part of NEVRAX NEL.
00010  * NEVRAX NEL is free software; you can redistribute it and/or modify
00011  * it under the terms of the GNU General Public License as published by
00012  * the Free Software Foundation; either version 2, or (at your option)
00013  * any later version.
00014 
00015  * NEVRAX NEL is distributed in the hope that it will be useful, but
00016  * WITHOUT ANY WARRANTY; without even the implied warranty of
00017  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
00018  * General Public License for more details.
00019 
00020  * You should have received a copy of the GNU General Public License
00021  * along with NEVRAX NEL; see the file COPYING. If not, write to the
00022  * Free Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
00023  * MA 02111-1307, USA.
00024  */
00025 
00026 #ifndef NL_ORDERING_TABLE_H
00027 #define NL_ORDERING_TABLE_H
00028 
00029 #include "nel/misc/types_nl.h"
00030 #include "nel/misc/debug.h"
00031 #include <vector>
00032 
00033 namespace NL3D 
00034 {
00035 
00036 // ***************************************************************************
00043 template<class T> class COrderingTable
00044 {
00045 
00046 public:
00047 
00048         COrderingTable();
00049         ~COrderingTable();
00050 
00055         void init( uint32 nNbEntries );
00056 
00060         uint32 getSize();
00061 
00066         void reset(uint maxElementToInsert);
00067 
00074         void insert( uint32 nEntryPos, T *pValue );
00075 
00088         void begin();
00089 
00093         T* get();
00094 
00098         void next();
00099 
00100 // =================
00101 // =================
00102 // IMPLEMENTATION.
00103 // =================
00104 // =================
00105 private:
00106 
00107         struct CNode
00108         {
00109                 T *val;
00110                 CNode *next;
00111 
00112                 CNode()
00113                 { 
00114                         val = NULL;
00115                         next = NULL;
00116                 }
00117         };
00118 
00119         // a raw allocator of node.
00120         std::vector<CNode>      _Allocator;
00121         CNode                           *_CurAllocatedNode;
00122 
00123         uint32 _nNbElt;
00124         CNode* _Array;
00125         CNode* _SelNode;
00126 
00127 };
00128 
00129 // ***************************************************************************
00130 template<class T> COrderingTable<T>::COrderingTable()
00131 {
00132         _nNbElt = 0;
00133         _Array = NULL;
00134         _SelNode = NULL;
00135         _CurAllocatedNode= NULL;
00136 }
00137 
00138 // ***************************************************************************
00139 template<class T> COrderingTable<T>::~COrderingTable()
00140 {
00141         if( _Array != NULL )
00142                 delete [] _Array;
00143 }
00144 
00145 // ***************************************************************************
00146 template<class T> void COrderingTable<T>::init( uint32 nNbEntries )
00147 {
00148         if( _Array != NULL )
00149         {
00150                 reset(0);
00151                 delete [] _Array;
00152         }
00153         _nNbElt = nNbEntries;
00154         _Array = new CNode[_nNbElt];
00155         reset(0);
00156 }
00157 
00158 // ***************************************************************************
00159 template<class T> uint32 COrderingTable<T>::getSize()
00160 {
00161         return _nNbElt;
00162 }
00163 
00164 // ***************************************************************************
00165 template<class T> void COrderingTable<T>::reset(uint maxElementToInsert)
00166 {
00167         // reset allocation
00168         maxElementToInsert= max(1U, maxElementToInsert);
00169         _Allocator.resize(maxElementToInsert);
00170         _CurAllocatedNode= &_Allocator[0];
00171 
00172         // reset OT.
00173         for( uint32 i = 0; i < _nNbElt-1; ++i )
00174         {
00175                 _Array[i].val = NULL;
00176                 _Array[i].next = &_Array[i+1];
00177         }
00178         _Array[_nNbElt-1].val  = NULL;
00179         _Array[_nNbElt-1].next = NULL;
00180 }
00181 
00182 // ***************************************************************************
00183 template<class T> void COrderingTable<T>::insert( uint32 nEntryPos, T *pValue )
00184 {
00185 #ifdef NL_DEBUG
00186         // check not so many calls to insert()
00187         nlassert( !_Allocator.empty() && _CurAllocatedNode < (&_Allocator[0])+_Allocator.size() );
00188         // check good entry size
00189         nlassert( nEntryPos < _nNbElt );
00190 #endif
00191         // get the head list node
00192         CNode *headNode = &_Array[nEntryPos];
00193         // alocate a new node
00194         CNode *nextNode = _CurAllocatedNode++;
00195         // fill this new node with data of head node
00196         nextNode->val= headNode->val;
00197         nextNode->next= headNode->next;
00198         // and replace head node with new data: consequence is pValue is insert in front of the list
00199         headNode->val= pValue;
00200         headNode->next= nextNode;
00201         // NB: prec of headNode is still correclty linked to headNode.
00202 }
00203 
00204 // ***************************************************************************
00205 template<class T> void COrderingTable<T>::begin()
00206 {
00207         _SelNode = &_Array[0];
00208         if( _SelNode->val == NULL )
00209                 next();
00210 }
00211 
00212 // ***************************************************************************
00213 template<class T> T* COrderingTable<T>::get()
00214 {
00215         if( _SelNode != NULL )
00216                 return _SelNode->val;
00217         else
00218                 return NULL;
00219 }
00220 
00221 // ***************************************************************************
00222 template<class T> void COrderingTable<T>::next()
00223 {
00224         _SelNode = _SelNode->next;
00225         while( ( _SelNode != NULL )&&( _SelNode->val == NULL ) )
00226                 _SelNode = _SelNode->next;
00227 }
00228 
00229 } // NL3D
00230 
00231 
00232 #endif // NL_ORDERING_TABLE_H
00233 
00234 /* End of ordering_table.h */