January 21st, 2014

Maze solver by Robert von der Schmidt

Inheritance

An example:

A UML class diagram showing an inheritance relationship

public class Words
{
   //-----------------------------------------------------------------
   //  Instantiates a derived class and invokes its inherited and
   //  local methods.
   //-----------------------------------------------------------------
   public static void main (String[] args)
   {
      Dictionary webster = new Dictionary();

      System.out.println ("Number of pages: " + webster.getPages());

      System.out.println ("Number of definitions: " +
                          webster.getDefinitions());

      System.out.println ("Definitions per page: " +
                          webster.computeRatio());
   }
}

public class Book
{
   protected int pages = 1500;

   //----------------------------------------------------------------
   //  Pages mutator.
   //----------------------------------------------------------------
   public void setPages (int numPages)
   {
      pages = numPages;
   }

   //----------------------------------------------------------------
   //  Pages accessor.
   //----------------------------------------------------------------
   public int getPages ()
   {
      return pages;
   }
}

public class Dictionary extends Book
{
   private int definitions = 52500;

   //-----------------------------------------------------------------
   //  Prints a message using both local and inherited values.
   //-----------------------------------------------------------------
   public double computeRatio ()
   {
      return (double) definitions/pages;
   }

   //----------------------------------------------------------------
   //  Definitions mutator.
   //----------------------------------------------------------------
   public void setDefinitions (int numDefinitions)
   {
      definitions = numDefinitions;
   }

   //----------------------------------------------------------------
   //  Definitions accessor.
   //----------------------------------------------------------------
   public int getDefinitions ()
   {
      return definitions;
   }
}

Inheritance Notes

• Inheritance is the process of deriving a new class from an existing one.
• One purpose of inheritance is to reuse existing software.
• The original class is called the parent class, superclass, or base class.
• Inheritance creates an “is-a” relationship between the parent and child classes.
• Java uses the reserved word extends to indicate that a new class is being derived from an existing class.
• Inheritance is a one-way street.

Visibility Modifiers

• Private methods and variables of the parent class cannot be referenced in the child class or through an object of the child class.
• Public visibility allows a derived class to reference it, but violates the principle of encapsulation.
• Protected visibility allows the class to retain some encapsulation properties.
• Protected visibility provides the best possible encapsulation that permits inheritance. However, the encapsulation is not as tight as if the variable or method were declared private, but it is better than if it were declared public.
• Modifiers list:
• public – visible anywhere
• protected – can only be applied to inner classes. Visible to any classes in the package and to children classes.
• private – can only be applied to inner classes. Visible enclosing class only.
• no modifier – default – visible to any classes in the same package.
• For the AP Computer Science A Exam a design question may required a student to develop a solution that includes all data declared private.

The Super keyword

• The reserved word super can be used in a class to refer to its parent class.
• Using the super reference, we can access a parent’s members.
• Like the this reference, what the word super refers to depends on the class in which it is used.
• A parent’s constructor can be invoked using the super reference. ( First line in the constructor )
• If no such call exists, Java will automatically make a call to super() at the beginning of the constructor.
• The super reference can also be used to reference other variables and meth- ods defined in the parent’s class.

public class Words2
{
   //-----------------------------------------------------------------
   //  Instantiates a derived class and invokes its inherited and
   //  local methods.
   //-----------------------------------------------------------------
   public static void main (String[] args)
   {
      Dictionary2 webster = new Dictionary2 (1500, 52500);

      System.out.println ("Number of pages: " + webster.getPages());

      System.out.println ("Number of definitions: " +
                          webster.getDefinitions());

      System.out.println ("Definitions per page: " +
                          webster.computeRatio());
   }
}

public class Book2
{
   protected int pages;

   //----------------------------------------------------------------
   //  Constructor: Sets up the book with the specified number of
   //  pages.
   //----------------------------------------------------------------
   public Book2 (int numPages)
   {
      pages = numPages;
   }

   //----------------------------------------------------------------
   //  Pages mutator.
   //----------------------------------------------------------------
   public void setPages (int numPages)
   {
      pages = numPages;
   }

   //----------------------------------------------------------------
   //  Pages accessor.
   //----------------------------------------------------------------
   public int getPages ()
   {
      return pages;
   }
}

public class Dictionary2 extends Book2
{
   private int definitions;

   //-----------------------------------------------------------------
   //  Constructor: Sets up the dictionary with the specified number
   //  of pages and definitions.
   //-----------------------------------------------------------------
   public Dictionary2 (int numPages, int numDefinitions)
   {
      super(numPages);

      definitions = numDefinitions;
   }

   //-----------------------------------------------------------------
   //  Prints a message using both local and inherited values.
   //-----------------------------------------------------------------
   public double computeRatio ()
   {
      return (double) definitions/pages;
   }

   //----------------------------------------------------------------
   //  Definitions mutator.
   //----------------------------------------------------------------
   public void setDefinitions (int numDefinitions)
   {
      definitions = numDefinitions;
   }

   //----------------------------------------------------------------
   //  Definitions accessor.
   //----------------------------------------------------------------
   public int getDefinitions ()
   {
      return definitions;
   }
}

Overriding Notes

• A child class can override (redefine) the parent’s definition of an inherited 
method.
• Constructors, however, are not inherited and cannot be overridden.
• Method overriding is a key element in object-oriented design.
• Method overriding allows two objects that are related by inheritance to use the same naming conventions for methods that accomplish the same general task in different ways.
• A method can be defined with the final modifier. A child class cannot override a final method. This technique is used to ensure that a derived class uses a particular definition of a method.
• The final modifier can also be applied to an entire class. A final class cannot be extended at all.

Shadowing

• If a variable of the same name is declared in a child class, it is called a shadow variable.
• To avoid confusion and logical errors, shadowing variables should be avoided.

Class Hierarchy

A UML class diagram showing a class hierarchy

• The child of one class can be the parent of one or more other classes, creating a class hierarchy.
• Common features should be located as high in a class hierarchy as is reasonably possible.
• All Java classes are derived, directly or indirectly, from the Object class.
• The toString and equals methods are inherited by every class in every 
Java program.
• Inheritance can be applied to interfaces so that one interface can be derived from another.
• Private members are inherited by the child class, but cannot be referenced directly by name. They may be used indirectly, however.
• Java’s approach to inheritance is called single inheritance.

Abstract Classes

• It represents a concept on which other classes can build their definitions.An abstract class cannot be instantiated.
• A class derived from an abstract parent must override all of its parent’s abstract methods, or the derived class will also be considered abstract.
• An abstract class is similar to an interface in some ways.
• However, unlike interfaces, an abstract class can contain methods that are not abstract.
• An abstract class can also contain data declarations other than constants.
• A class is declared as abstract by including the abstract modifier in the class header.
• Any class that contains one or more abstract methods must be declared as abstract.
• In abstract classes (unlike interfaces), the abstract modifier must be applied to each abstract method.
• A class declared as abstract does not have to contain abstract methods.
• Abstract classes serve as placeholders in a class hierarchy.
• If a child of an abstract class does not give a definition for every abstract method that it inherits from its parent, then the child class is also considered abstract.
• Note that it would be a contradiction for an abstract method to be modified as final or static.
• Because abstract methods have no implementation, an abstract static method would make no sense.

Interface Hierarchies

• The concept of inheritance can be applied to interfaces as well as classes.
• One interface can be derived from another interface.
• These relationships can form an interface hierarchy, which is similar to a class hierarchy.
• When a parent interface is used to derive a child interface, the child inherits all abstract methods and constants of the parent.
• Any class that implements the child interface must implement all of the methods.
• There are no visibility issues when dealing with inheritance between interfaces (as there are with protected and private members of a class), because all members of an interface are public.
• Class hierarchies and interface hierarchies do not overlap. That is, an interface cannot be used to derive a class, and a class cannot be used to derive an interface.

Designing for inheritance
▪ Every derivation should be an is-a relationship. The child should be a more specific version of the parent.
▪ Design a class hierarchy to capitalize on reuse, and potential reuse in the future.
▪ As classes and objects are identified in the problem domain, find their commonality. Push common features as high in the class hierarchy as appropriate for consistency and ease of maintenance.
▪ Override methods as appropriate to tailor or change the functionality of a child.
▪ Add new variables to the child class as needed, but don’t shadow (redefine) any inherited variables.
▪ Allow each class to manage its own data. Therefore use the super reference to invoke a parent’s constructor and to call overridden versions of methods if appropriate.
▪ Use interfaces to create a class that serves multiple roles (simulating multiple inheritance).
▪ Design a class hierarchy to fit the needs of the application, with attention to how it may be useful in the future.
▪ Even if there are no current uses for them, override general methods such as toString and equals appropriately in child classes so that the inherited versions don’t cause unintentional problems later.
▪ Use abstract classes to specify a common class interface for the concrete classes lower in the hierarchy.
▪ Choosing which classes and methods to make abstract is an important part of the design process. You should make such choices only after careful consideration. By using abstract classes wisely, you can create flexible, extensible software designs.
▪ Use visibility modifiers carefully to provide the needed access in derived classes without violating encapsulation.
▪ Using the final modifier to restrict inheritance abilities is a key design decision.

Homework:
Visit edmodo.com to write a paragraph about the recursive function algorithm used to solve the maze.

Recursion

Recursion

We say that a method is recursive when it calls itself.

A good analogy would be when we define a word with the word itself. Take a look at this example:

companion: A person who accompanies or associates with another; a comrade.

In algebra: composite function f(f(x))

A recursive program requires two parts:
1. The non-recursive part, the base case, which lets the recursion eventually end.
2. The recursive part: calling itself.

Indirect recursion: a method invokes another method, eventually resulting in the original method being invoked again.

    public int factorial(int num)
    {
        if ( num "less than or equal to" 1 ) return 1;
        else return (num * factorial(num-1));
    }

Happy New Year!!

Welcome back!

Classwork:

“Abstract Classes” already posted.

Students presentation/discussions about the following assignments:

1. Create a class DataSet of BankAccounts. The constructor creates an ArrayList. Write the test class to add, delete and print bank accounts.

2. Create a class Purse that contains an ArrayList of Coin(s). Write the test class to add, delete, and print coins.
Modify the Purse class to be implemented with ArrayList class and to use a for-each loop.
Implement the following methods in the Purse class:

/**
      Counts the number of coins in the purse
      @return the number of coins
   */
   public int count()
   {
     
   }

   /**
      Tests if the purse has a coin that matches
      a given coin.
      @param aCoin the coin to match
      @return true if there is a coin equal to aCoin
   */
   public boolean find(Coin aCoin)
   {

   }

   /**
      Counts the number of coins in the purse that match
      a given coin.
      @param aCoin the coin to match
      @return the number of coins equal to aCoin
   */
   public int count(Coin aCoin)
   {

   }

   /**
      Finds the coin with the largest value. 
      (Precondition: The purse is not empty)
      @return a coin with maximum value in this purse
   */
   Coin getMaximum()
   {

   }

Homework:
Self-review questions 7.1 through 7.8
1 Question on edmodo.com

Inheritance
Method behavior

Base and Derived classes are simple classes with one constructor and two methods

Constructors and Methods

Study the code and the output from the driver class. Make conclusions and post them in edmodo.com

Constructor behavior

Study the code and the output from the driver class. Make conclusions and post them in edmodo.com

Classwork:
Implement an application similar to the one above to show:

1. Calls to constructors with and without “super”
2. Calls to methods with and without “super”
3. Polymorphism – late binding
4. Do not forget to keep your code well documented with clear explanations

Assignments:
Self-Review 7.1 through 7.8
Programming Project 7.5

Visit edmodo.com

Polymorphism and Inheritance

In Java, the type of a variable does not completely determine the type of the object to which it refers. For example, a variable of type BankAccount can hold a reference to an actual BankAccount object or a subclass object such as SavingsAccount. You already encountered this phenomenon with variables whose type was an interface. A variable whose type is Measurable holds a reference to an object of a class that implements the Measurable interface, perhaps a Coin object or an object of an entirely different class.

What happens when you invoke a method? For example,

BankAccount anAccount = new CheckingAccount();
anAccount.deposit(1000);

Which deposit method is called? The anAccount parameter has type BankAccount, so it would appear as if BankAccount.deposit is called. On the other hand, the CheckingAccount class provides its own deposit method that updates the transaction count. The anAccount field actually refers to an object of the subclass CheckingAccount, so it would be appropriate if the CheckingAccount.deposit method were called instead.

In Java, method calls are always determined by the type of the actual object, not the type of the object reference. That is, if the actual object has the type CheckingAccount, then the CheckingAccount.deposit method is called. It does not matter that the object reference is stored in a field of type BankAccount. The ability to refer to objects of multiple types with varying behavior is called polymorphism .

If polymorphism is so powerful, why not store all account references in variables of type Object? This does not work because the compiler needs to check that only legal methods are invoked. The Object type does not define a deposit method—the BankAccount type (at least) is required to make a call to the deposit method.

Have another look at the transfer method to see polymorphism at work. Here is the implementation of the method:

public void transfer(double amount, BankAccount other)
{
   withdraw(amount);
   other.deposit(amount);
}

Suppose you call

anAccount.transfer(1000, anotherAccount);

Two method calls are the result:

anAccount.withdraw(1000);
anotherAccount.deposit(1000);

Depending on the actual types of anAccount and anotherAccount, different versions of the withdraw and deposit methods are called.

If you look into the implementation of the transfer method, it may not be immediately obvious that the first method call

withdraw(amount);

depends on the type of an object. However, that call is a shortcut for

this.withdraw(amount);

The this parameter holds a reference to the implicit parameter, which can refer to a BankAccount or a subclass object.

The following program calls the polymorphic withdraw and deposit methods.
Manually calculate what the program should print on edmodo.com for each account balance, and confirm that the correct methods have in fact been called.

AccountTester is the driver class:

  /**
     This program tests the BankAccount class and
     its subclasses.
  */
  public class AccountTester
  {
     public static void main(String[] args)
     {
        SavingsAccount momsSavings
             = new SavingsAccount(0.5);

       CheckingAccount harrysChecking
             = new CheckingAccount(100);

       momsSavings.deposit(10000);

       momsSavings.transfer(2000, harrysChecking);
       harrysChecking.withdraw(1500);
       harrysChecking.withdraw(80);

       momsSavings.transfer(1000, harrysChecking);
       harrysChecking.withdraw(400);

       // Simulate end of month
       momsSavings.addInterest();
       harrysChecking.deductFees();

       System.out.println("Mom\'s savings balance: "
             + momsSavings.getBalance());
       System.out.println("Expected: ????");

       System.out.println("Harry\'s checking balance: "
             + harrysChecking.getBalance());
       System.out.println("Expected: ????");
    }
 }

BankAccount Class:

  /**
     A bank account has a balance that can be changed by
     deposits and withdrawals.
  */
  public class BankAccount
  {
     /**
        Constructs a bank account with a zero balance.
     */
    public BankAccount()
    {
       balance = 0;
    }

    /**
       Constructs a bank account with a given balance.
       @param initialBalance the initial balance
    */
    public BankAccount(double initialBalance)
    {
       balance = initialBalance;
    }

    /**
       Deposits money into the bank account.
       @param amount the amount to deposit
    */
    public void deposit(double amount)
    {
       balance = balance + amount;
    }

    /**
       Withdraws money from the bank account.
       @param amount the amount to withdraw
    */
    public void withdraw(double amount)
    {
       balance = balance - amount;
    }

    /**
       Gets the current balance of the bank account.
       @return the current balance
    */
    public double getBalance()
    {
       return balance;
    }

    /**
       Transfers money from the bank account to another account.
       @param amount the amount to transfer
       @param other the other account
    */
    public void transfer(double amount, BankAccount other)
    {
       withdraw(amount);
       other.deposit(amount);
    }

    private double balance;
 }

CheckingAccount Class derived from BankAccount:

  /**
     A checking account that charges transaction fees.
  */
  public class CheckingAccount extends BankAccount
  {
     /**
        Constructs a checking account with a given balance.
        @param initialBalance the initial balance
     */
    public CheckingAccount(double initialBalance)
    {
       // Construct superclass
       super(initialBalance);

       // Initialize transaction count
       transactionCount = 0;
    }

    public void deposit(double amount)
    {
       transactionCount++;
       // Now add amount to balance
       super.deposit(amount);
    }

    public void withdraw(double amount)
    {
       transactionCount++;
       // Now subtract amount from balance
       super.withdraw(amount);
    }

    /**
       Deducts the accumulated fees and resets the
       transaction count.
    */
    public void deductFees()
    {
       if (transactionCount > FREE_TRANSACTIONS)
       {
          double fees = TRANSACTION_FEE *
                (transactionCount - FREE_TRANSACTIONS);
          super.withdraw(fees);
       }
       transactionCount = 0;
    }

    private int transactionCount;

    private static final int FREE_TRANSACTIONS = 3;
    private static final double TRANSACTION_FEE = 2.0;
 }

SavingsAccount derived from BankAccount:

 /**
   An account that earns interest at a fixed rate.
 */
 public class SavingsAccount extends BankAccount
 {
   /**
      Constructs a bank account with a given interest rate.
      @param rate the interest rate
   */
   public SavingsAccount(double rate)
   {
      interestRate = rate;
   }

   /**
      Adds the earned interest to the account balance.
   */
   public void addInterest()
   {
      double interest = getBalance() * interestRate / 100;
      deposit(interest);
   }

   private double interestRate;
}

Look up the definition of the standard Comparable interface in the API documentation. Modify the DataSet class to accept Comparable objects. With this interface, it is no longer meaningful to compute the average. The DataSet class should record the minimum and maximum data values. Test your modified DataSet class by adding a number of String objects. (The String class implements the Comparable interface.)

Complete the following class in your solution:

DataSet Class takes objects of classes that implement the Comparable interface:

/**
   Computes the minimum and maximum of a set of Comparable values.
*/
public class DataSet
{
   /**
      Constructs an empty data set.
   */
   public DataSet()
   {
      . . .
   }

   /**
      Adds a data value to the data set.
      @param x a data value
   */
   public void add(Comparable x)
   {
      . . .
   }

   /**
      Gets the largest of the added data.
      @return the maximum or null if no data has been added
   */
   public Comparable getMaximum()
   {
      . . .
   }

   /**
      Gets the largest of the added data.
      @return the maximum or null if no data has been added
   */
   public Comparable getMinimum()
   {
      . . .
   }

   . . .
}

Use the following class as your tester class:

/**
   This program demonstrates the use of the DataSet that accepts
   instances of the Comparable interface.
*/
public class DataSetTester
{
   public static void main(String[] args)
   {
      DataSet data = new DataSet();
   
      data.add("Helen");
      data.add("Andy");
      data.add("Robert");
      data.add("Vicky");

      Comparable max = data.getMaximum();
      Comparable min = data.getMinimum();
      System.out.println("Maximum: " + max);
      System.out.println("Expected: Vicky");
      System.out.println("Minimum: " + min);
      System.out.println("Expected: Andy");
   }
}

Assignments:
1. From the classes discussed above, draw the UML class diagram and show/demonstrate late binding in inheritance for the BankAccount classes.

1. Show/demonstrate late binding in inheritance for the StaffCrew classes.
   abstract public class StaffCrew
   Volunteer extends StaffCrew
   FullTimeStaff extends StaffCrew
   Supervisor extends FullTimeStaff
   PartTime extends FullTimeStaff

Classwork: Constructors and Methods behavior diagrams.

Polymorphism and Interfaces:

In Java, all instance methods are polymorphic. The same computation works for objects of many shapes, and adapts itself to the nature of the objects.

Polymorphism denotes the principle that behavior can vary depending on the actual type of an object.

When the virtual machine calls an instance method, it locates the method of the implicit parameter’s class. This is called dynamic method lookup.

Dynamic method lookup enables a programming technique called polymorphism.

There is an important difference between polymorphism and overloading. The compiler picks an overloaded method when translating the program, before the program ever runs. This method selection is called early binding.

Interfaces: when selecting the appropriate getMeasure method in a call x.getMeasure(), the compiler does not make any decision when translating the method as mentioned above. The program has to run before anyone can know what is stored in x. Therefore, the virtual machine, and not the compiler, selects the appropriate method. This method selection is called late binding.

Using a polymorphic reference as the formal parameter to a method is a powerful technique. It allows the method to control the types of parameters passed into it, yet gives it the flexibility to accept arguments of various types.

Looking again at the driver for the DataSet of Measurable objects, we have seen this code:

public static void main(String[] args)
   {
      DataSet bankData = new DataSet();
      
      bankData.add(new BankAccount(3000));
      bankData.add(new BankAccount(10000));
      bankData.add(new BankAccount(2000));

      System.out.println("Average balance = " + bankData.getAverage());
      
      Measurable max = bankData.getMaximum();
      System.out.println("Highest balance = " + max.getMeasure());
      //System.out.println("Get bank balance = " + max.getBalance()); 
      // ERROR since "max" is not an object of BankAccount
      BankAccount maxAccount = (BankAccount) max; 
      // casting from interfaces to classes
      // max ---> maxAccount ( object of BankAccount )
      System.out.println("Get bank balance = " + maxAccount.getBalance());
      // NO ERROR
      ....
}

To protect against bad casts, you can use the instanceof operator.

Here is a good example:

if ( max instaceof BankAccount )
   {
      BankAccount maxAccount = (BankAccount) max; 
      System.out.println("Get bank balance = " + maxAccount.getBalance());
    }