Garlands

Garlands: An Overview

In the final part of this assignment, you will extend the idea of the listy strings from the previous section and create a garland, which is a sort of two-dimensional list for storing strings. Each node in this data structure will contain a single character, as well as two pointers: a next pointer and a down pointer. A single string will run across the top of the garland using the next pointers (very much like a listy string), and the down pointers of the nodes in that top layer can be used to reach characters in strings that dangle down from each of those nodes.

For example, the following garland contains eight strings: "dwindle" across the top, and dangling from those nodes are the strings "din", "wind", "idealism", "needle", "dream", "lyrical", and "echo".

→

Note that in a garland, the next field is only used across the top layer of nodes. For example, in the nodes representing "wind" in the garland above, only the 'w' node has a next pointer that actually leads to another node. The 'i', 'n', and 'd' nodes all must have their next pointers set to nullptr.

Note also that the layer of next pointers across the top of a garland (which connect the first character of each of the dangling strings in the garland) will always be terminated with nullptr, and the chain of down pointers used to connect the characters in a dangling string will also always be terminated with a nullptr.

The top-left node of any garland is designated as its head node and is our point of entry to that structure.

The `GarlandNode` Struct

We have created a GarlandNode struct that you will use for your garlands. It is defined in garlandnode.h and can be used in any code you write in garlands.cpp:

struct GarlandNode {
    char data;            /* Data stored in the node. */
    GarlandNode *next;    /* Pointer to next node (moving right) in the list. */
    GarlandNode *down;    /* Pointer to next node (moving down) in the list. */
}

You also have access to a variety of constructors you can use when creating a new GarlandNode (which you can read about in garlandnode.h), but the one we think is the easiest to use is the following:

// This version of the constructor initializes the data field to
// the specified value and the pointer field to nullptr.
//
// Example usage:  GarlandNode *node = new GarlandNode('q');

GarlandNode(char data) {
    this->data = data;
    this->next = nullptr;
    this->down = nullptr;
}

Required Garland Functions

Implement all of the following functions in garlands.cpp. For additional examples of how these functions will be called and their expected behaviors, see the test cases in garlands.cpp

GarlandNode *createGarland(Vector<string>& v)
- Description: This function takes a vector of strings and creates a garland from them. The first string in the vector, v[0], forms the top layer of the garland, with nodes linked via next pointers. For example, given the vector {"dwindle", "din", "wind", "idealism", "needle", "dream", "lyrical", "echo"}, "dwindle" will form the top layer of the garland. This function should then loop through the nodes in the top layer of the garland and dangle the next remaining string in v from the down pointer in each successive node in that layer. For example, in the vector given above, "din" would dangle down from the first node in "dwindle", "wind" would dangle from the second node in "dwindle", "idealism" would dangle down from the third node, and so on.
  
  Notice that after the first string in v, the first characters of all our remaining strings, when taken in order, must match the characters in v[0]. This is the case with the example vector above, where the first characters of v[1] through v[7] spell "dwindle". If this function receives a vector where that is not the case, you should return nullptr without allocating any nodes. Furthermore, after v[0], our vector must contain exactly one string for each character in v[0]. In the example above, v[0] is "dwindle", which has 7 characters, and there are exactly 7 strings following "dwindle" in the vector, so we're good to go. If this function receives a vector where that is not the case (i.e., where the number of remaining strings is either less than or greater than the number of characters in v[0]), the function should return nullptr without allocating any nodes. Similarly, if the function receives an empty vector, or if it receives a vector that contains an empty string ("") at any index, it should simply return nullptr.
  
  The example vector given above should create the garland depicted at the top of this page. For additional examples, see our provided tests in garlands.cpp.
- Character Considerations: This function should be case sensitive. So, if v[0] starts with the character 'A' and v[1] (which has to hang down from the 'A' node) starts with the character 'a', the function should simply return nullptr without allocating any nodes, because those characters are not equal to one another.
- Suggested Helper Functions: Adding the following helper functions might make this function feel more manageable:
  - (1) A function that checks whether the vector passed to createGarland() is going to result in a valid garland. (From a testing standpoint, having a carefully vetted version of this function is helpful to the point that we almost made this a requirement!) If the vector violates any of the conditions above and therefore won't lead to the creation of a garland, then there is no need to allocate any nodes and risk creating a memory leak – or to go through all the trouble of carefully deallocating those nodes – before returning nullptr. Remember that if you create a helper function like this, you should also add a few STUDENT_TEST test cases to garlands.cpp to verify that it's working as intended.
  - (2) A function whose sole responsibility is to create the top layer of nodes in the garland that are linked via next pointers.
  - (3) A function that takes a pointer to one of the nodes from the top layer of the garland, as well as a string that we want to dangle from that node's down pointer, and sets up the chain of down nodes accordingly.
  - (4) It might also be really helpful to write a printGarland() function that you can use to print any garlands you create and inspect whether they're being constructed correctly.
- Other Considerations: As you create your garland, be sure to avoid creating orphaned nodes that are detached from the list. All of our provided test cases that call this function also attempt to delete all the nodes in your resulting garland, either manually or by calling destroyGarland() (described below). GarlandNode allocations are being tracked, so our test infrastructure will flag test cases with memory leaks. Be sure to squash all memory leaks. Also, be sure not to modify the contents of the vector being passed to this function by reference.
string garlandGet(GarlandNode *head, int i)
- Description: Take the head of a garland and return the i^th string it contains, where i = 0 refers to the string across the top layer of the garland, and the strings hanging from down pointers are numbered from left to right starting at i = 1. So, for the garland at the top of this page, garlandGet(0) should return "dwindle", garlandGet(1) should return "din", garlandGet(2) should return "wind", and so on.
  
  If this function receives a nullptr, or if i is not a valid index for a string in the garland, simply return an empty string ("").
- Special Consideration: Be sure to avoid segmentation faults in the case where head is nullptr or where i is invalid/out-of-bounds. In those cases, simply return from this function straight away.
- Special Consideration: This function should not modify the garland it receives as an argument at all.
- Suggested Helper Functions: You might find this function significantly more manageable if you write some carefully selected helper functions. We have a few suggestions below. These aren't required, however, and they're also not the only way to approach this problem. In fact, many of the course staff who have implemented solutions to this assignment have actually taken different approaches here. If you have a different set of helper functions in mind, we encourage you to follow your own path and implement those instead!
  - (1) A function that returns a pointer to the k^th node in the top layer of the garland.
  - (2) A function that takes a pointer to one of the nodes from the top layer of the garland and returns the string that is dangling down from that node.
  - (3) A function that takes the head of a garland and returns the string that is running across its top layer of next pointers.
void destroyGarland(GarlandNode*& head)
- Description: Delete all the nodes in this garland, and set the pass-by-reference head parameter to nullptr. Be sure to avoid segmentation faults and other memory errors. Remember, once you delete a node, you should not try to access any of the fields inside that node.
- Special Considerations: Be sure to avoid segmentation faults in the case where head is nullptr. In that case, simply return from this function straight away. Be careful to avoid segmentation faults if any of the nodes in the top layer of the garland have their down pointers set to nullptr, as well.
- Memory Leaks: Once you have this function implemented correctly, you should start passing all the destroyGarland() test cases we have provided. If you have already completed createGarland(), implementing destroyGarland() correctly should cause our test infrastructure to stop flagging memory leaks for that function, as well. If SimpleTest is still flagging memory leaks in the provided test cases for either of these two functions, that means at least one of them has not been implemented correctly.
bool garlandsAreEqual(GarlandNode *head1, GarlandNode *head2)
- Description: This function takes pointers to the heads of two garlands (head1 and head2) and returns true if the two garlands have the same structure and contents. Note that the actual addresses of the nodes in these garlands do not have to be identical. If needed, refer to the provided tests in garlands.cpp for further clarification on the expected behavior of this function.
- Special Considerations: Do not modify the garlands passed to this function. Do not allocate or deallocate any nodes in this function. As always, be sure to avoid segmentation faults.

Testing

⚠️ Please be sure to read this section carefully. We don't want you to skip over it and miss our note about the importance of testing on this assignment.

As with the listy strings, we would like you to create additional tests for each of the functions in this part of the assignment. Unlike our listy string tests, our provided tests for these garland functions are fairly sparse. We look forward to seeing a collection of STUDENT_TESTs that showcase the way you think about poking and prodding at the capabilities of these functions. Keep in mind that having a robust set of test cases will help you uncover potential bugs before submitting your code, and the quality and breadth of your test cases will be an important component of the grading for this assignment.

Because our garland tests are so sparse, we expect that you will want to add more test cases than usual for each of the functions in this part of the assignment to get good testing coverage. We're hoping you are ready to show us how much you have learned from the different testing exercises and provided tests that you've seen on the earlier assignments!

Extension: Tapestry

For this assignment extension, we introduce a new definition: a tapestry is a garland where we have relaxed the restrictions on the next pointers of dangling nodes, and which must instead meet the following properties:

All nodes in the top layer of the garland are connected via next pointers as normal.
Every dangling node (a node that is not in the top layer) must meet one of the following conditions: either its next pointer is set to nullptr, or its next pointer is pointing to the node directly to its right in the garland.
- For example, in the following garland, the nodes spelling "fate" form the top layer, and all six other nodes in the garland are considered dangling nodes. Let's consider each of them in turn:

f	→	a	→	t	→	e	→

l				o		b

u						b

b

The 'l' node in "flub" can have its next pointer set to nullptr, or it can point to the 'o' node in "to" (because that's the node directly to its right in the garland). If its next pointer were pointing to any other node (including a different node containing the character 'o'), this would not be considered a tapestry.

The 'u' node in "flub" can have its next pointer set to nullptr, or it can point to the second 'b' node in "ebb" (because that's the node directly to its right in the garland). If its next pointer were pointing to any other node (including a different node containing the character 'b'), this would not be considered a tapestry.

The 'b' node in "flub" can only have its next pointer set to nullptr, since there is no node directly to its right in the garland. If its next pointer were set to anything other than nullptr, this would not be considered a tapestry.

The 'o' node in "to" can have its next pointer set to nullptr, or it can point to the first 'b' node in "ebb" (because that's the node directly to its right in the garland).

Both of the 'b' nodes in "ebb" can only have their next pointers set to nullptr, since there are no nodes directly to their right in the garland.

So, we can add any number of the red links in the diagram below (all, some, or none), and this structure would still be considered a tapestry. However, adding any other non-null next pointers would render this no longer a tapestry.

Note that a nullptr, which corresponds to an empty garland, is considered a tapestry.
Note that in a regular garland, all dangling nodes have their next pointers set to nullptr, and so every regular garland qualifies as a tapestry.

With this definition in mind, write the following function in garlands.cpp.