Data structure – A
systematic way of organizing and accessing data.
Algorithm – A step-by-step
procedure for performing some task in a finite amount of time.
Correctness – A data
structure or algorithm works correctly for all possible inputs that one
might encounter within a certain domain of interest. The precise meaning
of correctness is inherently problem-dependent.
Efficiency – A data
structure or algorithm should be fast and use the minimum necessary amount
of resources such as memory space.
Implementation Goals
Robustness – Software
produces the correct output for all inputs. Robust software should
be able to handle inputs that are not explicitly defined for its domain
of interest.
Adaptability – Software
needs to evolve over time in response to changing conditions in its environment.
Software should also be able to adapt to unexpected events that, in hindsight,
really should have been anticipated. (Example: Y2K problem).
Reusability – The
high cost of developing software can be mitigated by ensuring that the
code developed for one application can be fully reused by other applications.
Object-Oriented Design Principles
Abstraction – Distill
a complicated system down to its most fundamental components and provide
a simple, precise description of these components.
Modularity and Hierarchy
{
static public void main(String[] args)
{
String outstring;
// Print out the set of command-line arguments. for(int i=0;i<args.length;i++)
{
outstring = "Argument " + i + " is: ";
System.out.println(outstring + args[i]);
}
}
}
C:\DataStructures\src>javac ShowArgs.javaRunning
C:\src>java ShowArgs Hello World Argument 0 is: HelloJDK 1.2 Documentation
Argument 1 is: World
javac - The Java Compiler
java - The Java Interpreter
Classes and Objects
Classes are the fundamental unit of programming in Java
and serve as the blueprints for objects. Almost all Java code is contained
within a class.
A simple class definition:
Class Body { public long idNum; public String name; public Body orbits; public static long nextID = 0; }The instance variables declared in a class definition may be primitive types (e.g., boolean, char, byte, short, int, long, float, double) or objects (essentially any other declaration).
Declare an object named mercury
of class Body:
Body mercury;
The above declaration does not create an object; that requires another step known as instantiation. The above declaration merely creates a reference that is allowed to refer to a Body object. Thus, object variables are reference variables. However, reference variables in Java cannot be assigned to arbitrary pointer values as in C and C++. As such, a hacker or careless programmer may never be given inadvertent access to protected system resources. Reference variables may be assigned to existing objects that are either of the same type or castable to the same type, assigned to newly created objects via the new() operator, or dereferenced to null for garbage collection.
Creating Objects
Body sun = new Body(); //instantiation sun.idNum = Body.nextID++; //use of static variable sun.name = "Sol"; sun.orbits = null; Body earth = new Body(); earth.idNum = Body.nextID++; earth.nameFor = "Earth"; earth.orbits = sun;
The new keyword is used to instantiate, or create objects. In this case, we are using the default constructor for class Body, since we have not as yet explicitly defined a constructor. The above code fragment declares, instantiates and initializes two objects of class Body named sun and earth, respectively.
Constructors
Constructors have the same name as the classes they initialize.
They may take zero or more parameters in the same manner as methods. Unlike
methods, however, constructors do not have a return value.
Class Body { public long idNum; public String name = "<unnamed>"; public Body orbits = null; private static long nextID = 0; Body() // no-arg constructor { idNum = nextID++; }
Body(String bodyName, Body orbitsAround)
{ this(); // invokes no-arg constructor name = bodyName; orbits = orbitsAround; } }
Here we have defined two constructors for class Body. We may also define methods that have the same name but use different parameters and return different types. This practice, known as overloading, is a very useful feature of Java. We may now use the second form of the Body constructor to instantiate and initialize, all in one command.
Body sun = new Body(); sun.name = "Sol"; Body earth = new Body("Earth", sun);
A class's methods contain the code that understands and
manipulates an object's state. Methods may accept parameters and return
primitive types or objects. The following toString()
method, which we now add to the Body
class, accepts no parameters but returns a new String
object
Class Body { : public String toString() { String desc = idNum + "(" + name + ")"; if(orbits != null) desc += " orbits " + orbits.toString(); return desc; } }
Note the recursive definition. We shall cover recursion in much greater detail in Lecture 3. A class's toString() method is invoked in the context of a string concatenation operation using the + operator. The following code fragment
System.out.println("Body "+sun);
System.out.println("Body "+earth);
produces the following output:
Body 0 (Sol)
Body 1 (Earth) orbits 0 (Sol)
All parameters to Java are "pass by value." In a method
call, when the actual parameters are primitive types, the formal
parameters (in the method definition) are local copies of those variables.
If the method changes a formal parameter, the parameter variable is only
affected inside the method.
class PassByValue { public static void main(String[] args) { double one = 1.0; System.out.println("one before = " + one); halveIt(one); System.out.println("one after = " + one); } public static void halveIt(double val) { val /= 2.0; System.out.println("one halved = "+val); } }
In the above example, the method halveIt receives a local copy of the variable (actual parameter) one as the formal parameter val. Although halveIt halves val, this change only affects the local copy.
one before = 1.0 one halved = 0.5 one after = 1.0
When a reference type (i.e., an object) is specified as
an actual parameter to a method call, the formal parameter is the value
of the reference. The method receives a local copy of the value of the
reference.
class PassRef { public static void main(String[] args) { Body sirius = new Body("Sirius",null); System.out.println("before: " + sirius); commonName(sirius); System.out.println("after: " + sirius); } public static void commonName(Body bodyref) { bodyRef.name = "Dog star"; bodyRef = null; } }
Both the local (formal parameter) copy of the reference and the actual parameter refer to the same object. Thus, modifications made to the object from within the method also affect the object outside the method.
before: 0 (Sirius)
after: 0 (Dog star)
Since all parameters are passed by value in Java, and
since deferencing is prohibited, Java programmers cannot have methods return
multiple values through dereferenced parameters, as in C or C++. There
are, however, several ways to accomplish this.
- Return references to objects that store the results as instance variables.
- Take one or more parameters that reference objects in which to store the results.
- Return an array that returns the results.
protected class Permissions { public boolean canDeposit, canWithdraw, canClose; } public class BankAccount { private long number; // account number private long balance; // current balance
public Permissions permissionsFor(Person who) { Permissions perm = new Permissions(); perm.canDeposit = canDeposit(who); perm.canWithdraw =canWithdraw(who); return perm; }
// code for defining canDeposit, canWithdraw, //etc. }
In many cases, a class's instance variables should be
modified as private for use within the class only. There are exceptions
to this advice, for example in the case of small classes such as java.awt.Point,
which simply stores an x and y coordinate. In general, however,
good programming practice involves using methods to get and (if allowed)
set the values of instance variables.
class Body { private long idNum; // now private public String name = "<unnamed>"; public Body orbits = null; private static long nextID = 0; : public long getID() { return idNum; } : }
Visibility Modifiers
| Variables or methods with this modifier can be accessed by methods in: | ||||
(default) |
||||
| Same class | ||||
| Classes in same package | ||||
| Subclasses | ||||
| Classes in different packages | ||||
static – This
indicates that a variable or method is shared by the entire class. It is
accessed by the classname rather than just by an instance. Static methods
can only refer to static variables or other static methods unless they
create an instance of the appropriate class.
final – For
a class, final indicates that it cannot be subclassed. For a variable or
method, final indicates that it cannot be changed at run time or overridden
in subclasses. For a variable, a final modifier makes it a constant.
abstract – Indicates
that the class cannot be instantiated. Abstract classes can have abstract
(blank) methods. More on this later…
Still more modifiers:
- synchronized
- volatile
- transient
- native
Strings in Java are "immutable," meaning that once instantiated,
they cannot be changed. While this may seem quite restrictive, most if
not all of the work you will need to do in this course can be done using
immutable strings. Each time you update a string, a new String
object is instantiated. For example, the following code segment involves
the instantiation of three different strings:
String helloWorld = "Hello" + "world";
The three instantiated string objects contain "Hello",
"world", and "Hello world", respectively. An equivalent piece of code is
String hello = "Hello";
String World = "world";
String helloWorld = hello + World;
Java also provides a StringBuffer
class which is not immutable and can be more efficient for code that does
a lot of string manipulation. Another useful class for parsing string content
is java.util.StringTokenizer, which lets the
programmer specify separator tokens and successively returns the token-separated
substrings in a string. Within the String class,
the following methods may be useful.
public char charAt(int index)
– Returns the character at the specified location.
public boolean compareTo(String comparison)
– Compares the current string with the one supplied in the parameter.
public boolean equals(Object comparison)
– Two different strings with the same characters will be equals
but not ==.
Java I/O
In this course, we will only be dealing with text I/O,
so we won't cover how to read and write binary-data files.
Writing a line of text to standard output.
double myNumber=3.14; String myString = "Pi is approximately " + myNumber; System.out.println(myString);
Writing a line of text to a file.
PrintWriter out = new PrintWriter(new FileWriter("myfile.txt")); try { out.println(myString); // more code goes here out.close(); // closes the PrintWriter } catch(IOExeption e1) { // code to handle exception }
Reading a line of text from a file.
try { BufferedReader in = new BufferedReader(new FileReader("myfile.txt")); String instring = in.readLine(); } catch(IOException e2) { // code to handle exception }Console Input:
include java.io.*; :: BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
Java provides the wrapper classes Boolean,
Byte, Character, Short, Integer, Long, Float,
and Double
to store the respective primitive (boolean,
byte,
char,
short, int, float, or double)
in an Object wrapper. These classes have many uses that we shall explore
in the course. One use of wrapper classes is to convert a string representation
of a number to the proper primitive type.
| int | new Integer(String).integerValue() |
| Integer.valueof(String).integerValue() | |
| Integer.parseInt(String) | |
| long | new Long(String).longValue() |
| Long.valueOf(String).longValue() | |
| Long.parseInt(String) | |
| float | new Float(String).floatValue() |
| Float.valueOf(String).floatValue() | |
| double | new Double(String).doubleValue() |
| Double.valueOf(String).doubleValue |
Java arrays provide ordered collections of elements. Components
of an array can be primitive types of references to objects, including
references to other arrays. The following code segment reads in the desired
array size from a file, allocates an array of double-precision numbers
of that size, and assigns a value, equal to the index, to each element
in the array.
BufferedReader in = new BufferedReader(new FileReader("myfile.txt")); String instring = in.readLine(); int n = Integer.valueof(inString).integerValue(); double[] x = new double[n]; for(int i=0; i<x.length; i++) x[i] = (double)i;
Array dimensions are omitted in the declaration of any array variable.
double[] x;
The number of components in an array is determined when it is created using new, not when it is declared.
double[] x = new double[n];
The length of any array is available via the length field. The first element of an array has index 0 and the last element has index length-1. Arrays are implicit extensions of the Object class and are, therefore, reference types.
Arrays may be initialized in the declaration.
int[] values = {0,1,2,3,4};Multidimensional arrays are implemented using arrays of arrays, as in C.
float[][] grid
= new float[25][25];
Constants
public static final double E
- The base for natural logarithms
public static final double PI
- p
General-purpose methods
public static int abs(int num)
public static long abs(long num)
public static float abs(float num)
public static double abs(double
num)
public static native double ceil(double
num)
public static native double floor(double
num)
public static native double exp(double
num)
public static native double log(double
num)
public static native double IEEEremainder(double
f1,
double f2)
public static double max(double
num1, double num2)
public static double min(double
num1, double num2)
max and min methods also exist for int, long, and float
public static native double pow(double
base, double exponent)
public static double random()
– Also see the Random class
public static int round(double num)
public static long round(double
num)
public static native double sqrt(double
num)
Trigonometric methods – all operate on radians (forward
methods) or return radians (arc methods)
public static native double sin(double
radians)
public static native double cos(double
radians)
public static native double tan(double
radians)
public static native double acos(double
val)
public static native double asin(double
val)
public static native double atan(double
val)
Inheritance is the process by which a new class is built
on top of a previously written class without having to rewrite the existing
class's functionality. The original class is known as the "parent class"
or "superclass" ("base class" in C++). The new class is known as the "child
class" or "subclass" ("derived class" in C++).
class Planet extends Body { String moons[]; Planet(String PlanetName, Body orbitsAround, String[] moons) { super(PlanetName,orbitsAround); this.moons = moons; } String toString() { String desc; desc = super.toString(); desc += " and the moons are:" for(int i=0; i<moons.length;i++) desc += " " + moons[i]; } }In addition to adding new variables and methods, a child class can override methods from a previous class. In the above example, the instance variable String moons[] was added to the child class, and the method toString() was overridden. The overridden method toString() in the child class can call the previous (parent) version by calling super.toString(). The super method call is used in constructors only to invoke superclass constructors. The super variable can be used in any method to access superclass fields and methods.
Abstract Classes
An abstract class is a class that cannot be instantiated.
It generally corresponds to a generic entity with details that need to
be "filled in" by a subclass. An abstract method is a method that does
not contain an implementation (i.e., an empty method). An abstract class
can intermix abstract and nonabstract method definitions. A class with
abstract methods must be modified as abstract. Modifying an abstract method
as final or static
would be a contradiction.
abstract class Benchmark
{
abstract void benchmark();
// abstract method
public long repeat(int count)
{
long start =
System.currentTimeMillis();
for(int i = 0;
i < count; i++)
benchmark();
return (System.currentTimeMillis()
– start);
}
}
class MethodBenchmark extends Benchmark
{
void benchmark()
{
double y = Math.log(100.0);
}
public static void main(String[]
args)
{
int count = Integer.parseInt(args[0]);
long time = new
MethodBenchmark().repeat(count);
System.out.println(count
+ " methods in " +
time + " milliseconds");
}
}
Interfaces
Interfaces may contain only constants, abstract methods,
and other interfaces. Interfaces may extend other interfaces. As an expression
of pure design, interfaces are useful constructs in the design of ADTs.
The interface specifies the methods must be defined in a class that implements
the interface, but does not specify the implementation of those methods.
All methods in an interface are by default declared to be public
and abstract.
Constants in an interface are by default public,
static,
and final.
/** Used in classes with measurable areas. */
public interface Measurable {
double getArea();
}
double getArea();
}
/** A circle. Since you can calculate the area
of
* circles, class implements the Measurable interface.
*/
* circles, class implements the Measurable interface.
*/
public class Circle extends Curve implements
Measurable {
private double radius;
private double radius;
public Circle(int x, int y, double radius)
{
setX(x);
setY(y);
setRadius(radius);
}
setX(x);
setY(y);
setRadius(radius);
}
public double getRadius() {
return(radius);
}
return(radius);
}
public void setRadius(double radius) {
this.radius = radius;
}
this.radius = radius;
}
/** Required for Measurable interface. */
public double getArea() {
return(Math.PI * radius * radius);
}
}
public double getArea() {
return(Math.PI * radius * radius);
}
}
Interfaces (2)
A formal parameter type that is an interface can accept
as an actual parameter any class or subclass that implements the interface.
/** Some operations on Measurable's. */
public class MeasureUtil {
public static double maxArea(Measurable m1,
Measurable m2) {
return(Math.max(m1.getArea(), m2.getArea()));
}
public class MeasureUtil {
public static double maxArea(Measurable m1,
Measurable m2) {
return(Math.max(m1.getArea(), m2.getArea()));
}
public static double totalArea(Measurable[]
mArray) {
double total = 0;
for(int i=0; i<mArray.length; i++)
total = total + mArray[i].getArea();
return(total);
}
}
double total = 0;
for(int i=0; i<mArray.length; i++)
total = total + mArray[i].getArea();
return(total);
}
}
/** Test of MeasureUtil. Note that we could change
* the actual classes of elements in the measurables
* array (as long as they implemented Measurable)
* without changing the rest of the code.
*/
* the actual classes of elements in the measurables
* array (as long as they implemented Measurable)
* without changing the rest of the code.
*/
public class MeasureTest {
public static void main(String[] args) {
Measurable[] measurables =
{ new Rectangle(0, 0, 5.0, 10.0), //also implements measurable
new Rectangle(0, 0, 4.0, 9.0),
new Circle(0, 0, 4.0),
new Circle(0, 0, 5.0) };
System.out.print("Areas:");
for(int i=0; i<measurables.length; i++)
System.out.print(" " + measurables[i].getArea());
System.out.println();
System.out.println("Larger of 1st, 3rd: " +MeasureUtil.maxArea(measurables[0],
measurables[2]) +"\nTotal area: " +
MeasureUtil.totalArea(measurables));
} }
public static void main(String[] args) {
Measurable[] measurables =
{ new Rectangle(0, 0, 5.0, 10.0), //also implements measurable
new Rectangle(0, 0, 4.0, 9.0),
new Circle(0, 0, 4.0),
new Circle(0, 0, 5.0) };
System.out.print("Areas:");
for(int i=0; i<measurables.length; i++)
System.out.print(" " + measurables[i].getArea());
System.out.println();
System.out.println("Larger of 1st, 3rd: " +MeasureUtil.maxArea(measurables[0],
measurables[2]) +"\nTotal area: " +
MeasureUtil.totalArea(measurables));
} }
Interfaces can be used to provide a limited form of multiple
inheritance. This is because methods may implement multiple interfaces,
e.g.
class MyFrame extends Frame implement
ItemListener,
ActionListener
{ … }
Interfaces may be cast to the objects that implement them.
import java.awt.*;
import java.awt.event.*;
import java.awt.event.*;
public class ChoiceEvent extends Frame implements
ItemListener
{
Choice myChoice;
public ChoiceEvent()
{
// code to setup layout manager, etc.
mychoice = new Choice();
myChoice.add("Java");
// additional choices added
myChoice.addItemListener(this);
// more code to build GUI, etc.
}
{
Choice myChoice;
public ChoiceEvent()
{
// code to setup layout manager, etc.
mychoice = new Choice();
myChoice.add("Java");
// additional choices added
myChoice.addItemListener(this);
// more code to build GUI, etc.
}
public void itemStateChanged(ItemEvent event)
{
if(event.getItemSelectable() == myChoice)
System.out.println(((Choice)event.getItemSelectable()).getSelectedItem() +
" was selected");
}
{
if(event.getItemSelectable() == myChoice)
System.out.println(((Choice)event.getItemSelectable()).getSelectedItem() +
" was selected");
}
// more code (main, etc.)
}
}
In the above example, event.getItemSelectable()
returns an Interface ItemSelectable
type, which is cast to an object of Class
Choice. Since the Choice
class implements the ItemSelectable
interface, and since the original object is of class Choice,
the run-time environment allows this cast. Also note the test for object
equality between a Choice object
and an Interface ItemSelectable
type.
Exception Handling
Java's flexible exception-handling capabilities facilitate
the programmer's goal of writing robust yet readable code. Rather than
relying on return codes or global variables, Java allows the programmer
to "throw" an exception which must get "caught" at the appropriate level.
Catching an exception involves the try,
catch,
and finally
clauses. The code within the try block is presumed to be able to throw
the exceptions corresponding to the catch clauses. If an exception is generated,
Java executes the first catch
clause
that matches the type of exception thrown.
/** Read a string from user and create URL from
it.
* If reading fails, give up and report error.
* If reading succeeds but URL is illegal, try again.
*/
* If reading fails, give up and report error.
* If reading succeeds but URL is illegal, try again.
*/
public URL getURL() {
if (url != null)
return(url);
System.out.print("Enter URL: ");
System.out.flush();
DataInputStream in = new DataInputStream(System.in);
String urlString = null;
try {
urlString = in.readLine();
url = new URL(urlString);
} catch(MalformedURLException mue) {
System.out.println(urlString + " is not valid.\n" +
"Try again.");
getURL();
} catch(IOException ioe) {
System.out.println("IOError when reading input: " + ioe);
ioe.printStackTrace(); // Can skip return(null) now
} finally {
return(url);
}
}
if (url != null)
return(url);
System.out.print("Enter URL: ");
System.out.flush();
DataInputStream in = new DataInputStream(System.in);
String urlString = null;
try {
urlString = in.readLine();
url = new URL(urlString);
} catch(MalformedURLException mue) {
System.out.println(urlString + " is not valid.\n" +
"Try again.");
getURL();
} catch(IOException ioe) {
System.out.println("IOError when reading input: " + ioe);
ioe.printStackTrace(); // Can skip return(null) now
} finally {
return(url);
}
}
In lieu of a try/catch/finally block, we could have simply
declared the getURL() method using the throws construct as follows:
public URL getURL() throws
MalFormedURLException, IOException
Exception Handling (2)
Using throw
is most common with exceptions you define yourself. Exceptions are objects
that are created from classes that extend from the base class Exception.
public class NegativeLengthException
extends Exception {
public NegativeLengthException()
{
super("Negative
dimensions not permitted.");
}
public NegativeLengthException(String
message) {
super(message);
}
:
public double[] createArray(int
size)
throws NegativeLengthException
{
double[] array;
if(size<0)
{
throw new NegativeLengthException();
return
null;
}
array = new double[size];
return array;
}
}
Since all exception classes are derived from the base
class Exception, all exceptions can be caught in a try/catch
block by using the generic
catch(Exception e)
Although the programmer is required to catch checked exceptions,
Java also includes two classes of unchecked exceptions: Error
and RunTimeException.
Packages and Compiling
Java provides a vehicle through which the programmer can
group similar classes into a package.
The first line of code in a source file should read
package packagename;
If this line is omitted, the classes in the source file
are added to the default package. When compiling, Java looks for classes
under the CLASSPATH, an environment variable that specifies the set of
root directories under which all classes may be found. The class directory
structure corresponds to the dot (.) structure of the fully qualified class
name. See the CLASSPATH handout.
When writing code in Java, classes must either be imported
or the fully qualified class name must be used. For example, to define
a class that extends the java.applet.Applet
class, one could either write
class myApplet extends java.applet.Appletor import the appropriate class and avoid the fully qualified classname.
import java.applet.*; : class myApplet extends Appletor, equivalently, if Applet is the only class we need from java.applet,
import java.applet.Applet; : class myApplet extends Applet
Compiling
We don't need "makefiles" in Java. Use "javac
file" to compile a class and recompile and
out-of-date classes it directly uses. Use
"javac -depend file" to compile a class and
recompile all out-of-date classes it directly or indirectly uses.
No comments:
Post a Comment