ARES / Mbed 2 deprecated RobotMain2015

a

Dependencies:   mbed

LinkedList/LinkedList.cpp@0:85567bbcebdb, 2014-12-14 (annotated)

Committer:
Jagang
Date:
Sun Dec 14 17:49:01 2014 +0000
Revision:
0:85567bbcebdb
New

Who changed what in which revision?

UserRevisionLine numberNew contents of line
Jagang 0:85567bbcebdb 1 /**
Jagang 0:85567bbcebdb 2 * @file LinkedList.cpp
Jagang 0:85567bbcebdb 3 * @brief Core Utility - Templated Linked List class
Jagang 0:85567bbcebdb 4 * @author sam grove
Jagang 0:85567bbcebdb 5 * @version 1.0
Jagang 0:85567bbcebdb 6 * @see
Jagang 0:85567bbcebdb 7 *
Jagang 0:85567bbcebdb 8 * Copyright (c) 2013
Jagang 0:85567bbcebdb 9 *
Jagang 0:85567bbcebdb 10 * Licensed under the Apache License, Version 2.0 (the "License");
Jagang 0:85567bbcebdb 11 * you may not use this file except in compliance with the License.
Jagang 0:85567bbcebdb 12 * You may obtain a copy of the License at
Jagang 0:85567bbcebdb 13 *
Jagang 0:85567bbcebdb 14 * http://www.apache.org/licenses/LICENSE-2.0
Jagang 0:85567bbcebdb 15 *
Jagang 0:85567bbcebdb 16 * Unless required by applicable law or agreed to in writing, software
Jagang 0:85567bbcebdb 17 * distributed under the License is distributed on an "AS IS" BASIS,
Jagang 0:85567bbcebdb 18 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
Jagang 0:85567bbcebdb 19 * See the License for the specific language governing permissions and
Jagang 0:85567bbcebdb 20 * limitations under the License.
Jagang 0:85567bbcebdb 21 */
Jagang 0:85567bbcebdb 22
Jagang 0:85567bbcebdb 23 #include "LinkedList.h" // api wrapper
Jagang 0:85567bbcebdb 24 #include "LogUtil.h"
Jagang 0:85567bbcebdb 25
Jagang 0:85567bbcebdb 26 template<class retT>
Jagang 0:85567bbcebdb 27 LinkedList<retT>::LinkedList()
Jagang 0:85567bbcebdb 28 {
Jagang 0:85567bbcebdb 29 // clear the member
Jagang 0:85567bbcebdb 30 _head = 0;
Jagang 0:85567bbcebdb 31
Jagang 0:85567bbcebdb 32 return;
Jagang 0:85567bbcebdb 33 }
Jagang 0:85567bbcebdb 34
Jagang 0:85567bbcebdb 35 template<class retT>
Jagang 0:85567bbcebdb 36 LinkedList<retT>::~LinkedList()
Jagang 0:85567bbcebdb 37 {
Jagang 0:85567bbcebdb 38 // free any memory that is on the heap
Jagang 0:85567bbcebdb 39 while(remove(1) != NULL);
Jagang 0:85567bbcebdb 40
Jagang 0:85567bbcebdb 41 return;
Jagang 0:85567bbcebdb 42 }
Jagang 0:85567bbcebdb 43
Jagang 0:85567bbcebdb 44 template<class retT>
Jagang 0:85567bbcebdb 45 retT *LinkedList<retT>::push(void *data)
Jagang 0:85567bbcebdb 46 {
Jagang 0:85567bbcebdb 47 retT *new_node = new retT [1];
Jagang 0:85567bbcebdb 48 // make sure the new object was allocated
Jagang 0:85567bbcebdb 49 if (0 == new_node)
Jagang 0:85567bbcebdb 50 {
Jagang 0:85567bbcebdb 51 ERROR("Memory allocation failed\n");
Jagang 0:85567bbcebdb 52 }
Jagang 0:85567bbcebdb 53 // update the next item in the list to the current head
Jagang 0:85567bbcebdb 54 new_node->next = _head;
Jagang 0:85567bbcebdb 55 // store the address to the linked datatype
Jagang 0:85567bbcebdb 56 new_node->data = data;
Jagang 0:85567bbcebdb 57 _head = new_node;
Jagang 0:85567bbcebdb 58
Jagang 0:85567bbcebdb 59 return _head;
Jagang 0:85567bbcebdb 60 }
Jagang 0:85567bbcebdb 61
Jagang 0:85567bbcebdb 62 //template<class retT>
Jagang 0:85567bbcebdb 63 //retT *LinkedList<retT>::insert(void *data, uint32_t loc)
Jagang 0:85567bbcebdb 64 //{
Jagang 0:85567bbcebdb 65 // retT *new_node = new retT [1];
Jagang 0:85567bbcebdb 66 // // make sure the new object was allocated
Jagang 0:85567bbcebdb 67 // if (0 == new_node)
Jagang 0:85567bbcebdb 68 // {
Jagang 0:85567bbcebdb 69 // ERROR("Memory allocation failed\n");
Jagang 0:85567bbcebdb 70 // }
Jagang 0:85567bbcebdb 71 // retT *current = _head->next;
Jagang 0:85567bbcebdb 72 // retT *prev = _head;
Jagang 0:85567bbcebdb 73 // // move to the item we want to insert
Jagang 0:85567bbcebdb 74 // for (uint32_t i=1; i!=(loc-1); i++)
Jagang 0:85567bbcebdb 75 // {
Jagang 0:85567bbcebdb 76 // prev = current;
Jagang 0:85567bbcebdb 77 // current = current->next;
Jagang 0:85567bbcebdb 78 // }
Jagang 0:85567bbcebdb 79 // // store the address to the linked datatype
Jagang 0:85567bbcebdb 80 // new_node->data = data;
Jagang 0:85567bbcebdb 81 // // clear the next pointer
Jagang 0:85567bbcebdb 82 // new_node->next = 0;
Jagang 0:85567bbcebdb 83 // // update the list and store the new stuff
Jagang 0:85567bbcebdb 84 // prev->next = new_node;
Jagang 0:85567bbcebdb 85 // new_node->next = current;
Jagang 0:85567bbcebdb 86 // // store the address to the linked datatype
Jagang 0:85567bbcebdb 87 // _head->data = data;
Jagang 0:85567bbcebdb 88 //
Jagang 0:85567bbcebdb 89 // return prev->next;
Jagang 0:85567bbcebdb 90 //}
Jagang 0:85567bbcebdb 91
Jagang 0:85567bbcebdb 92 template<class retT>
Jagang 0:85567bbcebdb 93 retT *LinkedList<retT>::append(void *data)
Jagang 0:85567bbcebdb 94 {
Jagang 0:85567bbcebdb 95 retT *current = _head;
Jagang 0:85567bbcebdb 96 retT *new_node = new retT [1];
Jagang 0:85567bbcebdb 97 // make sure the new object was allocated
Jagang 0:85567bbcebdb 98 if (0 == new_node)
Jagang 0:85567bbcebdb 99 {
Jagang 0:85567bbcebdb 100 ERROR("Memory allocation failed\n");
Jagang 0:85567bbcebdb 101 }
Jagang 0:85567bbcebdb 102 // store the address to the linked datatype
Jagang 0:85567bbcebdb 103 new_node->data = data;
Jagang 0:85567bbcebdb 104 // clear the next pointer
Jagang 0:85567bbcebdb 105 new_node->next = 0;
Jagang 0:85567bbcebdb 106 // check for an empty list
Jagang 0:85567bbcebdb 107 if (0 == current)
Jagang 0:85567bbcebdb 108 {
Jagang 0:85567bbcebdb 109 _head = new_node;
Jagang 0:85567bbcebdb 110 return _head;
Jagang 0:85567bbcebdb 111 }
Jagang 0:85567bbcebdb 112 else
Jagang 0:85567bbcebdb 113 {
Jagang 0:85567bbcebdb 114 // look for the end of the list
Jagang 0:85567bbcebdb 115 while (current->next != 0)
Jagang 0:85567bbcebdb 116 {
Jagang 0:85567bbcebdb 117 current = current->next;
Jagang 0:85567bbcebdb 118 }
Jagang 0:85567bbcebdb 119 // and then add the new item to the list
Jagang 0:85567bbcebdb 120 current->next = new_node;
Jagang 0:85567bbcebdb 121 }
Jagang 0:85567bbcebdb 122
Jagang 0:85567bbcebdb 123 return current->next;
Jagang 0:85567bbcebdb 124 }
Jagang 0:85567bbcebdb 125
Jagang 0:85567bbcebdb 126 template<class retT>
Jagang 0:85567bbcebdb 127 retT *LinkedList<retT>::remove(uint32_t loc)
Jagang 0:85567bbcebdb 128 {
Jagang 0:85567bbcebdb 129 retT *current = _head;
Jagang 0:85567bbcebdb 130 retT *prev = 0;
Jagang 0:85567bbcebdb 131 // make sure we have an item to remove
Jagang 0:85567bbcebdb 132 if ((loc <= length()) && (loc > 0))
Jagang 0:85567bbcebdb 133 {
Jagang 0:85567bbcebdb 134 // move to the item we want to delete
Jagang 0:85567bbcebdb 135 if (1 == loc)
Jagang 0:85567bbcebdb 136 {
Jagang 0:85567bbcebdb 137 _head = current->next;
Jagang 0:85567bbcebdb 138 delete [] current;
Jagang 0:85567bbcebdb 139 }
Jagang 0:85567bbcebdb 140 else
Jagang 0:85567bbcebdb 141 {
Jagang 0:85567bbcebdb 142 for (uint32_t i=2; i<=loc; ++i)
Jagang 0:85567bbcebdb 143 {
Jagang 0:85567bbcebdb 144 prev = current;
Jagang 0:85567bbcebdb 145 current = current->next;
Jagang 0:85567bbcebdb 146 }
Jagang 0:85567bbcebdb 147 // store the item + 1 to replace what we are deleting
Jagang 0:85567bbcebdb 148 prev->next = current->next;
Jagang 0:85567bbcebdb 149 delete [] current;
Jagang 0:85567bbcebdb 150 }
Jagang 0:85567bbcebdb 151 }
Jagang 0:85567bbcebdb 152
Jagang 0:85567bbcebdb 153 return _head;
Jagang 0:85567bbcebdb 154 }
Jagang 0:85567bbcebdb 155
Jagang 0:85567bbcebdb 156 template<class retT>
Jagang 0:85567bbcebdb 157 retT *LinkedList<retT>::pop(uint32_t loc)
Jagang 0:85567bbcebdb 158 {
Jagang 0:85567bbcebdb 159 retT *current = _head;
Jagang 0:85567bbcebdb 160 // make sure we have something in the location
Jagang 0:85567bbcebdb 161 if ((loc > length()) || (loc == 0))
Jagang 0:85567bbcebdb 162 {
Jagang 0:85567bbcebdb 163 return 0;
Jagang 0:85567bbcebdb 164 }
Jagang 0:85567bbcebdb 165 // and if so jump down the list
Jagang 0:85567bbcebdb 166 for (uint32_t i=2; i<=loc; ++i)
Jagang 0:85567bbcebdb 167 {
Jagang 0:85567bbcebdb 168 current = current->next;
Jagang 0:85567bbcebdb 169 }
Jagang 0:85567bbcebdb 170
Jagang 0:85567bbcebdb 171 return current;
Jagang 0:85567bbcebdb 172 }
Jagang 0:85567bbcebdb 173
Jagang 0:85567bbcebdb 174 template<class retT>
Jagang 0:85567bbcebdb 175 uint32_t LinkedList<retT>::length(void)
Jagang 0:85567bbcebdb 176 {
Jagang 0:85567bbcebdb 177 int32_t count = 0;
Jagang 0:85567bbcebdb 178 retT *current = _head;
Jagang 0:85567bbcebdb 179 //loop until the end of the list is found
Jagang 0:85567bbcebdb 180 while (current != 0)
Jagang 0:85567bbcebdb 181 {
Jagang 0:85567bbcebdb 182 ++count;
Jagang 0:85567bbcebdb 183 current = current->next;
Jagang 0:85567bbcebdb 184 }
Jagang 0:85567bbcebdb 185
Jagang 0:85567bbcebdb 186 return count;
Jagang 0:85567bbcebdb 187 }
Jagang 0:85567bbcebdb 188
Jagang 0:85567bbcebdb 189 // pre-define the type for the linker
Jagang 0:85567bbcebdb 190 template class LinkedList<node>;
Jagang 0:85567bbcebdb 191
Jagang 0:85567bbcebdb 192
Jagang 0:85567bbcebdb 193
Jagang 0:85567bbcebdb 194
Jagang 0:85567bbcebdb 195