Principles of Software Construction:

Objects, Design, and Concurrency

Design Case Study: Java Collections

 
 
 
Fall  2014  

Charlie Garrod Jonathan Aldrich

School of
Computer Science

© 2012-14 C Kästner, C Garrod, J Aldrich, and W Scherlis

 Administrivia
• No homework due next week
§  Start Homework 4b implementation soon…

• Graded midterm exams still available after class

15-­‐214 toad 2
 Key concepts from Tuesday

15-­‐214 toad 3
 The Observer design pattern
• A.k.a. listener, a.k.a. publish/subscribe

observers <<interface>>
Subject
Observer
0..*
+ subscribe(o : Observer) + update()
+ unsubscribe(o : Observer)
# publish()

for all o in observers

o.update();

ConcreteSubject ConcreteObserver

+ getState() + update()
+ setState()
+ observerState
subjectState

15-­‐214 toad 4
 The Strategy design pattern

15-­‐214 toad 5
 Design patterns we have seen so far

Composite Template Method

Adapter

Strategy
Observer

Decorator
Model-View-Controller

15-­‐214 toad 6
 Today: Java Collections

Source: http://wiki3.cosc.canterbury.ac.nz/index.php/User:Jenny_Harlow/Design_study/Java_Collections_Framework
15-­‐214 toad 7
 Learning goals for today
• Understand the design aspects of collection
libraries.
• Recognize the design patterns used and how
those design patterns achieve design goals.
§  Marker Interface
§  Decorator
§  Factory Method
§  Iterator
§  Strategy
§  Template Method
§  Adapter

• Be able to use common collection classes,

including helpers in the Collections class.

15-­‐214 toad 8
 Designing a data structure library
• Different data types: lists, sets, maps, stacks,
queues, …
• Different representations
§  Array-based lists vs. linked lists
§  Hash-based sets vs. tree-based sets
§  …

• Many alternative designs

§  Mutable vs. immutable
§  Sorted vs. unsorted
§  Accepts null or not
§  Accepts duplicates or not
§  Concurrency/thread-safe or not
§  …

15-­‐214 toad 9
 The philosophy of the Collections framework
• Powerful and general
• Small in size and conceptual weight
§  Only include fundamental operations
§  "Fun and easy to learn and use"

15-­‐214 toad 10
 The java.util.Collection<E> interface
   boolean          add(E  e);  
   boolean          addAll(Collection<E>  c);  
   boolean          remove(E  e);  
   boolean          removeAll(Collection<E>  c);  
   boolean          retainAll(Collection<E>  c);  
   boolean          contains(E  e);  
   boolean          containsAll(Collection<E>  c);  
   void                clear();  
   int                  size();  
   boolean          isEmpty();  
   Iterator<E>  iterator();  
   Object[]        toArray()  
   E[]                  toArray(E[]  a);  
   …  
15-­‐214 toad 11
 Java Collections design decisions
• Collection represents group of elements
§  e.g. lists, queues, sets, stacks, …

• No inherent concept of order or uniqueness

• Mutation is optional
§  May throw UnsupportedOperationException  
§  Documentation describes whether mutation is supported

• Maps are not Collections

• Helper functions (sort, search, copy, …) in a
separate Collections class

15-­‐214 toad 12
 The java.util.List<E> interface
• Defines order of a collection
§  Uniqueness unspecified

• Extends java.util.Collection<E>:
boolean  add(int  index,  E  e);  
E              get(int  index);  
E              set(int  index,  E  e);  
int          indexOf(E  e);  
int          lastIndexOf(E  e);  
List<E>  sublist(int  fromIndex,  int  toIndex);  

15-­‐214 toad 13
 The java.util.Set<E> interface
• Enforces uniqueness of each element in collection
• Extends java.util.Collection<E>:
//adds  invariant  (textual  specification)  only

• The Marker Interface design pattern

§  Problem: You want to define a behavioral constraint not
enforced at compile time.
§  Solution: Define an interface with no methods, but with
additional invariants as a Javadoc comment or JML
specification.

15-­‐214 toad 14
 The java.util.Queue<E> interface
• Additional helper methods only
• Extends java.util.Collection<E>:
boolean  add(E  e);        //  These  three  methods  
E              remove();        //  might  throw  exceptions  
E              element();        
 
boolean  offer(E  e);  
E              poll();            //  These  two  methods  
E              peek();            //  might  return  null  

• Aside: Is Queue<E> a behavioral subtype?

15-­‐214 toad 15
 The java.util.Map<K,V> interface
• Map of keys to values; keys are unique
• Does not extend java.util.Collection<E>  
V              put(K  key,  V  value);  
V              get(Object  key);  
V              remove(Object  key);  
boolean  containsKey(Object  key);  
boolean  containsValue(Object  value);  
void        putAll(Map<K,V>  m);  
int          size();  
boolean  isEmpty();  
void        clear();  
Set<K>                            keySet();  
Collection<V>              values();  
Set<Map.Entry<K,V>>  entrySet();  

15-­‐214 toad 16
 One problem: Java arrays are not Collections
• To convert a Collection to an array
§  Use the toArray() method
   List<String>  arguments  =  new  LinkedList<String>();  
   …                              //  puts  something  into  the  list  
   String[]  arr  =  (String[])  arguments.toArray();  
   String[]  brr  =  arguments.toArray(new  String[0]);  

• To view an array as a Collection  

§  Use the java.util.Arrays.asList() method
 String[]  arr  =  {"foo",  "bar",  "baz",  "qux"};  
   List<String>  arguments  =  Arrays.asList(arr);  

What design
pattern is this?

15-­‐214 toad 17
 One problem: Java arrays are not Collections
• To convert a Collection to an array
§  Use the toArray() method
   List<String>  arguments  =  new  LinkedList<String>();  
   …                              //  puts  something  into  the  list  
   String[]  arr  =  (String[])  arguments.toArray();  
   String[]  brr  =  arguments.toArray(new  String[0]);  

• To view an array as a Collection  

§  Use the java.util.Arrays.asList() method
   String[]  arr  =  {"foo",  "bar",  "baz",  "qux"};  
   List<String>  arguments  =  Arrays.asList(arr);  

• The Adapter design pattern

§  Arrays.asList() returns an adapter from an array to the List
interface

15-­‐214 toad 18
 Java Collections as a framework
• You can write specialty collections
§  Custom representations and algorithms
§  Custom behavioral guarantees
• e.g., file-based storage

• JDK built-in algorithms (e.g. all helper functions in

Collections) would then be calling your collections
code

15-­‐214 toad 19
 The abstract  java.util.AbstractList<T>  
   abstract  T      get(int  i);                          //  Template  Method.  
   abstract  int  size();                                  //  Template  Method.  
   boolean            set(int  i,  E  e);                //  set  add  remove  are    
   boolean            add(E  e);                              //  pseudo-­‐abstract  
   boolean            remove(E  e);                        //  Template  Methods.  
   boolean            addAll(Collection<E>  c);  
   boolean            removeAll(Collection<E>  c);  
   boolean            retainAll(Collection<E>  c);  
   boolean            contains(E  e);  
   boolean            containsAll(Collection<E>  c);  
   void                  clear();  
   boolean            isEmpty();  
   Iterator<E>    iterator();  
   Object[]          toArray()  
   E[]                    toArray(E[]  a);  
   …  
15-­‐214 toad 20
 Traversing a Collection
• Old-school Java for loop for ordered types
List<String>  arguments  =  …;  
for  (int  i  =  0;  i  <  arguments.size();  ++i)  {  
   System.out.println(arguments.get(i));  
}  

• Modern standard Java for-each loop

List<String>  arguments  =  …;  
for  (String  s  :  arguments)  {  
   System.out.println(s);  
}  
§  Works for every implementation of Iterable  
   public  interface  Iterable<E>  {  
       public  Iterator<E>  iterator();  
   }  

15-­‐214 toad 21
 The Iterator interface
public  interface  java.util.Iterator<E>  {  
   boolean  hasNext();  
   E  next();  
   void  remove();    //  removes  previous  returned  item  
}                                  //  from  the  underlying  collection  

• To use, e.g.:

List<String>  arguments  =  …;      
for  (Iterator<String>  it  =  arguments.iterator();  
         it.hasNext();    )  {  
   String  s  =  it.next();  
   System.out.println(s);  
}  

15-­‐214 toad 22
 The Iterator design pattern
• Provide a strategy to uniformly access all
elements of a container in a sequence
§  Independent of the container implementation
§  Ordering is unspecified, but every element visited once

• Design for change, information hiding

§  Hides internal implementation of container behind uniform
explicit interface

• Design for reuse, division of labor

§  Hides complex data structure behind simple interface
§  Facilitates communication between parts of the program

15-­‐214 toad 23
 Creating Iterators
public  interface  Collection<E>  {      
   boolean          add(E  e);  
   boolean          addAll(Collection<E>  c);  
   boolean          remove(E  e);  
   boolean          removeAll(Collection<E>  c);  
   boolean          retainAll(Collection<E>  c);  
   boolean          contains(E  e);  
   boolean          containsAll(Collection<E>  c);  
   void                clear();  
   int                  size();  
Defines an interface for
   boolean          isEmpty();  
creating an Iterator,
   Iterator<E>  iterator();  
but allows Collection
   Object[]        toArray()  
implementation to decide
   E[]                  toArray(E[]  a);  
which Iterator to create.
   …  
}  

15-­‐214 toad 24
 The Factory Method design pattern

15-­‐214 toad 25
 The Factory Method design pattern

• Applicability • Consequences
§  A class can’t anticipate §  Provides hooks for
the class of objects it subclasses to
must create customize creation
§  A class wants its behavior
subclasses to specify §  Connects parallel class
the objects it creates hierarchies
15-­‐214 toad 26
 A Pair Iterator example
public  class  Pair<E>  implements  Iterable<E>  {  
   private  final  E  first,  second;  
   public  Pair(E  f,  E  s)  {  first  =  f;  second=s;}  
   public  Iterator<E>  iterator()  {  
       return  new  PairIterator();  
   }  
   private  class  PairIterator  implements  Iterator<E>  {  
       private  boolean  seen1=false,  seen2=false;  
       public    boolean  hasNext()  {  return  !seen2;  }  
       public    E  next()  {  
           if  (!seen1)  {  seen1=true;  return  first;  }  
           if  (!seen2)  {  seen2=true;  return  second;  }  
           throw  new  NoSuchElementException();  
       }  
       public  void  remove()  {  throw  new  UnsupportedOperationExcepti
 
   }   Pair<String>  pair  =  new  Pair<String>("foo",  "bar");  
}   for  (String  s  :  pair)  {  …  }  
 
15-­‐214 toad 27
 Using a java.util.Iterator<E>: A warning
• The default Collections implementations are
mutable…
• …but their Iterator implementations assume the
collection does not change while the Iterator is
being used
§  You will get a ConcurrentModificationException  
§  One way to fix:
List<String>  arguments  =  …;      
     for  (Iterator<String>  it  =  arguments.iterator();  
               it.hasNext();    )  {  
         String  s  =  it.next();  
         if  (s.equals("Charlie"))    
             arguments.remove("Charlie");  //  runtime  error  
     }  

15-­‐214 toad 28
 Sorting a Collection
• Use the Collections.sort method:
public  static  void  main(String[]  args)  {  
   List<String>  lst  =  Arrays.asList(args);  
   Collections.sort(lst);  
   for  (String  s  :  lst)  {  
       System.out.println(s);  
   }  
}  

• A hacky aside: abuse the SortedSet:

public  static  void  main(String[]  args)  {  
   SortedSet<String>  set  =    
               new  TreeSet<String>(Arrays.asList(args));  
   for  (String  s  :  set)  {  
       System.out.println(s);  
   }  
}  

15-­‐214 toad 29
 Sorting your own types of objects
   public  interface  Comparable<T>  {  
       int  compareTo(T  o);  
   }  
• General contracts:
§  a.compareTo(b) should return:
<0 if a is less than b
0 if a and b are equal
>0 if a is greater than b
§  Should define a total order:
• If a.compareTo(b) < 0 and b.compareTo(c) < 0, then
a.compareTo(c) should be < 0
• If a.compareTo(b) < 0, then b.compareTo(a) should be
>0
§  Should usually be consistent with .equals:
• a.compareTo(b) == 0 iff a.equals(b)  

15-­‐214 toad 30
 Comparable objects – an example
public  class  Integer  implements  Comparable<Integer>  {  
   private  int  val;  
   public  Integer(int  val)  {  this.val  =  val;  }  
   …  
   public  int  compareTo(Integer  o)  {  
       if  (val  <  o.val)  return  -­‐1;  
       if  (val  ==  o.val)  return  0;  
       return  1;  
   }  
}   Aside: Is this
the Template
Method pattern?

15-­‐214 toad 31
 Comparable objects – another example

• Make Name comparable:

public  class  Name                                                          {  

   private  String  first;  
   private  String  last;  
   public  Name(String  first,  String  last)  {    //  should  
       this.first  =  first;    this.last  =  last;    //  check  
   }                                                                                  //  for  null  
   …  

• Hint: Strings implement Comparable<String>  

15-­‐214 toad 32
 Comparable objects – another example

• Make Name comparable:

public  class  Name  implements  Comparable<Name>  {  

   private  String  first;  
   private  String  last;  
   public  Name(String  first,  String  last)  {    //  should  
       this.first  =  first;    this.last  =  last;    //  check  
   }                                                                                  //  for  null  
   …  
   public  int  compareTo(Name  o)  {  
       int  lastComparison  =  last.compareTo(o.last);  
       if  (lastComparison  !=  0)  return  lastComparison;  
       return  first.compareTo(o.first);  
   }  
}  

15-­‐214 toad 33
 Alternative comparisons
public  class  Employee  implements  Comparable<Employee>  {  
   protected  Name  name;  
   protected  int    salary;  
   …  
}  

• What if we want to sort Employees by name, usually,

but sometimes sort by salary?

15-­‐214 toad 34
 Alternative comparisons
public  class  Employee  implements  Comparable<Employee>  {  
   protected  Name  name;  
   protected  int    salary;  
   …  
}  

• What if we want to sort Employees by name, usually,

but sometimes sort by salary?
• Answer: There's a Strategy design pattern
interface for that
public  interface  Comparator<T>  {  
   public  int          compare(T  o1,  T  o2);  
   public  boolean  equals(Object  obj);  
}

15-­‐214 toad 35
 Tradeoffs
void  sort(int[]  list,  String  order)  {  
     …    
   boolean  mustswap;    
   if  (order.equals("up"))  {  
       mustswap  =  list[i]  <  list[j];  
   }  else  if  (order.equals("down"))  {  
       mustswap  =  list[i]  >  list[j];  
   }  
   …  
}  
  void  sort(int[]  list,  Comparator  cmp)  {  
   …    
   boolean  mustswap;    
   mustswap  =  cmp.compare(list[i],  list[j]);  
   …  
}  
interface  Comparator  {  
   boolean  compare(int  i,  int  j);  
}  
class  UpComparator  implements  Comparator  {  
   boolean  compare(int  i,  int  j)  {  return  i<j;  }  }  
 
class  DownComparator  implements  Comparator  {  
   boolean  compare(int  i,  int  j)  {  return  i>j;  }  }  

15-­‐214 toad 36
 Writing a Comparator object
public  class  Employee  implements  Comparable<Employee>  {  
   protected  Name  name;  
   protected  int    salary;  
   public  int  compareTo(Employee  o)  {  
       return  name.compareTo(o.name);  
   }  
}  
 
public  class  EmpSalComp  implements  Comparator<Employee>  {  
   public  int  compare  (Employee  o1,  Employee  o2)  {  
       return  o1.salary  –  o2.salary;      
   }  
   public  boolean  equals(Object  obj)  {  
       return  obj  instanceof  EmpSalComp;  
   }  
}  

15-­‐214 toad 37
 Using a Comparator
• Order-dependent classes and methods take a
Comparator as an argument

public  class  Main  {  

   public  static  void  main(String[]  args)  {  
       SortedSet<Employee>  empByName  =      //  sorted  by  name  
                   new  TreeSet<Employee>();  
 
       SortedSet<Employee>  empBySal  =    //  sorted  by  salary    
                   new  TreeSet<Employee>(new  EmpSalComp());  
   }  
}  

15-­‐214 toad 38
 The java.util.Collections class
• Standard implementations of common algorithms
§  binarySearch, copy, fill, frequency, indexOfSubList,
min, max, nCopies, replaceAll, reverse, rotate, shuffle,
sort, swap, …

public  class  Main()  {  

   public  static  void  main(String[]  args)  {  
       List<String>  lst  =  Arrays.asList(args);  
       int  x  =  Collections.frequency(lst,  "Charlie");  
       System.out.println("There  are  "  +  x  +    
                                             "  students  named  Charlie");  
   }  
}  

15-­‐214 toad 39
 The java.util.Collections class
• Helper methods in java.util.Collections:
static  List<T>    unmodifiableList(List<T>    lst);  
static  Set<T>      unmodifiableSet(  Set<T>      set);  
static  Map<K,V>  unmodifiableMap(  Map<K,V>  map);  
§  e.g., Turn a mutable list into an immutable list
• All mutable operations on resulting list throw an
UnsupportedOperationException  

• Similar for synchronization:

static  List<T>    synchronizedList(List<T>    lst);  
static  Set<T>      synchronizedSet(  Set<T>      set);  
static  Map<K,V>  synchronizedMap(  Map<K,V>  map);  

15-­‐214 toad 40
 e.g., The UnmodifiableCollection class
public  static  <T>  Collection<T>  unmodifiableCollection(Collection<T>  c)  {
 return  new  UnmodifiableCollection<>(c);    
 }    

 class  UnmodifiableCollection<E>    
         implements  Collection<E>,  Serializable  {    

 final  Collection<E>  c;  

 UnmodifiableCollection(Collection<>  c){this.c  =  c;  }    

 public  int      size()    {return  c.size();}    
 public  boolean      isEmpty()      {return  c.isEmpty();}    
 public  boolean      contains(Object  o)    {return  c.contains(o);}    
 public  Object[]  toArray()      {return  c.toArray();}    
 public  <T>  T[]      toArray(T[]  a)    {return  c.toArray(a);}    
 public  String      toString()      {return  c.toString();}  
 public  boolean      add(E  e)  {throw  new  UnsupportedOperationException();  }  
 public  boolean      remove(Object  o)    {  throw  new  UnsupportedOperationExc
 public  boolean      containsAll(Collection<?>  coll)  {  return  c.containsAll(
 public  boolean      addAll(Collection<?  extends  E>  coll)  {  throw  new  Unsupp
 public  boolean
15-­‐214      removeAll(Collection<?>  coll)  {  throw  new  UnsupportedOp
toad 41
 e.g., The UnmodifiableCollection class
public  static  <T>  Collection<T>  unmodifiableCollection(Collection<T>  c)  {
What design
 return  new  UnmodifiableCollection<>(c);    
 }     pattern is this?
 class  UnmodifiableCollection<E>    
         implements  Collection<E>,  Serializable  {    

 final  Collection<E>  c;  

 UnmodifiableCollection(Collection<>  c){this.c  =  c;  }    

 public  int      size()    {return  c.size();}    
 public  boolean      isEmpty()      {return  c.isEmpty();}    
 public  boolean      contains(Object  o)    {return  c.contains(o);}    
 public  Object[]  toArray()      {return  c.toArray();}    
 public  <T>  T[]      toArray(T[]  a)    {return  c.toArray(a);}    
 public  String      toString()      {return  c.toString();}  
 public  boolean      add(E  e)  {throw  new  UnsupportedOperationException();  }
 public  boolean      remove(Object  o)    {  throw  new  UnsupportedOperationExc
 public  boolean      containsAll(Collection<?>  coll)  {  return  c.containsAll
 public  boolean      addAll(Collection<?  extends  E>  coll)  {  throw  new  Unsup
 public  boolean
15-­‐214      removeAll(Collection<?>  coll)  {  throw  new  UnsupportedO
toad 42
 e.g., The UnmodifiableCollection class
public  static  <T>  Collection<T>  unmodifiableCollection(Collection<T>  c)  {
What design
 return  new  UnmodifiableCollection<>(c);    
 }     pattern is this?
 class  UnmodifiableCollection<E>     UnmodifiableCollection
         implements  Collection<E>,  Serializable  {    
    decorates Collection by
 final  Collection<E>  c;   removing functionality…
 UnmodifiableCollection(Collection<>  c){this.c  =  c;  }    
 public  int      size()    {return  c.size();}    
 public  boolean      isEmpty()      {return  c.isEmpty();}    
 public  boolean      contains(Object  o)    {return  c.contains(o);}    
 public  Object[]  toArray()      {return  c.toArray();}    
 public  <T>  T[]      toArray(T[]  a)    {return  c.toArray(a);}    
 public  String      toString()      {return  c.toString();}  
 public  boolean      add(E  e)  {throw  new  UnsupportedOperationException();  }
 public  boolean      remove(Object  o)    {  throw  new  UnsupportedOperationExc
 public  boolean      containsAll(Collection<?>  coll)  {  return  c.containsAll
 public  boolean      addAll(Collection<?  extends  E>  coll)  {  throw  new  Unsup
 public  boolean
15-­‐214      removeAll(Collection<?>  coll)  {  throw  new  UnsupportedO
toad 43
 Summary
• Collections as reusable and extensible data
structures
§  design for reuse
§  design for change

• Iterators to abstract over internal structure

• Decorator to attach behavior at runtime
• Template methods and factory methods to
support behavior changes in subclasses
• Adapters to bridge between implementations
• Strategy pattern for sorting

15-­‐214 toad 44