// A simple extension to the Science of Computing List class. The extended
// lists can compute their lengths and extract every other item from themselves,
// as well as initializing themselves from a regular list. This class also
// contains a main method that exercises the extended lists.

// History:
//   October 2003 -- Created by Doug Baldwin.


import geneseo.cs.sc.List;


class ExtendedList extends List {




    // Initialize an extended list to be empty.

    public ExtendedList() {
        super();
    }




    // Initialize an extended list to contain a given first item and tail.

    public ExtendedList( Object head, ExtendedList tail ) {
        super( head, tail );
    }




    // Initialize an extended list by copying a regular list into it. This is based
    // on the recursive insight that copying an empty list just produces an empty
    // extended list, whereas copying a non-empty list produces an extended list whose
    // head is the same as the head of the original list, and whose tail is an extended
    // list made from the tail of the source list. Note that because of Java restrictions
    // on where a superclass's constructor can be called (only as the first action a
    // subclass's constructor takes), I have to implement this insight by initializing
    // the new ExtendedList to be empty at the very beginning of this method, then
    // letting it stay empty if the source list is empty, or replacing its head and
    // tail if the source list is not empty.

    // Correctness proof: Prove that after this constructor executes, the new
    // list contains the same items, in the same order, as "source". The proof is
    // by induction on the length of "source" (n).
    //   For a base case, assume n = 0 (i.e., "source" is empty). Then the call to
    // the superclass's constructor makes the new list empty, and nothing else
    // happens because the "! source.isEmpty()" test fails. Thus at the end,
    // the new list contains the same items (none), in the same order, as "source".
    //   For the induction hypothesis, assume that when "source" is any list of k-1 items,
    // where k-1 is a natural number, this constructor initializes the new list
    // to contain the same items, in the same order, as "source".
    //   Show that when "source"" is any list of k items, this constructor initializes
    // the new list to contain the same items, in the same order, as "source". The
    // initial "super" call initializes the new list to be empty. But then the
    // "! source.isEmpty()" test succeeds, and the constructor makes the head of
    // the new list equal to the head of "source", and makes the tail equal to a
    // new list made from the tail of "source". By the induction hypothesis, and
    // the fact that the tail of "source" contains k-1 items, this new tail contains
    // the same items, in the same order, as the tail of "source". Between its head
    // and tail, the new list contains all the items from "source". Further, since
    // "source's" head is the head of the new list, and so comes before the
    // items copied from "source's" tail, and those items are themselves in the
    // same order as they were in "source", the items in the new list are in the
    // same order as in "source".

    // Derivation of number of primitive List messages: The number of primitive
    // list messages is given as a function, p, of the length of "source" (n).
    // In the base case (n = 0), this constructor calls the primitive List constructor,
    // and then sends one "isEmpty" message. Thus
    //     p(n) = 2 if n = 0
    // In the recursive case (n > 0), the constructor calls the primitive List
    // constructor, sends "isEmpty", "setFirst", "first", "setRest", and "rest"
    // messages, plus invoking itself recursively. Thus
    //     p(n) = 6 + p(n-1) if n > 0
    // Looking for a pattern in the values of p(n) yields
    //     n:     p(n):
    //     0       2
    //     1       6 + p(0) = 6 + 2
    //     2       6 + p(1) = 6 + 6 + 2
    // It looks as if p(n) = 6n + 2. Prove this by induction on n:
    //   The base case is n=0. p(0) = 2 = 6*0 + 2.
    //   Assume that for some natural number k-1, p(k-1) = 6(k-1) + 2.
    //   Show that p(k) = 6k + 2
    //     p(k) = 6 + p(k-1), from the definition of p
    //       = 6 + 6(k-1) + 2, by the induction hypothesis
    //       = 6 + 6k - 6 + 2, distributing the 6 into (k-1)
    //       = 6k + 2, cancelling 6 and -6.

    public ExtendedList( List source ) {
        
        super();		// Start with the new list empty

        if ( ! source.isEmpty() ) {
            this.setFirst( source.first() );
            this.setRest(  new ExtendedList( source.rest() )  );
        }
    }




    // Count the number of items in an extended list. The algorithm is based on
    // the recursive insight that the length of an empty list is 0, and the
    // length of a non-empty list is one more than the length of its tail.

    // Correctness proof: Prove that when sent to a list of n items, "length"
    // returns n. The proof is by induction on n.
    //   For the base case, consider n = 0. The list is empty, so the
    // "this.isEmpty" test succeeds, and "length" returns 0, which is indeed
    // the length of an empty list.
    //   For the induction hypothesis, assume that when sent to any list of
    // k-1 items (where k-1 is a natural number), "length" returns k-1.
    //   Show that when sent to a list of k items, "length" returns k. The
    // k-item list is not empty, so the "this.isEmpty" test fails and "length"
    // returns 1 plus the result of sending a "length" message to the tail of
    // the list. Since the tail of the list contains k-1 items, this recursive
    // "length" message returns k-1. Adding 1 yields k, as desired.

    // Derivation of number of primitive List messages. I give the number
    // of primitive List messages as a function, p, of the length of the
    //list (n).
    //   When the list is empty, "length" only sends one primitive message,
    // "isEmpty". So
    //     p(n) = 1 if n = 0
    // When the list isn't empty (n > 0 ), "length" sends 2 primitive messages
    // directly ("isEmpty" and "rest"), plus however many the recursive message
    // to an (n-1)-item list sends. Thus
    //     p(n) = 2 + p(n-1) if n > 0
    // Looking for a pattern in the values for p(n) yields
    //     n:      p(n):
    //     0        1
    //     1        2 + p(0) = 2 + 1
    //     2        2 + p(1) = 2 + 2 + 1
    // It looks like the pattern is p(n) = 2n + 1. Prove this by induction
    // on n.
    //   For the base case, consider n = 0. p(0) = 1 = 2*0 + 1
    //   Assume that for some natural number k-1, p(k-1) = 2(k-1) + 1
    //   Show p(k) = 2k + 1
    //     p(k) = 2 + p(k-1), by the definition of p
    //       = 2 + 2(k-1) + 1, by the induction hypothesis
    //       = 2 + 2k - 2 + 1, distributing the 2 into (k-1)
    //       = 2k + 1, cancelling 2 and -2.

    public int length() {
        
        if ( this.isEmpty() ) {
            return 0;
        }
        else {
            return 1 + ((ExtendedList)this.rest()).length();
        }
    }




    // Copy every other item in an extended list into a new extended list. Copying
    // starts with the first item, skips the second, copies the third, etc. The
    // algorithm is based on the recursive insight that copying an empty list yields
    // another empty list, while copying a non-empty list yields a list whose head
    // is the same as the head of the source list, and whose tail is a copy of every
    // other item in the tail of the tail of the source list. Note, however, that I
    // have to be careful not to try to take the tail of the tail of a list with only
    // one element.

    // Correctness proof: Prove that "everyOtherItem" sent to a list
    // [x1, x2, x3, x4, ..., xn] returns the list [x1, x3, ...]. The proof is by
    // induction on n, the length of the original list.
    //   The proof has two base cases, corresponding to the base cases in the algorithm.
    // For the first base case, assume n = 0, so that the result should be an empty list.
    // The "this.isEmpty" test succeeds, and so "everyOtherItem" indeed returns an
    // empty list. For the second base case, suppose n = 1, i.e., the original list
    // is just [x1]. The "this.isEmpty" test fails, but the "this.rest().isEmpty" test
    // succeeds and so "everyOtherItem" returns a list containing the first item of
    // the original (x1), and nothing else. In other words, the result is [x1], as it
    // should be.
    //   For the induction hypothesis, assume that "everyOtherItem" sent to a list
    // of k-2 items, [x1, x2, x3, x4, ..., x(k-2)] returns a list containing
    // [x1, x3, ...]. Assume that k-2 is a natural number.
    //   Show that "everyOtherItem" sent to a list of k items, [x1, x2, x3, x4, ..., xk]
    // returns a list containing [x1, x3, ...]. Since k-2 is a natural number, this list
    // contains at least 2 items. Thus the "this.isEmpty" and "this.rest().isEmpty" tests
    // both fail, and so "everyOtherItem" returns a new list containing the first item
    // of the list (x1), followed by the result of sending an "everyOtherItem" message
    // to the tail of the tail of the list. Since the tail of the tail of a k-item list
    // contains k-2 items, the induction hypothesis tells us that this message returns
    // a list of the form [x3, x5, ...]. Placing x1 in front of this list yields
    // [x1, x3, ...], as desired.

    // Derivation of number of primitive List messages. I give the number of primitive
    // List messages as a function, p, of the list's length, n.
    //   If n = 0, the "this.isEmpty" test succeeds and so "everyOtherItem" creates
    // a new, empty, extended list to return. Testing for emptiness and making the
    // new list involves 2 primitives. Thus
    //     p(n) = 2 if n = 0.
    //   If n = 1, the "this.isEmpty" test fails, but "this.rest().isEmpty" succeeds.
    // The algorithm makes a new extended list from "this.first()" and a new, empty,
    // extended list. The total number of primitives required to do this is
    //     p(n) = 6 if n = 1
    //   Finally, if n > 1, "everyOtherItem" falls through to the last arm of its
    // conditional, and returns a new list made from "this.first()" and the result
    // of applying "everyOtherItem" to "this.rest().rest()". The total number of
    // primitive List messages and constructor invocations is then 7 plus however
    // many the recursive message causes. In other words
    //     p(n) = 7 + p(n-2) if n > 1
    // Note the "p(n-2)", reflecting the fact that the recursively processed list
    // is 2 items shorter than the original.
    //   The recurrence relation for p(n) has slightly different closed forms depending
    // on whether n is odd or even. I thus give separate closed forms for each case.
    //   For even n: Looking at values of p(n) when n is even yields
    //     n:       p(n):
    //     0         2
    //     2         7 + p(0) = 7 + 2
    //     4         7 + p(2) = 7 + 7 + 2
    //     6         7 + p(4) = 7 + 7 + 7 + 2
    // Each sum seems to contain n/2 7's, plus a 2. Thus I guess that the closed
    // form is p(n) = 7(n/2) + 2. I can prove this by induction on n:
    //   For a base case, consider n = 0. p(0) = 2 = 7*0 + 2 = 7(0/2) + 2.
    //   Now assume that for some natural number k-2, p(k-2) = 7( (k-2)/2 ) + 2.
    //   Show that p(k) = 7(k/2) + 2.
    //     p(k) = 7 + p(k-2), from the recurrence relation
    //       = 7 + 7( (k-2)/2 ) + 2, by the induction hypothesis
    //       = 7 + 7( k/2 - 1 ) + 2, dividing (k-2) by 2
    //       = 7 + 7k/2 - 7 + 2, distributing the 7 into (k/2 - 1)
    //       = 7(k/2) + 2, cancelling 7 and -7.
    //   For odd n, looking at values of p(n) yields
    //     n:       p(n):
    //     1         6
    //     3         7 + p(1) = 7 + 6
    //     5         7 + p(3) = 7 + 7 + 6
    //     7         7 + p(5) = 7 + 7 + 7 + 6
    // Here it looks like there are (n-1)/2 7's, i.e., p(n) = 7(n-1)/2 + 6.
    // Prove this by induction on n.
    //   For the base case, consider n = 1. p(1) = 6 = 7 * 0 + 6
    // = 7 * (1-1)/2 + 6.
    //   Assume that for some natural number k-2, p(k-2) = 7( (k-2)-1 )/2 + 6
    //   Show that p(k) = 7(k-1)/2 + 6.
    //     p(k) = 7 + p(k-2), from the recurrence relation
    //       = 7 + 7( (k-2) - 1 )/2 + 6, by the induction hypothesis
    //       = 7 + 7( (k-1) - 2 )/2 + 6, rewriting (k-2)-1 as (k-1)-2
    //       = 7 + 7( (k-1)/2 - 1) + 6, distributing division by 2 into (k-1)-2
    //       = 7 + 7(k-1)/2 - 7 + 6, distributing 7 into (k-1)/2 - 1
    //       = 7(k-1)/2 + 6, cancelling 7 and -7.

    public ExtendedList everyOtherItem() {

        if ( this.isEmpty() ) {
            return new ExtendedList();
        }
        else if ( this.rest().isEmpty() ) {
            return new ExtendedList( this.first(), new ExtendedList() );
        }
        else {
            return new ExtendedList( this.first(),
                                     ((ExtendedList)this.rest().rest()).everyOtherItem() );
        }
    }




    // Exercise extended lists and show what they do.
        
    public static void main( String args[] ) {


        // Load a list from a file, and then create an extended list from it:

        final String fileName = "AnimalList";

        List rawList = new List();
        rawList.restore( fileName );

        ExtendedList demoList = new ExtendedList( rawList );

        System.out.println( "The extended list: " + demoList );
        System.out.println( "\tSize = " + demoList.length() );


        // Copy every other element from the demo list into a new extended
        // list:

        ExtendedList halfList = demoList.everyOtherItem();

        System.out.println( "Every other item: " + halfList );
        System.out.println( "\tSize = " + halfList.length() );
    }
}