/* Implementations for node functions.
   Written by: Nadeem Abdul Hamid
   Date: 9/5/2006
*/

#include <stdio.h>
#include <stdlib.h>
#include "node.h"

/* =================== createNode ====================
   Creates a node in dynamic memory and stores data 
   pointer in it.
   Pre  itemPtr is pointer to data to be stored.
   Post node created and its address returned.
*/
NODE* createNode (void* itemPtr)
{
  NODE* nodePtr;
  nodePtr = (NODE*) malloc (sizeof (NODE));
  nodePtr->pdata = itemPtr;
  nodePtr->pnext   = NULL;
  return nodePtr;
} /* createNode */


/* Inserts a node at the beginning of a list.
   Pre: np is a pointer to a node structure
   Post: l is a list (may be empty)
*/
LIST insertNode(NODE* np, LIST l)
{
  np->pnext = l;
  return np;
}


/* Prints out the values in a list.
   Pre: l is a list of integers!!!***
 */
void printList(LIST l) 
{
  NODE* np = l;
  while(np) {
    printf("%d\n", *((int*)np->pdata));
    np = np->pnext;
  }
}


/* Applies a function to every node in the list */
void applyToList(LIST l, void (*nodeFunc)(NODE*)) 
{
  NODE* np = l;
  while(np) {
    nodeFunc(np);
    np = np->pnext;
  }
}


/* Calculates the length of a list */
int lengthList(LIST l)
{
  NODE *np;
  int len = 0;
  for(np = l; np; np = np->pnext)
    ++len;
  return len;
}


/* Sorts the nodes in the list using bubble sort */
LIST bubbleSort(LIST l, int (*comp)(void*, void*)) 
{
  const int length = lengthList(l);
  int i;
  NODE *curp, *prevp, *tempp, *nextp;

  for (i = 0; i < length-1; i++) {
    for (prevp = NULL, curp = l; curp->pnext; curp = nextp) {
      if ((*comp)(curp->pdata, curp->pnext->pdata) > 0) {
	if (prevp) prevp->pnext = curp->pnext;
	else l = curp->pnext;
	tempp = curp->pnext;
	curp->pnext = curp->pnext->pnext;
	tempp->pnext = curp;

	prevp = tempp;
	nextp = curp;
      }
      else {
	prevp = curp;
	nextp = curp->pnext;
      }
    }
  }
  
  return l;
}