Home  Previous  Next 

CSC205::Lecture Note::Week 07
Assignments 
Code 
Handouts 
Resources 
Email Thurman {
compufoo::Twitter 
Facebook 
YouTube}
GDT::Bits::
Time

Weather

Populations

Special Dates
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 bitwise 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} {Additional Resources}
Recursion is any solution technique in which large problems are solved by reducing them to smaller problems of the same form.
According to multiple sources, the text
Thinking Recursively
by Eric Roberts (John Wiley 1986) is an excellent resource on recursion.Internally, recursive functions are supported using a stack.
Almost every recursive function has the same basic structure:
if (test for simple case) return (simple solution computed w/o using recursion) else return (recursive solution involving a call to the same function)A recursive function is a function that calls itself in its function body. The call uses different arguments that ultimately read values that allow the function to return a result.
A recursive algorithm must have a welldefined stopping state, or termination condition.
Tail recursion is when the only recursive call appears in the function and that recursive call is the last operation performed at that procedural level. Typically, tail recursive functions can be easily rewritten as nonrecursive functions. The traverse linkedlist example provides an example of tail recursion.
Some final comments:
 Recursion replaces the loop.
 Recursion may provide no saving in storage, since somewhere a stack of the values being processed must be maintained.
 Recursion will not be faster.
 Recursive code is more compact, and often much easier to write and understand than the nonrecursive equivalent.
 Recursion is especially convienent for recursively defined data structures likes trees.
 Recursive procedures can be carried out with a stack.
Interesting Recursion Related Tidbit
Headline: "Microsoft's Java JIT compiler bungles tail recursion."
A programmer from England has discovered a flaw in Microsoft's Java environment running in Internet Explorer under Windows. On 10/20/1998 Andrew Kennedy posted a note to Java programming newsgroups showing that jview, Microsoft's commandline interface to its justintime compiler, calculates the factorial of 5 (i.e., 5 * 4 * 3 * 2 * 1 * 0!) to be 16. Kennedy writes:> Microsoft seem to have confused addition with multiplication. > Such an easy mistake to make.Followup postings pin down the likely source of the bug as incorrectly handled tail recursion in Microsoft's JIT compiler. Unfortunately there seems to be no way to turn off JIT. Kennedy speculates that this error may be responsible for the failure of a large number of Java applets to run in the IE 4 environment.Programming Loops vs Recursion  Computerphile
Computing the factorial of a number is popular example of using recursion.
Mathematically: n! = { 1 if n = 0; otherwise, n * (n1)! }To compute
n!
you must:
 remember what
n
is go compute
(n1)!
 once
(n1)!
is computed, multiply byn
to get the final answerTo compute (n1)!, you 1st compute (n2)!. Computing (n2)! requires finding (n3)! and so on. Eventually we end up at 0! and 0! is defined to be the value 1. In C: printf("%i\n", factorial(4)); int factorial(int n) { if (n == 0) return 1; return n * factorial(n 1); } 4 is pushed onto the stack 3 is pushed onto the stack 2 is pushed onto the stack 1 is pushed onto the stack 0 is pushed onto the stack returns 1 1 * 1 returns 1 2 * 1 returns 2 3 * 2 returns 6 4 * 6 returns 24See factorial.cpp and Factorial.java.
Recall: When a function is called, EXPRs are evaluated and are passed by value. An implicit argument that is passed to a function is a return address. Function return values, if any, are placed in a secure location from which the calling program may retrieve it.
Raising a number to a power can also be solved recursively.Power function: n**k = { 1 if k is 0; otherwise, n * (n**(k1)) }Computingx^{n}
, wherex
is a real number andn
is a nonnegative integer, is called the power function and its calculation is usually accomplished with repeated multiplication:x^{n} = x * x * x * ... *x * x where x multiplied with itself n times 2^{0} = 1 2^{1} = 2 * 1 = 2 2^{2} = 2 * 2 = 4 2^{3} = 2 * 2 * 2 = 8 2^{4} = 2 * 2 * 2 * 2 = 16The power function can be implemented as follows:power(x, n) = x^{n} = { 1, n = 0  x * x^{n1}, n > 0 } double power(double x, int n) { if (n == 0) return 1; return x * power(x, n1); }See power.cpp and Power.java.
printd(150); printd(int n) { if (n / 10) printd(n / 10); putchar(n % 10 + '0'); } 150 / 10  15 pushed onto the stack 15 / 10  1 pushed onto the stack 1 / 10 1 is printed 5 is printed 0 is printedSee printld.cpp and PrintLD.java.
{TopOfPage} {Oracle.com::API Specification  Tutorial} {Additional Resources}
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
 endoflist (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} {Additional Resources}
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} {Additional Resources}
A stack is a data structure in which all access is restricted to the mostrecentlyinserted elements (LIFO: LastInFirstOut).
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 topmost 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 mostrecently 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 deallocated 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} {Additional Resources}
A queue is a data structure in which all access is restricted to the leastrecentlyinserted elements (FIFO: FirstInFirstOut).
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} {Additional Resources}
Home  Previous  Next 
