ECE 234		Lab 6 Square List	design due Wed. 30 Nov. 1 PM

The implementation for lab 5 is due Mon. 28 Nov. at 1 PM.

Problem: Design and implement a square list data structure.

The source for lab 6 is the article "The SquareList Data Structure" by Mark 
Sams in the May 2003 issue of Dr. Dobb's Journal that appears on the course
home page as a pdf file.

You should read the article carefully several times.  You should draw some 
pictures of square lists to see how the operations of insert() and delete() 
work.

Your task is to design a set of classes to implement a square list of 
Comparable objects.  A building block of a square list is a doubly linked list 
of Comparable objects kept in sorted order.  The top vertical list of the 
article is a circular doubly linked list kept in sorted order.  Each 
horizontal list is a doubly linked list kept in sorted order.

A square list that contains m^2 Comparable objects consists of a top circular 
list of m items, each of which is a list of m items.  A square list that 
contains n Comparable objects when n is not a perfect square has some 
restrictions on the sizes of the lists.  The top list has size less than or 
equal to n^0.5 rounded up.  Each vertical list with the possible exception of 
the last list has size equal to either zero or one plus n^0.5 rounded up.  
After each insertion or deletion into a vertical list, you must ensure that 
these size constraints are valid.  The article suggests using shiftLeft() and 
shiftRight() operations to ensure these constraints hold.

The use of distinct classes will help you keep the pointers straight.  The 
classes that support the square list data structure must be generic.  I did 
not find the code on page 40 particularly useful.  

Include a class diagram for lab 6.
Include a technical scenario for "Add element to a square list".

Before 1 PM on Wed. 30 Nov. email yanushka your design for lab 6.
You may submit your drawings by hand before lecture.  

The implementation is due before 1 PM on Fri. 9 Dec.

Feel free to see me in my office or send me email for assistance.