Interfaces
One of the main objectives of Object-Oriented programming is software
reuse.
In this section we shall discuss how to make Java codes more reusable using
Interfaces and Generic Programming. Consider an example: the DataSet class
1 /**
2 Computes information about a set of data values. 3 */
4 public class DataSet
5{
6 private double sum;
7 private double maximum;
8 private int count;
9
10 /**
11 Constructs an empty data set.
12 */
13 public DataSet()
14 {
15 sum = 0;
16 count = 0;
17 maximum = 0;
18 } 19
20
21
22
23
24
25 { 26
27
28
29
30
31
32
33
34
/**
Adds a data value to the data set
@param x a data value
*/
public void add(double x)
}
/**
sum = sum + x;
if (count == 0 || maximum < x)
maximum = x;
count++;
Gets the average of the added data.
@return the avg. or 0 if no data has been added
*/
1
35 public double getAverage() 36 {
37
38
39
40 } 41
if (count == 0)
return 0;
return sum / count;
42
43
44
45
46
47 {
48 return maximum; 49 }
50 }
The DataSet class provides a service, namely computing the average and maximum of a set of input values.
The class is suitable only for computing the average of a set of numbers.
If we want to process bank accounts to find the bank account with the highest balance, we could not use the DataSet class in its current form.
/**
Gets the largest of the added data.
@return the max. or 0 if no data has been added
*/
public double getMaximum()
2
Suppose the DataSet class is modified to suit our needs:
public class DataSet // Modified for BankAccount objects {
private double sum;
private BankAccount maximum; private int count;
... // Other methods not shown for brevity
public void add(BankAccount x) {
sum = sum + x.getBalance();
if (count == 0 || maximum.getBalance() < x.getBalance())
maximum = x;
count++;
}
public BankAccount getMaximum() {
return maximum;
}
}
Now, if we want to find the coin with the highest value among a set of coins. The DataSet class is modified again!
Clearly, the algorithm for the data analysis service is the same in all cases, but the details of measurement differ.
We would like to provide a single class that provides this service to any objects that can be measured. Classes could agree on a method getMeasure that obtains the measure to be used in the analysis.
3
In Java, an interface type is used to specify required operations (functionality):
public interface Measurable {
double getMeasure(); // abstract method
// (without implementation)
}
A generic DataSet class for Measurable objects:
public class DataSet
{
private double sum;
private Measurable maximum; private int count;
... // Other methods not shown for brevity
//class of object x must implements the interface //Measurable
public void add(Measurable x)
{
sum = sum + x.getMeasure();
if (count == 0 ||
maximum.getMeasure() < x.getMeasure())
maximum = x;
count++; }
public Measurable getMaximum() {
return maximum;
}
}
4
An interface type is similar to a class, but there are several important differences:
In Java 7 and earlier versions, all methods in an interface type are abstract; they don’t have an implementation.
In Java 8 an interface can have static and default methods (these methods are fully implemented).
In Java 8 and earlier versions, all methods in an interface type are automatically public
In Java 9, private methods are allowed in an interface (private method cannot be abstract or default)
An interface type does not have instance variables, but it is legal to specify constants (variables in an interface are automatically public static final)
The DataSet class can be used to process bank accounts provided that the BankAccount class implements the Measurable interface
public class BankAccount implements Measurable {
public double getMeasure()
{
return balance;
}
}
The DataSet class can also be used to process coins
public class Coin implements Measurable {
public double getMeasure()
{
return value;
}
... }
5
Interfaces can reduce the coupling between classes.
Note that in the above example, DataSet is decoupled from BankAccount
and Coin.
Remark:
BankAccount is a Measurable Coin is a Measurable
DataSet uses Measurable
You can define variable whose type is an interface, e.g.
Measurable x;
Coin c = new Coin();
x = c; //allowed if the class Coin implements Measurable
// x = new Coin();
You cannot create an instance of an interface (except for anonymous class)
Measurable x = new Measurable(); //Syntax error
6
Generic Programming
Generic programming means to write code that can be reused for objects of different types.
//JDK 1.2, generic programming not supported
ArrayList files = new ArrayList(); // ArrayList stores a list // of objects (any type).
String sourceCode = “MyProgram.java”; files.add(sourceCode);
...
String sourceFile = (String)files.get(0); // require typecast files.add(new Employee()); // action is allowed
Java 5 and later versions support generic classes
A generic class is a class with one or more type variables.
The type variable E is enclosed in angle brackets
The type variable is used throughout the class definition to specify method
return types, and the types of fields and local variables.
The type variable E cannot be replaced by a primitive type (e.g. int,
double, etc) in object instantiation.
// JDK 5.0 and later versions
// Create an array list of filenames.
// Elements in the array list must be a string
ArrayList
…
String sourceFile = files.get(0); // no type casting required files.add(new Employee()); // compile time error
// type mismatch
// Similarly you can have an array list of Employee
ArrayList
7
User defined generic classes are allowed.
1 /**
2 This class collects a pair of elements of different types. 3 */
4 public class Pair
5{
6 private T first;
7 private S second;
8
9 /**
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
Constructs a pair containing two given elements. @param firstElement the first element
@param secondElement the second element
*/
public Pair(T firstElement, S secondElement) {
first = firstElement;
second = secondElement; }
/**
Gets the first element of this pair. @return the first element
*/
public T getFirst() { return first; }
/**
Gets the second element of this pair. @return the second element
*/
public S getSecond() { return second; }
public void setFirst(T element) { first = element; }
public void setSecond(S element) { second = element; }
public String toString() { return “(” + first + “, ” + second + “)”; } }
8
1 public class PairDemo
2{
3 public static void main(String[] args) 4{
5 String[] names = { “Tom”, “Diana”, “Harry” };
6 Pair
7 System.out.println(result.getFirst());
8 System.out.println(“Expected: Diana”);
9 System.out.println(result.getSecond());
10 System.out.println(“Expected: 1”);
11 }
12
13 /**
14 Gets the first String containing a given string, together
15 with its index.
16 @param strings an array of strings
17 @param sub a string
18 @return a pair (strings[i], i) where strings[i] is the first
19 strings[i] containing str, or a pair (null, -1) if there is no
20 match.
21 */
22 public static Pair
23 String[] strings, String sub)
24 {
25 for (int i = 0; i < strings.length; i++)
26 {
27 if (strings[i].contains(sub))
28 {
29 return new Pair
30 }
31 }
32 return new Pair
33 }
34 }
Remark:
A class to model key-value pair, class Pair
There is no setter method in the class.
https://openjfx.io/javadoc/14/javafx.base/javafx/util/Pair.html
9
Generic Methods
A generic method is a method with a type parameter.
Such a method can occur in a class that in itself is not generic.
Example: declare a method that can print an array of any type:
public class ArrayUtil {
public static
for (E e : a) //for each element e (of type E) in a[] (a collection)
System.out.print(e + ” “);
System.out.println(); }
… }
// process element e
// Remark: Cannot modify a[] within a for-each loop
10
When you call the generic method, you need not specify which type to use for the type parameter.
Simply call the method with appropriate parameters, and the compiler will match up the type parameters (target typing).
Example:
Rectangle[] rectangles = … //create an array of Rectangle
ArrayUtil.print(rectangles); //The compiler deduces that E //is Rectangle
11
Bounds for Type variables
Sometimes a class or a method needs to place restrictions on type variables. Suppose we want to find the smallest element of an array
class ArrayUtil
{
public static
{
E smallest = a[0];
for (int i = 1; i < a.length; i++)
if (smallest.compareTo(a[i]) > 0) smallest = a[i];
return smallest;
}
}
In the above example, the variable smallest has type E, which means that it
could be an object of an arbitrary class.
How do we know that the class to which E belongs has a compareTo method?
The solution is to restrict E to a class that implements the Comparable interface, a standard interface with a single method, compareTo.
12
class ArrayUtil
{
// correct implementation with type bound
public static
E smallest = a[0];
for (int i = 1; i < a.length; i++)
if (smallest.compareTo(a[i]) > 0)
smallest = a[i];
return smallest;
}
}
The notation
Both E and the bounding type can be either a class or an interface.
The extends keyword was chosen because it is a reasonable approximation of the subtype concept, and the Java designers did not want to create a new keyword to the language.
A type variable can have multiple bounds, e.g.
E extends Comparable & Serializable
13
Getting back to our previous examples on the Dataset class The Dataset class can be redesigned as a generic class.
public class DataSet
private double sum; private E maximum; private int count; …
public void add(E x) {
sum = sum + x.getMeasure();
if (count == 0 ||
maximum.getMeasure() < x.getMeasure())
maximum = x;
count++; }
public E getMaximum() {
return maximum;
}
}
14
Genericity and Inheritance
If SavingsAccount is a subclass of BankAccount,
is ArrayList
The answer is: it is not.
Inheritance of type parameters does not lead to inheritance of generic classes.
The following example codes illustrate reason behind the restriction.
ArrayList
BankAccount barrysChecking = new CheckingAccount(); //allowed
ba.add(harrysChecking); //Adding a CheckingAccount object //to an ArrayList of SavingsAccount!!
//Should NOT be allowed.
ArrayList
BankAccount barrysChecking = new CheckingAccount(); //allowed ba.add(harrysChecking); //This action is allowed
15
Wildcard Types
It is often necessary to formulate subtle constraints of type parameters. Wildcard types are invented for this purpose.
Example:
public void addAll(LinkedList other) {
ListIterator
add(iter.next());
}
The addAll method doesn’t require a specific type for the element type other. It allows you to use any type that is a subtype of E.
You can use addAll to add a LinkedList
type B or subclass of B
type B or superclass of B
16
Type Erasure
Generic types are a fairly recent addition to the Java language, the virtual machine that executes Java programs does not work with generic classes or methods.
Instead, type parameters are “erased”, that is, they are replaced with its bound, or with Object if it is not bounded.
The generic class Pair
public class Pair {
private Object first; private Object second;
public Pair(Object firstElement, Object secondElement) {
first = firstElement;
second = secondElement; }
public Object getFirst() { return first; } public Object getSecond() { return second; }
public void setFirst(Object element) { first = element; }
public void setSecond(Object element) { second = element; }
}
Remark: type checking is only performed by the compiler.
17
Type erasure is also applied to generic methods:
public static
E smallest = a[0];
for (int i = 1; i < a.length; i++)
if (smallest.compareTo(a[i]) > 0)
smallest = a[i];
return smallest;
}
This above generic method is type-erased to:
public static Comparable min(Comparable[] a) {
Comparable smallest = a[0];
for (int i = 1; i < a.length; i++)
if (smallest.compareTo(a[i]) > 0)
smallest = a[i];
return smallest;
}
18
Know about raw types helps you understand limitations of Java generics.
For example, trying to fill an array with copies of default objects would be wrong:
public static
for (int i = 0; i < a.length; i++)
a[i] = new E(); // Will not produce the expected effect
}
Type erasure yields:
public static void fillWithDefaults(Object[] a) {
for (int i = 0; i < a.length; i++)
a[i] = new Object(); // Not useful
}
To solve this particular problem, you can supply a default type:
public static
for (int i = 0; i < a.length; i++) a[i] = defaultValue;
}
E defaultValue)
19
You cannot construct an array of a generic type:
public class MyClass
private E[] elements; …
public MyClass()
{
elements = new E[MAX_SIZE]; // Error }
}
Because the array construction expression new E[] would be erased to new Object[].
One remedy is to use an ArrayList
public class MyClass
private ArrayList
public MyClass()
{
elements = new ArrayList(); // Ok }
}
20
Sorting and Searching an array
The class java.util.Arrays provides a number of utility functions (static methods), such as binary search and sorting, to support the basic sorting and searching operations.
The following binary search and sorting functions require the object class implements the Comparable interface.
The method compareTo() in the Comparable interface defines the natural order of objects that belong to the given class.
static int binarySearch(Object[] a, Object key)
static void sort(Object[] a)
The class Arrays also provides generic binary search and sorting functions. static
Comparator c)
static
To use the above generic functions, you need to provide a Comparator object (an instance of a class that implements the Comparator interface).
public interface Comparator
{
int compare(T o1, T o2);
// return 0 if o1 == o2
// return a positive value if o1 > o2
// return a negative value if o1 < o2
// Other static and default methods in the interface.
// Will explain the static methods in the Comparator
// interface later when we discuss functional programming.
}
21
Example design of the 2 versions of binary search method.
// Actual class of the object implements Comparable
static int binarySearch(Object[] a, Object key)
{
int low = 0;
int high = a.length - 1;
while (low <= high)
{
int mid = (low + high) / 2;
int r = ((Comparable)key).compareTo(a[mid]); if (r == 0)
return mid;
if(r<0) //key
Comparator c)
{
int low = 0;
int high = a.length – 1;
while (low <= high)
{
int mid = (low + high) / 2;
int r = c.compare(key, a[mid]); // c is a functional
if (r == 0)
return mid;
if(r<0) //key
// Comparator that can compare BankAccount
class BA_Comparator implements Comparator
@Override
public int compare(BankAccount a1, BankAccount a2) {
// compare BankAccount objects by balance
if (a1.getBalance() < a2.getBalance())
return -1;
else if (a1.getBalance() > a2.getBalance())
return 1;
else
return 0;
} }
int n = 100;
SavingsAccount[] sa_array = new SavingsAccount[n];
…
// statements to create and initialize the array
// Sort the array of SavingsAccount by balance.
Comparator cmp = new BA_Comparator(); Arrays.sort(sa_array, cmp);
// In this generic method invocation,
// type parameter T = SavingsAccount
// cmp is an instance of Comparator
// BankAccount is a superclass of SavingsAccount
23
Example : basic coding style
class Emp_Comparator implements Comparator
@Override
public int compare(Employee e1, Employee e2) {
// compare Employee by name
return e1.getName().compareTo(e2.getName());
}
}
int n = 100;
Employee[] emp_array = new Employee[n];
…
// statements to create and initialize the Employee array
Comparator cmp = new Emp_Comparator(); Arrays.sort(emp_array, cmp);
Example: coding style using anonymous class
Comparator cmp = new Comparator
public int compare(Employee e1, Employee e2)
{
return e1.getName().compareTo(e2.getName());
} };
Arrays.sort(emp_array, cmp);
// Another coding style using anonymous object
Arrays.sort(emp_array,
new Comparator
public int compare(Employee e1, Employee e2) {
return e1.getName().compareTo(e2.getName()); }
});
24
Defining a functional object using Lambda expression Lambda expression is introduced in Java 8.
Lambda expression is used to define an implementation of a Functional interface (an interface with only 1 abstract method).
Basic syntax of Lambda expression
(arg1, arg2) -> single statement;
(Type arg1, Type arg2) -> { multiple statements };
The number of arguments depends on the abstract method defined in the interface.
Arguments are enclosed in parentheses and separated by commas.
The arguments correspond to the inputs required by the (abstract) method of the Functional interface.
The expression or statement block corresponds to the body of the method.
The data type of the arguments can be explicitly declared or it can be inferred from the context (i.e. the compiler will determine the target data type)
When there is a single argument, if its type is inferred, it is not mandatory to use parentheses, e.g. (a) -> statement; is the same as a -> statement;
Code snippet to sort an array of Employee using Lambda expression:
Arrays.sort(emp_array,
(e1, e2) -> e1.getName().compareTo(e2.getName()));
25
Collection
A collection (called a container in C/C++) is simply an object that groups
multiple elements into a single unit.
Collections are used to store, retrieve, manipulate, and communicate aggregate data.
A collection typically represents data items that form a natural group, such as a mail folder (a collection of letters), or a telephone directory (a mapping from names to phone numbers).
Typical data structures used to implement a collection include array, array list, linked list, stack, queue, tree, hash table, and etc.
A collection framework is a unified architecture for representing and manipulating collections.
26
Interfaces of the collection frameworks:
Iterable means that there is a mechanism to allow the user to visit each member in the collection one by one in a specific order.
The object that facilitates the iterated processing is called an Iterator.
27
All Methods
Instance MethodsAbstract MethodsDefault Methods
Modifier and Type
boolean
boolean
void
boolean
boolean
boolean
int
boolean Iterator
boolean
default boolean boolean
int
default Spliterator
Method and Description
add(E e)
Ensures that this collection contains the specified element (optional operation).
addAll(Collection c)
Adds all of the elements in the specified collection to this collection (optional operation).
clear()
Removes all of the elements from this collection (optional operation).
contains(Object o)
Returns true if this collection contains the specified element.
containsAll(Collection c)
Returns true if this collection contains all of the elements in the specified collection.
equals(Object o)
Compares the specified object with this collection for equality.
hashCode()
Returns the hash code value for this collection.
isEmpty()
Returns true if this collection contains no elements.
iterator()
Returns an iterator over the elements in this collection.
parallelStream()
Returns a possibly parallel Stream with this collection as its source.
remove(Object o)
Removes a single instance of the specified element from this collection, if it is present (optional operation).
removeAll(Collection c)
Removes all of this collection’s elements that are also contained in the specified collection (optional operation).
removeIf(Predicate filter)
Removes all of the elements of this collection that satisfy the given predicate.
retainAll(Collection c)
Retains only the elements in this collection that are contained in the specified collection (optional operation).
size()
Returns the number of elements in this collection.
spliterator()
Creates a Spliterator over the elements in this collection.
stream()
Returns a sequential Stream with this collection as its source.
toArray()
Returns an array containing all of the elements in this collection.
toArray(T[] a)
Returns an array containing all of the elements in this collection; the runtime type of the returned array is that of the specified array.
28
Remark:Themethodscontains(), containsAll(), indexOf(), remove(), removeAll(), retainAll() should be used with care when you are dealing with user defined object classes !!
29
Methods defined in the class ArrayList
Modifier and Type
boolean void boolean
boolean void
Object
boolean void
void
E
int boolean
Iterator
ListIterator
E
Method and Description
add(E e)
Appends the specified element to the end of this list.
add(int index, E element)
Inserts the specified element at the specified position in this list.
addAll(Collection c)
Appends all of the elements in the specified collection to the end of this list, in the order that they are returned by the specified collection’s Iterator.
addAll(int index, Collection c)
Inserts all of the elements in the specified collection into this list, starting at the specified position.
clear()
Removes all of the elements from this list.
clone()
Returns a shallow copy of this ArrayList instance.
contains(Object o)
Returns true if this list contains the specified element.
ensureCapacity(int minCapacity)
Increases the capacity of this ArrayList instance, if necessary, to ensure that it can hold at least the number of elements specified by the minimum capacity argument.
forEach(Consumer action)
Performs the given action for each element of the Iterable until all elements have been processed or the action throws an exception.
get(int index)
Returns the element at the specified position in this list.
indexOf(Object o)
Returns the index of the first occurrence of the specified element in this list, or -1 if this list does not contain the element.
isEmpty()
Returns true if this list contains no elements.
iterator()
Returns an iterator over the elements in this list in proper sequence.
lastIndexOf(Object o)
Returns the index of the last occurrence of the specified element in this list, or -1 if this list does not contain the element.
listIterator()
Returns a list iterator over the elements in this list (in proper sequence).
listIterator(int index)
Returns a list iterator over the elements in this list (in proper sequence), starting at the specified position in the list.
remove(int index)
Removes the element at the specified position in this list.
remove(Object o)
boolean
30
Removes the first occurrence of the specified element from this list, if it is present.
boolean
removeAll(Collection c)
Removes from this list all of its elements that are contained in the specified collection.
boolean
removeIf(Predicate filter)
Removes all of the elements of this collection that satisfy the given predicate.
protected void
removeRange(int fromIndex, int toIndex)
Removes from this list all of the elements whose index is between fromIndex, inclusive, and toIndex, exclusive.
void
replaceAll(UnaryOperator
Replaces each element of this list with the result of applying the operator to that element.
boolean
retainAll(Collection c)
Retains only the elements in this list that are contained in the specified collection.
E
set(int index, E element)
Replaces the element at the specified position in this list with the specified element.
int
size()
Returns the number of elements in this list.
void
sort(Comparator c)
Sorts this list according to the order induced by the specified Comparator.
Spliterator
spliterator()
Creates a late-binding and fail-fast Spliterator over the elements in this list.
List
subList(int fromIndex, int toIndex)
Returns a view of the portion of this list between the specified fromIndex, inclusive, and toIndex, exclusive.
Object[]
toArray()
Returns an array containing all of the elements in this list in proper sequence (from first to last element).
toArray(T[] a)
Returns an array containing all of the elements in this list in proper sequence (from first to last element); the runtime type of the returned array is that of the specified array.
void
trimToSize()
Trims the capacity of this ArrayList instance to be the list’s current size.
31
ArrayList
• • •
•
ArrayList class manages a sequence of objects
Support random access, and can grow and shrink as needed.
ArrayList class supplies methods for many common tasks, such as inserting and removing elements
ArrayList
ArrayList
names.add(“Emily”);
names.add(“Bob”);
names.add(“Cindy”); //new item added at the end of the list
•
•
•
size() method yields number of elements
To obtain the value of an element at an index, use the get() method
Index starts at 0
String name = names.get(2);
// gets the third element of the array list
• Bounds error if index is out of range
• Most common bounds error:
int i = names.size();
name = names.get(i); // Error
// legal index values are 0 … i-1
32
• To set an element to a new value, use the set() method: names.set(2, “Carolyn”);
• To remove an element at an index, use the remove() method: names.remove(1);
Example:
names.add(“Emily”);
names.add(“Bob”);
names.add(“Cindy”);
names.set(2, “Carolyn”); //(1)
names.add(1, “Ann”); //(2), add new element at a given loc
// loc <= names.size()
names.remove(1); //(3)
33
ArrayList of numbers
• To collect numbers in an ArrayList, use the wrapper type as the type
parameter, and then rely on auto-boxing:
ArrayList
values.add(29.95);
double x = values.get(0);
• Storing wrapped numbers is quite inefficient
• Acceptable if you only collect a few numbers
• Use arrays for long sequences of numbers or characters
Remarks:
• ArrayList provides certain conveniences to the programmer
• Automatic grow and shrink, number of elements is equal to the size of the ArrayList.
• Support generic programming.
• Insertion and removal of elements at specific locations.
o Remove the last element (or append a new element at the end) requires
O(1) time.
o Remove the first element (or insert a new element at the front) requires
O(n) time.
• Auto-boxing of primitive types.
• Major disadvantage: slow
34
Processing elements in a collection one by one using an iterator The Iterator interface has 3 methods
boolean hasNext()
– returns true if there is another element to visit.
E next()
– returns the next object to visit. Throws a NoSuchElementException if
the end of the collection has been reached.
void remove()
– removes the last visited object. This method must immediately follow an
element visit. If the collection has been modified since the last element visit, then the method throws an IllegalStateException.
To visit elements in the collection one by one:
Collection
Iterator
while (iter.hasNext())
{
String element = iter.next();
//do something with element
}
As of JDK 5.0, you can use the “for each” loop to visit all elements in the collection:
Collection
for (String element : c) //for each element in c {
//do something with element
//but you cannot modify the contents of the collection //when using the for-each loop
}
35
Example codes on the uses of the method contains()
ArrayList
String s1 = “ABC”;
String s2 = “ABC123”;
list_s.add(s1);
String s3 = s2.substring(0, 3); // s3 = “ABC”
/*
Question: list_s.contains(s3) returns true or false ?
*/
ArrayList
list_r.add(r1);
StudentRecord r2 = new StudentRecord(r1.getName(),
r1.getSid(), r1.getProgCode());
/*
Question: list_r.contains(r2) returns true or false ?
*/
36
public class StudentRecord
{
private String name;
private int sid;
private String progCode;
…
@Override
public boolean equals(Object other) {
if (other instanceof StudentRecord)
{
StudentRecord r = (StudentRecord)other;
return name.equals(r.name) && sid == r.sid &&
progCode.equals(r.progCode);
return false;
} else
} }
class ArrayList
public boolean contains(Object obj)
{
for (E e : this)
if (e.equals(obj))
return true;
return false;
} }
Remark: if you override the method equals, you may also
need to override the method hashCode.
The equals method for class Object implements the most discriminating possible equivalence relation on objects; that is, for any non-null reference values x and y, this method returns true if and only if x and y refer to the same object (x == y has the value true).
Note that it is generally necessary to override the hashCode method whenever this method is overridden, so as to maintain the general contract for the hashCode method, which states that equal objects must have equal hash codes.
The hashCode method is used to support the implementation of hash table and hash map.
37
Linked List
In Java all linked lists are actually doubly linked; i.e. each node also stores a reference to its predecessor.
A linked list is an ordered collection in which the position of the objects matters. The LinkedList.add method adds the object to the end of the list.
There is no add method in the Iterator interface. Instead, the collection library provides a subinterface ListIterator that contains an add method and some other methods.
The ListIterator.add method allows you to add an element at specific location in the list.
interface ListIterator
{
void add(E newElement);
void set(E newElement);
boolean hasPrevious();
E previous();
int nextIndex();
int previousIndex();
}
38
You can think of Java iterators as being between elements.
When you call next(), the iterator jumps over the next element, and it returns a reference to the element that it just passed.
The remove() method of the Iterator interface removes the element that was returned by the last call to next().
Example: to remove the first 2 elements
LinkedList
Iterator
iter.next();
iter.remove(); //remove the 1st element
iter.next();
iter.remove(); //remove the 2nd element
39
To add a new element after the element just visited (before the iterator).
40
More than one iterator can be attached to a collection.
If an iterator traverses a collection while another iterator is modifying the
collection, confusing situations can occur.
List
ListIterator
iter1.remove(); // remove first element
iter2.next(); // throws ConcurrentModificationException
General rules:
1. You can attach as many iterators to a collection as you like, provided that
all of them are only readers; or
2. You can attach a single iterator that can both read and write.
41
42
43
Tree Sets
A tree set is a sorted collection.
You insert elements into a tree set in any order. When you iterate through the
collection, the values are automatically presented in sorted order.
In the current version of Java collection library, tree set is implemented as a
red-black tree (a form of balanced search tree).
Example:
public class TreeSetTest
{
public static void main(String[] args)
{
TreeSet
sorter.add(“Bob”);
sorter.add(“Amy”);
sorter.add(“Carl”);
for (String s : sorter)
System.out.println(s);
//output: Amy Bob Carl
} }
By default, the tree set assumes that you insert elements that implement the Comparable interface, i.e. elements can be ordered using the compareTo method.
What if the object class does not implement the Comparable interface, or you want to sort the items using another attribute?
44
For example, the compareTo method of the Student class is based on the ID field, and you want to sort the collection of students using the name field.
In that case, you tell the tree set to use a different comparison method, by passing a Comparator object into the TreeSet constructor.
The Comparator object must implement the Comparator interface (which contains a generic method compare)
class StudentComparator implements Comparator
public int compare(Student a, Student b)
{
return a.getName().compareTo(B.getName());
} }
You then pass a Comparator object to the tree set constructor
Comparator comp = new StudentComparator();
TreeSet
45
interface Map
class Hashtable
Serializable, Cloneable
class HashMap
class TreeMap
In many applications, we need to process (key, value) pairs.
Basic operations supported by a Map
The Hashtable
An instance of Hashtable has 2 parameters that affect its performance:
– initial capacity : number of buckets in the hash table
– load factor : f = n / C,
n = number of keys, C = capacity of the hash table
– Keys in the map are distinct
– Keys and values cannot be null
The HashMap
– Unsynchronized : have safety concern in multi-thread program
TreeMap
– Implementation based on search tree
– The map is sorted
– Guaranteed log(n) time for searching, insertion, and deletion
46