Revision 12:ab8a80bcfd64, committed 2017-07-11

Comitter:

sgnezdov

Date:

Tue Jul 11 00:15:05 2017 +0000

Parent:

11:4336cd18cce9

Child:

13:b06f7b37fff4

Commit message:

Changed LinkedList implementation to be in header (for templates), made node hard coded and data is part of template

Changed in this revision

--- a/LinkedList.cpp	Mon Jul 10 16:46:46 2017 +0000
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,213 +0,0 @@
-/**
- * @file    LinkedList.cpp
- * @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.
- */
-
-#include "LinkedList.h"    // api wrapper
-
-template<class retT>
-LinkedList<retT>::LinkedList()
-{
-    // clear the member
-    _head = 0;
-
-    return;
-}
-
-template<class retT>
-LinkedList<retT>::~LinkedList()
-{
-    // free any memory that is on the heap
-    while(remove(1) != NULL);
-
-    return;
-}
-
-template<class retT>
-retT *LinkedList<retT>::push(void *data)
-{
-    retT *new_node = new retT [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;
-}
-
-template<class retT>
-retT *LinkedList<retT>::insertOrdered(void *data, bool (isBigger)(void* data1, void *data2))
-{
-    retT *new_node = new retT [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;
-    }
-
-    retT *current = _head;
-    retT *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;
-}
-
-template<class retT>
-retT *LinkedList<retT>::append(void *data)
-{
-    retT *current = _head;
-    retT *new_node = new retT [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;
-}
-
-template<class retT>
-retT *LinkedList<retT>::remove(uint32_t loc)
-{
-    retT *current = _head;
-    retT *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;
-}
-
-template<class retT>
-retT *LinkedList<retT>::pop(uint32_t loc)
-{
-    retT *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;
-}
-
-template<class retT>
-uint32_t LinkedList<retT>::length(void)
-{
-    int32_t count = 0;
-    retT *current = _head;
-    //loop until the end of the list is found
-    while (current != 0)
-    {
-        ++count;
-        current = current->next;
-    }
-
-    return count;
-}
-
-// pre-define the type for the linker
-template class LinkedList<node>;
-
-
-
-
-

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