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
- Committer:
- sgnezdov
- Date:
- 2017-07-13
- Revision:
- 14:7fd12867824f
- Parent:
- 13:b06f7b37fff4
- Child:
- 15:f715e3067fa8
File content as of revision 14:7fd12867824f:
/** * @file LinkedList.h * @brief Core Utility - Templated Linked List class * @author sam grove * @version 1.0 * @see * * Copyright (c) 2013 * * Licensed under the Apache License, Version 2.0 (the "License"); * you may not use this file except in compliance with the License. * You may obtain a copy of the License at * * http://www.apache.org/licenses/LICENSE-2.0 * * Unless required by applicable law or agreed to in writing, software * distributed under the License is distributed on an "AS IS" BASIS, * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. * See the License for the specific language governing permissions and * limitations under the License. */ #ifndef LINKEDLIST_H_ #define LINKEDLIST_H_ #include <stdint.h> #include "mbed.h" #define DBG_LLIST 0 #if DBG_LLIST #define DBG(...) do{debug("[%s:%d]", __PRETTY_FUNCTION__,__LINE__);debug(__VA_ARGS__);} while(0); #else #define DBG(...) while(0); #endif /** * @struct node * @brief The Linked List structure */ template<typename T> struct node { T *data; /*!< pointer to list member data */ struct node *next; /*!< pointer to the next list member */ }; ///** Returns true if data1 shall be inserted before data 2. //*/ //typedef bool insertAtFunc(void *data1, void *data2); /** Example using the LinkedList Class * @code * #include "mbed.h" * #include "LinkedList.h" * * LinkedList<node>list; * * int main() * { * node *tmp; * * list.push((char *)"Two\n"); * list.append((char *)"Three\n"); * list.append((char *)"Four\n"); * list.push((char*)"One\n"); * list.append((char*)"Five\n"); * * for(int i=1; i<=list.length(); i++) * { * tmp = list.pop(i); * printf("%s", (char *)tmp->data); * } * * error("done\n"); * } * @endcode */ /** Example using new insertOrdered function: * @code #include "mbed.h" #include "LinkedList.h" void printList(LinkedList<node> &list, const char* msg) { printf("%s: ", msg); for(int i=1; i<=list.length(); i++) { node *tmp = list.pop(i); printf("%d ", *(int*)tmp->data); } printf("\n"); } bool ascending(int *n1, int *n2) { int *d1 = (int*)n1; int *d2 = (int*)n2; bool rv = *d1 <= *d2; printf("(%d %d:%d)", *d1, *d2, rv); return rv; } void testAscending() { node<int> *tmp; int n0 = 0; int n1 = 1; int n1B = 1; int n2 = 2; int n3 = 3; int n4 = 4; LinkedList<int>list; tmp = list.insertOrdered(&n2, ascending); if (NULL == tmp) { error("insertOrdered did not insert a node"); } printList(list, "exp 2"); tmp = list.insertOrdered(&n1, ascending); if (NULL == tmp) { error("insertOrdered did not insert a node"); } printList(list, "exp 1,2"); tmp = list.insertOrdered(&n4, ascending); if (NULL == tmp) { error("insertOrdered did not insert a node"); } printList(list, "exp 1,2,4"); tmp = list.insertOrdered(&n3, ascending); if (NULL == tmp) { error("insertOrdered did not insert a node"); } printList(list, "exp 1,2,3,4"); tmp = list.insertOrdered(&n0, ascending); if (NULL == tmp) { error("insertOrdered did not insert a node"); } printList(list, "exp 0,1,2,3,4"); tmp = list.insertOrdered(&n1B, ascending); if (NULL == tmp) { error("insertOrdered did not insert a node"); } printList(list, "exp 0,1,1,2,3,4"); tmp = list.pop(2); if (tmp->data != &n1) { error("pos 2 is not n1\n"); } printf("n1 is good\n"); tmp = list.pop(3); if (tmp->data != &n1B) { error("pos3 is not n1B"); } printf("n1B is good\n"); } bool descending(int *n1, int *n2) { int *d1 = (int*)n1; int *d2 = (int*)n2; bool rv = *d1 <= *d2; printf("(%d %d:%d)", *d1, *d2, rv); return rv; } void testDescending() { node<int> *tmp; int n0 = 0; int n1 = 1; int n1B = 1; int n2 = 2; int n3 = 3; int n4 = 4; LinkedList<int>l; tmp = l.insertOrdered(&n2, descending); if (NULL == tmp) { error("insertOrdered did not insert a node"); } printList(l, "exp 2"); tmp = l.insertOrdered(&n1, descending); if (NULL == tmp) { error("insertOrdered did not insert a node"); } printList(l, "exp 2,1"); tmp = l.insertOrdered(&n4, descending); if (NULL == tmp) { error("insertOrdered did not insert a node"); } printList(l, "exp 4,2,1"); tmp = l.insertOrdered(&n3, descending); if (NULL == tmp) { error("insertOrdered did not insert a node"); } printList(l, "exp 4,3,2,1"); tmp = l.insertOrdered(&n0, descending); if (NULL == tmp) { error("insertOrdered did not insert a node"); } printList(l, "exp 4,3,2,1,0"); tmp = l.insertOrdered(&n1B, descending); if (NULL == tmp) { error("insertOrdered did not insert a node"); } printList(l, "exp 4,3,2,1,1,0"); tmp = l.pop(4); if (tmp->data != &n1) { error("pos 2 is not n1\n"); } printf("n1 is good\n"); tmp = l.pop(5); if (tmp->data != &n1B) { error("pos3 is not n1B"); } printf("n1B is good\n"); } int main() { printf("\nJob Scheduler Demo\n"); testDescending(); error("done\n"); exit(0); } * @endcode */ /** * @class LinkedList * @brief API abstraction for a Linked List */ template<typename T> class LinkedList { protected: node<T> *_head; public: /** Create the LinkedList object */ LinkedList() { // clear the member _head = 0; } /** Deconstructor for the LinkedList object * Removes any members */ ~LinkedList() { // free any memory that is on the heap while(remove(1) != NULL); } /** Add a member to the begining of the list * @param data - Some data type that is added to the list * @return The member that was just inserted (NULL if empty) */ node<T> *push(T *data) { node<T> *new_node = new node<T>[1]; // make sure the new object was allocated if (0 == new_node) { error("Memory allocation failed\n"); } // update the next item in the list to the current head new_node->next = _head; // store the address to the linked datatype new_node->data = data; _head = new_node; return _head; } /** Add a member to some position based on sort condition. * The list will be iterated from _head to end and the moment inserted * data is NOT smaller than current node's data, then * data will be inserted in front of current node. * This will preserve ascending order of data. * @param data - some data type that is added to the list * @param isBigger - comparator function returns true if data1 is bigger * than data2 and false otherwise. * If data1 equals data2, then ">" comparision * will result in LIFO order. Using ">=" operator in the function * results in "FIFO" order and thus it preserves order in which items * were added to the list. * * If isBigger function is implemented with data1 < data2, then * result insert will be in descending order. If data1 equals data2, then * LIFO order is established. * If data1 <= data2, then FIFO order is preserved when data1 equals data2. * * @return The member that was just inserted (NULL if not inserted). */ node<T> *insertOrdered(T *data, bool (isBigger)(T* data1, T *data2)) { node<T> *new_node = new node<T> [1]; // make sure the new object was allocated if (0 == new_node) { error("Memory allocation failed\n"); } // store the address to the linked datatype new_node->data = data; // clear the next pointer new_node->next = 0; // check for an empty list if (0 == _head) { _head = new_node; DBG("[insertAsc] set as head\n"); return new_node; } node<T> *current = _head; node<T> *prev = 0; // move to the item we want to insert while (isBigger(data, current->data)) { // while(true) execute the following // data being inserted is smaller than current->data if (0 == current->next) { // there is no more data DBG("[insertAsc] insert at end\n"); current->next = new_node; return new_node; } prev = current; current = current->next; } if (0 == prev) { DBG("[insertAsc] insert at start\n"); new_node->next = _head; _head = new_node; return new_node; } DBG("[insertAsc] insert inside\n"); new_node->next = current; prev->next = new_node; return new_node; } /** Add a member to the end of the list * @param data - Some data type that is added to the list * @return The member that was just inserted (NULL if empty) */ node<T> *append(T *data) { node<T> *current = _head; node<T> *new_node = new node<T> [1]; // make sure the new object was allocated if (0 == new_node) { error("Memory allocation failed\n"); } // store the address to the linked datatype new_node->data = data; // clear the next pointer new_node->next = 0; // check for an empty list if (0 == current) { _head = new_node; return _head; } else { // look for the end of the list while (current->next != 0) { current = current->next; } // and then add the new item to the list current->next = new_node; } return current->next; } /** Remove a member from the list * @param loc - The location of the member to remove * @return The head of the list */ node<T> *remove(uint32_t loc) { node<T> *current = _head; node<T> *prev = 0; // make sure we have an item to remove if ((loc <= length()) && (loc > 0)) { // move to the item we want to delete if (1 == loc) { _head = current->next; delete [] current; } else { for (uint32_t i=2; i<=loc; ++i) { prev = current; current = current->next; } // store the item + 1 to replace what we are deleting prev->next = current->next; delete [] current; } } return _head; } /** Get access to a member from the list * @param loc - The location of the member to access * @return The member that was just requested (NULL if empty or out of bounds) */ node<T> *pop(uint32_t loc) { node<T> *current = _head; // make sure we have something in the location if ((loc > length()) || (loc == 0)) { return 0; } // and if so jump down the list for (uint32_t i=2; i<=loc; ++i) { current = current->next; } return current; } node<T> *pop(T* data, bool (isEqual)(T* data1, T* data2)) { DBG("..pop started\n"); if (_head == NULL) { DBG(".._head is NULL\n"); return NULL; } node<T> *current = _head; // make sure we have something in the location // and if so jump down the list while(!isEqual(current->data, data)) { DBG("..next current\n"); if (current->next == NULL) { DBG("..next is NULL; returning NULL\n"); return NULL; } current = current->next; } DBG("..found\n"); return current; } /** Get the length of the list * @return The number of members in the list */ uint32_t length(void) { int32_t count = 0; node<T> *current = _head; //loop until the end of the list is found while (current != 0) { ++count; current = current->next; } return count; } }; #endif /* LINKEDLIST_H_ */