// linked_list.cpp
// Glenn G. Chappell
// 2 Nov 2009
//
// For CS 311 Fall 2009
// Linked List Example, cont'd
// Based on list_size.cpp

#include <cstdlib>
using std::size_t;
#include <iostream>
using std::cout;
using std::endl;
using std::cin;
// Also using NULL


// struct LLNode
// Linked List node, with client-specified value type
// Invariants:
//     Either next_ is NULL, or next_ points to an LLNode,
//      allocated with new, owned by *this.
// Requirements on Types:
//     ValueType must have a copy ctor offering the Strong Guarantee
//      and a dctor offering the No-Throw Guarantee.
template <typename ValueType>
struct LLNode {
    ValueType data_;  // Data for this node
    LLNode * next_;   // Ptr to next node, or NULL if none

    // The following simplify creation & destruction

    // 1- & 2-param ctor
    // Pre:
    //     theNext, if passed, is either NULL,
    //      or else it points to an LLNode, allocated with new,
    //      with ownership transferred to *this.
    // Post:
    //     data_ == theData.
    //     If next_ passed, then next_ == theNext.
    //      otherwise, next_ is NULL.
    // Strong Guarantee, exception-neutral
    // If ValueType copy ctor does not throw, then this does not throw
    explicit LLNode(const ValueType & theData,
                    LLNode * theNext = NULL)
        :data_(theData), next_(theNext)
    {}

    // dctor
    // Pre: None.
    // Post: None. (next_ delete'd)
    // No-Throw Guarantee
    ~LLNode()
    { delete next_; }
};


// size
// Given ptr to Linked List, return its size (number of nodes).
// Pre:
//     head is ptr to NULL-terminated Linked List, or NULL.
// Post:
//     Return is size of list, or 0 if head is NULL.
// Requirements on Types:
//     ValueType must have a copy ctor offering the Strong Guarantee
//      and a dctor offering the No-Throw Guarantee.
//     NOTE: These requirements are inherited from struct LLNode;
//      we do not use any member functions of ValueType here.
// No-Throw Guarantee
template <typename ValueType>
size_t size(LLNode<ValueType> * head)
{
    LLNode<ValueType> * p = head;  // Iterates through list
    size_t n = 0;                  // Number of nodes so far
    while (p != NULL)
    {
        p = p->next_;
        ++n;
    }
    return n;
}


// insertBeg
// Given ptr to Linked List, and a data item to be inserted,
//  inserts the item at the beginning of the list. The given
//  (head) ptr is updated.
// Pre:
//     head is ptr to NULL-terminated Linked List, or NULL.
// Post:
//     head is ptr to NULL-terminated Linked List consisting
//      of the same items as before, with the given item
//      inserted at the beginning.
// Requirements on Types:
//     ValueType must have a copy ctor offering the Strong Guarantee
//      and a dctor offering the No-Throw Guarantee.
// Strong Guarantee, exception-neutral
// If ValueType copy ctor does not throw, then this does not throw
template <typename ValueType>
void insertBeg(LLNode<ValueType> * & head,
               const ValueType & item)
{
    head = new LLNode<ValueType>(item, head);
}


// Main program
// Creates a Linked List and finds its size
//  using function size.
int main()
{
    // Create Linked List of size 7, pointed to by head
    LLNode<int> * head = NULL;  // Create empty list
    insertBeg(head, 7);         // Add a node
    insertBeg(head, 6);         // As above ...
    insertBeg(head, 5);
    insertBeg(head, 4);
    insertBeg(head, 3);
    insertBeg(head, 2);
    insertBeg(head, 1);

    // Find & print size of Linked List
    cout << "Size of Linked List: " << size(head) << endl;
    cout << endl;

    cout << "Press ENTER to quit ";
    while (cin.get() != '\n') ;

    return 0;
}