// This file defines an extension to the List class that
// provides various operations that move items around in
// a list. This class is called "BuggyList", and provides
// the following to its clients:
//
//   o bringToFront, a message that takes an integer, i,
//       as its parameter, and returns a list that
//       contains the same items as the original, except
//       that the item that was in the i-th position is
//       now at the head of the list.
//     For stating pre- and postconditions, let the list
//       be x1, x2, ... xn. (So, i.e., n is the length of
//       the list)
//     Preconditions: 1 <= i <= n
//     Postconditions: The result is the list
//       xi, x1, x2, ... xi-1, xi+1, ... xn
//
//   o bubble, a parameterless message that returns a list
//       that contains the same items as the original, except
//       that the largest has moved to the end of the list
//       (i.e., it has floated up like a bubble).
//     Preconditions: The list contains at least one item. All
//       items in the list handle the "compareTo" message
//       (or, in more precise but obscure Java terminology,
//       all implement interface "Comparable").
//     Postconditions: The last item in the list is greater than
//       or equal to all others; the items in the list are the
//       same as before receiving the "bubble" message, although
//       possibly in different positions.
//
//   o isOrdered, a parameterless message that determines whether
//       the items in a list are in ascending order. This message
//       returns true if the items are in order, and false if they
//       aren't.
//     For stating pre- and postconditions, let the list
//       be x1, x2, ... xn. (So, i.e., n is the length of
//       the list)
//     Preconditions: n >= 1. All items in the list handle the
//       "compareTo" message (i.e., all items implement the "Comparable"
//       interface).
//     Postconditions: The result is true if and only if
//       x1 <= x2 <= x3 <= ... <= xn.
//
//
//   o A parameterless constructor, which initializes a
//       BuggyList to be empty.
//
//   o A constructor whose parameters are any object and a
//       BuggyList, and that initializes a new BuggyList with
//       the object as its first item and the list as its tail.
//
//   o A constructor whose only parameter is a regular list, and
//       that initializes a buggy list to contain the same items as
//       that regular list.
//
// BuggyLists also provide a "main" method that acts as a
// demonstrator or test driver for exploring what the lists do.
//
// Note that most of the methods in this class have bugs.
// Part of the reason for writing this class is to provide
// exercises in debugging or testing.

// History:
//
//   October 2003 -- Generated by Doug Baldwin from an original
//     that provided slightly different operations on buggy lists.
//
//   October 2002 -- Original created by Doug Baldwin.




import geneseo.cs.sc.List;




class BuggyList extends List {




    // The bringToFront method. This algorithm is based on the
    // following recursive insight: If i = 1, just return the
    // original list. If i > 1, bring item (i-1) of the list's tail
    // to the front of the tail, then create the result as a list
    // containing the first item of the rearranged tail, the first
    // item of the original list, and the tail of the rearranged tail,
    // in that order. (If the list itself is ever empty, i is out
    // of bounds and so just return an empty result.)

    public BuggyList bringToFront( int i ) {

        if ( this.isEmpty() ) {
            return new BuggyList();
        }
        else if ( i < 1 ) {
            return this;
        }
        else {
            BuggyList temp = ((BuggyList)this.rest()).bringToFront( i-1 );
            return new BuggyList( temp.first(),  new BuggyList( this.first(), (BuggyList)temp.rest() ) );
        }
    }




    // The bubble method. This method is based on the following
    // recursive insight: If the list only contains one element,
    // then the largest item is necessarily the last, so return the
    // list immediately. Otherwise, if the first item is greater than
    // the second, create a new list whose first item is the first
    // item of the original list and whose tail is the tail of the
    // tail of the original list; bubble this new list, and add the
    // original list's second item to the result. If the first item
    // is less than or equal to the second item, bubble the tail of
    // the list and add the original list's first item to the result.

    public BuggyList bubble() {

        if ( this.rest().isEmpty() ) {
            return this;
        }
        else {
            Comparable firstItem = (Comparable)this.first();
            Comparable secondItem = (Comparable)this.rest().first();
            if ( firstItem.compareTo( secondItem )  >  0) {
                BuggyList newList = new BuggyList( firstItem, (BuggyList)this.rest().rest() );
                return new BuggyList( secondItem, newList.bubble() );
            }
            else {
                return new BuggyList( secondItem, ((BuggyList)this.rest()).bubble() );
            }
        }
    }




    // The isOrdered method. This method is based on the recursive insight
    // that a list of 1 item is automatically in ascending order, and a list
    // of more than 1 item is in ascending order if the first item is less than
    // or equal to the second, and the tail of the list is in ascending
    // order.

    public boolean isOrdered() {

        if ( this.rest().isEmpty() ) {
            return true;
        }
        else {
            Comparable firstItem = (Comparable)this.first();
            Comparable secondItem = (Comparable)this.rest().first();
            if ( firstItem.compareTo(secondItem) <= 0 ) {
                return ((BuggyList)this.rest().rest()).isOrdered();
            }
            else {
                return false;
            }
        }
    }




    // The constructor that makes an empty BuggyList. This just
    // needs to make the underlying ordinary list empty.

    public BuggyList() {
        super();
    }




    // The constructor that makes a nonempty BuggyList. This just
    // needs to initialize the underlying list object with the given
    // head and tail.

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




    // The copying constructor. This is based on the recursive insight
    // that a copy of an empty regular list is an empty buggy list, while
    // a copy of a non-empty list is a buggy list whose first element is
    // the same as the first element of the buggy list, and whose tail
    // is a buggy list made by copying the tail of the regular list.

    public BuggyList( List source ) {

        super();			// Start the buggy list off being empty

        if ( ! source.isEmpty() ) {	// If it shouldn't be empty, fix it
            this.setFirst( source.first() );
            this.setRest(  new BuggyList( source.rest() )  );
        }
    }




    // main. This creates a BuggyList from items in a file, then uses
    // it to exercise the "bubble" and "bringToFront" algorithms.

    public static void main( String[] args ) {


        // Read a regular list from a file, and make a BuggyList from it. To
        // work with another list, just change the parameter to the "restore"
        // message:

        List listFromFile = new List();
        listFromFile.restore( "InstrumentList" );

        BuggyList bugs = new BuggyList( listFromFile );

        System.out.println( "The buggy list = " + bugs );


        // Show off the "bringToFront" message:

        final int place = 2;
        
        BuggyList broughtToFront = bugs.bringToFront( place );
        System.out.println( "Bringing item " + place + " to the front yields " + broughtToFront );


        // Show off the "bubble" message:

        BuggyList bubbled = bugs.bubble();
        System.out.println( "Bubbling yields " + bubbled );


        // Show off the "isOrdered" message:

        System.out.println( "The buggy list is in order..." );
        System.out.println( "\t" + bugs.isOrdered() );

        System.out.println( "The bubbled buggy list is in order: " + bugs.bubble().isOrdered() );
    }

}