/*
 *          File: list.tem
 *        Author: Robert I. Pitts <rip@cs.bu.edu> 
 * Last Modified: Fall 2000
 *         Topic: Templates
 * -----------------------------------------------------
 *
 * This is the implementation for a linked list template 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.

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

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

template <class Item>
void List<Item>::insertAtBeginning(Item item)
{
  // Allocate new node.
  Node *newNode = new Node;

  // Put data in it.
  newNode->item = item;

  // Put node at beginning of linked list.
  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 {
    // Find the last node and the one before it.

    Node *removeNode = head;
    Node *prev = NULL;

    while (removeNode->next != NULL) {
      prev = removeNode;
      removeNode = removeNode->next;
    }

    // Save the item before we deallocate the node that contains it.
    Item savedItem = removeNode->item;

    if (prev == NULL)
      head = NULL;  // Removing first node.
    else
      prev->next = NULL;  // Making second to last the last node.

    delete removeNode;  // Remember to deallocate.

    return savedItem;
  }
}

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

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