#include <stdlib.h> // Provides size_t
#include <assert.h>
#include <iostream.h>

struct Node
{   typedef double Item;
    Item data;
    Node *link;
};

size_t list_length(Node* head_ptr)
{
    Node *cursor;
    size_t answer;

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

void list_display(Node* head_ptr)
{
    Node *cursor;
    cout << "( ";
    for (cursor = head_ptr; cursor != NULL; cursor = cursor->link)
       cout << cursor->data << " ";
    cout << "), " << "Size = " << list_length(head_ptr) << endl << endl;
}

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;
}

Node* list_search(Node* head_ptr, const Node::Item& target) // pgae 220
{
    Node *cursor;

    for (cursor = head_ptr; cursor != NULL; cursor = cursor->link)
        if (target == cursor->data)
            return cursor;
    return NULL;
}

void list_insert(Node* previous_ptr, const Node::Item& entry) // page 218
{
    Node *insert_ptr;

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

Node* list_locate(Node* head_ptr, size_t position) // page 222
// Finding a node by its position in a llist
{
    Node *cursor;
    size_t i;

    assert (0 < position);
    assert (position <= list_length(head_ptr)); // by chung
    cursor = head_ptr;
    for (i = 1; (i < position) && (cursor != NULL); i++)
        cursor = cursor->link;
    return cursor;
}

Node::Item display_middle(Node* head_ptr)
{
    assert(head_ptr != NULL);
    int i = list_length(head_ptr)/2 + 1;
    return (list_locate(head_ptr, i))->data;
}

void list_copy(Node* src_ptr, Node*& head_ptr, Node*& tail_ptr)
{
    head_ptr = NULL;
    tail_ptr = NULL;

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

void list_head_remove(Node*& head_ptr) // removing just head
{
    Node *remove_ptr;

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

void list_remove(Node* previous_ptr) // removing a node after 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)
{
    while (head_ptr != NULL)
        list_head_remove(head_ptr);
}

void list_piece(Node* start_p, Node* end_p, Node*& head_p, Node*& tail_p)
// copying a part of a linked list, page 227
{
    head_p = NULL;
    tail_p = NULL;
    if (start_p == NULL) // Handle the case of the empty list
        return;
    
    // Make the head node for the newly created list, and put data in it
    list_head_insert(head_p, start_p->data);
    tail_p = head_p;
    if (start_p == end_p)
        return;
    
    // Copy the rest of the nodes one at a time, adding at the tail of new list
    for (start_p = start_p->link; start_p != NULL; start_p = start_p->link)
    {
        list_insert(tail_p, start_p->data);
        tail_p = tail_p->link;
        if (start_p == end_p) 
            return;
    }
}