Purpose: To emphasize the object-oriented programming approach used in Java, and to practice working with linked lists. Specifically, you will work with control structures, class-building, interfaces and generics to create and utilize a linked data structure.
Task 1: To design and implement a class LinkedDS< T> that will act as a data structure for accessing sequences of Java Objects. Your LinkedDS< T> class will primarily implement 2 interfaces - SequenceInterface< T> and ReorderInterface. The details of these interfaces are explained in the files SequenceInterface.java and ReorderInterface.java. Read these files over very carefully before implementing your LinkedDS< T> class.
Task 2: To utilize your LinkedDS< T> class to store and manipulate arbitrary length integers. We can think of an integer as a sequence of decimal digits. For example, the number 1234 could be stored as the digit '1' followed by the digit '2' followed by the digit '3' followed by the digit '4'. We will store these digits in a LinkedDS object. Clearly, to perform operations on a number that is stored in this fashion, we must access the digits one at a time in some systematic way. More specific details follow below.
For the details on the functionality of your LinkedDS< T> class, carefully read over the files SequenceInterface.java, ReorderInterface.java and Assig2A.java provided on the CourseWeb folder where you find this assignment description. You must use these files as specified and cannot remove/alter any of the code that is already written in them. There are different ways of implementing the SequenceInterface< T> and ReorderInterface interface methods, some of which are more efficient than others. Think of the best way of implementing these methods in this assignment. A lot of pencil-and-paper work is recommended before actually starting to write your code. Your LinkedDS
public class LinkedDS< T> implements SequenceInterface< T>, ReorderInterface
Important Note: The primary data within your LinkedDS< T> class must be an array list of linked chains as explained below. You may not use any predefined Java collection class (e.g., LinkedList) for other LinkedDS< T> data fields or local variables. You may not declare any arrays except in the toArray() method.
You must use the following instance variables inside the LinkedDS< T> class:
private ArrayList< Node> array; //1-D array of linked chains
private int size; //the number of items in the sequence
private T[] alphabet; //the possible item values (e.g., the decimal digits)
private T firstItem; //the first item in the sequence
private T lastItem; //the last item in the sequence
You should define the inner Node class and add other variables and named constants to follow the secure programming practices we mentioned in class.
Besides the methods of SequenceInterface< T> and ReorderInterface, the following constructors are already provided for you:
public LinkedDS(T[] alphabet)
public LinkedDS(LinkedDS< T> other)
Finally, you will need to override the following method:
public String toString();
This method will return a String that is the concatenation of all of the items in the sequence appended together without spaces. For example, if an LinkedDS object contains the numbers 1, 2, 3, 4, 5, 6, toString() should output: 123456
After you have finished your coding of LinkedDS< T>, the Assig2A.java file provided for you should compile and run correctly and should give output identical to the output shown in the file A2Out.txt. The BagInterface and the ResizableArrayBag classes are provided for you.
To illustrate how to store a sequence of objects as an array of linked chains, let's have an example.
Let's take the sequence 9875732732 as an example. This is a sequence of decimal digits. The sequence alphabet is the set of possible values from which the sequence items are drawn. So, in this example the alphabet is the set {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}. This sequence can be represented using the following diagram. Each of the ten digits of the alphabet is represented by a circle. Every pair of consecutive digits in the sequence results in an arrow in the diagram, and the arrow's label includes the position of the second digit in the pair. For example, because 9 is followed by 8 in the sequence, there is an arrow from 9 to 8 in the diagram. Because the position of 8 in the sequence is 1, the arrow from 9 to 8 has 1 in its label. Because 3 is followed by 2 twice in the sequence, the arrow from 3 to 2 is labeled by 6 and 9, the positions of 2 in the sequence in both occurrences of 32 in the sequence.
We can follow the arrows starting from the firstItem (9), then 8 then 7. At 7, we can go to 3 or 5. We go to 5 because of the label {3} of the arrow from 7 to 5. We can keep following the arrows until we reach the last item. The circles that we will go through represent the sequence. see image.
Here are some properties of the sequence in the example above. Please match these with the methods in SequenceInterface.java.
size() == 10
first() == 9 and last() == 2
predecessor(8, 7) == true but predecessor(9, 2) == false
getFrequencyOf(3) == 2
itemAt(3) == 5
firstOccurenceOf(7) == 2
indexInAlphabet(3) == 3
nextIndex(7, 2) == 5 and nextIndex(7, 7) == 3
prevIndex(2, 6) == 3 and prevIndex(2, 9) == 3
hasSubsequence(732) == true
hasSubsequence(983) == false
The diagram above (which by the way is called a graph) is represented as an array of linked chains. The size of the array is N, where N is the size of the alphabet (10 in the example). The array of chains representation of the diagram above is: see image.
Each entry in the array is the head of a chain. In the example, the first two entries represent empty chains. The node at chain 2 represents that digit 2 is followed by digit 7 at two positions in the sequence, position 6 and position 9. In general, a node in chain i that contains the number j and the set S represents that item i in the alphabet is followed by item j in the alphabet at each of the positions in the set S. Each set of positions is a Bag of Integers.
The sequence after append(7) will look like: see image.
Its array of chains representation is: see image.
After prefix(0): see image.
The second part of this assignment is to write the ReallyLongInt class with the specification given below. You may assume all numbers will be non-negative.
Inheritance: ReallyLongInt must be a subclass of LinkedDS. However, since LinkedDS is generic while ReallyLongInt is not generic, you should use the following header:
public class ReallyLongInt extends LinkedDS< Integer> implements Comparable< ReallyLongInt>
Note that rather than T, the underlying element data type is now Integer. This means that the individual digits of your ReallyLongInt will be Integer objects.
Data: The data for this class is inherited and you may not add any additional instance variables. You will certainly need method variables for the various operations but the only instance variables that you need are those inherited from LinkedDS. Note that you cannot access the LinkedDS instance variables directly from inside ReallyLongInt code. You may only use the public methods of LinkedDS.
Operations: Your ReallyLongInt class must implement the methods shown below. Note that the compareTo() method is necessary for the Comparable interface.
private ReallyLongInt(int size)
This constructor will create as "zeroed out" ReallyLongInt with the given size. Note that this leaves the number in an inconsistent state (having leading zeros), so it should only be used within the class itself as a utility (for example, you will probably need it in your add() and subtract() methods). For this reason, it is declared as private.
public ReallyLongInt(String s)
The string s consists of a valid sequence of digits with no leading zeros (except for the number 0 itself - a special case). Insert the digits as Integer objects, such that the most significant digit is at the beginning (head) of the sequence.
public ReallyLongInt(ReallyLongInt other)
This just requires a call to super. However, it is dependent upon a correct implementation of the copy constructor for the LinkedDS class.
To help you out with the assignment, I have implemented the methods above for you, with comments. See the code in ReallyLongInt.java.
public ReallyLongInt add(ReallyLongInt rightOp)
Return a NEW ReallyLongInt that is the sum of the current ReallyLongInt and the parameter ReallyLongInt, without altering the original values. For example:
ReallyLongInt X = new ReallyLongInt("123456789");
ReallyLongInt Y = new ReallyLongInt("987654321");
ReallyLongInt Z;
Z = X.add(Y);
System.out.println(X + " + " + Y + " = " + Z);
should produce the output:
123456789 + 987654321 = 1111111110
Be careful to handle the addition carry correctly and to process the digits in the correct order. Also, be careful to handle numbers with differing numbers of digits.
public ReallyLongInt subtract(ReallyLongInt rightOp)
Return a NEW ReallyLongInt that is the difference of the current ReallyLongInt and the parameter ReallyLongInt. Since ReallyLongInt is specified to be non-negative, if rightOp is greater than the current ReallyLongInt, you should throw an ArithmeticException. Otherwise, subtract digit by digit (borrowing if necessary) as expected. This method is tricky because it can result in leading zeros, which we don't want. Be careful to handle this case (and consider the tools provided by LinkedDS that will allow you to handle it). For example:
ReallyLongInt X = new ReallyLongInt("123456");
ReallyLongInt Y = new ReallyLongInt("123455");
ReallyLongInt Z;
Z = X.subtract(Y);
System.out.println(X + " - " + Y + " = " + Z);
should produce the output:
123456 - 123455 = 1
As with the add() method, be careful to handle numbers with differing numbers of digits. Also note that borrowing may extend over several digits. See RLITest.java for some example cases.
public int compareTo (ReallyLongInt rightOp)
Defined the way we expect compareTo to be defined for numbers. If one number has more digits than the other, then clearly it is bigger (since there are no leading 0s). Otherwise, the numbers must be compared digit by digit.
public boolean equals(Object rightOp)
Defined the way we expect equals to be defined for objects - comparing the data and not the reference. Don't forget to cast rightOp to ReallyLongInt so that its methods can be accessed (note: the argument here is Object rather than ReallyLongInt because we are overriding equals() from the version defined in class Object). Note: This method can easily be implemented once compareTo() has been completed.
public ReallyLongInt multTenToThe(int num)
Return the result of Multiplying the current ReallyLongInt by 10num. Note that this can be done very simply through adding of 0's.
public ReallyLongInt divTenToThe(int num)
Return the result of Dividing the current ReallyLongInt by 10num. Note that this can be done very simply through shifting.
To verify that your ReallyLongInt class works correctly, you will use it with the program RLITest.java, which is provided for you on the Assignments CourseWeb page. Your output should match that shown in RLITest.txt.
Important Note:
Both the add() and subtract() methods are tricky and have different cases to consider. For these methods especially I recommend working out some examples on paper to see what needs to be considered before actually coding them.