Question

Description

The purpose of this challenge is to implement a circular doubly-linked list using a dummy node. This challenge simulates an operating system’s window manager.

Requirements

Write the following struct

struct Window { string appname; Window *next; Window *prev; };

Create a class called WindowManager. In this class, create a private variable Window * head. This will keep track of the location of the head node.

Create private variables Window * current, * dummy. current will keep track of the “current” program. Think of it as the program currently being used by the user in this simulated operating system. head and dummy will always paint to the dummy node. (You really could get by using just head or just dummy)

Add the following private function. This function will be used to dynamically create new nodes for the linked list.Window * create() { Window * newnode; try { newnode = new Window; } catch (bad_alloc) { newnode = NULL; } return newnode; } // USAGE: To create a new node, use as follows // Window * newnode = create();

Create a private function called void deallocate(). This function will traverse the entire list and delete each node. Remember to make a copy of head. Also, realize that if you delete the current node as you’re traversing, you may lose the reference to the next node. Make sure that the dummy node is also deleted.

Create a destructor which will call deallocate() and set head to NULL.

Create a default constructor which will instantiate a dummy node. Set head and dummy to point to this dummy node. Set the appname property of the dummy node to a blank string.

Create a public function bool start_app(string name). This function will create a new Window node and insert the new node to the left of the dummy node. (Remember that after adding the first node, this node’s next and prev will point to the dummy node. Also, next and prev of the dummy node will point to the first node. This only occurs with the addition of the first node). Set current to the node created in this function. (think of current as the last app launched by the user)

Create a public function Window * find_app(string name). This function will perform a traversal searching the queue for a node with appname equal to name. You can perform the traversal in any direction (going in the direction of next from the dummy node, or going in the direction of prev from the prev node). No matter which direction you choose to traverse to search for the node, you will either find a matching node, in which case you will return the address of that node, or you end up back at the dummy node without finding a match. If you traverse the entire queue without finding the matching node, the function should return a NULL. Remember to skip over the dummy node during any traversals.

Create a public function bool close_app(string name). This function calls find_app() to help find the app’s node. If a matching node is found, delete the node and take it out of the queue. If a matching node is found, return true. Otherwise, return false. Set current to the next node following the app that was just closed. Remember to skip over the dummy node during any traversals — current cannot point to the dummy node. If the queue is empty, then current is NULL.

Create a public function string get_current(). This function will return  appname of current. If current is NULL, it should return a blank string.

Create a public function string next(). This program advances current to the next app in the circular queue. Remember to skip the dummy node during the traversal. If the queue is empty, then current is NULL.

Create a public function string previous(). This program “advances” current to the previous app in the circular queue. Remember to skip the dummy node during the traversal. If the queue is empty, then current is NULL.

main() is given below. Use it exactly as is. Note that main uses the WindowManager class as an abstract data type (ADT). From the perspective of the object winman, it doesn’t even know or care that a linked-list is the mechanism that makes the circular queue work.

In main(),

Option 1 will prompt the user to enter a string, the app’s name. Call winman.start_app() to simulate running this app.

Option 2 will close the current running app

Option 3 will prompt the user to enter an app name. Use winman.close_app() to find the app, and then close it

After both option 2 and 3, show the name of the new current app by calling the get_current() function (If an app is closed, then the next app becomes the new current app as long as other apps are running).

Option 4 calls winman.next() and shows the current app

Option 5 calls winman.previous() and shows the current app

Option 0 exits your running program.

Sample main()

int main() { WindowManager winman; // simulate some apps running winman.start_app("Microsoft Word"); winman.start_app("Firefox"); winman.start_app("Halo"); winman.start_app("Calculator"); // at this point, Calculator is the last app launched // and should be the value of current in winman int action; do { cout << "1 - Launch new app" << endl; cout << "2 - Close current app" << endl; cout << "3 - Find app, then close it" << endl; cout << "4 - Go to next app" << endl; cout << "5 - Go to previous app" << endl; cout << "0 - Shutdown" << endl; cin >> action; // fill in the rest of the necessary code to perform // menu actions } while (action != 0); cout << "Shutting down..." << endl; return 0;}

Answer 1

Below is required code. Let me know if you have any problem or doubts. Thank you.

==================================================================

#include <iostream>
#include <string>
using namespace std;

// structure to represent window
struct Window {
    string appname;
    Window* next;
    Window* prev;
};

class WindowManager {
private:
    Window* head; // keep track of the location of the head node
    Window* dummy;
    Window* current; // keep track of the "current" program.
    // function to dynamically create new nodes for the linked list
    Window* create() {
        Window* newnode;
        try {
            newnode = new Window;
        }
        catch (bad_alloc) {
            newnode = NULL;
        }
        return newnode;
    }
    // This function will traverse the entire list and delete each node
    void deallocate() {
        // move head to next of dummy
        head = dummy->next;
        while ((head != NULL) && (head != dummy)) {
            // create temp node to delete
            Window* temp = head;
            head = head->next; // move head to next node
            // delete the node
            delete temp;
        }
        // delete dummy node
        delete dummy;
    }
public:
    // destructor
    ~WindowManager() {
        deallocate();
        head = dummy = current = NULL;
    }
    // constructor
    WindowManager() {
        // create a dummy node
        dummy = create();
        // intialize dummy
        dummy->appname = "";
        dummy->next = NULL;
        dummy->prev = NULL;
        // set head to dummy
        head = dummy;
        current = NULL; // no app launched yet
    }
    // creates a new Window node and insert the new node to the left of the dummy node
    bool start_app(string name) {
        // create a new window
        Window* new_node = create();
        // check for NULL node
        if (new_node == NULL) {
            return false;
        }
        new_node->appname = name;
        // insert node to left of dummy
        // check for the first node to be inserted
        if (dummy->next == NULL) {
            dummy->next = new_node;
            new_node->prev = dummy;
        }
        else {
            new_node->prev = dummy->prev;
            dummy->prev->next = new_node;
        }
        new_node->next = dummy;
        dummy->prev = new_node;
        // set new node as current node
        current = new_node;
        return true;
    }
    // perform a traversal searching the queue for a node with appname equal to name
    Window* find_app(string name) {
        // check for empty list
        if (dummy->next == NULL) {
            return NULL;
        }
        // start searching from dummy
        Window* itr = dummy->next;
        while ((itr->appname.compare(name) != 0) && (itr != dummy)) {
            itr = itr->next;
        }
        // check if appname found
        if (itr == dummy) {
            return NULL;
        }
        else {
            return itr;
        }
    }
    // colose the app with given name
    bool close_app(string name) {
        // search for app in list
        Window* app = find_app(name);
        if (app == NULL) {
            return false;
        }
        // set current to next node
        current = app->next;
        // remove app node
        app->prev->next = app->next;
        app->next->prev = app->prev;
        delete app;
        // check for dummy node
        if (current == dummy) {
            current = current->next;
        }
        // check for empty list
        if (current == dummy) {
            current = NULL;
        }
        return true;
    }
    // return appname of current
    string get_current() {
        if (current == NULL) {
            return "";
        }
        return current->appname;
    }
    // advances current to the next app in the circular queue
    string next() {
        if (current != NULL) {
            current = current->next;
            // check for dummy node
            if (current == dummy) {
                current = current->next;
            }
            // check for empty list
            if (current == dummy) {
                current = NULL;
            }
        }
        // return appname
        return get_current();
    }
    // advances current to the previous app in the circular queue
    string previous() {
        if (current != NULL) {
            current = current->prev;
            // check for dummy node
            if (current == dummy) {
                current = current->prev;
            }
            // check for empty list
            if (current == dummy) {
                current = NULL;
            }
        }
        // return appname
        return get_current();
    }
};

int main() {
    WindowManager winman; // simulate some apps running
    winman.start_app("Microsoft Word");
    winman.start_app("Firefox");
    winman.start_app("Halo");
    winman.start_app("Calculator");
    // at this point, Calculator is the last app launched
    // and should be the value of current in winman
    int action;
    do {
        cout << "1 - Launch new app" << endl;
        cout << "2 - Close current app" << endl;
        cout << "3 - Find app, then close it" << endl;
        cout << "4 - Go to next app" << endl;
        cout << "5 - Go to previous app" << endl;
        cout << "0 - Shutdown" << endl;
        cin >> action;
        // menu actions
        if (action == 1) {
            // prompt the user to enter a string, the app's name
            string app_name;
            cout << "Enter app name: ";
            cin.ignore(); // ignore newline charater
            getline(cin, app_name);
            winman.start_app(app_name);
        }
        else if (action == 2) {
            // close current app if applist is not empty
            string name = winman.get_current();
            if (name.size() > 0) {
                winman.close_app(name);
                // show current app
                cout << "current app: " << winman.get_current() << endl;
            }
        }
        else if (action == 3) {
            // prompt the user to enter an app name
            string app_name;
            cout << "Enter app name: ";
            cin >> app_name;
            if (winman.close_app(app_name)) {
                // show current app
                cout << "current app: " << winman.get_current() << endl;
            }
        }
        else if (action == 4) {
            cout << "current app: " << winman.next() << endl;
        }
        else if (action == 5) {
            cout << "current app: " << winman.previous() << endl;
        }
    } while (action != 0);
    cout << "Shutting down..." << endl;

    return 0;
}

==================================================================