// Project identifier: 9504853406CBAC39EE89AA3AD238AA12CA198043
#include <queue>
#include <stack>
#include <deque>
#include <list>
#include <getopt.h>
#include <sstream>
#include <unistd.h>
#include <iostream>
#include <string>
#include <vector>
#include <stdio.h>
#include <ctype.h>
#include <algorithm>
#include "battle.h"

using namespace std;

// UTILITIES
// clears pq
void clear_pq(priority_queue<Zombie, vector<Zombie>, ZombieOrder> &zombie_queue){
    while(!zombie_queue.empty()){
        zombie_queue.pop();
    }
}

//initialize
void initialize(Game &game){
    // READ INPUT
    //void start battle
    // battle info
    string junk = "";
    uint32_t quiver_cap;
    uint32_t rand_seed;
    uint32_t mr_distance;
    uint32_t mr_speed;
    uint32_t mr_health;

    // ignore comment
    cin.ignore(256,'\n');
    cin >> junk;
    // get quiver
    cin >> quiver_cap;
    cin >> junk;
    // get seed
    cin >> rand_seed;
    cin >> junk;
    // get mr_distance
    cin >> mr_distance;
    cin >> junk;
    // get mr_speed
    cin >> mr_speed;
    cin >> junk;
    // get mr_health
    cin >> mr_health;

    //set quiver_cap
    game.quiver_cap = quiver_cap;

    //initialize
    P2random::initialize(rand_seed, mr_distance, mr_speed, mr_health);
}

// return index of zombie in master list
size_t get_zombie(const Zombie &top, deque<Zombie> &zombies){
    for(size_t i=0; i < zombies.size(); i++){
        if(top.name == zombies[i].name){
            return i;
        }
    }
    return 0;
}

//increment rounds active
void inc_rounds_active(Game &game){
    for(size_t i=0; i < game.zombies.size(); i++){
        if(game.zombies[i].health > 0){
            game.zombies[i].rounds_active++;
        }
    }
}

// FUNCTIONS 
// create zombies
void create_zombies(uint32_t &rand_zomb, uint32_t &named_zomb, deque<Zombie> &zombies, Line_args &line_args, string &junk){
    // create random zombies
    for(uint32_t i=0; i < rand_zomb; i++){
        Zombie zombie;
        zombie.name  = P2random::getNextZombieName();
	    zombie.distance = static_cast<int>(P2random::getNextZombieDistance());
	    zombie.speed    = static_cast<int>(P2random::getNextZombieSpeed());
	    zombie.health   = P2random::getNextZombieHealth();
        zombie.rounds_active = 1;
        // VERBOSE
        if(line_args.verbose){
            verbose_create(zombie); 
        }
        zombies.push_back(zombie);
    }
        
    // create named zombies.
    for(uint32_t i=0; i < named_zomb; i++){
        Zombie zombie;
        cin >> zombie.name >> junk >> zombie.distance >> junk >> zombie.speed >> junk >> zombie.health;
        zombie.rounds_active = 1;
        // VERBOSE
        if(line_args.verbose){
            verbose_create(zombie); 
        }
        zombies.push_back(zombie);
    }
}

// advance zombies
void advance_zombies(Game &game, Line_args &line_args, bool &game_over){
    // All active zombies advance toward you, updated in the order that they were created.
    // advance zombies
    size_t killer_zombie = 0;
    for(size_t i=0; i < game.zombies.size(); i++){
        if(game.zombies[i].health > 0){
            game.zombies[i].distance -= game.zombies[i].speed;
            // At this point, if the Player was killed in Step 3, the battle ends.
            if(game.zombies[i].distance <= 0){
                game.zombies[i].distance = 0;
            if(game_over == false){
                killer_zombie = i;
                game_over = true;
                }  
            }
            if(line_args.verbose){
                cout << "Moved: " << game.zombies[i].name 
                << " (distance: " << game.zombies[i].distance
                << ", speed: " << game.zombies[i].speed << ", health: " << game.zombies[i].health << ")\n";
            }
        }
    }
    if(game_over == true){
        print_defeat(game.current_round, game.zombies, killer_zombie);
        if(line_args.stats){
            print_stats(game, line_args);
        }
    game_over = true;
    exit(0);
    }
}

// load zombies to PQ
void load_zombies(Game &game){
    clear_pq(game.zombie_queue);
    // load active zombies to pq
    for(size_t i=0; i < game.zombies.size(); i++){
        if(game.zombies[i].health > 0){
            //create pointer and push
            game.zombie_queue.push(game.zombies[i]);
            //cout << "loaded " << zombies[i].name << ", " << zombies[i].health << "\n";
        }
    }
}

// shoot zombies
void shoot_zombies(uint32_t &quiver, Game &game, Line_args &line_args, string &last_killed){
    // Shoot the zombie with the lowest ETA (tie breaking described above) until your quiver is empty.
    while(quiver > 0 && !game.zombie_queue.empty()){
        //cout << "top zombie" << zombie_queue.top().name << "\n";
        if(game.zombies[get_zombie(game.zombie_queue.top(), game.zombies)].health > 0){
            game.zombies[get_zombie(game.zombie_queue.top(), game.zombies)].health -= 1;
        }
        // if zombie dies, remove from pq
        if(game.zombies[get_zombie(game.zombie_queue.top(), game.zombies)].health == 0){
            game.get_median = true;
            // VERBOSE
            if(line_args.verbose){
                verbose_destroy(game.zombies[get_zombie(game.zombie_queue.top(), game.zombies)]);
                }
            last_killed = game.zombie_queue.top().name;
            game.killed_zombies.push_back(game.zombie_queue.top());
            game.zombie_queue.pop();
            }
        quiver--;
    }
}


// MEDIAN
// print median
void print_median(Game &game){
    int median = 0;
    //get median
    priority_queue<int, vector<int>, std::less<int> > median_pq_min;
    priority_queue<int, vector<int>, std::greater<int> > median_pq_max;
    median_pq_max.push(std::numeric_limits<int>::max());
    median_pq_min.push (std::numeric_limits<int>::min());
    for(size_t i=0; i < game.zombies.size(); i++){
        if(game.zombies[i].health == 0){
            //If number is greater than the least upper number, it is an upper number
            if(game.zombies[i].rounds_active >= median_pq_max.top())
                median_pq_max.push(game.zombies[i].rounds_active);
            else //Otherwise it is a lower number
                median_pq_min.push(game.zombies[i].rounds_active);

            //Rebalance
            //If the queues sizes differ by 2, they need to be rebalanced so that they
            //differ by 1.
            if(median_pq_max.size() - median_pq_min.size() == 2){ 
                median_pq_min.push(median_pq_max.top());       
                median_pq_max.pop();                    
            } 
            else if(median_pq_min.size() - median_pq_max.size() == 2){ 
                median_pq_max.push(median_pq_min.top());               
                median_pq_min.pop();                          
            }
        }
    }

    if(median_pq_max.size() == median_pq_min.size()){         
        median = (median_pq_max.top() + median_pq_min.top()) / 2; 
    }
    else if(median_pq_max.size() > median_pq_min.size()){ 
        median = median_pq_max.top();
    }       
    // min size is greater   
    else {                                         
      median = median_pq_min.top();
    }
    
    //print median
    //At the end of round 1, the median zombie lifetime is 1
    cout << "At the end of round " << game.current_round
    << ", the median zombie lifetime is " << median << "\n";
}


// VERBOSE 
// output Zombie Creation
void verbose_create(Zombie &zombie){
    cout << "Created: " << zombie.name << 
    " (distance: " << zombie.distance << ", speed: " << zombie.speed 
    << ", health: " << zombie.health << ")\n";
}
// output Zombie Destruction
void verbose_destroy(Zombie &zombie){
    cout << "Destroyed: " << zombie.name << 
    " (distance: " << zombie.distance << ", speed: " << zombie.speed 
    << ", health: " << zombie.health << ")\n";
}
// print victory
void print_victory(int &current_round, string &last_killed){
    cout << "VICTORY IN ROUND " << current_round << "! " << last_killed <<  " was the last zombie.\n";
}
// print defeat
void print_defeat(int &current_round, deque<Zombie> &zombies, size_t &killer_zombie){
    cout << "DEFEAT IN ROUND " << current_round << "! " << zombies[killer_zombie].name << " ate your brains!\n";
}

// STATS
// print still active
void print_still_active(Game &game){
    cout << "Zombies still active: " << game.zombies.size() - game.killed_zombies.size() << "\n";
}
// resets killed zombie container
void reset_killed_zombies(Game &game, deque<Zombie> &reset){
    while(!reset.empty()){
        game.killed_zombies.push_front(reset.back());
        reset.pop_back();
    }
}
// loads active queue with all zombies
void load_active_queue(Game &game){
    for(size_t i=0; i < game.zombies.size(); i++){
        game.active_queue.push(game.zombies[i]);
        //cout << "pushed " << game.zombies[i].name << "\n";
    }
}
// loads rev active queue with all zombies
void load_rev_active_queue(Game &game){
    for(size_t i=0; i < game.zombies.size(); i++){
        game.rev_active_queue.push(game.zombies[i]);
        //cout << "pushed " << game.zombies[i].name << "\n";
    }
}
void print_killed_zombies(Game &game, Line_args &line_args){
    deque<Zombie> reset;
    //first N zombies killed
    uint32_t count = 1;
    cout << "First zombies killed:\n";
    while(!game.killed_zombies.empty() && count <= line_args.stats_num){
        cout << game.killed_zombies.front().name  << " " << count << "\n";
        reset.push_back(game.killed_zombies.front());
        game.killed_zombies.pop_front();
        count++;
    }
    //last N zombies killed
    reset_killed_zombies(game, reset);
    count = line_args.stats_num;
    if(static_cast<uint32_t>(game.killed_zombies.size()) < line_args.stats_num){
        count = static_cast<uint32_t>(game.killed_zombies.size());
    }
    cout << "Last zombies killed:\n";
    while(!game.killed_zombies.empty() && count > 0){
        cout << game.killed_zombies.back().name  << " " << count << "\n";
        game.killed_zombies.pop_back();
        count--;
    }
    //most active
    count = 0;
    cout << "Most active zombies:\n";
    load_active_queue(game);
    while(!game.active_queue.empty() && count < line_args.stats_num){
        cout << game.active_queue.top().name << " " << game.active_queue.top().rounds_active << "\n";
        game.active_queue.pop();
        count++;
    }
    //least active
    count = 0;
    cout << "Least active zombies:\n";
    load_rev_active_queue(game);
    while(!game.rev_active_queue.empty() && count < line_args.stats_num){
        cout << game.rev_active_queue.top().name << " " << game.rev_active_queue.top().rounds_active << "\n";
        game.rev_active_queue.pop();
        count++;
    }

}
//STATS
void print_stats(Game &game, Line_args &line_args){
    print_still_active(game);
    print_killed_zombies(game, line_args);
}
// TESTING //

// TESTING //