LinkedList.cpp

00001 /**
00002  * @file    LinkedList.cpp
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 #include "LinkedList.h"    // api wrapper
00024 
00025 template<class retT>
00026 LinkedList<retT>::LinkedList()
00027 {
00028     // clear the member
00029     _head = 0;
00030 
00031     return;
00032 }
00033 
00034 template<class retT>
00035 LinkedList<retT>::~LinkedList()
00036 {
00037     // free any memory that is on the heap
00038     while(remove(1) != NULL);
00039 
00040     return;
00041 }
00042 
00043 template<class retT>
00044 retT *LinkedList<retT>::push(void *data)
00045 {
00046     retT *new_node = new retT [1];
00047     // make sure the new object was allocated
00048     if (0 == new_node)
00049     {
00050         error("Memory allocation failed\n");
00051     }
00052     // update the next item in the list to the current head
00053     new_node->next = _head;
00054     // store the address to the linked datatype
00055     new_node->data = data;
00056     _head = new_node;
00057 
00058     return _head;
00059 }
00060 
00061 //template<class retT>
00062 //retT *LinkedList<retT>::insert(void *data, uint32_t loc)
00063 //{
00064 //    retT *new_node = new retT [1];
00065 //    // make sure the new object was allocated
00066 //    if (0 == new_node)
00067 //    {
00068 //        error("Memory allocation failed\n");
00069 //    }
00070 //    retT *current = _head->next;
00071 //    retT *prev = _head;
00072 //    // move to the item we want to insert
00073 //    for (uint32_t i=1; i!=(loc-1); i++)
00074 //    {
00075 //        prev = current;
00076 //        current = current->next;
00077 //    }
00078 //    // store the address to the linked datatype
00079 //    new_node->data = data;
00080 //    // clear the next pointer
00081 //    new_node->next = 0;
00082 //    // update the list and store the new stuff
00083 //    prev->next = new_node;
00084 //    new_node->next = current;
00085 //    // store the address to the linked datatype
00086 //    _head->data = data;
00087 //
00088 //    return prev->next;
00089 //}
00090 
00091 template<class retT>
00092 retT *LinkedList<retT>::append(void *data)
00093 {
00094     retT *current = _head;
00095     retT *new_node = new retT [1];
00096     // make sure the new object was allocated
00097     if (0 == new_node)
00098     {
00099         error("Memory allocation failed\n");
00100     }
00101     // store the address to the linked datatype
00102     new_node->data = data;
00103     // clear the next pointer
00104     new_node->next = 0;
00105     // check for an empty list
00106     if (0 == current)
00107     {
00108         _head = new_node;
00109         return _head;
00110     }
00111     else
00112     {
00113         // look for the end of the list
00114         while (current->next != 0)
00115         {
00116             current = current->next;
00117         }
00118         // and then add the new item to the list
00119         current->next = new_node;
00120     }
00121 
00122     return current->next;
00123 }
00124 
00125 template<class retT>
00126 retT *LinkedList<retT>::remove(uint32_t loc)
00127 {
00128     retT *current = _head;
00129     retT *prev = 0;
00130     // make sure we have an item to remove
00131     if ((loc <= length()) && (loc > 0))
00132     {
00133         // move to the item we want to delete
00134         if (1 == loc)
00135         {
00136             _head = current->next;
00137             delete [] current;
00138         }
00139         else
00140         {
00141             for (uint32_t i=2; i<=loc; ++i)
00142             {
00143                 prev = current;
00144                 current = current->next;
00145             }
00146             // store the item + 1 to replace what we are deleting
00147             prev->next = current->next;
00148             delete [] current;
00149         }
00150     }
00151 
00152     return _head;
00153 }
00154 
00155 template<class retT>
00156 retT *LinkedList<retT>::pop(uint32_t loc)
00157 {
00158     retT *current = _head;
00159     // make sure we have something in the location
00160     if ((loc > length()) || (loc == 0))
00161     {
00162         return 0;
00163     }
00164     // and if so jump down the list
00165     for (uint32_t i=2; i<=loc; ++i)
00166     {
00167         current = current->next;
00168     }
00169 
00170     return current;
00171 }
00172 
00173 template<class retT>
00174 uint32_t LinkedList<retT>::length(void)
00175 {
00176     int32_t count = 0;
00177     retT *current = _head;
00178     //loop until the end of the list is found
00179     while (current != 0)
00180     {
00181         ++count;
00182         current = current->next;
00183     }
00184 
00185     return count;
00186 }
00187 
00188 // pre-define the type for the linker
00189 template class LinkedList<node> ;
00190 
00191 
00192 
00193 
00194