Info:

Tasks:

Starter Code:

//---------------------------------------------------------------------------- // SpecializedListInterface. // // Interface for a class that implements a list of bytes // There can be duplicate elements on the list // The list has two special properties called the current forward position // and the current backward position -- the positions of the next element // to be accessed by getNextItem and by getPriorItem during an iteration // through the list. Only resetForward and getNextItem affect the current // forward position. Only resetBackward and getPriorItem affect the current // backward position. Note that forward and backward iterations may be in // progress at the same time //----------------------------------------------------------------------------

package a1;

public interface SpecializedListInterface {

public void resetForward(); // Effect: Initializes current forward position for this list // Postcondition: Current forward position is first element on this list

public byte getNextItem (); // Effect: Returns the value of the byte at the current forward // position on this list and advances the value of the // current forward position // Preconditions: Current forward position is defined // There exists a list element at current forward position // No list transformers have been called since most recent // call // Postconditions: Return value = (value of byte at current forward position) // If current forward position is the last element then // current forward position is set to the beginning of this // list, otherwise it is updated to the next position

public void resetBackward(); // Effect: Initializes current backward position for this list // Postcondition: Current backward position is first element on this list

public byte getPriorItem (); // Effect: Returns the value of the byte at the current backward // position on this list and advances the value of the // current backward position (towards front of list) // Preconditions: Current backward position is defined // There exists a list element at current backward position // No list transformers have been called since most recent // call // Postconditions: Return value = (value of byte at current backward // position) // If current backward position is the first element then // current backward position is set to the end of this list; // otherwise, it is updated to the prior position

public int lengthIs(); // Effect: Determines the number of elements on this list // Postcondition: Return value = number of elements on this list public void insertFront (byte item); // Effect: Adds the value of item to the front of this list // PostCondition: Value of item is at the front of this list public void insertEnd (byte item); // Effect: Adds the value of item to the end of this list // PostCondition: Value of item is at the end of this list }

3 The Implementation of SpecializedList The unique requirement for the SpecializedList is that we are able to traverse it either frontward or backward. Because a doubly linked list is linked in both directions, traversing the list either way is equally simple. Therefore, we use a reference-based doubly linked structure for our implementation. To begin our backward traversals, and to support the new insertEnd operation, it is clear that we need easy access to the end of a list. We have already seen how keeping the list reference pointing to the last element in a circular structure gives direct access to both the front element and the last element. So, we could use a doubly linked circular structure. However, another approach is also possible. We can maintain two list references, one for the front of the list and one for the back of the list. We use this approach in figure below. We use a doubly linked reference based approach, with instance variables to track the first list element, the last list element, the number of items on the list, and the positions for both the forward traversal and the backward traversal. Note that the info attribute of the SListNode class holds a value of the primitive byte type, as was discussed above. 4 Large Integers The range of numbers supported by Java, would seem to suffice for most applications that we might want to write. However, even given that large range of integers, some programmer is bound to want to represent integers with larger values. Let's design and implement a class LargeInt that allows the client programmer to manipulate integers in which the number of digits is only limited by the size of the available memory. Class LargeInt will have a constructor that accepts one argument of type String. Your constructor must be prepared to accept both positive and negative values (+ or , and assume no sign means positive). Because we are providing an alternate implementation for a mathematical object, an integer number, most of the operations are already specified: addition, subtraction, multiplication, division, assignment, and the relational operators. For this assignment, we limit our attention to addition (add) and subtraction (subtract). We will also need a way to change a LargeInt's sign (positive + or negative - ) if desired (setNegative). Additionally, we must have an observer operation that returns a string representation of the large integer. We follow the Java convention and call this operation toString. Please refer to the diagram below to see how we would like to structure LargeInt internally: For the LargeInt ADT, let's start by defining an interface, LargeIntInterface. Let's put the three abstract methods that we described earlier: add, subtract, and setNegative. (Also - why did I not list toString above? Just some food for thought.) So, based on the description as well as the diagrams provided, and some further details here, these are the details of LargeInt: - Implements LargeIntInterface (per above) - Constructor takes one argument of type String - Constructor can handle positive and negative values ( +,, and no sign i.e. positive) - Implements the three abstract methods that you declared in LargeIntInterface: add, subtract, setNegative - add and subtract have one argument for LargeInt, and returns LargeInt. So add is z=x+y where z is the return value, and y is the argument. subtract is z=xy where z is the return value, and y is the argument. - setNegative has no argument and doesn't return anything - toString should return a String representation of the LargeInt - underlying structure must be SpecializedList - LargeInt may use doubly linked nodes, unlike the diagram above - LargeInt nodes do not need to store more than one digit Other than these details, you can do whatever you like to accomplish the implementation (extra helper methods, extra attributes, etc.) 5 Your Tasks - Implement SpecializedListInterface as described above - Design a LargeInt ADT. Start by defining an interface called LargeInt Inter face. Declare the abstract operations (add, subtract, setNegative). Implement it. We are expecting that you use SpecializedList as the underlying structure of LargeInt. Create as many helper methods as needed. - LargeInt may use doubly linked nodes (unlike the diagram above) - LargeInt nodes do not need to have more than one digit - arguments for all methods must be of the type LargeInt with the exclusion of setNegative (shouldn't have argument) - LargeInt's constructor will have one argument of type String. We will assume that the input argument is always a valid integer, in the mathematical sense - thus, we are not bounded by the limitations of the primitive int type in java. This way, you could try to put something like 9999999999999999. Also, be prepared to accept both positive and negative values. Submission Checklist We are expecting at least 4 Java files, all under package al, corresponding to these classes: - SpecializedlistInterface (should not be modified) - SpecializedList (implementation of the above interface. You will need a helper class SListNode) - LargeIntInterface (should have three methods, add, subtract, setNegative) - LargeInt (implementation of the above interface, as well as having a toString method to override the default toString return value. You must use SpecializedList as your underlying structure)