// FILE: newlink.cxx
// IMPLEMENTS: The 14 functions of the expanded linked list toolkit
// (see linkplus.h). The four new functions implemented at the bottom of
// the file were implemented by Darin Gillis - gillisd@colorado.edu.

#include <assert.h>    // Provides assert
#include <stdlib.h>    // Provides NULL
#include "newlink.h"

long list_length(Node* head_ptr)
// Library facilities used: stdlib.h
{
    Node *cursor;
    long answer;

    answer = 0;
    for (cursor = head_ptr; cursor != NULL; cursor = cursor->link)
        answer++;

    return answer;
}

void list_head_insert(Node*& head_ptr, const Node::Item& entry)
{
    Node *insert_ptr;

    insert_ptr = new Node;
    insert_ptr->data = entry;
    insert_ptr->link = head_ptr;
    head_ptr = insert_ptr;
}

void list_insert(Node* previous_ptr, const Node::Item& entry) 
{
    Node *insert_ptr;
    
    insert_ptr = new Node;
    insert_ptr->data = entry;
    insert_ptr->link = previous_ptr->link;
    previous_ptr->link = insert_ptr;
}

Node* list_search(Node* head_ptr, const Node::Item& target) 
// Library facilities used: stdlib.h
{
    Node *cursor;
   
    for (cursor = head_ptr; cursor != NULL; cursor = cursor->link)
        if (target == cursor->data)
            return cursor;
    return NULL;
}

Node* list_locate(Node* head_ptr, long position) 
// Library facilities used: assert.h, stdlib.h
{
    Node *cursor;
    long i;
    
    assert (0 < position);
    cursor = head_ptr;
    for (i = 1; (i < position) && (cursor != NULL); i++)
        cursor = cursor->link;
    return cursor;
}

void list_head_remove(Node*& head_ptr)
{
    Node *remove_ptr;

    remove_ptr = head_ptr;
    head_ptr = head_ptr->link;
    delete remove_ptr;
}

void list_remove(Node* previous_ptr)
{
    Node *remove_ptr;

    remove_ptr = previous_ptr->link;
    previous_ptr->link = remove_ptr->link;
    delete remove_ptr;
}

void list_clear(Node*& head_ptr)
// Library facilities used: stdlib.h
{
    while (head_ptr != NULL)
        list_head_remove(head_ptr);
}

void list_copy(Node* source_ptr, Node*& head_ptr, Node*& tail_ptr) 
// Library facilities used: stdlib.h
{
    head_ptr = NULL;
    tail_ptr = NULL;

    // Handle the case of the empty list
    if (source_ptr == NULL)
        return;
    
    // Make the head node for the newly created list, and put data in it
    list_head_insert(head_ptr, source_ptr->data);
    tail_ptr = head_ptr;
    
    // Copy the rest of the nodes one at a time, adding at the tail of new list
    for (source_ptr = source_ptr->link; source_ptr != NULL; source_ptr = source_ptr->link)
    {
        list_insert(tail_ptr, source_ptr->data);
        tail_ptr = tail_ptr->link;
    }
}

void list_piece(Node* start_ptr, Node* end_ptr, Node*& head_ptr, Node*& tail_ptr)
// Library facilities used: stdlib.h
{
    head_ptr = NULL;
    tail_ptr = NULL;

    // Handle the case of the empty list
    if (start_ptr == NULL)
        return;
    
    // Make the head node for the newly created list, and put data in it
    list_head_insert(head_ptr, start_ptr->data);
    tail_ptr = head_ptr;
    if (start_ptr == end_ptr)
        return;
    
    // Copy the rest of the nodes one at a time, adding at the tail of new list
    for (start_ptr = start_ptr->link; start_ptr != NULL; start_ptr = start_ptr->link)
    {
        list_insert(tail_ptr, start_ptr->data);
        tail_ptr = tail_ptr->link;
        if (start_ptr == end_ptr) 
            return;
    }
}

long list_occurrences(Node* head_ptr, const Node::Item& target)
{

     Node *ctr;
     long occur=0;
     Node *found;
     
     for(ctr=head_ptr;ctr != NULL;ctr=ctr->link)
     {
	  if (ctr->data == target)
	       occur++;
	  
     }

     return occur;
}

void list_tail_attach(Node*& head_ptr, const Node::Item& entry)
{
     Node *insert_ptr;
     Node *tail;
     
     if(head_ptr==NULL)
     {
	  insert_ptr = new Node;
	  insert_ptr->data = entry;
	  insert_ptr->link = NULL;
	  head_ptr = insert_ptr;
     }
     else
     {
	  insert_ptr = new Node;
	  insert_ptr->data = entry;
	  insert_ptr->link = NULL;

	  tail = list_locate(head_ptr, list_length(head_ptr));
	  tail->link = insert_ptr; 
     }
}

void list_tail_remove(Node*& head_ptr)
{
     assert(head_ptr != NULL);

     Node *remove_ptr;
     Node *tail;


     if(head_ptr->link==NULL)
     {
	  list_clear(head_ptr);
     }
     else
     {
	  tail = list_locate(head_ptr, list_length(head_ptr)-1);
	  remove_ptr = tail->link;
	  tail->link = NULL;
	  delete remove_ptr;
     }

}

//   Node* list_copy_front(Node* source_ptr, long n)
//     Precondition: source_ptr is the head pointer of a linked list with
//     at least n nodes.
//     Postcondition: The value returned is the head pointer for
//     a new list that contains copies of the first n nodes from the list
//     that source_ptr points to.

Node* list_copy_front(Node* source_ptr, long n)
{
     assert(source_ptr != NULL);
     assert(list_length(source_ptr)>=n);

     Node *head_ptr, *tail;
     Node *ctr;
     long i;

     head_ptr = NULL;

// gets the first item set up in the list
     if (n > 0)
     {
	  head_ptr = new Node;
	  head_ptr->data = source_ptr->data;
	  head_ptr->link = NULL;
	  tail = head_ptr;
	  ctr = source_ptr->link;
     }
     
     for (i=1 ;i < n; i++, ctr=ctr->link)
     {
	  tail-> link = new Node;
	  tail = tail->link;
	  tail->data = ctr->data;
	  tail->link = NULL;   
     }
     
     return head_ptr;
}