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:
There are nested
if..elseconditions indeleteItem()andinsertItem(). Can this code be more elegant?Does
Sequencelook 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.
