In this quest you will implement a class called Playlist as a singly linked list of nodes with Song_Entry objects as their payloads. Your code should be organized into a header file (Playlist.h) and a separate implementation file (Playlist.cpp). Your Playlist class will encapsulate things the client (the user of the class) doesn't have to know about. Make them inner classes. An inner class is simply a class that is defined inside another class - duh! If an inner class is private, then only the containing class can create or manipulate objects of that class. If it is public then anyone can instantiate the inner class and invoke its public methods. But they'd have to access the class name with the outer-class qualifier. For example, if song_Entry is a public inner class of Playlist, a user, in their main() method, can refer to it as Playlist::Song_Entry. This kind of structuring also gives a nice namespace-like separation of the type from other classes elsewhere that may have the same name. You will have two inner classes in your Playlist class: Playlist::Song_Entry, which is public Playlist:: Node, which is private You don't have to modify anything in the structure (declaration of the above inner classes. But you will have to flesh out some of the method implementations in them. Keep the payload class, Playlist::Song_Entry, simple because that's not the focus of this quest. Define it as follows: // this class das should be placed in the publie section of Playlist pevate: int public: Song Inteyint id-0. int get 3) coat return boel et sans Deal operate(const Song Entrys that) bool operatoremnat Song Estays that friend atdzes apertornext or_head itself. To avoid this confusion. I've decided to use the word equals. In this document when I say the_prev to_current equals something. I mean that the contents of the pointer prev_to_current.equals it. You can think of it as overlooding our current understanding of the word equals with an added meaning C++ lets us do cool things like this in programming too! A few special things about Node Node::get_song() returns a reference to its Song_Entry object - not a copy. Why? Because that's the only way you can easily modify the contents of an existing node in this implementation. Extra credit rewards await meaningful discussion of this point, as well as thoughts on other ways in which you might change, say, the 5th song in a list from Ato B. Node::get_next() simply returns the node's _next pointer. Besides a Node's getters and setters, note the two special methods: insert_next() and remove_next(). You will invoke these from your Playlist instance methods. Since the idea of a Node needs to be abstracted away from your end-user (the programmer who uses your Playlist class). none of the Playlist's public methods will ever communicate in terms of Nodes with the outside world. Instead they will interface using Song_Entry objects - inserting songs, removing songs, and so on. However, these methods that insert and remove songs will, opaquely to the user. themselves use their private Node insertion and removal methods. Node::insert_next (Playlist:: Node *p) should insert the given node. p. directly in front of itself. That is, after the operation, its own _next member should be pointing at p. It should returnp, the pointer to the node that just got inserted. Playlist::Node *remove_next() should unlink and remove the node pointed to by next. Refer to a diagram later in this document to see what needs to get done. But here is an important question before you start cutting its code. What is the node that remove_next() returns? Is it the node that just got unlinked so the caller can extract and use the value that it pulled out of the list? No. It returns a pointer to itself (the this value). What is a good reason for doing so? Remember that the remove operation also deletes the node it unlinks (frees its memory). So you cannot return a node which doesn't belong to you any more. But one may object, saying that it makes sense to return the unlinked node to the caller and also shift the responsibility of deleting the node to the caller. Does this alternative approach make sense? Discuss the pros and cons (including esthetic reasons) for doing it one way versus the other (extra rewards may await insightful discussions). After you delete a successor node for a given node, make sure to set its value to NULL for easy debugging. This way you're sure to know which nodes are pointing to allocated memory. (There's one more important thing to keep in mind here. Look for my picture elsewhere in this document to know what that is.) Finally, here is the Playlist class. Heed the header comment // Important implementation note: with the exception of to_string() and tand... // all Playlist methods below should operate in a constant amount of time // regardless of the size of the Playlist instance. 17 // The semantics of prev_to_current is such that it always points to the // node *BEFORE the curso (current). This makes the manipulations easy because // we can only look forward and not back) in singly linked lists. class Playlist public: // Taner public class // The client can refer to it by using the qualitied same playlist: : Song Entry class Song Entry // TODO - your code here private // This is going to be our inner private class. The client doesn't need to 11 KOW class Mode // TODO - your code here private: Bode *_head, tail, prev_to_current: size_t size: public: Playlist: -Playlist: size_t get_size() const { return size: Song_Entrys get_current_song) const: // The following return this on success, null on failure. See the spec // for why Playlist "clear(); Playlist rewind Playlist push_back (const Song Entry s) Playlist "push_front (const Song Entry a): Playlist "insert_at_cursor(const Song Entryss): Playlist remove_at_cursor() Playlist advance_CUESOE() Playlist circular_advance_cursor(); // the following return the target payload (oz sentinel) reference on success Song Entrys find by_idfint id) const: Song_Entry find by_name (string songame) const: string to_string() const friend class Tests: // Don't remove this line On returning a pointer to the list Note that some of the public list manipulation methods return a pointer to the current list object. Why do we do that? We do it because it allows us to program using a very nice pattern my_list -push_back (song_1) ->push_back (song_2) ->push_back song_3) In fact, it would be better if you returned a reference to the current object rather than a pointer. Then you can write the even nicer pattern: my_list -push_back (song_1) -push_back song_2 -push_back song_3) I'll leave you to experiment with the esthetics and find out more. But in this quest, you're gonna have to return a pointer to the current object (essentially this) On being clear where your head is Note that you are guaranteed to find a head node in any valid list with this approach. The head node is always equal to the very first actual node of the list. It is not a data node, and we will use it to double as a sentinel (see next section). _prev_to_current is always equal to the node immediately before what we call the current node (by design. You can think of it as the cursor in this linked list. It always points to (or has a next element that is equal to the node that we define as current. All list operations are done at the location of this cursor. I think one of the best ways you'll get to appreciate the utility of this member is to try and program this quest without using it. This member saves you from having to scan the list from the beginning just to find where "here" is. If you use this member, then "here" (the current location) is always directly in front of your_prev_to_current node. This will make a whole lot more sense once you've programmed this functionality both ways. I highly recommend you do so (for your own edification). On sentinels Some of the Playlist methods return a Song_Entry object. What would you do if the requested operation failed and you don't have a Song_Entry object to return? For example, what would you return if I invoked your find_by_id () and passed it an non-existent song ID? The most common way to handle such a situation is using what are called exceptions. However, we don't cover exceptions until a week or so from now. So until then, we'll use a stopgap measure and make the method return a sentinel. A sentinel is a known invalid object. In this case, conveniently use the header node in a linked list as a sentinel. When you create a header node, make sure the object in it has an id of -1. This is the sentinel and will never change. The user only gets to see what_head->next points to and downstream from there. On to the miniquests... Your first miniquest - Know your songs, nodes and lists Implement the following public methods: Song_Entry::set_id() Song_Entry::set_name() Node constructor Playlist constructor Make sure you read about the special things to do with Nodes (earlier in this document) before you start implementing The Playlist constructor should create an empty Playlist that matches Figure 1. So it's easy rewards. Go for it. new Playlist _head Song_Entry _id: -1; name: "HEAD" tail NULL prev_to_current next Figure 1 The head node should be a Song_Entry object with an id of -1. Remember that you cannot set negative ids in a Song_Entry object using a setter on it. The only way to do it would be at construction time (that is, when you create the head node). Your second miniquest-Destructors Since your Playlist constructor is going to allocate memory on the heap, you must have a destructor or you will suffer memory leaks. Implement Playlist::-Playlist(); Make sure your destructor clears out the linked list by freeing all downstream nodes first and then deleting_head (which got allocated in the constructor). To accomplish this you would delete_head, which should trigger Playlist::-Node, the Node destructor. However, once invoked, the Node destructor will be called, and it should iteratively peel off one node at a time (adjacent to _head) and delete (free) it When all downstream nodes have been released thus, the Node destructor should delete_head and return. Note that there is no guarantee a memory location won't be overwritten the moment you delete the object to which it belongs. Thus, before you delete a node's descendants (starting at its _next member), make sure that you have taken a copy of that member into your local variable. Don't try to access it AFTER the node has been deleted. Then you will likely encounter unpredictable errors that cause your code to work sometimes and not other times. Carelessness here has resulted in forum posts that went "I'm sure I had it working, but something must have changed on the testing site because it's not working any more." Esthetics A good rule of thumbluse when I have questions about where to deallocate memory is this: If the memory was allocated in the constructor, then it should only be deallocated in the destructor. In general, I try and match up my allocations and deallocations into symmetric locations in the causal chain leading up to some action and back Also, keep in mind that you should not delete the "this" object. It is the deletion of the current object that triggers its destructor to be called. In here, you should only delete downstream nodes. This paragraph will likely save you several hours of debugging frustration: When you destroy a node, you will have to delete its _next member. This means that a node's deletion will auto invoke the delete on its_next pointer and so on. You want to make sure you delete no more than you should. Therefore make sure to (1) set every pointer you delete to nullptr so you can check before you attempt to double-delete something and (2) clear out a Node's _next pointer (set it to null) before you delete the node. This will prevent the delete from cascading to affect all downstream nodes. Your third miniquest - Insert song at current location Implement: Playlist Playlist::insert_at_cursor (const Song_Entry s); When I invoke it, I will pass it a Song_Entry object as its argument. It should insert a copy of that object at the current location of the Playlist object. It should leave the current location unchanged. This means that your _prev_to_current member will now end up pointing to this newly inserted Node. This is a tricky method and is worth getting correct before you move on. Refer to the picture in Figure 2 to see what needs to happen: Playlist PlaylistNodes head tant next Pre to current insert_at_cursor(my_song) Playlist Playlist: Nodes cant powstant NULL next Figure 2-insert at cursor Your fourth miniquest - Push back Implement: Playlist *push_back (const Song_Entrys s); This method must insert (a copy of the song s as a brand new node at the end of the list. That is, this newly allocated Node will become the new_tail. Since you have already implemented insert_at_cursor (). simply use it to complete this mini quest. 1. Save the current value of_prev_to_current, then set it to your_tail 2. Then insert the given string at the current position (which will now be the tail). 3. Finally restore the value of_prev_to_current to your saved value. Important! Remember that_prev_to_current can never benul because it's at least pointing to the list header. The current element visible to the user is always the element AFTER prev_to_current. So, when you're trying to advance the cursor and it's pointing to the element before_tail you return null (Why?? Your seventh miniquest - Circular Advance Implement: Playlist Playlist:: circular_advance_cursor(); This is essentially the same as advance_cursor() EXCEPT for the fact that if the cursor is pointing to the very last data node, the advance will silently reset to point to the first node. Refer to the picture below to see what needs to happen: Playlist Playlistdiode head talt , HULL Cerculer_advance_cutOS Playlist Playlist PlaylistNode head DOXE NULL pretources Figure 4-circular advance Your eighth miniquest - Get current song Implement: SongEntry Playlist::get_current_song(); If a_next element exists, then simply return its_song member. If no next element exists (this could happen if _prev_to_current is the same as your tail node), then you must return the sentinel (this->_head-> song) This method is only a few mins but malesure you understand itfully, Ask in the forums any of its under The current item is the song member of whichevernode is exulto preto current->_ext preto current->next = nullot which should not hoe we would really throw an exception. But since we havent covered aceptions yet we will return the sentinel Your ninth miniquest - Remove song at cursor Implement: Playlist Playlist:: remove_at_cursor(); NULE next next next next Ft remove at CUTE() bead prev_count NULL next next Figure 5 -remove at current position Again, this is a tricky method and important to get right. Refer to the picture in Figure 3 to decide exactly what needs to happen in your code Your tenth miniquest - Get size Implement: size_t Playlist::get_size() const; I can't believe you're gonna get a reward for just reporting the value of size! Still, I guess this is your first quest this quarter and you gotta have some freebies... Your eleventh miniquest - Rewind (but not relax just yet) Implement: Playlist Playlist::rewind(); This should reset_prev_to_current back to the_head node. Your twelfth miniquest - Clear Implement: void Playlist::clear(); Yet another tricky method to get right. When invoked, it must 1. Iteratively (not recursively) delete all the non-null nodes in the chain starting at _head->_next (Talking points: What might the problem be with a recursive delete instead?) Consider using the Node destructor you wrote. 2. Reset_prev_to_current and_tail back to _head 3. Set the value of_head->next to nullptr Note that you are not deleting the memory associated with the_head node itself. That is the job of the destructor. What the constructor created, only the destructor should undo Your thirteenth miniquest-Find an item Implement the following linear-search methods: Song_Entry& Playlist::find_by_id(int id) const; Song_Entry& Playlist::find_by_name (string id) const; Note an important aspect of the signature. They return references to Song Entry objects. Not copies. If the requested song exists in the list, then what gets returned is a reference to the actual data element. That means that if I assign something to this reference, it will change the contents of the list node that contains that song. It's important to understand exactly what that means. Please do discuss it in the forums and help each other out whenever possible. Ask me if you're stuck. What will this method return if the requested song is not found in the list? In that case, returna Sentinel in the same way you did for get_current_song(). Your fourteenth miniquest - Stringify Implement: string Playlist::to_string() const; This method must return a string representation of the list of strings in the following exact format. I've colored in the spaces. Each colored rectangle stands for exactly one space. Playlist: [N] lentries. Yid: [id], name: [Name of Ist song) lid: [id], name: [Name of and song) [ id: [idk], name: [Name of kth songi [B] lid: [ian], name: [Name of last song] ITI The parts in red above (also in square brackets) must be replaced by you with the appropriate values. The_prev_to_current element, if visible, should be marked with a [F] tag (see above). Similarly The very last element (the tail), if visible, should be marked with a [T] tag You would print a maximum of 25 elements this way. If the list has more than 25 strings, you must print first 25 and then print a single line of ellipses (...) in place of the remaining elements. There is one newline after the last line (which may be ellipses). Here's a point to ponder and discuss. Why do we need to say "if visible" when talking about the cursor above? Review Now I recommend that you rewind and review the specs one more time making notes along the way. It will help you when you start cutting code. In this quest you will implement a class called Playlist as a singly linked list of nodes with Song_Entry objects as their payloads. Your code should be organized into a header file (Playlist.h) and a separate implementation file (Playlist.cpp). Your Playlist class will encapsulate things the client (the user of the class) doesn't have to know about. Make them inner classes. An inner class is simply a class that is defined inside another class - duh! If an inner class is private, then only the containing class can create or manipulate objects of that class. If it is public then anyone can instantiate the inner class and invoke its public methods. But they'd have to access the class name with the outer-class qualifier. For example, if song_Entry is a public inner class of Playlist, a user, in their main() method, can refer to it as Playlist::Song_Entry. This kind of structuring also gives a nice namespace-like separation of the type from other classes elsewhere that may have the same name. You will have two inner classes in your Playlist class: Playlist::Song_Entry, which is public Playlist:: Node, which is private You don't have to modify anything in the structure (declaration of the above inner classes. But you will have to flesh out some of the method implementations in them. Keep the payload class, Playlist::Song_Entry, simple because that's not the focus of this quest. Define it as follows: // this class das should be placed in the publie section of Playlist pevate: int public: Song Inteyint id-0. int get 3) coat return boel et sans Deal operate(const Song Entrys that) bool operatoremnat Song Estays that friend atdzes apertornext or_head itself. To avoid this confusion. I've decided to use the word equals. In this document when I say the_prev to_current equals something. I mean that the contents of the pointer prev_to_current.equals it. You can think of it as overlooding our current understanding of the word equals with an added meaning C++ lets us do cool things like this in programming too! A few special things about Node Node::get_song() returns a reference to its Song_Entry object - not a copy. Why? Because that's the only way you can easily modify the contents of an existing node in this implementation. Extra credit rewards await meaningful discussion of this point, as well as thoughts on other ways in which you might change, say, the 5th song in a list from Ato B. Node::get_next() simply returns the node's _next pointer. Besides a Node's getters and setters, note the two special methods: insert_next() and remove_next(). You will invoke these from your Playlist instance methods. Since the idea of a Node needs to be abstracted away from your end-user (the programmer who uses your Playlist class). none of the Playlist's public methods will ever communicate in terms of Nodes with the outside world. Instead they will interface using Song_Entry objects - inserting songs, removing songs, and so on. However, these methods that insert and remove songs will, opaquely to the user. themselves use their private Node insertion and removal methods. Node::insert_next (Playlist:: Node *p) should insert the given node. p. directly in front of itself. That is, after the operation, its own _next member should be pointing at p. It should returnp, the pointer to the node that just got inserted. Playlist::Node *remove_next() should unlink and remove the node pointed to by next. Refer to a diagram later in this document to see what needs to get done. But here is an important question before you start cutting its code. What is the node that remove_next() returns? Is it the node that just got unlinked so the caller can extract and use the value that it pulled out of the list? No. It returns a pointer to itself (the this value). What is a good reason for doing so? Remember that the remove operation also deletes the node it unlinks (frees its memory). So you cannot return a node which doesn't belong to you any more. But one may object, saying that it makes sense to return the unlinked node to the caller and also shift the responsibility of deleting the node to the caller. Does this alternative approach make sense? Discuss the pros and cons (including esthetic reasons) for doing it one way versus the other (extra rewards may await insightful discussions). After you delete a successor node for a given node, make sure to set its value to NULL for easy debugging. This way you're sure to know which nodes are pointing to allocated memory. (There's one more important thing to keep in mind here. Look for my picture elsewhere in this document to know what that is.) Finally, here is the Playlist class. Heed the header comment // Important implementation note: with the exception of to_string() and tand... // all Playlist methods below should operate in a constant amount of time // regardless of the size of the Playlist instance. 17 // The semantics of prev_to_current is such that it always points to the // node *BEFORE the curso (current). This makes the manipulations easy because // we can only look forward and not back) in singly linked lists. class Playlist public: // Taner public class // The client can refer to it by using the qualitied same playlist: : Song Entry class Song Entry // TODO - your code here private // This is going to be our inner private class. The client doesn't need to 11 KOW class Mode // TODO - your code here private: Bode *_head, tail, prev_to_current: size_t size: public: Playlist: -Playlist: size_t get_size() const { return size: Song_Entrys get_current_song) const: // The following return this on success, null on failure. See the spec // for why Playlist "clear(); Playlist rewind Playlist push_back (const Song Entry s) Playlist "push_front (const Song Entry a): Playlist "insert_at_cursor(const Song Entryss): Playlist remove_at_cursor() Playlist advance_CUESOE() Playlist circular_advance_cursor(); // the following return the target payload (oz sentinel) reference on success Song Entrys find by_idfint id) const: Song_Entry find by_name (string songame) const: string to_string() const friend class Tests: // Don't remove this line On returning a pointer to the list Note that some of the public list manipulation methods return a pointer to the current list object. Why do we do that? We do it because it allows us to program using a very nice pattern my_list -push_back (song_1) ->push_back (song_2) ->push_back song_3) In fact, it would be better if you returned a reference to the current object rather than a pointer. Then you can write the even nicer pattern: my_list -push_back (song_1) -push_back song_2 -push_back song_3) I'll leave you to experiment with the esthetics and find out more. But in this quest, you're gonna have to return a pointer to the current object (essentially this) On being clear where your head is Note that you are guaranteed to find a head node in any valid list with this approach. The head node is always equal to the very first actual node of the list. It is not a data node, and we will use it to double as a sentinel (see next section). _prev_to_current is always equal to the node immediately before what we call the current node (by design. You can think of it as the cursor in this linked list. It always points to (or has a next element that is equal to the node that we define as current. All list operations are done at the location of this cursor. I think one of the best ways you'll get to appreciate the utility of this member is to try and program this quest without using it. This member saves you from having to scan the list from the beginning just to find where "here" is. If you use this member, then "here" (the current location) is always directly in front of your_prev_to_current node. This will make a whole lot more sense once you've programmed this functionality both ways. I highly recommend you do so (for your own edification). On sentinels Some of the Playlist methods return a Song_Entry object. What would you do if the requested operation failed and you don't have a Song_Entry object to return? For example, what would you return if I invoked your find_by_id () and passed it an non-existent song ID? The most common way to handle such a situation is using what are called exceptions. However, we don't cover exceptions until a week or so from now. So until then, we'll use a stopgap measure and make the method return a sentinel. A sentinel is a known invalid object. In this case, conveniently use the header node in a linked list as a sentinel. When you create a header node, make sure the object in it has an id of -1. This is the sentinel and will never change. The user only gets to see what_head->next points to and downstream from there. On to the miniquests... Your first miniquest - Know your songs, nodes and lists Implement the following public methods: Song_Entry::set_id() Song_Entry::set_name() Node constructor Playlist constructor Make sure you read about the special things to do with Nodes (earlier in this document) before you start implementing The Playlist constructor should create an empty Playlist that matches Figure 1. So it's easy rewards. Go for it. new Playlist _head Song_Entry _id: -1; name: "HEAD" tail NULL prev_to_current next Figure 1 The head node should be a Song_Entry object with an id of -1. Remember that you cannot set negative ids in a Song_Entry object using a setter on it. The only way to do it would be at construction time (that is, when you create the head node). Your second miniquest-Destructors Since your Playlist constructor is going to allocate memory on the heap, you must have a destructor or you will suffer memory leaks. Implement Playlist::-Playlist(); Make sure your destructor clears out the linked list by freeing all downstream nodes first and then deleting_head (which got allocated in the constructor). To accomplish this you would delete_head, which should trigger Playlist::-Node, the Node destructor. However, once invoked, the Node destructor will be called, and it should iteratively peel off one node at a time (adjacent to _head) and delete (free) it When all downstream nodes have been released thus, the Node destructor should delete_head and return. Note that there is no guarantee a memory location won't be overwritten the moment you delete the object to which it belongs. Thus, before you delete a node's descendants (starting at its _next member), make sure that you have taken a copy of that member into your local variable. Don't try to access it AFTER the node has been deleted. Then you will likely encounter unpredictable errors that cause your code to work sometimes and not other times. Carelessness here has resulted in forum posts that went "I'm sure I had it working, but something must have changed on the testing site because it's not working any more." Esthetics A good rule of thumbluse when I have questions about where to deallocate memory is this: If the memory was allocated in the constructor, then it should only be deallocated in the destructor. In general, I try and match up my allocations and deallocations into symmetric locations in the causal chain leading up to some action and back Also, keep in mind that you should not delete the "this" object. It is the deletion of the current object that triggers its destructor to be called. In here, you should only delete downstream nodes. This paragraph will likely save you several hours of debugging frustration: When you destroy a node, you will have to delete its _next member. This means that a node's deletion will auto invoke the delete on its_next pointer and so on. You want to make sure you delete no more than you should. Therefore make sure to (1) set every pointer you delete to nullptr so you can check before you attempt to double-delete something and (2) clear out a Node's _next pointer (set it to null) before you delete the node. This will prevent the delete from cascading to affect all downstream nodes. Your third miniquest - Insert song at current location Implement: Playlist Playlist::insert_at_cursor (const Song_Entry s); When I invoke it, I will pass it a Song_Entry object as its argument. It should insert a copy of that object at the current location of the Playlist object. It should leave the current location unchanged. This means that your _prev_to_current member will now end up pointing to this newly inserted Node. This is a tricky method and is worth getting correct before you move on. Refer to the picture in Figure 2 to see what needs to happen: Playlist PlaylistNodes head tant next Pre to current insert_at_cursor(my_song) Playlist Playlist: Nodes cant powstant NULL next Figure 2-insert at cursor Your fourth miniquest - Push back Implement: Playlist *push_back (const Song_Entrys s); This method must insert (a copy of the song s as a brand new node at the end of the list. That is, this newly allocated Node will become the new_tail. Since you have already implemented insert_at_cursor (). simply use it to complete this mini quest. 1. Save the current value of_prev_to_current, then set it to your_tail 2. Then insert the given string at the current position (which will now be the tail). 3. Finally restore the value of_prev_to_current to your saved value. Important! Remember that_prev_to_current can never benul because it's at least pointing to the list header. The current element visible to the user is always the element AFTER prev_to_current. So, when you're trying to advance the cursor and it's pointing to the element before_tail you return null (Why?? Your seventh miniquest - Circular Advance Implement: Playlist Playlist:: circular_advance_cursor(); This is essentially the same as advance_cursor() EXCEPT for the fact that if the cursor is pointing to the very last data node, the advance will silently reset to point to the first node. Refer to the picture below to see what needs to happen: Playlist Playlistdiode head talt , HULL Cerculer_advance_cutOS Playlist Playlist PlaylistNode head DOXE NULL pretources Figure 4-circular advance Your eighth miniquest - Get current song Implement: SongEntry Playlist::get_current_song(); If a_next element exists, then simply return its_song member. If no next element exists (this could happen if _prev_to_current is the same as your tail node), then you must return the sentinel (this->_head-> song) This method is only a few mins but malesure you understand itfully, Ask in the forums any of its under The current item is the song member of whichevernode is exulto preto current->_ext preto current->next = nullot which should not hoe we would really throw an exception. But since we havent covered aceptions yet we will return the sentinel Your ninth miniquest - Remove song at cursor Implement: Playlist Playlist:: remove_at_cursor(); NULE next next next next Ft remove at CUTE() bead prev_count NULL next next Figure 5 -remove at current position Again, this is a tricky method and important to get right. Refer to the picture in Figure 3 to decide exactly what needs to happen in your code Your tenth miniquest - Get size Implement: size_t Playlist::get_size() const; I can't believe you're gonna get a reward for just reporting the value of size! Still, I guess this is your first quest this quarter and you gotta have some freebies... Your eleventh miniquest - Rewind (but not relax just yet) Implement: Playlist Playlist::rewind(); This should reset_prev_to_current back to the_head node. Your twelfth miniquest - Clear Implement: void Playlist::clear(); Yet another tricky method to get right. When invoked, it must 1. Iteratively (not recursively) delete all the non-null nodes in the chain starting at _head->_next (Talking points: What might the problem be with a recursive delete instead?) Consider using the Node destructor you wrote. 2. Reset_prev_to_current and_tail back to _head 3. Set the value of_head->next to nullptr Note that you are not deleting the memory associated with the_head node itself. That is the job of the destructor. What the constructor created, only the destructor should undo Your thirteenth miniquest-Find an item Implement the following linear-search methods: Song_Entry& Playlist::find_by_id(int id) const; Song_Entry& Playlist::find_by_name (string id) const; Note an important aspect of the signature. They return references to Song Entry objects. Not copies. If the requested song exists in the list, then what gets returned is a reference to the actual data element. That means that if I assign something to this reference, it will change the contents of the list node that contains that song. It's important to understand exactly what that means. Please do discuss it in the forums and help each other out whenever possible. Ask me if you're stuck. What will this method return if the requested song is not found in the list? In that case, returna Sentinel in the same way you did for get_current_song(). Your fourteenth miniquest - Stringify Implement: string Playlist::to_string() const; This method must return a string representation of the list of strings in the following exact format. I've colored in the spaces. Each colored rectangle stands for exactly one space. Playlist: [N] lentries. Yid: [id], name: [Name of Ist song) lid: [id], name: [Name of and song) [ id: [idk], name: [Name of kth songi [B] lid: [ian], name: [Name of last song] ITI The parts in red above (also in square brackets) must be replaced by you with the appropriate values. The_prev_to_current element, if visible, should be marked with a [F] tag (see above). Similarly The very last element (the tail), if visible, should be marked with a [T] tag You would print a maximum of 25 elements this way. If the list has more than 25 strings, you must print first 25 and then print a single line of ellipses (...) in place of the remaining elements. There is one newline after the last line (which may be ellipses). Here's a point to ponder and discuss. Why do we need to say "if visible" when talking about the cursor above? Review Now I recommend that you rewind and review the specs one more time making notes along the way. It will help you when you start cutting code