Implementing sequence abstraction

Question

Below is the code that implements sequence abstraction using type abstraction Sequence (in Java):

/**
 * 
 * @author mohet01
 *
 * @param <T>
 */
public class Sequence<T>{
 /**
 * Abstract data type constitutes constructor and selector functions
 * written below under representation that hold below invariant:
 * If a recursive list s is constructed from a first element f and a recursive list r, then
 * • first(s) returns f, and
 * • rest(s) returns r, which is a recursive list.
 */
 /* Representation - start */
 //private static Sequence<?> emptyList = null;
 private T item;
 private Sequence<T> restOfTheList;
 /**
 * Constructor
 * @param first
 * @param rest
 */
 public Sequence(T first, Sequence<T> rest){
 this.item = first;
 this.restOfTheList = rest;
 }
 /**
 * Selector function
 * @param list
 * @return
 */
 private T first(){
 return this.item;
 }
 /**
 * Selector function
 * @param list
 * @return
 */
 private Sequence<T> rest(){
 return this.restOfTheList;
 }
 /* Representation - end */
 /* User interface - starts */
 /* These methods MUST take help of constructor or selector.*/
 /**
 * length of the list
 * @return
 */
 public final int length(){
 return this.lengthOfTheList(0); 
 }
 private final int lengthOfTheList(int length){
 if(this.rest() == null){
 return length + 1;
 }else{
 return this.rest().lengthOfTheList(length + 1);
 }
 }
 /**
 * Get an item from the given position.
 * @param position
 * @return
 */
 public final T getItem(int position){
 if(position == 1){
 return this.first();
 }else{
 return this.rest().getItem(position - 1);
 }
 }
 /**
 * Create a new sequence after deletion of an item at given position
 * @param position
 * @return
 */
 public final Sequence<T> deleteItem(int position){
 if(position <= this.length() && (position > 0)){
 return this.delete(position);
 }
 return this;
 }
 private final Sequence<T> delete(int position){
 if (position == 1){
 if(this.rest() != null){
 return this.rest().deleteItem(position - 1);
 }else{//last element case
 return null; 
 }
 } 
 else if(this.rest() == null){
 return new Sequence<T>(this.first(), null);
 }
 else{
 return new Sequence<T>(this.first(), this.rest().deleteItem(position - 1));
 }
 }
 /**
 * Create new sequence after inserting a new element at given position
 * @param item
 * @param position
 * @return
 */
 public final Sequence<T> insertItem(T item, int position){
 if((position <= this.length() + 1) && (position > 0)){
 return this.insert(item, position);
 }
 return this;
 }
 private final Sequence<T> insert(T item, int position){
 if(position == 1){
 return new Sequence<T>(item, this);
 }
 else{
 if(this.rest() == null){
 return new Sequence<T>(this.first(), new Sequence<T>(item, null));
 }
 else{
 return new Sequence<T>(this.first(), this.rest().insert(item, position - 1));
 }
 }
 }
 /* User interface ends */
 public static void main(String[] args){
 Sequence<Integer> list = new Sequence<Integer>(4, null);
 //Sequence<Integer> list = new Sequence<Integer>(1, new Sequence<Integer>(2, null));
 //Sequence<Integer> list = new Sequence<Integer>(3, new Sequence<Integer>(2, new Sequence<Integer>(1, null)));
 //list = new Sequence<Integer>(4, list);
 //System.out.println(list.length());
 //list = list.deleteItem(1);
 list = list.insertItem(5, 2);
 }
}

---

The above code is tested on python-tutor.

It follows the idea of recursive approach because of this recursive property i.e., item and rest of the sequence unlike node-based sequence.

public level access user API's are final for these reasons.

It is multi-user/multi-thread safe.

Above code is not measured/intend to write space/time efficient code.

My questions:

1. There are nested if..else conditions in deleteItem() and insertItem(). Can this code be more elegant?

2. Does Sequence look good to further maintain relations like inheritance with sub-class and composition within other class in/out of package? Assuming this code is written in a package.

• Ernest Friedman-Hill: This is really not a generative sequence; it's just a very inefficient linked list. A sequence wouldn't have insert/delete/length. On the other hand, an efficient linked list would maintain a length member so you didn't have to count.
• nhgrif: @ErnestFriedman-Hill This sounds like the beginnings of a decent answer--perhaps you could elaborate it into one?
• overexchange: @200_success For you point: "Your Sequence<T>is basically a LinkedListNode<T> by another name" How above code is different from public class SList { private SListNode head; private int size;..}?

Answer 1

Minor bug

/**
 * Get an item from the given position.
 * @param position
 * @return
 */
public final T getItem(int position){
 if(position == 1){
 return this.first();
 }else{
 return this.rest().getItem(position - 1);
 }
}

You need to do a lower-bound check here, namely since your Sequence is a 1-index based implementation, you need to make sure position >= 1. Passing 0 here will result in NullPointerException eventually.

Length checks

Deriving the Sequence length can probably be better expressed as:

return 1 + (rest() == null ? 0 : rest().length());

It's easier to literally express this as "length of sequence is myself and what follows behind", instead of relying on a helper method...

Unit tests

Please create more unit tests to test the expected behavior for unexpected positions, e.g. 0, negative values, far greater than length(), etc.

Performance

Above code is not measured/intend to write space/time efficient code.

Ok... but still, the performance is really bad... inserting and calculating the length of a Sequence is nowhere near instantaneous.

Other comments

IMO, your implementation depends heavily on knowing the exact positions or length of a Sequence at any time, it will facilitate the usage if you have wrapper methods to add to the front, the back, or even just a constructor that accepts only a seed value. Also, do consider implementing the Iterable interface, so that users of Sequence can iterate through them.

Answer 2

Re 1.: If you return in an if block an else is pointless since it will be never reached anyway. Thus insert() can be reduced to:

if (position == 1) {
 return new Sequence<T>(item, this);
}
if (this.rest() == null) {
 return new Sequence<T>(this.first(), new Sequence<T>(item, null));
}
return new Sequence<T>(this.first(), this.rest().insert(item, position - 1));

And delete(), lengthOfTheList(), getItem() likewise.

Answer 3

Each Sequence<T> is immutable. You should make that obvious by marking item and restOfTheList as final members.

---

Are you a fan of public-private partnerships? I think that you can get the job done just as effectively if you cut out the private sector. For example, @h.j.k has noted that length() can just be:

public int length() {
 return this.rest() == null ? 1 : 1 + this.rest().length();
}

The delete(int position) method is more troubling. If the position == 1 condition is met, then you call this.rest().deleteItem(0), which recurses to this.rest().rest().deleteItem(-1), this.rest().rest().rest().deleteItem(-2), and so on. That works, but you end up copying all of the subsequent nodes for no good reason.

I recommend that you avoid calling .length() at all, since that is an O(n) operation. (You would end up unnecessarily copying the list, though, in the case where the position to be deleted is past the end of the list.)

public Sequence<T> deleteItem(int position) {
 if (position == 1) {
 return this.rest();
 } else if (position < 1 || this.rest() == null) {
 return this; // Nothing to delete
 } else {
 return new Sequence<T>(this.first(), this.rest().delete(position - 1));
 }
}

The same goes for insertItem().

I'm concerned about the error handling for insertItem() (and, to a lesser extent, deleteItem()). If you try to insert something beyond one position past the end, then the data is silently discarded — with no indication in the return value, and no exception thrown.

• overexchange: why do we learn node based list in classroom? when the above representation is more-intuitive? Intuitive with an idea: item and rest of the list.
• 200_success: Not sure what you mean. Your Sequence<T> is basically a LinkedListNode<T> by another name.
• h.j.k.: @overexchange because to understand recursion, you must first understand recursion.
• overexchange: I think this condition this.rest() == nulldoes not look necessary in "elseif" of your above answer, and the code looks very elegant!!!
• overexchange: When you say, "Each Sequence<T> is immutable" that mean, the above sequence will be destroyed(after creation) only when jvm goes down, correct?