LL.cpp

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