// File:        list.hpp
// ---------------------------------------------------------------
// Author:      <your name>, <your e-mail address>
// TF:          <your TF's name>
// Date:        <current date>
// Assignment:  Unit 8 Hard supplementary exercises
// Version:     1
//
// Description:
//      Definition and implementation of classes for building singly 
//      linked lists.
//
//      Because we're using templates, we need to define the methods in
//      this file so that the compiler won't complain.
//

#ifndef LIST_HPP
#define LIST_HPP


// Class for nodes in the list.
template <class elt>
class node {
    public:
        // TODO - implement this
};

// Class for the list itself.
template <class elt>
class list {
    private:
        node<elt> *head;
        int num_items;

    public:
        list();
        ~list();

        node<elt>* insert(node<elt>* follow, elt& item);
        node<elt>* append(elt& item);
        node<elt>* retrieve(int pos);
        node<elt>* remove(node<elt>* n);
        node<elt>* remove(node<elt>* n, elt& target);

        node<elt>* search_ordered(elt& item, int &num_compares);
        node<elt>* search(elt& item, int &num_compares);

        node<elt>* prev_node(node<elt> *n);
        node<elt>* next_node(node<elt> *n);
        void traverse(void (*action)(int, elt));

        node<elt>* first();
        node<elt>* last();
        node<elt>* end();
        int get_num_items();

        void reinit();
        void sort();
        void print_list();
};


//
// Constructor - creates an empty list
//
template <class elt>
list<elt>::list()
{
    // TODO - implement this
}

//
// Destructor
//
template <class elt>
list<elt>::~list()
{
    // TODO - implement this
}

//
// insert - inserts an item before the node pointed to by follow.
// Returns a pointer to the inserted node.
//
template <class elt>
node<elt>*
list<elt>::insert(node<elt>* follow, elt& item)
{
    // TODO - implement this
}

//
// append - inserts an item at the end of the list
// Returns a pointer to the inserted node.
//
template <class elt>
node<elt>*
list<elt>::append(elt& item)
{
    // TODO - implement this
}

//
// remove - removes the specified node from the list, putting its
// data item in target.  Returns a pointer to the node that followed
// the removed one in the list.
//
template <class elt>
node<elt>*
list<elt>::remove(node<elt>* n, elt& target)
{
    // TODO - implement this
}

//
// remove w/o target - removes the specified node from the list.
// Returns a pointer to the node that followed the removed one in the list.
//
template <class elt>
node<elt>*
list<elt>::remove(node<elt>* n)
{
    // TODO - implement this
}

//
// retrieve - returns a pointer to the item at position pos in the list
//
template <class elt>
node<elt>*
list<elt>::retrieve(int pos)
{
    // TODO - implement this
}

//
// first - returns a pointer to the first item in the list.
// If the list is empty, this will point to the dummy head node.
//
template <class elt>
node<elt>* list<elt>::first()
{
    // TODO - implement this
}

//
// last - returns a pointer to the last item in the list.
// If the list is empty, this will point to the dummy head node.
//
template <class elt>
node<elt>*
list<elt>::last()
{
    // TODO - implement this
}

//
// end - returns a pointer to the "end" of the list, i.e., the
// dummy head node.
//
template <class elt>
node<elt>*
list<elt>::end()
{
    // TODO - implement this
}

//
// next_node - returns a pointer to the node that follows the specified
// node, or NULL if we're already at the end of the list.
//
template <class elt>
node<elt>*
list<elt>::next_node(node<elt>* n)
{
    // TODO - implement this
}

//
// prev_node - returns a pointer to the node that precedes the specified
// node, or NULL if we're already at the start of the list.
//
template <class elt>
node<elt>*
list<elt>::prev_node(node<elt>* n)
{
    // TODO - implement this
}

//
// get_num_items - returns the number of items in the list
//
template <class elt>
int
list<elt>::get_num_items()
{
    // TODO - implement this
}

//
// search - searches the list for the specified item.
// If search is successful, returns a pointer to the first occurrence
// of the item in the list.  Otherwise, returns NULL.
// In either case, stores the number of comparisons made
// in num_compares.
//
template <class elt>
node<elt>*
list<elt>::search(elt& item, int& num_compares)
{
    // TODO - implement this
}

//
// search_ordered - searches the list for the first item >= the 
// specified item.  If successful, returns a pointer to the node
// containing the first such item.  Otherwise, it returns a
// pointer to the dummy head node.
// In either case, stores the number of comparisons made
// in num_compares.
// 
template <class elt>
node<elt>*
list<elt>::search_ordered(elt& item, int& num_compares)
{
    // TODO - implement this
}

//
// traverse - traverse the list from front to back, applying
// the specified function to each item (i.e., the data item
// in each node).
//
template <class elt>
void
list<elt>::traverse(void (*action)(int, elt))
{
    // TODO - implement this
}

//
// sort - perform insertion sort on the items in the list
//
template <class elt>
void
list<elt>::sort()
{
    // TODO - implement this
}

//
// reinit - empty the list
//
template <class elt>
void
list<elt>::reinit()
{
    // TODO - implement this
}

//
// print_list -- print the list to standard out
//
template <class elt>
void
list<elt>::print_list()
{
    // TODO - implement this
}

#endif


