SE251Ex:Chain

Writing a Chain data structure

Description

Create a special data structure, which we decide to call Chain, that stores a sequence of elements - like a List does - but only stores at most one copy of each element - like a Set does. The main difference between a Chain and a TreeSet is that the ordering of the elements depends solely on the order in which they are inserted.

For example, adding elements A, B, C, B, A - in that order - to a List will result in [A,B,C,B,A]. On the other hand adding the same sequence of elements to a Chain will result in [A,B,C]. Below illustrates this in terms of a test case:

Chain<String> chain = new Chain<String>();
assertTrue(chain.add("a"));
assertTrue(chain.add("b"));
assertTrue(chain.add("c"));
assertFalse(chain.add("b"));
assertFalse(chain.add("a"));
assertEquals("[a, b, c]",chain.toString());

As you can see, we want our Chain to be a generic type, meaning it can be parameterised with a specific type of elements. In the above we parameterised Chain with String.

Also, we want to incorporate our Chain to the family of Java Collections. In other words we want it to implement the Collection interface so we can utilise the features from the Java Collections Framework that apply specifically to Collection objects. For example we could do this:

public static void inspect(Chain<String> chain) {
  for (String str : chain) {
     //etc...
  }
}
...
public static void maxAndMin(Chain<Integer> numbers) {
  int max = Collections.max(numbers);
  int min = Collections.min(numbers);
  //etc...
}

A convenient way to doing this is to extend the AbstractCollection class from java.util, which as its name suggests is an abstract class that implements Collection. Realise that AbstractCollection is a superclass of most classes from the Java Collections Framework (ArrayList, LinkedList, HashSet, TreeSet, etc). Also as a bonus, we can make Chain implement a Set at no cost. This way we can perform operations specific to Sets on Chains as well. Below is a template for Chain - complete each of the methods.

import java.util.*;

public class Chain<E> extends AbstractCollection<E> implements Set<E> {
   public Chain() {
      //Create an empty chain
   }
   
   public boolean add(E o) {
      //If o isn't already in the chain, add it to the end of the chain and return true.
      //Otherwise do nothing and return false.
   }
   
   public boolean add(int i, E o) {
      //If o isn't already in the chain, add it at the i'th index and return true.
      //Otherwise do nothing and return false.
   }
   
   public boolean remove(Object o) {
      //If o is in the chain, remove o and return true. Otherwise return false.
   }
   
   public E remove(int i) {
      //Remove the i'th element from the chain and return that element,
   }
   
   public E get(int i) {
      //Return the i'th element in the chain.
   }
   
   public boolean contains(Object o) {
      //Return true if o is in the chain; false otherwise.
   }
   
   public int size() {
      //Return the number of elements in the chain.
   }
   
   public Iterator<E> iterator() {
      //Return an iterator view of the elements in the chain.
   }
}

Test Cases

• The test case TestChain acts as a detailed specification of what your Chain should do.

Tips

You may find it easiest to use a List implementation (Vector, ArrayList or LinkedList) as your backing store. In fact you will find yourself delegating most of the methods to the backing list, as most operations apart from add() would be identical to those of a List. However this certainly isn't the most efficient way, as doing an add() everytime requires a lookup, which is linear time. Think about how you could improve this.

Discussion

Here you can ask questions and discuss stuff