//
// 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 -- Implemented Base list class.
// Updated: JCB 06/05/89 -- Fixed merge and sort.
// Updated: JCB 06/20/89 -- Implemented next_lunion, next_intersection,
//                          next_difference, next_exclusive_or.
// Updated: JCB 06/21/89 -- Modified next() and prev() to check for a current
//                          position not in THIS list, i.e. !traversal
// Updated: MJF 08/03/89 -- Improved operator== by checking for identical nodes
// Updated: MJF 08/10/89 -- Changed return values of operator+=, etc to List ref
// Updated: MJF 08/11/89 -- Changed methods which return new list references:
//                          tail, last, but_last, member, sublist and copy
// Updated: LGO 09/07/89 -- Made next, reference and dereference inline
// Updated: LGO 09/07/89 -- Moved the guts of find to the template classes.
// Updated: LGO 09/08/89 -- use do_find instead of compare_data in most places.
// Updated: LGO 09/08/89 -- Move push to the template classes.
// Updated: MBN 09/20/89 -- Added conditional exception handling
// Updated: LGO 10/05/89 -- Don't sort lists with less than 2 elements
// Updated: MBN 10/11/89 -- Change "current_position" to "curpos" and also
//                          "previous_position" to "prevpos"
// Updated: LGO 12/04/89 -- Make binary set operators not inline
// Updated: LGO 12/05/89 -- Make sort/merge predicate ANSI compatable
// Updated: MJF 03/12/90 -- Added group names to RAISE
// Updated: MJF 05/22/90 -- Fixed remove_duplicates
//
// This  file contains member and friend  function implementation code for  the
// List class defined in the  Base_List.h header  file.  Where appropriate  and
// possible, interfaces  to, and  us of,  existing system   functions has  been
// incorporated.  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.

#ifndef BASELISTH				// If List class not defined,
#include <cool/Base_List.h>				// include header file
#endif

List NIL = List();				// NIL -- Global NIL list


// get_data()  -- Gets data of node. There is no data for List class.
// Input:         None.
// Output:        A void* pointer.

void* List_Node::get_data() {
  cout << "\nWarning:  List_Node::get_data() has been called.\n";
  return 0;
}


// set_data()  -- Sets data of node to specified value. There is not data
//                to set for List class.
// Input:         A void* pointer.
// Output:        None.

void List_Node::set_data(void* value) {
  IGNORE(value);
#if ERROR_CHECKING
  RAISE (Warning, SYM(List_Node), SYM(Redundant_Method_Call),
	 "List_Node::set_data(): Method called is redundant");
#endif
}

// ~List -- Destructor (not inline because it's virtual)
// Input:         None
// Output:        None

List::~List () {;}

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

List* List::new_list(List_Node* np) {
  IGNORE(np);					       
#if ERROR_CHECKING
  RAISE (Warning, SYM(List_Node), SYM(Redundant_Method_Call),
	 "List_Node::new_list(): Method called is redundant");
#endif
  return (List*)0;  
}


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

List_Node* List::insert_before_node(void* value, List_Node* next_np) {
  IGNORE(value);
  IGNORE(next_np);					       
#if ERROR_CHECKING
  RAISE (Warning, SYM(List_Node), SYM(Redundant_Method_Call),
	"List_Node::insert_before_node(): Method called is redundant");
#endif
 return 0;
}


// 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.

List_Node* List::insert_after_node(void* value, List_Node* prev_np) CONST {
  IGNORE(value);
  IGNORE(prev_np);					       
#if ERROR_CHECKING
  RAISE (Warning, SYM(List_Node), SYM(Redundant_Method_Call),
	 "List_Node::insert_after_node(): Method called is redundant");
#endif
 return 0;
}


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

Boolean List::compare_data(CONST void* a, CONST void* b) CONST {
  IGNORE(a);
  IGNORE(b);
#if ERROR_CHECKING
  RAISE (Warning, SYM(List_Node), SYM(Redundant_Method_Call),
	 "List_Node::compare_data(): Method called is redundant");
#endif
  return FALSE;
}


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

void List::output_data(ostream& os, const List_Node* np) CONST {
  IGNORE(os);
  IGNORE(np);
#if ERROR_CHECKING
  RAISE (Warning, SYM(List_Node), SYM(Redundant_Method_Call),
	 "List_Node::output_data(): Method called is redundant");
#endif
}

void List::free_nodes(List_Node* np) {
  do {
    if (np->ref_count < 0) {
      cout << "\nWarning: negative ref count of " << np->ref_count;
      cout << " for data ";
      this->output_data(cout, np);
      cout << " and ";
#if GENERIC_TYPECHECK
      cout << (this->type_of())->name() << " = ";
#endif
      cout << this << ".\n";
    } 
    // no longer sharing this node with other Lists
    List_Node* next_np = np->next;     // save pointer to next node
    np->next = NULL;
//  delete np->data;			    // delete data of node
    delete np;				    // delete node structure
    np = next_np;			    // check reference of next node
  }
  while (np != NULL && --(np->ref_count) <= 0);
}


// Prev() -- decrement current position. If NULL, set it to last.
// Input:    None.
// Output:   TRUE or FALSE.

Boolean List::prev() {
  register List_Node* cp = this->curpos;
  List_Node* prev = this->prevpos;
  // if cp invalid (i.e. NULL) the following test will fail
  if (prev != NULL && prev->next == cp) {
    // already have the previous position
    cp = prev;
    this->prevpos = NULL; // this isn't needed, but why not...
  } else {
    // find previous node of current position
    // When cp is invalid, this finds the last node.
    register List_Node* np = this->node_ptr;
    prev = NULL;
    if (np != NULL) {
      while(np->next != cp)
	prev = np, np = np->next;
      cp = np;
      this->prevpos = prev;    
    }
  }
  // current position not found in list
  return (this->curpos = cp) != NULL;
}


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

List* List::operator=(const List& l) {
  this->reset();	// make current position invalid
  List_Node* new_np = l.node_ptr;
  this->dereference(this->node_ptr);
  this->reference(new_np);
  this->node_ptr = new_np;
  return this;
}


// operator== -- Returns TRUE if similar data in THIS and the specified List.
//               Uses the static list comparer function on elements.
// Input:        A list reference.
// Output:       TRUE or FALSE.

Boolean List::operator==(const List& l) CONST {
  if (this == &l) return TRUE;  // same lists
  for (List_Node *np = this->node_ptr, *np_l = l.node_ptr;
      np != NULL && np_l != NULL; 
      np = np->next, np_l = np_l->next) {
    if (np == np_l)
      return TRUE;   // same node pointers
    else if (!this->compare_data(np->get_data(), np_l->get_data()))
      return FALSE;
  }
  if (np == NULL && np_l == NULL) return TRUE;
  else return FALSE;
}


// operator[]() -- Returns the nth node of this list
// Input:          A positive integer index.
// Output:         A pointer to the nth node.

List_Node* List::operator[] (int n) {
  int count = n;
  for (List_Node *np = this->node_ptr, *prev_np = NULL;
      np != NULL && count > 0;
      prev_np = np, np = np->next, count--);

  // if n<length,  found nth node
  if (np != NULL && count == 0) {
    this->curpos = np;
    this->prevpos = prev_np;
    return np;
  }
  else return (List_Node*)0;  // or error
}


// tail() -- Sets list passed to the the nth tail of this list. With no 2nd
//           argument, tail() sets list passed to the 1st tail of this list.
// Input:    A list reference to store the nth tail elements of THIS and
//           the positive integer, n. (default 1)
// Output:   None.

void List::tail(List& l, int n) {
  this->dereference(l.node_ptr);
  int count = n;
  List_Node* np;
  for (np = this->node_ptr; np != NULL && count > 0; np = np->next, count--);
  // if n < length, return nth tail
  if (np != NULL && count == 0) {
    this->curpos = np;
    this->reference(np);
    l.node_ptr = np;
  }
  else l.node_ptr = 0;
}


// last() -- Sets list passed to the n last elements of this list. With no
//           2nd argument, sets list passed to the last element of thie list.
// Input:    A list reference to store the n last elements of THIS and
//           the positive interger, n (default 1).
// Output:   None.

void List::last(List& l, int n) {
  // last n elements = (size-n)th tail
  int nth = this->length() - n;   
  if (nth >= 0)
    tail(l, nth);
  else {
    this->dereference(l.node_ptr);
    l.node_ptr = 0;
  }
}


// but_last() -- Sets list passed to all but the last n elements of THIS list. 
//               With no 2nd argument, sets list passed to all but the last
//               element
// Input:        A positive integer (default 1).
// Output:       An altered THIS with all but the n last elements.

void List::but_last(List& l, int n) {
  this->reset();				// Current position invalid
  List_Node* np = this->node_ptr;
  this->dereference(l.node_ptr);
  if (n == 0) {
    this->reference(np);
    l.node_ptr = np;				// Points at all nodes of THIS
  }
  else {
    // get the number of nodes in this list and copy into list l
    int no_nodes = this->length() - n; 
    if (no_nodes > 0 && np != NULL)  {
      List_Node* first_np = this->insert_after_node(np->get_data(), 0);
      List_Node* rest_np = first_np;
      no_nodes--;
      for(np = np->next; 
	  np != NULL && no_nodes > 0; 
	  np = np->next, no_nodes--) {
	rest_np = this->insert_after_node(np->get_data(), rest_np);
      }
      this->reference(first_np);
      l.node_ptr = first_np;
    } else
      l.node_ptr = 0;
  }
}


// clear() -- Removes all nodes of THIS list.
// Input:     None.
// Output:    None.

void List::clear() {
  this->reset();	// make current position invalid   
  this->dereference(this->node_ptr);
  this->node_ptr = 0;
}


// length() -- Returns the number of elements in THIS list.
// Input:      None.
// Output:     An interger representing the number of elements in THIS.

int List::length() {
  int count = 0;
  for (List_Node* np = this->node_ptr; np != NULL; np = np->next, count++);
  return count;
}


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

int List::position() {
  if (this->curpos == NULL) return -1;
  int index = 0;
  for (List_Node* np = this->node_ptr;  np != NULL; np = np->next, index++)
    if (np == this->curpos) return index;
  return -1;
}


// position() -- Returns the position of the specified data item in this list,
//               else returns -1 if not found
// Input:        A void* pointer of a data item.
// Output:       The integer position.

int List::position(const void* x) {
  int index = 0;
  // NOTE: It's faster to call do_find, then count the position,
  // than to do the search ourselves using compare_data and get_data.
  if(!this->do_find(this->node_ptr, x, this->curpos, this->prevpos))
    return -1;
  else {
    int index = 0;
    List_Node* cp = this->curpos;
    List_Node* np = this->node_ptr;
    while (np != cp) np = np->next, index++;
    return index;
  }
}


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

Boolean List::do_find(List_Node* np, const void* x,
		      List_Node_Ptr &cp, List_Node_Ptr &pp) CONST {
  IGNORE(x);
  IGNORE(np);
  IGNORE(cp);
  IGNORE(pp);
  cout << "\nWarning:  List_Node::find(x) has been called.\n";
  return FALSE;
}


// search() -- Returns TRUE if the specified list is a subset of this list
// Input:      A reference to sublist to be searched.
// Output:     TRUE or FALSE.

Boolean List::search(const List& l) {
  List_Node* tnode = this->node_ptr;
  List_Node* lnode = l.node_ptr;
  if (tnode == lnode) {
    // this list and sublist l have same head node pointers
    this->curpos = tnode;
    this->prevpos = NULL;
    return TRUE;  
  }
  if (lnode == NULL) return FALSE;	// sublist l is nil
  while(tnode != NULL &&
	this->do_find(tnode, lnode->get_data(), this->curpos, this->prevpos)) {
    tnode = this->curpos;
    if (tnode == lnode) {
      // a node in this list and head node of list l are same
      return TRUE;
    }
    // data of node in this list is also in node of list l
    // continue searching rest of data
    for (List_Node *np2 = tnode->next, *lnp = lnode->next; 
	 np2 != NULL && lnp != NULL;
	 np2 = np2->next, lnp = lnp->next) {
      if (np2 == lnp) {
	// node in this list and node in list l are same
	return TRUE;
      }
      if  (!this->compare_data(np2->get_data(), lnp->get_data()))
	break;
    }
    if (lnp == NULL) {
      // found data of list l in this list
      return TRUE;
    }
    tnode = tnode->next;
  } 
  return FALSE;
}


// member() -- Returns TRUE if THIS list contains the specified element and
//             sets the specified list to a sublist in THIS list starting
//             at the first occurence of element.
// Input:      A reference to the list which will be set to a sublist within
//             THIS list, and a void* pointer of data item to be searched.
// Output:     A list pointer to some tail of THIS.

Boolean List::member(List& l,const void* x) {
  this->dereference(l.node_ptr);
  if (this->do_find(this->node_ptr, x, this->curpos, this->prevpos)) {
    this->reference(this->curpos);
    l.node_ptr = this->curpos;
    return TRUE;
  } else {
    l.node_ptr = 0;
    return FALSE;
  }
}


// sublist() -- Returns TRUE if THIS list contains second argument and sets
//              first argument to a sublist in THIS list starting at the 1st
//              occurence of second argument.
// Input:       A reference to the list which will be set to a sublist within
//              THIS list; and a reference to the list in search of.
// Output:      TRUE or FALSE.

Boolean List::sublist(List& l, const List& subl) {
  this->dereference(l.node_ptr);
  if (this->search(subl)) {
    this->reference(this->curpos);
    l.node_ptr = this->curpos;  
    return TRUE;
  } else {
    l.node_ptr = 0;
    return FALSE;
  }
}


// copy_nodes() -- Returns a copy of nodes in THIS list.
// Input:          NONE.
// Output:         The first node pointer of copy.

List_Node* List::copy_nodes() CONST {
  List_Node *np, *first_np;
  if ((np = this->node_ptr) == NULL)  
     first_np = NULL;
  else {
    // copy first node of this list
    first_np = this->insert_after_node(np->get_data(), 0);
    List_Node* rest_np = first_np;

    // copy rest of nodes of this list
    for (np = np->next; np != NULL; np = np->next) {
      rest_np = this->insert_after_node(np->get_data(), rest_np);
    }
  }
  return first_np;
}


// copy() -- Sets specified list with a copy of each element in this list
// Input:    The list reference which will be set with a new copy of each
//           element in this list
// Output:   None.

void List::copy(List& l) CONST {
  l.reset();	// make current position invalid
  l.dereference(l.node_ptr);
  List_Node* np = this->copy_nodes();
  l.reference(np); // **************** is this needed? - LGO *************
  l.node_ptr = np;
}


// reverse() -- Reverses the order of the elements of THIS list.
// Input:       None.
// Output:      None.

void List::reverse() {
  this->reset();				// Current position invalid
  List_Node *np, *np2, *rev_head;
  rev_head = NULL;
  for (np = this->node_ptr; np != NULL; np = np2) {
    np2 = np->next;
    np->next = rev_head;
    rev_head = np;
  }
  this->node_ptr = rev_head;
}


// push() -- Prepends the specified data item to the front of list
// Input:    A void* pointer of the data item to be prepended.
// Output:   Always TRUE.

Boolean List::push(const void* x) {
  this->curpos = this->insert_before_node(x, this->node_ptr);
  this->node_ptr = this->curpos;
  this->prevpos = NULL;
  return TRUE;
}


// push_new() -- Pushes a new element at head of THIS list if it is not already
//               a member of the list.
// Input:        A void* pointer of new data.
// Output:       TRUE if item not on list, FALSE otherwise.

Boolean List::push_new(const void* x) {
  List_Node* cp;
  List_Node* pp;
  if (!this->do_find(this->node_ptr, x, cp, pp)) // don't change curpos
    return push(x);
  else
    return FALSE;
}


// push_end() -- Appends the specified data item to the end of this list
// Input:        A void* pointer of the data item to be appended.
// Output:       Always TRUE.

Boolean List::push_end(const void* x) {
  List_Node* last_np = this->node_ptr;
  if (last_np == NULL) {  
    // there arn't any nodes in this list; x will be the head node
    this->node_ptr = this->curpos = this->insert_after_node(x, 0);
    this->prevpos = NULL;
  }
  else {
    List_Node* cp = this->curpos;
    // find last node of this list
    if (cp != NULL && cp->next == NULL)
      last_np = cp;
    else
      while(last_np->next != NULL) last_np = last_np->next;
    // insert x after last node
    this->curpos = this->insert_after_node(x, last_np);  
    this->prevpos = last_np;
  }
 return TRUE;
}


// push_end_new() -- Pushes a new element at end of THIS list if it is not
//                   already a member of the list.
// Input:            A void* pointer of new data.
// Output:           TRUE if item not on list, FALSE otherwise.

Boolean List::push_end_new(const void* x) {
  if (!this->do_find(this->node_ptr, x, this->curpos, this->prevpos))
    return this->push_end(x);
  else
    return FALSE;
}


// pop() -- Removes and returns head element of THIS list.
// Input:   None.
// Output:  Node pointer containing head data element of THIS list.

List_Node* List::pop() {
  List_Node* old_head = this->node_ptr;
  if (old_head != NULL) {
    this->reset();	// make current position invalid
    this->node_ptr = old_head->next;
    this->reference(old_head->next);
    return old_head;
  }
  else return NULL;
}


// prepend() -- Prepends the specified list to the front of this list and
//              returns TRUE if specified list is not NULL
// Input:       A reference to the list to be prepended.
// Output:      Always TRUE.

Boolean List::prepend(const List& l) {
  // first get copy of nodes in list l 
  List_Node* lnode = l.copy_nodes();
  if (lnode == NULL)
    return FALSE;
  // now prepend copy of list l to front of THIS list.  
  this->curpos = lnode;
  this->prevpos = NULL;
  List_Node* last_np = this->curpos;
  if (last_np != NULL) {  
    // find last node of list l
    while(last_np->next != NULL) last_np = last_np->next;
    // insert last node of list l in front of head node of this list
    // and set head node of this list to head node of list l
    last_np->next = this->node_ptr;
    this->node_ptr = this->curpos;
    this->reference(this->curpos);
  }
  return TRUE;
}


// append() -- Appends the specified list to the end of this list and returns
//             TRUE if specified list is not NULL.
// Input:      A reference to the list to be appended.
// Output:     TRUE or FALSE.

Boolean List::append(const List& l) {
  List_Node* lnode = l.node_ptr;
  if (lnode == NULL)
    return FALSE;
  this->curpos = lnode; // current position is head node of l
  List_Node* last_np = this->node_ptr;
  if (last_np == NULL) { 
    // there are no nodes in this;
    // just set head node of this list to head node of list l
    this->node_ptr = this->curpos;
    this->prevpos = NULL;
  }
  else {
    // find last node of this
    while(last_np->next != NULL) last_np = last_np->next;
    // add head node of list l after last node of this list
    last_np->next = this->curpos;
    this->prevpos = last_np;
  }
  this->reference(this->curpos);
  return TRUE;
}


// set_tail() -- Sets the nth tail of THIS list to the specified list
// Input:        A list reference, and a count (default 1).
// Output:       TRUE if nth tail exists, FALSE otherwise.

Boolean List::set_tail(const List& l, int n) {
  // find node at start of nth tail
  int count = n;
  for (List_Node *np = this->node_ptr, *prev_np = NULL; 
      np != NULL && count > 0;
      prev_np = np, np = np->next, count--);
  if (np != NULL && count == 0) {
     this->curpos = l.node_ptr;	// Current position=head node
     this->prevpos = prev_np;		// Previous position is nth-1
     // replace nth node with head node of list l
     if (prev_np == NULL) this->node_ptr = this->curpos; // when n=0
     else prev_np->next = this->curpos;	       // when n>0
     this->reference(this->curpos);
     // removing nth tail
     this->dereference(np);
     return TRUE;
   }
  return FALSE;
}


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

List_Node*  List::remove() {
  if (this->curpos == NULL)
    return NULL;
  List_Node* np = this->prevpos;
  List_Node* cp = this->curpos;
  if (np == NULL || np->next != cp) { 
    np  = this->node_ptr;
    if (np == cp) {			// node to remove is head node
      this->curpos = np->next;
      this->node_ptr = np->next;
      this->reference(np->next);
      return np;
    }
    // find previous node current position
    while (np != NULL && np->next != this->curpos) np = np->next;
    if (np == NULL) return NULL;  // error: current position was not in list
    else this->prevpos = np;
  }
  np->next = cp->next;
  this->curpos = cp->next;
  this->reference(cp->next);
  return cp;
}


// remove() -- Removes the first occurence 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.

Boolean List::remove(const void* x) {
  // find node for x
  if(this->do_find(this->node_ptr, x, this->curpos, this->prevpos)) {
    this->remove();
    return TRUE;
  }
  return FALSE;
}


// remove_duplicates() -- Removes all duplicate elements in THIS list.
// Input:                 None.
// Output:                TRUE if at least one item is removed, FALSE otherwise.

Boolean List::remove_duplicates() {
  Boolean success = FALSE; // return value
  List_Node* np = this->node_ptr;
  List_Node* np_next;
  while ((np != NULL) && ((np_next = np->next) != NULL)) {
    while (this->do_find(np_next, np->get_data(), this->curpos, this->prevpos))
      {
	this->remove();
	success = TRUE;
	if ((np_next = this->curpos) == NULL) break;
      }
    np = np->next;
  }
  return success;
}


// replace() -- Replaces the first occurence of specified data item in THIS
//              list with a new value
// Input:       Two void* pointers.
// Output:      TRUE if item found and replaced, FALSE otherwise.

Boolean List::replace(const void* old_data, const void* new_data) {
  // find node of old_data in this list
  if(this->do_find(this->node_ptr, old_data, this->curpos, this->prevpos)) {
    // replace old_data in node with new_data
    this->curpos->set_data(new_data);
    return TRUE;
  }
  return FALSE;
}


// replace_all() -- Replaces all occurences of the specified data item in THIS
//                  list with a new value.
// Input:           Two void* pointers.
// Output:          TRUE if at least one item found and replaced, else FALSE

Boolean List::replace_all(const void* old_data, const void* new_data) {
  this->reset();	// make current position invalid
  Boolean success = FALSE; // return value
  List_Node* pp;
  List_Node* np = this->node_ptr;
  while (np != NULL && this->do_find(np, old_data, np, pp)) {
    np->set_data(new_data);
    success = TRUE;
    np = np->next;
  }
  return success;
}


// sort() -- Sorts the elements of THIS using the specified predicate function.
//           The predicate function returns TRUE if and only if the first
//           element preceeds the second. The sort routine uses the Sort
//           algorithm as given in "Numerical Recipes in C" p247.
// Input:    A predicate function pointer.
// Output:   None.

void List::sort(Predicate f) {
  this->reset();	// make current position invalid
  List_Node* np;
  int l, j, ir, i;
  int n = this->length();
  if (n < 2) return;	// No sense sorting if less than two elements
  List_Node** node_array = new List_Node*[n+1];
  // put the nodes of THIS into an array which will be used by the
  // heap sort algorithm
  for (np = this->node_ptr, i = 1; np != NULL; np = np->next, i++)
     node_array[i] = np;
  // the heap sort algorithm
  List_Node* temp;
  l = (n >> 1) + 1;
  ir = n;
  while (TRUE) {
    if (l > 1)
      temp = node_array[--l];
    else {
      temp = node_array[ir];
      node_array[ir] = node_array[1];
      if (--ir == 1) {
	node_array[1] = temp;
	break;
      }
    }
    i = l;
    j = i << 1;
    while (j <= ir) {
      if (j < ir && (*f) ((node_array[j])->get_data(),
			  (node_array[j+1])->get_data()) < 0)
	++j;
      if ((*f) (temp->get_data(), (node_array[j])->get_data()) < 0) {
	node_array[i] = node_array[j];
	j += (i = j);
      }
      else
	j = ir + 1;
    }
    node_array[i] = temp;
  }

  // put the sorted nodes of the array back into THIS
  this->node_ptr = node_array[1];
  for (i = 1; i < n; i++) {
     (node_array[i])->next = node_array[i+1];
   }
  (node_array[n])->next = 0;

  delete [n+1] node_array;
}


// merge() -- Merges the elements of THIS list with the elements of the
//            specified list sorted with the specified predicate function.
//            If THIS is sorted already, then the result of the merge will be
//            sorted. Otherwise there are no guarantees for the sortedness of
//            the result.
// Input:     A reference to a list to be merged and a predicate function 
//            pointer.
// Output:    None.

void List::merge(const List& l, Predicate f) {
  this->reset();	// make current position invalid
  List_Node* tnode = this->node_ptr;
  if (tnode == NULL)
    // if this list is NULL, just assign this list to list l
    this->operator=(l);
  else {
    // begin merging list l into this list
    List_Node *lnode;

    // first merge nodes of list l in front of first node of this list
    // until a node in this list is less than a node in list l
    for (lnode = l.node_ptr;
	 lnode != NULL &&
	 (*f) (tnode->get_data(), lnode->get_data()) >= 0;
	 lnode = lnode->next) {
      tnode = this->insert_before_node(lnode->get_data(), tnode);
      this->node_ptr = tnode;
    }
      
    // merge rest of nodes in list l into this list
    List_Node* tnode_prev = tnode;
    tnode = tnode->next;
    while (lnode != NULL) {
      if (tnode == NULL) {
	// if the end of THIS is reached, 
	// add the list l nodes to the end of this list
	for (; lnode !=NULL; lnode = lnode->next)
	  tnode_prev = this->insert_after_node(lnode->get_data(), tnode_prev);
      }
      else if ((*f)(tnode->get_data(), lnode->get_data()) < 0) {
	// if node in this list is less than node in list l
	// just go to next node in this list
	tnode_prev = tnode;
	tnode = tnode->next;      
      } else {
	// if node in list l is less than node in this list
	// insert the list l node into THIS
	// and goto next node in list l
	tnode_prev->next = this->insert_before_node(lnode->get_data(), tnode);
	tnode_prev = tnode_prev->next;
	lnode = lnode->next;
      }
    }
  }
}


// insert_before() -- Inserts the specified item before the current position
// Input:             A void* pointer.
// Output:            TRUE if current position is valid, FALSE otherwise.

Boolean List::insert_before(const void* new_item) {
  List_Node* cp = this->curpos;
  List_Node *np = this->prevpos;
  if (cp == NULL)
    return FALSE;
  if (np == NULL || np->next != cp) {
    np = this->node_ptr;
    // current position is head node    
    if (np == cp)
      return this->push(new_item);
    // find previous node of current position in list
    while (np != NULL && np->next != cp) np = np->next;
    if (np == NULL)
      return FALSE;  // couldn't find current position
    else
      this->prevpos = np;
  }
  // insert new_item before current position and
  // set current position to this new node
  this->curpos = this->insert_before_node(new_item, cp);
  np->next = this->curpos;
  return TRUE;
}


// insert_after() -- Inserts the specified item after the current position
// Input:            A void* pointer.
// Output:           TRUE if current position is valid, FALSE otherwise.

Boolean List::insert_after(const void* new_item) {
  if (this->curpos == NULL)
    return FALSE;
  this->prevpos = this->curpos;
  this->curpos = this->insert_after_node(new_item,
						   this->curpos);
  return TRUE;
}


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

Boolean List::insert_before(const void* new_item, const void* target_item) {
  // find node with target item
  if (this->do_find(this->node_ptr, target_item, this->curpos, this->prevpos)){
    List_Node *np = this->curpos;
    List_Node *prev_np = this->prevpos;
    // insert new item before target item
    this->curpos = this->insert_before_node(new_item, np);
    if (prev_np == NULL)
      this->node_ptr = this->curpos;	 // new item is the head node
    else
      prev_np->next = this->curpos; // new item is a  middle node
    return TRUE;
  }
  return FALSE;
}


// insert_after() -- Inserts the specified new item after the specified target
//                   item in this list
// Input:            Two data void* pointers.
// Output:           TRUE if target item found, FALSE otherwise.

Boolean List::insert_after(const void* new_item, const void* target_item) {
  // find node with target item
  List_Node *np;
  if (this->do_find(this->node_ptr, target_item, np, this->prevpos)) {
    this->curpos = this->insert_after_node(new_item, np);
    this->prevpos = np;
    return TRUE;
  }       
  return FALSE;
}


// intersection() -- Changes THIS list to contain everything that is an element
//                   of both this and the specified list.
// Input:            A reference to list.
// Output:           None.

void List::intersection(const List& l) {
  this->reset();	// make current position invalid
  if (l.node_ptr == NULL)
    this->clear();
  else {
    List_Node* np = this->node_ptr;
    List_Node* prev_np = NULL;
    List_Node* next_np;
    while(np != NULL) {
      List_Node* cp;
      List_Node* pp;
      if (!l.do_find(l.node_ptr, np->get_data(), cp, pp)) {
        next_np = np->next;
        if (prev_np == NULL) this->node_ptr = np->next; // next node is at head
        else prev_np->next = np->next;		     // next node is in middle
        this->reference(np->next);
        this->dereference(np);   // delete np from this List.
        np = next_np;	   // set to next node to look at
      }
      else {
        prev_np = np; 
        np = np->next;
      }
    }
  }
}


// lunion() -- Changes THIS list to contain everything that is an element of
//             either THIS or the specified list
// Input:      A reference to list.
// Output:     None.

void List::lunion(const List& l) {
  this->reset();	// make current position invalid
  List_Node* tnode = this->node_ptr;
  List_Node* lnode = l.node_ptr;
  if (tnode ==  NULL && lnode != NULL) { 
    // this list is empty, so set head node of this list to head node of list l
    this->node_ptr = lnode;
    this->reference(lnode);
  }
  else
    for (; lnode !=NULL; lnode = lnode->next) {
      List_Node* cp;
      List_Node* pp;
      if (!do_find(this->node_ptr, lnode->get_data(), cp, pp))
	this->push(lnode->get_data());
    }
}


// difference() -- Removes from THIS list the elements which also appears in
//                 the specified list.
// Input:          A reference to list.
// Output:         None.

void List::difference(const List& l) {
  this->reset();	// make current position invalid
  if (l.node_ptr != NULL) {
    List_Node* np = this->node_ptr;
    List_Node* prev_np = NULL;
    List_Node* next_np;
    // if node in this list is found in list l, remove it from this list
    while(np != NULL) {
      List_Node* cp;
      List_Node* pp;
      if (l.do_find(l.node_ptr, np->get_data(), cp, pp)) {
        next_np = np->next;
        if (prev_np == NULL) this->node_ptr = np->next;	// Next node is at head
        else prev_np->next = np->next;		   // next node is in middle
        this->reference(np->next);
        this->dereference(np);   // delete np from this List.
        np = next_np;	   // set to next node to look at
      }
      else {
        prev_np = np; 
        np = np->next;
      }
    }
  }
}


// exclusive_or() -- Changes list to contain those eleme ts which appear in
//                   exactly one of THIS list and the specified list.
// Input:            A reference to list.
// Output:           None.

void List::exclusive_or(const List& l) {
  this->reset();	// make current position invalid
  // first get copy of nodes in list l
  List* lcopy = this->new_list((List_Node*)0);
  l.copy(*lcopy);
  // remove elements in this list from copy of list l
  lcopy->difference(*this);
  // remove elements in list l from this list  
  this->difference(l);
  // append elements left in lcopy to end of this list
  this->append((List&)*lcopy);
  delete lcopy;
}


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

List* List::operator+(const List& l) {
  this->reset();	// make current position invalid
  // just return a copy of this list, if list l is nil
  List_Node* lnode = l.node_ptr;
  if (lnode == NULL) return this->new_list(this->copy_nodes());
  // just return a copy of  list l, if this list is nil
  List_Node* tnode = this->node_ptr;
  if (tnode == NULL) return this->new_list(l.copy_nodes());
  // get copy of each node in  this list and remember last node;
  List_Node *first_np, *last_np;
  first_np = this->insert_after_node(tnode->get_data(), 0);
  last_np = first_np;
  for (List_Node* np = tnode->next; np != NULL; np = np->next)
    last_np = this->insert_after_node(np->get_data(), last_np);
  // now add copy of each node in list l to end of this list copy
  for (np = lnode; np != NULL; np = np->next)
     last_np = this->insert_after_node(np->get_data(), last_np);
  return this->new_list(first_np);
}


// next_intersection() -- Sets current position to next item in the
//                        intersection of this list and the specified list.
// Input:                 None.
// Output:                TRUE if the next item exists,  FALSE otherwise.

Boolean List::next_intersection(const List& l) {
  List_Node* np = this->curpos;
  if (!this->traversal) {			// end of intersection
    this->curpos = NULL;
    return FALSE;
  }
  if (np == NULL)				// starting fresh
    np = this->node_ptr;
  else
    np = np->next;				// increment position
  for (; np != NULL; np = np->next) {
    List_Node* cp;
    List_Node* pp;
    if (l.do_find(l.node_ptr, np->get_data(), cp, pp)) {
      this->curpos = np;
      return TRUE;
    }
  }
  this->traversal = FALSE;			// now traversing second list
  return FALSE;
}


// next_lunion() -- Sets current position to next item in the union of this
//                  list and the specified list.
// Input:           None.
// Output:          TRUE if the next item exists,  FALSE otherwise.

Boolean List::next_lunion(const List& l) {
  List_Node* np = this->curpos;
  if (np == NULL && !this->traversal)		// end of both lists
    return FALSE;
  if (np == NULL && this->traversal)		// starting fresh
    np = this->node_ptr;
  else  
    if (np->next == NULL && this->traversal) {	// end of first list
      this->traversal = FALSE;			// now traversing second list
      np = l.node_ptr;
    }
  else
    if (!this->traversal)  np = np->next;	// increment position

  if (this->traversal) {			// still in this list
    if (this->curpos != NULL) 
      this->curpos = np->next;	// increment current position
    else this->curpos = np;
    return TRUE;			
  }

  for (; np != NULL; np = np->next) {
    List_Node* cp;
    List_Node* pp;
    if (!do_find(this->node_ptr, np->get_data(), cp, pp)) {
      this->curpos = np;
      return TRUE;
    }
  }
  return FALSE;
}


// next_difference() -- Sets current position to next item in the difference
//                      of this list and the specified list
// Input:               None.
// Output:              TRUE if the next item exists,  FALSE otherwise.

Boolean List::next_difference(const List& l) {
  List_Node* np = this->curpos;
  if (np == NULL && !this->traversal) {  	// end of this list
    return FALSE;
  }
  if (np == NULL)				// starting fresh
    np = this->node_ptr;
  else {
    this->traversal = FALSE;			// now traversing second list
    np = np->next;				// incrementing position
  }
  for (; np != NULL; np = np->next) {
    List_Node* cp;
    List_Node* pp;
    if (!l.do_find(l.node_ptr, np->get_data(), cp, pp)) {
      this->curpos = np;
      return TRUE;
    }
  }
  return FALSE;
}


// next_exclusive_or() -- Sets current position to next item in exclusive_or
//                        of this list and the specified list.
// Input:                 None.
// Output:                TRUE if the next item exists,  FALSE otherwise.

Boolean List::next_exclusive_or(const List& l) {
  List_Node* cp;
  List_Node* pp;
  List_Node* np = this->curpos;
  if (!this->traversal && np == NULL)		// end of both lists
    return FALSE;
  if (np == NULL && this->traversal)		// starting fresh
    np = this->node_ptr;
  else 
    if (np->next == NULL && this->traversal) {	// end of first list
      this->traversal = FALSE;			// now traversing second list
      np = l.node_ptr;
    }
  else
    np = np->next;				// increment position
  if (this->traversal) {			// still in this list
    for (; np != NULL; np = np->next) 
      if (!l.do_find(l.node_ptr, np->get_data(), cp, pp)) {
        this->curpos = np;
	return TRUE;			
      } 
    this->traversal = FALSE;			// now traversing second list
    np = l.node_ptr; 
  }
  for (; np != NULL; np = np->next)
    if (!do_find(this->node_ptr, np->get_data(), cp, pp)) {
      this->curpos = np;
      return TRUE;
    }
  return FALSE;
}


// describe() -- Describes internal structure of each node of this list
// Input:        The output stream to display description on.
// Output:       None.

void List::describe(ostream& os) {
  os << "\nList " << this << ":\n";
  int count = 0;
  for (List_Node* np = this->node_ptr; np != NULL; np = np->next, count++) 
  {
    os << "Node" << count << ":\n";
    os << " Data = ";
    this->output_data(os,np);
    os << "\n";
    os << " Ref count = " << np->ref_count << "\n";
  }
}


// value_error -- Raise exception for List::value() method
// Input:         Type string
// Output:        None

void List::value_error (const char* Type) {
  RAISE (Error, SYM(List), SYM(Invalid_Cpos),
	 "List<%s>::value(): Invalid current position", Type);
}


// get_error -- Raise exception for List::get() method
// Input:       Type string
// Output:      None

void List::get_error (const char* Type, int n) {
  RAISE (Error, SYM(List), SYM(Negative_Index),
	 "List<%s>::get(): Negative index %d", Type, n);
}


// before_error -- Raise exception for List::insert_before() method
// Input:          Type string
// Output:         None

void List::before_error (const char* Type) {
  RAISE (Error, SYM(List), SYM(Invalid_Cpos),
	 "List<%s>::insert_before(): Invalid current position", Type);
}


// after_error -- Raise exception for List::insert_after() method
// Input:         Type string
// Output:        None

void List::after_error (const char* Type) {
  RAISE (Error, SYM(List), SYM(Invalid_Cpos),
	 "List<%s>::insert_after(): Invalid current position", Type);
}


// bracket_error -- Raise exception for List::operator[]() method
// Input:           Type string
// Output:          None

void List::bracket_error (const char* Type, int n) {
  RAISE (Error, SYM(List), SYM(Negative_Index),
	 "List<%s>::operator[](): Negative index %d", Type, n);
}


// pop_error -- Raise exception for List::pop() method
// Input:       Type string
// Output:      None

void List::pop_error (const char* Type) {
  RAISE (Error, SYM(List), SYM(No_Elements),
	 "List<%s>::pop(): No elements in list", Type);
}


// remove_error -- Raise exception for List::remove() method
// Input:          Type string
// Output:         None

void List::remove_error (const char* Type) {
  RAISE (Error, SYM(List), SYM(Invalid_Cpos),
	 "List<%s>::remove(): Invalid current position", Type);
}


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

ostream& operator<<(ostream& os, const List* l) {
  os << "(";
  List_Node* np = l->node_ptr;
  if (np != NULL) {
    l->output_data(os, np);
    for (np = np->next; np != NULL; np = np->next) {
      os << " ";
      l->output_data(os,np);
    }
  }
  return os << ")";
}


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

ostream& operator<<(ostream& os, const List& l) {
  return operator<<(os, &l);
}


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

List* List::operator&(const List& l) {
  List* lc = this->new_list((List_Node*)0);
  this->copy(*lc);
  lc->intersection(l);
  return lc;
}


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

List* List::operator|(const List& l) {
  List* lc = this->new_list((List_Node*)0);
  this->copy(*lc);
  lc->lunion(l);
  return lc;
}


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

List* List::operator-(const List& l) {
  List* lc = this->new_list((List_Node*)0);
  this->copy(*lc);
  lc->difference(l);
  return lc;
}


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

List* List::operator^(const List& l) {
  List* lc = this->new_list((List_Node*)0);
  this->copy(*lc);
  lc->exclusive_or(l);
  return lc;
}
