// FILE: node2.h (part of the namespace main_savitch_6B)
// PROVIDES: A template class for a node in a linked list, and list manipulation
// functions. The template parameter is the type of the data in each node.
// This file also defines a template class: node_iterator<Item>.
// The node_iterator is a forward iterators with two constructors:
// (1) A constructor (with a node<Item>* parameter) that attaches the iterator
// to the specified node in a linked list, and (2) a default constructor that
// creates a special iterator that marks the position that is beyond the end of a
// linked list. There is also a const_node_iterator for use with
// const node<Item>* .
//
// TYPEDEF for the node<Item> template class:
//   Each node of the list contains a piece of data and a pointer to the
//   next node. The type of the data (node<Item>::value_type) is the Item type
//   from the template parameter. The type may be any of the built-in C++ classes
//   (int, char, ...) or a class with a default constructor, an assignment
//   operator, and a test for equality (x == y).
// NOTE:
//   Many compilers require the use of the new keyword typename before using
//   the expression node<Item>::value_type. Otherwise
//   the compiler doesn't have enough information to realize that it is the
//   name of a data type.
//
// CONSTRUCTOR for the node<Item> class:
//   node(
//     const Item& init_data = Item(),
//     node* init_link = NULL
//   )
//     Postcondition: The node contains the specified data and link.
//     NOTE: The default value for the init_data is obtained from the default
//     constructor of the Item. In the ANSI/ISO standard, this notation
//     is also allowed for the built-in types, providing a default value of
//     zero. The init_link has a default value of NULL.
//
// NOTE about two versions of some functions:
//   The data function returns a reference to the data field of a node and
//   the link function returns a copy of the link field of a node.
//   Each of these functions comes in two versions: a const version and a
//   non-const version. If the function is activated by a const node, then the
//   compiler choses the const version (and the return value is const).
//   If the function is activated by a non-const node, then the compiler choses
//   the non-const version (and the return value will be non-const).
// EXAMPLES:
//    const node<int> *c;
//    c->link( ) activates the const version of link returning const node*
//    c->data( ) activates the const version of data returning const Item&
//    c->data( ) = 42; ... is forbidden
//    node<int> *p;
//    p->link( ) activates the non-const version of link returning node*
//    p->data( ) activates the non-const version of data returning Item&
//    p->data( ) = 42; ... actually changes the data in p's node
//
// MEMBER FUNCTIONS for the node<Item> class:
//   const Item& data( ) const <----- const version
//   and
//   Item& data( ) <----------------- non-const version
//   See the note (above) about the const version and non-const versions:
//     Postcondition: The return value is a reference to the  data from this node.
//
//   const node* link( ) const <----- const version
//   and
//   node* link( ) <----------------- non-const version
//   See the note (above) about the const version and non-const versions:
//     Postcondition: The return value is the link from this node.
//   
//   void set_data(const Item& new_data)
//     Postcondition: The node now contains the specified new data.
//   
//   void set_link(node* new_link)
//     Postcondition: The node now contains the specified new link.
//
// FUNCTIONS in the linked list toolkit:
//   template <class Item>
//   void list_clear(node<Item>*& head_ptr) 
//     Precondition: head_ptr is the head pointer of a linked list.
//     Postcondition: All nodes of the list have been returned to the heap,
//     and the head_ptr is now NULL.
//
//   template <class Item>
//   void list_copy
//   (const node<Item>* source_ptr, node<Item>*& head_ptr, node<Item>*& tail_ptr)
//     Precondition: source_ptr is the head pointer of a linked list.
//     Postcondition: head_ptr and tail_ptr are the head and tail pointers for
//     a new list that contains the same items as the list pointed to by
//     source_ptr. The original list is unaltered.
//
//   template <class Item>
//   void list_head_insert(node<Item>*& head_ptr, const Item& entry) 
//     Precondition: head_ptr is the head pointer of a linked list.
//     Postcondition: A new node containing the given entry has been added at
//     the head of the linked list; head_ptr now points to the head of the new,
//     longer linked list.
//
//   template <class Item>
//   void list_head_remove(node<Item>*& head_ptr) 
//     Precondition: head_ptr is the head pointer of a linked list, with at
//     least one node.
//     Postcondition: The head node has been removed and returned to the heap;
//     head_ptr is now the head pointer of the new, shorter linked list.
//
//   template <class Item>
//   void list_insert(node<Item>* previous_ptr, const Item& entry) 
//     Precondition: previous_ptr points to a node in a linked list.
//     Postcondition: A new node containing the given entry has been added
//     after the node that previous_ptr points to.
//
//   template <class Item>
//   size_t list_length(const node<Item>* head_ptr)
//     Precondition: head_ptr is the head pointer of a linked list.
//     Postcondition: The value returned is the number of nodes in the linked
//     list.
//
//   template <class NodePtr, class SizeType>
//   NodePtr list_locate(NodePtr head_ptr, SizeType position)
//   The NodePtr may be either node<Item>* or const node<Item>*
//     Precondition: head_ptr is the head pointer of a linked list, and
//     position > 0.
//     Postcondition: The return value is a pointer that points to the node at
//     the specified position in the list. (The head node is position 1, the
//     next node is position 2, and so on). If there is no such position, then
//     the null pointer is returned.
//
//   template <class Item>
//   void list_remove(node<Item>* previous_ptr) 
//     Precondition: previous_ptr points to a node in a linked list, and this
//     is not the tail node of the list.
//     Postcondition: The node after previous_ptr has been removed from the
//     linked list.
//
//   template <class NodePtr, class Item>
//   NodePtr list_search
//   (NodePtr head_ptr, const Item& target) 
//   The NodePtr may be either node<Item>* or const node<Item>*
//     Precondition: head_ptr is the head pointer of a linked list.
//     Postcondition: The return value is a pointer that points to the first
//     node containing the specified target in its data member. If there is no
//     such node, the null pointer is returned.
//
// DYNAMIC MEMORY usage by the toolkit: 
//   If there is insufficient dynamic memory, then the following functions throw
//   bad_alloc: the constructor, list_head_insert, list_insert, list_copy.

#ifndef MAIN_SAVITCH_NODE2_H  
#define MAIN_SAVITCH_NODE2_H
#include <cstdlib>   // Provides NULL and size_t
#include <iterator>  // Provides iterator and forward_iterator_tag

namespace main_savitch_6B
{
    template <class Item>
    class node
    {
    public:
        // TYPEDEF
        typedef Item value_type;
        // CONSTRUCTOR
        node(const Item& init_data=Item( ), node* init_link=NULL)
            { data_field = init_data; link_field = init_link; }
        // MODIFICATION MEMBER FUNCTIONS
        Item& data( ) { return data_field; }
        node* link( ) { return link_field; }
        void set_data(const Item& new_data) { data_field = new_data; }
        void set_link(node* new_link) { link_field = new_link; }
        // CONST MEMBER FUNCTIONS
        const Item& data( ) const { return data_field; }
        const node* link( ) const { return link_field; }
    private:
        Item data_field;
        node *link_field;
    };

    // FUNCTIONS to manipulate a linked list:
    template <class Item>
    void list_clear(node<Item>*& head_ptr);

    template <class Item>
    void list_copy
        (const node<Item>* source_ptr, node<Item>*& head_ptr, node<Item>*& tail_ptr);

    template <class Item>
    void list_head_insert(node<Item>*& head_ptr, const Item& entry); 

    template <class Item>
    void list_head_remove(node<Item>*& head_ptr);

    template <class Item>
    void list_insert(node<Item>* previous_ptr, const Item& entry);
 
    template <class Item>
	std::size_t list_length(const node<Item>* head_ptr);

    template <class NodePtr, class SizeType>
    NodePtr list_locate(NodePtr head_ptr, SizeType position);

    template <class Item>
    void list_remove(node<Item>* previous_ptr);
   
    template <class NodePtr, class Item>
    NodePtr list_search(NodePtr head_ptr, const Item& target);

    // FORWARD ITERATORS to step through the nodes of a linked list
    // A node_iterator of can change the underlying linked list through the
    // * operator, so it may not be used with a const node. The
    // node_const_iterator cannot change the underlying linked list
    // through the * operator, so it may be used with a const node.
    // WARNING:
    // This classes use std::iterator as its base class;
    // Older compilers that do not support the std::iterator class can
    // delete everything after the word iterator in the second line:

    template <class Item>
    class node_iterator
    : public std::iterator<std::forward_iterator_tag, Item>
    {
    public:
    	node_iterator(node<Item>* initial = NULL)
	    { current = initial; }
	Item& operator *( ) const
	    { return current->data( ); }
	node_iterator& operator ++( ) // Prefix ++
	    { 
		current = current->link( );
		return *this;
	    }
	node_iterator operator ++(int) // Postfix ++
	    {
		node_iterator original(current);
		current = current->link( );
		return original;      	  
	    }
	bool operator ==(const node_iterator other) const
	    { return current == other.current; }
	bool operator !=(const node_iterator other) const
	    { return current != other.current; }
    private:
	node<Item>* current;
    };

    template <class Item>
    class const_node_iterator
    : public std::iterator<std::forward_iterator_tag, const Item>
    {
    public:
    	const_node_iterator(const node<Item>* initial = NULL)
	    { current = initial; }
	const Item& operator *( ) const
	    { return current->data( ); }
	const_node_iterator& operator ++( ) // Prefix ++
	    {
		current = current->link( );
		return *this;
	    }
	const_node_iterator operator ++(int) // Postfix ++
	    {
		const_node_iterator original(current);
		current = current->link( );
		return original;
	    }
	bool operator ==(const const_node_iterator other) const
	    { return current == other.current; }
	bool operator !=(const const_node_iterator other) const
	    { return current != other.current; }
    private:
	const node<Item>* current;
    };

}

#include "node2.template"
#endif