[an error occurred while processing this directive]

Stanford CS 106B: Tiles

Assignment by Marty Stepp and Victoria Kirst. Based on a nifty assignment idea from Mike Clancy of Berkeley.

This problem focuses on linked lists and pointers, along with classes and objects. This is an individual assignment. Write your own solution and do not work in a pair/group on this program.

Files and Links:

icon
Project Starter ZIP
(open Tiles.pro)
icon
Turn in:
icon
Demo JAR
icon
Homework Survey
icon
output logs:
none

Problem Description:

In this problem you will write the logic for a graphical program that allows the user to click on rectangular tiles. This program is a bit like the window manager of your operating system. When the program runs, several random rectangular "tiles" will appear in the window. Some tiles overlap and occupy the same (x, y) pixels. We think of the tiles as having a "z-ordering" where the tile created/added later is "on top" of prior tiles and is able to partially cover them on the screen.

Your job is to write a class TileList that implements the collection of tiles using a doubly-linked list. Your class maintains a pointer to the front of your linked list, which represents the "top" tile, and each tile afterward is below it in the z-ordering. Because this is a doubly-linked list, you also maintain a pointer to the back of your linked list, which represents the "bottom" tile, the last one in the z-ordering. Each individual node contains data about a tile as well as two pointers: a link to the next tile (the one below it in the z-ordering) and previous tile (the one above it in the z-ordering). This allows you to traverse your linked list in either direction, which will be useful for the various operations we want to implement. In general a doubly-linked list looks something like the following diagram: 

          prev     next    prev     next           prev     next     prev     next
          +---+---+---+--> +---+---+---+-->        +---+---+---+-->  +---+---+---+
front --> | / | ? |   |    |   | ? |   |    ...    |   | ? |   |     |   | ? | / | <-- back
          +---+---+---+ <--+---+---+---+        <--+---+---+---+ <-- +---+---+---+

This program is graphical, but you do not directly draw any graphics yourself; all of the graphical interface code has already been written for you, and your code just has to manage the tiles and keep them in the proper order. The main client program and graphical user interface are provided for you as tilegui.cpp/h. When the program runs, it will create a graphical window that allows you to add tiles to your tile list at the front (top) or back (bottom). Each tile's position, size, and color are randomly generated by the main program. You must write the code to place the tiles into a linked list as they are pushed, to draw the tiles on the screen, and to perform operations on tiles when the user clicks on them.

screenshot

Depending on the user's action, one of several different actions occurs:

If the user clicks a pixel that is occupied by more than one tile, the top-most of these tiles is used. If the user clicks the window at a pixel not occupied by any tiles, nothing should happen.

Your code does not need to directly detect mouse clicks. Our provided code detects the clicks and responds by calling various member functions on your TileList object, as described below.

Implementation Details:

Provided TileNode Structure:

Your TileList class stores its list of tiles as a linked list of TileNode structures. A TileNode stores data about a single rectangular tile, along with links to a previous and next node to facilitate building a doubly-linked list. The node structure is provided to you in the files TileNode.h/cpp; do not modify those files. Each node has the following public members. Each member is assumed to have a Big-Oh of O(1).

Member Name Description
x, y, width, height The top/left (x, y) coordinate of the tile and its width and height in pixels.
color The color of the tile, specified as an RGB string such as "#ff00ff" or a color name such as "red".
prev, next Pointers to neighboring nodes; set to nullptr if there is no next structure.
contains(x, y) Returns true if this tile touches the given (x, y) pixel position.
draw(window) Draws the tile onto the given GWindow.
toString() Returns a text representation of the tile, which can be useful for debugging.
operator << Allows you to print a node to the console for debugging. (Remember to print the node itself and not a pointer to a node.)
members of provided TileNode structure

Here is a brief example of declaring and using a single tile node structure: 

// example of declaring and using a tile node
TileNode* node = new TileNode(x, y, w, h);
node->prev = nullptr;
node->next = nullptr;
if (node->contains(x, y)) {
    node->draw(window);
}
cout << *node << endl;   // print the node for debugging

You are required to have exactly two private member variables in your class: (1) a pointer to the front node in the list (the top of the z-ordering), and (2) a pointer to the back node in the list (the bottom of the z-ordering). When a new TileList is created, initially the tile list is empty, meaning that the front and back pointers are null. You are not allowed to have any other member variables in your class. For example, you are not allowed to keep a member variable pointing to any other nodes in the linked list, nor are you allowed to keep an int for the list's size/length.

TileList Members:

You must write the following public members in your TileList class. Each member must run within the Big-Oh runtime noted; the N in this context means the length of the linked list. You may assume that every parameter passed is valid unless otherwise specified. See the next page for some general restrictions about proper linked list usage and style.

We provide you a partially complete version of your header file TileList.h that declares the following members. You can add other member functions (such as helper functions) as long as they are private.

Member Name Description Big-Oh
TileList() In this constructor you initialize a new empty list of tiles. O(1)
~TileList() In this destructor you must free all dynamically allocated memory used by your nodes. O(N)
list.debug(); This member function is optional. It is called when the user clicks the Debug button in the GUI. You can put anything you want in this function, such as a loop to print your list or any other information to the console. Or you can leave it completely blank; it is up to you. O(?)
list.addFront(x, y, w, h, color); In this member function you should add a new tile with the given position, size, and color to the front of your linked list (the top of the z-ordering). O(1)
list.addBack(x, y, w, h, color); In this member function you should add a new tile with the given position, size, and color to the back of your linked list (the bottom of the z-ordering). O(1)
list.drawAll(window); In this member function you are passed a reference to a GWindow object, and you should draw all tiles in your list on that window in bottom-to-top (back-to-front) order using each tile node's draw function. O(N)
list.highlight(x, y); Called by the provided GUI when the user clicks the given x/y coordinates when the Highlight button is selected. In this member function, if these coordinates touch any tiles, you should set the topmost (closest to the front) of these tiles to have a color member value of "yellow". The tile should not move at all in the z-ordering, and no other tiles should change color. If no tile touches these x/y coordinates or they are out of bounds, nothing should happen. O(N)
list.raise(x, y); Called by the provided GUI when the user clicks the given x/y coordinates when the Raise button is selected. In this member function, if these coordinates touch any tiles, you should move the topmost (closest to the front) of these tiles to the front of the list (top of the z-ordering). All other tiles should remain at their original relative z-ordering. If no tile touches these x/y coordinates or they are out of bounds, nothing should happen. O(N)
list.lower(x, y); Called by the provided GUI when the user clicks the given x/y coordinates when the Lower button is selected. In this member function, if these coordinates touch any tiles, you should move the topmost (closest to the front) of these tiles to the back of the list (bottom of the z-ordering). No other tiles should be modified; all other tiles should remain at their original relative z-ordering. If no tile touches these x/y coordinates or they are out of bounds, nothing should happen. O(N)
list.remove(x, y); Called by the provided GUI when the user clicks the given x/y coordinates and the Remove button is selected. In this member function, if these coordinates touch any tiles, you should delete the topmost (closest to the front) of them from the list. No other tiles should be modified; all other tiles should remain present in the list and at their original relative z-ordering. If no tile touches these x/y coordinates or they are out of bounds, nothing should happen. O(N)
list.removeAll(x, y); Called by the provided GUI when the user clicks the given x/y coordinates and the Remove All button is selected. In this member function you should delete all tiles that touch or contain this x/y point from the list. (See screenshots earlier in this document.) No other tiles should be modified; all other tiles should remain present in the list and at their original relative z-ordering. If no tile touches these x/y coordinates or they are out of bounds, nothing should happen. O(N)
list.clear(); In this member function you should remove all tiles from the list and free their associated memory. O(N)
members you must write in TileList class

You will need to modify the provided TileList.h/cpp files to complete them. In particular, you will need to do the following:

Add descriptive comments to TileList.h/cpp. Both files should have top-of-file headers; one file should have header comments atop each member function, either the .h or .cpp; and the .cpp should have internal comments describing the details of each member function's implementation.

Declare your necessary two private member variables in TileList.h, along with any private member functions you want to help you implement the required public behavior. Your inner data storage must be a linked list of tiles; do not use any other collections or data structures in any part of your code.

Implement the bodies of all member functions and constructors in TileList.cpp. Notice that several operations are similar or have common aspects. As appropriate, avoid redundancy in your code by creating additional "helper" functions in your TileList to help reduce redundancy. (Declare them private, so outside code cannot call them.)

Make member functions const as appropriate. Some of the functions you will write do not modify the state of the linked list. For all such functions, mark them as const at the end of their headers in the .h and .cpp files in your code. For example, if a member named foo doesn't modify the list, you should change its header to: 

class TileList {
    ...
    void foo() const;
};

Other than adding const to some headers, you should not modify the provided public member headers in any way.

Development Strategy and Hints:

We suggest coding basic operations first, such as addFront and drawAll only. Then write highlight, because it has some similar elements to other member functions like raise and remove but without needing to modify the pointers in the linked list. Then write the rest of the list-modifying functions. To figure out if a tile touches a given x/y pixel, call the TileNode's contains member function. Do not use GRect or GRectangle on this program, nor the LinkedList library class.

Draw pictures: When manipulating linked lists, it is often helpful to draw pictures of the linked list before, during, and after each of the operations you perform on it. Manipulating linked lists can be tricky, but if you have a picture in front of you as you're coding it can make your job substantially easier.

Strongly recommended helpers: While you should decide for yourself how best to decompose the problem, we strongly recommend you write helper functions for common code between operations. One common operation is the task of figuring out which tile was clicked on at a given x/y position. Another common operation is to extract/remove a node from its place in the doubly-linked list so that it can be moved elsewhere (to the front/back) or removed entirely. Helper functions like these can greatly simplify your code and help you avoid redundancy and bugs.

List states: When processing a doubly-linked list, you should consider the following states and transitions between them in your code as you add and remove elements: You should also, for each state below, think about the effect of adding a node in the front, middle, and back of the list.

zero nodes 
front /    back /
one node 
          prev     next
          +---+---+---+
front --> | / | ? | / | <-- back
          +---+---+---+
two nodes 
          prev     next    prev     next
          +---+---+---+--> +---+---+---+
front --> | / | ? |   |    |   | ? | / | <-- back
          +---+---+---+ <--+---+---+---+
N nodes 
          prev     next    prev     next           prev     next     prev     next
          +---+---+---+--> +---+---+---+-->        +---+---+---+-->  +---+---+---+
front --> | / | ? |   |    |   | ? |   |    ...    |   | ? |   |     |   | ? | / | <-- back
          +---+---+---+ <--+---+---+---+        <--+---+---+---+ <-- +---+---+---+

Don't forget that you can put some code in your debug member function to print information about the current state of your list.

Style Details:

As in other assignments, you should follow our Style Guide for information about expected coding style. You are also expected to follow all of the general style constraints emphasized in the Homework 1-4 specs, such as the ones about good problem decomposition, parameters, redundancy, using proper C++ idioms, and commenting. The following are additional points of emphasis and style contraints specific to this problem. (Some of these may seem overly strict or arbitrary, but we need to constrain the assignment to force you to properly practice pointers and linked lists as intended.)

Redundancy and helpers: If your implementation has a common operation, make a private helper function and call it multiple times in that file.

Commenting: Add descriptive comments to your .h and .cpp files. Both files should have top-of-file headers. One file should have header comments atop each member function (either the .h or .cpp; your choice). The .cpp file should have internal comments describing the details of each function's implementation. Also put a comment atop every member function that states its Big-Oh. For example, the addFront operation runs in constant time, so you should put a comment on that function that says "O(1)."

Restrictions on pointers: The whole point of this assignment is to practice pointers and linked lists. Therefore, do not declare or use any other collections in any part of your code; all data should be stored in your linked list of nodes. There are some C++ "smart pointer" libraries that manage pointers and memory automatically, allocating and freeing memory as needed; you should not use any such libraries on this assignment.

Restrictions on private member variables: As stated previously, the only member variables (a.k.a. instance variables; private variables; fields) you are allowed to have are a TileNode* pointer to the front and back of your list. You may not have any other member variables. Do not declare an int for the list size. Do not declare members that are pointers to any other nodes in the list. Do not declare any collections or data structures as members.

Restrictions on modifying function headers: Please do not make modify the TileList class's public constructor or public member functions' names, parameter types, or return types. Our client code should be able to call public member functions on your list successfully without any modification.

Restrictions on creation and usage of nodes: The only place in your code where you should be using the new keyword is in the addFront and addBack functions. No other members should use new or create new nodes under any circumstances. You also should not be modifying or swapping nodes' data values, such as their x, y, width, and height. In other words, you should implement all of the linked list operations like raise and remove by manipulating node pointers, not by creating entirely new nodes and not by modifying "data" of existing nodes.

You also should not create any more TileNode structures than necessary. For example, if the client has called addFront 6 times, your code should have created exactly 6 total TileNode objects; no more, no less. You shouldn't, say, have a seventh empty "dummy" node at the front or back of the list that serves only as a marker, and you shouldn't accidentally create a temporary node object that is lost or thrown away. You can declare as many local variable pointers to nodes as you like.

Restrictions on traversal of the list: Any member function that modifies your tile list should do so by traversing across your linked list a single time, not multiple times. For example, in functions like drawAll, highlight, raise, lower, remove, and removeAll, do not make one traversal to find a node of interest and then a second traversal to manipulate/modify that node. Do the entire job in a single pass.

Since your program uses a doubly-linked list, you can traverse it in a forward or backward direction as desired. Your code should always choose an appropriate direction in which to traverse the list. For example, if you are looking for something near the back of the list, or if you need to visit nodes in back-to-front order, start from the back and loop backward. Otherwise, start at the front and loop forward.

Regardless of direction, do not traverse the list farther than you need to. That is to say, once you have found the node of interest, do not unnecessarily process the rest of the list; break/return out of code as needed once the work is done.

Avoiding memory leaks: This item is listed under Style even though it is technically a functional requirement, because memory leakage is not usually visible while a program is running. To ensure that your class does not leak memory, you must delete all of the node objects in your tile list whenever data is removed or cleared from the list. You must also properly implement a destructor that deletes the memory used by all of the linked list nodes inside your TileList object.

Frequently Asked Questions (FAQ):

For each assignment problem, we receive various frequent student questions. The answers to some of those questions can be found by clicking the link below.

Q: How do I detect a mouse click? I don't think we learned about the mouse or graphics in class.
A: You don't have to handle mouse clicks directly. The provided GUI code does that. It waits for a mouse click, and when one occurs, it calls the appropriate member function on your code, such as raise or lower or remove.
Q: How do I declare a TileNode?
A: Since the tile stack needs to keep its memory around dynamically, you must use the new keyword like this: 
TileNode* node = new TileNode(x, y, w, h);
node->color = ...;
node->prev = ...;
node->next = ...;
...

You *must* declare all your nodes as pointers; do not declare them as regular objects like the following code, because it will break when the list node goes out of scope: 

// do not do this!
TileNode node;         // bad bad bad
node.x = 42;           // bad bad bad no
node.y = 17;           // bad bad bad no stop
node.next = nullptr;   // bad bad bad no stop don't
...
Q: My program crashes and the console says "The program has unexpectedly finished" in red text. Why is this? How do I find and fix it?
A: That error means that you have accessed illegal memory, such as a null pointer or garbage pointer. Try running your program in Qt Creator's Debug mode (the "Play" button with a bug on it, below the normal Play button) and then when there is a crash, you can view the call stack of which functions were running. Find the line number where your program crashed and look at that line to find your bug.
Q: When I click on a rectangle, the window briefly "flickers" before it updates. Is this my fault? Is my code too slow?
A: This is just a side effect of how the Stanford graphical libraries are implemented. It isn't your fault, and you don't need to worry about it.
Q: Can I declare a Vector as a private field inside my TileList?
A: No. The point of this homework is to practice implementing data structures from scratch, not to use an existing class or library.
Q: Should my class store a pointer to a TileNode? A pointer to a pointer? A reference to a pointer? How do I declare it? ...
A: Store a TileNode* , that is, a pointer to a TileNode.
Q: Are these the correct private member variables for my class? ______ Do I have too many/few?
A: Member variables represent the state of the object and should exist as is necessary to store that state. Temporary variables, elements of data that do not need to be remembered between member function calls or uses of the object, should not be fields.
Q: Do I need to write a destructor? If so, what should it do? When am I supposed to call the destructor?
A: Yes, you need to write a destructor. It should free any dynamically allocated memory used by your list (any memory that was initialized with the new keyword). You don't explicitly call the destructor; the client program automatically calls it when the TileList variable it creates falls out of scope.
Q: Exactly what memory do I need to free (delete)? Do I need to free every int and pointer I declare? Do I need to free the TileList object itself? ...
A: You only need to free the object(s) that your code creates using new. You don't need to free an int; its memory is reclaimed automatically. Any memory that was not allocated using new is already handled by the program without any code from you. Just free your nodes by calling delete on each pointer to a node that is removed from the list.
Q: What is const? When do I need to make something const?
A: Make a member function const when it does not modify the state of the object it is called on. Examples of such methods are accessors / "getters" like getX or isEmpty, as well as methods that just display information like toString, print, draw, etc. But a member function that modifies the object, like nextDay, setY, or clear would not be const. Also use const in front of a parameter to a function, if that parameter is a reference to an object and your member function does not make any modifications to that parameter's state. Like if the client passes you a reference to a string or Map and you examine but don't modify it, make the parameter const.
Q: Why do my while loops always crash? I explicitly check for null and tell my loop to stop when nullptr is reached. Shouldn't the loop stop successfully?
A: Testing for nullptr is good, but it only works if you actually set the appropriate node pointer to nullptr. Are you sure that you did that? (Such as in your constructor) Remember that if you don't explicitly set an empty pointer to nullptr, it will point to garbage, and the program will likely crash if you try to follow the pointer.
Q: What is the difference between a destructor and the clear method? Don't they do the same thing, deleting all elements from the tile stack?
A: A clear method is called explicitly when a client wants to wipe the elements and then start over and use the same stack to store something else. A destructor is called implicitly by C++ when an object is being thrown away forever; it won't ever be used to store anything else after that. The implementations might be similar, but their external purpose is different.
Q: Can/should I use a circular list instead of a nullptr-terminated list?
A: No, you shouldn't do this.
Q: I'm trying to debug by printing my nodes. But every time I try to print a node, it just prints a memory address in hex format. Why?
A: Maybe you're actually printing a TileNode*, that is, a pointer to a node. Print the node itself (*p rather than p); just be careful that the pointer is not null or garbage before following it.
Q: I've heard of something called a "smart pointer" that frees itself and doesn't require memory management and new/delete. Can I use that on this assignment?
A: Sorry, no. We want you to practice manually allocating and freeing memory on this assignment. Those kinds of libraries are useful, but we want you to build certain skills before becoming dependent on any particular library to help you.

Possible Extra Features:

Here are some ideas for extra features that you could add to your program:

Indicating that you have done extra features: If you complete any extra features, then in the comment heading on the top of your program, please list all extra features that you worked on and where in the code they can be found (what functions, lines, etc. so that the grader can look at their code easily).

Submitting a program with extra features: Since we use automated testing for part of our grading process, it is important that you submit a program that conforms to the preceding spec, even if you want to do extra features. If your feature(s) cause your program to change the output that it produces in such a way that it no longer matches the expected sample output test cases provided, you should submit two versions of your program file: a first one with the standard file name without any extra features added (or with all necessary features disabled or commented out), and a second one whose file name has the suffix -extra.cpp with the extra features enabled. Please distinguish them in by explaining which is which in the comment header. Our turnin system saves every submission you make, so if you make multiple submissions we will be able to view all of them; your previously submitted files will not be lost or overwritten.

[an error occurred while processing this directive]