LinkedList.h

00001 /**
00002  * @file    LinkedList.h
00003  * @brief   Core Utility - Templated Linked List class
00004  * @author  sam grove
00005  * @version 1.0
00006  * @see     
00007  *
00008  * Copyright (c) 2013
00009  *
00010  * Licensed under the Apache License, Version 2.0 (the "License");
00011  * you may not use this file except in compliance with the License.
00012  * You may obtain a copy of the License at
00013  *
00014  *     http://www.apache.org/licenses/LICENSE-2.0
00015  *
00016  * Unless required by applicable law or agreed to in writing, software
00017  * distributed under the License is distributed on an "AS IS" BASIS,
00018  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
00019  * See the License for the specific language governing permissions and
00020  * limitations under the License.
00021  */
00022 
00023 #ifndef LINKEDLIST_H_
00024 #define LINKEDLIST_H_
00025 
00026 #include <stdint.h>
00027 #include "mbed.h"
00028 
00029 #define DBG_LLIST 0
00030 
00031 #if DBG_LLIST
00032 // #define DBG(...) do{debug("[%s:%d]", __PRETTY_FUNCTION__,__LINE__);debug(__VA_ARGS__);} while(0);
00033 #define DBG(...) do{debug("[DBG ][ll  ]");debug(__VA_ARGS__);} while(0);
00034 #else
00035 #define DBG(...) while(0);
00036 #endif
00037 
00038 /**
00039  *  @struct node
00040  *  @brief The Linked List structure
00041  */ 
00042 template<typename T>
00043 struct node
00044 {
00045     T           *data ;         /*!< pointer to list member data */
00046     struct node *next ;  /*!< pointer to the next list member */
00047 };
00048 
00049 ///** Returns true if data1 shall be inserted before data 2.
00050 //*/
00051 //typedef bool insertAtFunc(void *data1, void *data2);
00052 
00053 /** Example using the LinkedList Class
00054  * @code
00055  *  #include "mbed.h"
00056  *  #include "LinkedList.h"
00057  *  
00058  *  LinkedList<node>list;
00059  *  
00060  *  int main()
00061  *  {
00062  *      node *tmp;
00063  *      
00064  *      list.push((char *)"Two\n");
00065  *      list.append((char *)"Three\n");
00066  *      list.append((char *)"Four\n");
00067  *      list.push((char*)"One\n");
00068  *      list.append((char*)"Five\n");
00069  *      
00070  *      for(int i=1; i<=list.length(); i++)
00071  *      {
00072  *          tmp = list.pop(i);
00073  *          printf("%s", (char *)tmp->data);
00074  *      }
00075  *      
00076  *      error("done\n");
00077  *  }
00078  * @endcode
00079  */
00080  
00081  /** Example using new insertOrdered function:
00082  * @code
00083  
00084 #include "mbed.h"
00085 #include "LinkedList.h"
00086 
00087 void printList(LinkedList<node> &list, const char* msg) 
00088 {
00089     printf("%s: ", msg);
00090     for(int i=1; i<=list.length(); i++)
00091     {
00092         node *tmp = list.pop(i);
00093         printf("%d ", *(int*)tmp->data);
00094     }
00095     printf("\n");
00096 }
00097 
00098 bool ascending(int *n1, int *n2)
00099 {
00100     int *d1 = (int*)n1;
00101     int *d2 = (int*)n2;
00102     bool rv = *d1 <= *d2;
00103     printf("(%d %d:%d)", *d1, *d2, rv);
00104     return rv;
00105 }
00106 
00107 void testAscending()
00108 {
00109     node<int> *tmp;
00110     
00111     int n0 = 0;
00112     int n1 = 1;
00113     int n1B = 1;
00114     int n2 = 2;
00115     int n3 = 3;
00116     int n4 = 4;
00117     
00118     LinkedList<int>list;
00119     
00120     tmp = list.insertOrdered(&n2, ascending);
00121     if (NULL == tmp) {
00122         error("insertOrdered did not insert a node");
00123     }
00124     printList(list, "exp 2");
00125     
00126     tmp = list.insertOrdered(&n1, ascending);
00127     if (NULL == tmp) {
00128         error("insertOrdered did not insert a node");
00129     }
00130     printList(list, "exp 1,2");
00131 
00132     tmp = list.insertOrdered(&n4, ascending);
00133     if (NULL == tmp) {
00134         error("insertOrdered did not insert a node");
00135     }
00136     printList(list, "exp 1,2,4");
00137 
00138     tmp = list.insertOrdered(&n3, ascending);
00139     if (NULL == tmp) {
00140         error("insertOrdered did not insert a node");
00141     }
00142     printList(list, "exp 1,2,3,4");
00143 
00144     tmp = list.insertOrdered(&n0, ascending);
00145     if (NULL == tmp) {
00146         error("insertOrdered did not insert a node");
00147     }
00148     printList(list, "exp 0,1,2,3,4");
00149 
00150     tmp = list.insertOrdered(&n1B, ascending);
00151     if (NULL == tmp) {
00152         error("insertOrdered did not insert a node");
00153     }
00154     printList(list, "exp 0,1,1,2,3,4");
00155     
00156     tmp = list.pop(2);
00157     if (tmp->data != &n1) {
00158         error("pos 2 is not n1\n");
00159     }
00160     printf("n1 is good\n");
00161     
00162     tmp = list.pop(3);
00163     if (tmp->data != &n1B) {
00164         error("pos3 is not n1B");
00165     }
00166     printf("n1B is good\n");
00167 }
00168 
00169 bool descending(int *n1, int *n2)
00170 {
00171     int *d1 = (int*)n1;
00172     int *d2 = (int*)n2;
00173     bool rv = *d1 <= *d2;
00174     printf("(%d %d:%d)", *d1, *d2, rv);
00175     return rv;
00176 }
00177 
00178 void testDescending()
00179 {
00180     node<int> *tmp;
00181     
00182     int n0 = 0;
00183     int n1 = 1;
00184     int n1B = 1;
00185     int n2 = 2;
00186     int n3 = 3;
00187     int n4 = 4;
00188     
00189     LinkedList<int>l;
00190     
00191     tmp = l.insertOrdered(&n2, descending);
00192     if (NULL == tmp) {
00193         error("insertOrdered did not insert a node");
00194     }
00195     printList(l, "exp 2");
00196     
00197     tmp = l.insertOrdered(&n1, descending);
00198     if (NULL == tmp) {
00199         error("insertOrdered did not insert a node");
00200     }
00201     printList(l, "exp 2,1");
00202 
00203     tmp = l.insertOrdered(&n4, descending);
00204     if (NULL == tmp) {
00205         error("insertOrdered did not insert a node");
00206     }
00207     printList(l, "exp 4,2,1");
00208 
00209     tmp = l.insertOrdered(&n3, descending);
00210     if (NULL == tmp) {
00211         error("insertOrdered did not insert a node");
00212     }
00213     printList(l, "exp 4,3,2,1");
00214 
00215     tmp = l.insertOrdered(&n0, descending);
00216     if (NULL == tmp) {
00217         error("insertOrdered did not insert a node");
00218     }
00219     printList(l, "exp 4,3,2,1,0");
00220 
00221     tmp = l.insertOrdered(&n1B, descending);
00222     if (NULL == tmp) {
00223         error("insertOrdered did not insert a node");
00224     }
00225     printList(l, "exp 4,3,2,1,1,0");
00226     
00227     tmp = l.pop(4);
00228     if (tmp->data != &n1) {
00229         error("pos 2 is not n1\n");
00230     }
00231     printf("n1 is good\n");
00232     
00233     tmp = l.pop(5);
00234     if (tmp->data != &n1B) {
00235         error("pos3 is not n1B");
00236     }
00237     printf("n1B is good\n");
00238 }
00239 
00240 
00241 int main()
00242 {
00243     printf("\nJob Scheduler Demo\n");
00244 
00245     testDescending();
00246     
00247     error("done\n");
00248  
00249     exit(0);
00250 }
00251 
00252 
00253 
00254  * @endcode
00255  */
00256 
00257 /**
00258  *  @class LinkedList
00259  *  @brief API abstraction for a Linked List
00260  */ 
00261 template<typename T>
00262 class LinkedList
00263 {
00264 protected:
00265     node<T> *_head;
00266 
00267 public:
00268     /** Create the LinkedList object
00269      */   
00270     LinkedList() {
00271         // clear the member
00272         _head = 0;
00273     }
00274 
00275     
00276     /** Deconstructor for the LinkedList object
00277      *  Removes any members
00278      */ 
00279     ~LinkedList() {
00280         // free any memory that is on the heap
00281         while(remove(1) != NULL);
00282     }
00283 
00284     /** Add a member to the begining of the list
00285      *  @param data - Some data type that is added to the list
00286      *  @return The member that was just inserted (NULL if empty)
00287      */
00288     node<T> *push(T *data)
00289     {
00290         node<T> *new_node = new node<T>[1];
00291         // make sure the new object was allocated
00292         if (0 == new_node)
00293         {
00294             error("Memory allocation failed\n");
00295         }
00296         // update the next item in the list to the current head
00297         new_node->next  = _head;
00298         // store the address to the linked datatype
00299         new_node->data  = data;
00300         _head = new_node;
00301     
00302         return _head;
00303     }
00304     
00305     /** Add a member to some position based on sort condition.
00306     * The list will be iterated from _head to end and the moment inserted
00307     * data is NOT smaller than current node's data, then
00308     * data will be inserted in front of current node.
00309     * This will preserve ascending order of data.
00310     * @param data - some data type that is added to the list
00311     * @param isBigger - comparator function returns true if data1 is bigger
00312     * than data2 and false otherwise.  
00313     * If data1 equals data2, then ">" comparision
00314     * will result in LIFO order.  Using ">=" operator in the function
00315     * results in "FIFO" order and thus it preserves order in which items
00316     * were added to the list.
00317     *
00318     * If isBigger function is implemented with data1 < data2, then
00319     * result insert will be in descending order.  If data1 equals data2, then
00320     * LIFO order is established.
00321     * If data1 <= data2, then FIFO order is preserved when data1 equals data2.  
00322     *
00323     * @return The member that was just inserted (NULL if not inserted).
00324     */
00325     node<T> *insertOrdered(T *data, bool (isBigger)(T* data1, T *data2))
00326     {
00327          node<T>  *new_node = new  node<T>  [1];
00328         // make sure the new object was allocated
00329         if (0 == new_node)
00330         {
00331             error("Memory allocation failed\n");
00332         }
00333         // store the address to the linked datatype
00334         new_node->data  = data;
00335         // clear the next pointer
00336         new_node->next  = 0;
00337         // check for an empty list
00338         if (0 == _head)
00339         {
00340             _head = new_node;
00341             DBG("[insertAsc] set as head\n");
00342             return new_node;
00343         }
00344     
00345          node<T>  *current = _head;
00346          node<T>  *prev = 0;
00347         // move to the item we want to insert
00348         while (isBigger(data, current->data ))
00349         {
00350             // while(true) execute the following
00351             // data being inserted is smaller than current->data
00352             if (0 == current->next ) {
00353                 // there is no more data
00354                 DBG("[insertAsc] insert at end\n");
00355                 current->next  = new_node;
00356                 return new_node;
00357             }
00358             prev = current;
00359             current = current->next ;
00360         }
00361         if (0 == prev) {
00362             DBG("[insertAsc] insert at start\n");
00363             new_node->next  = _head;
00364             _head = new_node;    
00365             return new_node;
00366         }
00367         DBG("[insertAsc] insert inside\n");
00368         new_node->next  = current;
00369         prev->next  = new_node;
00370         return new_node;
00371     }
00372     
00373     /** Add a member to the end of the list
00374      *  @param data - Some data type that is added to the list
00375      *  @return The member that was just inserted (NULL if empty)
00376      */
00377     node<T> *append(T *data)
00378     {
00379         node<T> *current = _head;
00380         node<T> *new_node = new node<T> [1];
00381         // make sure the new object was allocated
00382         if (0 == new_node)
00383         {
00384             error("Memory allocation failed\n");
00385         }
00386         // store the address to the linked datatype
00387         new_node->data  = data;
00388         // clear the next pointer
00389         new_node->next  = 0;
00390         // check for an empty list
00391         if (0 == current)
00392         {
00393             _head = new_node;
00394             return _head;
00395         }
00396         else
00397         {
00398             // look for the end of the list
00399             while (current->next  != 0)
00400             {
00401                 current = current->next ;
00402             }
00403             // and then add the new item to the list
00404             current->next  = new_node;
00405         }
00406     
00407         return current->next ;
00408     }
00409     
00410     /** Remove a member from the list
00411      *  @param loc - The location of the member to remove
00412      *  @return The head of the list
00413      */
00414     node<T> *remove(uint32_t loc)
00415     {
00416         node<T> *current = _head;
00417         node<T> *prev = 0;
00418         // make sure we have an item to remove
00419         if ((loc <= length()) && (loc > 0))
00420         {
00421             // move to the item we want to delete
00422             if (1 == loc)
00423             {
00424                 _head = current->next ;
00425                 delete [] current;
00426             }
00427             else
00428             {
00429                 for (uint32_t i=2; i<=loc; ++i)
00430                 {
00431                     prev = current;
00432                     current = current->next ;
00433                 }
00434                 // store the item + 1 to replace what we are deleting
00435                 prev->next  = current->next ;
00436                 delete [] current;
00437             }
00438         }
00439     
00440         return _head;
00441     }
00442     
00443     /** Get access to a member from the list
00444      *  @param loc - The location of the member to access
00445      *  @return The member that was just requested (NULL if empty or out of bounds)
00446      */
00447     node<T> *pop(uint32_t loc)
00448     {
00449         node<T> *current = _head;
00450         // make sure we have something in the location
00451         if ((loc > length()) || (loc == 0))
00452         {
00453             return 0;
00454         }
00455         // and if so jump down the list
00456         for (uint32_t i=2; i<=loc; ++i)
00457         {
00458             current = current->next ;
00459         }
00460     
00461         return current;
00462     }
00463     
00464     node<T> *pop(T* data, bool (isEqual)(T* data1, T* data2))
00465     {
00466         DBG("..pop started\n");
00467         if (_head == NULL) {
00468             DBG(".._head is NULL\n");
00469             return NULL;
00470         }
00471         node<T> *current = _head;
00472         // make sure we have something in the location
00473         // and if so jump down the list
00474         while(!isEqual(current->data , data)) {
00475             DBG("..next current\n");
00476             if (current->next  == NULL) {
00477                 DBG("..next is NULL; returning NULL\n");
00478                 return NULL;
00479             }
00480             current = current->next ;
00481         }
00482         DBG("..found\n");
00483         return current;
00484     }
00485     
00486     /** Get the length of the list
00487      *  @return The number of members in the list
00488      */
00489     uint32_t length(void)
00490     {
00491         int32_t count = 0;
00492          node<T>  *current = _head;
00493         //loop until the end of the list is found
00494         while (current != 0)
00495         {
00496             ++count;
00497             current = current->next ;
00498         }
00499     
00500         return count;
00501     }
00502     
00503 };
00504 
00505 #endif /* LINKEDLIST_H_ */