/*
 * $Id$
 */

/**
 * prtTutorial-LinkedList-V2.c is part of the Pointer Tutorial for ROBOTC
 *
 * Changelog:
 * - 0.1: Initial release
 *
 * License: You may use this code as you wish, provided you give credit where it's due.
 *
 * THIS CODE WILL ONLY WORK WITH ROBOTC VERSION 3.55 AND HIGHER.
 * Xander Soldaat (xander_at_botbench.com)
 * 13 January 2013
 * version 0.1
 */

#pragma debuggerWindows(debugStream)

#define MAX_LIST_SIZE 5                // Maximum number of nodes in the list

// Individual list nodes struct
struct tListNode
{
  tListNode *next;                   // neighbouring node
  ubyte value;                          // value held by node
} tListNode;

// List struct to hold the nodes
struct tList
{
  tListNode *head;                   // pointer to the node at the head of the list
  tListNode *tail;                   // pointer to the node at the top of the list
  int size;                             // current size of the list
} tList;

tListNode _listNodePool[MAX_LIST_SIZE]; // array of nodes
bool _allocStatus[MAX_LIST_SIZE];       // Array to keep track of allocation
                                        // status of nodes. true == node is allocated

tList myList;

tListNode * NEW();
void FREE(tListNode *node);
void initList(tList *list);

tListNode * NEW()
{
  for (int i = 0; i < MAX_LIST_SIZE; i++)
  {
    // Return the node if it is not already allocated
    if (!_allocStatus[i])
    {
      writeDebugStreamLine("NEW: found node[%d]: %p", i, _listNodePool[i]);
      _allocStatus[i] = true;
      return _listNodePool[i];
    }
  }
  // No free nodes available
  writeDebugStreamLine("NEW: no free nodes left");
  return NULL;
}

void FREE(tListNode *node)
{
  for (int i = 0; i < MAX_LIST_SIZE; i++)
  {
    if (_allocStatus[i])
    {
      if (node == _listNodePool[i])
      {
        writeDebugStreamLine("FREE: deleting node[%d]: %p", i, _listNodePool[i]);
        _allocStatus[i] = false;
        memset(node, 0, sizeof(tListNode));
        return;
      }
    }
  }
  writeDebugStreamLine("FREE: could not find node: %p", node);
}


void insertNode(tList *list, tListNode *node, tListNode *newNode)
{
  writeDebugStreamLine("Inserting new node %p after node %p in list %p", node, newNode, list);
  // Is the list empty?
  if (list->size == 0)
  {
    list->head = newNode;
    list->tail = newNode;
    list->size++;
  }
  // node == NULL, so put the newNode at the start
  // of the list
  else if (node == NULL)
  {
    newNode->next = list->head;
    list->head = newNode;
    list->size++;
  }
  // Insert the newNode into the list, after the node
  else
  {
    newNode->next = node->next;
    node->next = newNode;
    // if the node was the tail, update this pointer to the newNode
    if (list->tail == node)
      list->tail = newNode;
    list->size++;
  }
}


void deleteNode(tList *list, tListNode *obsoleteNode)
{
  writeDebugStreamLine("Deleting node %p from list %p", list, obsoleteNode);
  tListNode *nodePtr;

  // We only have one node!
  if (list->size == 1)
  {
    list->head = NULL;
    list->tail = NULL;
    list->size--;
    FREE(obsoleteNode);
  }
  // The node we want to delete is the head of the list
  else if (list->head == obsoleteNode)
  {
    list->head = obsoleteNode->next;
    list->size--;
    FREE(obsoleteNode);
  }
  else
  {
    // we need to start looking for the obsoleteNode's
    // left neighbour
    nodePtr = list->head;
    while (nodePtr != NULL)
    {
      // The nodePtr's neighbour is the node we're looking for
      if (nodePtr->next == obsoleteNode)
      {
        // Check if it is also the tail
        if(obsoleteNode == list->tail)
        {
          list->tail = nodePtr;
        }
        // Update the node's left neighbour
        nodePtr->next = obsoleteNode->next;
        list->size--;
        FREE(obsoleteNode);
        return;
      }
      // advance to the next node
      nodePtr = nodePtr->next;
    }
  }
}


void initList(tList *list)
{
  writeDebugStreamLine("Initialising the list %p", list);
  // Reset all the value to 0
  memset(_listNodePool, 0, sizeof(tListNode) * MAX_LIST_SIZE);
  memset(_allocStatus, false, sizeof(bool) * MAX_LIST_SIZE);

  // Set the current head and tail to the first node
  list->head = NULL;
  list->tail = NULL;

  // Set the size to 0
  list->size = 0;

}


void appendNode(tList *list, tListNode *newNode)
{
  writeDebugStreamLine("appendNode: %p", newNode);

  insertNode(list, list->tail, newNode);
}


void swapNodes(tList *list, tListNode *nodeA, tListNode *nodeB)
{
  writeDebugStream("swapping nodes %p (%d)", nodeA, nodeA->value);
  writeDebugStreamLine("and %p (%d)", nodeB, nodeB->value);
  tListNode *nodePtr;

  // If the list is less than two nodes big, there's not much point
  if (list->size < 2)
    return;
  // If the list if exactly two nodes big, just swap 'em around
  else if (list->size == 2)
  {
    nodeB->next = nodeA;
    nodeA->next = NULL;
    list->head = nodeB;
    list->tail = nodeA;
    return;
  }

  // If the first node is the list's head,
  // swap 'em and update the list's head pointer.
  if (list->head == nodeA)
  {
    writeDebugStreamLine("nodeA is head");
    nodeA->next = nodeB->next;
    nodeB->next = nodeA;
    list->head = nodeB;
    return;
  }
  // The first node is a node somewhere in the list
  else
  {
    // We'll have to iterate through to find the
    // node, whose next pointer points to our
    // first node.
    // Start at the head and go through until we reach the end
    nodePtr = list->head;
    while(nodePtr != NULL)
    {
      writeDebugStreamLine("nodePtr: %p (%d)", nodePtr, nodePtr->value);
      // We've found the node, start swapping
      if (nodePtr->next == nodeA)
      {
        writeDebugStreamLine("nodePtr->next == nodeA");
        nodePtr->next = nodeB;
        nodeA->next = nodeB->next;
        nodeB->next = nodeA;
        // If the second node was the tail, update the tail pointer
        if (list->tail == nodeB)
        {
          writeDebugStreamLine("nodeB is tail");
          list->tail = nodeA;
        }
        return;
      }
      // go to the next node
      nodePtr = nodePtr->next;
    }
  }
}


void printList(tList *list)
{
  // set the initial node to the list's head node
  tListNode *nodePtr = list->head;

  writeDebugStream("printList: size: %d, items: ", list->size);

  // don't bother to print the list if it's empty
  if (list->size == 0)
  {
    writeDebugStreamLine("printList: list empty");
    return;
  }

  // print nodes until we reach the end
  while(nodePtr != NULL)
  {
    writeDebugStream("%d, ", nodePtr->value);
    // go to the next node
    nodePtr = nodePtr->next;
  }
  writeDebugStreamLine(" ");
}


/**
 * Sort the values of the list
 * @param list the list to sort
 */
void sortList(tList *list)
{
  writeDebugStreamLine("sortList");
  tListNode *nodePtr;
  // Don't bother to sort a list smaller than 2 nodes big
  if (list->size == 1)
  {
    return;
  }

  // This is a bubble sort, for details on how this works, check out
  // http://botbench.com/blog/2012/07/21/tutorial-sorting-your-data/
  for(int i = 0; i < list->size; i++)
  {
    // Iterate through the list, start at the head
    nodePtr = list->head;
    while(nodePtr != list->tail)
    {
      // The next node is bigger than the current one,
      // so swap them around
      if (nodePtr->value > nodePtr->next->value)
      {
        swapNodes(list, nodePtr, nodePtr->next);
      }
      // Update the nodePtr
      else if (nodePtr->next != NULL)
      {
        nodePtr = nodePtr->next;
      }
    }
  }
}


task main ()
{

  clearDebugStream();


  initList(myList);
  tListNode *nodePtr;

  // Fill our list
  for (int i = 4; i > -1; i--)
  {
    nodePtr = NEW();
    nodePtr->value = i;
    appendNode(myList, nodePtr);
  }
  // Sort the list from small to big
  printList(myList);
  sortList(myList);
  printList(myList);
}