CSD Univ. of Crete 

The Java Collection Framework: Interfaces, Classes, and Algorithms 

1 

Fall 2007 

The Java Collection Framework: Interfaces, Classes, and Algorithms

CSD Univ. of Crete 

What is a Framework? 

�  “A framework is a set of classes that embodies an abstract design for solutions to a family of related problems, and supports reuse at a larger granularity than classes.” ¿ “Designing Reuseable Classes”, Johnson and Foote 1988 

�  “A framework is a set of prefabricated software building blocks that programmers can use, extend, or customize for specific computing solutions.” ¿ “Building Object­Oriented Frameworks”  Taligent/IBM 

2 

Fall 2007 

What is a Framework? 

“A framework is a set of classes that embodies an abstract design for solutions to a family of related problems, and supports reuse at a larger 

“Designing Reuseable Classes”, Johnson and Foote 1988 

“A framework is a set of prefabricated software building blocks that programmers can use, extend, or customize for specific computing 

Oriented Frameworks”  Taligent/IBM

CSD Univ. of Crete 

The Gang of Four on Frameworks 

�  “The framework dictates the architecture of your application.  It will define the overall structure, its partitioning into classes and objects, the key responsibilities thereof, how the classes and objects collaborate, and the thread of control.  A framework predefines these design parameters so that you, the application designer/implementer can concentrate on the specifics of your application.  The framework captures the design decisions that are common to its application domain.  Frameworks thus emphases design reuse over code reuse, though a framework will usually include concrete subclasses you can put to work immediately.” ¿ Gamma, Helm, Johnson, Vlissides  “Design Patterns: Elements of Reusable Object­Oriented Software” p. 25 

3 

Fall 2007 

The Gang of Four on Frameworks 

“The framework dictates the architecture of your application.  It will define the overall structure, its partitioning into classes and objects, the key responsibilities thereof, how the classes and objects collaborate, and the thread of control.  A framework predefines these design parameters so that you, the application designer/implementer can concentrate on the specifics of your application.  The framework captures the design decisions that are common to its application domain.  Frameworks thus emphases design reuse over code reuse, though a framework will usually include concrete subclasses you can 

Gamma, Helm, Johnson, Vlissides  “Design Patterns: Elements of Oriented Software” p. 25

CSD Univ. of Crete 

More than just a Good O/O Implementation ? 

� “An abstract class is a design for a single object.  A framework is the design of a set of objects that collaborate to carry out a set of responsibilities.  Thus frameworks are larger scale designs than abstract classes.  Frameworks are a way to reuse high ¿“Reusing Object­Oriented Designs”, Johnson and Russo, 1991 

� “Frameworks are not simply collections of classes.  Rather, frameworks come with rich functionality and strong wired between object classes that provide an infrastructure for the developer.” ¿Taligent, 1993 

4 

Fall 2007 

More than just a Good O/O Implementation ? 

“An abstract class is a design for a single object.  A framework is the design of a set of objects that collaborate to carry out a set of responsibilities.  Thus frameworks are larger scale designs than abstract classes.  Frameworks are a way to reuse high­level design.” 

Oriented Designs”, Johnson and Russo, 1991 

“Frameworks are not simply collections of classes.  Rather, frameworks come with rich functionality and strong wired­in interconnections between object classes that provide an infrastructure for the developer.”

CSD Univ. of Crete 

Why Write a Framework? 

� Frameworks ¿

¿

¿

¿

¿

� Programming with Components ¿Finding functionality ¿Learning the structures and dependencies among components ¿Reading more than you write but more than you are used to...?  5 

Fall 2007 

Why Write a Framework? 

Frameworks decrease programmer effort ¿Make it easier to use different APIs together (Interoperability) ¿Reduces the effort required to learn APIs ¿Reduces the effort required to design and implement APIs ¿Increases code reliability ¿Fosters software reuse

CSD Univ. of Crete 

What is a Collection? 

�  A collection (sometimes called a container multiple elements into a single unit ¿ Collections are used to store, retrieve transmit data from one method to another 

¿ Collections typically represent data items that form a natural group, a card hand, a mail folder, a telephone directory… 

�  Recall the difference between ADTs and Data Structures: ¿ ADT: collection of data and a set of operations on that data ¿ Data structure: construct within a programming language that stores a collection of data 

ADT 

•Type •Operation 

Data Items: Logical Form 

6 

Fall 2007 

What is a Collection? 

container) is an object that groups 

retrieve and manipulate data, and to data from one method to another 

Collections typically represent data items that form a natural group, a card hand, a mail folder, a telephone directory… 

Recall the difference between ADTs and Data Structures: collection of data and a set of operations on that data 

construct within a programming language that stores 

Data Items: Physical Form 

Data Structure •Storage Space •Functions

CSD Univ. of Crete 

Given a Container, You ... 

� Put an object in � Take an object out � Ask about a specific object 

¿Is it in the container ? ¿Is an equivalent object in the container ? ¿How many times ? 

� Retrieve an object by a key value �  Iterate over everything in the container 

� Putting ADT theory into practice 

7 

Fall 2007 

Given a Container, You ... 

Is an equivalent object in the container ? 

Iterate over everything in the container

CSD Univ. of Crete 

The Java Collections Framework �  A new framework in Java 2: Provide a basic set of “Object Containers” 

¿ Core data structures for everyday coding �  Predecessors: 

¿ C++’s Standard Template Library and ObjectSpace’s JGL ¿ JDK 1.02 : Vector, Hashtable, and Enumeration 

�  The Java Collections Framework provides: ¿  Interfaces: abstract data types representing collections ¿  Implementations: concrete implementations of the collection interfaces ¿ Algorithms: methods that perform useful computations, like searching and sorting, on objects that implement collection interfaces 

�  Core Interfaces: ¿ Collection ¿ Set ¿ List ¿ Map ¿ SortedSet ¿ SortedMap  8 

Fall 2007 

The Java Collections Framework A new framework in Java 2: Provide a basic set of “Object Containers” 

Core data structures for everyday coding 

C++’s Standard Template Library and ObjectSpace’s JGL JDK 1.02 : Vector, Hashtable, and Enumeration 

The Java Collections Framework provides: : abstract data types representing collections 

: concrete implementations of the collection interfaces : methods that perform useful computations, like searching 

and sorting, on objects that implement collection interfaces �  Utility Interfaces 

¿ Comparator ¿  Iterator 

�  Utility Classes ¿ Collections ¿ Arrays

CSD Univ. of Crete 

Types of Collections 

� Collections can be classified by two parameters ¿is duplicates allowed? ¿are the elements ordered? 

List 

Map not allowed 

Ordered 

allowed Duplicates 

9 

Fall 2007 

Types of Collections 

two parameters 

List 

Map 

Ordered  Not ordered 

Multiset (Bag) 

Set

CSD Univ. of Crete 

The Java Collections Framework 

Abstract Classes 

Concrete Classes 

10 

Fall 2007 

The Java Collections Framework

Interfaces

CSD Univ. of Crete 

The Main Interfaces 

Collection 

Set  List 

SortedSet 

�  The Collection interface is a group of objects, with duplicates allowed ¿ Set extends Collection but forbids duplicates ¿ List extends Collection and allows duplicates and positional indexing 

¿ Map extends neither Set nor Collection 

Simple Container No 

Duplicates 

11 

Fall 2007 

The Main Interfaces 

Map 

List 

SortedMap 

interface is a group of objects, with duplicates allowed but forbids duplicates and allows duplicates and positional 

Collection and forbids duplicates 

Keyed Access 

Generalized Arrays

CSD Univ. of Crete 

The Main Implementations 

Collection 

Set 

List 

SortedSet AbstractList 

LinkedList 

HashSet 

TreeSet 

AbstractSet 

Abstract Collection 

12 

Fall 2007 

The Main Implementations 

Map 

List 

SortedMap 

ArrayList 

AbstractList 

HashMap  TreeMap 

AbstractMap

CSD Univ. of Crete 

Collection

� A Collection is a group of objects 

� Designed for access via Iterators ¿You can add, remove, lookup isolated items in the collection 

� Easily extended for sorting elements 

� Examples: ¿distinct words in a novel ¿reserved keywords in java ¿students taking HY252 

� A ciates a in 

� Designed for providing access to values stored by key 

� Examples 

13 

Fall 2007 

Collection versus Map A Map (mathematical function) asso­ ciates a value with each member key in its domain ¿set of pairs (key­value), each pair representing a “one­directional mapping” from one set to another 

Designed for providing associative access to values stored by key ¿The collection operations are available but they work with a key­ value pair instead of an isolated element ¿Listing all (key,value) pairs requires using an iterator on the key set (domain of the map) 

Examples ¿A map of keys to database records ¿A dictionary (words mapped to meanings)

CSD Univ. of Crete 

Collection 

Vassilis 

Dimitris 

Giorgos 

Grigoris 

Keys 

� map keeps association between key and value objects � every key in a map has a unique value � a value may be associated with several keys  14 

Fall 2007 

Collection versus Map 

Values 

map keeps association between key and value objects every key in a map has a unique value a value may be associated with several keys

CSD Univ. of Crete 

Set versus 

� Sets are faithful to their mathe­ matical definition 

� No methods added to Collection but simply enforces “no duplicates” rule using the equals method ¿More formally, sets contain no pair of elements e1 and e2  such that e1.equals(e2), and at most one null element 

� Access via Iterators � Examples 

¿The set of uppercase letters ‘A’ through ‘Z’ ¿The set of nonnegative integers { 0, 1, 2, … } ¿The empty set {}  15 

Fall 2007 

versus List

Collection but simply enforces “no duplicates” 

such 

The set of nonnegative integers 

� Lists are sequential structures � Duplicates allowed 

¿More formally, lists typically allow pairs of elements e1 and e2 such that e1.equals(e2), and they typically allow multiple null elements ¿It is not inconceivable that someone might wish to implement a list that prohibits duplicates, by throwing runtime exceptions when the user attempts to insert them, but we expect this usage to be rare 

�  Implements get and remove methods using integer index

CSD Univ. of Crete 

ArrayList versus 

� ArrayList is a wrapper around an array (resizes when it gets full) ¿Implements all optional list operations, and permits all elements, including null ¿This class provides methods to manipulate the size of the array that is used to store the list 

�  Insertion to the front or middle is expensive (O(n)) 

� Provides fast iterator and get(int) methods 

�

�

�

� 

16 

Fall 2007 

versus LinkedList 

manipulate the size of the array 

� LinkedList is a classic doubly linked list ¿Implements all optional list operations, and permits all elements, including null ¿Provides uniformly named methods to get, remove and insert an element at the beginning and end of the list (i.e., they can be used as a stack, queue, or double­ended queue (deque)) 

� Constant time insertion and removal (O(1)) anywhere in the list 

� Slower iterator � get(int) very slow 

¿implemented by iterating

CSD Univ. of Crete 

ArrayList versus 

� ArrayList implementation using simple, growing, possibly shrinking, arrays 

17 

Fall 2007 

versus LinkedList

� LinkedList implementation list head 

prev 

tail

CSD Univ. of Crete 

Trees and � Trees provide a two dimensional organization of data ¿Binary search trees (BST) are binary trees that impose an ordering on the elements 

� TreeMap is a red­black tree implementation of the Map interface ¿a semi­balanced BST ¿the keys are kept in a TreeSet

� TreeMap underlies TreeSet as well � Fast iteration through values 

¿TreeMap keys are stored ac­ cording to the ordering of keys e.g., we would access the names of a TreeMap in alphabetical order 

� get/put operations are slower (log(n) + rebalancing cost) but faster than ArrayList  18 

Fall 2007 

and Hashes 

as well 

cording to the ordering of keys e.g., 

but faster 

� Hashing is the process of transfor­ ming a key into an array index ¿h:key->hashvalue->index

� HashMap is a hash table­based implementation of the Map interface ¿uses a table containing a singly­ linked list of elements whose key hash to the index of that particular location 

� HashMap underlies HashSet as well 

� Constant time get/put (O(1))) ¿hashing is very fast if the load factor is not close to 100% ¿resize hash table when the load factor gets too large 

�  Iteration through values is slow

CSD Univ. of Crete 

Trees and 

� TreeSet implements Set as a Binary Search Tree 

M 

F  S 

C  I  P  V 

A ... Z 

N ... Z A ... L 

A ... E  G ... L  N ... R  T ... Z 

19 

Fall 2007 

and Hashes

� HashSet  implements Set as a hash table 

“Vassilis” 

Hash Function 

Danger Keep Out 

126 “Vassilis” 

122    123    124    125    126    127 

$ 

buckets

CSD Univ. of Crete 

Recall Hash Values and Hash Tables 

� An algorithm for converting a key to an hash value which is used as an index into a hash table array 

m­ 1 . . . 3 2 1 0 

hash table array 

hash

 value

 

1 0 

n 

Ran

ge of k

ey value

s 

… 

… 

7 6 5 4 3 2 1 0 

table 

hash

 value

 

20 

Fall 2007 

Recall Hash Values and Hash Tables 

null 

null 

null 

null  Obj5 key=1 

obj1 key=15 

Obj4 key=2 

Obj2 key=28 

7 6 5 4 3 2 1 0 

table 

Obj3 key=4 

buckets

CSD Univ. of Crete 

The Collection 

Found in the java.util java.util package 

Optional methods throw UnsupportedOperation UnsupportedOperation Exception Exception  if the implementing class does not support the operation 

Bulk operations perform some operation on an entire Collection in a single shot The toArray toArraymethods allow the contents of a Collection to be translated into an array 

// Basic Operations size size():int; isEmpty isEmpty():boolean; contains contains(Object):boolean; add add(Object):boolean; remove remove(Object):boolean; iterator iterator():Iterator;

// Bulk Operations containsAll containsAll addAll addAll(Collection):boolean; // Optional removeAll removeAll retainAll retainAll clear clear():void;

// Array Operations toArray toArray():Object[]; toArray toArray(Object[]):Object[];  21 

Fall 2007 

Collection Interface 

// Basic Operations ():int;

():boolean; (Object):boolean;

(Object):boolean; // Optional (Object):boolean; // Optional

():Iterator;

// Bulk Operations containsAll containsAll(Collection):boolean;

(Collection):boolean; // Optional removeAll removeAll(Collection):boolean;// Optional retainAll retainAll(Collecton):boolean; // Optional

():void; // Optional

// Array Operations ():Object[]; (Object[]):Object[];

CSD Univ. of Crete 

The Collection

boolean add(Object o): Ensures that this collection contains the specified element 

boolean addAll(Collection c): specified collection to this collection 

void clear(): Removes all of the elements from this collection boolean contains(Object o): Returns true if this collection contains 

the specified element boolean containsAll(Collection 

contains all of the elements in the specified collection boolean equals(Object o): Compares the specified object with this 

collection for equality int hashCode(): Returns the hash code value for this collection boolean isEmpty(): Returns true if this collection contains no elements. 22 

Fall 2007 

Collection Interface 

Ensures that this collection contains the 

c): Adds all of the elements in the specified collection to this collection 

Removes all of the elements from this collection Returns true if this collection contains 

(Collection c): Returns true if this collection contains all of the elements in the specified collection 

Compares the specified object with this 

Returns the hash code value for this collection Returns true if this collection contains no elements.

CSD Univ. of Crete 

The Collection Iterator iterator(): Returns an iterator over the elements in this 

collection boolean remove(Object o): Removes a single instance of the 

specified element from this collection, if it is present boolean removeAll(Collection 

elements that are also contained in the specified collection boolean retainAll(Collection 

this collection that are contained in the specified collection int size(): Returns the number of elements in this collection Object[ ] toArray(): Returns an array containing all of the elements 

in this collection Object[ ] toArray(Object[ ] a): 

the elements in this collection whose runtime type is that of the specified array 

l  Examples: `Object[ ] a= c.toArray( ); String[ ] a= (String[ ]) c.toArray(new String[0]);  23 

Fall 2007 

Collection Interface Returns an iterator over the elements in this 

Removes a single instance of the specified element from this collection, if it is present 

c): Removes all this collection's elements that are also contained in the specified collection 

c): Retains only the elements in this collection that are contained in the specified collection 

Returns the number of elements in this collection Returns an array containing all of the elements 

a): Returns an array containing all of the elements in this collection whose runtime type is that of the specified 

String[ ] a= (String[ ]) c.toArray(new String[0]);

CSD Univ. of Crete 

Creating and Using a 

� Collection is actually an interface ¿Each kind of Collection has one or more implementations ¿You can create new kinds of Collections ¿When you implement an interface, you supply all the required methods 

� All Collection implementations should have two constructors ¿A no­argument constructor to create an empty ¿A constructor with another Collection

� All the standard implementations obey this rule, but If you implement your own Collection type, this rule cannot be enforced, because an Interface Interface cannot specify constructors 

� Note that most methods e.g. boolean containsAll(Collection are defined for any type of Collection Collection as an argument ¿This makes it very easy to work with  24 

Fall 2007 

Creating and Using a Collection 

one or more implementations new kinds of Collections 

When you implement an interface, you supply all the required methods implementations should have two constructors: 

argument constructor to create an empty Collection Collection as argument 

All the standard implementations obey this rule, but If you implement your type, this rule cannot be enforced, because an 

cannot specify constructors boolean containsAll(Collection c);

Collection, and take any type of 

This makes it very easy to work with different types of Collections

CSD Univ. of Crete 

The Set

�  A Set Set is a Collection Collection  that cannot contain duplicate elements ¿ ¿ Set Set models the mathematical set 

�  The Set Set interface extends Collection Collection other than those inherited from Collection Collection

¿  It adds the restriction that duplicate elements are prohibited ¿ Two Set Set objects are equal if they contain the same elements 

�  The bulk operations perform standard set Suppose s1 and s2 are Set Sets ¿ s1.containsAll containsAll(s2): Returns ¿ s1.addAll addAll(s2): Transforms (The union of two sets is the set containing all the elements contained in either set) 

¿ s1.retainAll retainAll(s2): Transforms and s2 (The intersection of two sets is the set containing only the elements that are common in both sets) 

25 

Fall 2007 

Interface 

that cannot contain duplicate elements set abstraction 

Collection Collection and contains no methods Collection Collection 

It adds the restriction that duplicate elements are prohibited objects are equal if they contain the same elements 

perform standard set­algebraic operations: 

Returns true if s2 is a subset of s1 Transforms s1 into the union of s1 and s2 

(The union of two sets is the set containing all the elements 

Transforms s1 into the intersection of s1 (The intersection of two sets is the set containing only the 

elements that are common in both sets)

CSD Univ. of Crete 

Set Operations 

26 

Fall 2007 

Set Operations

CSD Univ. of Crete 

�  A List List is an ordered Collection Collection ¿  In a sequence every object (except the first and last) has a predeces sor and a successor, while occupies a unique position in the sequence 

¿ Lists may contain duplicate elements �  Inherits operations from Collection Collection

¿ ¿ add add(Object) //Append Object to receiver (add to the end of the sequence)

¿ ¿ contains contains(Object) // Returns TRUE if the receiver contains the Object

¿ ¿ remove remove(Object) //Remove the Object (adjust rest of the list)

�  The List List interface includes additional operations for: ¿ Positional Access ¿ Search ¿ List Iteration ¿ Range­view 

�  Think of the Vector Vector class 

The List 

27 

Fall 2007 

Collection Collection (sometimes called a sequence) In a sequence every object (except the first and last) has a predeces­ sor and a successor, while occupies a unique position in the sequence Lists may contain duplicate elements 

Collection Collection  as: (Object) //Append Object to receiver (add to the

(Object) // Returns TRUE if the receiver

(Object) //Remove the first occurrence of Object (adjust rest of the list) 

interface includes additional operations for: 

List  Interface

CSD Univ. of Crete 

// Positional Access //Returns a copy of the Object located at the index Object get get(int); //Overwrite contents of list at position of index with Object Object set set(int,Object); //Insert Object at indicated index (adjust the rest list) void add add(int, Object); //Remove Object at indicated index (adjust the rest list) Object remove remove(int index); boolean addAll addAll(int, Collection);// Optional // Search //Returns the index of the first occurrence of Object //returns length of list if the Object is not present int indexOf indexOf(Object); int lastIndexOf lastIndexOf(Object); // Iteration //Returns a ListIterator to traverse the referenced container ListIterator listIterator listIterator(); ListIterator listIterator listIterator(int); // Range-view List subList subList(int, int):List; 

The  List 

28 

Fall 2007 

//Returns a copy of the Object located at the index

//Overwrite contents of list at position of index with Object // Optional

//Insert Object at indicated index (adjust the rest list) // Optional

//Remove Object at indicated index (adjust the rest list) // Optional

(int, Collection);// Optional

//Returns the index of the first occurrence of Object – //returns length of list if the Object is not present

//Returns a ListIterator to traverse the referenced container

(int);

List Interface

CSD Univ. of Crete 

The  Map

� Replaces java.util.Dictionary ¿An object that maps keys to values ¿Each key can have at most one value 

� Ordering may be provided by implementation class, but not guaranteed � Methods 

¿Set keySet(); ¿Collection values(); ¿Set entrySet(); // returns a set view of the mappings

� Map.Entry ¿Object that contains a key­value pair

•getKey(), getValue() � Thread safety 

¿The collections returned are backed by the map •When the map changes, the collection changes 

¿Behavior can easily become undefined •Be very careful and read the docs closely  29 

Fall 2007 

Interface 

java.util.Dictionary interface An object that maps keys to values Each key can have at most one value 

Ordering may be provided by implementation class, but not guaranteed 

// returns a set view of the mappings 

value pair 

The collections returned are backed by the map When the map changes, the collection changes 

Behavior can easily become undefined Be very careful and read the docs closely

CSD Univ. of Crete 

The  Map // Basic Operations Object put put(Object, Object); //If the map already contains a // given key it replaces the value associated with that key Object get get(Object key); // returns the corresponding value Object remove remove(Object key); // removes the pair with that key boolean containsKey containsKey(Object); boolean containsValue containsValue(Object); int size size(); boolean isEmpty isEmpty();

// Bulk Operations void putAll putAll(Map t); //copies one Map into another void clear clear();

// Collection Views Set keySet keySet(); Collection values values(); Set entrySet entrySet();//returns a set of Map.Entry (key  30 

Fall 2007 

Interface 

(Object, Object); //If the map already contains a // given key it replaces the value associated with that key

(Object key); // returns the corresponding value (Object key); // removes the pair with that key

(Object);

(Map t); //copies one Map into another

();//returns a set of Map.Entry (key-value) pairs

CSD Univ. of Crete 

The Map.Entry

� This is a small interface for working with the Collection returned by entrySet entrySet( )

� Can get elements only from the Iterator during the iteration 

public interface Entry { Object getKey getKey(); Object getValue getValue(); Object setValue setValue(Object value);

} 

31 

Fall 2007 

Map.Entry Interface 

This is a small interface for working with the Collection returned by 

Iterator, and they are only valid 

public interface Entry { ();

(); (Object value);

CSD Univ. of Crete 

Map Operations 

32 

Fall 2007 

Map Operations

CSD Univ. of Crete 

Iterating Collections 

int size = collection.size(); for (int counter=0; counter<size; counter++) { Object value = collection.get(counter); System.out.println(o);

}

for (Object o: collection) { System.out.println(o);

} 

33 

Fall 2007 

Iterating Collections 

int size = collection.size(); for (int counter=0; counter<size; counter++) { Object value = collection.get(counter); System.out.println(o);

for (Object o: collection) { System.out.println(o);

CSD Univ. of Crete 

The  Iterator

�  Created by Collection.iterator() ¿  Improved method names ¿ Allows a remove() operation on the current item 

�  An object implementing the Iterator Iterator elements, one at a time ¿ A call to the method iterator( ) iterator( ) sets it to read the first element in the list. 

¿ Successive calls to the next next() of the series 

¿ See if there are any more elements in the sequence with a call to hasNext( ) hasNext( )

¿ The remove remove()method removes from the underlying the last element that was returned by 

�  Works for non­list collections �  Allows the iterators to have state 

34 

Fall 2007 

Iterator  Interface 

Collection.iterator(),  similar to Enumeration 

operation on the current item Iterator Iterator interface generates a series of 

iterator( ) iterator( ) returns an iterator object and sets it to read the first element in the list. 

() method return successive elements 

See if there are any more elements in the sequence with a call to 

method removes from the underlying Collection Collection the last element that was returned by next next()

boolean hasNext hasNext(); Object next next(); void remove remove();

CSD Univ. of Crete 

Using Iterators 

� Replace 

� with: Iterator i = collection.iterator(); while(i.hasNext()) { Object value = i.next(); .... }

int counter; int size = collection.size(); for (counter=0; counter<size; counter++) { Object value = collection.get(counter);

... } 

35 

Fall 2007 

Using Iterators 

Iterator i = collection.iterator(); while(i.hasNext()) { Object value = i.next();

int size = collection.size(); for (counter=0; counter<size; counter++) { Object value = collection.get(counter);

CSD Univ. of Crete 

Using Iterators � With an iterator one can write generic methods to handle any collection public class Printer {

static void printAll (Iterator Iterator

while (e.hasNext hasNext( ) )

System.out.print(e.next next( )+“ ”);

System.out.println( );

}

public class FrogPond {

public static void main(String [ ] args) {

ArrayList v = new ArrayList( );

for (int i = 0; i < args[0]; i++)

v.add(new Frog(i));

Printer.printAll(v.iterator iterator

}

}  36 

Fall 2007 

Using Iterators With an iterator one can write generic methods to handle any collection 

Iterator Iterator e) {

( )+“ ”);

public static void main(String [ ] args)

ArrayList v = new ArrayList( );

for (int i = 0; i < args[0]; i++)

iterator iterator( )); 

Obtain an iterator from the ArrayList and pass it to the Printer 

The method receives an iterator object as its argument with no distinction made about what collection produced it

CSD Univ. of Crete 

Removing items via an Iterator 

� Iterators can also be used to modify a 

Iterator i = collection.

while ( i.hasNext hasNext

{

if (object.equals(i.

{

i.remove remove() ;

}

} 

37 

Fall 2007 

Removing items via an Iterator 

s can also be used to modify a Collection: 

Iterator i = collection.iterator iterator();

hasNext hasNext() )

if (object.equals(i.next next()) )

CSD Univ. of Crete 

The  ListIterator

� A ListIterator ListIterator is produced by any List List  interface ¿interface ListIterator ListIterator extends

•Created by List.listIterator() List.listIterator()

�  It has an additional constructor that takes an index value as a parameter and returns an iterator set to begin visiting the element at this location on the first call to next next( ) ¿ ¿ListIterator(int); ListIterator(int);

� Adds methods to ¿traverse the List List in either direction ¿modify the List List during iteration 

� A client program can maintain multiple iterators to facilitate searches and swaps inside of a list 

38 

Fall 2007 

ListIterator  Interface 

is produced by any Collection implementing the 

extends Iterator Iterator List.listIterator() List.listIterator() 

that takes an index value as a parameter and returns an iterator set to begin visiting the element at this location on 

either direction 

A client program can maintain multiple iterators to facilitate searches and

CSD Univ. of Crete 

The  ListIterator

�  In addition to methods next next(), hasNext hasNext inherited from interface Iterator Iterator, following additional methods 

public int nextIndex nextIndex( ); //returns index of the element that would be called by next( )

public int previousIndex previousIndex( ); //returns index of the element that would be called by previous( )

public boolean hasPrevious hasPrevious( );

public Object previous previous( ) throws NoSuchElementException;

public void add add(Object o) throws UnsupportedOperationException, ClassCastException, IllegalArgumentException; //inserts the object into the list immediately before the current index position

public void set set(Object o) throws UnsupportedOperationException, ClassCastException, IllegalArgumentException; //overwrites the last element returned by next or previous with the specified element  39 

Fall 2007 

ListIterator  Interface 

hasNext hasNext(), and remove remove() that are , ListIterator ListIterator provides the 

( ); //returns index of the element that

( ); //returns index of the element that would be called by previous( )

( ) throws NoSuchElementException;

(Object o) throws UnsupportedOperationException, ClassCastException, IllegalArgumentException; //inserts the object into the list immediately before the current index position

(Object o) throws UnsupportedOperationException, ClassCastException, IllegalArgumentException; //overwrites the last element returned by next or previous with the specified element

CSD Univ. of Crete 

Using a ListIterator 

List list = new LinkedList( );

//fill the list with objects …

//Produces a ListIterator set to visit the element //at index 5

ListIterator itr = list.getListIterator(5) getListIterator(5)

while (i.hasNext hasNext() ) {

if ( object.compareTo(i.

break;

}

}

//A ListIterator allows items to be inserted in a List

i.add add(object); 

40 

Fall 2007 

Using a ListIterator 

List list = new LinkedList( );

//fill the list with objects …

//Produces a ListIterator set to visit the element

getListIterator(5) getListIterator(5);

if ( object.compareTo(i.next next()) < 0 ) {

//A ListIterator allows items to be inserted in a List

CSD Univ. of Crete 

The Abstract Class AbstractCollection

�  Implements the following methods: ¿ boolean containsAll(Collection c)

¿ boolean contains(Object o)

¿ boolean removeAll(Collection c)

¿ boolean remove(Object o)

¿ boolean retainAll(Collection c)

�  The implementation of the methods iterator are under the responsibility of the subclasses: ¿ boolean add(Object obj);

¿ Iterator iterator(); 

41 

Fall 2007 

AbstractCollection 

Implements the following methods: (Collection c)

(Object o)

(Collection c)

(Object o)

(Collection c) 

The implementation of the methods add  and are under the responsibility of the 

(Object obj);

CSD Univ. of Crete 

AbstractCollection

public boolean retainAll(Collection c){

boolean modified = false;

Iterator e = iterator();

while (e.hasNext()) {

if(!c.contains(e.next())) {

e.remove();

modified = true;

}

}

return modified;

} 

42 

Fall 2007 

AbstractCollection

if(!c.contains(e.next())) {

CSD Univ. of Crete

The Abstract Class 

� The AbstractSet class is a convenience class that extends AbstractCollection and implements Set

� Provides concrete implementations for the equals and hashCodemethods ¿The hash code of a set is the sum of the hash code of all the elements in the set 

� Since the size and iterator methods are not implemented, AbstractSet is an abstract class ¿The implementation of these methods is under the responsibility of the subclasses  43 

Fall 2007 

The Abstract Class AbstractSet 

Provides concrete implementations for methods 

The hash code of a set is the sum of the hash code of all the elements in 

methods is under the responsibility

CSD Univ. of Crete 

The SortedSet 

} 44 

Fall 2007 

SortedSet Interface 

all based on the (sorted) order of  the elements

CSD Univ. of Crete 

The Abstract Class 

� The AbstractList class is a convenience class that extends AbstractCollection and implements List

� Provides concrete implementations for the indexOf  and lastIndexOf  methods 

� Since the add  and list listiterator methods are not implemented, AbstractList is an abstract class ¿The implementation of these methods is under the responsibility of the subclasses 

45 

Fall 2007 

The Abstract Class AbstractList 

concrete implementations 

iterator 

abstract class 

responsibility of the subclasses

CSD Univ. of Crete 

Implementation Classes 

Interface  Implementation 

Hash table 

Resizable array 

Set HashSet

List ArrayList

Map HashMap

�When writing programs think about interfaces and not implementations ¿This way the program does not become dependent on any added methods in a given implementation, leaving the programmer with the freedom to change implementations 

�An implementation class may elect not to support a particular method of the interface � �UnsupportedOperationException UnsupportedOperationException exception  46 

Fall 2007 

Implementation Classes 

Implementation  Historical 

Tree (sorted) 

Linked list 

TreeSet

LinkedList Vector Stack

TreeMap HashTable Properties 

think about interfaces and not implementations This way the program does not become dependent on any added 

methods in a given implementation, leaving the programmer with the freedom to change implementations 

An implementation class may elect not to support a particular method of 

UnsupportedOperationException UnsupportedOperationException is a runtime (unchecked)

CSD Univ. of Crete 

Set Implementations 

� � HashSet HashSet

¿a Set Set backed by a hash table 

� � TreeSet TreeSet

¿A semi­balanced binary tree implementation ¿Imposes an ordering on its elements 

47 

Fall 2007 

Implementations

CSD Univ. of Crete 

List Implementations 

� � ArrayList ArrayList ¿a resizable­array implementation like Vector Vector

• unsynchronized, and without “legacy” methods 

� � LinkedList LinkedList ¿a doubly­linked list implementation ¿May provide better performance than ArrayList ArrayList

• if elements frequently inserted/deleted within the List List

¿For queues and double­ended queues (deques) 

� � Vector Vector ¿a synchronized resizable­array implementation of a List with additional "legacy" methods  48 

Fall 2007 

Implementations 

implementation 

implementation 

List List

CSD Univ. of Crete 

The LinkedList

� The LinkedList LinkedList class offers a few additional methods for directly manipulating the ends of the list: 

� These methods make it natural to implement other simpler data structures, like Stacks and Queues 

void addFirst addFirst(Object)

void addLast addLast(Object);

Object getFirst getFirst();

Object getLast getLast();

Object removeFirst removeFirst();

Object removeLast removeLast(); 

49 

Fall 2007 

LinkedList Class 

class offers a few additional methods for directly 

These methods make it natural to implement other simpler data

CSD Univ. of Crete 

Using LinkedList

� A few things to be aware of: ¿it is really bad to use the positional indexing features copiously of LinkedList LinkedList if you care at all about performance

•This is because the LinkedList LinkedList traverse the chain from the beginning 

¿Elements can be changed both with the objects

•That latter is often more convenient ¿You can create havoc by creating several iterators that you use to mutate the List List

•There is some protection built iterator that will actually mutate the list structure 

50 

Fall 2007 

LinkedLists 

it is really bad to use the positional indexing features copiously of if you care at all about performance 

LinkedList LinkedList has no memory and must always traverse the chain from the beginning 

Elements can be changed both with the List List and ListIterator ListIterator 

That latter is often more convenient You can create havoc by creating several iterators that you use to 

There is some protection built­in, but best is to have only one iterator that will actually mutate the list structure

CSD Univ. of Crete 

The ArrayList

� Additional methods for managing size of underlying array ¿void ensureCapacity ensureCapacity(int minCapacity) capacity of this ArrayList ArrayList instance, if necessary, to ensure that it can hold at least the number of elements specified by the minimum capacity argument ¿void trimToSize trimToSize(): Trims the capacity of this instance to be the list's current size 

� methods size(), isEmpty(), get() listIterator() all run in constant time 

� Adding n elements take O[n] time � Can explicitly grow capacity in anticipation of adding many elements � Note: legacy Vector class almost identical 

¿Main differences are naming and synchronization 

51 

Fall 2007 

ArrayList Class 

Additional methods for managing size of underlying array (int minCapacity): Increases the instance, if necessary, to ensure that it 

can hold at least the number of elements specified by the minimum 

: Trims the capacity of this ArrayList ArrayList instance to be the list's current size 

get(), set(), iterator() and all run in constant time 

Can explicitly grow capacity in anticipation of adding many elements Note: legacy Vector class almost identical 

Main differences are naming and synchronization

CSD Univ. of Crete 

Map Implementations 

� � HashMap HashMap

¿A hash table implementation of Map

¿Like Hashtable, but supports null keys & values 

� � TreeMap TreeMap

¿A semi­balanced binary tree implementation ¿Imposes an ordering on its elements 

� � Hashtable Hashtable

¿Synchronized hash table implementation of Map interface, with additional "legacy" methods 

� Load Factor & Initial Size 

52 

Fall 2007 

Implementations 

interface, "legacy" methods 

Load Factor & Initial Size ¿Number of entries in the hashtable exceeds the product of the load factor and the current capacity ¿Will rehash if load factor exceeds specified (time consuming)

CSD Univ. of Crete 

load factor 

� The load factor is a measure of how full the hash table is allowed to get before its capacity is automatically increased. When the number of entries in the hashtable exceeds the product of the load factor and the current capacity, the capacity is increased by calling the rehash method. 

� Generally, the default load factor (.75) offers a good tradeoff between time and space costs. Higher values decrease the space overhead but increase the time cost to look up an entry (which is reflected in most Hashtable operations, including get and put). 

� The initial capacity controls a tradeoff between wasted space and the need for rehash operations, which are time­ ever occur if the initial capacity is greater than the maximum number of entries the Hashtable will contain divided by its load factor. However, setting the initial capacity too high can waste space. 

�  If many entries are to be made into a Hashtable, creating it with a sufficiently large capacity may allow the entries to be inserted more efficiently than letting it perform automatic rehashing as needed to grow the table. 

53 

Fall 2007 

load factor 

is a measure of how full the hash table is allowed to get before its capacity is automatically increased. When the number of entries in the hashtable exceeds the product of the load factor and the current capacity, the capacity is increased by calling the rehash method. Generally, the default load factor (.75) offers a good tradeoff between time and space costs. Higher values decrease the space overhead but increase the time cost to look up an entry (which is reflected in most Hashtable 

The initial capacity controls a tradeoff between wasted space and the need ­consuming. No rehash operations will 

occur if the initial capacity is greater than the maximum number of entries the Hashtable will contain divided by its load factor. However, setting the initial capacity too high can waste space. If many entries are to be made into a Hashtable, creating it with a sufficiently large capacity may allow the entries to be inserted more efficiently than letting it perform automatic rehashing as needed to grow the table.

CSD Univ. of Crete 

The Hashtable

� Like a HashMap HashMap but older version � Constructors: Hashtable Hashtable() //Constructs a new, empty hashtable with a default initial capacity (11) and load factor, which is 0.75.

Hashtable Hashtable(int initialCapacity) //Constructs a new, empty hashtable with the specified initial capacity and default load factor, which is 0.75

Hashtable Hashtable(int initialCapacity, float loadFactor) //Constructs a new, empty hashtable with the specified initial capacity and the specified load factor

Hashtable Hashtable(Map t) //Constructs a new hashtable with the same mappings as the given Map 

54 

Fall 2007 

Hashtable Class 

() //Constructs a new, empty hashtable with a default initial capacity (11) and load factor, which is

(int initialCapacity) //Constructs a new, empty hashtable with the specified initial capacity and default load factor, which is 0.75

(int initialCapacity, float loadFactor) //Constructs a new, empty hashtable with the specified initial capacity and the specified load factor

(Map t) //Constructs a new hashtable with the same mappings as the given Map

CSD Univ. of Crete 

Other J2SE Implementations � Legacy (since 1.0) 

¿java.util.Vector ¿java.util.Stack ¿java.util.Hashtable ¿java.util.Properties

� J2SE 1.2 ¿java.util.WeakHashMap

� J2SE 1.4 ¿java.util.LinkedHashSet ¿java.util.LinkedHashMap ¿java.util.IdentityHashMap

� J2SE 1.5 ¿java.util.EnumSet ¿java.util.EnumMap ¿java.util.PriorityQueue ¿java.util.concurrent.*  55 

Fall 2007 

Other J2SE Implementations 

java.util.LinkedHashSet java.util.LinkedHashMap java.util.IdentityHashMap

java.util.PriorityQueue

CSD Univ. of Crete 

Example: Instantiating and Using Sets 

public class TestCollection { public static void main(String args[]) { // Create an empty bag Collection set = new HashSet HashSet // Populate the set set.add add(new Integer(47)); set.add add(new Double(3.14)); set.add add(new Character('h')); // iterate through the set of keys Iterator iter =  set.iterator iterator while (iter.hasnext hasnext()) { //Assume items are printed in same order //they were put in System.out.println(iter.next next } // end while

} // end main } // end TestCollection 

56 

Fall 2007 

Instantiating and Using Sets 

public class TestCollection { public static void main(String args[]) {

HashSet HashSet();

(new Integer(47)); (new Double(3.14)); (new Character('h'));

// iterate through the set of keys iterator iterator(); ()) {

//Assume items are printed in same order

next next());

47

3.14

h

CSD Univ. of Crete 

Example: Instantiating //instantiate a concrete map Map favoriteColors = new HashMap HashMap //Adding an association (key-value pair) favoriteColors.put put("Juliet", Color.pink); //Changing an existing association favoriteColors.put put("Juliet",Color.red); //Getting the value associated with a key Color julietsFavoriteColor = favoriteColors. //Removing a key and its associated value favoriteColors.remove remove("Juliet"); //Printing key/value Pairs Set keySet = favoriteColors.keySet keySet // iterate through the set of keys Iterator iter = keySet.iterator iterator while (iter.hasNext hasNext()) { Object key = iter.next next(); Object value = favoriteColors. System.out.println(key + "->" + value); }  57 

Fall 2007 

Instantiating and Using Maps 

HashMap HashMap(); value pair)

("Juliet", Color.pink); //Changing an existing association

("Juliet",Color.red); //Getting the value associated with a key Color julietsFavoriteColor = favoriteColors.get get("Juliet"); //Removing a key and its associated value

("Juliet");

keySet keySet(); //get the set of keys // iterate through the set of keys

iterator iterator();

Object value = favoriteColors.get get(key); >" + value); }

CSD Univ. of Crete 

Hash based Implementation 

� Hash based implementation stores set elements hash function 

� A suitable hash function is defined in class hashCode) and inherited by all subclasses 

�  If a class overrides the equalsmethod defined also necessary to override the hashCode and HashMap work correctly 

58 

Fall 2007 

Hash based Implementation 

implementation stores set elements (map keys) using a 

is defined in class Object (method subclasses 

method defined in class Object it is hashCodemethod to make HashSet

CSD Univ. of Crete 

Tree based Implementation 

� TreeSet

¿iteration gives elements in sorted order ¿To use a TreeSet,

• either your objects must implement interface • or you must provide a Comparator

� TreeMap

¿the keys are kept in a TreeSet ¿To use a TreeMap

• either your keys must implement interface • or you must provide a Comparator • there is no requirement for the values 

59 

Fall 2007 

Tree based Implementation 

iteration gives elements in sorted order 

either your objects must implement interface Comparable Comparator object 

TreeSet 

either your keys must implement interface Comparable Comparator object for the keys 

there is no requirement for the values

CSD Univ. of Crete 

What About User Objects? 

� The Collections framework will work with any Java class � You need to be sure you have defined 

¿ ¿equals equals()

¿ ¿hashCode hashCode()

¿ ¿compareTo compareTo() or compare compare()

� Don’t use mutable objects for keys in a � The Map hashCode hashCode() returns distinct integers for distinct objects 

¿If two objects are equal according to the the hashCode hashCode()method on each of the two objects must produce the same integer result ¿When hashCode hashCode() is invoked on the same object more than once, it must return the same integer, provided no information used in equals comparisons has been modified ¿It is not required that if two objects are unequal according to equals equals() that hashCode hashCode()must return distinct integer values 

60 

Fall 2007 

What About User Objects? 

The Collections framework will work with any Java class You need to be sure you have defined 

Don’t use mutable objects for keys in a Map Map returns distinct integers for distinct objects 

If two objects are equal according to the equals equals()method, then method on each of the two objects must 

produce the same integer result is invoked on the same object more than 

once, it must return the same integer, provided no information used in equals comparisons has been modified 

required that if two objects are unequal according to must return distinct integer values

CSD Univ. of Crete 

Sorting and Comparing � Comparable interface 

¿Must be implemented by all elements in ¿Must be implemented by all keys in ¿Method: int compareTo(Object o) ¿Defines "natural order" for that object class 

� Comparator interface ¿Defines a function that compares two objects ¿Can design custom ordering scheme ¿Method: int compare(Object o1, Object o2)

� Total vs. Partial Ordering ¿Technical, changes behavior per object class 

61 

Fall 2007 

Sorting and Comparing 

Must be implemented by all elements in SortedSet Must be implemented by all keys in SortedMap

int compareTo(Object o) Defines "natural order" for that object class 

Defines a function that compares two objects Can design custom ordering scheme 

int compare(Object o1, Object o2) 

Technical, changes behavior per object class

CSD Univ. of Crete 

Return Abstract Collections 

� OO is based on the notion of encapsulation ¿hiding implementation details behind interfaces 

� Therefore: Return the most abstract interface that can possibly work ¿Return a List List instead of an ArrayList ArrayList

¿Return a Collection Collection instead of a ¿Return an Iterator Iterator instead of a 

62 

Fall 2007 

Return Abstract Collections 

OO is based on the notion of encapsulation hiding implementation details behind interfaces 

Therefore: Return the most abstract interface that can possibly work ArrayList ArrayList 

instead of a List List instead of a Collection Collection

CSD Univ. of Crete 

The  Collections

�  This class consists exclusively of static methods that operate on or return Collections and Maps ¿ Polymorphic algorithms that operate on collections 

¿ Wrappers which return a new collection backed by a specified collection 

¿ Plus a few other odds and ends for creating synchronized collection classes, and for creating read­only collection classes 

�  Most of the algorithms operate on List List objects, but a couple of them (max max and min min) operate on arbitrary Collection Collection objects  63 

Fall 2007 

Collections Utility Class 

collection backed by a specified 

Plus a few other odds and ends 

objects, but a couple of them ) operate on arbitrary 

Collections 

+binarySearch(list: List, key: Object) : int + binarySearch(list: List, key: Object, c: Comparator) : int + copy(src: List, des: List) : void + enumeration(c: final Collection) : Enumeration + fill(list: List, o: Object) : void +max(c: Collection) : Object +max(c: Collection, c: Comparator) : Object +min(c: Collection) : Object +min(c: Collection, c: Comparator) : Object + nCopies(n: int, o: Object) : List + reverse(list: List) : void + reverseOrder() : Comparator + shuffle(list: List) : void +shuffle(list: List, rnd: Random) : void + singleton(o: Object) : Set + singletonList(o: Object) : List + singletonMap(key: Object, value: Object) : Map + sort(list: List) : void + sort(list: List, c: Comparator) : void + synchronizedCollection(c: Collection) : Collection + synchronizedList(list: List) : List + synchronizedMap(m: Map) : Map + synchronizedSet(s: Set) : Set + synchronizedSortedMap(s: SortedMap) : SortedMap + synchronizedSortedSet(s: SortedSet) : SortedSet + unmodifiedCollection(c: Collection) : Collection + unmodifiedList(list: List) : List + unmodifiedMap(m: Map) : Map + unmodifiedSet(s: Set) : Set + unmodifiedSortedMap(s: SortedMap) : SortedMap + unmodifiedSortedSet(s: SortedSet) : SortedSet

CSD Univ. of Crete 

Static Method Collections.sort()

� The sort operation uses a slightly optimized merge sort algorithm ¿Fast: This algorithm is guaranteed to run in n log(n) time, and runs substantially faster on nearly sorted lists ¿Stable: That is to say, it doesn't reorder equal elements 

� SortedSet, SortedMap interfaces ¿Collections that keep their elements sorted ¿Iterators are guaranteed to traverse in sorted order (only SortedSet) 

� Ordered Collection Implementations ¿TreeSet, TreeMap  64 

Fall 2007 

Collections.sort() 

time, and runs substantially faster 

interfaces 

Ordered Collection Implementations 

public static void sort sort(List list, Comparator c){

Object a[] = list.toArray();

Arrays.sort(a, c);

ListIterator i = list.listIterator();

for (int j=0;j<a.length; j++) {

i.next();

i.set(a[j]);

}

}

CSD Univ. of Crete 

Sort  Example 

import java.util.*;

public class SortExample { public static void main( String args[] ) { List l = new ArrayList();

for ( int i = 0; i < args.length; i++ ) l.add( args[ i ] );

Collections.sort( l );

System.out.println( l ); }

} 

65 

Fall 2007 

Example 

public class SortExample { public static void main( String args[] ) { List l = new ArrayList();

for ( int i = 0; i < args.length; i++ ) l.add( args[ i ] );

Collections.sort( l );

System.out.println( l );

CSD Univ. of Crete 

Other Algorithms 

�  Other algorithms provided by the ¿ Singleton

• Collections.singleton(e) containing only the element

• c.removeAll(Collections.singleton(e)); remove all occurrences of e from the Collection 

¿ Shuffling ¿ Data manipulation

• • reverse reverse() • • fill fill() • • copy copy()

¿ Searching ¿ Finding extreme values

• • max max() • • min min()  66 

Fall 2007 

Other Algorithms 

Collections Collections class include 

Collections.singleton(e) returns an immutable set containing only the element e c.removeAll(Collections.singleton(e)); will remove all occurrences of e from the Collection c

CSD Univ. of Crete 

The Arrays

�  It is too bad that arrays are not collections ¿You loose all of the power provided by the collection framework 

� The class Arrays Arrays contains ¿various static methods for manipulating arrays (such as sorting, searching, and comparing arrays, as well as filling array elements) ¿It also contains a method for converting arrays to lists 

� Object­based Array sorting ¿Arrays.sort(Object[])

¿Equivalent methods for all primitive types (e.g., int[]) 

+ asList(a : O bject[]) : List + b inarySearch (a: byte[],key: byte) : in t + b inarySearch (a: char[], key: char) : in t + b inarySearch (a: doub le[], key: doub le) : in t + b inarySearch (a,: floa t[]   key: floa t) : in t + b inarySearch (a: in t[] , key: int) : in t + b i + b inarySearch (a: Ob ject[] , key: O bject) : in t + b inarySearch (a: Ob ject[] , key: O bject, c : Com parator) : in t + b inarySearch (a: short[] , key: short) : in t + equals(a : boolean[], a2 : boolean []) : boolean + equals(a : byte[], + equals(a : char[], a2: char[]) : boolean + equals(a : double[], a2: doub le[]) : boolean + equals(a : float[], a2: float[]) : boolean + equals(a : int[] , a2 : int[]) : boolean + equals(a : long[], a2 : long[]) : boolean + equals(a : Ob jec t[] , a2 : + equals(a : short[] , a2 : short[]) : boolean + fill(a : boolean [], val: boolean ) : void + fill(a : boolean [], from Index: in t, toIndex: in t, va l: boolean ) : void 

Overloaded  fill m ethod  for char, byte, short, in t, long, floa t, doub le, and  O 

+ sort(a : byte[]) : void + sort(a : byte[], from Index: int, toIndex: int) : void 

Overloaded  sort m ethod for char, short, in t, long, floa t, doub le, and Ob ject. 

67 

Fall 2007 

Utility Class A rrays 

asList(a : O bject[]) : List b inarySearch (a: byte[],key: byte) : in t b inarySearch (a: char[], key: char) : in t b inarySearch (a: doub le[], key: doub le) : in t b inarySearch (a,: floa t[]   key: floa t) : in t b inarySearch (a: in t[] , key: int) : in t b inarySearch (a: long[], key: long) : in t b inarySearch (a: Ob ject[] , key: O bject) : in t b inarySearch (a: Ob ject[] , key: O bject, c : Com parator) : in t b inarySearch (a: short[] , key: short) : in t equals(a : boolean[], a2 : boolean []) : boolean equals(a : byte[],  a2 : byte[]) : boolean equals(a : char[], a2: char[]) : boolean equals(a : double[], a2: doub le[]) : boolean equals(a : float[], a2: float[]) : boolean equals(a : int[] , a2 : int[]) : boolean equals(a : long[], a2 : long[]) : boolean equals(a : Ob jec t[] , a2 : Ob ject[]) : boolean equals(a : short[] , a2 : short[]) : boolean fill(a : boolean [], val: boolean ) : void fill(a : boolean [], from Index: in t, toIndex: in t, va l: boolean ) : void 

Overloaded  fill m ethod  for char, byte, short, in t, long, floa t, doub le, and  Ob ject. 

sort(a : byte[]) : void sort(a : byte[], from Index: int, toIndex: int) : void 

Overloaded  sort m ethod for char, short, in t, long, floa t, doub le, and Ob ject.

CSD Univ. of Crete 

Sort  Example 

import java.util.*;

public class SortExample { public static void main( String args[] ) { Arrays.sort sort( args );

List l = Arrays.

System.out.println( l ); }

} 

68 

Fall 2007 

Example 

public class SortExample { public static void main( String args[] ) {

( args );

List l = Arrays.asList asList( args );

System.out.println( l );

CSD Univ. of Crete 

Utility Classes Summary 

� � Collections Collections class static methods: ¿sort(List) ¿binarySearch(List, Object) ¿reverse(List) ¿shuffle(List) ¿fill(List, Object) ¿copy(List dest, List src) ¿min(Collection) ¿max(Collection) ¿synchronizedX, unmodifiableX

� � Arrays Arrays  class static methods that act on Java arrays: ¿sort ¿binarySearch ¿equals ¿fill ¿asList ­ returns an ArrayList composed of this array's contents  69 

Fall 2007 

Utility Classes Summary 

class static methods: 

binarySearch(List, Object)

copy(List dest, List src)

synchronizedX, unmodifiableX  factory methods class static methods that act on Java arrays: 

returns an ArrayList composed of this array's contents

CSD Univ. of Crete 

parenthesis 

� StreamTokenizer takes a stream and a set of tokens and parses them one at a time. The different types of tokens that can be found are numbers, identifiers, quoted strings, and different comment styles. 

� Constants ¿TT_EOF The constant representing end of stream. ¿TT_EOL The constant representing end of line. ¿TT_NUMBER The constant representing a number token. ¿TT_WORD The constant representing a word token. 

� Public methods ¿... ¿ void ordinaryChar(int ch)

• Set the character ch to be regarded as an ordinary character. 

70 

Fall 2007 

parenthesis 

takes a stream and a set of tokens and parses them one at a time. The different types of tokens that can be found are numbers, identifiers, quoted strings, and different comment 

The constant representing end of stream. The constant representing end of line. 

The constant representing a number token. The constant representing a word token. 

Set the character ch to be regarded as an ordinary character.

CSD Univ. of Crete 

Example: Counting UniqueWords 

import java.io.*;

import java.util.*;

public class UniqueWords {

public static void main( String args[] ) {

// Usage check & open file

if ( args.length != 1 ) {

System.err.println( "Usage: java UniqueWords word

System.exit( 1 );

}

StreamTokenizer in = null;

try {

in = new StreamTokenizer( new BufferedReader (

new FileReader ( args[ 0 ] ) ) );

in.ordinaryChar( '.' ); }

catch ( FileNotFoundException e ) {

System.err.println( "UniqueWords: " + e.getMessage() );

System.exit( 1 );}  71 

Fall 2007 

Example: Counting UniqueWords 

public static void main( String args[] ) {

System.err.println( "Usage: java UniqueWords word-file" );

in = new StreamTokenizer( new BufferedReader (

new FileReader ( args[ 0 ] ) ) );

catch ( FileNotFoundException e ) {

System.err.println( "UniqueWords: " + e.getMessage() );

CSD Univ. of Crete 

Example: Counting UniqueWords 

try { Set set = new HashSet HashSet while ( ( in.nextToken() != in.TT_EOF ) ) {

if ( in.ttype == in.TT_WORD ) set.add add( in.sval );

} System.out.println("There are " + set.size() +

" unique words" ); System.out.println( set ); }

catch ( IOException e ) { System.err.println("UniqueWords: " +

e.getMessage()); System.exit( 1 ); }

} }  72 

Fall 2007 

Example: Counting UniqueWords 

HashSet HashSet(); while ( ( in.nextToken() != in.TT_EOF ) ) {

if ( in.ttype == in.TT_WORD ) ( in.sval );

System.out.println("There are " + set.size() + " unique words" );

System.out.println( set );

catch ( IOException e ) { System.err.println("UniqueWords: " +

e.getMessage()); 

Create Empty Set

CSD Univ. of Crete 

You Want Them Sorted? 

try { SortedSet set = new while ( ( in.nextToken() != in.TT_EOF ) ) { if ( in.ttype == in.TT_WORD )

set.add add( in.sval ); }

System.out.println("There are " + set.size() + " unique words" );

System.out.println( set ); }

catch ( IOException e ) { System.err.println("UniqueWords: " +

System.exit( 1 ); }

} }  73 

Fall 2007 

You Want Them Sorted? 

SortedSet set = new TreeSet TreeSet(); while ( ( in.nextToken() != in.TT_EOF ) ) { if ( in.ttype == in.TT_WORD )

( in.sval );

System.out.println("There are " + set.size() + " unique words" );

System.out.println( set );

catch ( IOException e ) { System.err.println("UniqueWords: " +

e.getMessage() );

CSD Univ. of Crete 

Or 

try { Set set = new HashSet HashSet while ( ( in.nextToken() != in.TT_EOF ) ) { if ( in.ttype == in.TT_WORD )

set.add add( in.sval ); }

System.out.println("There are " + set.size() + " unique words" );

System.out.println(new }

catch ( IOException e ) { System.err.println("UniqueWords: " +

e.getMessage() ); System.exit( 1 ); }

} }  74 

Fall 2007 

Or 

HashSet HashSet(); while ( ( in.nextToken() != in.TT_EOF ) ) { if ( in.ttype == in.TT_WORD )

( in.sval );

System.out.println("There are " + set.size() + " unique words" );

System.out.println(new TreeSet TreeSet(set) );

catch ( IOException e ) { System.err.println("UniqueWords: " +

e.getMessage() ); 

Copy Set

CSD Univ. of Crete 

Pretty Output is Good 

try { SortedSet set = new TreeSet TreeSet while ( ( in.nextToken() != in.TT_EOF ) ) { if ( in.ttype == in.TT_WORD )

set.add add( in.sval ); }

System.out.println("There are " + set.size() + " unique words" );

Iterator elements = set.iterator iterator System.out.println(); while ( elements.hasNext hasNext() )

System.out.println( elements. }

catch ( IOException e ) { System.err.println( "UniqueWords: " + e.getMessage() ); System.exit( 1 );

} }

}  75 

Fall 2007 

Pretty Output is Good 

TreeSet TreeSet(); while ( ( in.nextToken() != in.TT_EOF ) ) { if ( in.ttype == in.TT_WORD )

System.out.println("There are " + set.size() + " unique words" );

iterator iterator();

() ) System.out.println( elements.next next() );

System.err.println( "UniqueWords: " + e.getMessage() );

CSD Univ. of Crete 

Example: Counting UniqueWords 

try { HashMap map = new HashMap HashMap Integer one = new Integer( 1 );

while ( ( in.nextToken() != in.TT_EOF ) ) { if ( in.ttype == in.TT_WORD ) {

Integer freq = ( Integer ) map.

if ( freq == null ) freq = one;

else freq = new Integer( freq.

map.put put( in.sval, freq ); }

} 76 

Fall 2007 

Example: Counting UniqueWords 

HashMap HashMap(); Integer one = new Integer( 1 );

while ( ( in.nextToken() != in.TT_EOF ) ) { if ( in.ttype == in.TT_WORD ) {

Integer freq = ( Integer ) map.get get( in.sval );

if ( freq == null )

freq = new Integer( freq.intValue intValue() + 1 );

( in.sval, freq );

CSD Univ. of Crete 

Example: Counting UniqueWords 

System.out.println("There are " + map. " unique words" );

SortedMap sorted = new TreeMap TreeMap Iterator elements = sorted.

while ( elements.hasNext hasNext() ) { Map.Entry cur = ( Map.Entry )elements. System.out.println(cur.getValue getValue

"\t" + cur. }

} catch ( IOException e ) {

System.err.println( "UniqueWords: " + e.getMessage() ); System.exit( 1 );

} }  77 

Fall 2007 

Example: Counting UniqueWords 

System.out.println("There are " + map.size size() + " unique words" );

TreeMap TreeMap(map.entrySet entrySet() ); Iterator elements = sorted.iterator iterator();

() ) { Map.Entry cur = ( Map.Entry )elements.next next();

getValue getValue() + t" + cur.getKey getKey() );

System.err.println( "UniqueWords: " + e.getMessage() );

CSD Univ. of Crete 

Dealing with Changes of Collection Objects 

� Modifiable / Unmodifiable ¿Modifiable: Collections that support operations, e.g., add(), remove(), clear() ¿Unmodifiable: Collections that do not support any modification operations 

� Mutable / Immutable ¿Immutable: Collections that guarantee that Collection will ever be observable such as iterator(), size(), contains() ¿Mutable: Collections that are not immutable 

� Fixed­size / Variable­size ¿Fixed­size: Lists that guarantee that their size will remain constant even though the elements may change ¿Variable­size: Lists that are not fixed 

78 

Fall 2007 

Dealing with Changes of Collection Objects 

: Collections that support modification, “transformer” , e.g., add(), remove(), clear() 

: Collections that do not support any modification 

: Collections that guarantee that no change in the Collection will ever be observable via “selector" operations, e.g., such as iterator(), size(), contains() 

: Collections that are not immutable 

Lists that guarantee that their size will remain constant even though the elements may change 

Lists that are not fixed­size are referred to as

CSD Univ. of Crete 

Wrapper Implementations 

� Basic Containers are sometimes inadequate ¿You want to return an immutable collection ¿You want a threadsafe collection 

� Wrapper implementations add some functionality on top of what a collection offer ¿Unmodifiable ¿Synchronization 

� Wrappers simply delegate all of their real work to a specified collection 

Collection.unmodifiableSortedSet(SortedSet s) 

79 

Fall 2007 

Wrapper Implementations 

Basic Containers are sometimes inadequate You want to return an immutable collection You want a threadsafe collection 

Wrapper implementations add some functionality on top of what a 

Wrappers simply delegate all of their real work to a specified collection 

Collection.unmodifiableSortedSet(SortedSet s)

CSD Univ. of Crete 

Unmodifiable wrappers 

�  The unmodifiable wrappers, rather than adding functionality to the wrapped collection, take functionality away ¿ Any attempt to modify the collection generates an UnsupportedOperationException UnsupportedOperationException

�  The unmodifiable wrappers have two main uses: ¿ To make a collection immutable once it has been built ¿ To allow "second­class citizens" read structures. You keep a reference to the backing collection, but hand out a reference to the wrapper 

public static Collection unmodifiableCollection(Collection c); public static Set unmodifiableSet(Set s); public static List unmodifiableList(List list); public static Map unmodifiableMap(Map m); public static SortedSet unmodifiableSortedSet(SortedSet s); public static SortedMap unmodifiableSortedMap(SortedMap m);  80 

Fall 2007 

Unmodifiable wrappers 

The unmodifiable wrappers, rather than adding functionality to the wrapped collection, take functionality away 

Any attempt to modify the collection generates an UnsupportedOperationException UnsupportedOperationException 

The unmodifiable wrappers have two main uses: To make a collection immutable once it has been built 

class citizens" read­only access to your data structures. You keep a reference to the backing collection, but hand out a reference to the wrapper 

public static Collection unmodifiableCollection(Collection c); public static Set unmodifiableSet(Set s); public static List unmodifiableList(List list); public static Map unmodifiableMap(Map m); public static SortedSet unmodifiableSortedSet(SortedSet s); public static SortedMap unmodifiableSortedMap(SortedMap m);

CSD Univ. of Crete 

Thread Safety � Collections, by default, are NOT thread 

¿Design decision for performance and "conceptual weight" � Solutions: 

¿Encapsulated Collections: In general, if the only access to a collection is through a thread­safe object, then that collection is safe ¿Synchronized Collections: Wrapper implementations that synchronize all relevant methods

•Factory methods inside the Collections class: List list = Collections.synchronizedList(new ArrayList(...));

¿Unmodifiable Collections: If an object can't be modified, it is thread safe by definition

•Factory methods inside the Collections class List list = Collections.unmodifiableList(new ArrayList(...));

¿Fail­fast iterators  81 

Fall 2007 

Thread Safety Collections, by default, are NOT thread­safe 

Design decision for performance and "conceptual weight" 

: In general, if the only access to a collection safe object, then that collection is safe 

: Wrapper implementations that synchronize 

Factory methods inside the Collections class: List list = Collections.synchronizedList(new 

: If an object can't be modified, it is thread­ 

Factory methods inside the Collections class List list = Collections.unmodifiableList(new

CSD Univ. of Crete 

“Fail­fast” Iterators 

� What happens if the underlying collection changes during iteration ¿Iterators store enough information to detect concurrent modification 

�  Iterators throw exceptions if the underlying collection has changed ¿If collection is modified during the life of an iterator, then that iterator fails immediately rather than risking arbitrary, non behavior at an undetermined time in the future ¿Exception: the iterator's own add() fine 

final void checkForComodification() { if (modCount != expectedModCount)

throw new ConcurrentModificationException(); } 

82 

Fall 2007 

fast” Iterators 

underlying collection changes during iteration? Iterators store enough information to detect concurrent modification 

Iterators throw exceptions if the underlying collection has changed If collection is modified during the life of an iterator, then that iterator fails immediately rather than risking arbitrary, non­deterministic behavior at an undetermined time in the future 

add() and remove() methods work 

final void checkForComodification() { if (modCount != expectedModCount)

throw new ConcurrentModificationException();

CSD Univ. of Crete 

How To Select a Container 

� Determine how you access elements ¿it doesn't matter ¿access by key ¿access by integer index 

� Determine whether iteration order matters ¿it doesn't matter ¿elements must be sorted ¿elements must stay in order as inserted a (any) 

� Determine which operations need to be fast ¿it doesn't matter ¿adding and removing elements must be fast ¿Finding elements must be fast 

83 

Fall 2007 

How To Select a Container 

Determine how you access elements 

(any) Map ArrayList  (or array) 

Determine whether iteration order matters 

TreeSet elements must stay in order as inserted a (any)  List 

Determine which operations need to be fast 

adding and removing elements must be fast  LinkedList (any) Set

CSD Univ. of Crete 

For Sets and Maps: Tree 

�  if hashCode is consistent with equals order doesn't matter ¿use hash­based implementation ¿otherwise use tree based implementation 

�  If both Hash and Tree based implementations are applicable, then the Hash based is usually the faster 

� For tree based implementation: ¿Is Comparable implemented or must (on objects for Sets, on keys for 

84 

Fall 2007 

For Sets and Maps: Tree­ or Hash­based? 

equals (all API classes) and iteration 

based implementation tree based implementation 

based implementations are applicable, then based is usually the faster 

implemented or must Comparator be specified? s, on keys for Maps)

CSD Univ. of Crete 

Basic Analysis of Algorithms h(n) g(n) f(n) 

g(n) is O(f(n)) 

g(n) is Ω(h(n)) 

Figure 1 Big­O, big­? and big­Θ

class  order constant  O(1) logarithmic  O(lg n) linear  O(n) n log n  O(n lg n) quadratic  O(n 2 

cubic  O(n 3 

O(n 4 

O(2 n 

Table 2 Complexity classes 85 

Fall 2007 

Basic Analysis of Algorithms 

order O(1) O(lg n) O(n) O(n lg n) 

) ) ) ) 

Table 2 Complexity classes 

O(n) 

O(lg n) 

O(1) 

O(n lg n) O(n 2 ) O(n 3 ) O(2 n ) 

Figure 3 Orders of algorithms

CSD Univ. of Crete 

Operation  Member array representation 

contains  O(log n) 

add  O(n) 

remove  O(n) 

equals  O(n 2 ) 

containsAll  O(n 2 ) 

addAll  O(n 1 +n 2 ) 

removeAll  O(n 1 +n 2 ) 

retainAll  O(n 1 +n 2 ) 

Summary of Set 

86 

Fall 2007 

SLL representation 

Boolean array representation 

O(n)  O(1) 

O(n)  O(1) 

O(n)  O(1) 

O(n 2 )  O(m) 

O(n 2 )  O(m) 

O(n 1 +n 2 )  O(m) 

O(n 1 +n 2 )  O(m) 

O(n 1 +n 2 )  O(m) 

implementations

CSD Univ. of Crete 

Summary of Set 

Operation  Algorithm 

contains  CBHT search 

add  CBHT insertion 

remove  CBHT deletion 

�  Closed­bucket hash table (CBHT ¿ Each bucket may be occupied by several entries ¿ Buckets are completely separate 

�  Simplest implementation: each bucket is an 87 

Fall 2007 

implementations 

Time complexity 

CBHT search  O(1)  best O(n)  worst 

CBHT insertion  O(1)  best O(n)  worst 

CBHT deletion  O(1)  best O(n)  worst 

CBHT): Each bucket may be occupied by several entries Buckets are completely separate 

Simplest implementation: each bucket is an SLL

CSD Univ. of Crete 

Summary of Set 

Operation  Algorithm 

contains  BST search 

add  BST insertion 

remove  BST deletion 

88 

Fall 2007 

implementations 

Time complexity 

O(log n)  best O(n)  worst 

BST insertion  O(log n)  best O(n)  worst 

BST deletion  O(log n)  best O(n)  worst

CSD Univ. of Crete 

Operation  Key­indexed array repr­ esentation 

Array repr esentation 

get  O(1)  O(log n) 

remove  O(1)  O(n) 

put  O(1)  O(n) 

putAll  O(m)  O(n 1 +n 2 ) 

equals  O(m)  O(n 2 ) 

Summary of Map 

89 

Fall 2007 

Array repr­ esentation 

SLL repr­ esentation 

BST representation 

O(n)  O(log n)  best O(n)  worst 

O(n)  O(log n)  best O(n)  worst 

O(n)  O(log n)  best O(n)  worst 

O(n 1 +n 2 )  O(n 2  log (n 1 +n 2 ))best O(n 1 n 2 )  worst 

O(n 2 )  O(n 1  log n 2 )  best O(n 1 n 2 )  worst 

implementations

CSD Univ. of Crete 

Summary of Map 

Operation  Algorithm 

get  CBHT search 

remove  CBHT deletion 

put  CBHT insertion 

putAll  merge on corresponding buckets of both CBHTs 

equals  equality test on corresponding buckets of both CBHTs 

90 

Fall 2007 

implementations 

Time complexity 

O(1)  best O(n)  worst O(1)  best O(n)  worst 

O(1)  best O(n)  worst 

merge on corresponding buckets of both CBHTs 

O(m)  best O(n 1 n 2 )  worst 

equality test on corresponding buckets of both CBHTs 

O(m)  best O(n 1 n 2 )  worst

CSD Univ. of Crete 

Operation  Array representation 

get

set

add(int,Object)

add(Object)

remove

equals

addAll 

Summary of List 

91 

Fall 2007 

Array representation 

SLL representation 

O(1)  O(n) 

O(1)  O(n) 

O(n)  O(n) 

O(1)  O(1) 

O(n)  O(n) 

O(n 2 )  O(n 2 ) 

O(n 2 )  O(n 2 ) 

List implementations

CSD Univ. of Crete 

end 

92 

Fall 2007 

end

CSD Univ. of Crete 

Use Closures When Possible 

� A Closure is an object that encapsulates an iteration 

� Encapsulating the iterations allows them to have reusable state 

public abstract class ClosureImpl { public void forAll(Collection collection) { Iterator items = collection.getItems(); while (items.hasNext()) {

exec(items.next());} public abstract void exec(Object object);

}

public interfaceClosure { public void forAll(Collection collection); public void exec(Object object);

} 

93 

Fall 2007 

Use Closures When Possible 

is an object that encapsulates an iteration 

Encapsulating the iterations allows them to have reusable state 

public abstract class ClosureImpl { public void forAll(Collection collection) { Iterator items = collection.getItems(); while (items.hasNext()) {

exec(items.next());} public abstract void exec(Object object);

public interfaceClosure { public void forAll(Collection collection); public void exec(Object object);

CSD Univ. of Crete 

Avoiding Co­modification Exceptions 

lsm: List SelectionModel  listener 1 list: JList 

valueChanged valueChanged 

throws exception 

public void addListSelectionLsitener (ListSelectionListener foo) {

_listenerList = new ArrayList(_listenerList); _listenerList.add(foo);

}  94 

Fall 2007 

modification Exceptions 

listener 1  another part of the application 

listener 2 

valueChanged important stuff 

addListSelectionListener 

throws exception 

public void addListSelectionLsitener (ListSelectionListener foo) {

_listenerList = new ArrayList(_listenerList); _listenerList.add(foo);