A - 11/20/03 A2 -1CS494Interfaces and Collection in Java1/20/03 A2 -2Java Interfaces• Note that the word “interface”– Is a specific term for a language contstruct– Is not the general word for “communication boundary”– Is also a term used in UML (but not in C++)1/20/03 A2 -3Why Use Inheritance?• Why inherit? Create a class that…1. Makes sense in problem domain2. Locates common implementation in superclass3. Defines a shared API (methods) so we can…4. Use polymorphism• Define a reference or parameter in terms of the superclass• If just last two, then use Java interface– No shared implementation– You commit that part of what defines a class is that it meets a particular API– We can write methods etc. that operate on objects of any class that meets or supports that interface1/20/03 A2 -4Two Types of Inheritance• How can inheritance support reuse?• Implementation Inheritance– A subclass reuses some implementation from an ancestor– In Java, keyword extends• Interface Inheritance– A “subclass” shares the interface with an “ancestor”– In Java, keyword implements– I.e. this class will support this set of methods1/20/03 A2 -5Interfaces and Abstract Classes• Abstract classes:– Cannot create any instances• Prefer Java interfaces over abstract classes!– Existing classes can add an interface– Better support for mix-in classes• E.g. Comparable interface -- supports compare()– Do not need a hierarchical framework– Composition preferred over inheritance• E.g. wrapper classes• But, abstract classes have some implementation– Skeletal implementation classes, e.g. AbstractCollection• Disadvantage: once released, a public interface shouldn’t be updated1/20/03 A2 -6Interfaces in Other Languages• A modeling method in UML• Interfaces in C++– All methods are pure virtual– No data members– Use multiple inheritanceA - 21/20/03 A2 -7Collections in Java• ADT: more than one implementation meets same interface, models same data• In Java, separate interface from implementation• We’ll illustrate with “fake” Java example:– Queue interface– Two implementations1/20/03 A2 -8Defining an Interface• Java code:interface Queue {void add (Object obj);Object remove();int size();}• Nothing about implementation here!– methods and no fields1/20/03 A2 -9Using Objects by Interface• Say we had two implementations:Queue q1 = new CircularArrayQueue(100);orQueue q1 = new LinkedListQueue();q1.add( new Widget() );Queue q3 = new …Queue q2 = mergeQueue(q2, q3);1/20/03 A2 -10Implementing an Interface• Example:class CircularArrayQueue implements Queue { CircularArrayQueue(int capacity) {…}public void add(Object o) {…}public Object remove() {…}public int size() {…}private Object[] elements;private int head;private int tail;}1/20/03 A2 -11Implementing an Interface (2)• Implementation for LinkedListQueue similar• Question: How to handle errors?– Array version is bounded. add() when full?– Throw an exception, perhaps– Not an issue for linked list version, though1/20/03 A2 -12Real Collection Interfaces in Java• All collections meet Collection interface:boolean add(Object obj);Iterator iterator();int size();boolean isEmpty();boolean contains(Object obj);boolean containsAll (Collection other);…• See Java API documentation for all methodsA - 31/20/03 A2 -13Iterator Interface• Three fundamental methods:Object next();boolean hasNext();void remove();• We use an iterator object returned by Collection.iterator() to visit or process items in the collection– Don’t really know or care how its implemented1/20/03 A2 -14Example Iterator Code• Traverse a collection of Widgets and get each objectIterator iter = c.iterator();while ( iter.hasNext() ) {Object obj = iter.next();// or: Widget w = (Widget) iter.next();// do something with obj or w}• Note the cast!1/20/03 A2 -15Methods Defined by Other IF Methods• Some collection methods can be defined “abstractly”public boolean addAll (Collection from) {Iterator iterFrom = from.iterator();boolean modified = false;while ( iterFrom.hasNext() )if ( add(iterFrom.next()) ) modified = true;return modified;}1/20/03 A2 -16Collections and Abstract Classes• To define a new Collection, one must implement all methods -- a pain!• Better: define a skeletal implementation class– Leaves primitives undefined: add(), iterator()– Defines other methods in terms of those• Concrete collection class inherits from skeletal class– Defines “primitives”– Overrides any methods it chooses too• Java library: AbstractCollection– Implements Collection IF– You inherit from it to roll your own Collection1/20/03 A2 -17Java’s Concrete Collection Classes• Vector is like array but grows dynamically– Insertion or deletion in the middle expensive• LinkedList class– Doubly-linked– Ordered collection• add() inserts at end of list• How do we add in middle?1/20/03 A2 -18ListIterator Interface• ListIterator (sub)interface extends Iterator// add element before iterator positionvoid add(Object o); // on ListIterator objectObject previous();boolean hasPrevious();void set(Object o);int nextIndex(); and int previousIndex();• Also a factory that takes an initial position. E.g. ListIterator backIter = c.listIterator( c.size() );• Concurrent modification by two iterators?– ListIterator checks for thisA - 41/20/03 A2 -19ArrayList Collection• Like a Vector but implements the List IF– Stores an array internally– Access to element by index is constant, O(1)– Element insertion/removal is W(n) = O(n)– Expansion automatic (but with time costs)• Supports get(index) and set(index)– So does LinkedList but inefficient– Note: in Vector, elementAt() and setElementAt()• Supports synchronization– Vector does not.1/20/03 A2 -20List Interface• All methods from Collection interface, plus…• int indexOf(Object elem) -- not found? -1• int lastIndexOf(Object elem)• Object remove(int index)• Object set(int index, Object elem)• Object clone() -- makes a shallow copy• List subList(int fromIndex, int toIndex)1/20/03 A2 -21Other ArrayList Methods• Constructors:– default; given initial capacity; given Collection• Capacity management:– void ensureCapacity();void trimToSize();• Collection to array:– Object[] toArray();1/20/03 A2 -22Map Interface and Map Classes• Map interface defines generic map collection methods• Two
View Full Document