CSC 17 Lab 2

Download my LinkedList.java implementation from the class homepage.  Make
sure the programs you write are in the same directory.

You are going to add a few more operations to the LinkedList class.  However,
instead of editing the existing code, you're going to use inheritance: that
is, you are going to write a class that EXTENDS my LinkedList class.  Start
with the following skeleton:

public class CList<T extends Comparable<T>> extends LinkedList<T>
{
    public CList() { super(); } // subclass constructor

    // sample method to insert a value in sorted order
    public void orderInsert(T x)
    {
	size++;
	if (size==1) {first=last = new node(x); return; }
	if (x.compareTo(first.item)<=0) // push in front
	    { first = new node(x,first); return; }
	node current = first;
	// find node before insertion point:
	while (current!=last && x.compareTo(current.next.item)>=0) 
	    current=current.next;
	current.next = new node(x,current.next);
	if (current==last) last = current.next;
    }

// ... add other methods here

}//CList - Linked List of comparable elements.

Extending a class essentially imports code already written.  Moreover, an
instance of CList is still a LinkedList.  All non-private components of
the superclass are still visible in the subclass - there is no need to
re-declare them.  This is why I prefer "protected" to "private".  Private
components of the superclass are not visible in the subclass (they still
exist, but are hidden).  There is no need at all to rewrite operations
such as push/pop, etc because they're inherited.  We can override a
method by redefining it in the subclass but in this assignment there's no
need to do so.  Instead, we're going to add some new methods in the subclass.

Another important difference between this subclass and the superclass is that
the generic type variable T can only be instantiated by "comparable" values,
that is, values such as numbers that can be ordered (sorted).  From Lab1b you
already saw how two strings s and t can be compared using s.compareTo(b),
which returns 0 if s and t are "equal", a negative integer if s is "less" than
t and a positive value if s is "greater" than t.  This is because the string
class implements a built-in interface:

interface Comparable<T>   // part of Java API (don't redefine)
{
   int compareTo(T x);
}

class String implements Comparable<String>
...

We want to be able to write, for example, a procedure that finds the
"smallest" value in the list, but what does "smallest" mean?  That is
defined by the compareTo implementation of each class: it means different
things for different types.  For example, for your "team" class from lab1b,
if "smallest" means having the lowest winning percentage, you should define
your class as follows:

class team implements Playable, Comparable<team>
{
   public int compareTo(team B) 
   {
       double a = this.winningPercentage();
       double b = B.winningPercentage();
       if (a<b) return -1;  // return negative value if this less than B
       else if (a==b) return 0;  // return 0 if equals
       else return 1;  // return positive value if greater than
   }
   // ...
}

To implement the interface means to provide one possible algorithm for
the compareTo function.  Other classes will have other algorithms for
determing which instance is "smaller".  Once you've created such a
class, you can now create a CList of team objects: new CList<team>,
and all methods you write for CList (and for LinkedList) can be called
on such a list.
----
Besure to put the public class in a file CList.java.

Add to the CList class the following methods:

0. main to demonstrate each of the following methods...

1. public int count(T x)  // returns the number of times x is found as an 
item in the list.  Use a.equals(b) to compare if two objects are "equal"
(note: a.equals(b) returns a boolean, a.compareTo(b) returns an int, and
 a.compareTo(b)==0 does not necessarily mean the same as a.equals(b))

2. public void cut() : // this function should  do the following:    ****

   hint: this is one of the harder problems because it requires 
   deleting from the list.

  say your list contains items 2,4,1,4,2,7,2,3,8 calling cut() will
  change this list to 2 3 8.  That is , you want to cut out all the
  elements between first.item and the *last* occurrence of the same
  number in the list.  If the first.item is not repeated, then the
  function should have no effect.  This function is not implemented in
  the ArrayList class of java, but we will need it in one of our labs.

3. public CList<T> clone()  : // this should return a full clone (copy)
of the list being invoked on.  Changing the clone would not change the
original.  You have to clone not just first, last and size, but
also recreate every node in the list.

4. public CList<T> weakclone() : // this should return another
instance of the list with the same size and elements, but without
duplicating cells (first/last can point to existing cells).  This will
give us better efficiency in certain situations.  For example, a list
containing 1 4 5 6 and another one containing 2 4 5 6 can share the
same "tail": (4 5 6).  This kind of structure is not possible using
Java's built-in classes, which is why sometimes we need to use our own
linked lists.  Of course, you will have to be aware that adding to the
end of one list will also change the other list (but not adding to the
front. Why?)  This function is also not available in ArrayList, and again
illustrates why you may have to define your own lists.

5. Write a function to reverse a list.  This can be done in one of two
(or both) ways:

5a. constructively: do not change the original list; create a new list instead.

public CList<T> reverse()

A harder problem is to reverse the list in place - that is, "destructively",
by reversing the direction of each next pointer.  first and last would also
need to be swapped.  This problem is considered a challenge.

public void reverse()


6.  Write a function to find the smallest item in the list, as 
determined by the compareTo function of type T.  If the list is empty, 
you can either throw a RuntimeException, or return null.

public T min()

7. Use the orderInsert method to devise a sorting algorithm for CList linked
lists.  It's easier to write this constructively (create a new, sorted list
without changing the original list).

public CList<T> sort()