COSC 3P91: Week 3 Notes

Interfaces

Design guideline - Maximize the Uniformity of Common Aspects of Related Classes/Interfaces

classDiagram
    class Iterable~E~ {
    }
    class Collection~E~ {
    }
    class Set~E~ {
    }
    class List~E~ {
    }
    class SortedSet~E~ {
    }
    class Map~K, V~ {
    }
    class SortedMap~K, V~ {
    }

    Iterable~E~ <|-- Collection~E~
    Collection~E~ <|-- Set~E~
    Collection~E~ <|-- List~E~
    Set~E~ <|-- SortedSet~E~
    Map~K, V~ <|-- SortedMap~K, V~

Note: Map and SortedMap do not implement the Iterable Interface

• Iterable
  • iterator
  • forEach
• Collection
  • common interface for non-map collections
  • equals
• Set
  • modifies semantics - no duplicates
  • SortedSet
• List
  • modified semantics - ordered
• Map
  • not Collection - involves keys, no duplicate keys
  • views
    • entry set (key-value pairs)
    • key set
    • value collection
  • keys
    • equals
  • SortedMap

Types of Interfaces

Collection <E> Interface

There are a couple other methods, just included the “important” ones.

Method	Description
add(o)	Adds an element o to this collection.
addAll(c)	Adds all the elements in the collection c to this collection.
clear()	Removes all elements from this collection.
contains(o)	Returns true if this collection contains an element that equals o.
containsAll(c)	Returns true if this collection contains all the elements in the collection c.
isEmpty()	Returns true if this collection contains no elements.
iterator()	Returns an Iterator over the elements in this collection.
remove(o)	Removes an element that equals o from this collection.
removeAll(c)	Removes from this collection all elements from c.
retainAll(c)	Retains only the elements that are contained in c.
size()	Returns the number of elements in this collection.

Set<E> Interface

Method	Description
add(o)	Adds an element o to this set if it is not already present.
addAll(c)	all the elements in the collection c to this set if they are not already present.

HashSet<E>

• hash table (efficient in insertion and membership checking)
• unpredictable iteration order
• requires equals and hashCode

LinkedHashSet<E> (similar to HashSet)

• hash table with linked elements
• predictable iteration order (usually insertion order)
• requires equals and hashCode

TreeSet<E>

• red-black tree (a form of balanced binary trees)
• SortedSet
• requires ordering (Comparable or Comparator)
• iteration by natural order
• less efficient in insertion and membership checking

Overall

Use HashSet unless a sorted set or a predictable iteration order is required.

List<E> Interface

Method	Description
add(i, o)	Insert the element o at the i-th position in this list.
add(o)	Appends the element o to the end of this list.
addAll(c)	Inserts all the elements in the collection c to the end of this list, in the order that they are returned by the iterator of c.
addAll(i, c)	Inserts all the elements in the collection c into this list, starting at the i-th position.
get(i)	Returns the element at the i-th position in this list.
indexOf(o)	Returns the index in this list of the first occurrence of the element o, or -1 if the element is not present in this list.
lastIndexOf(o)	Returns the index in this list of the last occurrence of the element o, or -1 if the element is not present in this list.
listIterator()	Returns a ListIterator of the elements of this list.
listIterator(i)	Returns a ListIterator of the elements of this list, starting from the i-th position.
remove(i)	Removes the element at the i-th position in this list and returns the removed element.
remove(o)	Removes the first occurrence of the element o from this list.
set(i, o)	Replaces the element at the i-th position in this list with the element o, and returns the element that was replaced.
subList(i, j)	Returns a sublist of this list from the i-th position (inclusive) to the j-th position (exclusive).

ArrayList<E>

• Array extended when necessary
• Large enough to hold predicted number of elements
• Often, a large portion of the array is unused
• Large cost to increase size (copying)
• More efficient access

Vector<E> (similar to ArrayList)

• Same implementation as the ArrayList
• Supports additional “legacy methods”
• Thread-safe
• Significant overhead in performance

LinkedList<E>

• Doubly-linked list
• No additional penalty as list grows
• Less efficient access

Overall

Use LinkedList for volatile lists, ArrayList for stable lists.

SortedSet<E> Interface

Method	Description
comparator()	Returns the comparator associated with this sorted set, or null if the natural order is used.
first()	Returns the first (lowest) element currently in this sorted set.
headSet(o)	Returns a set view of the portion of this sorted set whose elements are strictly less than o.
last()	Returns the last (highest) element currently in this sorted set.
subSet(o1, o2)	Returns a set view of the portion of this sorted set whose elements range from o1, inclusive, to o2, exclusive.
tailSet(o)	Returns a set view of the portion of this sorted set whose elements are greater than or equal to o.

Map<K,V> Interface

Method	Description
clear()	Removes all entries from this map.
containsKey(k)	Returns true if this map contains an entry for the key k.
containsValue(v)	Returns true if this map contains one or more entries with the value v.
entrySet()	Returns the entry view of this map.
get(k)	Returns the value to which this map maps the key k.
isEmpty()	Returns true if this map contains no entries.
keySet()	Returns the key set view of this map.
put(k, v)	Maps the key k to the value v in this map.
putAll(m)	Copies all entries from the map m to this map.
remove(k)	Removes the entry for key k from this map if present.
size()	Returns the number of entries in this map.
values()	Returns the value collection view of this map.

HashMap<K, V>

• Hash table (efficient in insertion and membership checking)
• Unpredictable iteration order
• Requires equals and hashCode

Hashtable<K, V> (similar to HashMap)

• Same implementation as the HashMap
• Supports additional “legacy methods”
• Thread-safe
• Significant overhead in performance

LinkedHashMap<K, V>

• Hash table with linked elements
• Predictable iteration order (usually insertion order)
• Requires equals and hashCode

IdentityHashMap<K, V> (similar to HashMap)

• Key equality based on == (identity)
• Requires hashCode

TreeMap<K, V>

• Red-black tree
• SortedMap
• Iteration order by key
• Requires ordering for keys (Comparable or Comparator)
• Less efficient in insertion and membership checking

Overall

• Use TreeMap if a sorted map is required.
• Otherwise, use HashMap or IdentityHashMap for efficiency.

SortedMap<K,V> Interface

Method	Description
comparator()	Returns the comparator associated with this sorted map, or null if the natural order is used.
firstKey()	Returns the first (lowest) key currently in this sorted map.
headMap(k)	Returns a map view of the portion of this sorted map whose keys are strictly less than k.
lastKey()	Returns the last (highest) key currently in this sorted map.
subMap(k1, k2)	Returns a map view of the portion of this sorted map whose keys range from k1, inclusive, to k2, exclusive.
tailMap(k)	Returns a map view of the portion of this sorted map whose keys are greater than or equal to k.

Side note: Examples (hashCode() and equals())

public class Person {
	private final String name;
	private int number;
	private String phrase;
	// ...
 
	public int hashCode() {
		int hash = 5;
		hash = 53 * hash + name.hashCode();
		hash = 53 * hash + this.age;
		hash = 53 * hash + Objects.hashCode(this.phrase);
		return hash;
	}
 
	public boolean equals (Object obj) {
		return obj != null 
			&& obj instanceof Person pObj
			&& this.name.equals(pObj.name)
			&& this.number == pObj.number
			&& Objects.equals(this.phrase, pObj.phrase);
	}
}

Concrete Classes

Important issues:

• bounded vs unbounded
• time and space complexity of various operations
• interchangeability
• concrete collection classes in Java
  • all unbounded

Abstract Collection Classes

• for building new collections

AbstractCollection<E>

• Bag
• Must implement iterator and size

AbstractSet<E>

• Must implement add

AbstractList<E>

• Optimized for random access
• Must implement get and size

AbstractSequentialList<E>

• Optimized for sequential access
• Must implement listIterator and size

AbstractMap<K, V>

• Must implement entries

I/O

I/O: sequential and random access

Streams

• sequential
• uniform specification for any data transfer
  • file I/O
  • network transmission
  • to/from memory

Input Streams

classDiagram
    InputStream <|-- ByteArrayInputStream
    InputStream <|-- FileInputStream
    InputStream <|-- FilterInputStream
    InputStream <|-- PipedInputStream
    InputStream <|-- ObjectInputStream
    InputStream <|-- SequenceInputStream
    FilterInputStream <|-- DataInputStream
    FilterInputStream <|-- BufferedInputStream
    FilterInputStream <|-- LineNumberInputStream
    FilterInputStream <|-- PushbackInputStream

abstract class InputStream {
	//read a singe byte from the input
	int read() throws IOException;
	//read an array of values from the input
	int read(byte[] buffer) throws IOException;
	//skip the indicated number of values from input
	long skip(long n) throws IOException;
	//determine number of bytes readable without blocking
	int available() throws IOException;
	//close this input stream
	void close() throws IOException;
}

Physical Input Streams

ByteArrayInputStream

ByteArrayInputStream(byte[] buffer);
ByteArrayInputStrean(byte[] buffer, int offset, int count);

FileInputStream

FileInputStream(File f);
FileInputStream(String fileName);

PipedInputStream

PipedInputStream(PipedOutputStream p);

Virtual Input Streams

• do not read values form any input area
• rely on one or more underlying input streams
• are implementations of the design patter decorator

SequenceInputStream

InputStream f1 = new FileInputStream(“file1.txt“);
InputStream f2 = new FileInputStream(“file2.txt“);
InputStream f3 = new SequenceInputStream(f1,f2);
	//f3 now represents the catenation of file1 and file2
 
Vector fv = new Vector();
fv.addElement(f1);
fv.addElement(f2);
InputStream f4 = new SequenceInputStream(fv.elements());
	//f4 also now represents the same catenation

End of lecture 1

ObjectInputStream

FilterInputStream

… and it’s subclasses

Filter

Adds behaviour to the stream

• DataInputStream: read bytes from the source and return them as a primitive type
  • e.g. public readInt() throws IOException;
• PushbackInputStream: allows a single character to be unread
• BufferedInputStream: allows the input operations to backed up over a larger range - mark(), reset()

graph TD
    client -->|"read()"| filter
    filter -->|"read()"| InputStream

Output Streams

graph TB
    OutputStream --> ByteArrayOutputStream
    OutputStream --> FileOutputStream
    OutputStream --> FilterOutputStream
    OutputStream --> PipedOutputStream
    OutputStream --> ObjectOutputStream
    
    FilterOutputStream --> DataOutputStream
    FilterOutputStream --> BufferedOutputStream
    FilterOutputStream --> PrintStream

abstract class OutputStream {
	//write a singe byte value
	void write(int b) throws IOException;
	//write an array of byte values
	void write(byte[] buffer) throws IOException;
	//flush all output from buffers
	void flush() throws IOException;
	//close this output stream
	void close() throws IOException;
}

Physical Output Streams

ByteArrayOutputStream

FileOutputStream

PipedOutputStream

Virtual Output Streams

ObjectOutputStream

FilterOutputStream

… and it’s subclasses

• DataOutputStream: the output equivalent DataInputStream
• BufferedOutputStream: uses a buffer, values are written to the underlying stream only when the buffer becomes full or when the output is flushed
• PrintStream: similar to DataOutputStream but generates a textual representation rather than a binary representation

Piped I/O

• used for producer/consumer relationships
  • communication between producer/consumer (different threads) through a pipe
• each pipe is manifested by a matched pair of stream pointers, a PipedInputStream and a PipedOutputStream, e.g.

PipedInputStream in = new PipedInputStream();
PipedOutputStream out = new PipedOutputStream(in);

Piped I/O Example

Finding all numbers that are both prime numbers and Fibonacci numbers, i.e. a number defined by a recursive relation $f_0=0,f_1=1,f_{n+2}=f_n+f_{n+1}$

class FibMaker extends Thread {
	
	private DataOutputStream out;
 
	public FibMaker(DataOutputStream o) {
		out = o;
	}
 
	public void run() {
		try {
			out.writeInt(newValue);
			out.close();
		} catch (IOException e) {
			return;
		}
	}
}

class PrimeMaker extends Thread {
	
	private DataOutputStream out;
 
	public PrimeMaker(DataOutputStream o) {
		out = o;
	}
 
	public void run() {
		try {
			out.writeInt(newValue);
			out.close();
		} catch (IOException e) {
			return;
		}
	}
}

class PipeTest {
	
	public static void main(String[] args) {
		PipeTest world = new PipeTest(System.out);
	}
	
	private DataInputStream makeFibs() {
		try {
			PipedInputStream in = new PipedInputStream();
			PipedOutputStream out = new PipedOutputStream(in);
			Thread fibThread = new FibMaker(
				new DataOutputStream(out));
			fibThread.start();
			return new DataInputStream(in);
		} catch (IOException e) {
			return null;
		}
	}
}

	private DataInputStream makePrimes() {…}
 
	private PipeTest(PrintStream out) {
		DataInputStream fibs = makeFibs();
		DataInputStream primes = makePrimes();
		try {
			int x = fibs.readInt();
			int y = primes.readInt();
			while (x < 100000) {
				if (x == y) {
					out.println(…);
					x = fibs.readInt();
					y = primes.readInt();
				} else if (x < y)
					x = fibs.readInt();
				else
					y = primes.readInt();
			}
		} catch (IOException e) {
			System.exit(0);
		}
	}
}

Character Streams

• Reader/Writer mirror the functionality found in InputStream and OutputStream
  • 8-bit bytes vs 16-bit Unicode characters
• Physical Reader / Writer
  • CharArrayReader / Writer
  • StringReader / Writer
  • FileReader / Writer
  • PipedReader / Writer
• Virtual Reader / Writer
  • BufferedReader / Writer
  • FilterReader / Writer
  • PrintWriter
• InputStreamReader / OutputStreamWriter act as filter for streams, i.e., they convert streams to character streams, e.g.,

FileInputStream f = new FileInputStream(“fileName“);
InputStreamReader r = new InputStreamReader(f);

graph TD
    Reader --> BufferedReader
    Reader --> CharArrayReader
    Reader --> InputStreamReader
    Reader --> FilterReader
    Reader --> PipedReader
    Reader --> StringReader

    BufferedReader --> LineNumberReader
    InputStreamReader --> FileReader
    FilterReader --> PushbackReader

graph TD
    Writer --> BufferedWriter
    Writer --> CharArrayWriter
    Writer --> OutputStreamWriter
    Writer --> FilterWriter
    Writer --> PipedWriter
    Writer --> PrintWriter
    Writer --> StringWriter

    OutputStreamWriter --> FileWriter

StreamTokenizer

• StreamTokenizer is neither a InputStream nor a Reader
• provides a useful mechanism for breaking a textual file into a sequence of tokens

StreamTokenizer Example

“23-skidoo, kid!” returns the output:

number: 23.0
token: -
word: skidoo
token: ,
word: kid
token: !

Reader r = new InputStreamReader(System.in); 
StreamTokenizer tok = new StreamTokenizer(r);
try {
	while (tok.nextToken() != tok.TT_EOF) {
		switch (tok.ttype) {
	case tok.TT_NUMBER: 
	  	System.out.println(“number: “ + tok.nval);
		break;
	case tok.TT_EOL:
		System.out.println(“end of line.“);		
		break;
	case tok.TT_WORD:
		System.out.println(“word: “ + tok.sval);
		break;
	default:
		System.out.println(“token: “ + (char) tok.ttype);
		break;
		}
	}
} catch (IOException e) {}

Random Access I/O

• storing serialized objects in random access files
  • Idea: write object as size followed by serialized version

RandomAccessFile

• can read & write at the same time
• implements DataInput & DataOutput
  • Interfaces which are also implemented by DataInputStream and DataOutputStream
• Changing current I/O position
  • seek(l) moves the read/write position to the l-th byte counting from the beginning of the file
  • skipBytes(i) moves the read/write position i bytes from the current position

Examples:

copy a file (unfiltered, byte by byte)

try {
	FileInputStream in = new FileInputStream(“source“);
	FileOutputStream out = new FileOutputStream(“target“);
	int val = in.read();
	while (val != -1) {
		out.write(val);
		val = in.read();
	};
	in.close();
	out.close();
} catch (IOException e) {}

copy a file (buffered Reader/Writer)

try {
	FileReader fin = new FileReader(“source“);
	BufferedReader in = new BufferedReader(fin);
	FileWriter fout = new FileWriter(“target“);
	BufferedWriter out = new BufferedWriter(fout);
	String str = in.readLine();
	while (str != null) {
		out.write(str);
		str = in.readLine();
	};
	in.close();
	out.close();
} catch (IOException e) {}

End of week 3 lecture slides, moving to week 4

Design Pattern - Iterator

• aka Cursor
• a behavioural pattern
• intent:
  • allow sequential access to elements of an aggregate without exposing underlying representation
• motivation:
  • want to be able to access elements of an aggregate object without exposing internal structure
  • want to use several different traversals
  • want different traversals pending on the same list

Iterator - Model

classDiagram
    class Aggregate {
        CreateIterator()
    }
    
    class ConcreteAggregate {
        CreateIterator()
    }
    
    class Iterator {
        First()
        Next()
        IsDone()
        CurrentItem()
    }
    
    class ConcreteIterator

    class Client

    Aggregate <|-- ConcreteAggregate
    Iterator <|-- ConcreteIterator
    Client --> Aggregate
    Aggregate --> Iterator
    ConcreteAggregate --> ConcreteIterator : return new ConcreteIterator(this)

Use

• Access aggregate object’s contents without exposing internal representation
• support multiple traversals of aggregate objects
• provide uniform interface for traversing different structures

Consequences

• supports variations in traversal of aggregate
• simplified aggregate interface
• more than one traversal can be pending on an aggregate

Considerations

• internal versus external iterators
  • Iterator<E> interface
  • void forEach(Consumer<? super T> action) method
• who defines traversal algorithm?

Iterators

• Based on Iterator Design Patterns

Iterator

public interface Iterator<E> {
	public boolean hasNext();
	public E next();
	public void remove();
}

• iterator() in Collection
• sequential traversal

Enumeration

public interface Enumeration<E> {
	public boolean hasMoreElements();
	public E nextElement();
}

• functionality of this interface is duplicated by the Iterator interface
• new implementations should consider using Iterator in preference to Enumeration

ListIterator

ListIterator
public interface ListIterator<E> extends Iterator<E> {
	public void add(E o);
	public boolean hasPrevious();
	public E previous();
	public int nextIndex();
	public int previousIndex();
	public void set(E o);
}

• listIterator() in List
• forward and backward sequential traversal

Map Iterator

• Iterating through Map views
  • views
    • key set
    • value collection
    • entry set (nested interface Map.Entry)

public static interface Map.Entry<K,V> {
	public K getKey();
	public V getValue();
	public V setValue(V v);
}