//**************************************************
// COMP102
// Simplified Linked List for Undirected Graphs
// for use in SparseGraph Class.
//**************************************************
// Note: Additonal Class Methods provided:
//    
//    public static boolean IsMember (int v, EdgeList E)
//       returns true if v is the Node value of
//       some ListCell in E;
//
//    public static EdgeList DeleteCell (int v, EdgeList E)
//       returns the EdgeList resulting by removing
//       the ListCell with Node value v from E.
//       
//
// Paul E. Dunne 18/1/00
//
//**************************************************
public class EdgeList
  {
  //*****************
  // ListCell Class *
  //*****************
  private class ListCell
  {
  private int Node;   // NB int not Object
  private ListCell Link;
  //
  private ListCell(int node_val, ListCell next_cell)
    {
    Node = node_val; Link=next_cell; 
    }
  }
  //*************
  // List Fields*
  //*************
  private ListCell Head;         
  private ListCell Tail;         
  private int Count;       
  //***********************
  // EdgeList Constructor *
  //***********************
  public EdgeList()
    {
    Head = null;
    Tail = null;      
    Count=0; // Initiates the empty list.
    }
  //*******************
  // Instance Methods *
  //*******************
  //
  //  Test if this instance is the Empty list.
  //
  public boolean IsEmpty()
    {
    return (Count==0);
    };
  //
  //**********************
  //  Add a new ListCell *
  //**********************
  //
  public void AddHead ( int Node )
    {
    if (IsEmpty())               // If it's currently empty;
      {
      Head = new ListCell(Node,Head);   // Create the new Head.
      Tail = null;                       // The link is still `null'
      Count=1;                       // and this list now contains 1 cell.
      }
    else                                 // If it's not empty
      {
      Head = new ListCell(Node,Head);   // Add the new List Node,
      Tail = Head.Link;                  // Reset the `Tail' of the list.
      Count++;                       // and this list now has 1 extra cell.
      };
    }
  //
  //****************************************************
  //  Remove the ListCell at the start of this EdgeList*
  //****************************************************
  //
  public void RemoveHead()
    {
    if (Count<=1)                // There is an argument for raising
      {                          // an exception if Count=0
                                 // however, we adopt the convention
                                 // that RemoveHead() applied to
                                 // the empty list leaves the empty list.
      Head = null; 
      Count=0;
      }
    else
      {
      Head = Tail;               // Tail is never the null reference here.
      Count--;                   // and this list has one fewer cell.
      if (Count==1)
        Tail=null;               // If there's only a single cell then its Link field
                                 // must point to the empty list (i.e. null reference)
      else
        Tail = Head.Link;        // Otherwise we can update Tail without any problem.
      };
    }
  //
  //********************************************************
  //  Obtain the int in the Node field of the ListCell at  *
  //  the start of this EdgeList.                          *
  //  This method will not change the current instantiation*
  //********************************************************
  //
  public int GetHead()
    {
    if (Count!=0)            // If there's anything to return
      return Head.Node;      // then return it.
    else
      return -1;             // otherwise return -1.
    }
  //
  //*******************************************************************
  //  Obtain the (reference) to the EdgeList for the Link field of the*
  //  ListCell at the start of this instance.                         *
  //  This method will not change the current instantiation.          *
  //*******************************************************************
  //
  public EdgeList GetTail()
    {
    EdgeList temporary= new EdgeList();
    temporary.Head=Head; temporary.Tail=Tail;
    temporary.Count = Count;
    temporary.RemoveHead();
    return temporary;
    } 
  //
  //**********************************************************
  //  Convert this EdgeList into a String in which each      *
  // Node of the component ListCells is separated by a space *
  //**********************************************************
  //
  public String toString()
    {
    String res = new String();
    EdgeList temporary = new EdgeList();
    temporary.Head = Head; 
    temporary.Tail = Tail; 
    temporary.Count=Count;
    while (!temporary.IsEmpty())
      {
      res = res+temporary.GetHead()+"  ";
      temporary = temporary.GetTail();
      };
    return res;
    }     
  //*********************************************************//
  //  The Class Methods below are discussed (in connection   //
  // with Linked Lists) in later lectures.                   //
  //*********************************************************//
  //
  //*****************************************
  // Test if Node with value v occurs in E  *
  //*****************************************
  public static boolean IsMember (int v, EdgeList E)
    {
    EdgeList temp = E;
    if (temp.IsEmpty())
      return false;
    else if (v==temp.GetHead())
      return true;
    else
      return IsMember(v,temp.GetTail());
    } 
  //****************************************************
  // Return the EdgeList resulting by removing a cell  *
  // with Node value v from E.                         *
  // Note: Thismethod changes the order of cells in    *
  // the result when compared with E.                  *
  //****************************************************
  public static EdgeList DeleteCell (int v, EdgeList E)
    {
    EdgeList temp=E;
    EdgeList Save =  new EdgeList();
    if (!IsMember(v,temp))
      return temp;          // Nothing to do.
    else
      while (v!=temp.GetHead())
        {
        Save.AddHead(temp.GetHead());
        temp = temp.GetTail();
        };
      temp = temp.GetTail();        // Remove the cell holding v.
      while (!temp.IsEmpty())       // join the remainder to Save.
        {
        Save.AddHead(temp.GetHead());
        temp = temp.GetTail();
        };
      return Save;
    }
  }