Abstract Data Types

• Recall the idea of Abstract Data Types → Separate public interface from private implementation.

For instance, let us look at a generic queue → A queue that can store object of any type. Sample Implementation:

public class Queue<E>{
	public void add(E element) { ... }
	public E remove() { ... }
	public int size() { ... }
	...
}

• Now the concrete implementation of this queue can either be using a Circular Array or a Linked List.
• The person who implements the Queue has the ability to decide on which implmentation to use.
  • Whichever implementation is used, the public interface will remain unchanged.
  • Completely follows the idea of Abstract Data Types.
• Now the Question is: Does the user of this Queue need to have a choice on which implementation to use(either a circular array or a Linked List)?
  • The above idea does not give user the choice to do so.
• The user of Queue may need to have a choice on the implementation due to several reasons:
  • Efficiency: Circular array is better
  • Flexibility : Linked List is better → can have unbounded size unlike circular array.
• Question: How to offer the user with a choice.

Solution : Multiple Implementations

• Create two separate implementations:

  public class CircularArrayQueue<E>{
  	public void add(E element){ ... }
  	public E remove() { ... }
  	public int size() { ... }
  	...
  }
  

  public class LinkedListQueue<E>{
  	public void add(E element){ ... }
  	public E remove(){ ... }
  	public int size(){ ... }
  	...
  }
  

• Now the user can choose either of the implementations like below:

  CircularArrayQueue<Date> dateq;
  LinkedListQueue<String> stringq;
  
  dateq = new CircularArrayQueue<Date>();
  
  stringq = new LinkedListQueue<String>();
  

• What if the user decides at a later point that he need to use another implementation of Queue???→ In this example , if user realizes that he need the size of the dateq to be flexible (i.e. Implemented using LinkedList).

  • Then he will need to change the declaration of dateq from CircularArrayQueue to LinkedListQueue
  • This is tedious because, anywhere he uses a function that accepts this CircularArrayQueue , the function headers of those functions will have the function parameter declared as CircularArrayQueue .So everywhere this type comes, the user will need to replace the code.

• Solution: Adding Indirection

Adding Indirection

• Create a Queue interface.

  public interface Queue<E>{
  	abstract void add(E element);
  	abstract E remove();
  	abstract int size();
  }
  

• Now provide concrete implementations by implementing this interface:

  public class CircularArrayQueue<E> implements Queue<E>{
  	public void add(E element){ ... }
  	public E remove(){ ... }
  	public int size(){ ... }
  	...
  }
  

  public class LinkedListQueue<E> implements Queue<E>{
  	public void add(E element){ ... }
  	public E remove(){ ... }
  	public int size(){ ... }
  	...
  }