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@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?

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 */
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_ */