#include <stdio.h>
#include <stdlib.h>
#include <strings.h>

typedef struct itemTag item;

/* inventory item record */
struct itemTag
{
    char name[64];   /* item name */
    int quantity;    /* # of items in stock */
    float cost;      /* cost per item */
    item *nextItem;  /* pointer to the next item in the list */
};

/* stack manipulation subroutines */
int Push(item **head, char *name, int q, float cost);
item* Pop(item **head);

/* queue access subroutines */
item* dequeue(item **head);
int enqueue(item **head, char *name, int q, float cost);

/* delete item from the list (by name) */
int DeleteItem(item **head, char *name);


/* insert item in alphabetical order */
int InsertItem(item **head, char *name, int q, float cost);

/* compute total cost of the inventory */
float CalculateInventoryCost(item *head);

/* print list */
void PrintList(item *head);

/* delete list */
void FreeList(item **head);

/* find item */
item *FindItem(item *head, char *name);

/* linked list sort subroutine */
void BubbleSort(item **head);

/* help function used by BubbleSort */
void SwapTwoNodes(item **head); 

int main(int argc, char *argv[])
{
    item *inventory = NULL;
    float totalCost = 0.0f;

    PrintList(inventory);

    /* stack */
    Push(&inventory, "part3", 10, 1.0f);
    Push(&inventory, "part1", 5, 1.0f);
	Push(&inventory, "part2", 5, 1.0f);
    PrintList(inventory);    
	Pop(&inventory);
    PrintList(inventory);
	
	FreeList(&inventory);
	
    /* queue */
    enqueue(&inventory, "part3", 10, 1.0f);
    enqueue(&inventory, "part2", 5, 1.0f);
	enqueue(&inventory, "part1", 5, 1.0f);
    PrintList(inventory);
    dequeue(&inventory);
    PrintList(inventory);
	
	FreeList(&inventory);
	
	/* Insert/Sort example */
	InsertItem(&inventory, "paerC", 1, 1.0f);
	InsertItem(&inventory, "paerA", 1, 1.0f);
	InsertItem(&inventory, "paerD", 1, 1.0f);
	InsertItem(&inventory, "paerQ", 1, 1.0f);
	InsertItem(&inventory, "paerB", 1, 1.0f);
	PrintList(inventory);
    BubbleSort(&inventory);
	PrintList(inventory);

	FreeList(&inventory);
	
    return 0;
}


int Push(item **head, char *name, int q, float cost)
{
    item *new_item;

    /* allocate new item */
    new_item = (item *)malloc(sizeof(item));
    if (new_item == NULL)
        return 0;

    /* copy data */
    strcpy(new_item->name, name);
    new_item->cost = cost;
    new_item->quantity = q;
    new_item->nextItem = NULL;

    /* attach it in front of the head */
    new_item->nextItem = *head;
    *head = new_item;

    return 1;
}

/* delete item by its name */
item* Pop(item **head)
{
    item *removed;
	
    if (*head == NULL)
		return NULL;
	
	removed = *head;
	*head = (*head)->nextItem;
	
	return removed;
}


int enqueue(item **head, char *name, int q, float cost)
{
    item *new_item;
	
    if (*head == NULL)
    {
		if ((new_item = (item *)malloc(sizeof(item))) == NULL)
			return 0;
		
		new_item->quantity = q;
		new_item->cost = cost;
		strcpy(new_item->name, name);
		new_item->nextItem = *head;
		*head = new_item;
		
		return 1;
    }
	
    return enqueue(&(*head)->nextItem, name, q, cost);
}


item* dequeue(item **head)
{
    item *removed;
	
    if (*head == NULL)
		return NULL;
	
	removed = *head;
	*head = (*head)->nextItem;
	
	return removed;
}


int InsertItem(item **head, char *name, int q, float cost)
{
    item *new_item;

    if ((*head == NULL) || (strcmp((*head)->name, name) > 0))
    {
       if ((new_item = (item *)malloc(sizeof(item))) == NULL)
          return 0;

       new_item->quantity = q;
       new_item->cost = cost;
       strcpy(new_item->name, name);
       new_item->nextItem = *head;
       *head = new_item;

       return 1;
    }

    return InsertItem(&(*head)->nextItem, name, q, cost);
}




/* delete item by its name */
int DeleteItem(item **head, char *name)
{
    item *removed;

    if (*head == NULL)
       return 0;

    if (strcmp((*head)->name, name) == 0)
    {
        removed = *head;
        *head = (*head)->nextItem;
        free(removed);
        return 1;
    }

    return DeleteItem(&(*head)->nextItem, name); 
}


/* compute inventory */
float CalculateInventoryCost(item *head)
{
    item *current_item = head;
    float totalCost = 0.0f;

    while (current_item != NULL)
    {
        totalCost += current_item->quantity * current_item->cost;
        current_item = current_item->nextItem;
    }

    return totalCost;
}


/* print list */
void PrintList(item *head)
{
    item *current_item = head;
    int ic = 0;

    printf("Printing linked list:\n");
    while (current_item != NULL)
    {
        printf("Item #%i @ %p: ", ic, current_item);
        printf("%s %d %f %p\n", current_item->name, current_item->quantity,
                current_item->cost, current_item->nextItem);
      
        current_item = current_item->nextItem; 
        ic++;
    }

    printf("\n");
}

/* delete list */
void FreeList(item **head)
{
    item *removed = NULL;

    if (*head == NULL) /* nothing to delete */
        return;

    removed = *head;
    *head = (*head)->nextItem;
    free(removed);
   
    FreeList(head);
}

 
/* find item */
item *FindItem(item *head, char *name)
{
   if (head == NULL)
       return NULL;

   if (strcmp(head->name, name) == 0)
      return head;
  
    return FindItem(head->nextItem, name);
}


void SwapTwoNodes(item **head)
{
    item *node1, *node2;
    item *new_head;

    node1 = *head;
    if (node1 == NULL)
        return;

    node2 = node1->nextItem;
    if (node2 == NULL)
        return;

    new_head = node2;
    node1->nextItem = node2->nextItem;
    node2->nextItem = node1;
	*head = new_head;
}


void BubbleSort(item **head)
{
    item **node1 = head;
    int swapped = 1;
	
    while (swapped) 
    {
        swapped = 0;
        for (node1 = head; (*node1)->nextItem != NULL; node1 = &(*node1)->nextItem)
        {			
            if (strcmp((*node1)->name, (*node1)->nextItem->name) < 0)
            {
                /* swap nodes */
                SwapTwoNodes(node1);
                swapped = 1;
            }
        }
    }
}