// list_size.cpp
// Glenn G. Chappell
// 25 Sep 2009
//
// For CS 311 Fall 2009
// Linked List Example: Create & find size

#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 and a dctor.
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.
    explicit LLNode(const ValueType & theData,
                    LLNode * theNext = NULL)
        :data_(theData), next_(theNext)
    {}

    // dctor
    // Pre: None.
    // Post: None. (next_ delete'd)
    ~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 and a dctor.
//     NOTE: These requirements are inherited from struct LLNode;
//      we do not use any member functions of ValueType here.
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;
}


// 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
    head = new LLNode<int>(7, head);  // Add a node
    head = new LLNode<int>(6, head);  // As above ...
    head = new LLNode<int>(5, head);
    head = new LLNode<int>(4, head);
    head = new LLNode<int>(3, head);
    head = new LLNode<int>(2, head);
    head = new LLNode<int>(1, head);

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