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
Diff: LinkedList.h
- Revision:
- 12:ab8a80bcfd64
- Parent:
- 11:4336cd18cce9
- Child:
- 13:b06f7b37fff4
--- a/LinkedList.h Mon Jul 10 16:46:46 2017 +0000 +++ b/LinkedList.h Tue Jul 11 00:15:05 2017 +0000 @@ -30,9 +30,10 @@ * @struct node * @brief The Linked List structure */ +template<typename T> struct node { - void *data; /*!< pointer to list member data */ + T *data; /*!< pointer to list member data */ struct node *next; /*!< pointer to the next list member */ }; @@ -74,24 +75,6 @@ #include "mbed.h" #include "LinkedList.h" -bool ascending(void *n1, void *n2) -{ - int *d1 = (int*)n1; - int *d2 = (int*)n2; - bool rv = *d1 >= *d2; - printf("(%d %d:%d)", *d1, *d2, rv); - return rv; -} - -bool descending(void *n1, void *n2) -{ - int *d1 = (int*)n1; - int *d2 = (int*)n2; - bool rv = *d1 <= *d2; - printf("(%d %d:%d)", *d1, *d2, rv); - return rv; -} - void printList(LinkedList<node> &list, const char* msg) { printf("%s: ", msg); @@ -103,9 +86,18 @@ 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 *tmp; + node<int> *tmp; int n0 = 0; int n1 = 1; @@ -114,7 +106,7 @@ int n3 = 3; int n4 = 4; - LinkedList<node>list; + LinkedList<int>list; tmp = list.insertOrdered(&n2, ascending); if (NULL == tmp) { @@ -165,9 +157,18 @@ 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 *tmp; + node<int> *tmp; int n0 = 0; int n1 = 1; @@ -176,7 +177,7 @@ int n3 = 3; int n4 = 4; - LinkedList<node>l; + LinkedList<int>l; tmp = l.insertOrdered(&n2, descending); if (NULL == tmp) { @@ -248,27 +249,49 @@ * @class LinkedList * @brief API abstraction for a Linked List */ -template<class retT> +template<typename T> class LinkedList { protected: - retT *_head; + node<T> *_head; public: /** Create the LinkedList object */ - LinkedList(); + LinkedList() { + // clear the member + _head = 0; + } + /** Deconstructor for the LinkedList object * Removes any members */ - ~LinkedList(); + ~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) */ - retT *push(void *data); + 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 @@ -290,30 +313,179 @@ * * @return The member that was just inserted (NULL if not inserted). */ - retT *insertOrdered(void *data, bool (isBigger)(void* data1, void *data2)); + 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; + printf("[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 + printf("[insertAsc] insert at end\n"); + current->next = new_node; + return new_node; + } + prev = current; + current = current->next; + } + if (0 == prev) { + printf("[insertAsc] insert at start\n"); + new_node->next = _head; + _head = new_node; + return new_node; + } + printf("[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) */ - retT *append(void *data); + 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 */ - retT *remove(uint32_t loc); + 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) */ - retT *pop(uint32_t loc); + 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)) + { + if (_head == NULL) { + 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)) { + current = current->next; + if (current->next == NULL) { + return NULL; + } + } + return current; + } /** Get the length of the list * @return The number of members in the list */ - uint32_t length(void); + 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_ */