1
CIS 265Data Structures (Java)
Are you in the right class?
What this course is not about. . .
Learning Basics of Java
Learning about computer operation
Using software such as word processor
What this course is about. . .
Review of OOP
Learning Typical Data Structures
Learning Basic Algorithms
Challenging
How to do well
Attend class regularly with the notes and have read the material assigned for the week before the week starts
You have already paid $$$ for my office hours - USE THEM
Learn what we are discussing at the time. Failing behind will likely lead to a bad as the material builds though out the course.
If you do not understand something I have just discussed in class, ask right then
Start programming assignments early, just in case
Pay attention to my courses web site
We have a lot to teach in 15 weeks. Do not fall behind or it will be very hard to catch up!!!
Chapter 1: Java, OOP, Scope, GUI Events, Setting Up Your PC
Java
Java is object oriented language that is designed to be safe, platform independent and to be easier to use than C++. It is a fully object oriented interpreter. An examination of Java turns up several interesting points
Java is in some sense a compiled language, because Java programs are first byte code compiled. This means that our English language commands are first converted to a very dense platform neutral code. This code is not directly executable however, it just an intermediate form of code. The upside to this is that any machine that can read this byte code can run your program. This is the essence of the “Write once, Run anywhere” motto of Java. The downsides are that Java loses the ease of debugging compared to truly interpreted languages. And, that this cross platform compatibility is not really 100%. Although it does this far better than any other language I am aware of
Older versions of Java areinterpreted. Each time you run a program, the byte codes are loaded by the Java Virtual Machine which then interprets them as your code runs. The plus is that these byte codes are much faster to interpret than traditional interpreter. They are still notably slower than other compiled languages such as C++ or the .Net languages giving rise to the lampoon, “Write once, Run anywhere slowly” made by its detractors
Java is a clean ground up design incorporating almost all the object oriented features that allow large, scalable, maintainable and reusable code to be created fairly easily. The exceptions? Java is implemented in such a way that some trivial things are actually harder (text input and file usage), or slower (arrays) than in other languages. Also, a few important features of most other OOP languages where left out of Java, primarily templates and operator overloading
Java supports safe computing. The JVM first checks Java code to be sure that it can not do anything malicious before running it. This is especially true of Java applets (small Java programs downloaded off of web pages). This increases the safety of running Java programs, but at the cost of increased start up times. The later issue is one reason why there are very few web sites that have client side executable Java content any more, despite the safety guarantee
Java supports Rapid Application Development (RAD). Java makes it easier to do such things such as DB connectivity and Graphical User Interfaces (GUI) in comparison to the bad old days VC++ (pre VC++ .net). And, through Java Beans, it even offers some “click and code” functionality similar to VB. However, it is not as easy to do so as when using the newer versions of any of the .Net languages, or VB 6.0 for that matter.
Java is pointer free language that handles memory allocation and freeing up that memory automatically for you. This may not mean much to you, but in the bad old days (and still in C++) pointer errors where/are the number two cause of runtime bugs. This means that Java code tends to be more robust and easier to write / debug.
However, this same approach makes it both hard to get to the lowest level of the machine/OS and can make it impossible to directly manipulate memory as you may wish at times. Luckily the need for this is rare
OOP
An Object Oriented Programming (OOP)Languagecombines several concepts that allow us to work with ever larger projects and enhance their maintenance and reusability. Since Java is only capable of creating OOP programs, we will focus on what OOP is,rather than a compare it non-OOP languages and techniques. Suffice to say that OOP is generally beneficial, but at a cost of complexity for the designer/coder and sometimes program execution speed.
OOP Concepts The key conceptual building blocks of the structure of most OOP languages are as follows
Encapsulation is word that means that data and code are combined to together in one indivisible item with access restrictions. A program consists of one or more of these objects. To accomplish this separation we need two things. First, a container that holds both the data and the code. In most OOP languages this is called a class (from which objects are created). And second, a means of enforcing what can (not) access these pieces of data and algorithms in the class. In java we use one of four keywords to control this access
Public anyobject canaccess the code or data. Even
objects of an entirely different class
Protected only objects of this class, or of a class that is
derived from them, may access the code or data
Package only objects of this class and its’ derivatives
ORclasses that are part of a given project (package), can
access the data or code. This is the default for Java and
is also an unique encapsulation type to myknowledge
Private only objects of this classmay access the data or
code
Abstraction is typically lumped in with encapsulation, but is technically different. Abstraction means that the data that the world sees may not be how that data is represented internally to the class. An analogy, while we type characters, the computer stores everything as binary numbers anyway. In combination with encapsulation this means that we are free to change how ourcode works, and how we store data in our class. So long as the means of accessing (interface) and results our code produces for a given input stay the same
Inheritance means that a class can be expanded to perform other functions by just creating a file (a derivedor extendedclass) that adds/modifiesonly the changed feature(s) to the baseclasswithout, re-writing the whole thing. As an example, several versions of windows are all the same code base and can be easily maintained because of this. Note that in Java, it is not fully possible to support Multiple Inheritance where a class derives from two (or more base classes).
Extends is the keyword that indicates a class is derived
from another. You can only extend off of one class
Implements is a keyword that indicates a class is using an
interface from another abstract class. You can implement
as many abstract classes as you wish, but you must fully
implement each method from those classes
Polymorphism means that a class with a given interface can be reused for a similar purpose in another project. Or that a given interface is retained regardless of the class that underlies it. For the former, a gas gauge class could be used in a Honda, a Nissan or whatever. For the later, an on off switch works the same to the user even though its connections to a calculator, or to a radio, would do different things internally
Dynamic Binding is a nuts and bolts concept that goes hand and hand with inheritance. While, not one of the prime concepts of OOP, it is required to handle inheritance correctly. Essentially, if code expects one object, it will also work with any inherited object (More on this much later)
Javahas a varietyOOP Structures are used to embody the key OOP concepts we previously mentioned. The basic Java structures are
As we know a class is construct that consists of methods and field variables. It serves as a blue print for objects, which are created from the class file. Classes are designed to support encapsulation, inheritance and polymorphism.
Class or Object? A class is the code we write, but (theoretically) that is not the code that runs. Instead we can create any number of copies of this code and each represents an object which we use in the program itself. Note that each object is created exactly as the class as, but after that each individual object has a life of its own and may change
Creating an Object is called instantiation. This is different from primitive declaration and definition, because instantiation refers to the creation of a copy of the class on the heaparea of memory. Additionally, each time an object is instantiated, a special method of the class called a constructor is run. To instantiate an object we need a reference variable to hold the address in the heap of the object we just made.
Reference Variables all object variables are actually references. This means that they hold the address of the actual object in memory. You declare and define them normally, but all you are creating is a variable that can hold an address of an object. To actually create an object itself you need to instantiate it. Note that you can set a reference variable to point to nothing by assigning it null
We use the new keyword to instantiate an object. New not only allocates memory for the object on the heap, but also calls a constructor method for the object. When complete, new returns a reference to the object to your reference variable
classname objVariableName = new classname();
Garbage Collection is the term for cleaning up all these objects that have been allocated on the heap. In Java this is automatic and occurs at the end of the program or when the JVM detects that an object is no longer needed. Generally this automation is a good thing, however it has two downsides
If the JVM determines you need to do garbage collection
despite some critical task – to bad
JVM is not perfect, you can create code that will cause
Java to fail to garbage collect correctly (thankfully this
is rare!) This causes a memory leak where each run of the
program (or over time) consumes more memory than it frees
up
Finalize() is a method thatwill be called by the GC when an object is to be destroyed. You can use it to do any manual cleanup of your object that you wish
Built in Method / Operator Functionality for every class includes the constructor, the assignment operator and the comparison operator. We will see examples later
The constructor is the method that runs once, when each object is first instantiated. Typically this is used for initializing the default values of the object. The constructor method must be named the same as the class but you can have a different versions based on parameters. If you do not provide constructor(s), then the default version is automatically provided, although it does nothing special
The assignment operator will assign one reference over another. This does not actually copy an object nor change the object on the left hand side. It just changes the reference to look at the right hand side object. This means that the left hand side object is now set to be garbage collected (assuming no other references are looking at it) and it means we now have to reference variables pointing to the same object (right hand side)
The equality comparison operator only works with the reference addresses and not the contexts of those addresses. In other words no two different objects will ever register as equal, even of they have the same values and are of the same class. Only a single object compared with itself will be true. If you want some other sort of equality test (such as comparing values in an object) you will have to write the method yourself
Examples of things that could be objects)
A neighborhood composed of houses
All the accords built off of the Honda Accord plans
Books in a library
Fractions in a math program
Each part of a car engine
Advanced Use of Classes
Inheritance allows a new (derived) class to be based on the code of an old class by using the extends keyword. In this way the derived class gains all the methods and field variables of the base class. The derived class can then change the implementation of any method or add methods / fields to the new class. The big advantage is to reduce the amount of code needed to write as well as ease maintenance. Inheritance is used whenever we can compare two classes with an “is-a” relationship
Examples)
Animal (base class)
Fish (from animal)
Bird (from animal)
Guppie(from fish)
Gold Fish(from fish)
Interface is similar to inheritance, and is used in situations when we either have more than one base class or wish to enforce an interface. The base class is not defined and it is up to us to implement each and every method in it. We use implement as the keyword here and can implement any number of interfaces
Examples)
Events are all interfaces whose details are up to us to specify. Or example, every button can be clicked and so has a clicked event. But, what each button actually does in terms of code will vary by both the program and the button in question
Composition means using objects from other classes inside anther class as part of its code. We can declare such objects as either local variables or field variables as needed. The difference here is that the new class does not (usually) have access to anything other than public methods and properties of objects it uses. This is called a “has-a” relationship
Examples)
A House
house has a refridgerator
house has a oven
house has a bedroom
Example of Composition)
// fraction class in its own file
// allows setting and output of fractions
public class fraction
{
int iNum;
int iDen;
fraction()
{
iNum = 1;
iDen = 1;
}
fraction(int iTop, int iBot)
{
set(iTop, iBot);
}
public void set(int iTop, int iBot)
{
iNum = iTop;
iDen = iBot;
} // set
public fraction add(fraction otherFrac)
{
fraction answer = new fraction();
int iNewDen = iDen * otherFrac.iDen;
int iNewNum = iNum * otherFrac.iDen + otherFrac.iNum * iDen;
answer.set(iNewNum, iNewDen);
return answer;
}
public void output()
{
System.out.print(iNum + "/" + iDen);
} // end output
}
// Class test in its own file
// uses fraction class
public class test
{
public static void main( String args[] )
{
fraction frac1 = new fraction();
fraction frac2 = new fraction();
fraction answer;
frac1.set(4,5);
frac2.set(2,3);
answer = frac1.add(frac2);
System.out.print("answer = ");
answer.output();
System.exit(0); // ends the program
} // end main method
} // end class main
Example of Inheritance)
// fraction class in its own file
// allows setting and output of fractions
public class fraction
{
protected int iNum;
protected int iDen;
fraction()
{
iNum = 1;
iDen = 1;
}
fraction(int iTop, int iBot)
{
set(iTop, iBot);
}
public void set(int iTop, int iBot)
{
iNum = iTop;
iDen = iBot;
} // set
public void add(fraction otherFrac, fraction answer)
{
int iNewDen = iDen * otherFrac.iDen;
int iNewNum = iNum * otherFrac.iDen + otherFrac.iNum * iDen;
answer.set(iNewNum, iNewDen);
}
public void output()
{
System.out.print(iNum + "/" + iDen);
} // end output
}
// fraction2 class in its own file (inherits from fraction)
// allows setting and output of fractions
public class fraction2 extends fraction
{
fraction2()
{
super(); // this is how we refer to a inherited default
// constructor
}
fraction2(int iTop, int iBot)
{
set(iTop, iBot);
}
public void mult(fraction2 otherFrac, fraction2 answer)
{
int iNewDen = iDen * otherFrac.iDen;
int iNewNum = iNum * otherFrac.iNum;
answer.set(iNewNum, iNewDen);
}
}
// Class test in its own file
// uses fraction class
public class test
{
public static void main( String args[] )
{
fraction2 frac1 = new fraction2();
fraction2 frac2 = new fraction2();
fraction2 answer = new fraction2();
frac1.set(4,5);
frac2.set(2,3);
frac1.add(frac2, answer);
System.out.print("frac1 + frac2 = ");
answer.output();
frac1.mult(frac2, answer);
System.out.print("frac1 * frac2 = ");
answer.output();
System.exit(0); // ends the program
} // end main method
} // end class main
Scope and Methods
Scope refers to the visibility the program has at a given line of execution when determining if we can access methods, objects and primitive variables. If we can access one of the above, then it is referred to as in scope. Otherwise, it is out of scope, and we can not access it at that point. It is important to understand that each object has its own copies of variables or objects unless the static keyword modifier is involved
Class WideScope indicates that a method or field variable is available to any method in a particular class. Note that any method or field variable is available to any other object of a given class via the dot naming scheme. However, all other classes must use the rules of encapsulation
LocalScope occurs when a variable is declared and defined inside of a method. In this case only that method of that class can use that variable. If both a local and class wide variable of the same name exists, we assume the local variable is dominant. All local variables (except static ones) are created on the stack (more later) that means that they exist only until the method call returns ro exits