/* This file contains the declaration of class LinkedList.

------------------------------------------------------------------*/

#include "Boolean.h"
#include "Strings.h"

#include <fstream.h>

typedef int ListElement;

/*
#include "Employee.h"
typedef Employee ListElement;
*/

/*
typedef Strings ListElement;
*/

class LinkedList
{                  // LinkedList data members are protected, to allow
protected:         //  them to be accessed by derived classes

   struct ListNode // use a struct so that LinkedList member functions
   {               //  can access the ListNode members
      ListElement
         Data;     // the value being stored
      ListNode
         *Next;    // the link to the next list node

      ListNode(void)
      {
         Next = 0;
      }

      ListNode(const ListElement& E, ListNode *Ptr = 0)
      {
         Data = E;
         Next = Ptr;
      }
   }
   *First,         // a pointer to the first node in the linked list
   *Last;          // a pointer to the last node in the linked list

   int
      NumNodes;    // the length of the linked list


public:

   /* This function initializes a LinkedList to be empty.

      Precondition:  The LinkedList containing this function has been
                     declared.
      Postcondition: That LinkedList is initialized as an empty list.
   -------------------------------------------------------------------*/

   LinkedList(void)
   {
     First = 0;
     Last = 0;
     NumNodes = 0;
   }

   /* This function displays a LinkedList on the screen.
      Receive: Out, the stream to which the values are to be sent;
               L, the list of values
      Output:  The values from L
      Return:  Out
   ------------------------------------------------------------------*/

   friend ostream& operator<<(ostream& Out, const LinkedList& L);

   /* This function constructs a copy of a LinkedList.

      Receive: L, a LinkedList to be copied
      Return:  the LinkedList containing this function, as a copy of L
   -------------------------------------------------------------------*/

   LinkedList(const LinkedList& L);

   /* This function finds the length of a LinkedList.

      Return:  The number of nodes in the LinkedList containing
                  this function
   ------------------------------------------------------------------*/

   int Length(void) const
   {
      return (NumNodes);
   }

   /* These functions access the ith element of a LinkedList.

      Receive: i, an (unsigned) list index.
      Return:  (a reference to) the element at index i.
   ------------------------------------------------------------------*/

   ListElement& operator[] (unsigned i);            // noncons version

   const ListElement& operator[] (unsigned i) const // const version

   /*-----------------------------------------------------------------
    This function inserts a ListElement into a LinkedList at a given
      index.

      Receive: A ListElement Elem
               An index Pos
      Return:  The LinkedList containing this function, with Elem
                  inserted at index Pos in it
   ------------------------------------------------------------------*/

   void Insert(const ListElement& Elem, int Pos);

   /*-----------------------------------------------------------------
   This function deletes the Node at position Pos from a LinkedList.

      Receive: Pos, an index value
      Return:  The LinkedList containing this function, with the
                  Node whose index is Pos removed
   -----------------------------------------------------------------*/

   Boolean Delete(int Pos);

   /*-----------------------------------------------------------------
   This function searches a LinkedList for a given ListElement.

      Receive: SearchVal, a ListElement
      Return:  The index of SearchVal within the LinkedList
                  containing this function if it is present,
                  -1 otherwise
   ------------------------------------------------------------------*/

   int LSearch(const ListElement& SearchVal) const;

   /* This function tears down a LinkedList.

      Precondition:  The lifetime of the LinkedList containing this
                        function is over.
      Postcondition: The memory allocated to this LinkedList has been
                        reclaimed.
   ------------------------------------------------------------------*/

   ~LinkedList(void);

   Boolean Empty(void) const {return (NumNodes == 0);}

   /* This function assigns one LinkedList to another.

      Receive: L, an LinkedList.
      Return:  The LinkedList containing this function,
                 as a copy of L.
   ------------------------------------------------------------------*/

   LinkedList& operator=(const LinkedList& L);

   enum {   Beginning = -2,
            End = -1 };

   /* This function concatenates two LinkedLists.

      Receive: L1 and L2, two LinkedLists;
      Return: The LinkedList consisting of L1 followed by L2.
   -----------------------------------------------------------------*/

   friend LinkedList operator&(const LinkedList& L1, const LinkedList& L2);

   Boolean Load(const Strings& FileName);

   Boolean Write(const Strings& FileName);

};