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 write 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 example) and AGH Java Chapters 2-3 contain examples
that should help you with this part.
In defining the data fields for these classes, use protected rather than private, as explained 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 example, 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 example, 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 example, a few of the many subsequences of the previous example 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 example, 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 example, 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 example, 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 examples of the use of iterators. AGH Java Chapter 21 discusses collections and iterators:
Section 21.2 contains an example of their use and the ABLIterator in Section 21.14 is close to, but more complicated
than, what you need to write 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 write 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 example, 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 example, 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 write 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 example, in the sense described in Part 8), do not be overly concerned with efficiency.
On the other hand, do not write 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