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

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


/* Creates a node in dynamic memory and stores a
   data pointer in it.
   Pre: itemPtr is pointer to data to be stored
   Post: node is created and its address is returned
*/
NODE* createNode(void* itemPtr) 
{
  NODE *pnode;
  pnode = (NODE*)malloc(sizeof(NODE));
  if (!pnode)
    return NULL;

  pnode->pdata = itemPtr;
  pnode->pnext = NULL;
  return pnode;
}


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



/* Frees all nodes in this list */
void destroyList(LIST head)
{
  NODE *next;
  if (!head) return;
  next = head->pnext;
  free(head);
  destroyList(next);
}




void applyToList(LIST l, void (*nodeFunc)(NODE*))
{
  NODE *curp = l;
  while(curp) {
    nodeFunc(curp);
    curp = curp->pnext;
  }
}


int lengthList(LIST l) 
{
  NODE *curp;
  int len = 0;
  for (curp = l; curp; curp = curp->pnext)
    ++len;
  return len;
}



LIST bubbleSort(LIST l, int (*comp)(void*, void*))
{
  const int length = lengthList(l);
  int i;
  NODE *curp, *prevp, *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 ) {
	/* need to swap nodes */
	if (prevp) prevp->pnext = curp->pnext;
	else l = curp->pnext;
	
	
	curp->pnext = curp->pnext->pnext;
	if (prevp) prevp->pnext = curp;
	else l->pnext = curp;
	
	prevp = prevp ? prevp->pnext : l;
	nextp = curp;
      }
      else {
	prevp = curp;
	nextp = curp->pnext;
      }
    }
  }

  return l;
}