Main Page   Packages   Namespace List   Class Hierarchy   Alphabetical List   Compound List   File List   Compound Members   File Members   Search  

C:/temp/src/j2k/DataType/Link/DList.cpp

Go to the documentation of this file.
00001 // DList.cpp - Class interface for a Doubly-Linked list node with freelist 
00002 
00003 #ifndef __J2K__DList_CPP__
00004 #define __J2K__DList_CPP__
00005 
00006 #include <j2k/DataType/Link/DList.hpp>
00007 
00008 inline DList::DList()           // Default Constructor
00009   : nbElements( 0 ), pos( 0 )   // No Element in the list yet !
00010 {
00011   head = new DLink();           // Create an empty header Link 
00012                                 // where prev and next are NULL
00013   curr = tail = head;           // Share the same empty Link
00014 
00015   assert( head != NULL );
00016   assert( curr != NULL );
00017   assert( tail != NULL );
00018 }
00019 
00020 DList::~DList() {               // Destructor
00021   while(head != NULL) {         // Return Link nodes to free shared memory
00022     curr = head;                // Set the current ptr to the head ptr.
00023     head = head->next;          // The current head ptr now points to 
00024     delete curr;                // the next elem which become the new head,
00025     nbElements--;               // so the current head ptr can be deleted.
00026   }
00027 }
00028 
00029 void DList::clear()             // Remove all Elements from list except Head!
00030 { 
00031   while (head->next != NULL)    // Return Link nodes to free memory
00032   {
00033     curr       = head->next;    // Current ptr points to next header element
00034     head->next = curr->next;    // Next head elem is the next current element
00035     delete curr;                // Delete the current element
00036     nbElements--;               
00037   }   
00038   curr = tail = head;           // The head, tail and current is the samething
00039   pos = 0;
00040 }
00041 
00042 inline void DList::setFirst()   // Set current to the first position
00043 {
00044   if ( head->next != NULL )  
00045   {
00046     curr = head;
00047     pos = 1;
00048   } 
00049   else 
00050   { 
00051     curr = head;
00052     pos = 0;
00053   }
00054 }
00055 
00056 inline void DList::prev()       // Move current to previous position
00057 {
00058   if (curr != NULL) 
00059   {
00060     curr = curr->prev;          // Current ptr is now the previous position ptr
00061     pos--;
00062   } 
00063   else 
00064   {
00065     curr = head;
00066     pos  = 0;
00067   }
00068 }
00069 
00070 inline void DList::next()       // Move current to the next position
00071 {
00072   if ( curr != NULL )           // if current is known.
00073   {
00074     if ( curr->next == NULL )  
00075     {
00076       curr = tail;
00077       pos = nbElements;
00078     } 
00079     else 
00080     { 
00081       curr = curr->next;        // Current ptr is now the next position ptr
00082       pos = 0;
00083     }
00084   }
00085 }
00086 
00087 inline long DList::size() 
00088 {
00089   return nbElements;
00090 }
00091 
00092 ULONG DList::length()           // Return current length of list
00093 {
00094   ULONG cnt = 0;
00095   for(DLink* temp = head->next; // Create a temp which next head ptr.
00096       temp != NULL;             // Until tail i.e. NULL
00097       temp = temp->next )       // Move the the next Link ptr.
00098   {
00099      cnt++;                     // Count the number of elements available
00100   }
00101 
00102   nbElements = cnt;
00103   return cnt;                   // which are not NULL.
00104 }
00105 
00106 void DList::setPos( ULONG pos )         // Set current to a specific position
00107 {
00108   curr = head;                          // The header is position 0
00109   pos = 0;                                    
00110   for( register ULONG i = 0;
00111        (curr != NULL) && (i < pos);     // Move to position 1, 2, ... , pos.
00112        i++ )  
00113   {
00114     curr = curr->next;
00115     pos++;
00116   }
00117 }
00118 
00119 void DList::setValue(Elem val)     // Set current element's value
00120 {
00121   if ( curr != NULL  &&  curr != head  &&  nbElements > 0 )  
00122   {
00123     curr->element = val;
00124   }
00125 }
00126 
00127 inline Elem DList::currValue() 
00128 {
00129   return getValue();
00130 }
00131 
00132 Elem DList::getValue() 
00133 { 
00134   if ( curr != NULL  &&  curr != head  &&  nbElements > 0 ) 
00135   {
00136     return curr->element;    // Return value of the current element
00137   }
00138 
00139   return ZERO;
00140 }
00141 
00142 inline BOOL DList::isEmpty() const         // Return TRUE if list is empty
00143 {
00144   return ( head->next == NULL );
00145 }
00146 
00147 inline BOOL DList::isInList() const        // TRUE if current is in the list
00148 {
00149   return ( curr != NULL );
00150 }
00151 
00152 void DList::insert( Elem item ) 
00153 {
00154   if ( curr == NULL  ||  curr->prev == NULL ) 
00155   {
00156     curr = head;
00157     pos = 0;
00158     append( item );
00159     return;
00160   }
00161 
00162   // Create the new DLink(Elem Element, DLink* nextp, DLink* prevp)
00163 
00164   curr->next = new DLink( item, curr->next, curr ); 
00165 
00166   if ( curr->next->next != NULL )         // New element is not the tail ?
00167   {           
00168      curr->next->next->prev = curr->next; // Set the old curr->next DLink
00169   }                                       // Backward ptr to the new DLink.
00170 
00171   if ( tail == curr ) 
00172   {
00173     tail = curr->next;
00174   }
00175 
00176   curr = curr->next;                      // New element is now the current.
00177   nbElements++;
00178 }
00179 
00180 // Append an Element at the tail of the list
00181 void DList::append( Elem item ) 
00182 {
00183   if ( tail == NULL ) 
00184   {
00185     tail = curr = head;
00186   }
00187 
00188   // Create the new tail DLink(Elem Element, DLink* nextp, DLink* prevp)
00189   tail->next = new DLink( item, NULL, tail );
00190   tail = tail->next;     
00191   curr = tail;
00192 
00193   nbElements++;
00194   pos++;
00195 }
00196 
00197 inline void DList::enqueue( Elem item )
00198 {
00199   append( item );
00200 }
00201 
00202 inline Elem DList::dequeue()                 // Dequeue Elem from head
00203 {
00204   assert( head != NULL );
00205   curr = head->next;
00206   if ( curr == NULL ) return ZERO;
00207   return remove();
00208 }
00209 
00210 
00211 Elem DList::remove()          // Remove the current element from the list
00212 {
00213   assert( curr != NULL );     // Must be a valid position in the list
00214   if ( curr == head ) 
00215   {
00216     curr = head->next;
00217   }
00218 
00219   assert( nbElements > 0 );   // Is it the head ?
00220 
00221   Elem   temp      = curr->element; // Save the removed element's data
00222   DLink* newCurr   = curr->prev;    // Save the new current position
00223 
00224   curr->prev->next = curr->next;    // Set prev elem forward ptr to next elem
00225 
00226   if ( curr->next == NULL )         // Is it the tail ?
00227   { 
00228     tail == curr->prev;             // Previous element is now the tail
00229   } 
00230   else 
00231   {
00232     curr->next->prev = curr->prev; // Set next elem backward ptr to prev elem
00233   }   
00234 
00235   delete curr;                 // Delete the current removed Link
00236   curr = newCurr;              // Moving backward, in case we are at the tail
00237   nbElements--;                // We just erase an element, so substract it.
00238   pos--;
00239   return temp;                 // Send the old current data to user
00240 }
00241 
00242 inline long DList::getPos() 
00243 {
00244   return pos;
00245 }
00246 
00247 void DList::display() 
00248 {
00249   if ( nbElements < 1 )  
00250   {
00251     printf( "Empty List\n" );
00252     return;   // Empty List
00253   }
00254  
00255   DLink* temp = curr;
00256 
00257   setFirst();
00258 
00259   printf( "\n===========================================\n" );
00260 
00261   while ( curr != NULL )             // Stop if we reach the end
00262   {
00263     printf( "%d) ", pos );
00264     printf( "%d\t", curr->element );
00265     printf( "%s\t", curr->element->pkt+4 );
00266     printf( "[%u]\t", curr->element->pktLength );
00267 
00268     if ( curr->prev == NULL ) 
00269     {
00270       printf( "NULL \t" );
00271     } 
00272     else 
00273     {
00274       printf( "%d\t", curr->prev->element );
00275     }
00276 
00277     if ( curr->next == NULL ) 
00278     {
00279       printf( "NULL \n" );
00280     } 
00281     else 
00282     {
00283       printf( "%d\n", curr->next->element );
00284     }
00285 
00286     curr = curr->next;
00287     pos++;
00288   }
00289 
00290   printf( "\n===========================================\n" );
00291   fflush( stdout );
00292   curr = temp;
00293 }
00294 
00295 long DList::find( Elem val )         // Search Something in the DList
00296 {
00297   if ( curr == NULL ) 
00298   { 
00299     curr = head;
00300     pos = 0;
00301   }
00302 
00303   if ( nbElements < 1 ) 
00304   {
00305      printf( "Can't search inside an empty list\n" );    
00306      return -50;
00307   }
00308 
00309   if ( curr == head ) 
00310   {
00311     curr = head->next;               // We start at the next header element
00312     pos = 1;
00313   }
00314 
00315   register ULONG i = 0;
00316   DLink* temp = curr;
00317 
00318   for( ; curr != NULL; i++, pos++ )             // Stop if we reach the tail
00319   {
00320     if ( curr->element == ZERO )   // Valid data inside !?
00321     {
00322       exit( 1 );
00323       printf( "Search process aborted, since current element's data are not defined.\n" );   
00324       curr = temp;
00325       return -100 - i;
00326     }
00327    
00328     if ( curr->element == val ) 
00329     {
00330       return pos;                    // Found it
00331     } 
00332     else 
00333     {
00334       curr = curr->next;
00335     }
00336   }
00337 
00338   curr = temp;
00339   return -1;                         // Not found
00340 }
00341 
00342 
00343 // Search an ID value within the list
00344 long DList::findID( ULONG ID ) 
00345 {
00346   if ( curr == NULL ) 
00347   { 
00348     curr = head;
00349     pos = 0;
00350   }
00351 
00352   if ( nbElements < 1 ) 
00353   {
00354     // printf( "Can't search inside an empty list\n" );    
00355     return -50;
00356   }
00357 
00358   if ( curr == head ) 
00359   {
00360     curr = head->next;          // We start at the next header element
00361     pos = 1;
00362   }
00363 
00364   register ULONG i = 0;
00365   DLink* temp = curr;
00366 
00367   for( ; curr != NULL; i++, pos++ )       // Stop if we reach the tail
00368   {
00369     if ( curr->element == ZERO )          // Valid data inside !?
00370     {
00371       exit( 1 );
00372       printf( "Search process aborted, since current element's data are not defined.\n" );   
00373       curr = temp;
00374       return -100 - i;
00375     }
00376    
00377     if ( curr->element->getID() == ID ) 
00378     {
00379       return pos;                    // Found it
00380     } 
00381     else 
00382     {
00383       curr = curr->next;
00384     }
00385   }
00386 
00387   curr = temp;
00388   return -1;                         // Not found
00389 }
00390 
00391 // Search an ID value within the list
00392 long DList::findTimeStamp( double stamp ) 
00393 {
00394   if ( curr == NULL ) 
00395   { 
00396       setFirst();
00397   }
00398 
00399   
00400   if ( nbElements < 1 ) 
00401   {
00402     // printf( "Can't search inside an empty list\n" );    
00403     return -50;
00404   }
00405 
00406   if ( curr == head ) 
00407   {
00408       setFirst();
00409   }
00410 
00411   register ULONG i = 0;
00412   DLink* temp = curr;
00413 
00414   for( ; curr != NULL; i++, pos++ )       // Stop if we reach the tail
00415   {
00416     if ( curr->element == ZERO )          // Valid data inside !?
00417     {
00418       exit( 1 );
00419       printf( "Search process aborted, since current element's data are not defined.\n" );   
00420       curr = temp;
00421       return -100 - i;
00422     }
00423    
00424     if ( curr->element->getTimeStamp() <= stamp ) 
00425     {
00426       printf("Found at %d\n",pos);
00427       fflush(stdout);
00428       return pos;                    // Found it
00429     } 
00430     else 
00431     {
00432       curr = curr->next;
00433     }
00434   }
00435 
00436   curr = temp;
00437   return -1;                         // Not found
00438 }
00439 
00440 #endif // End of DList.cpp

Generated on Sun Oct 14 18:46:17 2001 for Standard J2K Library by doxygen1.2.11.1 written by Dimitri van Heesch, © 1997-2001