Programming project 6

LinkedQueue

In the class, we discussed the implementation LinkedStack of the stack trait using linked objects.

Your task is to make an implementation LinkedQueue of the Queue trait, in a file named linkedqueue.scala. Your LinkedQueue must use a singly-linked list with fast append: Enqueue elements at the rear of the list, dequeue them at the front of the list. Both enqueue and dequeue must work in constant time.

Start by compiling the three sources (queue.scala, linkedqueue.scala, checklinkedqueue.scala), and run the test suite:

$ fsc queue.scala 
$ fsc linkedqueue.scala 
$ fsc checklinkedqueue.scala 
$ scala org.scalatest.run CheckLinkedQueueSuite
Run starting. Expected test count is: 3
CheckLinkedQueueSuite:
- basic queue test *** FAILED ***
- many items *** FAILED ***
- interleaved enqueuing and dequeuing *** FAILED ***
Run completed in 1 second, 7 milliseconds.
Total number of tests run: 3
Suites: completed 1, aborted 0
Tests: succeeded 0, failed 3, canceled 0, ignored 0, pending 0
*** 3 TESTS FAILED ***

As usual, when you are done with your implementation, all tests should pass.

Doubly-linked lists

In this project, you should add several interesting methods to the doubly-linked list that we developed for our Josephus program in the lecture.

Download doublylinkedlist.scala and implement the following methods:

• findFirst(x) returns the first node containing the element x (or null if there is no such node);
• findLast(x) returns the last node containing the element x (or null if there is no such node);
• count(x) returns the number of times that the element x appears in the list;
• removeFirst(x) removes the first node containing x (and does nothing if there is no such node);
• removeLast(x) removes the last node containing x (and does nothing if there is no such node);
• removeAll(x) removes all nodes containing elements equal to x from the list;
• count(f) returns the number of elements of the list that satisfy the condition f. Here, f is a function object that maps elements of the list (that is, of type T) to a Boolean.
• filter(f) returns a new DoublyLinkedList that contains copies of all the elements of the list that satisfy the condition f (again, f is a function object).

You can read about function objects in my tutorial.

Use the test suite checkdoublylinked.scala to test your implementations.

CircularList

In the Josephus program discussed in the class, we used a doubly-linked list to store the circle of participants.

Your task is to implement a circular linked list, and to modify the Josephus program to use the circular list.

In a circular list, the previous field of the first list node refers to the last list node, and the next field of the last list node refers to the first list node. (What does this mean when there is only one list node?)

There is no need for sentinels in a circular list. To simplify the design, we do not allow empty circular lists, so the constructor of the CircularList class takes an element argument and creates a circular list with one node.

Download circularlist.scala and complete the implementation of the following methods:

• new CircularList(el) constructs a circular list with one string element;
• first returns some node of the circular list. This must always be the node containing the element given in the list constructor if that node has not been deleted;
• toString returns a string with the contents of the list in the format [A, B, C] (with one space between list elements);
• remove(p) removes the given node from the list (but throws an IllegalArgumentException if this is the last node);
• insert(p, el) inserts element el in front of node p;
• append(el) appends element el at the end of the circular list (this is the same as insert(first, el);
• length returns the number of elements.

Note that there is no prepend function, since for circular lists prepend and append are the same operation.

You can use the test suite checkcircular.scala to test your implementations. Note that you must get toString working for the tests to work at all!

Then download josephus2.scala, and change the code so that it makes use of the CircularList class instead of the DoublyLinkedList class.