Programming 2 Exam Revision
BST Traversal
Traversals are closely related to the operations of finding and searching.
A traversal is an inspection operation which involves processing each node of the tree once.
The Java code for traversal:
public class BinTree {
private BinTreeNode root;
// Behaviour methods
public void addNode(BinTreeNode newNode, ...) { ... }
public void removeNode(...) { ... }
public int getHeight() { ... }
...
In-order:
The traversal order with nodes is as follows: Left, Root, Right.
The Java code for traversal:
public void inOrderTrav(BinaryTreeNode node) {
if ( node == null ) return;
inOrderTrav( node.getLeftChild() );
System.out.print( node.getValue() + “ “ );
inOrderTrav( node.getRightChild() );
} // end inOrderTrav
Pre-order:
The traversal order with nodes is as follows: Root, Left, Right.
The Java code for traversal:
public void preOrderTrav(BinaryTreeNode node) {
if ( node == null ) return;
System.out.print( node.getValue() + “ “ );
preOrderTrav( node.getLeftChild() );
preOrderTrav( node.getRightChild() );
} // end preOrderTrav
Post-order:
The traversal order with nodes is as follows: Left, Right, Root.
The Java code for traversal:
public void postOrderTrav(BinaryTreeNode node) {
if ( node == null ) return;
postOrderTrav( node.getLeftChild() );
postOrderTrav( node.getRightChild() );
System.out.print( node.getValue() + “ “ );
} // end postOrderTrav
BST Notes
A binary tree is full if every level that contains any nodes contains the maximum number of nodes for that level.
A full binary tree has the minimum height for the number of nodes that it has.
The minimum height of a binary tree can be calculated with: n <= 2h - 1
E.g. if there are 6 nodes, n = 6.
If we say h=2: 22 - 1 = 3. 6>≠ 3 so it is invalid.
If we say h=3: 23 - 1 = 7. 6<= 7 therefore, the minimum height is 3.
BST Organising
There are 2 rules for BST's:
1. If L is any node in the left sub-tree of N, then the value of L is less than N
2. If R is any node in the right sub-tree of N, then the value of R is greater than N
The Java code for searching a BST:
while ( key not found and more tree to search ) {
if ( key 'less than' current value ) {
search left sub-tree
}
else {
search right sub-tree
}
}
Deleting a BST node
This is easy if the node is a leaf node otherwise deleting a node is a complex process that requires the rearrangement of large portions of the tree.
The Java algorithm for deleting a BST, non-leaf node is:
if (just one sub-tree of target node is empty) { // another straightforward case
Copy the target node's non-null child pointer to update the relevant child pointer of the parent of the target node
// target node will then get 'garbage collected'
}
else { // this is the 'tricky' case ...
Find the rightmost node (RMN) in the left sub-tree of the target node
Over-write the target node's data with the RMN's data
Let the first node from the RMN's left sub-tree take RMN's place
(i.e. by letting the child pointer of RMN's original parent point to first node)
}
Removing Data:
Removing a value is also quite complicated.
If, after removing a value, the node contains too few keys then it will have to be adjusted.
Nodes may have to gain a value from somewhere else...
A simple movement if there is a "spare" slot in one of the descendant leaf nodes.
If descendant nodes are all as small as they can be, then there will be a need to merge nodes:
We need to check whether there is a knock-on effect from the change made and possibly these operations will have to be applied recursively up and down the tree.
Binary Tree Node Implementation
public class BinTreeNode {
private Object data; // Reference to the node’s data.
private BinTreeNode leftNode; // Reference to the left node.
private BinTreeNode rightNode; // Reference to the right node.
private BinTreeNode parentNode; // Reference to the parent node.
// getters & setters
public BinTreeNode getLeftChild(...) { ... }
public void setLeftChild(BinTreeNode newNode) { ... }
public BinTreeNode getRightChild(...) { ... }
public void setRightChild(BinTreeNode newNode) { ... }
...
}
Binary Tree Implementation
public class BinTree {
private BinTreeNode root;
// Behaviour methods
public void addNode(BinTreeNode newNode, ...) { ... }
public void removeNode(...) { ... }
public int getHeight() { ... }
public void preOrderTrav(BinaryTreeNode node) {
if ( node == null ) return;
System.out.print( node.getValue() + “ “ );
preOrderTrav( node.getLeftChild() );
preOrderTrav( node.getRightChild() );
} // end preOrderTrav
public void inOrderTrav(BinaryTreeNode node) {
if ( node == null ) return;
inOrderTrav( node.getLeftChild() );
System.out.print( node.getValue() + “ “ );
inOrderTrav( node.getRightChild() );
} // end inOrderTrav
public void postOrderTrav(BinaryTreeNode node) {
if ( node == null ) return;
postOrderTrav( node.getLeftChild() );
postOrderTrav( node.getRightChild() );
System.out.print( node.getValue() + “ “ );
} // end postOrderTrav
...
}
OOP
OOP has self-contained objects containing both the programming routine/procedures and the data being processed.
These objects interact by sending data to one another.
In OOP, you write classes that represent real world things and create objects based on these classes.
Classes have attributes as well as procedures (known as methods).
Overloading methods
Constructor methods:
1. Have the same identifier as the class.
2. Are invoked when the new operator is used to create an instance of the class (i.e. to perform object-creation).
3. Perform such tasks as initialisation of variables, and do not return a value.
4. They are also often overloaded.
4.1 - This means that we can have more than one constructor with same name/identifier.
4.2 - But each constructor has different numbers or types of arguments specified in its declaration. (Often referred to as a different method signature).
Instance variables would normally be declared as private so that:
1. They cannot be directly viewed by any outside object.
2. Other objects could only access them via the object's public "get-er" methods (N.B. encapsulation).
If you want an instance variable or method to be only used by inheriting sub-classes, it must be declared as protected in the super-class.
Overriding methods
A sub-class can add to the methods, constants and variables declared in a super-class.
It can also override methods that are declared in the super-class by declaring a new method which has the same name,
visibility and set of formal arguments. (This is NOT the same as overloading!)
Polymorphic methods
Inheritance using the ability to overload and override existing functionality is one of the most important O-O techniques.
It allows existing code to be re-used in a structured way.
Polymorphism allows flexible & robust coding:
Methods with same method-signature can be called to carry out the same operation in bespoke ways.
Abstract classes
Abstract classes are one way for software developers to ensure that any future programmers will only re-use their code in more constrained way.
N.B. Inheritance alone places no restriction on future programmers in terms of whether they will choose override any components of the super-class, or not.
Abstract classes are a way to effectively force future programmers to create methods in any future sub-classes they might create:
1. By declaring a method signature in the super-class with the qualifier abstract and providing no method body.
Code example:
public abstract void addInterest(int r);
Now any inheriting sub-classes must provide an implementation for addInterest to avoid compilation errors
2. Creating an abstract method will mean that the class it is declared in also has to become an abstract class.
Code example:
public abstract class DepositAccount extends BankAccount{...};
An important consequence for the software designer to consider is that Java’s new operator cannot create object instances of any abstract classes – only of its sub-classes
However, in addition to abstract methods (N.B. they have no method body) abstract classes can still have regular methods/variables coded inside them.
So that inheriting sub-classes can still be provided with some existing re-usable functionality, as we have seen before.
Streams and Files
A file can be anything from a disk file to a physical device (screen, keyboard, sound card, sensor etc.)
A stream is an abstraction/interface between the programmer and the file.
File I/O Procedure in Java
Create a stream and associate it with a data source (i.e. the file). This effectively also opens the data source.
Access the stream (read from or write to it).
Close the stream to free up system resources and "flush" any buffered data.
Java Data Streams
Classes managing streams are implemented in the java.io package. Import this package to be able to use I/O classes.
There are two major types of streams in Java:
1. Byte streams:
1.1 - FileInputStream & FileOutputStream
1.2 - DataInputStream & DataOutputStream
2. Character Streams:
2.1 - FileReader & FileWriter
2.2 - BufferedReader & PrintWriter
FileInputStream and FileOutputStream
To create a new FileInputStream:
FileInputStream myStr = new FileInputStream( Filename );
To read from a FileInputStream:
int myByte = myStr.read();
To create a new FileOutputStream:
FileOutputStream myStr = new FileOutputStream( Filename );
To write to a FileOutputStream:
myStr.write( int );
Used to read/write data at low level such as image pixels, implement communication links
DataInputStream and DataOutputStream
Used to read and write Java primitive data types (i.e. boolean, byte, double, float, int, long and short).
It is more abstract than FileInputStream and FileOutputStream.
To create a new DataOutputStream:
DataOutputStream myStr = new DataOutputStream(new FileOutputStream( Filename ));
To create a new DataInputStream:
DataInputStream myStr = new DataInputStream(new FileInputStream( Filename ));
FileReader & FileWriter
Can be used to read and write characters from/to files:
The FileReader class implements:
int read()
int read(char[] cbuf, int offset, int length)
The FileWriter class implements:
void write(int c)
void write(char[] cbuf, int offset, int length)
void write(String str, int offset, int length)
BufferedReader & PrintWriter
Used to read and write characters but more efficiently than FileReader and FileWriter.
The BufferedReader class implements:
int read()
int read(char[] cbuf, int offset, int length)
String readLine()
The PrintWriter class implements:
void write(int c)
void write(char[] cbuf, int offset, int length)
void write(String str, int offset, int length)
void print(String str)
void println(String str)
ObjectOutputStream and ObjectInputStream
These are used to write and read objects to/from files.
They are even more abstract than the IO classes that have been introduced to you so far.
Only objects that are serializable (like nearly all classes defined in the Java packages) can be written/read using these IO classes.
You can mix object types when writing in a file but you must read objects back in the same order that they were written.
Searching & Sorting data from files
Computers are very good at storing large amounts of data and sifting through it of course, someone has to write the ‘sifting’ instructions.
Searching and sorting data are extremely important parts of many, if not most, applications – even many that are not directly thought of as "data processing".
To consider ways in which we can search through data, we will need:
1. A structure to hold some data to search through.
2. Some operations that we can perform on that structure.
3. One or more algorithms or approaches to follow that carries out the 'sifting'.
Common reasons for searching are:
1. To find the maximum/minimum value in a dataset.
2. To find out whether a particular value is present or absent.
3. Sort the entire dataset into some order.
Data structures
A data structure is really a collection of data items organised for efficient storage and processing.
Often it is convenient to define a set of operations on a data structure, so that we can process the data items in a regular and well understood way.
Exactly what the data in a data structure means is not so important to us as programmers!
What is important is that we are able to write?
1. Appropriate code to store the data items in a structure.
2. Code that can also process the data items efficiently.
The combination of data storage and the coding of basic operations to process it, is a Data Structure.
Searching an array
An array is just about the simplest data structure that we can search through.
The array data structure is fairly flexible, but has some restrictions:
1. We can use the very simple operations defined for arrays to perform our search.
2. Data values are all of a known type.
3. Data may, or may not, be ordered.
4. More than one data item might have the same value.
5. We have a maximum amount of data that can be processed at one time.
File I/O and Exception Handling
Java Exceptions
Exceptions are the outcome of run-time errors that are potentially fatal to your program.
In the Java exception handling mechanism, exceptions are thrown in a fatal situation (to allow graceful reporting).
The programmer can choose to deal with exceptions to allow their program to terminate more gracefully or even prevent the termination of their program altogether and deal with the problem (to allow graceful recovery).
Checked and Unchecked Exceptions
Methods throw exceptions that can be checked or unchecked.
Checked exceptions describe problems that are likely to occur due to circumstances outside of the program’s control (corrupt file, end of file, broken network etc).
The programmer should still deal with checked exceptions gracefully. The compiler needs to know what will happen in case a checked exception is thrown.
Unchecked exceptions occur because of the programmer’s fault.
The programmer can choose not to deal with unchecked exceptions.
Catching Exceptions with try…catch
If we have to (or choose to) deal with exceptions we must catch them using a try…catch structure.
Code example:
try {
program’s application statements
}
catch(exceptionClass1 exceptionObject) {
statements that could gracefully deal with exceptionClass1 problems
}
catch(exceptionClass2 exceptionObject) {
statements that could gracefully deal with exceptionClass2 problems
}
...
The finally Clause
Used when some action needs to be taken whether or not an exception occurs.
Code example:
try {
... // Open file.
... // Access file (read/write).
}
catch(IOException e) {
... // Report error to user/logs.
}
finally {
... // Close file or
... // retry or
... // maybe save any data?
}
Passing on Exceptions with the throws
If potential checked exceptions in a method are not handled by that method (using a try…catch structure) then the caller of that method must be informed using the throws specifier (otherwise compilation error):
Code example:
public int[] readNumbers(String filename) throws IOException
{... stmts to read a file of integer data into an array ...}
If potential checked exceptions in a method are not handled by that method (using a try…catch structure) then the caller of that method must be informed using the throws specifier (otherwise compilation error):
Code example:
...
try {
int[] nums = readNumbers(“data.txt”);
}
catch(IOException e) {
System.out.println(“IOException occurred”);
}
...
Creating and Throwing Exceptions
You can throw exceptions using the throw keyword.
Code example:
if(...) {
NumberFormatException e = new NumberFormatException();
throw e;
}
The calling method must then deal with your exception.
Also, you can create your own exception classes that extend (inherit from) any of the existing exception classes.
I/O Hierarchies
Java’s I/O streams are realised as an inheritance hierarchy of classes.
Near the top of the hierarchy are classes that read and write raw data to streams.
As we move down the hierarchy, classes are responsible for more and more sophisticated processing of input and output streams.
Data Structures & Algorithms
Finding the maximum/minimum value
For this example we assume that the whole array is to be searched.
public class Searching {
public int findMaximum(int[] data) {
int result = data[0]; // initialise result
for (int i = 1; i< data.length; i++) {
if (data[i] > result) { // curr value larger
result = data[i]; // update result value
}
}
return result;
} // end findMaximum
} // end class Searching
Searching for a target key value (tKey)
Assume first data item is at element 0, and last item of data is at an array location given by the lastElement argument:
public class Searching {
public int findKey1( int tKey, int[] buffer,
int lastElement ) {
int i;
for (i=0; buffer[i]!=tKey && i <= lastElement; i++);
if (i == lastElement+1) {
return -1; // indicate tKey not found
}
else {
return i; // return tKey position
}
} // end findKey1
} // end class Searching
Using a sentinel value
FindKey1's algorithm can be improved by using a sentinel item to mark the end of the data in the array.
If the sentinel item is given the same value as the target-key itself, we ensure that a ‘find’ will always be successful.
So now we need only test for the target key’s value on each iteration, and we can omit a test for reaching the last data item present.
Code example:
public int findKey2(int tKey, int[] buffer, int lastElement) {
int i;
buffer[lastElement+1] = tKey; // set sentinel
for (i = 0; buffer[i] != tKey; i++);
if (i == lastElement+1) {
return -1; // indicate tKey not found
}
else {
return i; // return tKey position
}
} // end findKey2
Linear searching
Linear searching (in either form) is quite a naive approach to searching through data.
no reliance on particular knowledge about the data, such as ordering.
It is therefore the least efficient approach to searching, but widely applicable.
Classifying algorithmic efficiency – Big O
We can think about how efficient a simple linear search is and express this in Big O notation. Note that:
1. 'On average' we’ll need to read through half of an unsorted list of items to find a particular value.
2. We have to read the entire list to discover that a particular value doesn’t exist.
3. If the size of the list doubles, the number of items we’ll look at doubles.
A linear search is therefore an O(n) operation.
The two linear searches, seen so far, will take different amounts of time to execute, but their performance will always scale in the same way – that’s what Big O shows.
Algorithmic order - summary
Exact performance figures can depend on the data itself.
and the particular executing machine’s spec/performance ...
and any other concurrently-running tasks ...
A formula/equation predicting an algorithm's performance, t(n) derived by inspecting lines of code, may be complex.
But some parts of any such formula will be much more significant than others.
1. As the amount of data (n) increases, usually a single term of any prospective equation for t(n) becomes the dominant factor.
2. Big O retains this dominant characteristic and disregards the rest of any potential terms in the t(n) formula from further consideration.
We call this dominant factor the Order of the algorithm.
Denote the order by using the big O notation e.g. O(1) constant time, O(n) linear time, O(n2) quadratic time.
Iteration & Algorithmic efficiency
Given N items of data to process, e.g. myProcess(N), what would be the order of the following alternative code fragments?
int z=0;
...
public void myProcess(int N) {
for (i=1; i <= 1000000; i++){
... z = z + 1;
} // end for i
}
public void myProcess(int N) {
for (i=1; i <= N; i++){
... z = z + 1;
} // end for i
}
public void myProcess(int N) {
for (i=1; i <= N; i++){
for (j=1; j <= N; j++){
... z = z + 1;
} //end for j
} // end for i
}
Instead of finding max/min values, searching for a target value in a set of data etc.
Bubble sort is just about the simplest algorithm that will take an array of unsorted data and can be used to sort that data into order …
Bubble sort
The structure of the code to carry out a Bubble Sort:
for (int top=lastItem; top > 0; top--) {
for (int i=0; i < top; i++) {
if ( data[i] > data[i+1] ) {
int temp = data[i];
data[i] = data[i+1];
data[i+1] = temp;
} // end if
} // end for i
} // end for top
Note that the Bubble sort algorithm is quite an inefficient sorting technique, requiring several passes through the data being sorted (due to the nested "for" loops in the Java code above).
Bubble sort is an O(n2) algorithm.
This means it is OK for small amounts of data but becomes very slow with large amounts of data.
Many algorithms, not just sorting algorithms, could behave in this way, hence Big O analysis is important!
All algorithms can be subjected to a Big O classification.
Big O notation can be used to discuss different aspects of efficiency.
1. Performance (execution time).
2. Memory usage.
3. Etc.
Linear data structures
The data structures we have seen so far have been based on one of two organising principles:
1. Some variant of the time of arrival as is usually the case with arrays, lists and queues.
2. Array-based data sequenced upon some intrinsic property of the data e.g. priority queues.
Note that priority queues can be constructed using "optimised" linked lists: if the list is a doubly linked list with both a head and a tail pointer and if every linked-list-item has a prevItem pointer.
Priority queues can be constructed easily using a modified linked-list variant: if the list is a doubly linked list i.e. with both a head and a tail pointer; and if every linked-list-item has a prevItem pointer as well as a nextItem pointer.
Non-linear data structures
For many real-world applications these linear organisational schemes don't work.
Consider a manufacturing process that describes how elementary components should be put together to form larger assemblies.
How many levels of sub-assemblies should gather together to ultimately synthesise a final product?
How about the File Manager’s directory (or folder) structure in your PC: The organisation of folders, sub-folders, files etc.
For these kinds problem domains we require data structures that are not linear.
Where there is an implicit hierarchical organisation scheme we use branching Tree Data Structures.
A tree exhibits a one-to-many relationship among its elements.
Trees are the most important non-linear data structure that we use in computing.
Tree Definitions
Nodes are the elements of the tree. A node will contain a key which uniquely identifies that node.
Edges link nodes together. Their orientation reflects the hierarchy between the nodes.
The root node is unique. It has no predecessors and may have many successors.
Leaf nodes are nodes at the end of a branch, and always have a predecessor but no successors.
A path is a distinct sequence of nodes connected by edges.
The path length between any two nodes is the count of the nodes in the path, including end nodes.
Trees are usually described using genealogical terms:
1. Parent is the unique predecessor of every node (except for the root node of course).
2. Child is a successor node.
3. Siblings are nodes that have a common parent.
4. The level of a node is the number of nodes passed through on the path from the root to that node.
Trees are Recursive Structures
When expressed in a binary tree form, it is easier to see that trees are inherently recursive data structures.
Each node can be defined using three qualities:
1. The data pertaining to the node itself.
2. A reference (possibly null) to the left-child node.
3. A reference (possibly null) to the right-child node.
They are particularly well suited to manipulation by recursive code.
Sub-trees
Sub-trees are an important concept. A sub-tree is formed by any node, together with all of its descendants, and with that node acting as the root node of the sub-tree.
In the example, the green nodes form a sub-tree which has ‘B’ as its root node.
Binary Tree
Trees can take many forms but one that is of pivotal importance to computing is the Binary Tree.
This is because any kind of tree structure can be transformed into an equivalent binary tree.
This is an important fact in principle but in practice many applications also require the use of trees that are not binary.
Binary trees form an important sub-class of trees in terms of their use and implementation.
Two significant forms are:
1. A Knuth Binary Tree (KBT) is defined as one where:
1.1 - Each node may have 0, 1 or 2 sub-trees.
1.2 - Each sub-tree is defined as being either the left subtree or the right sub-tree.
2. A Strictly Binary Tree is one in which each node has exactly 0 or 2 sub-trees.
Binary Search & Linked List concepts
Binary Search
For large datasets that are already sorted and stored in an array this can be very effective.
The basic concept is quite simple.
1. Divide the data list into two equal portions.
2. Determine which half might contain the key (this action is termed a probe ): if the target key-item is not found at the mid-point of course.
3. Repeat the process on the appropriate half of the list. This should be easy to determine since data is already sorted !
Binary Search – iterative form
Code example:
public int binarySearch1(int target, int[] buffer){
int top = buffer.length-1, bottom = 0, middle;
while ( top > bottom ) {
middle = (top + bottom)/2;
if ( buffer[middle] < target ) {
bottom = middle + 1;
}
else {
top = middle;
}
} // end while
if ( top == -1 ) // loop was never executed
return -2; // so indicate list is empty
if ( buffer[top] == target ) {
return top; // key successfully found
}
else {
return -1; // indicate key not found
}
} // end binarySearch1
Binary search is efficient for searching large lists. (The algorithm given above can be made even more efficient - for the best case scenario.)
When it is used with smaller lists, the overheads involved may actually mean that sequential search is faster.
The form of the algorithm lends itself to a recursive implementation.
Recursive implementation can be expressed more simply than the iterative form.
Arrays and Computer Memory
When an array is declared, Java creates a reference to the array for example:
int[] myArray;
The elements of the array are created by the new operator and then we are able to load data into the array:
myArray = new int[10];
myArray[0] = 5;
...
Assigning Java references
As Java programmers we know that the new operator can be used to return a reference to the area of computer memory that has been allocated to an array, or object instance of a Java Class etc.
Once created these references can be assigned and reassigned at will for example:
int[] array1;
int[] array2;
...
array1 = new int[10];
array1[0] = 5;
...
array2 = array1;
...
array1 = null;
Costly Operations on Arrays: Creation
Regardless of whether all 10 elements of the array are needed to hold any meaningful data, 10 elements-worth of computer memory are allocated for array1 (in the previous example).
This is no problem if only 10 elements are allocated, but what about if 1,000,000 elements were allocated when the array was created and for most of the program we only use a small amount (say 10-20) of those elements?
Linked Lists & Dynamic Data Structures
The recurring problem with the simple Array data structure in the above examples is that it is not dynamic enough.
An alternative, the Linked List data structure, provides just the sort of dynamism that is lacking in a simple Array.
Minimal linked list usually consists of an (optional) counter, maybe a maxSize, always has a special reference variable called head.
A linked list is then constructed from a more fundamental building block called the linked list item.
Every linked list item is a structured item which is self-referential.
The smallest linked list is the empty list which actually consists of no linked list items at all i.e. counter=0 and head=null.
The next smallest list consists of just a single list-item and so on.
There is no absolute maximum size for a linked list - as new list items are added we simply ask the operating system to allocate more memory to accommodate the new linked list item.
Java’s Garbage Collection
Whenever a Java object is left in a state where there are no valid reference variables pointing to it, the memory occupied by that item of data is released.
The Java Virtual Machine, will then make the freed-up space available for any other programs to use.
This process of identifying un-referenced data items and releasing the memory they once used is called Garbage Collection.
In Java, Garbage Collection is an automatic process!!!
Linked lists, Interfaces, ADTs & Array-based Queues
Linked Lists & Dynamic Data Structures
Linked Lists do not have a maximum length associated with them: the only unavoidable limitation is the size of the executing machine's memory.
We could still choose to associate an arbitrary maximum number of elements to a given Linked List, if we wish.
Consider the Algorithmic Complexity of common operations (add item, delete item, insert item etc).
For example increasing the length of a Linked List, by adding a new data item to the front only involves allocating memory for the new data item, and then a simple update: to make sure that the List head correctly points to it.
Abstract Data Types (ADT’s)
Abstract Data Type (ADT): A specification of the fundamental operations that characterise a data type without supplying an implementation.
The key issue here is that we do not need to know exactly how a type is implemented.
We only require the implementation to adhere to the definition of the type.
Information Hiding is a complementary concept to that of abstraction.
We conceal details of implementation and focus on making only the key properties visible.
This will be an important characteristic of ADTs.
ADTs in Java
In Java, abstractions can be effectively realised using the Class mechanism. We can then:
1. Create new instances using constructor methods.
2. Modify values (or states) by providing arguments to public methods.
3. Inspect values (or states) by providing public methods.
4. Hide implementation using private.
For example for BankAccount we have:
1. Constructors (BankAccount).
2. Modification operations (deposit, withdraw,...).
3. Inspection operations (getBalance).
4. An ADT's set of permitted values is likely to be controlled by these methods, rather than by explicit literal values.
Java interface
We have already been naively using Java interfaces when we were building listener classes for event-handling in our drawing application.
Importantly, the listener interfaces themselves did not implement any functionality.
We had to do the implementation of each interface by coding our implementing listener classes.
Interfaces are similar in some ways to abstract classes.
In an interface though we can only specify public and abstract methods - no implementing functionality is allowed!
In a Java interface, if we don’t explicitly declare a method as public and abstract then this will be assumed for us by the compiler.
The Queue data structure
A Queue is an example of an ordered list, where the ordering criterion for the contents of the queue (its elements) may be:
1. Time of Arrival normally termed FIFO (First In - First Out) e.g. bus/bank/shop queues.
2. Priority of the associated event or data value e.g. hospital casualty debts, disk access in an OS.
For a FIFO queue the items of interest are:
1. The first item (next to be used) also called the head or the front.
2. The last item (where we append additions to the queue) also called the tail or the back.
A Queue ADT, using a Java Interface
In order to ensure consistency of access, regardless of the form of implementation, we often make use of an Interface specification for a queue.
public interface IntQueue {
public boolean isFull();
public boolean isEmpty();
public void enQueue(int element);
public int Serve();
public int getHead();
public int queueLength();
} // end interface class
Queue ADT Operations
The operations for a queue include:
1. Create generates a new queue object.
2. Delete removes an existing queue object.
3. enQueue adds an element to the queue.
4. Serve returns the ‘first’ item from the queue and removes it from the queue.
5. getHead returns the first element, leaving the queue unchanged.
6. isFull - returns true if the queue buffer is full.
7. isEmpty - returns true if there are no elements in the queue.
Interface Pre- and Post-Conditions
In specifying the operations for an ADT, we often employ pre-conditions and post-conditions. These are often placed in a comment block.
Pre-condition defines the state that the ADT has to already be in, in order for the operation to succeed.
Post-condition defines the state that it will have after the operation has completed successfully.
It is the responsibility of the program using the ADT to ensure that the pre-conditions are met.
Code Example:
public void enqueue(int newData);
/* pre: the size of the queue has not reached an upper bound
post: the queue includes the new element as its most
recently arrived element (ie at the back) */
Queue Boundary Exceptions
We do this by creating a new sub-class of RuntimeException.
We can then catch these exceptions in any application/program encounters them when using the queue.
Code Example:
import java.lang.RuntimeException;
...
class QueueBoundaryException extends RuntimeException {
QueueBoundaryException(String message){
super(message);
} // end constructor
} // end class
Implementation with Cyclic buffering
Another way of organising a queue of elements in an array is to use cyclic buffering.
This is a form of organisation by which we manage the front and back indices so that they are more independent of the physical bounds of the array:
the queue data is still ordered from the first item to the last item.
By using this form we avoid the need to copy data along elements of the array each time an item is removed.
but this time at the cost of doing some extra work each time the contents of the queue are modified.
the extra work involves slightly more complex control of the front and the back indices.
Cyclic Buffering by masking
One simple solution is to use the remainder operator, % , (also called the modulus) to always give a reliable cyclic index value for the head and tail values:
we just start initially with head and tail values set as 0 and -1 respectively, even if the array length is, say, 4 (index values 0..3).
then always pre-increment the tail index variable before each insertion, providing queue is not full.
and always post-increment the head index variable after each removal, providing queue is not empty.
we can tell if the queue is empty whenever tail < head.
queue's current size is always tail - head + 1.
queue is full if queueLength()== buffer.length.
Array-based implementation for a Queue
public class ArrayQueue implements IntQueue {
int buffer[];
int head, tail, count;
// constructor
public ArrayQueue(int maxqueuesize){
buffer = new int[maxqueuesize];
head = 0;
tail = -1;
count = 0;
} // end constructor
}
Recursion in program control & data structures
Linked List
Simple size() method:
public int size() {
int count = 0;
LLItem currItem = head;
while(currItem != null) {
count++;
currItem = currItem.getNextItem();
}
return count;
}
Linked Lists & Recursion:
public int rSize() {
return ( recursiveSize(head) );
} // end rSize
public int recursiveSize(LLItem ci) {
if (ci == null) return 0;
else return ( 1 + recursiveSize(ci.getNextItem()) );
} // end recursiveSize
Self Reference: Recursion
A recursive program/method is one which calls itself.
This simply means that somewhere inside the body of the method there is an invocation of the method we are currently in.
This seems to make little sense at first.
Until we realise that each invocation uses slightly different values for the actual arguments.
Not all programming languages allow for this kind of self referential flow of control, but Java is one of the languages that does so.
Recursion can lead to some powerful solutions to various problems.
How recursion works
A recursive method has a least two parts:
1. One or more statement(s) which represent a Base Case.
2. One or more statement(s) which represent a Recursive Case.
Code Example:
public void printAnswer(int n) {
System.out.println("The value of " + n +
" factorial is = " + calcFactorial(n) );
} // end printAnswer
public int calcFactorial(int n) {
if ( n == 0 ) return 1; // tests for Base Case
int factorial = n * calcFactorial(n-1); // recursive call ...
return factorial;
} // end calcFactorial
Recursion as divide and conquer
Recursive processing can be very important when we write algorithms that process large data structures that have a very regular structure.
Each recursive invocation must use actual arguments which makes the problem at hand smaller/easier.
The base case must detect a trivial condition/solution, so that:
1. An answer can be readily stated.
2. The processing which follows a return arrives at the final answer.
Recursive example with Strings
public boolean isPalindrome( String s ){
if ( s.length() <= 1) return true;
else {
if ( s.charAt(0) == s.charAt( s.length()-1 ) )
return isPalindrome( s.substring( 1, s.length()-1 ) );
}
else {
return false;
} // end else
} // end isPalindrome
How can a data structure be recursive?
Essentially by defining the data structure in terms of.
1. A base case structure.
2. A self-referential case.
We could then define, linked list, as follows:
1. Either an empty list.
2. A list consisting of at least one item and the rest of the list.
The list can grow by adding a new item to the front of the list: i.e. the item that was at the front is now the start of the rest of the list.
A data structure defined in this way is not declaring that the data starts and ends at a particular location/element - as is the case for an array.
Part of a Linked List class
public class LinkedList {
// instance variable for the list
private LinkedListItem head;
// constructor
public LinkedList(){
head = null;
} // end constructor
public int size() {
int count = 0;
LinkedListItem currItem = head;
while (currItem != null) {
count++;
currItem = currItem.getNext();
} // end while
return count;
} // end size
some more methods ...
} // end class LinkedList
A Linked List class with recursion
public class LinkedList {
// instance variable for the list
private LinkedListItem head;
// constructor
public LinkedList(){
head = null;
} // end constructor
public int size() {
return recursiveSize(head);
} // end size
public int recursiveSize(LinkedListItem ci) {
if (ci == null) return 0;
else return ( 1 + recursiveSize(ci.getNext()) );
} // end recursiveSize
... some more list-processing methods ...
} // end class LinkedList
Binary Search
Binary search is efficient for searching large lists.
When it is used with smaller lists, the overheads involved may actually mean that sequential search is faster.
The form of the algorithm lends itself to a recursive implementation
Recursive implementation can be expressed more simply than the iterative form.
Iterative code example:
public int binarySearch1(int target, int[] buffer){
int top = buffer.length-1, bottom = 0, middle;
while ( top > bottom ) {
middle = (top + bottom)/2;
if ( buffer[middle] < target ) {
bottom = middle + 1;
}
else {
top = middle;
}
} // end while
if ( top == -1 ) { // loop was never executed
return -2; // so indicate list is empty
}
if ( buffer[top] == target ) {
return top; // key successfully found
}
else {
return -1; // indicate key not found
}
} // end binarySearch1
Recursive code example:
public static int binarySearch2(int tKey, int[]buffer, int bottom, int top) {
int middle;
middle = ( bottom + top )/2;
if ( bottom > top ) return -1; // key was not found
else if ( tKey == buffer[middle] ) return middle; // found it
else if ( tKey > buffer[middle] ) { // recursive search goes on ...
// look to right of middle
return binarySearch2(tKey, buffer, middle+1, top);
}
else {
// look to left of middle
return binarySearch2(tKey, buffer, bottom, middle-1);
}
} // end binarySearch2
Stack ADT
Stack ADT
We can build more complex abstract data types by using the elementary Java features i.e.
Primitive types: characters, integers, floats, booleans etc.
Elementary data structures: strings, lists and arrays (of whichever type).
In each of the above cases there is a very simple set of operations defined for data type.
But with the ability to create abstract data types we can specify more complex data structures for which:
It is the set of valid operations defined for an ADT that is its most distinctive feature not whether a concrete implementation of the ADT consists of character, integer, float ... data items etc.
Using a Stack
A Stack is a form of Abstract Data Type (ADT) that exhibits a LIFO (Last In - First Out) kind of behaviour.
Stacks are often employed in computer software such as operating systems and compilers. Two examples are:
1. Nesting of method (sub-program) calls (a stack is normally used to store 'return' addresses - vital for recursion etc).
2. Intermediate storage of 'results' (e.g. for computation during the evaluation of arithmetic formulae).
Human-centred activities provide a few analogies with stacks:
We often 'stack' items when disassembling equipment for repair, to ensure that we reassemble them in the right order.
Stack ADT operations
The public operations provided by a Stack ADT would usually include:
Create a new stack object.
Delete a stack object.
Push an element on to a stack.
Pop an element from a stack.
Peek the value of the top element, leaving the stack unchanged.
isEmpty to check if the stack is currently empty.
isFull to check if the stack is currently full.
currentSize a useful operation to report how many items present.
If implementing a Stack ADT as a Java class, each of these operations could be realised as a separate public method defined in a Stack interface.
Code example:
public interface Stack {
public boolean isFull();
public boolean isEmpty();
public int currentSize();
public void push(int newData);
public int pop();
public int peek();
} // end Stack interface
private int [] stackArray;
private int top;
public ArrayStack(int arraySize) {
stackArray = new int[arraySize];
top = -1;
} // end constructor
public boolean isEmpty() {
if ( top <= -1 ) return true;
else return false;
} // end isEmpty
public boolean isFull() {
if ( top >= arrayStack.length ) return true;
else return false;
} // end isFull
public int peek() {
if ( isEmpty() )
throw new StackBoundaryException(”Stack underflow");
else return stackArray[top];
} // end peek
ADT specific exceptions
For most ADTs there are two typical exceptional scenarios that frequently recur:
1. Notice that trying to Pop from an empty stack is an erroneous thing to do – there is no Object to be returned. To do so should result in underflow.
2. Also, trying to Push data onto a stack that happens to be full is also an erroneous thing to do – there is no room for the Object to be properly stored by the stack. To do so should result in overflow.
Stack ADT - list-based
Of course there are further alternative ways in which a Stack could implemented.
One of the alternatives is an implementation that uses linked-lists rather than arrays.
In this case:
1. Push requests could be realised using an addToHead(…)list based operation.
Pop requests could be realised using a removeFromToHead(…)list based operation.
The algorithmic complexity in each case is O(1) as the list-based Push and Pop would only ever need to interact with the head element of the list.
Stack data structures
Along with Arrays, Linked Lists, Queues and Trees the Stack is one of the most important and fundamental data structures in Computer Science.
We have already mentioned how the LIFO mode of operation of a Stack is a fundamental component of many computational processes e.g.
When the operating system to correctly and precisely control blocks memory during recursive processing.
The recursive traversal of data structures like Linked Lists and Trees.
Hash Files, Hash Tables & Intro to MVC Design Patterns
Hash Files
Hash files are intended to allow fast random access to logical records without the indexing overheads.
Each record must have a key field.
The file’s physical storage space is divided into regions called buckets.
Each bucket can store more than one logical record.
A logical record is stored in a particular target bucket – determined from its key field value by means of a special hashing function.
A hash function computes a bucket number for each key value stored in the file.
Each record gets stored in the target bucket corresponding to the hash of its key.
The number of buckets available in a hash file plays an important role in its effectiveness.
The total number of buckets in a file is usually specified as a large prime number.
Collisions
Collision: The case of two keys hashing to the same bucket.
This can be tolerated while there is enough room for logical records in the target bucket but causes within-bucket sequential search problems also arise when a bucket becomes full.
Future colliding records may have to be stored in a separate overflow area requiring pointer-following and more search time.
Solutions:
Increase number of buckets and then rehash all data.
Have expandable variable size buckets – still requires within-bucket sequential search.
Use overflow buckets for full target buckets to point to.
Collisions not usually a major problem while typical hash files are less than 75% full.
Hash files therefore often need to waste some space in a trade-off for speed of access!
Collisions inevitably start to occur as more data gets added to the hash-file.
For example, starting with an empty hash-file of 41 buckets inserting records one at a time:
First record hashes to an empty bucket with probability 41/41 = 1
Second record hashes to an empty bucket with probability 40/41
Third record hashes to an empty bucket with probability 39/41
Fourth record hashes to an empty bucket with probability 38/41
Fifth record hashes to an empty bucket with probability 37/41
Sixth record hashes to an empty bucket with probability 36/41
Seventh record hashes to an empty bucket with probability 35/41
BUT eighth record hashes to an empty bucket with probability 34/41
Overall probability of avoiding collisions after just 8 records added:
(41/41).(40/41).(39/41).(38/41).(37/41).(36/41).(35/41).(34/41) = 0.482
I.e. probability that a collision has occurred = 1 – 0.482 = 0.518
Hash Tables
The Hashing technique described above can also be used to find elements in a data structure without having to perform any linear search (recall searching in lists).
HashSets and HashMaps specifically utilise this technique.
In both structures, elements are stored in a hash table.
Think of a hash table as a kind of array and the hash code of an element as the index for the element in the array.
The hash code of an object (an integer value) is produced by a hash function in such a way that different objects are likely to produce different hash codes.
In the simplest implementation the hash code can be used as the index to the hash table.
However, this would require the creation of very large hash tables that (in some cases) would only be sparsely populated.
Instead hash tables of smaller sizes (than the number of all possible hash codes) are created and hash codes can be reduced in order to fall within the hash table bounds.
Searching a Hash Table
Algorithm for finding an object x in a hash table:
Compute the hash code (using a hashCode() method) and reduce it modulo(%) the table size.
all done in the search method of the data structure.
this results in an index i into the hash table.
Search through the elements of the bucket (perhaps a linked list) found at position i.
If a match is found among the elements of the bucket then item x is in the data structure, otherwise it is not present.
Hash Table Operations
The computational complexity of adding, finding and removing an element from a hash table depends on how it is populated.
In the best case, all buckets will contain either 0 or 1 element(s). This is the case with no collisions and all three operations mentioned above will take O(1) time.
In practice the number of buckets should be around 1.3x larger than the number of elements intended to be stored in the hash table.
The competing concerns in making this choice are the number of collisions and the amount of allocated memory.
Model-View-Controller (MVC) Design
MVC Design Pattern
Model:
1. The data (i.e. system’s state).
2. Methods for accessing and modifying state.
View:
1. Renders contents of model for user visualisation.
2. When model changes - view may need to be updated.
Controller:
1. Translates user actions (i.e. interactions via the view) into operations on the model.
2. Example user actions: button clicks, menu selections etc
MVC with Java/Swing
View:
- Would usually be realised using an over-arching JFrame and then all of the accompanying GUI components and their layouts (recall that for the DrawingApplication we tried to confine much of this to the application’s constructor method?).
Controller(s):
- Take the form of Java’s listener classes. Recall that we wrote many inner-class listeners and attached instances of them to individual GUI components.
Model:
- A separate Java class for data structures (maybe even a DB).
MVC Problems
Controllers sometimes need to produce their own outputs and responses from the user.
E.g. pop-up menus or Dialogue boxes.
Some aspects of system state are shared between Controller and View – without being part of the Model.
Some Java GUI components allow direct user control without Controller intervention.
E.g. moving the slider on a JScrollbar.
In each of the above cases the issue is the degree of overlap between the roles of the View and Controller software design concepts.
So many Java MVC implementations relax the need for these two to be crisply separated.
MVC Adherence
One good way to check if the Model is properly isolated from the View or View-Controller is to try it out with a completely different model of user interaction (UI).
E.g. can it be operated by a program using console directed input/output?
More complex/long-running Model processes may necessitate the need to develop a multi-threaded application to prevent GUI-locking?