File content as of revision 10:cb2e50ed6945:

/**
 * @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"

/**
 *  @struct node
 *  @brief The Linked List structure
 */ 
struct node
{
    void *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 insertAsc function:
 * @code
 
 #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;
}

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");
}

int main()
{
    printf("\nJob Scheduler Demo\n");
    
    node *tmp;
    
    int n0 = 0;
    int n1 = 1;
    int n1B = 1;
    int n2 = 2;
    int n3 = 3;
    int n4 = 4;
    
    LinkedList<node>list;
    
    tmp = list.insertAsc(&n2, ascending);
    if (NULL == tmp) {
        error("insertAsc did not insert a node");
    }
    printList(list, "exp 2");
    
    tmp = list.insertAsc(&n1, ascending);
    if (NULL == tmp) {
        error("insertAsc did not insert a node");
    }
    printList(list, "exp 1,2");

    tmp = list.insertAsc(&n4, ascending);
    if (NULL == tmp) {
        error("insertAsc did not insert a node");
    }
    printList(list, "exp 1,2,4");

    tmp = list.insertAsc(&n3, ascending);
    if (NULL == tmp) {
        error("insertAsc did not insert a node");
    }
    printList(list, "exp 1,2,3,4");

    tmp = list.insertAsc(&n0, ascending);
    if (NULL == tmp) {
        error("insertAsc did not insert a node");
    }
    printList(list, "exp 0,1,2,3,4");

    tmp = list.insertAsc(&n1B, ascending);
    if (NULL == tmp) {
        error("insertAsc 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");

    error("done\n");
 
    exit(0);
}

 * @endcode
 */

/**
 *  @class LinkedList
 *  @brief API abstraction for a Linked List
 */ 
template<class retT>
class LinkedList
{
protected:
    retT *_head;

public:
    /** Create the LinkedList object
     */   
    LinkedList();
    
    /** Deconstructor for the LinkedList object
     *  Removes any members
     */ 
    ~LinkedList();

    /** 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);
    
    /** 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.
    * @return The member that was just inserted (NULL if not inserted).
    */
    retT *insertAsc(void *data, bool (isBigger)(void* data1, void *data2));
    
    /** 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);
    
    /** 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);
    
    /** 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);
    
    /** Get the length of the list
     *  @return The number of members in the list
     */
    uint32_t length(void);
};

#endif /* LINKEDLIST_H_ */