/* This file contains the implementation for class LinkedList.

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

#include "LinkedList.h"

#include <assert.h>
#include <stdlib.h>

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

ostream& operator<<(ostream& Out, const LinkedList& L)
{
   LinkedList::ListNode
      *TempPtr = L.First;          // start at the list's beginning

   while (TempPtr != 0)            // while there are unvisited nodes:
   {
      Out << TempPtr->Data << ' '; //   display the node's data
      TempPtr = TempPtr->Next;     //   advance TempPtr to next node
   }

   return Out;                     // return ostream for chaining
}

/*-----------------------------------------------------------------
   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::LinkedList(const LinkedList& L)
{
   ListNode
      *OldNode = L.First,                // Ptr to node being copied
      *NewNode = 0;                      // Ptr to copied node

   NumNodes = L.NumNodes;                // copy scalar field

                                         // COPY L'S FIRST NODE:
   if (NumNodes == 0)                    // if L is empty
      First = 0;                         //   set First to NULL
   else                                  // otherwise
   {                                     //
      NewNode =
         new ListNode(OldNode->Data);    //   make a copy of OldNode
      assert(NewNode != 0);              //   verify
      OldNode = OldNode->Next;           //   move OldNode to next node
      First = NewNode;                   //   set First to new Node
   }
                                         // COPY THE REMAINING NODES:
   while (OldNode != 0)                  //  while not at end-of-list
   {
      NewNode->Next =
         new ListNode(OldNode->Data);    //    make a copy of OldNode
      assert(NewNode->Next != 0);        //    verify
      NewNode = NewNode->Next;           //    move NewNode to next node
      OldNode = OldNode->Next;           //    move OldNode to next node
   }

   Last = NewNode;                       // update Last
}

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

   Receive: i, an (unsigned) list index.
   Return:  (a reference to) the element at index i.
------------------------------------------------------------------*/
//nonconstant version
ListElement& LinkedList::operator[] (unsigned i)
{
   if (i >= NumNodes)               // check for range error
   {
      cerr << "\n*** LinkedList Subscript: index " << i
           << " is outside of List !\n";
      exit (-1);
   }

   ListNode
      *Position = First;            // pointer to first node

   for (int j = 0; j < i; j++)      // move through the list
      Position = Position->Next;    //   to the i-th node

   return Position->Data;
}

//constant version
const ListElement& LinkedList::operator[] (unsigned i) const
{
   if (i >= NumNodes)               // check for range error
   {
      cerr << "\n*** LinkedList Subscript: index " << i
           << " is outside of List !\n";
      exit (-1);
   }

   ListNode
      *Position = First;            // pointer to first node

   for (int j = 0; j < i; j++)      // move through the list
      Position = Position->Next;    //   to the i-th node

   return Position->Data;
}


/*-----------------------------------------------------------------
 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 LinkedList::Insert(const ListElement& Elem, int Pos)
{
  if ((Pos >= NumNodes) &&
      (Pos != LinkedList::End))        // check for range error
    {
      cerr << "\n*** LinkedList Insert: index " << Pos
           << " is past the end of the list!\n";
      Pos = LinkedList::End;
    }
  else if (Pos < LinkedList::Beginning)
    {
      cerr << "\n*** LinkedList Insert: index " << Pos
           << " is before the beginning of the list!\n";
      Pos = LinkedList::Beginning;
    }

  ListNode                             // build new Node
    *NewPtr = new ListNode(Elem);      //   containing Elem

  assert(NewPtr != 0);                 // verify

  if (Pos == LinkedList::Beginning)    // if inserting at beginning
  {
     NewPtr->Next = First;             //   set Next to first Node
     First = NewPtr;                   //   make First point to NewPtr
     if (NumNodes == 0)                //   if List is empty
        Last = NewPtr;                 //     update Last as well
  }
  else if ((Pos == LinkedList::End) || // else if inserting at the end
           (Pos == NumNodes))
  {
     if (NumNodes == 0)                //   if List is empty
        First = NewPtr;                //      update First
     else                              //   otherwise
        Last->Next = NewPtr;           //      attach to end of list
     Last = NewPtr;                    //   update Last
  }

  else
  {
     ListNode
        *PrevPtr = First;              // start at the beginning

     for (int i = 0; i < Pos - 1; i++)// find the node just before
        PrevPtr = PrevPtr->Next;       //   the insertion point

     NewPtr->Next = PrevPtr->Next;     // append trailing nodes to new node
     PrevPtr->Next = NewPtr;           // append new node to prior nodes
  }

  NumNodes++;                          // increment NumNodes;
}

/*-----------------------------------------------------------------
 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 LinkedList::Delete(int Pos)
{                                          // check if valid index
   if ((Pos >= NumNodes) && (Pos != LinkedList::End))
   {
      cerr << "\n*** LinkedList Delete: index " << Pos
           << " is past the end of the list!\n";
      Pos = LinkedList::End;
   }
   else if (Pos < LinkedList::Beginning)
   {
      cerr << "\n*** LinkedList Delete: index " << Pos
           << " is before the beginning of the list!\n";
      Pos = LinkedList::Beginning;
   }

   ListNode                                 // pointer to node
      *DelPtr;                              //   being deleted

   if ((Pos == LinkedList::Beginning) ||    // if deleting first node
      ((Pos == LinkedList::End) && (NumNodes == 1)))
   {
      DelPtr = First;                       //   save the node
      First = First->Next;                  //   remove it from list
      DelPtr->Next = 0;
   }
   else                                     // otherwise
   {
      if (Pos == LinkedList::End)           //  if deleting last node
         Pos = NumNodes-1;                  //    reset Pos correctly

      ListNode
         *PredPtr = First;                  //   start at beginning

      for (int Pred = 1; Pred < Pos; Pred++)//  find predecessor of
         PredPtr = PredPtr->Next;           //    node being removed

      DelPtr = PredPtr->Next;               //  save node
                                            //    being removed
      PredPtr->Next = DelPtr->Next;         //  remove node from list
      DelPtr->Next = 0;

      if (Pos == NumNodes - 1)
         Last = PredPtr;
   }

   delete DelPtr;                          // deallocate node
   NumNodes--;                             // update nodecounter

   return True;
}

/*-----------------------------------------------------------------
 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 LinkedList::LSearch(const ListElement& SearchVal) const
{
   ListNode
      *NodePtr = First;                // start at the beginning

   for (int i = 0; i < NumNodes; i++)  // check each node in sequence
      if (NodePtr->Data == SearchVal)  // if it's the one we seek
         return i;                     //   return its index
      else                             // otherwise
         NodePtr = NodePtr->Next;      //   move on to the next node

   return -1;                          // indicate search failure
}

/*-----------------------------------------------------------------
   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::~LinkedList(void)
{
   ListNode
      *TempPtr = First;       // set TempPtr to first node

   while (TempPtr != 0)       // while there are nodes to be deleted:
   {
      First = First->Next;    //   move First to the next node
      delete TempPtr;         //   delete the current node
      TempPtr = First;        //   update TempPtr
   }

   NumNodes = 0;              // set NumNodes to zero
   Last = 0;                  // set Last to NULL
}

/*-----------------------------------------------------------------
This function assigns one LinkedList to another.

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

LinkedList& LinkedList::operator=(const LinkedList& L)
{
  ListNode
    *LNode = L.First,                // position within L
    *ThisNode = 0,                   // position within this LinkedList
    *TempPtr = First;                // set TempPtr to first node

  while (TempPtr != 0)               // while there are nodes to be deleted:
  {
     First = First->Next;            //   move First to the next node
     delete TempPtr;                 //   delete the current node
     TempPtr = First;                //   update TempPtr
  }

  NumNodes = 0;                      // set NumNodes to zero
  Last = 0;                          // set Last to NULL

  NumNodes = L.NumNodes;             // copy scalar field

                                     // copy L's first Node:
  if (NumNodes == 0)                 // if L is empty
    First = 0;                        //   set First to NULL
  else                               // otherwise
    {
      ThisNode = new ListNode(       //   allocate a Node whose Data
                       LNode->Data); //    is a copy of L's Data
      assert(ThisNode != 0);         //   verify
      LNode = LNode->Next;           //   move to next Node in L
      First = ThisNode;               //   set First to first Node
    }
                                     // copy the remaining Nodes
  while (LNode != 0)                 //  while not at end-of-list
    {
      ThisNode->Next = new ListNode( //    allocate a new Node whose Data
                       LNode->Data);//       is a copy of L's Data
      assert(ThisNode->Next != 0);   //    verify
      ThisNode = ThisNode->Next;     //    move to the new Node
      LNode = LNode->Next;           //    move to next Node in L
    }

  Last = ThisNode;                   // make Last point at last Node

  return (*this);                    // allow chaining
}

/*-----------------------------------------------------------------
This function concatenates two LinkedLists.

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

LinkedList operator&(const LinkedList& L1, const LinkedList& L2)
{
  LinkedList
    ReturnList = L1;

  LinkedList::ListNode
    *NodePtr = L2.First;

  while (NodePtr != 0)
    {
      ReturnList.Insert(NodePtr->Data, LinkedList::End);
      NodePtr = NodePtr->Next;
    }

  return ReturnList;
}

Boolean LinkedList::Load(const Strings& FileName)
{
  fstream
    In(FileName, ios::in);

  if (In.bad())
    {
      cerr << "\n*** Load: unable to open file " << FileName << endl;
      exit(-1);
    }

  ListElement
    E;

  for (;;)
    {
      In >> E;
      if (In.eof())
        break;

      Insert(E, LinkedList::End);
    }

  In.close();

  return 1;
}

Boolean LinkedList::Write(const Strings& FileName)
{
  fstream
    Out(FileName, ios::out);

  if (Out.bad())
    {
      cerr << "\n*** Write: unable to open " << FileName << endl;
      exit (-1);
    }

  ListNode
    *NodePtr = First;

  while (NodePtr != 0)
    {
      Out << NodePtr->Data << endl;
      NodePtr = NodePtr->Next;
    }

  Out.close();

  return 1;
}