Soft Dev 3

• A byte stream manages bytes of raw binary data
• The classes that handle such streams are in two hierarchies– InputStream and its descendant– OutputStream and its descendants
• System.out and System.err are PrintStreams,– ... which is a subclass of FilterOutputStream, – ... which is a subclass of OutputStream and by default map to the same window on screen. – They have print and println methods
• System.in is a generic InputStream, but is usually mapped into a stream that offers more functionality

• A character stream is designed to deal with 16-bit Unicode characters
• Input is handled by the class Reader and its descendants
• Output is handled by the class Writer and its descendants

• To read from the keyboard you can use the java.util.Scanner class– with System.in as parameter
• Within a line it works on tokens :
• – sc.hasNext() checks if there are more tokens
• – String s = sc.next(); // next (string) token
• – String s = sc.nextLine(); // the full line
• – int i = sc.nextInt(); // next int token

• We will first discuss how to read a text file
• To read a file we must:
• – open the stream to the file
• – read the data item by item into variable(s)
• – close the stream to the file
• To read/write text we use character streams
• To achieve this we use a FileReader which is a subclass of an InputStreamReader

• An exception is an unexpected event occurring during execution of a program
• Many of the IO methods throw an exception– for example, if the given file name does not exists– in most cases they throw an IOException
• This is especially the case for input streams
• Any method using these classes must either– be declared to throws IOException, or– must catch and handle the exception itself
• An uncaught exception terminates the running program

• public void readTextFile(String filename){ try{ FileReader fr = new FileReader(filename);
• BufferedReader br = new BufferedReader(fr);
• String line;
• while(br.ready()){ line = br.readLine();
• System.out.println(line);
• } // end of while loop br.close();
• } // end of try clause
• catch(Exception e){ // this will catch any exception System.out.println(e.getMessage());
• } // end of catch clause
• } // end of method

• readLine() returns the complete line of the text file
• We can use a StringTokenizer to separate each of the tokens in this line
• By default this is each word– i.e. white space as delimiter– but other delimiters can be specified
• For example, we can count the number of words in a file

• public int count(String filename) throws Exception{
• FileReader fr = new FileReader(filename);
• BufferedReader br = new BufferedReader(fr);
• String line;
• StringTokenizer st;
• int count = 0;
• while(br.ready()){ line = br.readLine();
• st = new StringTokenizer(line);
• while (st.hasMoreTokens()){
• st.nextToken();
• count++;
• } // end inner while loop
• } // end of outer while loop br.close(); return count;} // end of method
• The wrapper is the parse part

• Sometimes we want to convert a string to a primitive type– e.g. if we want to read in a price of something, then we may want to use an int
• A wrapper class wraps such a primitive type.
• Examples include Character, Integer and Double
• These have method to convert a string to the primitive type they wrap, e.g:18int val = Integer.parseInt(string);
• double d = Double.parseDouble(another_string)

• Writing a string into a text file is similar to reading a file
• Create a BufferedWriter object using a FileWriter object– the FileWriter accepts a filename as argument
• Write the given string to the BufferedWriter object
• close the stream

• public void writeTextFile(String filename,String content){
• try{ FileWriter wr = new FileWriter(filename);
• BufferedWriter bw = new BufferedWriter(wr);
• bw.write(content);
• bw.close(); }
• catch(Exception e){ System.out.println(e.getMessage()); }}

• Data files are of bytes (binary) rather than characters
• We can save an entire object to a file
• When an object is saved, all referenced objects are also written to the file
• This object (and all objects referenced) must be serialisable, i.e. the class has to implement the java.io.Serializable interface (and that’s all extra code you have to add to this class):
• import java.io.Serializable;
• public class MyClass implements Serializable { .... }

• To write a serialisable object to a file you can use an ObjectOutputStream.
• FileOutputStream fos = new FileOutputStream(filename);
• ObjectOutputStream oos = new ObjectOutputStream(fos);
• oos.write(object);
• oos.close();

• To read a serialisable object to a file you can use an ObjectInputStream. 
• To write the object you can use the readObject() method
• readObject() returns an Object (which all objects inherits)– you must then cast this object to the correct type
• FileInputStream fis = new FileInputStream(filename);
• ObjectInputStream ois = new ObjectInputStream(fis);
• MyClass m = (MyClass) ois.readObject();
• ois.close();

• We measure the program in the worst possible running time
• long before = System.currentTimeMillis();
• program(n);
• long after = System.currentTimeMillis();
• long time = after - before;

• In Big-Oh we try to write the functions in the simplest terms
• The following rules are used to simplify terms– drop lower-order terms– drop constant factors
• For our example: 6N+5– we drop the lower-order term 5 (left with 6N)– we drop the constant 6 (left with N)– meaning it is expressed by the linear function O(N)

• An Abstract Data Type (ADT) is an abstraction of a data type specifying– data stored– operations– error conditions
• Example coffee shop:–
• Data is money, coffee, customer
• Operations are: take_order(customer), make(coffee), ...
• Error conditions: no_money, no_coffee, ...

• • The data is the type of elements stored•
• Main operations: push(object) - adds object to the top of the stack–
• pop() - remove and returns element at the top
• Auxiliary operations– top() - return element at top 
• size() - return number of elements– isEmpty() - check if empty 
• Error conditions: pop/top of empty stack

• public interface Stack {
• public int size();
• public boolean isEmpty();
• public Object top() throws StackException;
• public void push(Object element);
• public Object pop() throws StackException;}

• We can re-implement our stack using generics
• Instead of using an Object we now use a generic type <E>
• public interface Stack<E> {
• public int size();
• public boolean isEmpty();
• public E top() throws StackException;
• public void push(E element);
• public E pop() throws StackException;}

• The data is the type of elements stored
• Main operations– elements enter a queue at the rear and are removed from the front–
• enqueue(object) - adds object to the rear of the queue 
• dequeue() - remove and returns element at the top
• Auxiliary operations– front() - return the front element 
• size() - return number of elements
• isEmpty() - check if empty
• Error conditions: dequeue/front of empty queue

• We use generics to represent the Queue interface
• The type Object is replaced by the E and the casting is no longer needed
• Similarly to stacks, we throw a QueueException when accessing an empty queue public interface Queue<E> {
• public int size();
• public boolean isEmpty();
• public E front() throws QueueException;
• public void enqueue(E element);
• public E dequeue() throws QueueException;}

(capacity - front + rear) % capacity

• We have previously learned about wrapper classes for the Java primitives such as Integer and Character
• Java will automatically convert a primitive to it’s wrapper class when required, and this is called autoboxing. E.g.: Integer i = 1;Character c = ‘c’;
• The dual, i.e. converting a wrapper class to it’s primitive is called unboxing, and is automatically applied when the wrapper class is:-
• passed as an argument expecting the primitive
• assigned to a value expecting the primitive
• public Integer myfun(int arg){ .... }Integer i = 10; // autoboxing
• int x = myfun(i) // unboxing (twice)

• • Using Generics we can generalise this algorithm to any class which have a key we can compare with
• • Comparable is an interface (in java.util) containing one method:public interface Comparable<T>{public int compare(T o);}
• • This method should give a natural order of the objects compared, and returns:
• a negative number if this < o
• 0 if they are considered the same
• a positive number if this > o

• public interface Comparator<T>{public int compare(T o1,T o2);}
• This method should give a natural order of the objects compared, and returns:
• –a negative number if o1 < o2
• – 0 if they are considered the same
• – a positive number if o1 > o2

• Bubble/insertion sort - o(N^2)
• selection sort - o(N^2)
• Binary search - o(Log N)
• Merge Sort - o(n log n) is a divide and conquer algorithm
• Quick sort - o(n log n)

• Requires sorted list
• • Step cases?
• – smaller than means search bottom half
• – greater than means search top half
• public Person binarySearch(int age,int first,int last) throws NotFoundException{ if (middle_age == age) // success case return arr[middle];
• else if (age < middle_age) // bottom half return binarySearch(age,first,middle-1) else // top half return binarySearch(age,middle+1,last) }}

• A recursive method is a method that calls itself
• The parameters are changed for each call, and in the method we separate between two types of cases
• The base case is where the method does not call itself
• The step case are values where the method call itself

• • To generalise we –replace the Person class with a generic D (for data), –and the age int with a generic K (for key) We need to compare an element with a key
• • This can be achieved with the compareTo method in the Comparable interface
• Meaning that D must implement Comparable<K>– using Generics we can write this using the extends keyword

• public class LinearSearch<D extends Comparable<K>,K>{
• public D linearSearch(D[] arr,K key) throws NotFoundException{
• for(int i = 0; i < arr.length; i++){
• if(arr[i].compareTo(k) == 0) return arr[i]; }
• throw new NotFoundException ("No element found"); }}

• Is the inverse of the bubble sort
• All items on the left of the current item being compared

• public static void insertionSort(int [] list)
• {// iterates throw the array
• for(int i = 0; i < list.length; i++)
• { int cur = list[i]; // select current elements
• int j = i - 1; // start at element before current element
• // find the correct place and move each element forward
• while(j >= 0 && list[j] > cur) list[j+1] = list[j--];// add the element to the correct place list[j+1] = cur; }

• public class InsertionSort<E extends Comparable<E>> {
• public void insertionSort(E[] list)
• {// iterates throw the array
• for(int i = 0; i < list.length; i++)
• {E cur = list[i]; // select current elements
• int j = i - 1; // start at element before current element
• // finds the correct place and move each element forward
• while(j >= 0 && cur.compareTo(list[j]) < 0)
• list[j+1] = list[j--];// add the element to the correct place
• list[j+1] = cur; } }}

• Quick-Sort is another Divide-and-Conquer algorithm
• 1. Divide: select an element x from S which is called the pivot (often the last element of S).
• Divide S into 3 sub-lists:
• • L storing elements of S less than x
• • E storing elements of S equal to x
• • G storing elements of S larger than x
• 2.Recur: Recursively sort L and G
• 3.Conquer: Put back elements in the order of first elements of L, then elements of E, then elements of G.

• A hash map is a map implemented using a hash table. It consists of
• • a hash function h
• • an array (called table) of size N
• The hash function h turns a key into a value between 0 and N-1
• It is used to compute the index of the array in which to store the value
• Sometimes h will compute the same value for different keys
• Dealing with these cases are called collision handling

• Ways of handling collisions are separate chaining and linear probing:–
• Separate chaining: Each element of the array can store multiple elements.
• •E.g. an array of ArrayLists. When there is a collision, multiple elements are store at the same index
• –Linear probing: When there is a collision the next free index of the array is used.

• Union of two sets A and B, written A ∪ B, which are all the elements in A or B
• Intersection, written A ∩ B, which are all elements in A and also in B
• Subtraction, written A B, which are all elements in A but not in B–
• Subset, written A ⊆B, which holds (returns a boolean) if all elements of A are also in the set B, 2

• Consists of a sequence of nodes containing links to the next node and the element of that node
• The list has a head and a tail pointer that point to the first and last node of the  list
• The last element of the list points to null

• Allocate a new node
• 2. Insert new element
• 3. Have new node point to old head
• 4. Update head to point to new node

• Allocate a new node
• 2. Insert new element
• 3. Have new node point to null
• 4. Have old last node point to new node
• 5. Update tail to point to new node

Move the header pointer to the new head node and allow the computer to deal with the old head

• Move the tail pointer to new node
• Have the new node point to null

• Consist of a sequence of nodes, each node has
• a link to the previous node,
• a link to the next node
• and the element it holds
• and has a header and trailer node instead of pointer

• Consists of a list of singly linked nodes
• Last node links to first node
• Has a cursor node that points to current node

• Root: node without parent 
• Internal node: node with at least one child 
• External node (a.k.a. leaf ): node without children 
• Ancestors of a node: parent, grandparent, grand-grandparent, etc.
• Descendant of a node: child, grandchild, grand-grandchild, etc

• Algorithm preOrder(v)
• visit(v)
• for each child w of v preorder (w)

• Algorithm postOrder(v)
• for each child w of v
•     postOrder (w)
• visit(v)

• Algorithm inOrder(v)
• if hasLeft
•    (v)inOrder
• (left (v))visit(v)
• if hasRight (v)
• inOrder (right (v))

• Each internal node has at most two children (exactly two for properbinary trees)
•  The children of a node are an ordered pair

•  The BinaryTree ADT extends the Tree ADT, i.e., it inherits all the methods of the Tree ADT
•  Additional methods:
•  position left(p)
•  position right(p)
•  boolean hasLeft(p)
•  boolean hasRight(p)
•  Update methods may be defined by data structures implementing the BinaryTree ADT

•  A priority queue stores a collection of entries
•  Each entry is a pair (key, value)
•  Main methods of the Priority Queue ADT
•  insert(k, x) inserts an entry with key k and value x
•  removeMin() removes and returns the entry with smallest key
•  Additional methods
•  min() returns, but does not remove, an entry with smallest key
•  size(), isEmpty()