/*
 *          File: list.cpp
 *        Author: Robert I. Pitts <rip@cs.bu.edu> 
 * Last Modified: Fall 2000
 *         Topic: Templates
 * -----------------------------------------------------
 *
 * This is the implementation for a linked list class.
 *
 */

#include <iostream.h>

/*
 * Constructor
 * -------------------------
 * List starts out empty (i.e., no nodes).
 */

template <class Item>
List<Item>::List()
{
  head = NULL;
}

/* Destructor
 * -----------------------
 * This deallocates all memory associated with the list.
 */

template <class Item>
List<Item>::~List()
{
  // Since removeFromEnd() deallocates memory for the
  // node it removes, let it do the work.  Inefficient if
  // removeFromEnd() is inefficient, but ok for now.

  while (head != NULL)
    removeFromEnd();
}

/*
 * Function: insertAtBeginning
 * -----------------------
 * Add an item to the beginning of the list.
 */

template <class Item>
void List<Item>::insertAtBeginning(Item item)
{
  Node *newNode = new Node;
  newNode->item = item;
  newNode->next = head;
  head = newNode;
}

/*
 * Function: removeFromEnd
 * -----------------------
 * Remove the last node and return its item.  Since we
 * are only using a pointer to the beginning ("head"),
 * we have to do the inefficient thing and search for
 * the last node, maintaining a "previous" pointer.
 */

template <class Item>
Item List<Item>::removeFromEnd()
{
  if (head == NULL) {
    cerr << "can't remove from empty list" << endl;
    exit(1);  // Terminate program.
  } else {
    Node *removeNode = head;
    Node *prev = NULL;

    while (removeNode->next != NULL) {
      prev = removeNode;
      removeNode = removeNode->next;
    }
    
    // prev now points to the node before last
    if (prev == NULL) 	
	head = NULL; // empty list
    else
	prev->next = NULL;  // make second to last last

    // delete memory, saving the item before that
    Item item = removeNode->item;
    delete removeNode;
    
    return item;
  }
}

/*
 * Function: isempty
 * -----------------------
 * Tells whether list is empty or not.
 */

template <class Item>
bool List<Item>::isempty() const
{
  return head == NULL;
}