Sergei G / LinkedList

Added ability to maintain ordered linked list based on "insertAsc" function. The function takes a comparator function that allows for specific order behavior. If values collide, then FIFO or LIFO order can be maintained based on comparator function implementation.

Dependents:   JobScheduler

Fork of LinkedList by Sam Grove

LinkedList.h@12:ab8a80bcfd64, 2017-07-11 (annotated)

Committer:
sgnezdov
Date:
Tue Jul 11 00:15:05 2017 +0000
Revision:
12:ab8a80bcfd64
Parent:
11:4336cd18cce9
Child:
13:b06f7b37fff4
Changed LinkedList implementation to be in header (for templates), made node hard coded and data is part of template

Who changed what in which revision?

UserRevisionLine numberNew contents of line
sam_grove 0:3f64a15357ac 1 /**
sam_grove 0:3f64a15357ac 2 * @file LinkedList.h
sam_grove 0:3f64a15357ac 3 * @brief Core Utility - Templated Linked List class
sam_grove 0:3f64a15357ac 4 * @author sam grove
sam_grove 0:3f64a15357ac 5 * @version 1.0
sam_grove 0:3f64a15357ac 6 * @see
sam_grove 0:3f64a15357ac 7 *
sam_grove 0:3f64a15357ac 8 * Copyright (c) 2013
sam_grove 0:3f64a15357ac 9 *
sam_grove 0:3f64a15357ac 10 * Licensed under the Apache License, Version 2.0 (the "License");
sam_grove 0:3f64a15357ac 11 * you may not use this file except in compliance with the License.
sam_grove 0:3f64a15357ac 12 * You may obtain a copy of the License at
sam_grove 0:3f64a15357ac 13 *
sam_grove 0:3f64a15357ac 14 * http://www.apache.org/licenses/LICENSE-2.0
sam_grove 0:3f64a15357ac 15 *
sam_grove 0:3f64a15357ac 16 * Unless required by applicable law or agreed to in writing, software
sam_grove 0:3f64a15357ac 17 * distributed under the License is distributed on an "AS IS" BASIS,
sam_grove 0:3f64a15357ac 18 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
sam_grove 0:3f64a15357ac 19 * See the License for the specific language governing permissions and
sam_grove 0:3f64a15357ac 20 * limitations under the License.
sam_grove 0:3f64a15357ac 21 */
sam_grove 0:3f64a15357ac 22
sam_grove 0:3f64a15357ac 23 #ifndef LINKEDLIST_H_
sam_grove 0:3f64a15357ac 24 #define LINKEDLIST_H_
sam_grove 0:3f64a15357ac 25
sam_grove 0:3f64a15357ac 26 #include <stdint.h>
Sissors 7:4ed66162aaa8 27 #include "mbed.h"
sam_grove 0:3f64a15357ac 28
sam_grove 0:3f64a15357ac 29 /**
sam_grove 1:a032c0392ba1 30 * @struct node
sam_grove 0:3f64a15357ac 31 * @brief The Linked List structure
sam_grove 0:3f64a15357ac 32 */
sgnezdov 12:ab8a80bcfd64 33 template<typename T>
sam_grove 0:3f64a15357ac 34 struct node
sam_grove 0:3f64a15357ac 35 {
sgnezdov 12:ab8a80bcfd64 36 T *data; /*!< pointer to list member data */
sam_grove 0:3f64a15357ac 37 struct node *next; /*!< pointer to the next list member */
sam_grove 0:3f64a15357ac 38 };
sam_grove 0:3f64a15357ac 39
sgnezdov 8:918b196b0ac4 40 ///** Returns true if data1 shall be inserted before data 2.
sgnezdov 8:918b196b0ac4 41 //*/
sgnezdov 8:918b196b0ac4 42 //typedef bool insertAtFunc(void *data1, void *data2);
sgnezdov 8:918b196b0ac4 43
sam_grove 0:3f64a15357ac 44 /** Example using the LinkedList Class
sam_grove 0:3f64a15357ac 45 * @code
sam_grove 1:a032c0392ba1 46 * #include "mbed.h"
sam_grove 1:a032c0392ba1 47 * #include "LinkedList.h"
sam_grove 1:a032c0392ba1 48 *
sam_grove 1:a032c0392ba1 49 * LinkedList<node>list;
sam_grove 1:a032c0392ba1 50 *
sam_grove 1:a032c0392ba1 51 * int main()
sam_grove 1:a032c0392ba1 52 * {
sam_grove 1:a032c0392ba1 53 * node *tmp;
sam_grove 1:a032c0392ba1 54 *
sam_grove 1:a032c0392ba1 55 * list.push((char *)"Two\n");
sam_grove 1:a032c0392ba1 56 * list.append((char *)"Three\n");
sam_grove 1:a032c0392ba1 57 * list.append((char *)"Four\n");
sam_grove 1:a032c0392ba1 58 * list.push((char*)"One\n");
sam_grove 1:a032c0392ba1 59 * list.append((char*)"Five\n");
sam_grove 1:a032c0392ba1 60 *
sam_grove 3:c14e7a918e21 61 * for(int i=1; i<=list.length(); i++)
sam_grove 1:a032c0392ba1 62 * {
sam_grove 1:a032c0392ba1 63 * tmp = list.pop(i);
sam_grove 1:a032c0392ba1 64 * printf("%s", (char *)tmp->data);
sam_grove 1:a032c0392ba1 65 * }
sam_grove 1:a032c0392ba1 66 *
sam_grove 1:a032c0392ba1 67 * error("done\n");
sam_grove 1:a032c0392ba1 68 * }
sam_grove 0:3f64a15357ac 69 * @endcode
sam_grove 0:3f64a15357ac 70 */
sgnezdov 9:b173aed98988 71
sgnezdov 11:4336cd18cce9 72 /** Example using new insertOrdered function:
sgnezdov 10:cb2e50ed6945 73 * @code
sgnezdov 9:b173aed98988 74
sgnezdov 11:4336cd18cce9 75 #include "mbed.h"
sgnezdov 9:b173aed98988 76 #include "LinkedList.h"
sgnezdov 9:b173aed98988 77
sgnezdov 9:b173aed98988 78 void printList(LinkedList<node> &list, const char* msg)
sgnezdov 9:b173aed98988 79 {
sgnezdov 9:b173aed98988 80 printf("%s: ", msg);
sgnezdov 9:b173aed98988 81 for(int i=1; i<=list.length(); i++)
sgnezdov 9:b173aed98988 82 {
sgnezdov 9:b173aed98988 83 node *tmp = list.pop(i);
sgnezdov 9:b173aed98988 84 printf("%d ", *(int*)tmp->data);
sgnezdov 9:b173aed98988 85 }
sgnezdov 9:b173aed98988 86 printf("\n");
sgnezdov 9:b173aed98988 87 }
sgnezdov 9:b173aed98988 88
sgnezdov 12:ab8a80bcfd64 89 bool ascending(int *n1, int *n2)
sgnezdov 12:ab8a80bcfd64 90 {
sgnezdov 12:ab8a80bcfd64 91 int *d1 = (int*)n1;
sgnezdov 12:ab8a80bcfd64 92 int *d2 = (int*)n2;
sgnezdov 12:ab8a80bcfd64 93 bool rv = *d1 <= *d2;
sgnezdov 12:ab8a80bcfd64 94 printf("(%d %d:%d)", *d1, *d2, rv);
sgnezdov 12:ab8a80bcfd64 95 return rv;
sgnezdov 12:ab8a80bcfd64 96 }
sgnezdov 12:ab8a80bcfd64 97
sgnezdov 11:4336cd18cce9 98 void testAscending()
sgnezdov 9:b173aed98988 99 {
sgnezdov 12:ab8a80bcfd64 100 node<int> *tmp;
sgnezdov 9:b173aed98988 101
sgnezdov 9:b173aed98988 102 int n0 = 0;
sgnezdov 9:b173aed98988 103 int n1 = 1;
sgnezdov 9:b173aed98988 104 int n1B = 1;
sgnezdov 9:b173aed98988 105 int n2 = 2;
sgnezdov 9:b173aed98988 106 int n3 = 3;
sgnezdov 9:b173aed98988 107 int n4 = 4;
sgnezdov 9:b173aed98988 108
sgnezdov 12:ab8a80bcfd64 109 LinkedList<int>list;
sgnezdov 9:b173aed98988 110
sgnezdov 11:4336cd18cce9 111 tmp = list.insertOrdered(&n2, ascending);
sgnezdov 9:b173aed98988 112 if (NULL == tmp) {
sgnezdov 11:4336cd18cce9 113 error("insertOrdered did not insert a node");
sgnezdov 9:b173aed98988 114 }
sgnezdov 9:b173aed98988 115 printList(list, "exp 2");
sgnezdov 9:b173aed98988 116
sgnezdov 11:4336cd18cce9 117 tmp = list.insertOrdered(&n1, ascending);
sgnezdov 9:b173aed98988 118 if (NULL == tmp) {
sgnezdov 11:4336cd18cce9 119 error("insertOrdered did not insert a node");
sgnezdov 9:b173aed98988 120 }
sgnezdov 9:b173aed98988 121 printList(list, "exp 1,2");
sgnezdov 9:b173aed98988 122
sgnezdov 11:4336cd18cce9 123 tmp = list.insertOrdered(&n4, ascending);
sgnezdov 9:b173aed98988 124 if (NULL == tmp) {
sgnezdov 11:4336cd18cce9 125 error("insertOrdered did not insert a node");
sgnezdov 9:b173aed98988 126 }
sgnezdov 9:b173aed98988 127 printList(list, "exp 1,2,4");
sgnezdov 9:b173aed98988 128
sgnezdov 11:4336cd18cce9 129 tmp = list.insertOrdered(&n3, ascending);
sgnezdov 9:b173aed98988 130 if (NULL == tmp) {
sgnezdov 11:4336cd18cce9 131 error("insertOrdered did not insert a node");
sgnezdov 9:b173aed98988 132 }
sgnezdov 9:b173aed98988 133 printList(list, "exp 1,2,3,4");
sgnezdov 9:b173aed98988 134
sgnezdov 11:4336cd18cce9 135 tmp = list.insertOrdered(&n0, ascending);
sgnezdov 9:b173aed98988 136 if (NULL == tmp) {
sgnezdov 11:4336cd18cce9 137 error("insertOrdered did not insert a node");
sgnezdov 9:b173aed98988 138 }
sgnezdov 9:b173aed98988 139 printList(list, "exp 0,1,2,3,4");
sgnezdov 9:b173aed98988 140
sgnezdov 11:4336cd18cce9 141 tmp = list.insertOrdered(&n1B, ascending);
sgnezdov 9:b173aed98988 142 if (NULL == tmp) {
sgnezdov 11:4336cd18cce9 143 error("insertOrdered did not insert a node");
sgnezdov 9:b173aed98988 144 }
sgnezdov 9:b173aed98988 145 printList(list, "exp 0,1,1,2,3,4");
sgnezdov 9:b173aed98988 146
sgnezdov 9:b173aed98988 147 tmp = list.pop(2);
sgnezdov 9:b173aed98988 148 if (tmp->data != &n1) {
sgnezdov 9:b173aed98988 149 error("pos 2 is not n1\n");
sgnezdov 9:b173aed98988 150 }
sgnezdov 9:b173aed98988 151 printf("n1 is good\n");
sgnezdov 9:b173aed98988 152
sgnezdov 9:b173aed98988 153 tmp = list.pop(3);
sgnezdov 9:b173aed98988 154 if (tmp->data != &n1B) {
sgnezdov 9:b173aed98988 155 error("pos3 is not n1B");
sgnezdov 9:b173aed98988 156 }
sgnezdov 9:b173aed98988 157 printf("n1B is good\n");
sgnezdov 11:4336cd18cce9 158 }
sgnezdov 9:b173aed98988 159
sgnezdov 12:ab8a80bcfd64 160 bool descending(int *n1, int *n2)
sgnezdov 12:ab8a80bcfd64 161 {
sgnezdov 12:ab8a80bcfd64 162 int *d1 = (int*)n1;
sgnezdov 12:ab8a80bcfd64 163 int *d2 = (int*)n2;
sgnezdov 12:ab8a80bcfd64 164 bool rv = *d1 <= *d2;
sgnezdov 12:ab8a80bcfd64 165 printf("(%d %d:%d)", *d1, *d2, rv);
sgnezdov 12:ab8a80bcfd64 166 return rv;
sgnezdov 12:ab8a80bcfd64 167 }
sgnezdov 12:ab8a80bcfd64 168
sgnezdov 11:4336cd18cce9 169 void testDescending()
sgnezdov 11:4336cd18cce9 170 {
sgnezdov 12:ab8a80bcfd64 171 node<int> *tmp;
sgnezdov 11:4336cd18cce9 172
sgnezdov 11:4336cd18cce9 173 int n0 = 0;
sgnezdov 11:4336cd18cce9 174 int n1 = 1;
sgnezdov 11:4336cd18cce9 175 int n1B = 1;
sgnezdov 11:4336cd18cce9 176 int n2 = 2;
sgnezdov 11:4336cd18cce9 177 int n3 = 3;
sgnezdov 11:4336cd18cce9 178 int n4 = 4;
sgnezdov 11:4336cd18cce9 179
sgnezdov 12:ab8a80bcfd64 180 LinkedList<int>l;
sgnezdov 11:4336cd18cce9 181
sgnezdov 11:4336cd18cce9 182 tmp = l.insertOrdered(&n2, descending);
sgnezdov 11:4336cd18cce9 183 if (NULL == tmp) {
sgnezdov 11:4336cd18cce9 184 error("insertOrdered did not insert a node");
sgnezdov 11:4336cd18cce9 185 }
sgnezdov 11:4336cd18cce9 186 printList(l, "exp 2");
sgnezdov 11:4336cd18cce9 187
sgnezdov 11:4336cd18cce9 188 tmp = l.insertOrdered(&n1, descending);
sgnezdov 11:4336cd18cce9 189 if (NULL == tmp) {
sgnezdov 11:4336cd18cce9 190 error("insertOrdered did not insert a node");
sgnezdov 11:4336cd18cce9 191 }
sgnezdov 11:4336cd18cce9 192 printList(l, "exp 2,1");
sgnezdov 11:4336cd18cce9 193
sgnezdov 11:4336cd18cce9 194 tmp = l.insertOrdered(&n4, descending);
sgnezdov 11:4336cd18cce9 195 if (NULL == tmp) {
sgnezdov 11:4336cd18cce9 196 error("insertOrdered did not insert a node");
sgnezdov 11:4336cd18cce9 197 }
sgnezdov 11:4336cd18cce9 198 printList(l, "exp 4,2,1");
sgnezdov 11:4336cd18cce9 199
sgnezdov 11:4336cd18cce9 200 tmp = l.insertOrdered(&n3, descending);
sgnezdov 11:4336cd18cce9 201 if (NULL == tmp) {
sgnezdov 11:4336cd18cce9 202 error("insertOrdered did not insert a node");
sgnezdov 11:4336cd18cce9 203 }
sgnezdov 11:4336cd18cce9 204 printList(l, "exp 4,3,2,1");
sgnezdov 11:4336cd18cce9 205
sgnezdov 11:4336cd18cce9 206 tmp = l.insertOrdered(&n0, descending);
sgnezdov 11:4336cd18cce9 207 if (NULL == tmp) {
sgnezdov 11:4336cd18cce9 208 error("insertOrdered did not insert a node");
sgnezdov 11:4336cd18cce9 209 }
sgnezdov 11:4336cd18cce9 210 printList(l, "exp 4,3,2,1,0");
sgnezdov 11:4336cd18cce9 211
sgnezdov 11:4336cd18cce9 212 tmp = l.insertOrdered(&n1B, descending);
sgnezdov 11:4336cd18cce9 213 if (NULL == tmp) {
sgnezdov 11:4336cd18cce9 214 error("insertOrdered did not insert a node");
sgnezdov 11:4336cd18cce9 215 }
sgnezdov 11:4336cd18cce9 216 printList(l, "exp 4,3,2,1,1,0");
sgnezdov 11:4336cd18cce9 217
sgnezdov 11:4336cd18cce9 218 tmp = l.pop(4);
sgnezdov 11:4336cd18cce9 219 if (tmp->data != &n1) {
sgnezdov 11:4336cd18cce9 220 error("pos 2 is not n1\n");
sgnezdov 11:4336cd18cce9 221 }
sgnezdov 11:4336cd18cce9 222 printf("n1 is good\n");
sgnezdov 11:4336cd18cce9 223
sgnezdov 11:4336cd18cce9 224 tmp = l.pop(5);
sgnezdov 11:4336cd18cce9 225 if (tmp->data != &n1B) {
sgnezdov 11:4336cd18cce9 226 error("pos3 is not n1B");
sgnezdov 11:4336cd18cce9 227 }
sgnezdov 11:4336cd18cce9 228 printf("n1B is good\n");
sgnezdov 11:4336cd18cce9 229 }
sgnezdov 11:4336cd18cce9 230
sgnezdov 11:4336cd18cce9 231
sgnezdov 11:4336cd18cce9 232 int main()
sgnezdov 11:4336cd18cce9 233 {
sgnezdov 11:4336cd18cce9 234 printf("\nJob Scheduler Demo\n");
sgnezdov 11:4336cd18cce9 235
sgnezdov 11:4336cd18cce9 236 testDescending();
sgnezdov 11:4336cd18cce9 237
sgnezdov 9:b173aed98988 238 error("done\n");
sgnezdov 9:b173aed98988 239
sgnezdov 9:b173aed98988 240 exit(0);
sgnezdov 9:b173aed98988 241 }
sgnezdov 9:b173aed98988 242
sgnezdov 11:4336cd18cce9 243
sgnezdov 11:4336cd18cce9 244
sgnezdov 10:cb2e50ed6945 245 * @endcode
sgnezdov 9:b173aed98988 246 */
sam_grove 0:3f64a15357ac 247
sam_grove 0:3f64a15357ac 248 /**
sam_grove 0:3f64a15357ac 249 * @class LinkedList
sam_grove 0:3f64a15357ac 250 * @brief API abstraction for a Linked List
sam_grove 0:3f64a15357ac 251 */
sgnezdov 12:ab8a80bcfd64 252 template<typename T>
sam_grove 0:3f64a15357ac 253 class LinkedList
sam_grove 0:3f64a15357ac 254 {
sam_grove 0:3f64a15357ac 255 protected:
sgnezdov 12:ab8a80bcfd64 256 node<T> *_head;
sam_grove 0:3f64a15357ac 257
sam_grove 0:3f64a15357ac 258 public:
sam_grove 0:3f64a15357ac 259 /** Create the LinkedList object
sam_grove 0:3f64a15357ac 260 */
sgnezdov 12:ab8a80bcfd64 261 LinkedList() {
sgnezdov 12:ab8a80bcfd64 262 // clear the member
sgnezdov 12:ab8a80bcfd64 263 _head = 0;
sgnezdov 12:ab8a80bcfd64 264 }
sgnezdov 12:ab8a80bcfd64 265
sam_grove 0:3f64a15357ac 266
sam_grove 0:3f64a15357ac 267 /** Deconstructor for the LinkedList object
sam_grove 0:3f64a15357ac 268 * Removes any members
sam_grove 0:3f64a15357ac 269 */
sgnezdov 12:ab8a80bcfd64 270 ~LinkedList() {
sgnezdov 12:ab8a80bcfd64 271 // free any memory that is on the heap
sgnezdov 12:ab8a80bcfd64 272 while(remove(1) != NULL);
sgnezdov 12:ab8a80bcfd64 273 }
sam_grove 0:3f64a15357ac 274
sam_grove 0:3f64a15357ac 275 /** Add a member to the begining of the list
sam_grove 0:3f64a15357ac 276 * @param data - Some data type that is added to the list
sam_grove 0:3f64a15357ac 277 * @return The member that was just inserted (NULL if empty)
sam_grove 0:3f64a15357ac 278 */
sgnezdov 12:ab8a80bcfd64 279 node<T> *push(T *data)
sgnezdov 12:ab8a80bcfd64 280 {
sgnezdov 12:ab8a80bcfd64 281 node<T> *new_node = new node<T>[1];
sgnezdov 12:ab8a80bcfd64 282 // make sure the new object was allocated
sgnezdov 12:ab8a80bcfd64 283 if (0 == new_node)
sgnezdov 12:ab8a80bcfd64 284 {
sgnezdov 12:ab8a80bcfd64 285 error("Memory allocation failed\n");
sgnezdov 12:ab8a80bcfd64 286 }
sgnezdov 12:ab8a80bcfd64 287 // update the next item in the list to the current head
sgnezdov 12:ab8a80bcfd64 288 new_node->next = _head;
sgnezdov 12:ab8a80bcfd64 289 // store the address to the linked datatype
sgnezdov 12:ab8a80bcfd64 290 new_node->data = data;
sgnezdov 12:ab8a80bcfd64 291 _head = new_node;
sgnezdov 12:ab8a80bcfd64 292
sgnezdov 12:ab8a80bcfd64 293 return _head;
sgnezdov 12:ab8a80bcfd64 294 }
sam_grove 0:3f64a15357ac 295
sgnezdov 8:918b196b0ac4 296 /** Add a member to some position based on sort condition.
sgnezdov 8:918b196b0ac4 297 * The list will be iterated from _head to end and the moment inserted
sgnezdov 8:918b196b0ac4 298 * data is NOT smaller than current node's data, then
sgnezdov 8:918b196b0ac4 299 * data will be inserted in front of current node.
sgnezdov 8:918b196b0ac4 300 * This will preserve ascending order of data.
sgnezdov 8:918b196b0ac4 301 * @param data - some data type that is added to the list
sgnezdov 8:918b196b0ac4 302 * @param isBigger - comparator function returns true if data1 is bigger
sgnezdov 11:4336cd18cce9 303 * than data2 and false otherwise.
sgnezdov 11:4336cd18cce9 304 * If data1 equals data2, then ">" comparision
sgnezdov 8:918b196b0ac4 305 * will result in LIFO order. Using ">=" operator in the function
sgnezdov 8:918b196b0ac4 306 * results in "FIFO" order and thus it preserves order in which items
sgnezdov 8:918b196b0ac4 307 * were added to the list.
sgnezdov 11:4336cd18cce9 308 *
sgnezdov 11:4336cd18cce9 309 * If isBigger function is implemented with data1 < data2, then
sgnezdov 11:4336cd18cce9 310 * result insert will be in descending order. If data1 equals data2, then
sgnezdov 11:4336cd18cce9 311 * LIFO order is established.
sgnezdov 11:4336cd18cce9 312 * If data1 <= data2, then FIFO order is preserved when data1 equals data2.
sgnezdov 11:4336cd18cce9 313 *
sgnezdov 8:918b196b0ac4 314 * @return The member that was just inserted (NULL if not inserted).
sgnezdov 8:918b196b0ac4 315 */
sgnezdov 12:ab8a80bcfd64 316 node<T> *insertOrdered(T *data, bool (isBigger)(T* data1, T *data2))
sgnezdov 12:ab8a80bcfd64 317 {
sgnezdov 12:ab8a80bcfd64 318 node<T> *new_node = new node<T> [1];
sgnezdov 12:ab8a80bcfd64 319 // make sure the new object was allocated
sgnezdov 12:ab8a80bcfd64 320 if (0 == new_node)
sgnezdov 12:ab8a80bcfd64 321 {
sgnezdov 12:ab8a80bcfd64 322 error("Memory allocation failed\n");
sgnezdov 12:ab8a80bcfd64 323 }
sgnezdov 12:ab8a80bcfd64 324 // store the address to the linked datatype
sgnezdov 12:ab8a80bcfd64 325 new_node->data = data;
sgnezdov 12:ab8a80bcfd64 326 // clear the next pointer
sgnezdov 12:ab8a80bcfd64 327 new_node->next = 0;
sgnezdov 12:ab8a80bcfd64 328 // check for an empty list
sgnezdov 12:ab8a80bcfd64 329 if (0 == _head)
sgnezdov 12:ab8a80bcfd64 330 {
sgnezdov 12:ab8a80bcfd64 331 _head = new_node;
sgnezdov 12:ab8a80bcfd64 332 printf("[insertAsc] set as head\n");
sgnezdov 12:ab8a80bcfd64 333 return new_node;
sgnezdov 12:ab8a80bcfd64 334 }
sgnezdov 12:ab8a80bcfd64 335
sgnezdov 12:ab8a80bcfd64 336 node<T> *current = _head;
sgnezdov 12:ab8a80bcfd64 337 node<T> *prev = 0;
sgnezdov 12:ab8a80bcfd64 338 // move to the item we want to insert
sgnezdov 12:ab8a80bcfd64 339 while (isBigger(data, current->data))
sgnezdov 12:ab8a80bcfd64 340 {
sgnezdov 12:ab8a80bcfd64 341 // while(true) execute the following
sgnezdov 12:ab8a80bcfd64 342 // data being inserted is smaller than current->data
sgnezdov 12:ab8a80bcfd64 343 if (0 == current->next) {
sgnezdov 12:ab8a80bcfd64 344 // there is no more data
sgnezdov 12:ab8a80bcfd64 345 printf("[insertAsc] insert at end\n");
sgnezdov 12:ab8a80bcfd64 346 current->next = new_node;
sgnezdov 12:ab8a80bcfd64 347 return new_node;
sgnezdov 12:ab8a80bcfd64 348 }
sgnezdov 12:ab8a80bcfd64 349 prev = current;
sgnezdov 12:ab8a80bcfd64 350 current = current->next;
sgnezdov 12:ab8a80bcfd64 351 }
sgnezdov 12:ab8a80bcfd64 352 if (0 == prev) {
sgnezdov 12:ab8a80bcfd64 353 printf("[insertAsc] insert at start\n");
sgnezdov 12:ab8a80bcfd64 354 new_node->next = _head;
sgnezdov 12:ab8a80bcfd64 355 _head = new_node;
sgnezdov 12:ab8a80bcfd64 356 return new_node;
sgnezdov 12:ab8a80bcfd64 357 }
sgnezdov 12:ab8a80bcfd64 358 printf("[insertAsc] insert inside\n");
sgnezdov 12:ab8a80bcfd64 359 new_node->next = current;
sgnezdov 12:ab8a80bcfd64 360 prev->next = new_node;
sgnezdov 12:ab8a80bcfd64 361 return new_node;
sgnezdov 12:ab8a80bcfd64 362 }
sam_grove 0:3f64a15357ac 363
sam_grove 0:3f64a15357ac 364 /** Add a member to the end of the list
sam_grove 0:3f64a15357ac 365 * @param data - Some data type that is added to the list
sam_grove 0:3f64a15357ac 366 * @return The member that was just inserted (NULL if empty)
sam_grove 0:3f64a15357ac 367 */
sgnezdov 12:ab8a80bcfd64 368 node<T> *append(T *data)
sgnezdov 12:ab8a80bcfd64 369 {
sgnezdov 12:ab8a80bcfd64 370 node<T> *current = _head;
sgnezdov 12:ab8a80bcfd64 371 node<T> *new_node = new node<T> [1];
sgnezdov 12:ab8a80bcfd64 372 // make sure the new object was allocated
sgnezdov 12:ab8a80bcfd64 373 if (0 == new_node)
sgnezdov 12:ab8a80bcfd64 374 {
sgnezdov 12:ab8a80bcfd64 375 error("Memory allocation failed\n");
sgnezdov 12:ab8a80bcfd64 376 }
sgnezdov 12:ab8a80bcfd64 377 // store the address to the linked datatype
sgnezdov 12:ab8a80bcfd64 378 new_node->data = data;
sgnezdov 12:ab8a80bcfd64 379 // clear the next pointer
sgnezdov 12:ab8a80bcfd64 380 new_node->next = 0;
sgnezdov 12:ab8a80bcfd64 381 // check for an empty list
sgnezdov 12:ab8a80bcfd64 382 if (0 == current)
sgnezdov 12:ab8a80bcfd64 383 {
sgnezdov 12:ab8a80bcfd64 384 _head = new_node;
sgnezdov 12:ab8a80bcfd64 385 return _head;
sgnezdov 12:ab8a80bcfd64 386 }
sgnezdov 12:ab8a80bcfd64 387 else
sgnezdov 12:ab8a80bcfd64 388 {
sgnezdov 12:ab8a80bcfd64 389 // look for the end of the list
sgnezdov 12:ab8a80bcfd64 390 while (current->next != 0)
sgnezdov 12:ab8a80bcfd64 391 {
sgnezdov 12:ab8a80bcfd64 392 current = current->next;
sgnezdov 12:ab8a80bcfd64 393 }
sgnezdov 12:ab8a80bcfd64 394 // and then add the new item to the list
sgnezdov 12:ab8a80bcfd64 395 current->next = new_node;
sgnezdov 12:ab8a80bcfd64 396 }
sgnezdov 12:ab8a80bcfd64 397
sgnezdov 12:ab8a80bcfd64 398 return current->next;
sgnezdov 12:ab8a80bcfd64 399 }
sam_grove 0:3f64a15357ac 400
sam_grove 0:3f64a15357ac 401 /** Remove a member from the list
sam_grove 0:3f64a15357ac 402 * @param loc - The location of the member to remove
sam_grove 0:3f64a15357ac 403 * @return The head of the list
sam_grove 0:3f64a15357ac 404 */
sgnezdov 12:ab8a80bcfd64 405 node<T> *remove(uint32_t loc)
sgnezdov 12:ab8a80bcfd64 406 {
sgnezdov 12:ab8a80bcfd64 407 node<T> *current = _head;
sgnezdov 12:ab8a80bcfd64 408 node<T> *prev = 0;
sgnezdov 12:ab8a80bcfd64 409 // make sure we have an item to remove
sgnezdov 12:ab8a80bcfd64 410 if ((loc <= length()) && (loc > 0))
sgnezdov 12:ab8a80bcfd64 411 {
sgnezdov 12:ab8a80bcfd64 412 // move to the item we want to delete
sgnezdov 12:ab8a80bcfd64 413 if (1 == loc)
sgnezdov 12:ab8a80bcfd64 414 {
sgnezdov 12:ab8a80bcfd64 415 _head = current->next;
sgnezdov 12:ab8a80bcfd64 416 delete [] current;
sgnezdov 12:ab8a80bcfd64 417 }
sgnezdov 12:ab8a80bcfd64 418 else
sgnezdov 12:ab8a80bcfd64 419 {
sgnezdov 12:ab8a80bcfd64 420 for (uint32_t i=2; i<=loc; ++i)
sgnezdov 12:ab8a80bcfd64 421 {
sgnezdov 12:ab8a80bcfd64 422 prev = current;
sgnezdov 12:ab8a80bcfd64 423 current = current->next;
sgnezdov 12:ab8a80bcfd64 424 }
sgnezdov 12:ab8a80bcfd64 425 // store the item + 1 to replace what we are deleting
sgnezdov 12:ab8a80bcfd64 426 prev->next = current->next;
sgnezdov 12:ab8a80bcfd64 427 delete [] current;
sgnezdov 12:ab8a80bcfd64 428 }
sgnezdov 12:ab8a80bcfd64 429 }
sgnezdov 12:ab8a80bcfd64 430
sgnezdov 12:ab8a80bcfd64 431 return _head;
sgnezdov 12:ab8a80bcfd64 432 }
sam_grove 0:3f64a15357ac 433
sam_grove 0:3f64a15357ac 434 /** Get access to a member from the list
sam_grove 0:3f64a15357ac 435 * @param loc - The location of the member to access
sam_grove 0:3f64a15357ac 436 * @return The member that was just requested (NULL if empty or out of bounds)
sam_grove 0:3f64a15357ac 437 */
sgnezdov 12:ab8a80bcfd64 438 node<T> *pop(uint32_t loc)
sgnezdov 12:ab8a80bcfd64 439 {
sgnezdov 12:ab8a80bcfd64 440 node<T> *current = _head;
sgnezdov 12:ab8a80bcfd64 441 // make sure we have something in the location
sgnezdov 12:ab8a80bcfd64 442 if ((loc > length()) || (loc == 0))
sgnezdov 12:ab8a80bcfd64 443 {
sgnezdov 12:ab8a80bcfd64 444 return 0;
sgnezdov 12:ab8a80bcfd64 445 }
sgnezdov 12:ab8a80bcfd64 446 // and if so jump down the list
sgnezdov 12:ab8a80bcfd64 447 for (uint32_t i=2; i<=loc; ++i)
sgnezdov 12:ab8a80bcfd64 448 {
sgnezdov 12:ab8a80bcfd64 449 current = current->next;
sgnezdov 12:ab8a80bcfd64 450 }
sgnezdov 12:ab8a80bcfd64 451
sgnezdov 12:ab8a80bcfd64 452 return current;
sgnezdov 12:ab8a80bcfd64 453 }
sgnezdov 12:ab8a80bcfd64 454
sgnezdov 12:ab8a80bcfd64 455 node<T> *pop(T* data, bool (isEqual)(T* data1, T* data2))
sgnezdov 12:ab8a80bcfd64 456 {
sgnezdov 12:ab8a80bcfd64 457 if (_head == NULL) {
sgnezdov 12:ab8a80bcfd64 458 return NULL;
sgnezdov 12:ab8a80bcfd64 459 }
sgnezdov 12:ab8a80bcfd64 460 node<T> *current = _head;
sgnezdov 12:ab8a80bcfd64 461 // make sure we have something in the location
sgnezdov 12:ab8a80bcfd64 462 // and if so jump down the list
sgnezdov 12:ab8a80bcfd64 463 while(!isEqual(current->data, data)) {
sgnezdov 12:ab8a80bcfd64 464 current = current->next;
sgnezdov 12:ab8a80bcfd64 465 if (current->next == NULL) {
sgnezdov 12:ab8a80bcfd64 466 return NULL;
sgnezdov 12:ab8a80bcfd64 467 }
sgnezdov 12:ab8a80bcfd64 468 }
sgnezdov 12:ab8a80bcfd64 469 return current;
sgnezdov 12:ab8a80bcfd64 470 }
sam_grove 0:3f64a15357ac 471
sam_grove 0:3f64a15357ac 472 /** Get the length of the list
sam_grove 0:3f64a15357ac 473 * @return The number of members in the list
sam_grove 0:3f64a15357ac 474 */
sgnezdov 12:ab8a80bcfd64 475 uint32_t length(void)
sgnezdov 12:ab8a80bcfd64 476 {
sgnezdov 12:ab8a80bcfd64 477 int32_t count = 0;
sgnezdov 12:ab8a80bcfd64 478 node<T> *current = _head;
sgnezdov 12:ab8a80bcfd64 479 //loop until the end of the list is found
sgnezdov 12:ab8a80bcfd64 480 while (current != 0)
sgnezdov 12:ab8a80bcfd64 481 {
sgnezdov 12:ab8a80bcfd64 482 ++count;
sgnezdov 12:ab8a80bcfd64 483 current = current->next;
sgnezdov 12:ab8a80bcfd64 484 }
sgnezdov 12:ab8a80bcfd64 485
sgnezdov 12:ab8a80bcfd64 486 return count;
sgnezdov 12:ab8a80bcfd64 487 }
sgnezdov 12:ab8a80bcfd64 488
sam_grove 0:3f64a15357ac 489 };
sam_grove 0:3f64a15357ac 490
sam_grove 0:3f64a15357ac 491 #endif /* LINKEDLIST_H_ */