///////     File :  ArbList.java    ///////
//  generic linked list objects

public class ArbList
{ 
    public ArbList() { }            // empty list constructor 
    public ArbList(Object it)  // list with first cell
    { head=new ArbCell(it,null); }
    public ArbCell first() { return head; } // first cell
    public ArbCell last() // last cell
    {     ArbCell p = head;
          while( p != null && p.next != null )
                 p =  p.next; 
          return(p);
    }
    public ArbCell find(Object it) // first item equals it
    {   for( ArbCell p = head; p!=null ; p = p.next )
           if( p.item.equals(it) ) // overriding equals
               return(p);
        return(null);  // c not on list
    }
    public boolean substitute(Object r, Object s) // r for first s on list
    {     ArbCell p = find(s);
          if( p == null ) return(false);     // s not on list
          p.item = r;
          return(true);
    }
    public int remove(Object it) // it from entire list
    {     ArbCell p = head;
          int count = 0;
          if ( p == null ) return(count);
          while (p.next != null)      // treat all but head cell
          {  if ((p.next).item.equals(it) )
             {   count++;
                 p.next = (p.next).next;
             }
             else
                    p = p.next;
          }
          if( head.item.equals(it) ) // treat head cell
          {  head = head.next;
             count++;
          }
          return(count);       // number of items removed
    }
    public int shorten(int n) // remove first n cells
    {    while (n-- > 0 && head != null)
             head = head.next;
         return(n);
    }
    public void putOn(Object it) // insert in front
    {  head = new ArbCell(it,head);
    }
    
    public void insert(Object it, ArbCell e) // insert after cell
    {  e.next = new ArbCell(it,e.next);
    }

    public void append(Object it)  // insert at end
    {   insert(it, last()); }

    public boolean isEmpty() { return(head == null); }

    public String toString()
    {   return toString(head);  }

    public String toString(ArbCell p)
    {   String s = "(";
        while ( p != null )
        {    s = s + p.item;
             if ( (p = p.next) != null ) s = s + " ";
        }
        return( s + ")");
    }
    private ArbCell head = null;           // first cell of list
}

class ArbCell
{  
    ArbCell(Object it, ArbCell cell)
    { item=it; next=cell; }
    ArbCell() { }
    Object content()
    { return(item); }

    Object item = null;
    ArbCell next = null;
}

class TestArbList
{   
    static Fraction[] fra = 
    { new Fraction(1,2), new Fraction(3,4),
      new Fraction(1,3), new Fraction(3,5),
      new Fraction(1,4), new Fraction(3,7),
      new Fraction(1,5), new Fraction(3,8), new Fraction(3,5) };

    public static void main(String[] args)
    {    ArbList a = new ArbList(fra[0]);
         a.putOn(fra[1]);
         a.append(fra[2]); a.append(fra[3]); a.append(fra[4]);
         System.out.println("a = " + a);
         ArbCell lp = a.find(fra[8]);
         if ( lp != null ) 
         {    System.out.println(a.toString(lp));
              a.insert(fra[6], lp);
         }
         System.out.println("a = " + a);
         a.remove(fra[4]);
         a.shorten(2);
         System.out.println("a = " + a);
         a.remove(fra[6]);
         System.out.println("a = " + a);
    }

}


/* output
a = (3/4 1/2 1/3 3/5 1/4)
(3/5 1/4)
a = (3/4 1/2 1/3 3/5 1/5 1/4)
a = (1/3 3/5 1/5)
a = (1/3 3/5)
*/