#ifndef CA_UWATERLOO_ALUMNI_DWHARDER_DISK_REQUEST_SIMULATIONS
#define CA_UWATERLOO_ALUMNI_DWHARDER_DISK_REQUEST_SIMULATIONS

#include <cassert>
#include "Events.h"

// Author:  Douglas Wilhelm Harder
// Copyright (c) 2012 by Douglas Wilhelm Harder.  All rights reserved.

void update( int &time, Event &eve, int &current_track, int ord, int read_time, int head_speed ) {
	time += abs( current_track - eve.track )/head_speed + read_time;
	eve.order = ord;
	eve.service_time = time;
	current_track = eve.track;
}

void simulate_fcfs( Event *event_list, int N, int read_time, int head_speed ) {
	int time = 0;
	int current_track = 0;

	for ( int i = 0; i < N; ++i ) {
		if ( time < event_list[i].request_time ) {
			time = event_list[i].request_time;
		}

		update( time, event_list[i], current_track, i, read_time, head_speed );
	}
}

void push_onto_priority_queue( Event *event_list, int N, std::set< std::pair< int, int > > &list, int &j, int &time, bool is_empty ) {
	bool at_least_one = false;

	for ( ; j < N; ++j ) {
		if ( event_list[j].request_time <= time ) {
			list.insert( std::pair<int, int>( event_list[j].track, j ) );
			at_least_one = true;
		} else {
			break;
		}
	}

	if ( !at_least_one && is_empty && j != N ) {
		list.insert( std::pair<int, int>( event_list[j].track, j ) );
		time = event_list[j].request_time;
		++j;
	}
}


void simulate_sstf( Event *event_list, int N, int read_time, int head_speed ) {
	int time = 0;
	int current_track = 0;

	std::set< std::pair< int, int > > list;

	list.insert( std::pair<int, int>( event_list[0].track, 0 ) );
	std::set< std::pair<int, int> >::iterator itr = list.begin();

	int j = 1;

	for ( int i = 0; i < N; ++i ) {
		int n = itr->second;

		if ( event_list[n].request_time > time ) {
			time = event_list[n].request_time;
		}

		update( time, event_list[n], current_track, i, read_time, head_speed );
		push_onto_priority_queue( event_list, N, list, j, time, list.size() == 1 );

		if ( itr == list.begin() ) {
			++itr;
		} else {
			std::set< std::pair<int, int> >::iterator n_itr = itr;

			++n_itr;

			if ( n_itr == list.end() ) {
				--itr;
			} else {
				std::set< std::pair<int, int> >::iterator p_itr = itr;
				--p_itr;

				if ( ( current_track - p_itr->first ) <= ( n_itr->first - current_track ) ) {
					--itr;
				} else {
					++itr;
				}
			}
		}

		list.erase( std::pair<int, int>( event_list[n].track, n ) );
	}
}

void simulate_look( Event *event_list, int N, int read_time, int head_speed ) {
	int time = 0;
	int current_track = 0;
	int direction = 0;

	std::set< std::pair< int, int > > list;

	list.insert( std::pair<int, int>( event_list[0].track, 0 ) );
	std::set< std::pair<int, int> >::iterator  itr = list.begin();

	int j = 1;

	for ( int i = 0; i < N; ++i ) {
		int n = itr->second;

		if ( event_list[n].request_time > time ) {
			time = event_list[n].request_time;
		}

		update( time, event_list[n], current_track, i, read_time, head_speed );
		push_onto_priority_queue( event_list, N, list, j, time, list.size() == 1 );

		if ( direction == 0 ) {
			++itr;

			if ( itr == list.end() ) {
				direction = 1;
				--itr;
				--itr;
			}
		} else {
			if ( itr == list.begin() ) {
				direction = 0;
				++itr;
			} else {
				--itr;
			}
		}

		list.erase( std::pair<int, int>( event_list[n].track, n ) );
	}
}

void simulate_c_look( Event *event_list, int N, int read_time, int head_speed ) {
	int time = 0;
	int current_track = 0;

	std::set< std::pair< int, int > > list;

	list.insert( std::pair<int, int>( event_list[0].track, 0 ) );
	std::set< std::pair<int, int> >::iterator  itr = list.begin();

	int j = 1;

	for ( int i = 0; i < N; ++i ) {
		int n = itr->second;

		if ( event_list[n].request_time > time ) {
			time = event_list[n].request_time;
		}

		update( time, event_list[n], current_track, i, read_time, head_speed );
		push_onto_priority_queue( event_list, N, list, j, time, list.size() == 1 );

		++itr;

		if ( itr == list.end() ) {
			itr = list.begin();
		}

		list.erase( std::pair<int, int>( event_list[n].track, n ) );
	}
}

void simulate_f_look( Event *event_list, int N, int read_time, int head_speed ) {
	int time = 0;
	int current_track = 0;
	int current_queue = 0;

	std::set< std::pair< int, int > > list[2];

	list[current_queue].insert( std::pair<int, int>( event_list[0].track, 0 ) );
	std::set< std::pair<int, int> >::iterator  itr = list[current_queue].begin();

	int j = 1;

	for ( int i = 0; i < N; ++i ) {
		int n = itr->second;

		if ( event_list[n].request_time > time ) {
			time = event_list[n].request_time;
		}

		update( time, event_list[n], current_track, i, read_time, head_speed );
		push_onto_priority_queue( event_list, N, list[1 - current_queue], j, time, list[current_queue].size() == 1 );

		++itr;
		list[current_queue].erase( std::pair<int, int>( event_list[n].track, n ) );

		if ( itr == list[current_queue].end() ) {
			assert( list[current_queue].size() == 0 );
			current_queue = 1 - current_queue;
			itr = list[current_queue].begin();
		}
	}
}

#endif