iLinkedList.h
Go to the documentation of this file.
00001 /*
00002 imagen - Simple object-oriented imaging library
00003 Copyright (C) 2011-2012 Mark D. Procarione
00004 
00005 imagen is free software: you can redistribute it and/or
00006 modify it under the terms of the GNU Lesser General Public
00007 License as published by the Free Software Foundation, either
00008 version 3 of the License, or (at your option) any later version.
00009 
00010 imagen is distributed in the hope that it will be useful,
00011 but WITHOUT ANY WARRANTY; without even the implied warranty of
00012 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
00013 GNU General Public License for more details.
00014 */
00015 
00016 #ifndef __ILINKEDLIST_H__
00017 #define __ILINKEDLIST_H__
00018 
00019 #include <cstdio>
00020 
00021 namespace imagen
00022 {
00024         template <class dType> class iListNode
00025         {
00026                 public:
00027                         iListNode()
00028                         {
00029                                 // Warning! Undefined data. Only use this constructor for head!
00030                                 next = NULL;
00031                                 prev = NULL;
00032                         }
00033 
00034                         iListNode( const dType &nodeData )
00035                         {
00036                                 data = nodeData;
00037                                 next = NULL;
00038                                 prev = NULL;
00039                         }
00040 
00041                 public: // This should probably be private
00042                         dType data;
00043                         iListNode *next, *prev;
00044         };
00045 
00047 
00054         template <class dType> class iLinkedList
00055     {
00056                 typedef iListNode<dType> Node;
00057 
00058         public:
00060 
00061                         iLinkedList()
00062                         {
00063                                 head = new Node();
00064                                 tail = new Node();
00065                                 size = 0;
00066                         }
00067 
00069                         iLinkedList( const iLinkedList<dType> &list )
00070                         {
00071                 head = new Node();
00072                                 tail = new Node();
00073                                 size = 0;
00074 
00075                             *this = list;
00076                         }
00077 
00079                         ~iLinkedList()
00080                         {
00081                                 clear();
00082                                 delete head;
00083                                 delete tail;
00084                         }
00085 
00087 
00088                         void append( const dType &newData )
00089                         {
00090                                 Node *node = new Node(newData);
00091 
00092                                 if(head->next == NULL)
00093                                         head->next = node;
00094                                 if(tail->prev == NULL)
00095                                         tail->prev = node;
00096 
00097                                 node->next = tail;
00098                                 node->prev = tail->prev;
00099                                 node->prev->next = node;
00100                                 tail->prev = node;
00101 
00102                                 size++;
00103                         }
00104 
00106 
00107                         void prepend( const dType &newData )
00108                         {
00109                                 Node *node = new Node(newData);
00110 
00111                                 if(head->next == NULL)
00112                                         head->next = node;
00113                                 if(tail->prev == NULL)
00114                                         tail->prev = node;
00115 
00116                                 node->next = head->next;
00117                                 node->prev = head;
00118                                 node->next->prev = node;
00119                                 head->next = node;
00120 
00121                                 size++;
00122                         }
00123 
00125 
00127                         void insert( int i, const dType &newData )
00128                         {
00129                                 Node *node = new Node(newData);
00130                                 Node *after;
00131 
00132                                 if(i <= 0) prepend(newData);
00133                                 else if(i >= size-1) append(newData);
00134                                 else
00135                                 {
00136                                         after = _getNode(i);
00137 
00138                                         node->next = after;
00139                                         node->prev = after->prev;
00140                                         node->prev->next = node;
00141                                         after->prev = node;
00142 
00143                                         size++;
00144                                 }
00145                         }
00146 
00148                         void removeFirst()
00149                         {
00150                                 Node *tmp = head->next;
00151 
00152                                 head->next = head->next->next;
00153                                 head->next->prev = head;
00154 
00155                                 delete tmp;
00156 
00157                                 size--;
00158                         }
00159 
00161                         void removeLast()
00162                         {
00163                                 Node *tmp = tail->prev;
00164 
00165                                 tail->prev = tail->prev->prev;
00166                                 tail->prev->next = tail;
00167 
00168                                 delete tmp;
00169 
00170                                 size--;
00171                         }
00172 
00174 
00175                         void remove( int i )
00176                         {
00177                                 if(size == 0) return;
00178 
00179                                 if(i <= 0) removeFirst();
00180                                 else if(i >= size-1) removeLast();
00181                                 else
00182                                 {
00183                                         Node *node = _getNode(i);
00184 
00185                                         node->prev->next = node->next;
00186                                         node->next->prev = node->prev;
00187 
00188                                         delete node;
00189 
00190                                         size--;
00191                                 }
00192                         }
00193 
00195 
00197                         int removeAll( dType val )
00198                         {
00199                                 if(size == 0) return 0;
00200 
00201                                 Node *node = head->next;
00202                                 int num = 0;
00203                                 int count = 0;
00204 
00205                                 while(count < size)
00206                                 {
00207                                         if(node->data == val)
00208                                         {
00209                                                 Node *tmp = node;
00210                                                 node->prev->next = node->next;
00211                                                 node->next->prev = node->prev;
00212                                                 node = node->next;
00213                                                 delete tmp;
00214                                                 num++;
00215                                         }
00216                                         else
00217                                                 node = node->next;
00218 
00219                                         count++;
00220                                 }
00221 
00222                                 size-=num;
00223                                 return num;
00224                         }
00225 
00227 
00229                         void replace( int i, const dType &newData )
00230                         {
00231                                 _getNode(i)->data = newData;
00232                         }
00233 
00235 
00236                         dType &getFirst() { return head->next->data; }
00237 
00239 
00240                         const dType &getFirst() const { return head->next->data; }
00241 
00243 
00244                         dType &getLast() { return tail->prev->data; }
00245 
00247 
00248                         const dType &getLast() const { return tail->prev->data; }
00249 
00251 
00253                         dType &getItem( int i ) { return _getNode(i)->data; }
00254 
00256 
00257                         const dType &getItem( int i ) const { return _getNode(i)->data; }
00258 
00260 
00261                         dType takeFirst()
00262                         {
00263                                 dType data = getFirst();
00264                         removeFirst();
00265                         return data;
00266                         }
00267 
00269 
00270                         dType takeLast()
00271                         {
00272                                 dType data = getLast();
00273                         removeLast();
00274                         return data;
00275                         }
00276 
00278 
00280                         dType takeItem( int i )
00281                         {
00282                                 dType data = getItem(i);
00283                         remove(i);
00284                         return data;
00285                         }
00286 
00288 
00289                         void reverse()
00290                         {
00291                                 /*
00292                                 Node *result = NULL;
00293                                 Node *current = head->next;
00294                                 Node *next = NULL;
00295                                 int count = 0;
00296 
00297                                 while(count < size)
00298                                 {
00299                                         next = current->next;
00300                                         current->next = result;
00301                                         result = current;
00302                                         current = next;
00303                                 }
00304 
00305                                 head = result;
00306                                  */
00307                         }
00308 
00310 
00312                         int countAll( dType val )
00313                         {
00314                                 Node *node = head->next;
00315                                 int num = 0;
00316                                 int count = 0;
00317 
00318                                 while(count < size)
00319                                 {
00320                                         if(node->data == val)
00321                                                 num++;
00322 
00323                                         node = node->next;
00324                                         count++;
00325                                 }
00326 
00327                                 return num;
00328                         }
00329 
00331 
00332             int getSize() { return size; }
00333 
00335                         void clear()
00336                         {
00337                                 if(isEmpty()) return;
00338 
00339                                 //Node *tmp;
00340                                 Node *node = head->next;
00341                                 int count = 0;
00342 
00343                                 while(count < size)
00344                                 {
00345                                         Node *tmp = node;
00346                                         node = node->next;
00347                                         delete tmp;
00348                                         count++;
00349                                 }
00350 
00351                                 head->next = NULL;
00352                                 tail->prev = NULL;
00353 
00354                                 size = 0;
00355                         }
00356 
00358 
00360             bool isMember( const dType &val )
00361             {
00362                                 Node *node = head->next;
00363                                 int count = 0;
00364 
00365                                 while(count < size)
00366                                 {
00367                                         if(node->data == val)
00368                                                 return true;
00369 
00370                                         node = node->next;
00371                                         count++;
00372                                 }
00373                                 return false;
00374                         }
00375 
00377 
00378             bool isEmpty() { return !size; }
00379 
00381             iLinkedList<dType> &operator = ( const iLinkedList<dType> &l )
00382             {
00383                                 clear();
00384 
00385                 for(int i=0; i<l.size; i++)
00386                     append(l[i]);
00387 
00388                 return *this;
00389             }
00390 
00392             iLinkedList<dType> &operator += ( const iLinkedList<dType> &l )
00393             {
00394                 for(int i=0; i<l.size; i++)
00395                     append(l[i]);
00396 
00397                 return *this;
00398             }
00399 
00401 
00402             dType &operator[] ( int i ) { return getItem(i); }
00403 
00405 
00406             const dType &operator[] ( int i ) const { return getItem(i); }
00407 
00408         private:
00409                         iListNode<dType> *_getNode( int i )
00410                         {
00411                                 Node *current = head->next;
00412                                 int count = 0;
00413 
00414                                 if(i <= 0) return head->next;
00415                                 else if(i >= size-1) return tail->prev;
00416                                 //if(i < 0) i = 0;
00417                                 //else if(i > size-1) i = size-1;
00418 
00419                                 // Determines whether to work backward or forward.
00420                                 // This cuts search time by half.
00421                                 // More optimizations would be welcome.
00422                                 if(i < (size/2))
00423                                 {
00424                                         while(count < i)
00425                                         {
00426                                                 current = current->next;
00427                                                 count++;
00428                                         }
00429                                 }
00430                                 else if(i >= (size/2))
00431                                 {
00432                                         current = tail->prev;
00433                                         count = size-1;
00434 
00435                                         while(count > i)
00436                                         {
00437                                                 current = current->prev;
00438                                                 count--;
00439                                         }
00440                                 }
00441 
00442                                 return current;
00443                         }
00444 
00445             const iListNode<dType> *_getNode( int i ) const
00446                         {
00447                 Node *current = head->next;
00448                                 int count = 0;
00449 
00450                                 if(i <= 0) return head->next;
00451                                 else if(i >= size-1) return tail->prev;
00452                                 //if(i < 0) i = 0;
00453                                 //else if(i > size-1) i = size-1;
00454 
00455                                 // Determines whether to work backward or forward.
00456                                 // This cuts search time by half.
00457                                 // More optimizations would be welcome.
00458                                 if(i < (size/2))
00459                                 {
00460                                         while(count < i)
00461                                         {
00462                                                 current = current->next;
00463                                                 count++;
00464                                         }
00465                                 }
00466                                 else if(i >= (size/2))
00467                                 {
00468                                         current = tail->prev;
00469                                         count = size-1;
00470 
00471                                         while(count > i)
00472                                         {
00473                                                 current = current->prev;
00474                                                 count--;
00475                                         }
00476                                 }
00477 
00478                                 return current;
00479                         }
00480 
00481         private:
00482             iListNode<dType> *head;
00483             iListNode<dType> *tail;
00484             int size;
00485     };
00486 }
00487 
00488 #endif // __ILINKEDLIST_H__