Week 3: OOP and Basic Data structures

3.1 Object Oriented World

• Traditional Languages vs OOP Languages
• VB, C vs Java C++
• The Concept of Object Factory
• Hardware vs Software

3. 11 Objecct Oriented Programming

• Program is an object
• Certain properties (data) and operations (methods) object can perform
• Care only about the objects expose, do not care what is inside
  (For example, draw a string ... do not care what way and how we draw)
• OOP puts data first, then operations (vs Algo + Data Structure = Programs)
• Object carries their own task
• In OOP, we have clients send messages to server objects

3.12 Speaking of OOP

• A class can be described as the template or blueprint from which the object is actually made
• QNetWareTape myobj = new QNetWareTape();
  (Using the new operator to create a new instance of the QNetWareTape class)
• Do not as rich as toolkit language such as VB, MFC
• Base class - class based from or built on (extend)
• Java - all classes extend the cosmic base class called Object (inheritance)
• Encapsulation (data hiding, have programs never access instance variables in a class)
• Data in an object are usually called its instance variables or fields

3.13 Other Important Concept

• OOA, OOD
• Relationships (use, containment "has-a", inheritance "is-a")
• In general, if class A extends class B, class A inherits methods from class B but has more capabilities
• Traditional vs OOP (2000 functions web browser vs 100 classes with 20 methods per class)

3.2 Object declaration and construction

• Declaration - declares type and name of object
• Construction - uses "constructor" to create the object
• Can be combined
• Object is destroyed automatically (garbage collection)

Examples:

// Declaration:
Vector v1;

// Construction:
v1 = new Vector ();

// Combined declaration and construction:
Vector v2 = new Vector ();

3.21 Other Simple Example

• TapeDrive mytape = new TapeDrive(); // Create a new instance of TapeDrive class
• TapeDrive othertape = mytape; // Both vars refer to the same object
• mytape.play();
• othertape.stop();

3.22 Using Java Build-in Classes

Vectors

• Collection of elements
• Not a vector in the mathematical sense
• Slower than arrays (...)
• Arrays in java can hold any type, including number types and all class types,
  Vectors in Java must hold instances of Object (But we can cast integer to Integer class wrapper)
• More versatile than arrays
  • The size (number of elements) can change
  • Elements can be removed and inserted
  • Elements can be different types

More on Vectors

• addElement (Object element)
• removeElement (Object element)
• size ()
• indexes start at 0
• elementAt (int index) - need to cast element to expected type
• insertElementAt (Object element, int index)
• removeElementAt (int index)
• indexOf (Object element, int startIndex)
• internal details:
  • size vs. capacity
  • automatically growing and shrinking
  • capacity and increment can be specified in the constructor
    Note:
    
    API doc under javasoft in java.util.Vector class
    Vector()
    Constructs an empty vector.
    Vector(int)
    Constructs an empty vector with the specified initial capacity.
    Vector(int, int)
    Constructs an empty vector with the specified initial capacity and capacity increment.

Examples:

Vector v = new Vector ();
v.addElement ("Apple");
v.addElement ("Banana");
v.insertElementAt ("Cherry", 1);  // Will throw an exception if invalid
// Each component in this vector with an index greater or equal 
// to the specified index is shifted upward to have an index one 
// greater than the value it had previously. 
// A,C,B

int s = v.size (); // Returns 3.

// Need to cast return value of elementAt().
// This will return "Banana".
String fruit = (String) v.elementAt (2); // Object is return 

v.removeElement ("Apple");
v.removeElementAt (1);

Hashtables

• Also know as maps, dictionaries, lookups
• Data is accessed by key, not index
• key and element can be any object
• put (Object key, Object element)
• get (Object key) - need to cast element to expected type
• remove (Object key)
• containsKey (Object key)
• size ()
• internal details:
  • key maps to index using hashCode ()
  • if multiple keys map to the same index, a linked list if formed
  • performance bad if to many linked lists needed
  • solution #1: redefine hashCode ()
  • solution #2: change size of Hashtable using constructor

Examples:

// Create a hashtable with names as keys and
// birthdays as elements.
Hashtable birthdays = new Hashtable ();
birthdays.put ("Dylan", "June 25");
birthdays.put ("Liam", "February 28");
birthdays.put ("Angie", "February 10");

// Need to cast return value of get().
// This will return "February 28".
String bd1 = (String) birthdays.get ("Liam"); 

birthdays.remove ("Angie");

// This will return false:
boolean x = birthdays.contains ("Richard");

// This will return true:
boolean y = birthdays.contains ("Dylan");

Enumerations

• used to iterate through elements of a collection
• provides a common interface regardless of the collection
  • Vector.elements ()
  • Hashtable.keys ()
  • Hashtable.elements ()
  • many more
• hasMoreElements ()
• nextElement () - need to cast element to expected type
• most commonly used with while loop
• many enumerations can be active for one collection

Examples:

Enumeration e = v.elements ();
while (e.hasMoreElements ())
{
	String s = (String) e.nextElement ();
	System.out.println ("The next element is: " + s);
}

Date

• stores date and time as a long
• the number of milliseconds since midnight, 1 January 1970
• default constructor creates Date object with current date and time
• getTime () - returns long

Examples:

// Get current date and time before the operation.
Date before = new Date (); 

// ... Do something.

// Get current date and time after the operation.
Date after = new Date (); 
long difference = after.getTime () - before.getTime ();
System.out.println ("The operation took " + difference + " milliseconds.");

3.3 Packages

• provide a way of grouping similar functions and objects
• Date, Hashtable, and Vector are in java.util package
• must "qualify" as java.util.Date, java.util.Hashtable, and java.util.Vector
• import java.util.Date; import java.util.Vector; import java.util.Hashtable;
• import java.util.*;
• String is in java.lang package
• java.lang objects do not need to be qualified
• JDK contains many packages beginning with java.
• you can create your own packages

3.4 Lab

Create a benchmark application (called Week3) that compares the performance of arrays, Vectors, and Hashtables is 3 criteria: creation, iteration, searching.

Your application should:

1. Create an array of 1000 Strings. Assign the values to be the String containing the digits of a number (e.g., "657"). You can create a String from a number as follows:
   

   String s = Integer.toString (657);

2. Create a Vector with the same 1000 Strings.
3. Create a Hashtable using the Strings as keys and an empty String ("") as elements.
4. Iterate through the elements of the array using a for loop.
5. Iterate through the elements of the Vector using size () and elementAt ().
6. Iterate through the elements of the Vector using an Enumeration.
7. Search for the element "888" in the array using a for loop.
8. Search for the element "888" in the Vector using indexOf ().
9. Search for the element "888" in the Hashtable using get ().

Your application should time each step using Dates and report the time each step takes to run.

Copyright 1996-2001 OpenLoop Computing. All rights reserved.