1

CIS 265 Data 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

 2

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

 Java is primarily an interpreter. 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
 3
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) Language combines 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
 4
 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 any object can access 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

OR classes 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 my knowledge

Private only objects of this class may 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 our code
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 derived or extended class) that
adds/modifies only the changed feature(s) to the base class without,
re-writing the whole thing. As an example, several versions of
 5
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)

Java has a variety OOP 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
 6
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 heap area 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
 7
program (or over time) consumes more memory than it frees
up

 Finalize() is a method that will be called by the GC when an objext

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
 8
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
 9

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);
 10
} // 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;
frac2.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
{
int iNum;
int iDen;

fraction()
{
iNum = 1;
iDen = 1;
}

fraction(int iTop, int iBot)

{
set(iTop, iBot);
}
 11

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);
}
}
 12
// 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 Wide Scope 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
 13

 Local Scope 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

Rules for Scope

· If you trace back through the code the most recent method or
variable declaration and definition in a class is the correct one to
use. That is a local scope always takes precedence over a global
scope.

· To access a specific class wide variable use the dot notation

ObjectInstanceX.variableY;. This works for multiple classes that can
all have the same variable or method name(s)

· To avoid call by reference referring to the same object you must

make a new local object and copy the parameter into it

· To make call by value work like call by reference you will need to
pass the values using a specialized object designed for this and then
changing them will work like call by reference because it is

There are two Memory Locations that we are concerned with

 The Heap is a general pool of memory. The heap is allocated when a

program starts and is freed up when a program terminates. Objects
themselves and their field variables are allocated on the heap. Only
a lack of reference to an object or the completion of a program will
cause things here to be freed up. Note that static local variables
are also stored on the heap
 14

 The Stack contains activation records for each call to a method.

These records contain an indication of what instruction we are
executing as well as what the local variables are, among other
things. Each time a method is called a record is added to the stack.
When that method finishes, the record is deleted and the previous
record is resumed. This is why local variables disappear after a
call is finished. Note that a local reference variable will also
disappear when a call is complete. Its’ associated object (if any)
is on the heap, but will be garbage collected as well if no other
references to it exist

Methods are subprograms that can receive parameters and return a

single reference value or primitive. Each method has a signature
that includes its name and the number, type and order of the
parameters it receives. These parameters must match the arguments in
number, type and order when it is called. Method access can be
affected by

 Encapsulation is required for each method and as described before

 Static modifier means that there will be only one method ever
created for any number of objects. A static method may access static
field variables or call other static methods from the same class.
You may instantiate local objects and access their properties
normally
Method Arguments and Parameters in Java are predefined to use call by
value for all primitives, and call by reference for all objects, no
exceptions

 Call by Value means that the method’s parameter receives a copy of

the value (not the argument’s variable itself) to use. The advantage
here is that we can change this value locally and not affect the
scope of the method where it was called from. Note, since we are
passing a copy of the value, the names of the variables on both ends
do not need to match (although they can)
 15
 Call by Reference means that the method receives the variable from
the calling function’s scope under the name of an alias. Any
modification to that alias will affect the calling method’s scope
since both variable names “refer” to the same value. Once again the
name does not have to match between the arguments listed in the call
and the calling method

Strings are objects but act strangely because the

assignment operator causes a new string to be instantiated.
Because of this they tend to act like call by value

Examples of Scope)

// Class test
// shows off scope

public class test

{

public static void main( String args[] )

{
int iA = 1;
int iB = 5;

System.out.println("main() sees A as " + iA + " and B as " + iB);

meth1(iA, iB);

System.out.println("main() sees A as " + iA + " and B as " + iB);

System.exit(0); // ends the program
} // end main method

public static void meth1(int iX, int iY)

{
iA++;
iX++;
iY++;

System.out.println("m1() sees X as " + iX + " and Y as " + iY);

meth2(iX, iY);
} // end meth2

public static void meth2(int iB, int iA)

{
iA++;
 16
iB++;

System.out.println("m2() sees A as " + iA + " and B as " + iB);

} // end meth2

} // end class main

// Class test
// shows off scope & return

public class test

{

public static void main( String args[] )

{
int iA = 1;
int iB = 5;

System.out.println("main() sees A as " + iA + " and B as " + iB);

intB = meth1(iA, iB);

System.out.println("main() sees A as " + iA + " and B as " + iB);

System.exit(0); // ends the program

} // end main method

public static int meth1(int iX, int iY)

{
iX++;
iY++;

System.out.println("m1() sees X as " + iX + " and Y as " + iY);

iB = meth2(iX, iY);

return( 23 );
} // end meth2

public static int meth2(int iB, int iA)

{
iA++;
iB++;

System.out.println("m2() sees A as " + iA + " and B as " + iB);

 17
return( iA + iB );
} // end meth2

} // end class main

GUI Events

Events are actions that can cause programmer changeable code to run.
Examples of events include a printer reporting out of paper, a user
clicking a mouse, each character entered in a text box, etc. If the
programmer does not over ride these actions, then they do whatever
they would normally do (usually very little). However, it is
possible to use inheritance to add code to events so that they can do
more (or less) then what is normally done

 All Events are objects based on a hierarchy of inherited classes,

this makes expanding the event code easy when new events are needed.
An example, is a mouse click this event object that contains all the
data (which button was clicked, what the mouse was over, etc) and
code needed to know about, and handle, that particular an event

 All Events are originally triggered by the OS. This in turn passes
the event objects to the Java Virtual Machine (JVM, more later). The
JVM periodically checks to see what events it has. If someone’s Java
program has some special event code that matches that event, it will
run that code

Event Handling means dealing with GUI input as if it where

“asynchronous” and “multithreaded.” Asynchronous because we are
unsure when events may occur in relation to our program flow
(when/how events are detected is hidden from the programmer).
Multithreaded, because any number of events can be triggered at one
moment.

The three areas of events we are concerned with are

 Event Source which object triggered (is affected by) the event

 Event Object is an encapsulated “message” describing the event and

containing a reference to the object which caused the event
 18

 Event Listener is the code which waits to receive the event object.
It must both be registered with the event source as well as have code
that will handle the event in question. This is the portion we
write to handle events

How Events Are Handled

 An Event is triggered

 The OS determines that the event is handled by the JVM

 Periodically, the JVM looks for any events that it should handle

 For each event, it will execute either a custom handler we have

registered or the default code, as appropriate

The event listeners we can use are provided as interfaces that you
can implement in your code. Generally, this is done by the use of
inner classes. The event interface system is as follows

EventListener
ActionListener
AdjustmentListener
ComponentListener
ContainerListener
FocusListener
ItemListener
KeyListener
MouseListener
MouseMotionListener
TextListner
 19
WindowListener

How We Set Up Event Listeners

 Define a class and ALL the methods in the class to handle a

particular listener interface. In our case, Write a TextField
handler class that extends ActionListener and defines
actionPerformed()

 Instantiate this class for each class of GUI widget / event

listener you wish. Ex) TextFieldHandler handler = new
TextFieldHandler(); Which is fine for all text fields we my use
since the code will be the same. If this is not the case, we will
need different classes

 Register the instance of your class with each object . Ex)

MyText.addActionListener( handle );

Inner Classes and Anonymous Inner Classes are two ways we can use to
create our event classes. Both involve creating a class inside a
class (our GUI class)

 Inner Classes follow rules similar to other classes except for a

few points. First, that the class is declared and defined inside
anther class. Second, that all encapsulated methods and class wide
variables are available to the inner class as well as any local
variables of the method the inner class is instantiated in
 Anonymous Inner Classes are similar to inner classes, but are
declared, defined and instantiated in one use fashion. I.e. you can
only instantiate them once

The JtextField and JPasswordField GUI widgets hold a single line of

text that is enterable by the user. The JPasswordField varient echos
* to the text field. Use inteli-sense to learn about the methods and
field variables available
 20

Code Example)

// Fig. 13.7: TextFieldTest.java

// Demonstrating the JTextField class.
import java.awt.*;
import java.awt.event.*;
import javax.swing.*;

public class TextFieldTest extends JFrame

{
private JTextField textField1, textField2, textField3;
private JPasswordField passwordField;

// set up GUI
public TextFieldTest()
{
super( "Testing JTextField and JPasswordField" );

Container container = getContentPane();

container.setLayout( new FlowLayout() );

// construct textfield with default sizing

textField1 = new JTextField( 10 );
container.add( textField1 );

// construct textfield with default text

textField2 = new JTextField( "Enter text here" );
container.add( textField2 );

// construct textfield with default text,

// 20 visible elements and no event handler
textField3 = new JTextField( "Uneditable text field", 20 );
textField3.setEditable( false );
container.add( textField3 );

// construct passwordfield with default text

passwordField = new JPasswordField( "Hidden text" );
container.add( passwordField );

// register event handlers

TextFieldHandler handler = new TextFieldHandler();
textField1.addActionListener( handler );
textField2.addActionListener( handler );
textField3.addActionListener( handler );
passwordField.addActionListener( handler );

setSize( 325, 100 );

 21
setVisible( true );

} // end constructor TextFieldTest

public static void main( String args[] )

{
TextFieldTest application = new TextFieldTest();
application.setDefaultCloseOperation( JFrame.EXIT_ON_CLOSE );
}

// private inner class for event handling

private class TextFieldHandler implements ActionListener
{
// process textfield events
public void actionPerformed( ActionEvent event )
{
String string = "";

// user pressed Enter in JTextField textField1

if ( event.getSource() == textField1 )
{
string = "textField1: " + event.getActionCommand();
}
// user pressed Enter in JTextField textField2
else if ( event.getSource() == textField2 )
{
string = "textField2: " + event.getActionCommand();
}
// user pressed Enter in JTextField textField3
else if ( event.getSource() == textField3 )
{
string = "textField3: " + event.getActionCommand();
}
// user pressed Enter in JTextField passwordField
else if ( event.getSource() == passwordField )
{
string = "passwordField: " +
new String( passwordField.getPassword() );
}

JOptionPane.showMessageDialog( null, string );

} // end method actionPerformed

} // end private inner class TextFieldHandler

} // end class TextFieldTest

 22

The JButton GUI widget is a typical button. Use inteli-sense to

learn about the methods and field variables available

Code Example)

// Fig. 13.10: ButtonTest.java

// Creating JButtons.
import java.awt.*;
import java.awt.event.*;
import javax.swing.*;

public class ButtonTest extends JFrame

{
private JButton plainButton, fancyButton;

// set up GUI
public ButtonTest()
{
super( "Testing Buttons" );

// get content pane and set its layout

Container container = getContentPane();
container.setLayout( new FlowLayout() );

// create buttons
plainButton = new JButton( "Plain Button" );
container.add( plainButton );

Icon bug1 = new ImageIcon( "bug1.gif" );

Icon bug2 = new ImageIcon( "bug2.gif" );
fancyButton = new JButton( "Fancy Button", bug1 );
fancyButton.setRolloverIcon( bug2 );
container.add( fancyButton );

// create an instance of inner class ButtonHandler

// to use for button event handling
ButtonHandler handler = new ButtonHandler();
fancyButton.addActionListener( handler );
plainButton.addActionListener( handler );

setSize( 275, 100 );

setVisible( true );

} // end ButtonTest constructor

public static void main( String args[] )

 23
{
ButtonTest application = new ButtonTest();
application.setDefaultCloseOperation( JFrame.EXIT_ON_CLOSE );
}

// inner class for button event handling

private class ButtonHandler implements ActionListener {

// handle button event

public void actionPerformed( ActionEvent event )
{
JOptionPane.showMessageDialog( ButtonTest.this,
"You pressed: " + event.getActionCommand() );
}

} // end private inner class ButtonHandler

} // end class ButtonTest

Combining Both

// Creating test5
import java.awt.*;
import java.awt.event.*;
import javax.swing.*;

public class test5 extends JFrame

{
private JButton plainButton, fancyButton;
private JTextField txtTest;

// set up GUI
public test5()
{
super( "Testing Buttons" );

// get content pane and set its layout

Container container = getContentPane();
container.setLayout( new FlowLayout() );

// create buttons
plainButton = new JButton( "Plain Button" );
container.add( plainButton );

Icon bug1 = new ImageIcon( "bug1.gif" );

Icon bug2 = new ImageIcon( "bug2.gif" );
 24
fancyButton = new JButton( "Fancy Button", bug1 );
fancyButton.setRolloverIcon( bug2 );
container.add( fancyButton );

txtTest = new JTextField( "", 20);

container.add( txtTest );

// create an instance of inner class ButtonHandler

// to use for button event handling
ButtonHandler handler = new ButtonHandler();
fancyButton.addActionListener( handler );
plainButton.addActionListener( handler );

setSize( 275, 100 );

setVisible( true );

} // end ButtonTest constructor

public static void main( String args[] )

{
test5 application = new test5();
application.setDefaultCloseOperation( JFrame.EXIT_ON_CLOSE );
}

// inner class for button event handling

private class ButtonHandler implements ActionListener {

// handle button event

public void actionPerformed( ActionEvent event )
{
JOptionPane.showMessageDialog( test5.this,
"You pressed: " + event.getActionCommand() + " and the
text is " + txtTest.getText() );
}

} // end private inner class ButtonHandler

} // end class ButtonTest

Setting Up Java on Your PC

 You can get an older version of Java off of the CD that comes with
the course book. However, a newer free version is located at
http://java.sun.com/j2se/1.4.2/download.html. Note that this is a
big download. Do it over night if you are a modem user (or go to a
friend’s house with broadband and burn a CD from him/her)
 25

 I do not recommend the IDE that comes on the CD. It is very slow,
difficult to use and quite buggy. To get a decent free IDE that
works on all Windows versions that I am aware of, try going to the
site http://www.jcreator.com/ and downloading the current free
version of JCreator LE. It is only a 1.8 meg download. A “Pro”
version featuring inteli-sense is about $30 and well worth it.

 If you wish to use Java from the command line you will need to set
the Path Environment Variable. Under XP / 2000 this can be set in
control panel -> system -> advanced -> environment variables ->
system variables -> path. Add the following to the path to make it
look like the end of this line ( That assumes that is the version and
location where Java is installed for you – should be correct if you
downloaded from Sun’s site above and changed nothing during
installation )

;C:\Program Files\j2sdk_nb\j2sdk1.4.2\bin; C:\Program Files\j2sdk_nb\

j2sdk1.4.2\lib

 Class Documentation for the various standard components of Java can

be found at http://java.sun.com/j2se/1.4.1/docs/api/index.html. Mark
this and use it when needed

 Some good free tutorial/references include Thinking Java, 3rd

Edition a free downloadable web book which I base my notes in part on
at http://64.78.49.204/. Also Sun has an extensive site on Java
tutorials at http://java.sun.com/docs/books/tutorial/

 Other help can be found on the web at http://www.google.com/ by

searching for the key words. If you needed help on
System.out.println for example. Try the keyword line “Java Tutorial
println” as a good starting place.
 26

Chapter 2: Arrays, Big O, Searching, Design, Array Operations

Arrays

Arrays are an indexed container of the same type of variable. Each

array consists of a number of base types (either objects or
primitives) that use a common array name and an index into that name
to determine which element of the array we wish to access at a given
time. Think of arrays like a freight train and the elements of the
array as the cars on the train. The array itself is an object
regardless of what type of variables the array holds
 27
 If the array stores primitives, the array object on the heap stores
the data directly

 If the array stores objects, then the array stores references to

the objects in the array, which are created independently on the heap
as well. That means that accessing them needs to go through at least
two references

Notes on Arrays

 Arrays start at index 0, so an array declared to be size 10 will

have indexes with the range of 0 to 9. Please pay attention to this!

 Arrays are always dynamically created and so creation time is

increased accordingly. Note that arrays of objects do not
automatically instantiate an object for each element, instead the
element holds a null reference

 Arrays have built in methods such as length() that help keep track
of things for you that you might otherwise have had to track
yourself. Of course, such method calls have the same overhead as
standard method calls

 While the entire array is always passed by reference, individual

elements of each array are passed by reference for all objects, and
by value for all primitives

Code Example)

// SumArray.java
// Total the values of the elements of an array.
public class SumArray
{

public static void main( String args[] )

 28
{
// short cut way of declaring, defining and filling values in
// an array
int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
int total = 0;
int lcv;

// print out each element of the array

for ( lcv = 0; lcv < array.length; lcv++ )
{
System.out.println(“index “ + lcv + “ holds value “ +
array[lcv] );
}

System.out.println();

// add each element's value to total

for ( int counter = 0; counter < array.length; counter++ )
{
total += array[ counter ];
}

System.out.println(“the total is ” + total);

System.exit( 0 );

} // end main

} // end class SumArray

Code Example)

// Pass Array
// Passing arrays and individual array elements to methods.
public class SumArray
{

public static void main( String args[] )

{
// long hand way of declaring, defining and instantiating an
// array
int myArray[] = new int[10];
int total = 0;
int lcv;
 29
// fill in each element of the array with numbers 1 to 10
for ( lcv = 0; lcv < myArray.length; lcv++ )
{
myArray[lcv] = lcv + 1;
}

modifyArray( myArray ); // array passed by reference

// now print out each element of the array

for ( lcv = 0; lcv < myArray.length; lcv++ )
{
System.out.println(“index “ + lcv + “ holds value “ +
myArray[lcv] );
}

System.out.println(“”);

modifyElement( myArray[ 3 ] ); // now attempt to modify

array[3]
System.out.println(“index 3 holds value “ + myArray[3] );

System.exit( 0 );

} // end main

} // end class SumArray

// multiply each element of an array by 2

public static void modifyArray( int array2[] )
{
for ( int counter = 0; counter < array2.length; counter++ )
{
array2[ counter ] *= 2;
}
}

// multiply argument by 2
public static void modifyElement( int element )
{
element *= 2;
}

} // end class PassArray

Multi-Dimensional Arrays in Java are composed of array of arrays of

arrays. This means you can represent such structures as graph paper
 30
(two dimensions) or a Rubix cube (three dimensions), etc. Each
dimension of the array is represented by its own bracket which
handles that dimensions index.
Such arrays are actually implemented as an array of arrays.
Unfortunately, this is slower approach then most other languages
take. But, for all intents and purposes, they still work just like
C/C++ arrays, including being row major. I.e. change the right most
bracket index the fastest and your code will be the most efficient

Declaring and Initializing a multidimensional array can be

accomplished either as

int array[][] = { {1,2}, {2, 3}, {4, 5} };

or

int array[3][2];

Example)

// Pass Array2d
// Passing arrays and individual array elements to methods.
public class test3
{

public static void main( String args[] )

{
int myArray[][] = { {1,2}, {3,4}, {5,6} };
// could also be declared int myArray[3][2];
int total = 0;
int lcv, lcv2;

// show start of array

for ( lcv = 0; lcv < 3; lcv++ )
{
for ( lcv2 = 0; lcv2 < 2; lcv2++ )
{
System.out.println("set " + lcv + "," + lcv2 + " = " +
myArray[lcv][lcv2] );
}
 31
}

modifyArray( myArray ); // array passed by reference

System.out.println("");

// show start of array

for ( lcv = 0; lcv < 3; lcv++ )
{
for ( lcv2 = 0; lcv2 < 2; lcv2++ )
{
System.out.println("set " + lcv + "," + lcv2 + " = " +
myArray[lcv][lcv2] );
}
}

System.out.println("");
System.exit( 0 );
} // end main

// multiply each element of an array by 2

public static void modifyArray( int array2[][] )
{
for ( int counter = 0; counter < array2.length; counter++ )
{
for ( int counter2 = 0; counter2 < array2[counter].length;
counter2++ )
{
array2[ counter ][ counter2 ] *= 2;
}
}
}

} // end class PassArray2d

// Pass Array
// Passing arrays and individual array elements to methods.
public class test3
{

public static void main( String args[] )

{
// long hand way of declaring, defining and instantiating an
// array
int myArray[][] = { {1,2}, {3,4}, {5,6} };
// coul also be declared int myArray[3][2];
int total = 0;
int lcv, lcv2;
 32
// show start of array
for ( lcv = 0; lcv < 3; lcv++ )
{
for ( lcv2 = 0; lcv2 < 2; lcv2++ )
{
System.out.println("set " + lcv + "," + lcv2 + " = " +
myArray[lcv][lcv2] );
}
}

modifyArray( myArray ); // array passed by reference

System.out.println("");

// show start of array

for ( lcv = 0; lcv < 3; lcv++ )
{
for ( lcv2 = 0; lcv2 < 2; lcv2++ )
{
System.out.println("set " + lcv + "," + lcv2 + " = " +
myArray[lcv][lcv2] );
}
}

System.out.println("");
System.exit( 0 );
} // end main

// multiply each element of an array by 2

public static void modifyArray( int array2[][] )
{
for ( int counter = 0; counter < array2.length; counter++ )
{
for ( int counter2 = 0; counter2 < array2[counter].length;
counter2++ )
{
array2[ counter ][ counter2 ] *= 2;
}
}
}

} // end class PassArray

Big O Notation
 33

Algorithm & Heuristic Evaluation is traditionally done using a

notation scheme called Big O. The idea behind this scheme is to
provide a performance measurement for code that is independent of the
hardware that it runs on. We base this evaluation on the product of
the size of the data we will work with (N) and the depth of the
deepest sequence of nested loops that operate on that data. Big O
notation completely ignores constants and lesser terms, as these will
not be dominant when N grows to some arbitrarily large value

Notes on Loops / Big O

 A program without loops is O(1), or constant time. This is

generally ideal as our program works at the same pace regardless of
how much data we throw at it. It is also generally impossible for
any practical application

 Loops usually contribute either O(N), O(lg N) or O(1) to the

algorithms total. If the loop executes once for each of the N data
elements, it contributes O(N). If it executes log N times for each N
data elements, it contributes O(N). And if the loop executes some
fixed number of times regardless of data, it contributes 1

 Only the most expensive nested loop counts toward the maximum total
evaluation for the algorithm. So a program with a nested loop of N,
N and log N, followed by another nested loop of N and N evaluates to
just N2 log N

 The evaluation we generate is only valid among other algorithms

looking at the same granularity of data. I.e. System.out.println is
O(1) if you consider your data to be a string, but O(N) if you count
it as characters
 34
 A typical ranking might be as follows. Note that if your algorithm
enters the realm of exponentials, it is typically not computable for
even fairly small values for N

O(1)
O(log N)
O(N)
O(N log N)
O(N2)
O(N2 log N)
O(N3)
. . .
O(2N) // Here we leave the realm of polynomials and enter
// exponentials

Searching

Searching is one of the two most common algorithms used in computer

sciences today. It entails looking through data to find a matching
value(s). There are several algorithms for searching and the data
structure we are using has a large effect on just which algorithm /
how efficient this process will be. Here are a few things to
remember about searching

 Unique Keys is the value we are searching for unique. If so, we

can stop when we find it. If not then we have non-unique keys and we
can not stop searching until all data has been examined

 Ordered (Sorted) is the data we have guaranteed to be sorted

already or not (unsorted). If so, we can stop searching as soon as
we reach a value larger than we are looking for as well
 O(N) or O(log N) are typical evaluations for searches. This is
much better than sorting

Searching Arrays can be done in a number of ways there are probably

around 10 major search algorithms out there, two of which we will
look at here because they work on single dimensional, arrays and are
fairly straight forward to code and understand

 Linear Search O(N) essentially looks at each item until a match is

found and then stops, unless duplicate keys exist
 35

Snippet Example)

iKey = 100;
Bfound = false;
for ( lcv = 0; lcv < array.length; lcv++)
{
if ( array[lcv] == iKey )
{
bFound = true;
break;
}
}

 Binary Search O(log N) requires that data be sorted and works by

looking at the mid point of the array. If it is not the value we
want, split the data in half and choose the side which the result
could be in. Repeat until key is found or nothing is left to split
(ran out of data)

Snippet Example)

// bin search
// tbl The table of elements
// n The element to be searched for

public class BinarySearch

{
public static boolean BinarySearch(int tbl[], int n)
{
int iLow = 0;
int iHigh = tbl.length-1;

while( iLow <= iHigh )

{
int iMid = ( iLow + iHigh ) / 2;
if( n == tbl[iMid] )
{
return true;
}
else
{
 36
if( n < tbl[iMid] )
{
iHigh = iMid-1;
}
else
{
iLow = iMid + 1;
}
}
return false;
}

OOP Design

OOP Design is almost a field unto itself. The flexibility and power
of OOP come at a price of increased code complexity as well as
increased design complexity. One common approach with data
structures is to have the data itself as one (or more) classes and
anther class to serve as the data structure itself. The main
application (consisting of however many classes) accesses the data
structure, but rarely the data objects themselves to do more than
create or read them. Some things to note

 Composition is used at a minimum. Both the data structure class

and the application class(es) itself will use it

 Not Truly Generic* funnily enough, Java lacks both templates and
overloaded operators which, if present, would allow us to create
universal algorithms and data structures. We can work around some of
these constraints with polymorphism, base object types and
reflection, but it is fairly ugly

 Data Class(es) contain all functionality to do with manipulating

the data and the data itself. Note that if the data is a primitive,
this may not be a necessary part of our solution
 37
 Data Structure Class contains all the functionality needed to deal
with manipulating the data structure. Instantiates the data elements

 Data Structure Functionality should contain at least the following

methods to provide a generic re-usable component; insert, search,
delete. Additional methods could include; set, read, update and
iterate among others. In general we frequently should try to create
atomic methods and build the more complex methods from them

 Main Program contains code that instantiates and manipulates the

data structure. May instantiate and manipulate the odd data element
as well

Code Example)

// highArray.java
// demonstrates array class with high-level interface
// to run this program: C>java HighArrayApp
////////////////////////////////////////////////////////////////

class HighArray
{
private long[] a; // ref to array a
private int nElems; // number of data items

public HighArray(int max) // constructor

{
a = new long[max]; // create the array
nElems = 0; // no items yet
}

public boolean find(long searchKey)

{ // find specified value
int j;
for( j=0; j<nElems; j++ ) // for each element,
{
if( a[j] == searchKey ) // found item?
{
break; // exit loop before end
}
if(j == nElems) // gone to end?
{
return false; // yes, can't find it
 38
}
else
{
return true; // no, found it
}
} // end loop
} // end find()

public void insert(long value) // put element into array

{
a[nElems] = value; // insert it
nElems++; // increment size
}

public boolean delete(long value)

{
int j;
for(j=0; j<nElems; j++) // look for it
{
if( value == a[j] )
{
break;
}
if(j==nElems) // can't find it
{
return false;
}
else // found it
{
for( int k = j; k < nElems; k++ ) // move higher ones down
{
a[k] = a[k+1];
}
nElems--; // decrement size
return true;
}
} // end loop
} // end delete()

public void display() // displays array contents

{
for(int j=0; j<nElems; j++) // for each element,
{
System.out.print(a[j] + " "); // display it
}
System.out.println("");
}
 39

} // end class HighArray

// Main app
////////////////////////////////////////////////////////////////
class HighArrayApp
{
public static void main(String[] args)
{
int maxSize = 100; // array size
HighArray arr; // reference to array
arr = new HighArray(maxSize); // create the array

arr.insert(77); // insert 10 items

arr.insert(99);
arr.insert(44);
arr.insert(55);
arr.insert(22);
arr.insert(88);
arr.insert(11);
arr.insert(00);
arr.insert(66);
arr.insert(33);

arr.display(); // display items

int searchKey = 35; // search for item

if( arr.find( searchKey ) )

{
System.out.println("Found " + searchKey);
}
else
{
System.out.println("Can't find " + searchKey);
}

arr.delete(00); // delete 3 items

arr.delete(55);
arr.delete(99);

arr.display(); // display items again

} // end main()
 40
} // end class HighArrayApp

Code Example)

// classDataArray.java
// data items as class objects
// to run this program: C>java ClassDataApp
////////////////////////////////////////////////////////////////
class Person
{
private String lastName;
private String firstName;
private int age;

public Person(String last, String first, int a)

{ // constructor
lastName = last;
firstName = first;
age = a;
}

public void displayPerson()

{
System.out.print(" Last name: " + lastName);
System.out.print(", First name: " + firstName);
System.out.println(", Age: " + age);
}

public String getLast() // get last name

{
return lastName;
}
} // end class Person

// Data structure
/////////////////////////////////////////////////////////
class ClassDataArray
{
private Person[] a; // reference to array
private int nElems; // number of data items
 41
public ClassDataArray(int max) // constructor
{
a = new Person[max]; // create the array
nElems = 0; // no items yet
}

public Person find(String searchName)

{ // find specified value
int j;
for( j = 0; j < nElems; j++ ) // for each element,
{
if( a[j].getLast().equals(searchName) ) // found item?
{
break; // exit loop before end
}
} // end for

if(j == nElems) // gone to end?

{
return null; // yes, can't find it
}
else
{
return a[j]; // no, found it
}
} // end find()

// put person into array

public void insert(String last, String first, int age)
{
a[nElems] = new Person(last, first, age);
nElems++; // increment size
}
public boolean delete(String searchName)
{ // delete person from array
int j;
for( j = 0; j < nElems; j++ ) // look for it
{
if( a[j].getLast().equals(searchName) )
{
break;
}
} // end for

if( j == nElems ) // can't find it

{
return false;
}
 42
else // found it
{
for( int k = j; k < nElems; k++ ) // shift down
{
a[k] = a[k+1];
} // end for
nElems--; // decrement size
return true;
}
} // end delete()

public void displayA() // displays array contents

{
for(int j=0; j < nElems; j++ ) // for each element,
{
a[j].displayPerson(); // display it
} // end for
}
} // end class ClassDataArray

// main code
////////////////////////////////////////////////////
class ClassDataApp
{
public static void main(String[] args)
{
int maxSize = 100; // array size
ClassDataArray arr; // reference to array
arr = new ClassDataArray(maxSize); // create the array
// insert 10 items

arr.insert("Evans", "Patty", 24);

arr.insert("Smith", "Lorraine", 37);
arr.insert("Yee", "Tom", 43);
arr.insert("Adams", "Henry", 63);
arr.insert("Hashimoto", "Sato", 21);
arr.insert("Stimson", "Henry", 29);
arr.insert("Velasquez", "Jose", 72);
arr.insert("Lamarque", "Henry", 54);
arr.insert("Vang", "Minh", 22);
arr.insert("Creswell", "Lucinda", 18);

arr.displayA(); // display items

String searchKey = "Stimson"; // search for item

// Person found;
 43
found = arr.find(searchKey);
if(found != null)
{
System.out.print("Found ");
found.displayPerson();
}
else
{
System.out.println("Can't find " + searchKey);
}

System.out.println("Deleting Smith, Yee, and Creswell");

arr.delete("Smith"); // delete 3 items
arr.delete("Yee");
arr.delete("Creswell");

arr.displayA(); // display items again

} // end main()
} // end class ClassDataApp

Chapter 3: Sorting, Bubble, Selection, Insertion, Objects

Sorting

Sorting is the other major area of algorithms. Sorting almost always

uses some form of comparison to arrange the data in some order.
Order can be anything consistent such as increasing, decreasing, by
blueness or by time. Here are a few things to remember about sorting

 In Place refers to a sort that uses almost no extra memory than

needed by the original data itself
 44

 In Order refers to a sort that keeps equal valued keys in the same
order they initially appeared in

 O(N log N) or O(N2) are typical evaluations for sorts. This is

higher than searching, but allows us to then use a binary search on
arrays. So, we need to decide between search speed and sort costs.
Note that we typically look at both comparisons and exchanges when
evaluating a sort

 Best Case, Average Case and Worst Case may or may not be different
for a particular sort algorithm. For example, a quick sort is O(N
log N) on average, but if data is almost sorted already, it is O(N2).
The basic sorts in this chapter do not have different cases

 Nearly Sorted Results can allow us to use simplified algorithms.

For example, inserting one item into an already sorted array is an
O(N) operation, and thus simpler than sorting the entire array.
Note, since there are N items to insert the total time is still O(N2)

Simple Sorts All of the simple sorts presented In this chapter are
O(N2), in place and in order. Note that just because they are simple
and slow, does not mean that they do not have uses. They are quick
to code and have low constants so are actually quicker than some of
their fancier brethren for small sizes of N

Bubble Sort works by an outer loop making N passes over N data. Each
inner loop pass then looks at successive pairs of elements in order.
If the inner loop finds that one element is smaller than its
predecessor, it swaps them

 Evaluation O(N2) overall, with O(N2) compares and O(N2) swaps

 45

 Optimizations We can speed this process up some by stopping the

inner loop one element earlier after each outer loop and cut our work
in half. Embed the swap method

Example Code)

// demonstrates bubble sort

// to run this program: C>java BubbleSortApp
////////////////////////////////////////////////////////////////
class ArrayBub
{
private long[] a; // ref to array a
private int nElems; // number of data items

public ArrayBub(int max) // constructor

{
a = new long[max]; // create the array
nElems = 0; // no items yet
}

public void insert(long value) // put element into array

{
a[nElems] = value; // insert it
nElems++; // increment size
}

public void display() // displays array contents

{
for(int j=0; j<nElems; j++) // for each element,
{
System.out.print(a[j] + " "); // display it
}
System.out.println("");
}

public void bubbleSort()

{
int out, in;

for(out = nElems - 1; out > 1; out-- ) // outer loop (backward)

{
 46
for( in = 0; in < out; in++ ) // inner loop (forward)
{
if( a[in] > a[in+1] ) // out of order?
{
swap(in, in+1); // swap them
}
}
}
} // end bubbleSort()

private void swap(int one, int two)

{
long temp = a[one];
a[one] = a[two];
a[two] = temp;
} // end swap

} // end class ArrayBub

////////////////////////////////////////////////////////////////
class BubbleSortApp
{
public static void main(String[] args)
{
int maxSize = 100; // array size
ArrayBub arr; // reference to array
arr = new ArrayBub(maxSize); // create the array

arr.insert(77); // insert 10 items

arr.insert(99);
arr.insert(44);
arr.insert(55);
arr.insert(22);
arr.insert(88);
arr.insert(11);
arr.insert(00);
arr.insert(66);
arr.insert(33);

arr.display(); // display items

arr.bubbleSort(); // bubble sort them

arr.display(); // display them again

} // end main()
} // end class BubbleSortApp
 47

Selection Sort works by an outer loop making N passes over N data.

Each inner loop examines successive data elements, starting with 1
more into to the end after each outer loop to find the minimum
element. After the inner loop swap the first element the inner loop
looked at with the minimum from that pass

 Evaluation O(N2) overall, with O(N2) compares and O(N) swaps

 Optimizations Embed the swap method

Example Code)

// selectSort.java
// demonstrates selection sort
// to run this program: C>java SelectSortApp
////////////////////////////////////////////////////////////////
class ArraySel
{
private long[] a; // ref to array a
private int nElems; // number of data items

public ArraySel(int max) // constructor

{
a = new long[max]; // create the array
nElems = 0; // no items yet
}
public void insert(long value) // put element into array
{
a[nElems] = value; // insert it
nElems++; // increment size
}

public void display() // displays array contents

{
for(int j = 0; j < nElems; j++ ) // for each element,
{
System.out.print(a[j] + " "); // display it
}
System.out.println("");
}

public void selectionSort()

 48
{
int out, in, min;

for(out=0; out<nElems-1; out++) // outer loop

{
min = out; // minimum
for(in = out + 1; in < nElems; in++ ) // inner loop
{
if(a[in] < a[min] ) // if min greater,
{
min = in; // we have a new min
}
swap(out, min); // swap them
}
} // end for(out)
} // end selectionSort()

private void swap(int one, int two)

{
long temp = a[one];
a[one] = a[two];
a[two] = temp;
}
} // end class ArraySel

////////////////////////////////////////////////////////////////
class SelectSortApp
{
public static void main(String[] args)
{
int maxSize = 100; // array size
ArraySel arr; // reference to array
arr = new ArraySel(maxSize); // create the array

arr.insert(77); // insert 10 items

arr.insert(99);
arr.insert(44);
arr.insert(55);
arr.insert(22);
arr.insert(88);
arr.insert(11);
arr.insert(00);
arr.insert(66);
arr.insert(33);
arr.display(); // display items
 49
arr.selectionSort(); // selection-sort them

arr.display(); // display them again

} // end main()
} // end class SelectSortApp

Insertion Sort works by an outer loop making N passes over N data

starting with element 2. Each inner loop pass then works like
areverse bubble sort. Swapping the starting inner loop element back
towards the start of the array until it fits in the correct place

 Evaluation O(N2) overall, with O(N2) compares and O(N2) exchanges

 Optimizations Possibly separate the && conditions and make one a

break inside the loop

Example Code)

// insertSort.java
// demonstrates insertion sort
// to run this program: C>java InsertSortApp
//--------------------------------------------------------------

class ArrayIns
{
private long[] a; // ref to array a
private int nElems; // number of data items

public ArrayIns(int max) // constructor

{
a = new long[max]; // create the array
nElems = 0; // no items yet
}

public void insert(long value) // put element into array

{
a[nElems] = value; // insert it
nElems++; // increment size
}
 50
public void display() // displays array contents
{
for(int j = 0; j < nElems; j++ ) // for each element,
{
System.out.print(a[j] + " "); // display it
}
System.out.println("");
}

public void insertionSort()

{
int in, out;

for(out = 1; out < nElems; out++ ) // out is dividing line

{
long temp = a[out]; // remove marked item
in = out; // start shifts at out
while(in>0 && a[in-1] >= temp) // until one is smaller,
{
a[in] = a[in-1]; // shift item to right
--in; // go left one position
}
a[in] = temp; // insert marked item
} // end for
} // end insertionSort()
} // end class ArrayIns

////////////////////////////////////////////////////////////////
class InsertSortApp
{
public static void main(String[] args)
{
int maxSize = 100; // array size
ArrayIns arr; // reference to array
arr = new ArrayIns(maxSize); // create the array

arr.insert(77); // insert 10 items

arr.insert(99);
arr.insert(44);
arr.insert(55);
arr.insert(22);
arr.insert(88);
arr.insert(11);
arr.insert(00);
 51
arr.insert(66);
arr.insert(33);

arr.display(); // display items

arr.insertionSort(); // insertion-sort them

arr.display(); // display them again

} // end main()
} // end class InsertSortApp

Objects

Sorting Objects involves several additional issues that do not arise

when working with primitives

 Objects consist of the object itself and a reference to the object.

The smart (and normal) way to sort objects is to re-arrange the
references, not to actually copy the objects themselves around during
a swap operation

 Objects cannot be compared with =, <, >, etc, because the value
stored in the reference variable is

 Lack of Operator Overloading means we have to find some way to

compare our objects. There is no standard method of doing this in
Java. One approach is to always use a comparison method that that
will return a less than, equal or greater than when looking at two
objects. Using such a method in our data structure class will not
work if we wish to use primitives however

 Lack of Templates means that our data structure is also not

generic. We can work with things of type object and cast them
accordingly, but this may be no better solution than simply changing
the array type in the data structure code

Example Code)
 52

// objectSort.java
// demonstrates sorting objects (uses insertion sort)
// to run this program: C>java ObjectSortApp
////////////////////////////////////////////////////////////////
class Person
{
private String lastName;
private String firstName;
private int age;

public Person(String last, String first, int a)

{ // constructor
lastName = last;
firstName = first;
age = a;
}

public void displayPerson()

{
System.out.print(" Last name: " + lastName);
System.out.print(", First name: " + firstName);
System.out.println(", Age: " + age);
}

public String getLast() // get last name

{
return lastName;
}
} // end class Person
////////////////////////////////////////////////////////////////
class ArrayInOb
{
private Person[] a; // ref to array a
private int nElems; // number of data items

public ArrayInOb(int max) // constructor

{
a = new Person[max]; // create the array
nElems = 0; // no items yet
}
// put person into array
public void insert(String last, String first, int age)
{
a[nElems] = new Person(last, first, age);
nElems++; // increment size
}
 53
public void display() // displays array contents
{
for(int j = 0; j < nElems; j++ ) // for each element,
{
a[j].displayPerson(); // display it
}
}

public void insertionSort()

{
int in, out;

for(out = 1; out < nElems; out++ )

{
Person temp = a[out]; // out is dividing line
in = out; // start shifting at out

while( in>0 && a[in-1].getLast().compareTo(temp.getLast())>0)

{
a[in] = a[in-1]; // shift item to the right
--in; // go left one position
}

a[in] = temp; // insert marked item

} // end for
} // end insertionSort()

} // end class ArrayInOb

////////////////////////////////////////////////////////////////
class ObjectSortApp
{
public static void main(String[] args)
{
int maxSize = 100; // array size
ArrayInOb arr; // reference to array
arr = new ArrayInOb(maxSize); // create the array

arr.insert("Evans", "Patty", 24);

arr.insert("Smith", "Doc", 59);
arr.insert("Smith", "Lorraine", 37);
arr.insert("Smith", "Paul", 37);
arr.insert("Yee", "Tom", 43);
arr.insert("Hashimoto", "Sato", 21);
arr.insert("Stimson", "Henry", 29);
arr.insert("Velasquez", "Jose", 72);
 54
arr.insert("Vang", "Minh", 22);
arr.insert("Creswell", "Lucinda", 18);

System.out.println("Before sorting:");

arr.display(); // display items

arr.insertionSort(); // insertion-sort them

System.out.println("After sorting:");
arr.display(); // display them again
} // end main()
} // end class ObjectSortApp

Chapter 4: Stacks, Queues, Dynamic Arrays

Stack

A Stack is much like a can of tennis balls, the first ball out of the
can was the last one in the can. This is referred to as a LIFO (list
in, first out) structure in computer science. Stacks can be created
with both lists and arrays (which we will focus on here). A stack
has essentially two basic operations with several optional helper
methods

 Push which adds an item to the top of the stack

 55
 Pop which removes and item from the top of the stack

 Peek which looks at the item from the top of the stack (no removal)

 IsFull which returns true if the stack is full

 IsEmpty which returns true if the stack is empty

 *Length which returns the number of items on the stack

Efficient Array Implementation of a stack means making use of how

arrays work. When pushing, add an element to the end of the used
elements in the array. When popping, do the reverse. In this way
push and pop are both O(1), trying it the other way is not O(1)
unless some kind of a circular (more later) stack is used

Code Example)

// stack.java
// demonstrates stacks
// to run this program: C>java StackApp
////////////////////////////////////////////////////////////////
class StackX
{
private int maxSize; // size of stack array
private long[] stackArray;
private int top; // top of stack

public StackX(int s) // constructor

{
maxSize = s; // set array size
stackArray = new long[maxSize]; // create array
top = -1; // no items yet
}
 56

public void push(long j) // put item on top of stack

{
stackArray[++top] = j; // increment top, insert item
}

public long pop() // take item from top of stack

{
return stackArray[top--]; // access item, decrement top
}

public long peek() // peek at top of stack

{
return stackArray[top];
}

public boolean isEmpty() // true if stack is empty

{
return (top == -1);
}

public boolean isFull() // true if stack is full

{
return (top == maxSize-1);
}
} // end class StackX

////////////////////////////////////////////////////////////////
class StackApp
{
public static void main(String[] args)
{
StackX theStack = new StackX(10); // make new stack
theStack.push(20); // push items onto stack
theStack.push(40);
theStack.push(60);
theStack.push(80);

while( !theStack.isEmpty() ) // until it's empty,

{ // delete item from stack
long value = theStack.pop();
System.out.print(value); // display it
System.out.print(" ");
} // end while
System.out.println("");
 57
} // end main()
} // end class StackApp

Code Example)

////////////////////////////////////////////////////////////////
class Reverser
{
private String input; // input string
private String output; // output string

public Reverser(String in) // constructor

{
input = in;
}

public String doRev() // reverse the string

{
int stackSize = input.length(); // get max stack size
StackX theStack = new StackX(stackSize); // make stack

for(int j=0; j<input.length(); j++)

{
char ch = input.charAt(j); // get a char from input
theStack.push(ch); // push it
}
output = "";
while( !theStack.isEmpty() )
{
char ch = theStack.pop(); // pop a char,
output = output + ch; // append to output
}
return output;
} // end doRev()
} // end class Reverser

////////////////////////////////////////////////////////////////
class ReverseApp
{
public static void main(String[] args) throws IOException
{
String input, output;
while(true)
{
 58
System.out.print("Enter a string: ");
System.out.flush();
input = getString(); // read a string from kbd
if( input.equals("") ) // quit if [Enter]
{
break;
}
// make a Reverser
Reverser theReverser = new Reverser(input);
output = theReverser.doRev(); // use it
System.out.println("Reversed: " + output);
} // end while
} // end main()

public static String getString() throws IOException

{
InputStreamReader isr = new InputStreamReader(System.in);
BufferedReader br = new BufferedReader(isr);
String s = br.readLine();
return s;
}
} // end class ReverseApp

Queues

A Queue is much like a line you would wait in, the first person in
line is the first to get out of the line. In computer science this
type of structure is referred to as FIFO (first in, first out).
Queues can be created with both lists and arrays (which we will focus
on here). There are several flavors of queues, but all have
essentially two basic operations with several optional helper methods

 Enqueue which adds an item to the rear of the queue

 DeQueue which removes and item from the front of the queue
 59
 Peek which looks at the item from the front of the queue (no
removal)

 IsFull which returns true if the queue is full

 IsEmpty which returns true if the queue is empty

 *Length which returns the number of items on the queue

A Circular Queue is a queue, but the enqueue and the dequeue can wrap
around ends of the array by using mod

A Deque stands for doubly ended queue which allows enquing and
dequing from either end of the queue. Best done with a circular
queue

A Priority Queue works like any other queue, except that items are
queued up according to some other priority rather than arrival time.
In this case we must slide values down when we prioritize them, so a
circular implementation will not help here

Efficient Array Implementation of a queue means making use of the

circular queue described above. When enquing, add an element to the
end of the used elements in the array with modulus for wrap around.
When dequeing, remove an element from the beginning of the used
elements in the array. In this way enqueue and dequeue are both
O(1), trying it the other way can only be O(1) for one of those
methods, the other is O(N)

Code Examples)

// Queue.java
// demonstrates queue
// to run this program: C>java QueueApp
 60
////////////////////////////////////////////////////////////////
class Queue
{
private int maxSize;
private long[] queArray;
private int front;
private int rear;
private int nItems;

public Queue(int s) // constructor

{
maxSize = s;
queArray = new long[maxSize];
front = 0;
rear = -1;
nItems = 0;
}

public void insert(long j) // put item at rear of queue

{
if(rear == maxSize-1) // deal with wraparound
{
rear = -1;
}
queArray[++rear] = j; // increment rear and insert
nItems++; // one more item
}

public long remove() // take item from front of queue

{
long temp = queArray[front++]; // get value and incr front
if( front == maxSize ) // deal with wraparound
{
front = 0;
}
nItems--; // one less item
return temp;
}

public long peekFront() // peek at front of queue

{
return queArray[front];
}

public boolean isEmpty() // true if queue is empty

{
return (nItems==0);
 61
}

public boolean isFull() // true if queue is full

{
return (nItems==maxSize);
}

public int size() // number of items in queue

{
return nItems;
}

} // end class Queue

////////////////////////////////////////////////////////////////
class QueueApp
{
public static void main(String[] args)
{
Queue theQueue = new Queue(5); // queue holds 5 items

theQueue.insert(10); // insert 4 items

theQueue.insert(20);
theQueue.insert(30);
theQueue.insert(40);

theQueue.remove(); // remove 3 items

theQueue.remove(); // (10, 20, 30)
theQueue.remove();

theQueue.insert(50); // insert 4 more items

theQueue.insert(60); // (wraps around)
theQueue.insert(70);
theQueue.insert(80);

while( !theQueue.isEmpty() ) // remove and display

{ // all items
long n = theQueue.remove(); // (40, 50, 60, 70, 80)
System.out.print(n);
System.out.print(" ");
}
System.out.println("");
} // end main()
} // end class QueueApp
 62

Hybrid Array

A Hybrid (Dynamic) Array is one that can be resized on the fly. This
is important because arrays normally are fixed in size which
frequently leads to either an over flow because they are too small,
or over utilization of memory. There are two things that we need to
do to create generic dynamic arrays

 Allow the user to specify a size of the data structure at

instantiation. This can be done by declaring a field variable
reference to an array and then actually instantiating it in the data
structure’s constructor

 Allow the array to change size during the data structures use.
Typically we pick some break points to do this. For example, if
array falls beneath 25% utilization, shrink its size by half.
Conversely if the array is full, double its size. Both c neb
accomplished by creating a new array (sized appropriately) and
copying the old array into it. Then set the old array reference to
equal the new array and it will be transparent

Code Example)

TBD In class