Assignment Four, CS351 S2001

Data structure display subsystem

... [software] quality has much in common with sex. Everybody is for it. (Under certain conditions, of course.) Everyone feels they understand it. (Even though they wouldn't want to explain it.) Everyone thinks execution is only a matter of following natural inclinations. (After all, we do get along somehow.) And, of course, most people feel that problems in these areas are caused by other people. (If only *they* would take the time to do things right.)

-- Philip Crosby

We trained hard, but it seemed that every time we were beginning to form up into teams, we would be reorganized. I was to learn later in life that we tend to meet any new situation by reorganizing; and a wonderful method it can be for creating the illusion of progress while producing confusion, inefficiency, and demoralization.

---Petronius Arbiter, 210 BC

ON WRITING
Write quickly and you will never write well; write well, and you will soon write quickly.
Clearness is the first essential, then brevity, and vigor.
Correct repeatedly and stoically.
Erasure is as important as writing.
Prune what is turgid, elevate what is commonplace, arrange what is disorderly, introduce rhythm where the language is harsh, modify where it is too absolute.
The best method of correction is to put aside for a time what we have written, so that when we come to it again it may have an aspect of novelty, as of being another man's work; in this way we may preserve ourselves from regarding our writings with the affection that we lavish upon a newborn child.
Marcus Fabius Quintilianus, Roman Poet, Circa 65 AD

You must work in teams of 2. You may form one yourself, or contact Cami Renfrew and she will put you in one.

You must write a specification and a design for a software subsystem to display a static data structure as a box-and-pointers diagram on the screen.

Aesthetics of the display, and generality for different structures, are explicit design criteria. You will need to handle circular structures, but aesthetics can be sacrificed in that case.

Your specifications must be sufficient to allow someone else to use your library to display their data structures, once it is implemented. This means it must specify all details of the interface.

Your design should be sufficient to allow someone to implement the system without deciding on any algorithms, or classes, or public functions. The design should describe exactly how everything will be implemented internally, what algorithms will be used, what parameters various internal functions will take and return, etc.

When the system it actually implemented, it will use the GTK-- library for the actual graphics. There is copious documentation available, and we will go over it in class and labs. See also /usr/doc/libgtkmm-dev/ on the CS machines.

The documents you turn in should be in plain ascii text. They should look nice when viewed with "more" or "emacs" on an 80 character wide window. If you include figures or diagrams, they should be either written, ie on actual paper drawn using a pencil or pen, or standard bitmap formats (such as PNG or GIF) which can be viewed using "xv" on the CS machines, or postscript that renders correctly using "gv" on the CS machines.

FAQ

Q: Is it okay if I write the documents in [strange wierdo format converted from some other strange wierdo format]?
A: No.

Q: Do diagrams need to be machine readable?
A: No, drawing diagrams and figures using a pen is fine. (We may xerox them so please don't use some crazy kind of writing implement that won't photoreproduce.)

Q: I do all my writing on a computer. What is a ``pen''?
A: A pen is a short rod which, when stroked across the surface of a sheet of paper, leaves a trail of ink. Small pens are used in plotters, a computer output device often seen in architecture firms. Manually operated pens, whose shafts are often made of exotic materials like gold or ivory and elaborately decorated, are available in specialty stores.

Q: How detailed should it be?
A: Imagine that we give it to some other group and tell them to implement it. They should not complain about it not giving enough details, or about having to figure out any part of the implementation strategy. Everything must be spelled out.

Q: Should each member of the team turn in their own copy of the assignment?
A: No, one is enough. Please put both team members' names at the top of at least one of your documents.

Q: Do we have an API to make sure it will plug into the overall system?
A: Yes, you do need one! But you have to design it - that is part of the specification document you must produce. This is part of designing software. The API you define should make someone who wants to use your subsystem happy with how pleasant it will be to use.

Q: Does this mean that we won't be provided with a solution to homework 3 to use for this assignment?
A: No. That is an orthogonal issue - using the API you design you should be able to add some stuff to pretty much any appropriate data structure to get it displayed.

Q: How broad is the family of data structures that this subsystem might be called upon to display?
A: Anything that can reasonably be displayed as a bunch of boxes with arrows between them, in a stylized fashion. You can assume that there are only a small number of arrows out of a box, and the display can get a bit ugly when boxes have more than one incoming arrow.

Q: Should there be text in the boxes of the box-and-pointer diagrams produced?
A: Do you think users of your subsystem would be very happy if all the boxes were simply blank rectangles? Would you be happy if I drew ptree's in class without labels in the nodes?

Q: How can we display a data structure with out knowing the names of it's private data members? How can we recurse down the data structure if we don't know the names of its pointers?
A: You need to define an interface that a user of your subsystem must include in, ie add to, the data structures to be displayed. How exactly this works is your decision.

Q: Most of the programs in /usr/doc/libgtkmm-dev/examples/ won't compile.
A: We've patched these to fix the errors, and working versions are available in ~bap/public_html/teach/S2001/CS351/code/GTK--/examples/. This includes a proper Makefile.

Due date: