Listas enlazadas en Arduino (primera versión)

LList <tipo> lista;

/**
*************************************************************
* @file ArduinoList.pde
* Another implementation of linked lists to use in Arduino.
*    Copyright (C) 2011 Gaspar Fernández
*
*    This program is free software: you can redistribute it and/or modify
*    it under the terms of the GNU General Public License as published by
*    the Free Software Foundation, either version 3 of the License, or
*    (at your option) any later version.
*
*    This program is distributed in the hope that it will be useful,
*    but WITHOUT ANY WARRANTY; without even the implied warranty of
*    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
*    GNU General Public License for more details.
*
*    You should have received a copy of the GNU General Public License
*    along with this program.  If not, see <http://www.gnu.org/licenses/>.
*
* @brief Linked list implementation for Arduino
*
* Features:
*   - Can access to head and tail directly
*   - Can pop back and front from this class
*   - Can access any item from the item number
*   - Can set a callback function when an error occurs
*
* @author Gaspar Fernández <blakeyed@totaki.com>
* @web https://poesiabinaria.net
* @version 0.1
* @date 27 nov 2011
* Change history
*
* To-do:
*   - Better control over non-critical errors, maybe another callback
*   - Pre-defined error methods: by serial, by output leds...
*************************************************************/

#define LLIST_ERROR_NOMEMORY     1 // Not enough memory to insert element
#define LLIST_ERROR_NOTAIL       2 // Can't get last items
#define LLIST_ERROR_NOFRONT      3 // Can't get head items
#define LLIST_ERROR_NOITEMS      4 // List empty, can't read items
#define LLIST_ERROR_NEITEMS      5 // Not enough items (pos>=sz)

template <typename Type>
class LList
{
public:
  typedef void (*ErrorCallback)(int);

  // We can add more error types
  enum ListErrorType
    {
      NO_ERROR_REPORTING,   // No error reporting
      CALLBACK          // Errors will trigger a callback
    };

  // Destruction. Clear data
  ~LList();

  // Initialization
  LList();

  // Inserts new item in the last position
  void push_back(const Type item);
  // Is the list empty?
  inline bool isEmpty() const;
  // Returns the size of the list
  inline int size();
  // Returns the last item
  inline Type back();
  // Returns the first item
  inline Type front();
  // Return the last item and delete it
  Type pop_back();
  // Return the first item and delete it
  Type pop_front();

  // Get the item at position pos
  Type getElement(unsigned pos);
  // Insert a new item at position pos
  void insert(int pos, Type item);
  // set error callback function
  void setErrorCallback(ErrorCallback cback);
  // no error reporting
  void setNoErrorReporting();
  // clears the list
  void clear();
private:
  // Reports an error
  void report_error(int err);
 
  // Deletes a list when there is only one element
  void delete_list();

  typedef struct node
  {
    Type item;
    node *next;
  } node;

  node *head;           // Pointer to the head
  node *tail;           // Pointer to the tail
  int sz;           // List size
  ListErrorType errorType; 
  ErrorCallback ecback;     // Callback when reporting an error
};

template <typename Type>
LList<Type>::LList()
{
  head=NULL;
  tail=NULL;
  sz=0;
  errorType=NO_ERROR_REPORTING;
}

template <typename Type>
LList<Type>::~LList()
{
  clear();          // Clears the list before destroying
}

template <typename Type>
void LList<Type>::push_back(const Type item)
{
  node *aux=tail;
 
  // Reserve memory for a new node
  tail=(node*)malloc(sizeof(node));
  if (tail==NULL)
    {
      report_error(LLIST_ERROR_NOMEMORY);
      return;
    }

  // Stores the item information
  tail->item=item;
  tail->next=NULL;

  // Link to the list
  if (isEmpty())
    head=tail;
  else
    aux->next=tail;

  sz++;

}

template <typename Type>
bool LList<Type>::isEmpty() const
{
  return (sz==0);       // (sz==0) = EMPTY
}

template <typename Type>
int LList<Type>::size()
{
  return sz;
}

template <typename Type>
inline Type LList<Type>::back()
{
  if (isEmpty())        // List empty = No last item
    {
      Type t;
      report_error(LLIST_ERROR_NOTAIL);
      return t;
    }

  return tail->item;
}

template <typename Type>
inline Type LList<Type>::front()
{
  if (isEmpty())        // List empty = No first item
    {
      Type t;
      report_error(LLIST_ERROR_NOFRONT);
      return t;
    }

  return head->item;
}

template <typename Type>
Type LList<Type>::pop_back()
{
  node *aux=head;
  Type t;

  if (isEmpty())        // List empty = No last item
    {
      report_error(LLIST_ERROR_NOTAIL);
      return t;
    }
 
  if (head==tail)       // If there is only 1 item
    {
      t=head->item;
      delete_list();
      return t;
    }
  else
    {               // More than one item
      while (aux->next!=tail)   // Searches for the item previous to the last
    aux=aux->next;
     
      t=tail->item;     // I will return the tail item
      free(tail);      
      tail=aux;         // Define the new tail
      tail->next=NULL;
      sz--;         // 1 item less

      return t;
    }
}

template <typename Type>
Type LList<Type>::pop_front()
{
  Type t;
  node *aux=head;
 
  if (isEmpty())        // List empty = No head
    {
      report_error(LLIST_ERROR_NOFRONT);
      return t;
    }

  t=aux->item;          // I will return the head
  head=head->next;      // The new head is the item after the head
  free(aux);
  if (head==NULL)       // If I had deleted the last item, replace the tail
    tail=NULL;          // too.
  sz--;

  return t;
}

template <typename Type>
void LList<Type>::delete_list()
{
  free(head);           // I will call this method when deleting
  head=NULL;            // a list with only one element, so all
  tail=NULL;            // the variables are set.
  sz=0;
}

template <typename Type>
void LList<Type>::insert(int pos, Type item)
{
  node *newitem;
  node *aux=head;
  int i;

  // Allocate memory for the new item
  newitem=(node*)malloc(sizeof(node));
  if (newitem==NULL)
    {
      report_error(LLIST_ERROR_NOMEMORY);
      return;
    }
  // Stores the item information
  newitem->item=item;
  newitem->next=NULL;

  // Link the item to the list
  if (isEmpty())
    {               // If the list is empty there will be only
      head=newitem;     // one item, so it will be the head and the
      tail=newitem;     // tail.
    }
  else if (pos==0)      // If the item is going to be inserted at the beginning
    {
      newitem->next=head;   // we will move the head
      head=newitem;
    }
  else if (pos>=sz)     // If the position is greater than the last item's position
    {               // it will be inserted after this item, at the tail.
      tail->next=newitem;      
      tail=newitem;
    }
  else
    {               // If not, we will have to find the position of the
      i=0;          // previous item to link its next pointer to the new
      while (i<pos-1)       // element.
    {
      aux=aux->next;
      ++i;
    }
      newitem->next=aux->next;  // And then link the next pointer of our new element
      aux->next=newitem;    // to where the next pointer of the previour element
    }               // was pointing.
  sz++;
}

template <typename Type>
Type LList<Type>::getElement(unsigned pos)
{
  int i=0;
  Type t;
  node *aux=head;

  if (isEmpty())        // If the list is empty = No data
    {
      report_error(LLIST_ERROR_NOITEMS);
      return t;
    }

  if (pos>=sz)          // If the item asked for is greater than the
    {               // last item's position. There is no valid element
      report_error(LLIST_ERROR_NEITEMS);
      return t;
    }
 
  if (pos==sz-1)        // If the item we asked for is the last, we can
    return tail->item;      // return it inmediately


  while (i<pos)         // If not, we must look for it
    {
      aux=aux->next;
      i++;
    }
  return aux->item;
}

template <typename Type>
void LList<Type>::setErrorCallback(ErrorCallback cback)
{
  ecback=cback;         // This method sets the error callback to invoke
  errorType=CALLBACK;       // when an error occurs.
}

template <typename Type>
void LList<Type>::report_error(int err)
{
  if (errorType==CALLBACK)  // If the error reporting is through a callback,
    {               // call it.
      ecback(err);
    }
}

template <typename Type>
void LList<Type>::clear()
{
  node *aux;

  while (head!=NULL)        // Delete all elements
    {
      aux=head;
      head=head->next;
      free(aux);
    }
 
  tail=NULL;            // Restore variable stats
  sz=0;
}  

template <typename Type>
void LList<Type>::setNoErrorReporting()
{
  errorType=NO_ERROR_REPORTING;
}

// Test program
// LList<int> l;

// void blink(int err)
// {
//   while (1)
//     {
//       digitalWrite(11,HIGH);
//       delay(1000);
//       digitalWrite(11, LOW);
//       delay(1000);  
//     }
// }

// void setup()
// {
//   pinMode(11, OUTPUT);
//   Serial.begin(9600);
//   l.setErrorCallback(blink);
//   l.push_back(45);
//   l.push_back(42);
//   l.push_back(47);
//   l.push_back(89);
//   l.insert(0, 33);
//   l.insert(1, 53);
//   l.insert(9, 73);
//   // 33
//   // 53
//   // 45
//   // 42
//   // 47
//   // 89
//   // 73
// }

// void loop()
// {
//   char r;
//   if (Serial.available()>0)
//     {
//       while (Serial.available()>0)
//  {
//    r=Serial.read();
//    delayMicroseconds(10000);
//  }

//       for (unsigned i=0; i<l.size(); i++)
//  {
//    Serial.println(l.getElement(i), DEC);
//  }
//       Serial.print("Elements: ");
//       Serial.println(l.size(), DEC);
//       Serial.print("Last: ");
//       Serial.println(l.pop_front(), DEC);
//     }
// }