Incremental Java
Dean's List

Problem Statement

Imagine you have a class called StudentList. It contains an instance variable which is an ArrayList, which itself contains Student objects.

Here's the class definition for Student 

public class Student
{
   private String lastName, String firstName ;
   private double gpa ;

   public Student( String firstNameIn, String lastNameIn )
   {
      lastName = lastNameIn ;
      firstName = firstNameIn ;
   }

   public void setGpa( double gpaIn )
   {
      gpa = gpaIn ;
   }

   public double getGpa()
   {
      return gpa ;
   }
}
This is a simple class, but it serves its purpose.

This is the StudentList class definition. 

public class Student
{
   private ArrayList studentList = new ArrayList() ;

   public StudentList()
   {
   }

   public Student getStudent( int index )
   {
      return (Student) studentList.get( index ) ;
   }

   public Student addStudent( Student stu )
   {
      return studentList.add( stu ) ;
   }

   public int size()
   {
      return studentList.size() ;
   }
    
}
We want to add a method called getDeansList() which returns a new StudentList containing students with a GPA above 3.5.

There are some interesting issues on how to do this.

Pseudocode and Implementation

Here's one approach to the problem.
  1. Make a new StudentList as a local variable
  2. Go to next student in the StudentList
  3. Does the student have a GPA above 3.5?
  4. If yes, add Student to new StudentList
  5. Go back to step 2
So, we go through the list checking each student. If the student has the minimum GPA, they are added to a second list. The first list doesn't change.

Here's an implementation. 

public ArrayList getDeansList()
{
   // Make new list
   StudentList newList = new StudentList() ;

   // studentList is an instance variable
   // Look at each student
   for ( int i = 0 ; i < studentList.size() ; i++ )
   {
      Student s = studentList.getStudent( i ) ;
      // Filter based on GPA
      if ( s.getGpa() >= 3.5 )
         newList.addStudent( s ) ;
   }
}

Filtering

A program that goes through a container list, and selects only those that meet a criteria (in this case, GPA above 3.5), is a filter program.

Unlike a "real" filter, a filter program does not usually separate a list of items into two or more categories. Instead, it goes through one list, copies the object handles, adds it to a second list. The original list is not changed.

Handles Are Copied

Although we've created a new StudentList (called newList), no new Student objects are constructed. We only copied handles. For example, suppose there's a student named Jana Novotna who has a 3.6 GPA that appears in the original studentList. There is an object handle to this Student object in newList as well.

Suppose we went into studentList and modified the GPA for Jana Novotna to 3.7. If we found Java Novotna in the newList, and looked at the GPA, it would also be 3.7. That's because studentList and newList both have a handle to the same Student object.

Deep vs. Shallow Copy

When you copy handles, you are making a shallow copy. This means there's an object shared by more than one handle.

We can make a deep copy where the entire object is copied. When this happens, we have two completely separate objects. If one of the objects is modified, the other is left alone.

Here's an example of the same method, but this time using a deep copy. 

public ArrayList getDeansList()
{
   // Make new list
   StudentList newList = new StudentList() ;

   // studentList is an instance variable
   // Look at each student
   for ( int i = 0 ; i < studentList.size() ; i++ )
   {
      Student s = studentList.getStudent( i ) ;
      Student deepCopy = new Student( s.getFirstName(), s.getLastName() ) ;
      deepCopy.setGpa( s.getGpa() ) ;
      // Filter based on GPA
      if ( deepCopy.getGpa() >= 3.5 )
         newList.addStudent( deepCopy ) ;
   }
}
This time, we made a deep copy. The local variable deepCopy constructs a completely new Student object, then copies the data from the original object to a new one.

Previously, we copied the object handle, which was a shallow copy.

Which is Better?

There's no good answer. Basically, you ask yourself whether you want to share objects when you copy (if so, use a shallow copy) or not. If you want a completely different copy, you do a deep copy.

It's more efficient to do shallow copies (which only copy handles) than deep copies (which usually requires a lot more copying).

Diagram of Shallow Copy

PICTURE GOES HERE

Immutability

When you studied String objects, you learned they were immutable. Once a string is constructed, you can't change. You can concatenate, but that makes a new string. Want to get a substring? Also makes a new string.

Even though the object (balloon) can't change, you can assign the variable (which is a handle) to another balloon. But you can't modify the object.

If an object is immutable, then you don't really need deep copies. Deep copies are more "expensive" (they take more time) than shallow copies. Unfortunately, few classes are immutable, so you then have to decide whether you need a true deep copy, or whether copying handles and sharing the object is better.