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.
Fork of LinkedList by
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?
User | Revision | Line number | New 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_ */ |