CSci 2101 Takehome exam 2.

Due Sunday, April 16, at 11:59pm

You may not take more than 9 hours on this test.

40 points

You may use the textbook, your lecture notes, in-class examples, and other materials for this class. You may use any Java textbook. General online Java resources may be used with preapproval only (send me an e-mail if you plan to use any). You may not google for any problem-specific keywords.

The work is strictly individual. You may ask me questions in person or by e-mail, you may not ask anyone else any questions about any material on the test. Any exceptions to this rule (such as discussions with a TA) will be announced in class.

Please include your name in comments in each file and comment the program appropriately.

As always, your work is graded not just on correctness, but also on style and the quality of testing.

Implementing a Three-orderings linked list class


Your task is to write tests (JUnit is preferred) and implementation for a class called ThreeOrderingsList, explained below.

A standard linked list has elements in a specific order: you add an element at a given index, and that index indicates the position of that element in the current list. As elements are added and removed, their indices shift. For instance, in the following fragment (using the standard Java linked list) "apple" is added at index 0, then "banana" is added after it at index 1, but then "orange" is added at the index 0, so the final order of elements is "orange", "apple", "banana":

    		LinkedList<String> list = new LinkedList<String>();
		for(String s: list) {

A ThreeOrderingsList is a list in which every element participates in three different orderings. When an element is added, one needs to specify three indices that indicates the element's position in each of the three orderings. Consider the following example:

		ThreeOrderingsList<String> multilist = new ThreeOrderingsList<String>();

Here the first index in each of the "add" methods specifies the positions of the elements in the first ordering, so the first ordering of elements is "orange", "pear", "apple", "banana".
Likewise, the second set of indices gives the positions in the second ordering. The second index in the first "add" (adding "apple") is 0, then "banana" is added at the index 0, then "orange" is added at the index 2 (the last index), and finally "pear" is added at the index 1 (after "banana", before "apple"). The final order is in this ordering is "banana", "pear", "apple", "orange".
The last set of indices for the same three elements are 0, 0, 1, 3, so this ordering is "banana", "orange", "apple", "pear".

To get an element at a given index, you need to specify which of the three orderings you are using. Thus, the list will have three "get" methods: "get1", "get2", "get3". Calling multilist.get1(1) after all the elements are added as above will return "pear". Calling multilist.get2(0) will return "banana". Calling multilist.get3(1) returns "orange".

For this problem the only remove we implement is removing an element by its value, such as multilist.remove("banana"). This will result in the list in which the orderings are:

Important: if there are multiple occurrences of the same element (say, two occurrences of "apple"), only the one that is first in the first ordering is removed.
Use equals method, not ==, to determine which element matches the given one.
Removing an element that is not there doesn't cause any changes and doesn't throw an exception.

Finally, there are three possible iterators for this list, one for each ordering, so we will have the ability to set the which of the iterators we are using. The method multilist.setIterator(0) sets it to use the first ordering. Passing 1 and 2 to the setIterator method sets the order of iteration to the second and third orderings, respectively. Calling this method before a for-each loop sets the ordering for that loop and all future loops, until the order is reset. the default (before the first call to setIterator) is the first ordering.

Your class must be parameterized over a type E (just like OurLinkedList). It must implement Iterable<E>. There are no other interfaces that you need to implement.

The class must be a linked list with a Node inner class which has four fields: item, next1, next2, next3. The next1 field is the address of the next node in the first ordering, the next2 is the address of the next node in the second ordering, next3 is the next node in the third ordering.
The list itself will have three references to the first node: first1, first2, first3. They will point to the starting nodes of the three orderings.

If any of the indices are out of valid bounds, a ListIndexOutOfBounds exception needs to be thrown, indicating which index is out of bounds.

Methods that you need to write

How to do well on this test:

  1. Start early.
  2. Read the entire problem carefully and work through your own short example on paper. You may use your example as a basis of your tests.
  3. Implement required functionality one method at a time. Write tests before you write the methods, test after. I suggest implementing the methods in this order: the constructor, Node, instance variables, then empty, size, clear, add, get, then the iterator and setIterator, and then remove.
  4. If something is not clear, look at the linked list example and ask questions as needed. I will have regular office hours this week. There will also be regular TA hours on Tuesday. I will try to answer my email promptly, but this week is busy with senior seminar, so there may be delays, sorry. Office hours are a better option.
  5. Write comments as your work progresses (not all at the end)
  6. Write tests as your work progresses (definitely not all at the end). Think of cases that you are not sure of, test for those. Test for combinations of methods (add after removing, for instance).
  7. The problem is long, but it's not that difficult. Implement things one at a time, and you will be fine.

Grading criteria

How to submit

Please submit it by e-mail to me with the subject 2101 Midterm II.

CSci 2101 course web site.

The views and opinions expressed in this page are strictly those of the page author. The contents of this page have not been reviewed or approved by the University of Minnesota.