ASSIGNMENT : Java object oriented program

Overview

The purpose of this assignment is for you to gain experience with object oriented programming in Java: in particular,

the ideas of inheritance, dynamic binding (virtual methods), overriding and overloading methods, iterators (aka

generators). It will also give you some exposure to how some programming language features are implemented,

i.e., what happens "behind the scenes" when you execute a program. Although no language provides the exact features

in this assignment, a number of languages (e.g., Awk, Icon, LISP, CLU, Sisal) do provide similar features. (In

fact, you could define a little language, using techniques from the first program, that would contain features like

those in this assignment.)

Your program needs to provide several abstractions for three kinds of finite sequences of integers: ‘constant’,

‘delta’, and ‘jumble’. In a ‘constant’ sequence, all elements are the same; in a ‘delta’ sequence, successive elements

differ by a constant; and in a ‘jumble’ sequence, there are no restrictions on elements. Your program will

also be defining iterators and addition on these sequences. Details of these are given below in each part of this

assignment.

N.B., you are restricted as to how you prepare your code. See “Details” before you start coding.

attached code.rar To understand what is doing, tutor needs to read whole requirement. To check whether your work is correct or not, type "make runv" as sample.jpg under Linux machine To get idea, sometime, you can check Main.java to see what is passed to the functions. We need to work on "Plus.java" Not Main.java 

Part 1: Basic Derivation

You will be given a Seq class. From it, derive classes whose constructors’ signatures are:

Constant( int num, int value )

Delta( int num, int initial, int delta )

Jumble( int [] values)

In each class, provide code for the class’s constructor and override the toString method. (toString comes from

Object, so it doesn’t need to be declared in Seq.) toString for a Constant gives the string

[ num : value ]

E.g.,

[ 4 : 11 ]

toString for a Delta gives the string

< num : initial &delta >

E.g.,

< 4 : 10 &-2 >

(The & almost looks like a lowercase delta on some screens.)

toString for a Jumble gives the string

{ num : val1 val2 ... }

E.g.,

{ 4 : 10 12 11 18 }

See the correct output files for details on spacing.

You may assume that num is non-negative. Do not impose a fixed upper limit on the number of integers in a Jumble

(or other sequence).

As special cases (which slightly simplify later parts), a Constant or a Delta with a num of zero should have its other

field(s) stored as zero. E.g., for

Delta( 0, 10, 23 )

zero is stored for its initial and delta and toString gives the string

< 0 : 0 &0 >

A zero-length Jumble will have an empty array, so it doesn’t need to be handled specially.

Store only a constant amount (i.e., O(1)) of information for a Constant and a Delta. That is, do not expand the

sequence and store it (say in an array), just store the information needed to later generate the sequence. A Jumble

needs to make a copy of its array argument (not just keep a reference) in case the array is changed. Use System.

arraycopy. Store a Jumble as an array (see “Details”).

Louden Sections 10.2-10.4 (especially the ClosedFigure ex) and AGH Java Chapters 2-3 contain exs

that should help you with this part.

In defining the data fields for these classes, use protected rather than private, as describeed further in the next section.

Part 2: The min method

Define a method, min, that returns the minimum value in a sequence. More specifically, define an abstract min

method in the Seq class with signature

public abstract int min()

Provide code for the min method in each sequence class.

As a special case, for any sequence that contains no numbers, min returns 0.

Use only a constant amount (i.e., O(1)) of time to compute the min of a Constant and a Delta. That is, do not

expand the sequence and then search it for the minimum value; instead, compute the minimum from the information

already stored in the sequence object. Use only linear time (i.e., O(N), where N is the size of the sequence) to

compute min of a Jumble (i.e., do the obvious: search the underlying array).

Part 3: Iterators over Sequences

Define a SeqIt interface to serve as an iterator (aka generator) over Seq. Implement, from SeqIt, each of the following

classes: a ConstantIt class to serve as an iterator over Constant, a DeltaIt class to serve as an iterator over Delta,

and a JumbleIt class to serve as an iterator over Jumble. For ex, ConstantIt’s constructor has signature

ConstantIt( Constant s )

The values returned by one of these iterators are the values in the sequence, in order of appearance, with which the

iterator is associated. More precisely, define for each class the iterator methods

// any more elements?

public boolean hasNext();

// return the next element and advance iterator to following item.

public int next();

The iterator classes need access to fields in the associated classes. Declaring these fields as protected (as noted in

Part 1) allows such access since these classes are in the same “program” package. If this were a “real” program,

then we would define a separate package for these classes. However, we want to avoid some of the complications

involving packages. (These complications are not conceptual, just practical, dealing with classpaths, etc.) Note that

in C++ each iterator class would be made a friend of its associated class.

The Jumble iterator is not allowed to copy the array of its associated object; it may, of course, reference it. Other

iterators may copy information from their associated classes. Each iterator object must use only constant (i.e.,

O(1)) space. You may assume that a sequence is not deleted (or modified) while an iterator is active on it.

If next() is invoked when no elements remain, then your program is to print an appropriate error message to System.

err and then System.exit(1);

Also, add a new class JumbleUser, which contains the method with signature

public static int lengthLongestNDCSS1(Jumble j)

NDCSS stands for non-decreasing, contiguous subsequence. To understand what all that means, recall that a Jumble

represents a sequence. For ex, it might consist of the elements:

5 6 7 1 2 2 3 2 4 5 6 9 0 0 3

A subsequence of a sequence S is itself a sequence; it contains some of the elements S in the same order as they

appeared in S. For ex, a few of the many subsequences of the previous ex sequence are:

5 6

7

1 2 2 3

2 4 5 6 9

3 2 4

5 7

6 0 3

A contiguous subsequence of a sequence S is just a subsequence of S in which the elements appear contiguously

within S. For ex, of the previous subsequences, the first five subsequences are contiguous, but the last two are

not. Finally, non-decreasing means that for any two adjacent elements, the first element is £ the second element.

For ex, of the continguous subsequences,

5 6

7

1 2 2 3

2 4 5 6 9

are non-decreasing. But,

3 2 4

is not non-decreasing.

The problem is the find the length of the longest NDCSS for Jumble j. Continuing the ex, the length of the

longest NDCSS is 5 (i.e., the length of "2 4 5 6 9"). If Jumble j is zero-length, lengthLongestNDCSS1(j) returns 0.

Since an NDCSS is contiguous, this problem has a straightforward solution. Your solution is allowed to allocate

only a constant amount (i.e., O(1)) of space. Your solution is allowed to use only a linear amount of time (i.e.,

O(N), where N is the length of Jumble j).

lengthLongestNDCSS1’s code must use the JumbleIt iterator in a meaningful way. That is, it is to use hasNext() and

next(). It is not to access directly the fields in Jumble (or use access methods in Jumble, etc.); instead it uses JumbleIt

to do so indirectly. (Don’t bother writing symmetric methods for Constant or Delta, although those would be

even more straightforward.)

The test program gives many exs of the use of iterators. AGH Java Chapter 21 discusses collections and iterators:

Section 21.2 contains an ex of their use and the ABLIterator in Section 21.14 is close to, but more complicated

than, what you need to prepare for JumbleIt.

Part 4: Adding Exceptions to Iterators

Change the behavior of next() so that if it is invoked when no elements remain, then it just throws a UsingIterator-

PastEndException. That is, next() now has the signature

public int next() throws UsingIteratorPastEndException

You’ll need to define the class UsingIteratorPastEndException, with an appropriate constructor (similar to that in

the notes; also see the correct output for output details). In practice, you would likely use Java’s NoSuchElementException,

but it’s important to see how to declare your own exceptions. Also, Java’s NoSuchElementException is a

RuntimeException, which is an unchecked exception; recall that means that the exception need not be declared in a

method’s throws clause if the method might throw the exception. In practice, UsingIteratorPastEndException

should be a RuntimeException, but we intentionally don’t do that (and instead make it a checked exception) just to

give you practice with throw clauses, etc.

A coding detail: To prevent warnings from javac (with -Xlint), e.g.,

UsingIteratorPastEndException.java:1: warning: [serial] serializable

class UsingIteratorPastEndException has no definition of serialVersionUID

put in the top level of the UsingIteratorPastEndException class:

static final long serialVersionUID = 98L; // any number works here.

Because next() can now throw an exception, you’ll need to revise the body of lengthLongestNDCSS1() in class JumbleUser.

Also, add a new method to class JumbleUser:

public static int lengthLongestNDCSS2(Jumble j)

It computes the same result as lengthLongestNDCSS1, but in a different way. lengthLongestNDCSS2 can use only

the iterator’s next() method (not the hasNext() method). It must use try/catch in meaningful ways. lengthLongest-

NDCSS2() must not call (directly or indirectly) lengthLongestNDCSS1. Note: this is not a recommended programming

style, but it will help you see how exception handling works. Hint: use try/catch in place of hasNext(); see

the test program.

Part 5: Creating Iterators

Extend the Seq class by adding the method

SeqIt createSeqIt()

Implement this method in each of the Constant, Delta, and Jumble classes. In the Constant class, it returns a new

ConstantIt for the object. It behaves similarly in the Delta and Jumble classes. This method provides a nice way of

creating an iterator for any kind of Seq; examine the test program to understand this important point.

In practice, one would prepare this part before or as part of Part 3, but we choose to do it in this order to simplify the

testing of the iterators. Also, in practice, one would extend Seq from Java’s Collection class and one would extend

the iterators from Java’s Iterator class. However, doing so would require dealing with some additional complexities

(e.g., additional methods, generics), so we choose to do it this simpler way.

Part 6: Polymorphic Overloaded Plus

Define a polymorphic plus overloaded method on sequences. It returns a new sequence formed by adding corresponding

elements in the two sequences. If one of the sequences is shorter than the other, the new sequence is the

length of the shorter and the extra elements in the longer sequence are ignored.

The signatures are

Seq plus (Constant, Constant)

Seq plus (Delta, Delta)

Seq plus (Jumble, Jumble)

In this part, the arguments to plus are both sequences of the same kind. plus returns a new sequence object; in this

part, each plus must return an object of the same kind as its arguments. (Part 8 deals with simplification.)

There are, in general, several ways to code such methods. One could define them within the individual sequence

classes. However, you must define them as public static methods in a new Plus class. (As in the previous part,

this code will be able to access the data fields of the sequence classes. In C++, these methods would be declared as

friends.) Do not add anything new to the sequence classes.

Part 7: More Polymorphic Overloaded Plus

Add to the Plus class new methods so that the arguments to plus can be any kind of sequence. In particular, provide

the methods:

Seq plus (Constant, Delta)

Seq plus (Delta, Constant)

Seq plus (Constant, Jumble)

Seq plus (Jumble, Constant)

Seq plus (Delta, Jumble)

Seq plus (Jumble, Delta)

For this part, the first two plus methods above each must return a Delta and the rest must return a Jumble. (Part 8

deals with simplification.)

Part 8: Optimizing the Result of Polymorphic Plus

For this part, we’re concerned with minimizing the costs of creating the result sequence from the plus methods.

Our measure of cost here is simply space; we’ll ignore time. Assume that the relative costs of creating the different

kinds of sequences, starting with the least expensive, are (in all cases):

Constant

Delta

Jumble

For ex, it is always better to create a Delta rather than a Jumble. So, if the result of a plus can be expressed as

a Delta instead of as a Jumble, then the plus method should return a Delta. Similarly, other results can also be optimized;

see the correct output.

Note that this part concerns itself only with optimizing the result sequences of plus, not with the actual creation of

sequences; i.e., the Constant, Delta, and Jumble constructors must remain as they were in the previous part.

You are allowed to allocate only a constant amount (i.e., O(1)) of space. That is, the amount of space you allocate

in deciding what kind of sequence to return must be independent of the length of the sequences and must work for

sequences of any length. The single exception is that you may allocate an int array that is passed to the Jumble constructor,

but only after you have decided to return a Jumble. Recall that time is free in our definition of cost, so feel

free to use computing time to analyze the sequences.

Note that the above implies that you cannot just compute the result into a Jumble and then simplify it into either a

Delta or a Constant.

It’s fine to have a single plus method with signature ‘Seq plus(Seq, Seq)’.

Hint: a brute force approach to coding this problem will work, but there’s a rather elegant approach that will

require quite little coding effort. Here, brute force means a case analysis considering the possible combinations of

the types of the two operands of plus and the possible outcomes of plus on those operands. Think about it. A correct

brute force approach will earn half the points for this part. (I don’t plan to give further hints on this part.)

Details

• You must use Java 1.7 (as you did on the previous Java assignment), not Java 1.4.

• You will be given an initial Seq class, an initial SeqIt interface, and a Makefile for each part. Your code for each

part must work with the provided Makefile. (You won’t need to modify the Makefiles.) It asks the Java compiler

to give all possible warnings about your code. Your code for each part must compile without any warnings.

• Each class or interface X must be put in its own X.java file.

• Create private methods and fields of your choice, but no public or protected methods or fields not explicitly

assigned.

• Use only ints, booleans, and arrays of ints in your code. Use String only in toString methods and error messages.

Do not use any predefined Java or other package.

• For ex, do not use java.util.ArrayList, anything in java.util.Arrays, java.util.Vector, etc.

• Exception: you may use methods in String and the println and print methods from System.out and System.

err.

• Exception: you may use Java’s Math.min and Math.max.

• Exception: the UsingIteratorPastEndException class needs to extend Java’s Exception class.

In particular, using any Java collection or iterator would trivialize parts of this assignment and you will receive no

credit. One purpose of this assignment is for you to prepare your own iterators (some students in previous offerings

of this course have never written an iterator class).

• This program has no input data. Instead, you will be given test programs that will employ and exercise your

classes. You may modify the tests during debugging (e.g., by commenting out some advanced tests, inserting

additional code or tests, etc.) but your program must work on the unmodified and, as usual, possibly other tests.

• “Correct” output will also be given. Be sure to use the provided test files and test scripts. Your output must

match the “correct” output, except for the wording of and the level of detail in the error messages. By “match”,

we mean match exactly character by character, including blanks, on each line; also, do not add or omit any blank

lines. Note: there may be a blank at the end of some lines. (So, make your output conform to the given, correct

output and then use “make run” or “make runv”, which employs diff to test for and display differences.)

• Express your program neatly. Part of your grade will be based on presentation. Indentation and comments are

important. Unless it’s immediately obvious, be sure to define each variable used and each method with a concise

comment describing its purpose.

• Except as specifically noted (for ex, in the sense described in Part 8), do not be overly concerned with efficiency.

On the other hand, do not prepare a grossly inefficient program.

• Grading will be divided as follows.

Percentage

5 Part 1: Basic Derivation

5 Part 2: The min method

15 Part 3: Iterators over Sequences

15 Part 4: Adding Exceptions to Iterators

10 Part 5: Creating Iterators

20 Part 6: Polymorphic Overloaded Plus

20 Part 7: More Polymorphic Overloaded Plus

10 Part 8: Optimizing the Result of Polymorphic Plus

• In seeking assistance on this project, bring a listing of the last working part along with your attempt at the next

part.

• Work in an incremental style, focusing on a small piece of a part at a time, and getting that to work, before moving

on. Unless you are a truly expert programmer and designer, don’t try to solve the whole program, or even an

entire part, at a time.

• A message giving exact details of what to turn in, where the provided source files are, etc. will be posted. You

will be expected to turn in all working parts along with your attempt at the next part. So, be sure to save your

work for each part. No credit will be given if the initial working parts are not turned in.

• Points will be deducted for not following instructions, such as the above.

Attachment:- Code.rar

Attachment:- sample.jpg