Home | Previous | Next |
---|
CSC205::Lecture Note::Week 08
Assignments |
Code |
Handouts |
Resources |
Email Thurman {
compufoo::Twitter |
Facebook |
YouTube}
GDT::Bits::
Time
|
Weather
|
Populations
|
Special Dates
[exceptions]
TestExceptions.java |
Xception.java |
BlastOff.java |
AmusementRide.java
[interfaces]
InterfaceExample.java |
InterfaceEG.java |
{I_ExitStatus.java |
TestI_ExitStatus.java}
[more interfaces]
TestSerializable.java |
{TestClone.java |
CloneableEG.java}
CSC205_Containers
[multi-dimensional arrays]
TwoDimensionalArrays.java |
BYTES.java |
ThreeDimensionalArray.java
[memory/heap/stack]
Memory.java
[static main() methods]
Main.java
[list]
#IntList.java |
[stack]
NumberSystemStack.java |
Stack.java |
ParenChecker.java |
Stack2.java
[queue]
Queue.java |
FootNotes.java
(footnotes.in.txt) |
Q.java |
TestQ.java |
PriorityQueue.java |
CircularArrayQ.java
Exceptions are "exceptional" conditions that can occur while a program is executing (i.e. running). Some exceptions are caused due to software defects (e.g. using a
null
object handle, or indexing beyond the bounds of an array).String s = null; String s1 = "hello"; ... if (s.equals(s1)) { ... } //this will cause an exception ... int[] array = new int[10]; ... array[array.length] = 200; //this will cause an exceptionExceptions are also generated by errors that are beyond the control of the program (e.g. the program needs to access a file that doesn't exist, or the program needs to fetch a webpage given an invalid [mal-formed] URL).
Exceptions can be "caught" by programs, but if an exception does occur that isn't caught, then the program (assuming it is non-graphical) terminates. (A GUI program returns to the user interface).
Exceptions are objects that are created from the
Exception
andRuntimeException
classes.Throwable | Error Exception ..... / ... \ IOException RuntimeException (checked) (unchecked)There are two categories of exceptions: checked and unchecked. Checked exceptions must be caught (otherwise, your program will not compile). Unchecked exceptions typically are not caught (i.e. they cause your program to terminate when they occur).
A method can
throw
an exception when it encounters a situation it cannot handle. There are numerous methods that come with the JCL (java class library) that throw exceptions.A method declaration must contain a list of the the checked exceptions it may throw.
public int someMethod() throws IOException, MalformedURLExceptionA method does not need to declare
RuntimeException
inherited exceptions that it may throw.If a method overrides a method from a parent class, then the child method cannot throw more checked exceptions that the parent method does.
A method can say it throws exceptions that it really doesn't throw.
Catching an Exception
Whenever a method is called that throws a checked exception, then that method call must be called from within a
try
block and an exception handler (catch
block) must be implemented.try { ... someMethodThatThrowsIOException(); ... } catch (IOException e) { ... }If an exception occurs, then the flow control of the program jumps to a catch block. All remaining statements, if any, within the try block are skipped. If no exception is thrown, then the catch blocks are skipped.
A
try
block must be a compound statement. Ditto for thecatch
blocks.The
catch
blocks are passed an argument: a reference to the exception (which may or may not be used).Throwing an Exception
An exception is thrown as follows.
throw new EOFException(); or throw new EOFException("file's empty"); //supply additional information about the exception //this information can help the client "fix" the problemA method that throws an exception does not return to the caller.
An exception can be re-thrown. You may want to do this in the event an exception occurs: you catch it locally to clean up any locally allocated objects and/or system resources, and then "pass" the exception on to those who know about handling it.
Exception
A
can be caught, and exceptionB
can be thrown.Creating an Exception Class
You can create your own exceptions by extending
Exception
or some child class ofException
.class MyException extends Exception { public MyException() {} public MyException(String msg) { super(msg); } }Terminology
The following exception terminology was obtained from Just Java by Peter van der Linden:
Note Java Other Languages An error condition that happens at run time Exception Exception Causing an exception to occur Throwing Raising Capturing an exception that has just occurred, and executing statements to resolve it in some way Catching Handling The block that does this Catch clause Handler The sequence of call statements that brought control to the method where the exception happened Stack trace Call chain Miscellaneous Comments
Detect errors at a low level, handle them at a high level.
Use exceptions only for exceptional situations.
YouTube.com::CS 61B Lecture 14: Exceptions
{TopOfPage} {Oracle.com::API Specification | Tutorial} {Derek Banas Videos} {Data Structure Visualizations}
From the The Java Programming Language by Arnold, Gosling, Holmes.
The fundamental unit of programming in Java is the class, but the fundamental unit of object-oriented design is the type. Interfaces define types in an abstract form as a collection of methods or other types that form the contract for that type.An interface is defined using the keyword
interface
rather thanclass
.An interface contains no instance variables, nor does it contain any method implementations. You cannot create instances of an interface.
interface Foo { ... } //! Foo f = new Foo(); // not legalAn
interface
can declare three kinds of members:
- constants
- methods
- nested classes and interfaces
All interface members are implicitly
public
.A
class
guarantees to implement the methods of an interface by using theimplements
keyword when the class is defined.class X implements YAny class that implements an
interface
must define (i.e. implement) the methods, if any, declared in theinterface
.A class can implement more that one interface. In addition, a class can extend another class and still implement one or more interfaces.
class X implements Y, Z { ... } class X extends A implements Y, Z { ... }To an extent, interfaces support the concept of multiple inheritance.
Common interfaces from the
java.lang
package:
Enumeration
-- class must implement thehasMoreElements()
andnextElement()
methodsCloneable
-- class must implement theclone()
methodRunnable
-- used with threads; class must implement the therun
methodAn interface can be used to "tie" together classes that are in separate inheritance trees.
Object | Assignment Interface: Submitable | Exam Program Homework ... ... ... Object | Game Interface: Submitable | Guessing Yahtzee Blackjack ... ... ....An interface can be used to encapsulate a collected of related manifest constants (i.e. simulate an
enum
in C).interface ExitStatus { int EXIT_SUCCESS = 0; int EXIT_FAILURE = 1; }When an
interface
declares named constants, then they are implicitly defined to bepublic
,static
, andfinal
. [blank finals are not allowed]Methods declared in an interface are implicitly
abstract
.An interface can extend (i.e. inherit) other interfaces.
interface Sortable { ... } interface Searchable { ... } interface Container extends Sortable, Searchable { ... }Any class that implementsinterface Container
must also implement theSortable
andSearchable
interfaces.Although you cannot instantiate an object using an interface, you can use an interface as the type for variable and assign to that variable any object whose class implements the interface. This allows for polymorphic run-time binding.
interface Container { ... } class List implements Container { ... } List list = new List(); ... Container c = list; // list is a containerFrom a naming convention perspective, many interfaces have a -able suffix applied to them.
{TopOfPage} {Oracle.com::API Specification | Tutorial} {Derek Banas Videos} {Data Structure Visualizations}
Any object that implements the
Serializable
interface can be turned into a sequence of bytes that can be restored fully into the original object.Benefits.
- don't have to worry about data representation
- don't have to worry about byte ordering
The
Serializable
interface is used as a flag -- it has no methods. Some objects may not want to be serialized.To serialize an object you create some sort of
OutputStream
object and wrap it inside anObjectOutputStream
object. Then, the object can be serialized by callingwriteObject()
. Reversing the process is accomplished by creating anInputStream
inside aObjectInputStream
and calling thereadObject()
method.When an object is serialized, so are all the references it may contain to other objects.
- Object Serialization (java1.1) * useful for saving the state of an application/applet * objects serialized/deserialized with ObjectOutputStream and ObjectInputStream, respectively, using the writeObject() and readObject() methods * primitive types written to stream as if using DataOutputStream; otherwise, writeObject() is called recursively to serialize other objects (arrays, strings, objects) -- infinite recursion is not a problem (so they say); can end up with an entire graph object serialized * not all objects can or should be serialized * a class is serialable iff it implements Serializable (or Externalizable); no methods defined -- it is a marker interface * Component implements Serializable; thus, all AWT components can be serialized * transient indicates that a field should not be serialized * custom serialization is accomplished by overriding writeObject() and readObject(), and by using defaultWriteObject() and defaultReadObject() -- note: they must be declared private * classes are assigned a version # -- cannot deserialize a class that has a different version # than what was used when it was serialized; 'serialver' program + static final long serialVersionUID = 19971209L; * serialized applets + <applet code=appletName.ser ...> + applets can be shipped in a pre-initialized state * Externalizable + ObjectOutputStream and ObjectInputStream use the writeExternal() and readInternal() methods instead of writeObject() and readObject(); allows the class to take complete control over writing/reading their state
{TopOfPage} {Oracle.com::API Specification | Tutorial} {Derek Banas Videos} {Data Structure Visualizations}
Objects cannot be cloned unless they are created using a class that implements the
Cloneable
interface.For a class to use the default implementation of
Object.clone()
, it must implement theCloneable
interface.The
Cloneable
interface is an empty interface -- it is used as a tag only. In many cases, classes that can be cloned overrideObject.clone()
.
Object.clone()
does a bit-wise copy, which works fine for primitive types, but not necessarily with references. Only individual classes know how to be cloned (if at all). By default, a shallow copy is done versus a deep copy.If an attempt is made to clone an object that is not cloneable, then the
CloneNotSupportedException
exception is thrown. This is a checked exception; therefore, it must be caught.It is common for cloneable classes to override
clone()
so as to make itpublic
rather thanprotected
.The Population class extends class X (which is cloneable), and it contains numerous primitive types and a bunch of object references: try { Population p = (Population)super.clone(); p.name = new String(getName()); p.growthRate = (GrowthRate)growthRate.clone(); p.density = (Density)density.clone(); return p; } catch (CloneNotSupportedException e) { return null; }From the CoreJava book.
Why clone? You never want to return a mutable object as the value of a method because this violates encapsulation. As a rule of thumb, always use
clone
whenever you need to return a copy of a mutable data field.When you start dealing with objects instantiated from classes that you do not know well, then how they clone becomes an unknown.
Here is an example of a program that will result in the throwing of a
CloneNotSupportedException
.class A { int a; public A (int i) { a = i; } public Object clone() throws CloneNotSupportedException { return super.clone(); } } public class Main { public static void main(String[] arg) { A a1 = new A(260); try { A a2 = (A)(a1.clone()); } catch (CloneNotSupportedException e) {} } } The execeptions occurs because class A calls Object.clone(), but it does not implement the cloneable interface.
{TopOfPage} {Oracle.com::API Specification | Tutorial} {Derek Banas Videos} {Data Structure Visualizations}
A list is a linear data structure whose components can only be accessed sequentially, one after another.The first item is a list is called the head or front and the last item is called the tail , back or end.
Lists have the following features:
List operations include:
- varying lengths (a list grows when items are added to it, and it shrinks when items are removed)
- homogeneous components (e.g. list of integers, list of prime numbers, list of
string
objects)- sequential access to components via a list cursor
- define a list
- check if a list is empty
- check if a list is full
- reset (move list cursor to front of the list)
- advance the list cursor
- end-of-list (move list cursor to back of the list)
- get current item
- insert before current item
- insert after current item
- remove item
GDT::Java::Code::GoofyIntList.java
{TopOfPage} {Oracle.com::API Specification | Tutorial} {Derek Banas Videos} {Data Structure Visualizations}
A set is a basic building block of mathematics and is a collection of objects (e.g. integers, real numbers, boolean values, geometric points, strings, records, etc.).
The objects of a set are called elements (or members).
A set the following properties:
- all elements of a set belong to some universe
- any object of the universe is either in a set or it is not
- there is no particular ordering of elements within a set
Example of sets:
- a set of classes that a student it taking
- a set of email addresses in an adress book
- a set of prime numbers
The following operations are performed on a set:
- construct (i.e. define/create/instantiate) a set
- check to see if an object is a member of a set
- test if a set is empty
- get the cardinality (size of a set; number of elements/members)
- check if set A is included in set B (if so, then A is subset of B and B is superset of A)
- determine union of two sets (all elements appearing in A or B)
- determine intersection of two sets (all elements appearing in A and B)
- difference between to sets (all elements of set A not in set B -- notation: A - B)
- add an object to a set
- remove an object from a set
- clear all objects from a set
An array (i.e. vector) can be used to store a set.
A class that is used to represent a set could have the following instance methods:
Set(); Set(int capacity); boolean isMember(Object element); boolean isEmpty(); boolean isSubset(Set other); int size(); Set union(Set other); Set intersection(Set other); Set difference(Set other); void add(Object element); void remove(Object element); void clear();
{TopOfPage} {Oracle.com::API Specification | Tutorial} {Derek Banas Videos} {Data Structure Visualizations}
A stack is a data structure in which all access is restricted to the most-recently-inserted elements (LIFO: Last-In-First-Out).
My favorite real world example of a stack is a salad bar. Typically, at the start of the salad bar line is a stack of plates and normally you take the top-most plate (unless it is dirty or has some type of foreign looking object on it, in which case you dig down and take a plate from somewhere lower in the stack [atypical stack behavior]). In actualality, a stack is the wrong way to store plates at a salad bar because of the following scenario: The dishwasher cleans the dirty plates, brings them out front to the salad bar, and pushes them on top of the stack -- now John Q. Customer comes up and is stuck using a hot plate.
A stack has three natural operations: insert, delete, and find; but in stack terminology these operations are called push , pop and top .
Elements are inserted onto a stack by using a push operation.
Elements are deleted from a stack by using a pop operation.
The most-recently inserted element can be examined by using a top operation.
Stacks are heavily used in system software (e.g. compilers). A stack can be used to check for unbalanced symbols (e.g. (), {}, []). Example algorithm:
- create an empty stack
- read symbols until EOF
- if the symbol is an opening symbol, push it onto the stack
- if the symbol is a closing symbol and the stack is empty, then report an error
- otherwise, pop the stack (if symbol popped is not the corresponding opening symbol, then report an error)
- at EOF, if stack is *not* empty, then report an error
A stack is used to implement function (method) calls in most languages. For example in C++, when a function is called, memory for parameters and locally defined variables is allocated from the stack. When the function returns, the memory for the parameters and local variables is de-allocated from the stack. In addition, "jump" information and return value data is stored on the stack.
Stacks are also used in the evaluation of expressions (e.g. operator precedence parsing).
{TopOfPage} {Oracle.com::API Specification | Tutorial} {Derek Banas Videos} {Data Structure Visualizations}
A queue is a data structure in which all access is restricted to the least-recently-inserted elements (FIFO: First-In-First-Out).
Operations are:
enqueue
-- insert at the back of the line (append)dequeue
-- remove from the front of the linefront
-- access item from front of the lineExamples of a queue: buffered input and a line printer spooler.
Another queue example: message queues.
{TopOfPage} {Oracle.com::API Specification | Tutorial} {Derek Banas Videos} {Data Structure Visualizations}
A priority queue allows the highest priority element to be removed from a queue even though it may not be the "oldest."
Real world example of a priority queue: You go to a restaurant with a friend that has a wait. There are a number of queues: a queue for two person table, a queue for a four person table, and a queue for large party table. You are placed on the queue for a two person table. There are three "elements" ahead of you. In comes a VIP with a friend. The next two person table that opens up is given to the VIP.
An operating system may use a priority queue when scheduling jobs. By default, each job is given the same priority. CPU access is granted using a queue (first come, first served). In certain cases, however, you may have a job that needs to get more CPU usage. In those cases, it will be given a priority higher than the default. The OS will use a scheduling algorithm to ensure the higher priority job gets the CPU with more frequency.
{TopOfPage} {Oracle.com::API Specification | Tutorial} {Derek Banas Videos} {Data Structure Visualizations}
A linked list is a low-level structure upon which high-level data structures can be built (e.g.
stacks
andqueues
can be implemented using a linked-list).To date, we have grouped program data using the following ADTs (Abstract Data Types, or User Defined Types): array,
class
),Vector
, set, list, stack, and queue (and priority queue).Sometimes the only ADT available for organizing data is the built-in array; however, this can be problem if the the elements of the array need to be stored in some sort of order and elements are going to be inserted and deleted from the array. In these cases a linked-list may be the solution.
A linked-list is a collection of records, called nodes, each containing at least one field (member) that gives the location of the next node in the list. In the simplest case, each node contains two members: a data member (the data value of the list item) and a link member (a value locating the next node).
If each node contains only one link member, then we have a singly linked list.
Unlike an array, the nodes of a linked-list do not necessarily occupy consecutive memory locations. [C/C++ comment]
The implementation of a linked-list relies heavily on dynamic memory allocation. [Every node is dynamically allocated. When a linked-list is created, its length (i.e. # of nodes) is unknown.] [C/C++ comment]
Although arrays support "simple" list storage applications, they cannot efficiently handle dynamic changes such as inserting and deleting from the middle of a list. As we have seen, these operations require shifting elements either to the right or the left. With large volumes of data, these copy operations can be expensive.
Terminology
A linked list consists of a set of nodes. Each node contains data and link members. The first element is called the front and is pointed to by head. The end-of-list (EOL) is called the rear its link data member has the value
NULL
(i.e. 0). In some implementations the rear is pointed to by tail. List applications traverse the linked list using a cursor as a reference (or pointer) to the current element.Description of a Node
A node can be described as follows:
Data
data field
-- value is not used in any operation other than initializationnext pointer
-- pointer to the following node (ornull
if there is no next node)Operations
constructor
-- initialize a new nodenextNode
-- returnnext
insertAfter
-- resetnext
to point at the new node and adjust the value ofnext
in the new node to reference the successor of the current nodedeletetAfter
-- unlink thenext
node and assign the valuenext
to reference the successor of the next nodeBjarne Stroustrup: Why you should avoid Linked Lists
{TopOfPage} {Oracle.com::API Specification | Tutorial} {Derek Banas Videos} {Data Structure Visualizations}
A set is a basic building block of mathematics and is a collection of objects (e.g. integers, real numbers, boolean values, geometric points, strings, records, etc.).
The objects of a set are called elements (or members).
A set the following properties:
- all elements of a set belong to some universe
- any object of the universe is either in a set or it is not
- there is no particular ordering of elements within a set
Example of sets:
- a set of classes that a student it taking
- a set of email addresses in an adress book
- a set of prime numbers
The following operations are performed on a set:
- construct (i.e. define/create/instantiate) a set
- check to see if an object is a member of a set
- test if a set is empty
- get the cardinality (size of a set; number of elements/members)
- check if set A is included in set B (if so, then A is subset of B and B is superset of A)
- determine union of two sets (all elements appearing in A or B)
- determine intersection of two sets (all elements appearing in A and B)
- difference between to sets (all elements of set A not in set B -- notation: A - B)
- add an object to a set
- remove an object from a set
- clear all objects from a set
An array (i.e. vector) can be used to store a set.
A class that is used to represent a set could have the following instance methods:
Set(); Set(int capacity); boolean isMember(Object element); boolean isEmpty(); boolean isSubset(Set other); int size(); Set union(Set other); Set intersection(Set other); Set difference(Set other); void add(Object element); void remove(Object element); void clear();
{TopOfPage} {Oracle.com::API Specification | Tutorial} {Derek Banas Videos} {Data Structure Visualizations}
A stack is a data structure in which all access is restricted to the most-recently-inserted elements (LIFO: Last-In-First-Out).
My favorite real world example of a stack is a salad bar. Typically, at the start of the salad bar line is a stack of plates and normally you take the top-most plate (unless it is dirty or has some type of foreign looking object on it, in which case you dig down and take a plate from somewhere lower in the stack [atypical stack behavior]). In actualality, a stack is the wrong way to store plates at a salad bar because of the following scenario: The dishwasher cleans the dirty plates, brings them out front to the salad bar, and pushes them on top of the stack -- now John Q. Customer comes up and is stuck using a hot plate.
A stack has three natural operations: insert, delete, and find; but in stack terminology these operations are called push , pop and top .
Elements are inserted onto a stack by using a push operation.
Elements are deleted from a stack by using a pop operation.
The most-recently inserted element can be examined by using a top operation.
Stacks are heavily used in system software (e.g. compilers). A stack can be used to check for unbalanced symbols (e.g. (), {}, []). Example algorithm:
- create an empty stack
- read symbols until EOF
- if the symbol is an opening symbol, push it onto the stack
- if the symbol is a closing symbol and the stack is empty, then report an error
- otherwise, pop the stack (if symbol popped is not the corresponding opening symbol, then report an error)
- at EOF, if stack is *not* empty, then report an error
A stack is used to implement function (method) calls in most languages. For example in C++, when a function is called, memory for parameters and locally defined variables is allocated from the stack. When the function returns, the memory for the parameters and local variables is de-allocated from the stack. In addition, "jump" information and return value data is stored on the stack.
Stacks are also used in the evaluation of expressions (e.g. operator precedence parsing).
{TopOfPage} {Oracle.com::API Specification | Tutorial} {Derek Banas Videos} {Data Structure Visualizations}
A queue is a data structure in which all access is restricted to the least-recently-inserted elements (FIFO: First-In-First-Out).
Operations are:
enqueue
-- insert at the back of the line (append)dequeue
-- remove from the front of the linefront
-- access item from front of the lineExamples of a queue: buffered input and a line printer spooler.
Another queue example: message queues.
{TopOfPage} {Oracle.com::API Specification | Tutorial} {Derek Banas Videos} {Data Structure Visualizations}
A priority queue allows the highest priority element to be removed from a queue even though it may not be the "oldest."
Real world example of a priority queue: You go to a restaurant with a friend that has a wait. There are a number of queues: a queue for two person table, a queue for a four person table, and a queue for large party table. You are placed on the queue for a two person table. There are three "elements" ahead of you. In comes a VIP with a friend. The next two person table that opens up is given to the VIP.
An operating system may use a priority queue when scheduling jobs. By default, each job is given the same priority. CPU access is granted using a queue (first come, first served). In certain cases, however, you may have a job that needs to get more CPU usage. In those cases, it will be given a priority higher than the default. The OS will use a scheduling algorithm to ensure the higher priority job gets the CPU with more frequency.
{TopOfPage} {Oracle.com::API Specification | Tutorial} {Derek Banas Videos} {Data Structure Visualizations}
Home | Previous | Next |
---|