Lab #5: Striking sequences via DCLLs

The problem statement

1. we will allow negative numbers in the sequence (heck, let's throw in zero while we're at it!);

2. we will specifically require that the solution be cast in terms of doubly-circularly-linked lists (or DCLLs for short).

OK, here's the original contest problem text:

Say we have a sequence of positive numbers: we can strike off the first one in the sequence, call it k, and then strike off every kth number following. This will give us a new sequence, so that we can repeat the process. Eventually, we will run out of numbers and be doneÑtypically this happens when we reach a 1 at the front. Here is an example: Write a program which will read in a sequence of numbers (possibly on several lines), terminated by a zero (which is not part of the sequence). It should then print out the original sequence and each of the ÒstrickenÓ versions, not with actual slashes through the numbers, of course, but with only the remaining values showing. For example:

		2 3 4 2 3 1 2 5 2 3 4 1 3 2

		3 2 1 5 3 1 2

		2 1 3 1

		1 1

For our purposes, as noted above, we will also allow negative and zero values in the sequence, with the following interpretations:

• zero values cause the first element and none others to be struck from the list;

• negative values cause the first element (i.e., the negative element itself) to be struck, call it negative k, and every kth element from it going the other way round the list, that is to say, starting the count from the last element and going toward the first.

  Furthermore, as stated above, you should use an implementation of DCLLs, which you write yourself, as the basis for your implementation. Make sure that your implementation is generic (uses Objects as the items, so you will need to use a wrapper class such as Integer or MyInteger in this case) and make sure that it is separate from the rest of the program (i.e., there should be separate classes for DCLLs and DCLL elements, not part of the class definitions for this specific problem).

  Set up your program so that you can read the numbers in, either from a GUI or from a file, and come up with a few interesting test cases of your own (say, ones which require at least 5 passes befor ethey finish). You may use different termination signalling for your input (e.g., just take a string from a text field).