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.
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>();
list.add(0,"apple");
list.add(1,"banana");
list.add(0,"orange");
for(String s: list) {
System.out.println(s);
}
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>();
multilist.add("apple",0,0,0);
multilist.add("banana",1,0,0);
multilist.add("orange",0,2,1);
multilist.add("pear",1,1,3);
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.
ThreeOrderingsList<E>() that creates an empty list.boolean empty() that returns true if the list doesn't have any elements, and false otherwise.int size() that returns the number of elements in the listvoid clear() that restores the list to an empty state.E get1(int index1), E get2(int index2), E get3(int index3)
as described abovevoid remove(E item) that removes an item, as described above (carefully read all
of the assumptions and requirements)void setIterator(int ordering), where ordering can only be 0, 1, or 2, to
set the ordering that the next iterator will follow. If the ordering number isn't valid, an exception
must be thrown (create your own exception type)Iterator<E> iterator() method returns an iterator, as described above.How to do well on this test:
empty, size, clear, add, get, then the iterator and setIterator,
and then remove.get since
get starts from the beginning every timePlease submit it by e-mail to me with the subject 2101 Midterm II.