// Template Version of Link List Toolkit
#ifndef LINK2_H
#define LINK2_H
#include <stdlib.h> // Provides size_t
template <class Item>
struct Node
{   Item data;
    Node *link;
};

template <class Item>
size_t list_length(Node<Item>* headp)
{   Node<Item> *cursor;
    size_t answer;
    answer = 0;
    for(cursor = headp; cursor != NULL; cursor = cursor->link)
        answer++;
    return answer;
}

template <class Item>
void list_head_insert(Node<Item>*& headp, const Item& new_item)
{
    Node<Item> *insert_ptr;
    insert_ptr = new Node<Item>;
    insert_ptr->data = new_item;
    insert_ptr->link = headp;
    headp = insert_ptr;
}

template <class Item>
void list_insert(Node<Item>* previous_ptr, const Item& new_item)
{
    Node<Item> *insert_ptr;
    insert_ptr = new Node<Item>;
    insert_ptr->data = new_item;
    insert_ptr->link = previous_ptr->link;
    previous_ptr->link = insert_ptr;
}

template <class Item>
Node<Item>* list_search(Node<Item>* headp, const Item& target)
{
    Node<Item> *cursor;
    for (cursor = headp; cursor != NULL; cursor = cursor->link)
        if (cursor->data == target)
            return cursor;
    return NULL;
}

template <class Item, class SizeType>
Node<Item>* list_locate(Node<Item>* headp, SizeType position)
{
    Node<Item> *cursor;
    size_t i;

    assert(position > 0);
    cursor = headp;
    for(i = 1; (i != position) && (cursor != NULL); i++)
        cursor = cursor->link;
    return cursor;
}

template <class Item>
void list_head_remove(Node<Item>*& headp)
{
    Node<Item> *remove_ptr;

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

template <class Item>
void list_remove(Node<Item>* previous_ptr)
{
    Node<Item> *remove_ptr;

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

template <class Item>
void list_clear(Node<Item>*& headp)
{
    while (headp != NULL)
        list_head_remove(headp);
}

template <class Item>
void list_copy(Node<Item>* srcPtr, Node<Item>*& headp, Node<Item>*& tail_ptr)
{
    headp = NULL;
    tail_ptr = NULL;

    if (srcPtr == NULL)  // Handle empty list
        return;

    // Make the head node for the newly created list, and put data in it
    list_head_insert(headp, srcPtr->data);
    tail_ptr = headp;

    // Copy the rest of the nodes one at a time, adding at the tail of new list
    for (srcPtr = srcPtr->link; srcPtr != NULL; srcPtr = srcPtr->link)
    {   list_insert(tail_ptr, srcPtr->data);
        tail_ptr = tail_ptr->link;
    }
}

template <class Item>
void list_piece
(Node<Item>* startp, Node<Item>* endp, Node<Item>*& headp, Node<Item>*& tailp)
{   headp = NULL;
    tail_ptr = NULL;

    if (startp == NULL)
        return;
    
    // Make the head node for the newly created list, and put data in it
    list_head_insert(headp, startp->data);
    tail_ptr = headp;
    if (startp == endp)
        return;
    
    // Copy the rest of the nodes one at a time, adding at the tail of new list
    for (startp = startp->link; startp != NULL; startp = startp->link)
    {   list_insert(tailp, startp->data);
        tailp = tailp->link;
        if (startp == endp)
            return;
    }
}
#endif