//
// Copyright (C) 1991 Texas Instruments Incorporated.
//
// Permission is granted to any individual or institution to use, copy, modify,
// and distribute this software, provided that this complete copyright and
// permission notice is maintained, intact, in all copies and supporting
// documentation.
//
// Texas Instruments Incorporated provides this software "as is" without
// express or implied warranty.
//
// Created: MJF 03/27/89 -- Initial design and implementation.
// Updated: MJF 04/15/89 -- Added a Base List class.
// Updated: MJF 06/01/89 -- Added const to member function arguments.
// Updated: MJF 06/21/89 -- Changed return types from List& to void or Boolean.
// Updated: MJF 08/10/89 -- Changed return values of methods to List reference
// Updated: MBN 08/20/89 -- Changed template usage to reflect new syntax
// Updated: LGO 10/02/89 -- Fix reference count bug in insert_after_node
// Updated: LGO 10/02/89 -- Set reference count to 1 in node constructor and
//                          eliminate many reference method calls.
// Updated: MBN 10/11/89 -- Change "current_position" to "curpos" and also
//                          "previous_position" to "prevpos"
// Updated: LGO 10/18/89 -- Get rid of the sort_test method
// Updated: LGO 10/18/89 -- Simplify the value method to avoid yacc stack oflow
// Updated: MBN 10/19/89 -- Added optional argument to set_compare method
// Updated: MBN 10/19/89 -- Added optional starting position to find method
// Updated: MBN 02/14/90 -- Make push return FALSE if out of heap memory
//
// A list is simply  made up  of a  collection of nodes.   Each node contains a
// reference count, a  pointer to  the next node  in  the  list, and the   data
// object.  An overview   of the structure of  the  List class,  along  with  a
// synopsis of each member and friend function, can be found in the Base_List.h
// header file.
//
//
//                      +--------+         +--------+         +--------+
//                      | Ref=2  |         | Ref=1  |         | Ref=2  |
//    +-------+         +--------+         +--------+         +--------+
//    | List--+---+---->| Next --+-------->| Next --+----+--->| Next 0 |
//    +-------+   |     +--------+         +--------+    |    +--------+
//                |     | Data   |         | Data   |    |    | Data   |
//                |     +--------+         +--------+    |    +--------+
//                |                                      |
//    +-------+   |                          +-------+   |
//    | List--+---+                          | List--+---+
//    +-------+                              +-------+
//

#ifndef LISTH					// If LIST not yet defined,
#define LISTH					// indicate class List done

#ifndef BASELISTH				// If Base LIST not defined,
#include <cool/Base_List.h>				// include Base_List header
#endif

#ifdef ERROR_CHECKING
#include <cool/Exception.h>
#endif

template <class Type> 
class List_Node<Type> : public List_Node {
  friend class List<Type>;
private:
  Type data;					// Data of node

public:
  List_Node<Type>(List_Node<Type>&);		// Constructor with reference
  List_Node<Type>(const Type& head, List_Node<Type>* tail);
  virtual void* get_data();			// Returns data element 
  virtual void  set_data(void*);		// Set data element
};

template <class Type> List {
  typedef Boolean (*Type##_List_Compare)(const Type&, const Type&);   // Compare function
  typedef Boolean (*Type##_List_Predicate)(const Type&, const Type&); // Predicate function
  DECLARE List_Node<Type>
}

template <class Type>
class List<Type> : public List {
private:
  static Type##_List_Compare compare_s;		// Function used by == test
  friend Boolean Type##_List_is_data_equal(const Type& a, const Type& b); // a==b

  List<Type>(List_Node<Type>*);			// Internal-use constructor
  virtual List* new_list(List_Node*);		// Creates a new list from node

  virtual List_Node* insert_before_node(void* v, List_Node* next_np);
  virtual List_Node* insert_after_node(void* v, List_Node* prev_np) CONST;

  virtual Boolean compare_data(CONST void*, CONST void*) CONST;
  virtual Boolean do_find(List_Node* np, const void* x,
			  List_Node_Ptr &cp, List_Node_Ptr &pp) CONST;

  virtual void output_data(ostream&, const List_Node*) CONST;

public:
  List<Type>();					// List<int> l;  a nil list.
  List<Type>(const Type& head);			// List<String> l1 = "333";
  List<Type>(const Type& head, List<Type>& tail);// List<String>l2 = ("a", l1);
  List<Type>(List<Type>& tail);			// List<String> l3 = l2;
  List<Type>(int n, ...);			// List<int> l4 = (3,11,22,33);
  ~List<Type>();				// Destructor for List object

  inline Type& value();				// Value at current position
  int position();				// Current position index

  inline void set_compare(Type##_List_Compare cf = NULL); // Sets Compare
  inline List<Type>& operator=(const List<Type>& l);	  // list1 = list2;

  Type& operator[](int n);			// x = l[n];
  inline Type& get(int n = 0);			// Returns nth data-node
  Boolean put(const Type& x, int n = 0);	// Sets nth data-node to x

  inline int position(const Type& x);		// Returns zero-relative index 
  inline List_state& current_position ();	// Set/Get current position
  inline Boolean find(const Type& x, List_state s = NULL); // True if contains x

  // returns true if THIS list contains element x and 
  // sets list l to a sublist in THIS list starting at first occurrence of x
  inline Boolean member(List<Type>& l, const Type& x);

  Boolean push(const Type& x);			// Adds x to head of this list
  inline Boolean push_new(const Type& x);	// Push if not already member
  inline Boolean push_end(const Type& x);	// Adds x at end of this list
  inline Boolean push_end_new(const Type& x);	// Push_end(x) if not member

  Boolean pop(Type& result);			// Removes head/returns data
  Type pop();					// Removes head/returns data

  Type& remove();				// Remove/return curpos
  inline Boolean remove(const Type& x);		// Removes first occurrence

  inline Boolean replace(const Type& old_data, const Type& new_data); 
  inline Boolean replace_all(const Type& old_data, const Type& new_data); 

  inline void sort(Type##_List_Predicate f);	// Sort list using predicate
  inline void merge(const List<Type>& l, Type##_List_Predicate f); // Merge

  inline Boolean insert_before(const Type& new_item); // Insert item before
  inline Boolean insert_after(const Type& new_item);  // Insert item after

  inline Boolean insert_before(const Type& new_item, const Type& targ_item);
  inline Boolean insert_after(const Type& new_item, const Type& targ_item);

  inline List<Type>& operator&(const List<Type>& l); // Intersection
  inline List<Type>& operator|(const List<Type>& l); // Union
  inline List<Type>& operator-(const List<Type>& l); // Difference
  inline List<Type>& operator^(const List<Type>& l); // XOR
  inline List<Type>& operator+(const List<Type>& l); // Concatenation

  inline List<Type>& operator&=(const List<Type>& l); // Intersection/assign
  inline List<Type>& operator|=(const List<Type>& l); // Union/assign
  inline List<Type>& operator-=(const List<Type>& l); // Difference/assign
  inline List<Type>& operator^=(const List<Type>& l); // XOR/assign
  inline List<Type>& operator+=(const List<Type>& l); // Concatenation/assign

#ifndef __cplusplus				// Inherintance works in 2.0
  inline friend ostream& operator<<(ostream& os, const List<Type>& l);
  inline friend ostream& operator<<(ostream& os, const List<Type>* l);
#endif
};

#ifndef STDARGH
#if defined(DOS)
extern "C" {
#include <stdarg.h>				// for variable arglists
}
#else
#include <stdarg.h>				// for varialbe arglists
#endif
#define STDARGH
#endif

// List_Node<Type>() -- A List Node constructor to create a node from head and
//                      tail specified
// Input:               A Type reference and List reference.
// Output:              None.

template <class Type> 
List_Node<Type>::List_Node<Type>(const Type& head, List_Node<Type>* tail) {
  this->ref_count = 1;
  this->next = tail;
  this->data = head;
}


// get_data()  -- Gets data of node.
// Input:         None.
// Output:        A void* pointer.

template <class Type> 
void* List_Node<Type>::get_data() {
  return &this->data;
}


// set_data()  -- Sets data of node to specified value.
// Input:         A void* pointer.
// Output:        None.

template <class Type> 
void List_Node<Type>::set_data(void* value) {
  this->data = *(Type*)value;
}


template <class Type> List {
  IMPLEMENT List_Node<Type>;
}


// set_compare() -- Sets the Compare function.
// Input:           A compare function pointer.
// Output:          None.

template <class Type> 
inline void List<Type>::set_compare(Type##_List_Compare cf) {
  if (cf == NULL)				// If no value supplied
    this->compare_s = &Type##_List_is_data_equal; // Use default compare
  else 
    this->compare_s = cf;			// Else set to user function
}


// value() -- Returns value at current position.
// Input:     None.
// Output:    A Type reference of data at current position.

template <class Type> 
inline Type& List<Type>::value() {
#ifdef ERROR_CHECKING  
  if (List::curpos == NULL)
    this->value_error (#Type);			// Raise exception
#endif
  return ((List_Node<Type>*) List::curpos)->data;
}


// position -- Return current position.
// Input:      THIS.
// Output:     An integer representing current position.

template <class Type> 
inline int List<Type>::position() {
  return List::position();
}


// current_position () -- Return current position state
// Input:                 None
// Output:                Reference to current position state

template <class Type> 
inline List_state& List<Type>::current_position () {
  return this->curpos;
}


// operator=() -- Assigns THIS to the specified list.
// Input:         A reference to a list which THIS will be assigned to.
// Output:        A reference to THIS.

template <class Type> 
inline List<Type>& List<Type>::operator=(const List<Type>& l) {
  return *(List<Type>*) List::operator=(l);
}

// get() -- Returns the nth node of THIS. With no arguments, returns first node
// Input:   A positive integer index (default 0).
// Output:  A Type reference of data in the nth node of THIS.

template <class Type> 
inline Type& List<Type>::get(int n) {
#if ERROR_CHECKING
  if (n < 0)
    this->get_error (#Type, n);
#endif
  return operator[](n);
}


// position() -- Returns the position of the specified data item in this list.
//               If item not in list, returns -1
// Input:        A Type reference to a data item.
// Output:       The integer position.

template <class Type> 
inline int List<Type>::position(const Type& x) {
  return List::position((CONST void*)&x);
}


// find() -- Returns TRUE if the specified element is a member of THIS list.
// Input:    A Type reference to data item to be searched.
// Output:   TRUE or FALSE.

template <class Type> 
inline Boolean List<Type>::find(const Type& x, List_state s) {
  if (s == NULL)				// If no starting position?
    s = this->node_ptr;				// Start at head of list
  return this->do_find(s, &x, this->curpos, this->prevpos); // Find and return
}

template <class Type> 
Boolean List<Type>::do_find(List_Node* np, const void* x,
			    List_Node_Ptr &cp, List_Node_Ptr &pp) CONST {
  List_Node* prev_np = NULL;
  for (; np != NULL; 
       prev_np = np, np = np->next_node())
    if ((*compare_s)(((CONST List_Node<Type>*) np)->data, *(CONST Type*)x)) {
      cp = np;					// found x
      pp = prev_np;
      return TRUE;
    }
  cp = NULL;
  pp = NULL;
  return FALSE;
}


// member() -- Returns the tail of THIS list beginning with the first
//             occurrence of the specified data item.
// Input:      A Type reference to data item to be searched.
// Output:     A list reference of some tail of THIS.

template <class Type> 
inline Boolean List<Type>::member(List<Type>& l, const Type& x) {
  return List::member(l, (CONST void*)&x);
}


// push() -- Prepends the specified data item to the front of this list
// Input:    A Type reference to the data item to be prepended.
// Output:   TRUE.

template <class Type> 
Boolean List<Type>::push(const Type& x) {
  List_Node* anode = new List_Node<Type>(x, (List_Node<Type>*) this->node_ptr);
  if (!anode)
    return FALSE;
  this->curpos = anode;
  this->node_ptr = anode;
  this->prevpos = NULL;
  return TRUE;
}


// push_new() -- Pushes the specified data item at front of this list if it is
//               not already a member 
// Input:        A reference to a new Type.
// Output:       TRUE if item not on list, FALSE otherwise.

template <class Type> 
inline Boolean List<Type>::push_new(const Type& x) {
  return List::push_new((CONST void*)&x);
}


// push_end() -- Appends the specified data item to the end of this list
// Input:        A Type reference to the data item to be appended.
// Output:       TRUE.

template <class Type> 
inline Boolean List<Type>::push_end(const Type& x) {
  return List::push_end((CONST void*)&x);
}


// push_end_new() -- Appends the specified data item to the end of THIS list
//                   if not already a member 
// Input:            A Type reference to the data item to be appended.
// Output:           TRUE if item not on list, FALSE otherwise.

template <class Type> 
inline Boolean List<Type>::push_end_new(const Type& x) {
  return List::push_end_new((CONST void*)&x);
}


// remove() -- Removes the first occurrence of the specified item in this list
// Input:      A refernce to data item to be removed.
// Output:     TRUE if item found and removed, FALSE otherwise.

template <class Type> 
inline Boolean List<Type>::remove(const Type& x) {
  return List::remove((CONST void*)&x);
}


// replace() -- Replaces the first occurrence of specified data item in THIS
//              list with a new value
// Input:       A reference to the data item to be replaced and the new value.
// Output:      TRUE if item found and replaced, FALSE otherwise.

template <class Type> 
inline Boolean List<Type>::replace(const Type& old_data, const Type& new_data) {
  return List::replace((CONST void*)&old_data, (CONST void*)&new_data);
}


// replace_all() -- Replaces all occurrences of the specified data item in THIS
//                  list with a new value.
// Input:           A reference to the data item to be replaced and new value.
// Output:          TRUE if at least one item found and replaced, else FALSE

template <class Type> 
inline Boolean List<Type>::replace_all(const Type& old_d, const Type& new_d) {
  return List::replace_all((CONST void*)&old_d, (CONST void*)&new_d);
}


// sort() -- Sorts the elements of THIS using the specified predicate function.
// Input:    A predicate function pointer.
// Output:   None.

template <class Type> 
inline void List<Type>::sort(Type##_List_Predicate f) {
  List::sort((Predicate)f);
}


// merge() -- Merges the elements of list with the elements of the specified
//            list sorted with the specified predicate function
// Input:     A reference to a list to be merged and a predicate function
//            pointer.
// Output:    None.

template <class Type> 
inline void List<Type>::merge(const List<Type>& l, Type##_List_Predicate f) {
  List::merge(l, (Predicate)f);
}


// insert_before() -- Inserts the specified item before the current position
// Input:             A Type reference of new item.
// Output:            TRUE if current position is valid, FALSE otherwise.

template <class Type> 
inline Boolean List<Type>::insert_before(const Type& new_item) {
#if ERROR_CHECKING
  if (this->curpos == NULL)
    this->before_error (#Type);
#endif
  return List::insert_before((CONST void*)&new_item);
}


// insert_after() -- Inserts the specified item after the current position
// Input:            A Type reference of new item.
// Output:           TRUE if current position is valid, FALSE otherwise.

template <class Type> 
inline Boolean List<Type>::insert_after(const Type& new_item) {
#if ERROR_CHECKING
  if (this->curpos == NULL)
    this->after_error (#Type);
#endif
  return List::insert_after((CONST void*)&new_item);
}


// insert_before() -- Inserts the specified new item before the specified
//                    target item in this list
// Input:             Two data Type references.
// Output:            TRUE if target item found, FALSE otherwise.

template <class Type> 
inline Boolean List<Type>::insert_before(const Type& new_item,
					 const Type& target_item) {
  return List::insert_before((CONST void*)&new_item,(CONST void*)&target_item);
}

// Boolean insert_after(Type&, Type&) -- inserts the specified new item
//                                       after the specified target item
//                                       in THIS list.
//
// Input:   Two data Type references.
// Output:  TRUE if target item found, FALSE otherwise.

template <class Type> 
inline Boolean List<Type>::insert_after(const Type& item, const Type& target) {
  return List::insert_after((CONST void*)&item, (CONST void*)&target);
}


// operator&() -- Intersection of a copy of THIS list with the specified list
// Input:         A reference to the list.
// Output:        A reference to a new list containing a copy of the elements
//                of THIS and the elements of the specified list.

template <class Type> 
inline List<Type>& List<Type>::operator&(const List<Type>& l) {
  return *(List<Type>*) List::operator&(l);
}


// operator|() -- Union of a copy of THIS list with the specified list
// Input:         A reference to the list.
// Output:        A reference to a new list containing a copy of the elements
//                of THIS and the elements of the specified list.

template <class Type> 
inline List<Type>& List<Type>::operator|(const List<Type>& l) {
  return *(List<Type>*) List::operator|(l);
}


// operator-() -- Difference of a copy of THIS list with the specified list.
// Input:         A reference to the list.
// Output:        A reference to a new list containing a copy of the elements
//                of THIS and the elements of the specified list.

template <class Type> 
inline List<Type>& List<Type>::operator-(const List<Type>& l) {
  return *(List<Type>*) List::operator-(l);
}


// operator^() -- Exclusive-or of a copy of THIS list with the specified list.
// Input:         A reference to the list.
// Output:        A reference to a new list containing a copy of the elements
//                of THIS and the elements of the specified list.

template <class Type> 
inline List<Type>& List<Type>::operator^(const List<Type>& l) {
  return *(List<Type>*) List::operator^(l);
}


// operator+() -- Concatenates a copy of THIS list with the specified list.
// Input:         A reference to the list to be concatenated.
// Output:        A reference to a new list containing a copy of the elements
//                of THIS and the elements of the specified list.

template <class Type> 
inline List<Type>& List<Type>::operator+(const List<Type>& l) {
  return *(List<Type>*) List::operator+(l);
}


// operator&=() -- Intersection of THIS list with the specified list.
// Input:          A reference to the list.
// Output:         A modified THIS.

template <class Type> 
inline List<Type>& List<Type>::operator&=(const List<Type>& l) {
  return *(List<Type>*) List::operator&=(l);
}


// operator|=() -- Union of THIS list with the specified list.
// Input:          A reference to the list.
// Output:         A reference to a new list containing a copy of the elements
//                 of THIS list and the elements of the specified list.

template <class Type> 
inline List<Type>& List<Type>::operator|=(const List<Type>& l) {
  return *(List<Type>*) List::operator|=(l);
}


// operator-=() -- Difference of THIS list with the specified list.
// Input:          A reference to the list.
// Output:         A modified THIS.

template <class Type> 
inline List<Type>& List<Type>::operator-=(const List<Type>& l) {
  return *(List<Type>*) List::operator-=(l);
}


// operator^=() -- Exclusive-or of THIS list with the specified list.
// Input:          A reference to the list.
// Output:         A modified THIS.

template <class Type> 
inline List<Type>& List<Type>::operator^=(const List<Type>& l) {
  return *(List<Type>*) List::operator^=(l);
}


// operator+=() -- Concatenates THIS list with the specified list.
// Input:          A reference to the list to be concatenated.
// Output:         A modified THIS.
//

template <class Type> 
inline List<Type>& List<Type>::operator+=(const List<Type>& l) {
  return *(List<Type>*) List::operator+=(l);
}


// List<Type>() -- a List constructor to create a List instance with no
//                 elements.  The node pointer is initialized to NULL.
// Input:          None.
// Output:         None.

template <class Type> 
List<Type>::List<Type>() {
  this->reset();
  this->set_compare(this->compare_s);
  this->node_ptr = NULL;
}


// List<Type>() -- A List constructor to create a List with one element
// Input:          A Type reference.
// Output:         None.

template <class Type> 
List<Type>::List<Type>(const Type& head) {
  this->reset();
  this->set_compare(this->compare_s);
  this->node_ptr = new List_Node<Type>(head, (List_Node<Type>*)0);
}


// List<Type>() -- A List constructor to create a List with the specified
//                 head element and list tail.
// Input:          A Type reference and List reference.
// Output:         None.

template <class Type> 
List<Type>::List<Type>(const Type& head, List<Type>& tail) {
  this->reset();
  this->set_compare(this->compare_s);
  this->node_ptr = new List_Node<Type>(head, (List_Node<Type>*)tail.node_ptr);
  this->reference(tail.node_ptr);
}


// List<Type>() -- A List constructor to create a List from the specified list.
// Input:          A List reference.
// Output:         None.

template <class Type> 
List<Type>::List<Type>(List<Type>& tail) {
  this->reset();
  this->compare_s = tail.compare_s;
  this->node_ptr = (List_Node<Type>*)tail.node_ptr;
  this->reference(this->node_ptr);
}


// List<Type>() -- A List constructor to initialize a List with "n" elements.
// Input:          The number of elements, and "n" data Type elements
// Output:         None.

template <class Type> 
List<Type>::List<Type>(int n, ...) {
  this->reset();
  this->set_compare(this->compare_s);
  if (n > 0) {
    va_list argp;
    va_start(argp, n);
    // add head node
    Type temp = va_arg(argp, Type);
    this->node_ptr = new List_Node<Type>(temp, (List_Node<Type>*)0);
    // add remaining nodes
    List_Node* prev_np = this->node_ptr;
    List_Node* next_np;
    for (int i = 1; i < n; i++) {
      temp = va_arg(argp, Type);
      next_np = new List_Node<Type>(temp, (List_Node<Type>*)0);
      prev_np->next_node() = next_np;
      prev_np = next_np;
    }
    va_end(argp);
  }
  else  this->node_ptr = (List_Node<Type>*)0;
}


// ~List<Type>() -- the List destructor will decrement reference counts
//                  starting at head node and free up memory allocated by
//                  these nodes if they are no longer referenced.
// Input:           None.
// Output:          None.

template <class Type> 
List<Type>::~List<Type>() {
  this->dereference(this->node_ptr);
}


// List<Type>() -- A List constructor used internally by List member functions
//                 to initialize a List object with an object with a pointer
//                 to a node structure
// Input:          The node pointer.
// Output:         None.

template <class Type> 
List<Type>::List<Type>(List_Node<Type>* head_node) {
  this->set_compare(this->compare_s);
  this->node_ptr = head_node;
  this->reference(this->node_ptr);
}


// new_list() -- Returns a new list with head node initialized to node.
// Input:        The node pointer.
// Output:       A pointer to the new list.

template <class Type> 
List* List<Type>::new_list(List_Node* head_node) {
  List<Type>* l = new List<Type>((List_Node<Type>*)head_node);
  return (List*) l;
}


// insert_before_node() -- Insert a new node before the specified node.
// Input:                  A Type reference and a Node pointer.
// Output:                 A pointer to the new node.

template <class Type> 
List_Node* List<Type>::insert_before_node(void* value, List_Node* next_np) {
  List_Node* anode = new List_Node<Type>(*(Type*)value, 
                                              (List_Node<Type>*)next_np);
  return anode;
}


// insert_after_node() -- Inserts a new node after the specified node.
// Input:                 A Type reference and a Node pointer.
// Output:                A pointer to the new node.

template <class Type> 
List_Node* List<Type>::insert_after_node(void* value, List_Node* prev_np) CONST {
  List_Node* anode = new List_Node<Type>(*(Type*)value, (List_Node<Type>*)0);
  // note that if prev_np is NULL,
  // then we just return a new node with no reference to it.
  if (prev_np != NULL) {
     anode->next_node() = prev_np->next_node();
     prev_np->next_node() = anode;
   }
  return anode;
}


// compare_data() -- Compares data using default compare function of this list
// Input:            Two void* pointers which will be type cast.
// Output:           None.

template <class Type> 
Boolean List<Type>::compare_data(CONST void* a, CONST void* b) CONST {
  return (*compare_s)(*(CONST Type*)a, *(CONST Type*)b);
}


// output_data()  -- Outputs node data from specified stream and is called
//                   by operator<<.
// Input:            An output stream reference and node pointer.
// Output:           A void* pointer of data.

template <class Type> 
void List<Type>::output_data(ostream& os, const List_Node* np) CONST {
  Type d = ((CONST List_Node<Type>*)np)->data;
  os << d;
}


// operator[]() -- Returns the nth node of THIS list.
// Input:          A positive integer index.
// Output:         A Type reference of data in the nth node of THIS.

template <class Type> 
Type& List<Type>::operator[] (int n) {
  List_Node<Type>* np = (List_Node<Type>*)List::operator[](n);
#if ERROR_CHECKING
  if (np == NULL)
    this->bracket_error (#Type, n);
#endif
  return np->data;
}


// put() -- Replaces the data slot of the nth node of this list and if
//          successful, returns the  new data item. With no arguments,
//          replaces the data at the first node.
// Input:   A Type reference and a positive integer index.
// Output:  TRUE if nth node exists, FALSE otherwise.

template <class Type> 
Boolean List<Type>::put(const Type& x, int n) {
  List_Node<Type>* np = (List_Node<Type>*)List::operator[](n);
  if (np != NULL) {
    np->data = x;
    return TRUE;
  }
  else return FALSE;
}


// pop() -- Removes and returns head element of THIS list.
// Input:   None.
// Output:  A copy of the head data element of THIS list.

template <class Type> 
Type List<Type>::pop() {
  List_Node<Type>* head = (List_Node<Type>*)List::pop();
#if ERROR_CHECKING
  if (head == NULL)
    this->pop_error (#Type);
#endif
  Type head_data = head->data;
  this->dereference(head);
  return head_data;
}


// pop(Type& result) -- Removes head node and returns data
// Input:   Reference to place to copy the result.
// Output:  returns TRUE when the list is empty

template <class Type> 
Boolean List<Type>::pop(Type& result) {
  List_Node<Type>* head = (List_Node<Type>*)List::pop();
#if ERROR_CHECKING
  if (head == NULL) 
    this->pop_error (#Type);
#endif
  result = head->data;
  this->dereference(head);
  return TRUE;
}


// remove() -- Removes item at current position.
// Input:      None.
// Output:     The item removed.

template <class Type> 
Type& List<Type>::remove() {
  List_Node<Type>* np = (List_Node<Type>*)List::remove();
#if ERROR_CHECKING
  if (np == NULL)
    this->remove_error (#Type);
#endif
  Type* new_data = new Type;
  *new_data = np->data;
  this->dereference(np);  // remove node
  return *new_data;
}


// is_data_equal() -- A private friend function used internnaly returning TRUE
//                    if a == b.  The default value of  the List Compare slot
//                    is set to the address of this function. This must be
//                    done to get the address of operator==.
// Input:             The two void* pointers to be compared.
// Output:            TRUE if items are equal, FALSE otherwise. 

template <class Type> List {
  Boolean Type##_List_is_data_equal(const Type& a, const Type& b) {
    return a == b;
  }
}

#ifndef __cplusplus				// Inherintance works in 2.0

// operator<<() -- Overload output operator for List objects.
// Input:          An output stream reference and List reference.
// Output:         An output stream reference.

template <class Type>
inline ostream& operator<< (ostream& os, const List<Type>& l) {
  return operator<<(os, (CONST List*)&l);
}


// operator<<() -- Overload output operator for List objects.
// Input:          An output stream reference and List pointer.
// Output:         An output stream reference.

template <class Type>
inline ostream& operator<< (ostream& os, const List<Type>* l) {
  return operator<<(os, (CONST List*)l);
}
#endif

#endif				// End #ifdef of LISTH
