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@10:cb2e50ed6945, 2017-07-07 (annotated)
- Committer:
- sgnezdov
- Date:
- Fri Jul 07 23:36:03 2017 +0000
- Revision:
- 10:cb2e50ed6945
- Parent:
- 9:b173aed98988
- Child:
- 11:4336cd18cce9
marked code as code
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 | |
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 | */ |
sam_grove | 0:3f64a15357ac | 33 | struct node |
sam_grove | 0:3f64a15357ac | 34 | { |
sam_grove | 0:3f64a15357ac | 35 | void *data; /*!< pointer to list member data */ |
sam_grove | 0:3f64a15357ac | 36 | struct node *next; /*!< pointer to the next list member */ |
sam_grove | 0:3f64a15357ac | 37 | }; |
sam_grove | 0:3f64a15357ac | 38 | |
sgnezdov | 8:918b196b0ac4 | 39 | ///** Returns true if data1 shall be inserted before data 2. |
sgnezdov | 8:918b196b0ac4 | 40 | //*/ |
sgnezdov | 8:918b196b0ac4 | 41 | //typedef bool insertAtFunc(void *data1, void *data2); |
sgnezdov | 8:918b196b0ac4 | 42 | |
sam_grove | 0:3f64a15357ac | 43 | /** Example using the LinkedList Class |
sam_grove | 0:3f64a15357ac | 44 | * @code |
sam_grove | 1:a032c0392ba1 | 45 | * #include "mbed.h" |
sam_grove | 1:a032c0392ba1 | 46 | * #include "LinkedList.h" |
sam_grove | 1:a032c0392ba1 | 47 | * |
sam_grove | 1:a032c0392ba1 | 48 | * LinkedList<node>list; |
sam_grove | 1:a032c0392ba1 | 49 | * |
sam_grove | 1:a032c0392ba1 | 50 | * int main() |
sam_grove | 1:a032c0392ba1 | 51 | * { |
sam_grove | 1:a032c0392ba1 | 52 | * node *tmp; |
sam_grove | 1:a032c0392ba1 | 53 | * |
sam_grove | 1:a032c0392ba1 | 54 | * list.push((char *)"Two\n"); |
sam_grove | 1:a032c0392ba1 | 55 | * list.append((char *)"Three\n"); |
sam_grove | 1:a032c0392ba1 | 56 | * list.append((char *)"Four\n"); |
sam_grove | 1:a032c0392ba1 | 57 | * list.push((char*)"One\n"); |
sam_grove | 1:a032c0392ba1 | 58 | * list.append((char*)"Five\n"); |
sam_grove | 1:a032c0392ba1 | 59 | * |
sam_grove | 3:c14e7a918e21 | 60 | * for(int i=1; i<=list.length(); i++) |
sam_grove | 1:a032c0392ba1 | 61 | * { |
sam_grove | 1:a032c0392ba1 | 62 | * tmp = list.pop(i); |
sam_grove | 1:a032c0392ba1 | 63 | * printf("%s", (char *)tmp->data); |
sam_grove | 1:a032c0392ba1 | 64 | * } |
sam_grove | 1:a032c0392ba1 | 65 | * |
sam_grove | 1:a032c0392ba1 | 66 | * error("done\n"); |
sam_grove | 1:a032c0392ba1 | 67 | * } |
sam_grove | 0:3f64a15357ac | 68 | * @endcode |
sam_grove | 0:3f64a15357ac | 69 | */ |
sgnezdov | 9:b173aed98988 | 70 | |
sgnezdov | 9:b173aed98988 | 71 | /** Example using new insertAsc function: |
sgnezdov | 10:cb2e50ed6945 | 72 | * @code |
sgnezdov | 9:b173aed98988 | 73 | |
sgnezdov | 9:b173aed98988 | 74 | #include "mbed.h" |
sgnezdov | 9:b173aed98988 | 75 | #include "LinkedList.h" |
sgnezdov | 9:b173aed98988 | 76 | |
sgnezdov | 9:b173aed98988 | 77 | bool ascending(void *n1, void *n2) |
sgnezdov | 9:b173aed98988 | 78 | { |
sgnezdov | 9:b173aed98988 | 79 | int *d1 = (int*)n1; |
sgnezdov | 9:b173aed98988 | 80 | int *d2 = (int*)n2; |
sgnezdov | 9:b173aed98988 | 81 | bool rv = *d1 >= *d2; |
sgnezdov | 9:b173aed98988 | 82 | printf("(%d %d:%d)", *d1, *d2, rv); |
sgnezdov | 9:b173aed98988 | 83 | return rv; |
sgnezdov | 9:b173aed98988 | 84 | } |
sgnezdov | 9:b173aed98988 | 85 | |
sgnezdov | 9:b173aed98988 | 86 | void printList(LinkedList<node> &list, const char* msg) |
sgnezdov | 9:b173aed98988 | 87 | { |
sgnezdov | 9:b173aed98988 | 88 | printf("%s: ", msg); |
sgnezdov | 9:b173aed98988 | 89 | for(int i=1; i<=list.length(); i++) |
sgnezdov | 9:b173aed98988 | 90 | { |
sgnezdov | 9:b173aed98988 | 91 | node *tmp = list.pop(i); |
sgnezdov | 9:b173aed98988 | 92 | printf("%d ", *(int*)tmp->data); |
sgnezdov | 9:b173aed98988 | 93 | } |
sgnezdov | 9:b173aed98988 | 94 | printf("\n"); |
sgnezdov | 9:b173aed98988 | 95 | } |
sgnezdov | 9:b173aed98988 | 96 | |
sgnezdov | 9:b173aed98988 | 97 | int main() |
sgnezdov | 9:b173aed98988 | 98 | { |
sgnezdov | 9:b173aed98988 | 99 | printf("\nJob Scheduler Demo\n"); |
sgnezdov | 9:b173aed98988 | 100 | |
sgnezdov | 9:b173aed98988 | 101 | node *tmp; |
sgnezdov | 9:b173aed98988 | 102 | |
sgnezdov | 9:b173aed98988 | 103 | int n0 = 0; |
sgnezdov | 9:b173aed98988 | 104 | int n1 = 1; |
sgnezdov | 9:b173aed98988 | 105 | int n1B = 1; |
sgnezdov | 9:b173aed98988 | 106 | int n2 = 2; |
sgnezdov | 9:b173aed98988 | 107 | int n3 = 3; |
sgnezdov | 9:b173aed98988 | 108 | int n4 = 4; |
sgnezdov | 9:b173aed98988 | 109 | |
sgnezdov | 9:b173aed98988 | 110 | LinkedList<node>list; |
sgnezdov | 9:b173aed98988 | 111 | |
sgnezdov | 9:b173aed98988 | 112 | tmp = list.insertAsc(&n2, ascending); |
sgnezdov | 9:b173aed98988 | 113 | if (NULL == tmp) { |
sgnezdov | 9:b173aed98988 | 114 | error("insertAsc did not insert a node"); |
sgnezdov | 9:b173aed98988 | 115 | } |
sgnezdov | 9:b173aed98988 | 116 | printList(list, "exp 2"); |
sgnezdov | 9:b173aed98988 | 117 | |
sgnezdov | 9:b173aed98988 | 118 | tmp = list.insertAsc(&n1, ascending); |
sgnezdov | 9:b173aed98988 | 119 | if (NULL == tmp) { |
sgnezdov | 9:b173aed98988 | 120 | error("insertAsc did not insert a node"); |
sgnezdov | 9:b173aed98988 | 121 | } |
sgnezdov | 9:b173aed98988 | 122 | printList(list, "exp 1,2"); |
sgnezdov | 9:b173aed98988 | 123 | |
sgnezdov | 9:b173aed98988 | 124 | tmp = list.insertAsc(&n4, ascending); |
sgnezdov | 9:b173aed98988 | 125 | if (NULL == tmp) { |
sgnezdov | 9:b173aed98988 | 126 | error("insertAsc did not insert a node"); |
sgnezdov | 9:b173aed98988 | 127 | } |
sgnezdov | 9:b173aed98988 | 128 | printList(list, "exp 1,2,4"); |
sgnezdov | 9:b173aed98988 | 129 | |
sgnezdov | 9:b173aed98988 | 130 | tmp = list.insertAsc(&n3, ascending); |
sgnezdov | 9:b173aed98988 | 131 | if (NULL == tmp) { |
sgnezdov | 9:b173aed98988 | 132 | error("insertAsc did not insert a node"); |
sgnezdov | 9:b173aed98988 | 133 | } |
sgnezdov | 9:b173aed98988 | 134 | printList(list, "exp 1,2,3,4"); |
sgnezdov | 9:b173aed98988 | 135 | |
sgnezdov | 9:b173aed98988 | 136 | tmp = list.insertAsc(&n0, ascending); |
sgnezdov | 9:b173aed98988 | 137 | if (NULL == tmp) { |
sgnezdov | 9:b173aed98988 | 138 | error("insertAsc did not insert a node"); |
sgnezdov | 9:b173aed98988 | 139 | } |
sgnezdov | 9:b173aed98988 | 140 | printList(list, "exp 0,1,2,3,4"); |
sgnezdov | 9:b173aed98988 | 141 | |
sgnezdov | 9:b173aed98988 | 142 | tmp = list.insertAsc(&n1B, ascending); |
sgnezdov | 9:b173aed98988 | 143 | if (NULL == tmp) { |
sgnezdov | 9:b173aed98988 | 144 | error("insertAsc did not insert a node"); |
sgnezdov | 9:b173aed98988 | 145 | } |
sgnezdov | 9:b173aed98988 | 146 | printList(list, "exp 0,1,1,2,3,4"); |
sgnezdov | 9:b173aed98988 | 147 | |
sgnezdov | 9:b173aed98988 | 148 | tmp = list.pop(2); |
sgnezdov | 9:b173aed98988 | 149 | if (tmp->data != &n1) { |
sgnezdov | 9:b173aed98988 | 150 | error("pos 2 is not n1\n"); |
sgnezdov | 9:b173aed98988 | 151 | } |
sgnezdov | 9:b173aed98988 | 152 | printf("n1 is good\n"); |
sgnezdov | 9:b173aed98988 | 153 | |
sgnezdov | 9:b173aed98988 | 154 | tmp = list.pop(3); |
sgnezdov | 9:b173aed98988 | 155 | if (tmp->data != &n1B) { |
sgnezdov | 9:b173aed98988 | 156 | error("pos3 is not n1B"); |
sgnezdov | 9:b173aed98988 | 157 | } |
sgnezdov | 9:b173aed98988 | 158 | printf("n1B is good\n"); |
sgnezdov | 9:b173aed98988 | 159 | |
sgnezdov | 9:b173aed98988 | 160 | error("done\n"); |
sgnezdov | 9:b173aed98988 | 161 | |
sgnezdov | 9:b173aed98988 | 162 | exit(0); |
sgnezdov | 9:b173aed98988 | 163 | } |
sgnezdov | 9:b173aed98988 | 164 | |
sgnezdov | 10:cb2e50ed6945 | 165 | * @endcode |
sgnezdov | 9:b173aed98988 | 166 | */ |
sam_grove | 0:3f64a15357ac | 167 | |
sam_grove | 0:3f64a15357ac | 168 | /** |
sam_grove | 0:3f64a15357ac | 169 | * @class LinkedList |
sam_grove | 0:3f64a15357ac | 170 | * @brief API abstraction for a Linked List |
sam_grove | 0:3f64a15357ac | 171 | */ |
sam_grove | 0:3f64a15357ac | 172 | template<class retT> |
sam_grove | 0:3f64a15357ac | 173 | class LinkedList |
sam_grove | 0:3f64a15357ac | 174 | { |
sam_grove | 0:3f64a15357ac | 175 | protected: |
sam_grove | 0:3f64a15357ac | 176 | retT *_head; |
sam_grove | 0:3f64a15357ac | 177 | |
sam_grove | 0:3f64a15357ac | 178 | public: |
sam_grove | 0:3f64a15357ac | 179 | /** Create the LinkedList object |
sam_grove | 0:3f64a15357ac | 180 | */ |
sam_grove | 0:3f64a15357ac | 181 | LinkedList(); |
sam_grove | 0:3f64a15357ac | 182 | |
sam_grove | 0:3f64a15357ac | 183 | /** Deconstructor for the LinkedList object |
sam_grove | 0:3f64a15357ac | 184 | * Removes any members |
sam_grove | 0:3f64a15357ac | 185 | */ |
sam_grove | 0:3f64a15357ac | 186 | ~LinkedList(); |
sam_grove | 0:3f64a15357ac | 187 | |
sam_grove | 0:3f64a15357ac | 188 | /** Add a member to the begining of the list |
sam_grove | 0:3f64a15357ac | 189 | * @param data - Some data type that is added to the list |
sam_grove | 0:3f64a15357ac | 190 | * @return The member that was just inserted (NULL if empty) |
sam_grove | 0:3f64a15357ac | 191 | */ |
sam_grove | 0:3f64a15357ac | 192 | retT *push(void *data); |
sam_grove | 0:3f64a15357ac | 193 | |
sgnezdov | 8:918b196b0ac4 | 194 | /** Add a member to some position based on sort condition. |
sgnezdov | 8:918b196b0ac4 | 195 | * The list will be iterated from _head to end and the moment inserted |
sgnezdov | 8:918b196b0ac4 | 196 | * data is NOT smaller than current node's data, then |
sgnezdov | 8:918b196b0ac4 | 197 | * data will be inserted in front of current node. |
sgnezdov | 8:918b196b0ac4 | 198 | * This will preserve ascending order of data. |
sgnezdov | 8:918b196b0ac4 | 199 | * @param data - some data type that is added to the list |
sgnezdov | 8:918b196b0ac4 | 200 | * @param isBigger - comparator function returns true if data1 is bigger |
sgnezdov | 8:918b196b0ac4 | 201 | * than data2 and false otherwise. If data1 equals data2, then ">" comparision |
sgnezdov | 8:918b196b0ac4 | 202 | * will result in LIFO order. Using ">=" operator in the function |
sgnezdov | 8:918b196b0ac4 | 203 | * results in "FIFO" order and thus it preserves order in which items |
sgnezdov | 8:918b196b0ac4 | 204 | * were added to the list. |
sgnezdov | 8:918b196b0ac4 | 205 | * @return The member that was just inserted (NULL if not inserted). |
sgnezdov | 8:918b196b0ac4 | 206 | */ |
sgnezdov | 8:918b196b0ac4 | 207 | retT *insertAsc(void *data, bool (isBigger)(void* data1, void *data2)); |
sam_grove | 0:3f64a15357ac | 208 | |
sam_grove | 0:3f64a15357ac | 209 | /** Add a member to the end of the list |
sam_grove | 0:3f64a15357ac | 210 | * @param data - Some data type that is added to the list |
sam_grove | 0:3f64a15357ac | 211 | * @return The member that was just inserted (NULL if empty) |
sam_grove | 0:3f64a15357ac | 212 | */ |
sam_grove | 0:3f64a15357ac | 213 | retT *append(void *data); |
sam_grove | 0:3f64a15357ac | 214 | |
sam_grove | 0:3f64a15357ac | 215 | /** Remove a member from the list |
sam_grove | 0:3f64a15357ac | 216 | * @param loc - The location of the member to remove |
sam_grove | 0:3f64a15357ac | 217 | * @return The head of the list |
sam_grove | 0:3f64a15357ac | 218 | */ |
sam_grove | 0:3f64a15357ac | 219 | retT *remove(uint32_t loc); |
sam_grove | 0:3f64a15357ac | 220 | |
sam_grove | 0:3f64a15357ac | 221 | /** Get access to a member from the list |
sam_grove | 0:3f64a15357ac | 222 | * @param loc - The location of the member to access |
sam_grove | 0:3f64a15357ac | 223 | * @return The member that was just requested (NULL if empty or out of bounds) |
sam_grove | 0:3f64a15357ac | 224 | */ |
sam_grove | 0:3f64a15357ac | 225 | retT *pop(uint32_t loc); |
sam_grove | 0:3f64a15357ac | 226 | |
sam_grove | 0:3f64a15357ac | 227 | /** Get the length of the list |
sam_grove | 0:3f64a15357ac | 228 | * @return The number of members in the list |
sam_grove | 0:3f64a15357ac | 229 | */ |
sam_grove | 0:3f64a15357ac | 230 | uint32_t length(void); |
sam_grove | 0:3f64a15357ac | 231 | }; |
sam_grove | 0:3f64a15357ac | 232 | |
sam_grove | 0:3f64a15357ac | 233 | #endif /* LINKEDLIST_H_ */ |