Algorithms and Data Structures

G52ADS Coursework for Autumn 2008

Informal Coursework 3

General Introduction

• This is an unofficial page. For all formal details, see Andrew J. Parkes and his Technicolor website.
• From 1st year Programming, you should know: Core Java 5+, including Collections, Generics, and some interfaces, most notably Collection, List, Comparator, and Comparable.
• By this exercise, you should know jUnit 4.5. It is well worth learning, as it is the industry-wide standard testing tool. Birmingham School of CS has a decent tutorial on-line.
• It's heartily recommended that you learn to use Java Logging and a version control system such as Subversion or Mercurial. (There could have been a lecture or two on CVS in G51SWT.)
• It's heartily recommended that you learn to use and one of great IDEs there are for Java. The big & free IDEs are NetBeans and Eclipse, then there is JBuilder, and last but not least, there is a very nice "learn Java" IDE by the name of Blue J.
• The recommended Java textbook is the 4th edition of Eckel's Thinking in Java (available in the library or at Amazon). The first seven chapters are available for free here. The complete, if slightly out-dated, 4th revision of the 3rd edition is available for free here.
• When stuck, don't panic. Try to think for a bit. Then try Google, the documentation, and the textbook, and when all fails, go and see Jakub in B78. Beware, though: If he can google up the answer within five seconds, he may be reluctant to answer better questions you could have in the future.

The Assignment

The goal is to implement Interface SmartList as declared here. Roughly, this is:

public interface SmartList<E> extends List<E> {

    // First, notice this extends Collection (but should update the indices)
    
    // Second, notice this extends List (but should update the indices)
    
    // Finally, notice the new bits:
    
    // Preprocess an index for a given Comparator
    void preprocess(Comparator c);
    
    // Binary-search and range-retrieval using the given comparator
    int firstIndexOfEqual(Comparator c, E e);
    int lastIndexOfEqual(Comparator c, E e);
    List<E> subListEqual(Comparator c, E e);
    void removeAllEqual(Comparator c, E element);    
}

This should be reasonably easy to do either using linked lists, or any other data structure you fancy.

Implementation Details

Your implementation should:

1. implement a void constructor, following the general contract for Collection<E>
2. implement a constructor taking an argument of type Collection<E>, which copies all the elements, following the general contract for Collection<E>
3. implement the size query operations (size(); and isEmpty();) of Collection<E>, following the general contract for Collection<E>
4. implement the element query operations (contains(E e); iterator(); toArray(); toArray(E[] a);) of Collection<E>, following the general contract for Collection<E>
5. implement modification operations (add(E e); remove(Object o); containsAll(Collection<?> c); addAll(Collection<? extends Comparable> c); removeAll(Collection<?> c); retainAll(Collection<?> c); clear();) of Collection<E>, following the general contract for Collection<E>
6. implement positional access (get(int i); set(int i); remove(int i); of List<E>), following the general contract for List<E>
7. implement iteration (listIterator; listIterator(int i);) of List<E>, following the general contract for List<E>
8. implement hashing (methods equals(Object o); and hashCode();), following the general contract for Object
9. throw UnsupportedOperationException when a method is not supported and throw ClassCastException when an element of unsupported type is encountered, following the general contract for Collection<E>
10. implement all further methods (preprocess(Comparator c); firstIndexOfEqual(Comparator c, E e); lastIndexOfEqual(Comparator c, E e); subListEqual(Comparator c, E e); removeAllEqual(Comparator c, E element);) specified in the interface SmartList<E>, following the contract for SmartList<E>

Submission

You are given an interface AntherList and a test suite AntherListTest in a zip file, and are expected to submit a zip file with an implementation AntherListImpl which passes the test suite AntherListTest via cw. Please feel free to work in groups, but please do not use any nasty tricks. In particular, please consult classes SmartListTrick1 and SmartListTrick2 for suggestions of what should not be submitted.

See more of Jakub's homepage or the list of exercises, if you please.