/*
 main.c
 Project 10

 Created by Nhung Blaschke on 4/15/15.
 Copyright (c) 2015 Nhung Blaschke. All rights reserved.

 4/25/2015 - singly linked list program which counts how often a data
 value occurs, deletes first, adds last and detects if the list is in order
*/

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

struct NODE
{
    struct NODE *link;
    int value;
};

typedef struct NODE Node;

Node *insertFirst( Node **ptrToHeadPtr, int val )
{
    Node *node = (Node *)malloc( sizeof( Node ) ); node->value = val;
    node->link = *ptrToHeadPtr;
    *ptrToHeadPtr = node;
    return node;
}

void traverse( Node *p )
{
    while ( p != NULL )
    {
        printf("%d ", p->value );
        p = p->link;
    }
}

void freeList( Node *p )
{
    Node *temp;
    while ( p != NULL )
    {
        temp = p;
        p = p->link;
        free( temp );
    }
}

/* Count the number of nodes in a linked list */

int countNodes( Node *p )
{
    int count = 0; while ( p )
    {
        count++ ;
        p = p->link;
    }
    return count;
}

/*
Return a pointer to the first node that contains the target, or NULL if
no node contains the target.
*/

Node *search( Node *p, int target)
{
    while ( p && target != p->value )
    {
        p = p->link;
    }
    return p;
}

int countTarget(Node *start, int target)
{
    int count = 0;
    while (start != NULL)
    {
        if (target == start->value)
            count ++;
        start = start->link;
    }
    return count;
}

int inOrder(Node *start)
{
    if (start == NULL)
        return 1;
    else
    {
        while (start->link != NULL)
        {
            if (start->value <= start->link->value)
                start = start->link;
            else
                return 0;
        }
        return 1;
    }
}

Node *deleteFirst(Node **ptrToHeadPtr)
{
    Node *temp;
    if (*ptrToHeadPtr == NULL)
        return NULL;
    else
    {
        temp = *ptrToHeadPtr;
        *ptrToHeadPtr = temp->link;
        free(temp);
    }
    return temp;
}
    
Node *insertLast(Node **ptrToHeadPtr, int val)
    {
        Node *newNode = (Node *)malloc (sizeof (Node));
        newNode->value = val;
        newNode->link = NULL;
        Node *node = *ptrToHeadPtr;
        while (node && node->link != NULL)
        {
            node = node->link;
        }
        if(!node)
            *ptrToHeadPtr = newNode;
        else
            node->link = newNode;
        return newNode;
    }

int main(void)
{
    printf("\nsingly linked list demo\n\n");
    Node *head = NULL;
    int j;
	srand(time(NULL));
    for ( j=0; j<10; j++ )
//      insertLast(&head, rand()%100);
        insertLast(&head, j);
    traverse(head);
    printf("\nThere is/are %d 2s", countTarget(head, 2));
    printf("\nIn order: %d",inOrder(head));
    deleteFirst(&head);
    printf("\n");
    traverse (head);
    freeList(head);
    printf("\n");
    return 1;
}