Tuesday, 2 July 2013

Data Structure and JAVA Language

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.    

High-Level Design Goals

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.

Abstract Data Type (ADT) – An abstract model of a data structure that specifies the type of data stored, the operations supported on them, and the types of parameters of the operations. Specifies what each operation does but not how it does it. Encapsulation – The various components of a software system should implement an abstraction without revealing the internal details of the implementation. This gives the programmer freedom in implementing the internal details of a software system. It also frees the user (or higher-level developer) from worrying about these internal details.
 

Modularity and Hierarchy

Modularity – The various components of a software system are divided into separate functional units. Hierarchy – The modular components are grouped together in a level-by-level manner that goes from specific to more general as one traverses up the hierarchy. ("is-a")

A Simple Java Application

public class ShowArgs
{
  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]);
        }
    }
}
 
Compiling
C:\DataStructures\src>javac ShowArgs.java
Running
 

C:\src>java ShowArgs Hello World Argument 0 is: Hello
Argument 1 is: World
 JDK 1.2 Documentation
 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);



Methods

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)
 

Parameter Values

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


Object Parameters

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)
 

Methods Returning Multiple Results

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.
    1. Return references to objects that store the results as instance variables.
    2. Take one or more parameters that reference objects in which to store the results.
    3. Return an array that returns the results.
The following is an illustration of option 1.
 

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. }


Using Methods to Control Access

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;   }   : }



Modifiers in Declarations
Visibility Modifiers



Variables or methods with this modifier can be accessed by methods in:
Variable or method modifier
public
private
protected
"package"
(default)
Same class
Y
Y
Y
Y
Classes in same package
Y
N
Y
Y
Subclasses
Y
N
Y
N
Classes in different packages
Y
N
N
N

 
Other Modifiers

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

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));



Reading Numerical Values from a String Representation

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.
Target type
Code to convert from a String instance
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


Arrays

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];

The Math Class

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

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();
}
/** A circle. Since you can calculate the area of
* circles, class implements the Measurable interface.
*/
public class Circle extends Curve implements Measurable {
  private double radius;
  public Circle(int x, int y, double radius) {
    setX(x);
    setY(y);
    setRadius(radius);
  }
  public double getRadius() {
    return(radius);
  }
  public void setRadius(double radius) {
    this.radius = radius;
  }
  /** Required for Measurable interface. */
  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 static double totalArea(Measurable[] mArray) {
    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.
*/
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));
  }
}
 

Interfaces (3)

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.*;
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.
  }
  public void itemStateChanged(ItemEvent event)
  {
    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.
  */
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);
  }
}
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.Applet
or import the appropriate class and avoid the fully qualified classname.
import java.applet.*; : class myApplet extends Applet
or, 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.