#include <iostream>
using namespace std;
#include "Node.h"

Node *create();
void add(Node *loc, char x);
void add(Node *loc, Node *p);
Node *find_insert_spot(Node *p, char x);
Node *find_item(Node *p, char x);
void remove(Node *p);
void display_all(Node *p);

int main()
{
    Node *head, *p;

    // Create new linked list with
    // only header and trailer.
    head = create();

    // Add node with item M.
    p = find_insert_spot(head, 'M');
    add(p, 'M');

    // Add node with item S.
    p = find_insert_spot(head, 'S');
    add(p, 'S');

    // Add node with item B.
    p = find_insert_spot(head, 'B');
    add(p, 'B');

    // Add node with item Q.
    p = find_insert_spot(head, 'Q');
    add(p, 'Q');

    // Add node with item K.
    p = find_insert_spot(head, 'K');
    add(p, 'K');

    // Add node with item X.
    p = find_insert_spot(head, 'X');
    add(p, 'X');

    // Display the linked list
    display_all(head);

    p = find_item(head, 'Q');
    remove(p);

    // Display the linked list
    display_all(head);

    return EXIT_SUCCESS;
}

// Output
//  B K M Q S X
//  B K M S X

// After this are the function 
// definitions.

// Create a new linked list with
// header node containing '\0' and
// trailer node containing '~'.
Node *create()
{
    Node *q;
    q = new Node('\0');
    q -> set_next(new Node('~'));
    return q;
}

// Allocate a node with item x
// and add it to the linked list.
void add(Node *loc, char x)
{
    Node *q;
    q = new Node(x);
    q -> set_next(loc -> get_next());
    loc -> set_next(q);
}

// Add existing node with address
// in p to the linked list.
void add(Node *loc, Node *p)
{
    p -> set_next(loc -> get_next());
    loc -> set_next(p);
}

// Find the last node with item before x.  
// This is the spot to insert the new node 
// to preserve sorted linked list.
Node *find_insert_spot(Node *start, char x)
{
    Node *q;
    for(q = start; true; q = q -> get_next())
        if (q -> get_next() -> get_item() > x)
            break;
    return q;
}

// Find node with given item in linked list
// for purpose of removing the node from the
// linked list.
Node *find_item(Node *start, char x)
{
    Node *q;
    for(q = start; true; q = q -> get_next())
        if (q -> get_next() -> get_item() == x)
            break;
    return q;
}

// Remove item with address in p.
void remove(Node *p)
{
    Node *q;
    q = p -> get_next();
    p -> set_next(q -> get_next());
    delete q;
}

// Display all nodes in the linked list
// except the header and trailer nodes.
void display_all(Node *p)
{
    Node *q;
    for(q = p; q -> get_item() != '~'; 
               q = q -> get_next())
        q -> display();
    cout << endl;
}