//
// list.hpp
//
// Definition and implementation of classes for building circular,
// doubly linked lists.
//
// Because we're using templates, we need to define the methods in
// this file so that the compiler won't complain.
//
// Computer Science S-111, Harvard University
//

#ifndef LIST_HPP
#define LIST_HPP


// Class for nodes in the list.
template <class elt>
class node {
public:
    elt data;
    node<elt> *next;
    node<elt> *prev;
};

// 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();
    void reverse_list();
};


//
// Constructor - creates an empty list
//
template <class elt>
list<elt>::list()
{
    head = new node<elt>;
    head->next = head;
    head->prev = head;
    num_items = 0;
}

//
// Destructor
//
template <class elt>
list<elt>::~list()
{
    reinit();
    delete head;
}

//
// 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)
{
    node<elt> *n = new node<elt>;
    n->data = item;
    num_items++;

    follow->prev->next = n;
    n->prev = follow->prev;
    n->next = follow;
    follow->prev = n;
    
    return n;
}

//
// 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)
{
    //
    // This works because the dummy head node comes after the
    // last node in the list.
    //
    return (insert(head, item));
}

//
// 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)
{
    // Don't remove the dummy head node.
    if (n == head) {
		return NULL;
	}
    
    target = n->data;
    return (remove(n));
}

//
// 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)
{
    // Don't remove the dummy head node.
    if (n == head) {
		return NULL;
	}

    num_items--;
    n->prev->next = n->next;
    n->next->prev = n->prev;
    
    return n->next;
}

//
// retrieve - returns a pointer to the item at position pos in the list
//
template <class elt>
node<elt>* list<elt>::retrieve(int pos)
{
    node<elt> *trav = first();
    while (pos > 1 && trav != end()) {
		pos--;
		trav = trav->next;
    }
    
    if (trav == head) {
		return NULL;
    } else {
		return trav;
	}
}

//
// 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()
{
    return head->next;
}

//
// 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()
{
    return head->prev;
}

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

//
// 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)
{
    if (n == head) {
		return NULL;
    } else {
		return n->next;
	}
}

//
// 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)
{
    if (n == head) {
		return NULL;
    } else {
		return n->prev;
	}
}

//
// get_num_items - returns the number of items in the list
//
template <class elt>
int list<elt>::get_num_items()
{
    return num_items;
}

//
// 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)
{
    node<elt> *trav = first();
    num_compares = 1;
    
    while (trav != end() && !(trav->data == item)) {
		num_compares++;
		trav = trav->next;
    }
    
    if (trav == end()) {
		return NULL;
    } else {
		return trav;
	}
}

//
// 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)
{
    node<elt> *trav = first();
    num_compares = 1;
    
    while (trav != end() && (trav->data < item)) {
		num_compares++;
		trav = trav->next;
    }

    return trav;
}

//
// 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))
{
    node<elt> *trav = first();

    for (int pos = 1; pos <= num_items; pos++) {
		(*action)(pos, trav->data);
		trav = trav->next;
    }
}

//
// sort - perform insertion sort on the items in the list
//
template <class elt>
void list<elt>::sort()
{
    elt data;
    int count;
    node<elt> *p = first();

    while (p != end()) {
		node<elt>* q = search_ordered(p->data, count);
		node<elt>* pnext = next_node(p);

		if (q != p) {
		    remove(p, data);
		    insert(q, data);
		}

		p = pnext;
    }
}

//
// reinit - empty the list
//
template <class elt>
void list<elt>::reinit()
{
    node<elt> *trav, *temp;

    trav = first();
	while (trav != end()) {
		temp = trav;
		trav = remove(trav);
		delete temp;
    }
}

//
// print_list -- print the list to standard out
//
template <class elt>
void list<elt>::print_list()
{
    if (num_items == 0) {
		cout << "\tlist is empty\n";
    } else {
		traverse(print_item);
	}
}

//
// reverse_list -- reverse the list of items
//
template <class elt>
void list<elt>::reverse_list()
{
	node<elt> * temp;
	
	// get number of items [n] in list 
	int n = get_num_items();

	// append n items to list end, deleting originals
	for(int i = 0; i < n; i++ ) {
		temp = retrieve(n-i);		// get last item
		append(temp->data);			// append item to end of list
		remove(temp);				// delete original item
	}
}

#endif
