Main Page | Modules | Namespace List | Class Hierarchy | Alphabetical List | Class List | Directories | File List | Namespace Members | Class Members | File Members | Related Pages

phLinkedList.cpp

Go to the documentation of this file.
00001 /* ---------------------------------------------------------------------------
00002     Phission : 
00003         Realtime Vision Processing System
00004     
00005     Copyright (C) 2003-2006 Philip D.S. Thoren (pthoren@cs.uml.edu)
00006     University of Massachusetts at Lowell,
00007     Laboratory for Artificial Intelligence and Robotics
00008     
00009     This file is part of Phission.
00010 
00011     Phission is free software; you can redistribute it and/or modify
00012     it under the terms of the GNU Lesser General Public License as published by
00013     the Free Software Foundation; either version 2 of the License, or
00014     (at your option) any later version.
00015 
00016     Phission is distributed in the hope that it will be useful,
00017     but WITHOUT ANY WARRANTY; without even the implied warranty of
00018     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00019     GNU Lesser General Public License for more details.
00020 
00021     You should have received a copy of the GNU Lesser General Public License
00022     along with Phission; if not, write to the Free Software
00023     Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
00024 
00025  ---------------------------------------------------------------------------*/
00026 #ifdef HAVE_CONFIG_H
00027     #include <phissionconfig.h>
00028 #endif
00029 
00030 #include <phStandard.h>
00031 
00032 #include <phObject.h>
00033 #include <phLinkedList.h>
00034 
00035 #include <phError.h>
00036 #include <phMemory.h>
00037 #include <phPrint.h>
00038 
00039 /* ---------------------------------------------------------------------- */
00040 /* phLinkedListNode                                                             */
00041 /* ---------------------------------------------------------------------- */
00042 phLinkedListNode::phLinkedListNode() : phObject()
00043 {
00044     /* phFUNCTION("phLinkedListNode::phLinkedListNode") */
00045 
00046     this->setName("phLinkedListNode");
00047     this->m_previous = this->m_next = NULL;
00048 }
00049 
00050 /* ---------------------------------------------------------------------- */
00051 phLinkedListNode::~phLinkedListNode()
00052 {
00053     /* phFUNCTION("phLinkedListNode::~phLinkedListNode") */
00054 
00055     this->m_next = this->m_previous = NULL;
00056 }
00057 
00058 /* ---------------------------------------------------------------------- */
00059 int phLinkedListNode::setNext ( phLinkedListNode *node )
00060 {
00061     /* phFUNCTION("phLinkedListNode::setNext") */
00062 
00063     this->m_next = node;
00064 
00065     return phSUCCESS;
00066 }
00067 
00068 /* ---------------------------------------------------------------------- */
00069 int phLinkedListNode::setPrevious ( phLinkedListNode *node )
00070 {
00071     /* phFUNCTION("phLinkedListNode::setPrevious") */
00072 
00073     this->m_previous = node;
00074 
00075     return phSUCCESS;
00076 }
00077 
00078 /* ---------------------------------------------------------------------- */
00079 phLinkedListNode *phLinkedListNode::getNext ( )
00080 {
00081     /* phFUNCTION("phLinkedListNode::getNext") */
00082 
00083     return this->m_next;
00084 }
00085 
00086 /* ---------------------------------------------------------------------- */
00087 phLinkedListNode *phLinkedListNode::getPrevious ( )
00088 {
00089     /* phFUNCTION("phLinkedListNode::getPrevious") */
00090     return this->m_previous;
00091 }
00092 
00093 
00094 /* ---------------------------------------------------------------------- */
00095 /* phLinkedList                                                                 */
00096 /* ---------------------------------------------------------------------- */
00097 phLinkedList::phLinkedList() : phObject()
00098 {
00099     phFUNCTION("phLinkedList::phLinkedList")
00100 
00101     this->setName("phLinkedList");
00102     
00103     this->m_totalNodes = 0;
00104     this->m_head = this->m_tail = NULL;
00105 }
00106 
00107 /* ---------------------------------------------------------------------- */
00108 phLinkedList::~phLinkedList()
00109 {
00110     phFUNCTION("phLinkedList::~phLinkedList")
00111 
00112     rc = this->empty();
00113     phPRINT_RC(rc,NULL,"this->empty()");
00114 }
00115 
00116 /* ---------------------------------------------------------------------- */
00117 uint32_t phLinkedList::length()
00118 {
00119     return this->getTotal();
00120 }
00121 
00122 /* ---------------------------------------------------------------------- */
00123 uint32_t phLinkedList::getTotal()
00124 {
00125     /* phFUNCTION("phLinkedList::getTotal") */
00126     return this->m_totalNodes;
00127 }
00128 
00129 /* ---------------------------------------------------------------------- */
00130 int phLinkedList::isEmpty()
00131 {
00132     /* phFUNCTION("phLinkedList::isEmpty") */
00133     return (this->m_totalNodes > 0) ? 0 : 1;
00134 }
00135 
00136 /* ---------------------------------------------------------------------- */
00137 /* insert - inserts a node into the list. The node must be allocated
00138  * before being passed. */
00139 /* ---------------------------------------------------------------------- */
00140 int phLinkedList::insert( phLinkedListNode *node, uint32_t index )
00141 {
00142     /* phFUNCTION("phLinkedList::insert") */
00143 
00144     phLinkedListNode *insert_after  = NULL;
00145     phLinkedListNode *insert_before = NULL;
00146     uint32_t i = 0;
00147 
00148     if (node == NULL) return phFAIL;
00149 
00150     /* head and tail should be NULL only at the same time */
00151     if ((this->m_head == NULL) && (this->m_tail == NULL))
00152     {
00153         this->m_tail = this->m_head = node;
00154         
00155         /* Adjust the total count of nodes in the list */
00156         this->m_totalNodes++;
00157     }
00158     else 
00159     {   
00160         if (index <= 0)
00161         {
00162             /* this should always happen if the previous if block 
00163              * isn't satisfied */
00164             if (this->m_head != NULL)
00165             {
00166                 insert_before = this->m_head;
00167                 
00168                 this->m_head = node;
00169             }
00170         }
00171         else if (index >= this->m_totalNodes)
00172         {
00173             /* this should always happen if the previous if block 
00174              * isn't satisfied */
00175             if (this->m_tail != NULL)
00176             {
00177                 insert_after = this->m_tail;
00178                 
00179                 this->m_tail = node;
00180             }
00181         }
00182         else if ((index < this->m_totalNodes) && (index > 0))
00183         {
00184             uint32_t temp_half = 0;
00185             
00186             /* Even */
00187             if ((this->m_totalNodes % 2) == 0)
00188             {
00189                 temp_half = this->m_totalNodes / 2;
00190             }
00191             /* Odd */
00192             else
00193             {
00194                 temp_half = (this->m_totalNodes + 1) / 2;
00195             }
00196             
00197             if (index > temp_half)
00198             {
00199                 insert_after  = this->m_tail;
00200                 insert_before = NULL;
00201        
00202                 for ( i = this->m_totalNodes; i > index; i-- )
00203                 {
00204                     insert_before = insert_after;
00205                     
00206                     if (insert_before != NULL)
00207                     {
00208                         insert_after = insert_before->getPrevious();
00209                     }
00210                     else
00211                     {
00212                         insert_after = NULL;
00213                     }
00214                 }
00215             }
00216             else
00217             {
00218                 insert_after  = NULL;
00219                 insert_before = this->m_head;
00220        
00221                 for ( i = 0; i < index; i++ )
00222                 {
00223                     insert_after = insert_before;
00224                     
00225                     if (insert_after != NULL)
00226                     {
00227                         /* Set the new "insert_before" to the 'next' ptr */
00228                         /* Don't need to unlock the previous "insert_before"
00229                          * because it's now the current "insert_after" */
00230                         insert_before = insert_after->getNext();
00231                     }
00232                     else
00233                     {
00234                         insert_before = NULL;
00235                     }
00236                 }
00237             }
00238         }
00239         
00240         node->setNext( insert_before );
00241         
00242         node->setPrevious( insert_after );
00243 
00244         if (insert_after != NULL)
00245         {
00246             insert_after->setNext( node );
00247         }
00248         else
00249         {
00250             this->m_head = node;
00251         }
00252 
00253         if (insert_before != NULL)
00254         {
00255             insert_before->setPrevious( node );
00256         }
00257         else
00258         {
00259             this->m_tail = node;
00260         }
00261     
00262         /* Adjust the total count of nodes in the list */
00263         this->m_totalNodes++;
00264     }
00265 
00266     return phSUCCESS;
00267 }
00268 
00269 /* ---------------------------------------------------------------------- */
00270 int phLinkedList::remove( phLinkedListNode *node )
00271 {
00272     /* phFUNCTION("phLinkedList::remove") */
00273 
00274     if (node == NULL) return phFAIL;
00275     if (this->m_totalNodes <= 0) return phFAIL;
00276 
00277     phLinkedListNode *prev = node->getPrevious();
00278     phLinkedListNode *next = node->getNext();
00279 
00280     /* if there is no previous and next node, this is the only node */
00281     if ((prev == NULL) && (next == NULL) &&
00282         (this->m_head == node) && (this->m_tail == node))
00283     {
00284         /* Adjust the list's first node to this node's next node */
00285         this->m_head = this->m_tail = NULL;
00286     }
00287     /* "Dequeue"/"Pop" */
00288     /* if there is no next pointer, this is the last node... */
00289     else if ((next == NULL) && (this->m_tail == node))
00290     {
00291         /*... there must be a previous node, otherwise the first if block  *
00292          * would have executed. So, Adjust the previous node               */
00293         prev->setNext(NULL);
00294 
00295         /* Adjust the list's last node to the removed node's previous */
00296         this->m_tail = prev;
00297     }
00298     /* "Shift" */
00299     /* If there is no previous pointer, this is the first node ... */
00300     else if ((prev == NULL) && (this->m_head == node))
00301     {
00302         /*... there must be a next node, otherwise the first "if block" *
00303          * would have executed. So, Adjust the first node:              */
00304         next->setPrevious( NULL );
00305 
00306         /* Adjust the list's first node to this node's next */
00307         this->m_head = next;
00308     }
00309     /* The node is in the middle somewhere, neither first nor last */
00310     else
00311     {
00312         /* Adjust the previous's next, then the next's previous */
00313         prev->setNext( next );
00314         next->setPrevious( prev );
00315     }
00316         
00317     /* Adjust the total count of nodes in the list */
00318     this->m_totalNodes--;    
00319 
00320     /* adjust the removed node's pointers */
00321     node->setNext( NULL );
00322     node->setPrevious( NULL );
00323 
00324     return phSUCCESS;
00325 }
00326 
00327 /* ---------------------------------------------------------------------- */
00328 /* empty: Delete all the nodes in the list */
00329 /* ---------------------------------------------------------------------- */
00330 int phLinkedList::empty()
00331 {
00332     /* phFUNCTION("phLinkedList::empty") */
00333 
00334     phLinkedListNode *node = NULL;
00335     phLinkedListNode *next = NULL;
00336 
00337     node = this->m_head;
00338 
00339     while (node != NULL)
00340     {
00341         next = node->getNext();
00342 
00343         phDelete(node);
00344 
00345         node = next;
00346     }
00347 
00348     this->m_head = this->m_tail = NULL;
00349     this->m_totalNodes = 0;
00350     
00351     return phSUCCESS;
00352 }
00353 
00354 /* ---------------------------------------------------------------------- */
00355 /* push: insert at the end of the list */
00356 /* ---------------------------------------------------------------------- */
00357 int phLinkedList::push( phLinkedListNode *node )
00358 {
00359     phFUNCTION("phLinkedList::push")
00360 
00361     if (node == NULL) return phFAIL;
00362 
00363     rc = this->insert( node, this->m_totalNodes );
00364     phCHECK_RC(rc,NULL,"this->insert");
00365     
00366     return phSUCCESS;
00367 error:
00368     return phFAIL;
00369 }
00370 
00371 /* ---------------------------------------------------------------------- */
00372 /* pop: remove from the end of the list */
00373 /* ---------------------------------------------------------------------- */
00374 phLinkedListNode *phLinkedList::pop( ) /* a.k.a. dequeue */
00375 {
00376     phFUNCTION("phLinkedList::pop")
00377 
00378     phLinkedListNode  *node   = NULL;
00379 
00380     node = this->m_tail;
00381 
00382     rc = this->remove( node );
00383     phCHECK_RC(rc,NULL,"this->remove(this->m_head)");
00384 
00385     return node;
00386 error:
00387     return NULL;
00388 }
00389 
00390 /* ---------------------------------------------------------------------- */
00391 /* enqueue: insert on the front of the list */
00392 /* ---------------------------------------------------------------------- */
00393 int phLinkedList::enqueue( phLinkedListNode *node ) /* a.k.a. unshift */
00394 {
00395     phFUNCTION("phLinkedList::enqueue")
00396 
00397     rc = this->insert( node, 0 );
00398     phCHECK_RC(rc,NULL,"this->insert( node, 0 )");
00399 
00400     return phSUCCESS;
00401 error:
00402     return phFAIL;
00403 }
00404 
00405 /* ---------------------------------------------------------------------- */
00406 /* dequeue: remove from the end of the list */
00407 /* ---------------------------------------------------------------------- */
00408 phLinkedListNode *phLinkedList::dequeue( ) /* a.k.a. pop */
00409 {
00410     phFUNCTION("phLinkedList::dequeue")
00411 
00412     phLinkedListNode  *node   = NULL;
00413 
00414     node = this->m_tail;
00415     
00416     rc = this->remove( node );
00417     phCHECK_RC(rc,NULL,"this->remove( this->m_tail )");
00418 
00419     return node;
00420 error:
00421     return NULL;
00422 }
00423 
00424 /* ---------------------------------------------------------------------- */
00425 /* shift: remove from the front of the list */
00426 /* ---------------------------------------------------------------------- */
00427 phLinkedListNode *phLinkedList::shift( )
00428 {
00429     phFUNCTION("phLinkedList::shift")
00430     
00431     phLinkedListNode  *node   = NULL;
00432 
00433     node = this->m_head;
00434 
00435     rc = this->remove( node );
00436     phCHECK_RC(rc,NULL,"this->remove(this->m_head)")
00437 
00438     return node;
00439 error:
00440     return NULL;
00441 }
00442 
00443 /* ---------------------------------------------------------------------- */
00444 /* unshift: insert on the front of the list */
00445 /* ---------------------------------------------------------------------- */
00446 int phLinkedList::unshift( phLinkedListNode *node ) /* a.k.a. enqueue */
00447 {
00448     phFUNCTION("phLinkedList::unshift")
00449 
00450     rc = this->insert( node, 0 );
00451     phCHECK_RC(rc,NULL,"this->insert( node, 0 )");
00452 
00453     return phSUCCESS;
00454 error:
00455     return phFAIL;
00456 }
00457 
00458 /* ---------------------------------------------------------------------- */
00459 phLinkedListNode *phLinkedList::removeTail() /* a.k.a. dequeue */
00460 {
00461     phFUNCTION("phLinkedList::removeTail")
00462 
00463     phLinkedListNode  *node   = NULL;
00464 
00465     node = this->m_tail;
00466     
00467     rc = this->remove( node );
00468     phCHECK_RC(rc,NULL,"this->remove( this->m_tail )");
00469 
00470     return node;
00471 error:
00472     return NULL;
00473 }
00474 
00475 /* ---------------------------------------------------------------------- */
00476 phLinkedListNode *phLinkedList::removeHead() /* a.k.a. shift */
00477 {
00478     phFUNCTION("phLinkedList::removeHead")
00479     
00480     phLinkedListNode  *node   = NULL;
00481 
00482     node = this->m_head;
00483 
00484     rc = this->remove( node );
00485     phCHECK_RC(rc,NULL,"this->remove(this->m_head)")
00486 
00487     return node;
00488 error:
00489     return NULL;
00490 }
00491 
00492 /* ---------------------------------------------------------------------- */
00493 const phLinkedListNode *phLinkedList::getHead()
00494 {
00495     /* phFUNCTION("phLinkedList::removeHead") */
00496     return this->m_head;
00497 }
00498 
00499 /* ---------------------------------------------------------------------- */
00500 const phLinkedListNode *phLinkedList::getTail()
00501 {
00502     /* phFUNCTION("phLinkedList::removeHead") */
00503     return this->m_tail;
00504 }
00505 




Copyright (C) 2002 - 2007 Philip D.S. Thoren ( pthoren@users.sourceforge.net )
University Of Massachusetts at Lowell
Robotics Lab
SourceForge.net Logo

Generated on Sat Jun 16 02:44:02 2007 for phission by  doxygen 1.4.4