// ***********************************************************
// *                                                         *
// *  singlist.h                                             *
// *                                                         *
// *  Interface for a list class, implemented via            *
// *        singly-linked memory                             * 
// *                                                         *
// *  Written 5 May 1997 by Jason Zych                       * 
// *     Revised 20 February 1999 by Jason Zych              *
// *       - added headers for MP4 functions                 * 
// *                                                         *
// *********************************************************** 

#ifndef LIST_H
#define LIST_H

#include <stddef.h>
#include <iostream.h>
#include "asserts.h"
#include "array.h"

template <class Etype>
class ListNode
{
private:

   friend class List<Etype>; 
  
   // ListNode Constructor
   ListNode() { next = NULL; }

   Etype element;
   ListNode* next;
};



template <class Etype>
class List
{
public:


 // *** Allocation/Deallocation

   // List 
   //    - default constructor
   //    - creates an empty list
   List();
 
 
   // List 
   //    - copy constructor
   //    - parameters : origVal - a previously allocated List object 
   //    - initializes the list to be a copy of origVal 
   List(const List& origVal);


   // ~List
   //    - destructor 
   //    - deallocates all dynamically allocated memory inside the list 
   virtual ~List();


 // *** Mass Update

   // Clear
   //    - deletes all values from list, resulting in an empty list 
   void Clear(); 

   
   // operator=
   //    - parameters: origVal - a previously allocated List object
   //    - return value: reference to the List object
   //    - sets the the list to be a copy of origVal
   const List& operator= (const List& origVal);


 // *** Singular Update

   // InsertAfter
   //    - parameters : newElem - an element of the list's type, to be inserted
   //    - inserts newElem after current position in list
   void InsertAfter(Etype newElem); 


   // InsertBefore
   //    - parameters : newElem - an element of the list's type, to be inserted
   //    - inserts newElem before current position in list
   void InsertBefore(Etype newElem); 


   // Remove
   //    - removes the element at the current postition of the list
   void Remove();


   // Update
   //    - parameters : updateElem - an element of the list's type
   //    - replaces the value at the current position with updateElem 
   void Update(Etype updateElem); 


 // *** Traversal

   // Head
   //    - makes the first position in the list the current position 
   void Head();

   
   // Tail
   //    - makes the last position in the list the current position 
   void Tail();


   // operator++
   //    - moves the current position one forward in the list  
   List& operator++ (int);


   // operator--
   //    - moves the current position one backward in the list
   List& operator-- (int); 

 // *** Information Access 

   // Retrieve
   //    - returns the element at the current list position
   Etype Retrieve() const; 

   
   // Find 
   //    - parameters : queryElem - an element of the list's type, 
   //                       to be searched for
   //    - return value : a boolean yes or no
   //    - searches list for queryElem...if found, make that position the current
   //         position and return 1; otherwise, return 0 
   int Find(Etype queryElem); 


   // Length
   //    - return value : an integer representing the list's length 
   //    - returns the length of the list 
   int Length() const; 

// *** Output

   // Print
   //    - writes the individual elements of the list to the output
   //         stream object, and then returns that output stream object
   void Print() const;



// *** CS225 Spring 1999 MP4 functions


   // Replace
   //    - parameters : oldVal - the value we want to replace in the list
   //                 : newVal - the value we want to replace it with
   //    - replaces all occurences of oldVal in the list with newVal,
   //        and then sets current to be the first item in the list,
   //        if there are items in the list   
   void Replace(const Etype oldVal, const Etype newVal);

   
   // ToArray
   //    - return type : an Array object whose size is equal to the size
   //                       of the list
   //    - returns an Array containing the elements of the list, 
   //        appearing in the same order in the Array as they do in the list 
   //        Assumes list is non-empty. 
   Array<Etype> ToArray();


   // SortedInsert
   //    - parameters : insElem - the value we wish to insert 
   //    - inserts the parameter element in sorted order. This 
   //        function requires that operator< is defined for the 
   //        type in question, and assumes that the list is already
   //        sorted from smallest to largest value as defined by
   //        operator< on that type. The newly-inserted element
   //        should become the current element. 
   void SortedInsert(const Etype insElem);


   // Reverse 
   //    - reverses the order of the elements in the list 
   void Reverse();


   // Splice
   //    - parameters : spliceList - a list to be spliced into this list 
   //    - splices the values of spliceList into this list starting at the
   //        position after the current value of this list. When the
   //        function has completed, the current location indicator
   //        should be set to be the first element of this list, if any
   //        elements are in this list. The parameter list spliceList
   //        should be empty when you are done, as you are not splicing
   //        copies of the values of spliceList, but rather, you are
   //        splicing the values themselves.   
   void Splice(List& spliceList);


protected:

   ListNode<Etype> *head,        // points to first node of list
                   *current,     // points to node at current list position
                   *tail;        // points to last node of list

   int size;          // number of nodes in list

};


#endif 

   







