Author: Dekai Wu
Date: Due 2014.09.16 at 23:00 by CASS
Download: http://www.cs.ust.hk/~dekai/2012H/assignments/a0.tar.gz
Assignment page: http://www.cs.ust.hk/~dekai/2012H/assignments/a0/html/
Course page: http://www.cs.ust.hk/~dekai/2012H/
You've been assigned to implement a linked list data structure. Specifically, you will implement a simple library supporting singly linked lists, which other programs will then use for purposes that you do not have to care about.
If there is ever any error in the way that your library is used, your library functions should print the string ERROR on standard error (cerr << "ERROR"), and call exit(1) to terminate program execution.
As a starting point, you are being given top-level requirements in the form of a skeleton implmentation containing the desired API and certain required details of the implementation approach. Download the package at the top of this page, then:
$ tar xzf a0.tar.gz // unpack the archive
$ cd a0
$ make
g++ -c main.cpp -o main.o
g++ -c linkedlist.cpp -o linkedlist.o
g++ main.o linkedlist.o -o main
$ main
Bus error: 10
You will see the test program crash, since you haven't implemented the library functions yet; only dummy functions are in the code you've been given.
You'll need to implement:
Cell* make_int(const int i) returns a newly constructed int cell, i.e., a leaf node initialized to hold the int value i Cell* make_double(const double d) returns a newly constructed double cell, i.e., a leaf node initialized to hold the double value d Cell* make_symbol(const char* const s) returns a newly constructed symbol cell, i.e., a leaf node initialized to hold the symbol name s Node* make_node(Cell* const my_elem, Node* const my_next) returns a newly constructed linked list node, i.e., a node initialized to hold the two pointers my_elem and my_next bool intp(Cell* const c) returns true iff the cell pointed to by c is an int cell bool doublep(Cell* const c) returns true iff the cell pointed to by c is a double cell bool symbolp(Cell* const c) returns true iff the cell pointed to by c is a symbol cell int get_int(Cell* const c) returns the value in the int cell pointed to by c (error if c is not an int cell) double get_double(Cell* const c) returns the value in the double cell pointed to by c (error if c is not a double cell) string get_symbol(Cell* const c) returns the value in the string cell pointed to by c (error if c is not a string cell) Cell* get_elem(Node* const n) returns a pointer to the data held by this node n Cell* get_next(Node* const n) returns a pointer to the next node in the linked list ostream& operator<<(ostream& os, Node* const n) prints the list pointed to by
to the output stream os, in parentheses
Notice that even though these are just ordinary functions (not member functions of a class), nevertheless this set of functions constitutes an interface for an abstract data type; we'll discuss more background on this particular ADT below. The way that Cell.hpp specifies the ADT interface is nice because it makes very few assumptions about how the concrete implementation might be done. (Good object-oriented programming style does not necessarily require using classes! For example, see Scott Myer's article How Non-Member Functions Improve Encapsulation.)
The file that you received just connects all the functions to a dummy example implementation of the ADT that makes use of a super-simple, incomplete Cell class. This dummy example implementation isn't actually capable of building a list data structure with pointers and nodes.
In this assignment, cells can hold three kinds of data: int, double, and symbol. You need a way to store any of these types of values in your cells. How do you do this efficiently?
The obvious naive way is just to have four data members:
struct Cell { ... int int_m; double double_m; char* symbol_m; };
But this is a terribly inefficient waste of memory. Any instance of a Cell will only be using one of these data members. So a better way is to use a union:
struct Cell { union { int int_m; double double_m; char* symbol_m; }; };
Unions exist in both C and C++. A union is sort of like a struct, except that a struct provides memory space to simultaneously store all its members, whereas a union provides memory space to store only one of its members at a time. So this way, we won't waste memory space.
The only problem is: when you're using a union, how do you know which of the data members is the valid one? C++ won't tell you; it is your program's own responsibility to keep track of this. If you don't, you can easily create horrible bugs. For example:
Cell* c = new Cell;
c->double_m = 2.718;
cout << c->int_m; // whoops! will print out a garbage int
cout << c->symbol_m; // whoops! will either seg fault or do wildly unpredictable things
To keep track of which member in the union is currently valid, you should use what's known as a tagged union or discriminated union approach:
struct Cell { enum TypeTag {type_int, type_double, type_symbol}; TypeTag tag_m; union { int int_m; double double_m; char* symbol_m; }; };
Now you can write your code so that you make sure that the tag_m always holds an up-to-date value indicating which of the union members is valid at the current time.
You must follow the design approach outlined in this document. Do not just implement the required functionality using a different design. Your proper software engineering skills are being graded.
Do not use virtual functions or templates in this assignment. This assignment is about static OO support in C++. (You'll get a chance to use dynamic OO polymorphism and templates in the following assignments...)
Do not edit the files Cell.hpp, Node.hpp, or linkedlist.hpp. The programming assignments are mini-exercises in how multiple programmers are supposed to interact and communicate in the real world; these files are owned and maintained by the other author(s).
You may need to add things to Cell.hpp, but do not delete anything from it. Replace the files Cell.cpp, Node.cpp and linkedlist.cpp with your own implementations. Depending on your approach, you may or may not also wish to add more files.
Depending on your approach, you may or may not need to change the Makefile. Whether you changed it or not, always make sure you include whatever Makefile is needed to build your program, when you submit the assignment. Otherwise, the graders cannot build your program.
Documentation is also a critically important part of your software engineering. Your use of doxygen comments, as in Lab 3, will be graded.
You must write the final version of the program on your own. Sophisticated plagiarism detection systems are in operation, and they are pretty good at catching copying! If you worked in study groups, you must also acknowledge your collaborators in the write-up for each problem, whether or not they are classmates. Other cases will be dealt with as plagiarism. Re-read the policy on the course home page, and note the University's tougher policy this year regarding cheating.
Your programming style (how clearly and how well you speak C++) is what will be graded. Correct functioning of your program is necessary but not sufficient!
Below is the grading sheet that will be used by the graders, so you can see what software engineering skills they're checking you for.
Your grade consists of two parts: (1) program correctness, worth 60%. and (2) style & design, worth 40%. Points are deducted for the error types as shown (but the minimum you can get for each part is 0%, so you cannot get negative point scores on either program correctness or style & design).
| Name: | |
| Email: | |
| Submission Time: | |
| Late Penalty: | |
| Total Pts: | / 100 Pts |
| PROGRAM CORRECTNESS (Maximum: 60 Pts; Minimum: 0 Pts) | ||
| Description | Pts | Notes |
| Base Pts. (+60 Pts) | ||
| Program fails to compile. (-60 Pts) | ||
| Cell class fails (link against reference solution and run tests) (-60 Pts) | ||
| does not pass simple test cases. (-15 Pts) | ||
| does not pass general test cases. (-15 Pts) | ||
| does not handle semantically invalid cases. (-15 Pts) | ||
| Program prints irrelevant information. (-10 Pts) | ||
Encapsulation (Min -40 Pts)
| ||
| Proper destruction (+10 Pts) | ||
| BONUS: Detailed error messages (+5 Pts) | ||
| STYLE & DESIGN (Maximum: 40 Pts; Minimum: -100 Pts) | ||
| Description | Pts | Notes |
| Base Pts. (+40 Pts) | ||
| No Doxygen output. (-10 Pts) | ||
| Inadequate function level documentation. (-10 Pts) | ||
| Inadequate algorithm level (i.e. within function) documentation. (-15 Pts) | ||
| Inadequate variable level documentation (i.e. meaning of the variable). (-10 Pts) | ||
| Poor readability of function and variable names. (-10 Pts) | ||
| Improper use of indentation and space. (-10 Pts) | ||
| Inconsistent naming of functions and variables. (-10 Pts) | ||
| Incorrect ‘const’ usage. (-10 Pts) | ||
| Improper private data encapsulation. (-10 Pts) | ||
1.5.8