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@15:f715e3067fa8, 2017-07-14 (annotated)

Committer:
sgnezdov
Date:
Fri Jul 14 17:02:05 2017 +0000
Revision:
15:f715e3067fa8
Parent:
14:7fd12867824f 
minor debugging changes

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