/*------------------------------------------------------------------------------
 * problem005.cc: visualize the state of a work queue
**----------------------------------------------------------------------------*/

/* Copyright (c) 2009 Peter Bui. All Rights Reserved.
 *
 * Peter Bui <pbui@cse.nd.edu>
 *
**------------------------------------------------------------------------------
 * Includes
**----------------------------------------------------------------------------*/

#include <cstdlib>
#include <algorithm>
#include <functional>
#include <iostream>
#include <list>
#include <map>
#include <string>

using namespace std;

/*------------------------------------------------------------------------------
 * Data Structures
**----------------------------------------------------------------------------*/

struct Job {
    char    id;
    int	    priority;
};

/*------------------------------------------------------------------------------
 * Type Definitions
**----------------------------------------------------------------------------*/

typedef struct Job	    Job;
typedef map<string, int>    UserMap;
typedef list<Job*>	    JobList;
typedef map<char, int>	    JobMap;

/*------------------------------------------------------------------------------
 * Functions
**----------------------------------------------------------------------------*/

struct JobId : public binary_function<Job*, char, bool> {
    bool operator () (const Job *job, const char &id) const {
	return (job->id == id);
    }
};

Job *
job_create(char id, int priority)
{
    Job *e;

    e = new Job;
    e->id = id;
    e->priority = priority;

    return (e);
}

void
job_destroy(Job *job)
{
    delete job;
}

void
job_list_submit(JobList &job_list, Job *job)
{
    JobList::reverse_iterator it;
    
    if (job_list.empty()) {
	job_list.push_front(job);
    } else {
	for (it = job_list.rbegin(); it != job_list.rend(); it++)  
	    if ((*it)->priority <= job->priority) 
		break;
	job_list.insert(it.base(), job);
    }
}

void
job_list_evict(JobList &job_list, char id)
{
    JobList::iterator it;

    it = find_if(job_list.begin(), job_list.end(), bind2nd(JobId(), id));
    if (it != job_list.end()) {
	job_list.erase(it);
	job_destroy(*it);
    }
}

void
job_list_visualize(JobList &job_list, int step) {
    JobList::iterator it;

    cout << "WQ[";
    cout.width(4);
    cout.fill('0');
    cout << step << "] = [ ";

    for (it = job_list.begin(); it != job_list.end(); it++)
	cout << (*it)->id << ' ';

    cout << ']' << endl;
}

void
read_users(UserMap &users)
{
    string  user;
    int	    priority;

    while (true) {
	cin >> user;
	if (user == "*Users*")
	    continue;
	else if (user == "*Events*")
	    break;

	cin >> priority;
	users[user] = priority;
    }
}

void
read_events(UserMap &users)
{
    JobList job_list;
    JobMap  job_map;
    Job	*job;
    string event, user;
    char id;
    int i = 0;

    while (true) {
	cin >> event;
	if (cin.eof()) break;

	if (event == "Submit") {
	    cin >> user >> id;
	    job = job_create(id, users[user]);
	    job_list_submit(job_list, job);
	    job_map[id] = job->priority;
	} else if (event == "Evict") {
	    cin >> id;
	    job_list_evict(job_list, id);
	} else if (event == "Retry") {
	    cin >> id;
	    
	    job = job_create(id, job_map[id]);
	    job_list.push_front(job);
	} else /* (event == "Run")*/ {
	    job = job_list.front();
	    job_list.pop_front();
	    job_destroy(job);
	}

	job_list_visualize(job_list, ++i);
    }
}

/*------------------------------------------------------------------------------
 * Main Execution
**----------------------------------------------------------------------------*/

int
main(int argc, char *argv[]) 
{
    UserMap users;

    read_users(users);
    read_events(users);

    return (EXIT_SUCCESS);
}

/*------------------------------------------------------------------------------
 * vim: sts=4 sw=4 ts=8 ft=cpp
**----------------------------------------------------------------------------*/