#include <iostream>  /* console "reading" */
#include <fstream>   /* file reading */
#include <cstring>   /* strncmp() */
#include <sstream>   /* parse string of integers */
#include <stdlib.h>  /* atoi */
#include <chrono>    /* test proccess time elapsed */
#include <algorithm>
#include <vector>
#include <string>
#include <random>

/*
* Run test or IO stream by default.
* Make this variable 'false' to run tests.
* */
const bool kUseIoByDefault = true;
/*
* Stopes executing of the program in the end.
* Make 'true' to see test results.
* */
const bool kStopConsoleProgramBeforeExit = false;

const std::string kTestFileA = "../resource/test-1.txt";
const std::string kTestFileB = "../resource/test-2.txt";
const std::string kTestFileC = "../resource/test-3.txt";
const std::string kTestFileD = "../resource/test-4.txt";
const std::string kTestFileE = "../resource/test-5.txt";

#ifndef READER_IO_H
#define READER_IO_H

class ReaderIo {
public:
    ReaderIo();

    ~ReaderIo();

    unsigned int ReadNumber();

    std::vector<unsigned int> ReadNumbers(const unsigned int amount);

    std::vector<bool> ReadBools(const unsigned int amount);
};

#endif // READER_IO_H

#ifndef RFILER_H
#define RFILER_H

const char kDelimeter = ' ';

class RFiler {
public:
    RFiler();

    explicit RFiler(const std::string file_name);

    ~RFiler();

    bool Open(const std::string file_name = "");

    void Close();

    void Read();

    void PrintLastString();

    bool IsFileOpened();

    unsigned int ReadNumber();

    std::vector<unsigned int> ReadNumbers(const unsigned int amount);

    std::vector<bool> ReadBools(const unsigned int amount);

    bool SetLineNumber(const unsigned int new_line_number);

    bool IncreaseLineNumber(const unsigned int number_for = 1);

    bool DecreaseLineNumber(const unsigned int number_for = 1);

private:
    std::ifstream current_file_stream_;
    std::string current_file_name_;
    unsigned int current_line_number_;
};

#endif // RFILER_H

RFiler::RFiler() {}

RFiler::RFiler(const std::string file_name) {
    this->current_file_name_ = file_name;
    this->current_file_stream_.open(file_name.c_str());
}

bool RFiler::Open(const std::string file_name) {
    this->current_file_name_ = file_name;
    this->current_file_stream_.open(file_name.c_str());
    return this->IsFileOpened();
}

void RFiler::Close() {
    if (this->IsFileOpened()) {
        this->current_file_stream_.close();
    }
}

void RFiler::Read() {
    std::string line;

    if (this->current_file_stream_.is_open()) {
        while (getline(this->current_file_stream_, line)) {
            std::cout << line << '\n';
        }
        this->current_file_stream_.close();
    } else {
        std::cout << "File for reading \""
                  << this->current_file_name_ << "\" is closed!\n";
    }
}

void RFiler::PrintLastString() {
    std::string line;

    if (this->current_file_stream_.is_open()) {
        while (getline(this->current_file_stream_, line)) {
            // do nothing, just getting last string
        }
        std::cout << line << '\n';
        this->current_file_stream_.close();
    } else {
        std::cout << "File for reading \""
                  << this->current_file_name_ << "\" is closed!\n";
    }
}

bool RFiler::IsFileOpened() {
    return this->current_file_stream_.is_open();
}

unsigned int RFiler::ReadNumber() {
    std::string line;
    unsigned int result = 0;

    if (this->current_file_stream_.is_open()) {
        if (getline(this->current_file_stream_, line)) {
            result = atoi(line.c_str());
        } else {
            std::cout << "Error occurred while file \""
                      << this->current_file_name_ << "\" reading - no lines!\n";
        }
        ++this->current_line_number_;
    } else {
        std::cout << "File for reading \""
                  << this->current_file_name_ << "\" is closed!\n";
    }

    return result;
}

std::vector<unsigned int> RFiler::ReadNumbers(const unsigned int amount) {
    std::string line, token;
    std::stringstream string_stream;
    std::vector<unsigned int> result(amount);

    if (this->current_file_stream_.is_open()) {
        if (getline(this->current_file_stream_, line)) {
            string_stream.str(line);
            for (unsigned int iter = 0; iter < amount; ++iter) {
                std::getline(string_stream, token, kDelimeter);
                result[iter] = atoi(token.c_str());
            }
        } else {
            std::cout << "Error occurred while file \""
                      << this->current_file_name_ << "\" reading - no lines!\n";
        }
        ++this->current_line_number_;
    } else {
        std::cout << "File for reading \""
                  << this->current_file_name_ << "\" is closed!\n";
    }

    return result;
}

std::vector<bool> RFiler::ReadBools(const unsigned int amount) {
    std::string line;
    std::vector<bool> result(amount);

    if (this->current_file_stream_.is_open()) {
        if (getline(this->current_file_stream_, line)) {
            for (unsigned int iter = 0; iter < amount; ++iter) {
                result[iter] = line[iter] == 'R';
            }
        } else {
            std::cout << "Error occurred while file \""
                      << this->current_file_name_ << "\" reading - no lines!\n";
        }
        ++this->current_line_number_;
    } else {
        std::cout << "File for reading \""
                  << this->current_file_name_ << "\" is closed!\n";
    }

    return result;
}

bool RFiler::SetLineNumber(const unsigned int new_line_number) {
    if (new_line_number > this->current_line_number_) {
        return this->IncreaseLineNumber(new_line_number -
                                        this->current_line_number_);
    } else if (new_line_number < this->current_line_number_) {
        return this->IncreaseLineNumber(this->current_line_number_ -
                                        new_line_number);
    }
    return true;
}

bool RFiler::IncreaseLineNumber(const unsigned int number_for) {
    std::string line;
    for (unsigned int iter = 0; iter < number_for; ++iter) {
        if (!getline(this->current_file_stream_, line)) {
            return false;
        }
        ++this->current_line_number_;
    }
    return true;
}

bool RFiler::DecreaseLineNumber(const unsigned int number_for) {
    std::string line;
    unsigned int new_position = current_line_number_ - number_for;

    if (new_position < 0) {
        return false;
    }
    this->current_file_stream_.seekg(0, this->current_file_stream_.beg);

    for (unsigned int iter = 0; iter < new_position; ++iter) {
        if (!getline(this->current_file_stream_, line)) {
            return false;
        }
        ++this->current_line_number_;
    }
    return true;
}

RFiler::~RFiler() {
    if (this->IsFileOpened()) {
        this->current_file_stream_.close();
    }
}

ReaderIo::ReaderIo() {}

unsigned int ReaderIo::ReadNumber() {
    unsigned int result = 0;
    std::cin >> result;
    return result;
}

std::vector<unsigned int> ReaderIo::ReadNumbers(const unsigned int amount) {
    std::vector<unsigned int> result(amount);

    for (unsigned int iter = 0; iter < amount; ++iter) {
        std::cin >> result[iter];
    }
    return result;
}

std::vector<bool> ReaderIo::ReadBools(const unsigned int amount) {
    std::vector<bool> result(amount);
    char tmpp;

    for (unsigned int iter = 0; iter < amount; ++iter) {
        std::cin >> tmpp;
        result[iter] = tmpp == 'R';
    }
    return result;
}

ReaderIo::~ReaderIo() {}

#ifndef HEAP_H
#define HEAP_H

typedef enum {
    none, smallest_numbers, non_allocated_numbers
} placement;

struct HeapElement {
public:
    unsigned int value;
    unsigned int heap_position;
    unsigned int array_position;
    placement which_heap_in;

    HeapElement();

    HeapElement(unsigned int value, unsigned int heap_position = 0,
                placement which_heap_in = placement::none);
};

class Heap {
public:
    Heap();

    void Insert(HeapElement *element);

    void Remove(HeapElement *element);

    void Remove(unsigned int index);

    HeapElement *GetTopValue();

    unsigned int GetSize();

    void Clear();

private:
    std::vector<HeapElement *> queue_;
    unsigned int size_;

    virtual bool Comparator(unsigned int value_a, unsigned int value_b) = 0;

    int GetParent(unsigned int index) const;

    int GetChild(unsigned int index) const;

    int Find(unsigned int index, HeapElement *element) const;

    unsigned int GetMinimumIndex(unsigned int index_a,
                                 unsigned int index_b, unsigned int index_c);

    void BubbleUp(int index);

    void BubbleDown(unsigned int index);
};

class HeapDesc : public Heap {
private:
    bool Comparator(unsigned int value_a, unsigned int value_b);
};

class HeapAsc : public Heap {
private:
    bool Comparator(unsigned int value_a, unsigned int value_b);
};

#endif // HEAP_H

#ifndef SLIDINGSTATISTICS_H
#define SLIDINGSTATISTICS_H

class SlidingStatistics {
public:
    SlidingStatistics();

    ~SlidingStatistics();

    void ReadNumbers(const std::vector<unsigned int> numbers);

    void SetOffset(const unsigned int offset);

    std::vector<int> MoveSlides(const std::vector<bool> slide_right_point_array);

private:
    unsigned int iterator_right_;
    unsigned int iterator_left_;
    unsigned int offset_;
    HeapDesc smallest_numbers_;
    HeapAsc non_allocated_numbers_;
    std::vector<HeapElement *> all_numbers_;
};

#endif // SLIDINGSTATISTICS_H

HeapElement::HeapElement(unsigned int value,
                         unsigned int heap_position, placement which_heap_in) {
    this->value = value;
    this->array_position = 0;
    this->heap_position = heap_position;
    this->which_heap_in = which_heap_in;
}

HeapElement::HeapElement() {
    this->value = 0;
    this->heap_position = 0;
    this->array_position = 0;
    this->which_heap_in = placement::none;
}

Heap::Heap() {
    this->Clear();
}

unsigned int Heap::GetSize() {
    return this->size_;
}

void Heap::Clear() {
    this->queue_.clear();
    this->size_ = 0;
}

int Heap::GetParent(unsigned int index) const {
    if (this->size_ < 1) {
        return -1; // empty or root has no parent
    }
    return (static_cast<int> (index - 1) / 2);
}

int Heap::GetChild(unsigned int index) const {
    if (this->size_ <= 1 || 2 * (index + 1) > this->size_) {
        return -1; // empty or root has no child
    }
    return (2 * (index + 1));
}

int Heap::Find(unsigned int index, HeapElement *element) const {
    if (index + 1 > this->size_) {
        return -1; // base case: index out of bounds
    }
    if (element->value < this->queue_[index]->value) {
        return -1;   // base case: val not in min-heap
    }
    if (this->queue_[index]->value == element->value) {
        return index; // Found the value, return its index
    }

    int child_index = this->GetChild(index);
    int max_from_children = -1;

    if (child_index != -1) {
        max_from_children = std::max(this->Find(child_index, element),
                                     this->Find(child_index - 1, element));
    }

    return max_from_children;
}

void Heap::BubbleUp(int index) {
    int parent_index = this->GetParent(index);

    if (parent_index == -1 || parent_index == index) {
        return; // base case: root of heap
    }

    if (!this->Comparator(this->queue_[parent_index]->value,
                          this->queue_[index]->value)) {
        this->queue_[parent_index]->heap_position = index;
        this->queue_[index]->heap_position = parent_index;
        std::swap(this->queue_[parent_index], this->queue_[index]);
        this->BubbleUp(parent_index);
    }
}

void Heap::Insert(HeapElement *element) {
    element->heap_position = this->size_;
    this->queue_.push_back(element);
    this->BubbleUp(size_);
    this->size_++;
}

unsigned int Heap::GetMinimumIndex(unsigned int index_a,
                                   unsigned int index_b, unsigned int index_c) {
    bool left_smaller = this->Comparator
            (this->queue_[index_a]->value, this->queue_[index_b]->value);

    if (index_c >= (unsigned int) this->size_) {
        return left_smaller ? index_a : index_b;
    } else if (left_smaller) {
        return this->Comparator
                (this->queue_[index_a]->value, this->queue_[index_c]->value) ?
               index_a : index_c;
    } else {
        return this->Comparator
                (this->queue_[index_b]->value, this->queue_[index_c]->value) ?
               index_b : index_c;
    }
}

void Heap::BubbleDown(unsigned int index) {
    int child_index = this->GetChild(index);

    if (child_index == -1) {
        return; // base case: no children left
    }
    unsigned int minimum_index = this->GetMinimumIndex
            (index, child_index - 1, child_index);

    if (minimum_index != index) {
        this->queue_[minimum_index]->heap_position = index;
        this->queue_[index]->heap_position = minimum_index;
        std::swap(this->queue_[minimum_index], this->queue_[index]);
        this->BubbleDown(minimum_index);
    }
}

void Heap::Remove(HeapElement *element) {
    this->Remove(element->heap_position);
    element->which_heap_in = placement::none;
    element->heap_position = 0;
}

void Heap::Remove(unsigned int index) {
    --this->size_;
    this->queue_[index] = this->queue_[this->size_];
    this->queue_[index]->heap_position = index;
    this->queue_.resize(this->size_);
    this->BubbleDown(index);
    this->BubbleUp(index);
}

HeapElement *Heap::GetTopValue() {
    if (this->size_ == 0) {
        return nullptr;
    }
    return this->queue_[0];
}

bool HeapDesc::Comparator(unsigned int value_a, unsigned int value_b) {
    return value_a > value_b;
}

bool HeapAsc::Comparator(unsigned int value_a, unsigned int value_b) {
    return value_a < value_b;
}

SlidingStatistics::SlidingStatistics() {}

SlidingStatistics::~SlidingStatistics() {
    for (unsigned int iter = 0; iter < this->all_numbers_.size(); ++iter) {
        delete this->all_numbers_[iter];
    }
}

void SlidingStatistics::ReadNumbers(std::vector<unsigned int> numbers) {
    // pushing first number to Heap & adding other to array
    unsigned int iter, numbers_amount = numbers.size();
    this->all_numbers_.resize(numbers_amount);

    HeapElement *first_element = new HeapElement();
    first_element->value = numbers[0];
    first_element->array_position = 0;
    first_element->which_heap_in = placement::smallest_numbers;
    this->smallest_numbers_.Insert(first_element);
    this->all_numbers_[0] = first_element;

    this->iterator_right_ = 1;
    this->iterator_left_ = 0;

    for (iter = 1; iter < numbers_amount; ++iter) {
        this->all_numbers_[iter] = new HeapElement(numbers[iter]);
        this->all_numbers_[iter]->array_position = iter;
    }
}

void SlidingStatistics::SetOffset(unsigned int offset) {
    this->offset_ = offset;
}

std::vector<int> SlidingStatistics::MoveSlides(std::vector<bool> slide_right_point_array) {
    unsigned int slides_amount = slide_right_point_array.size();
    std::vector<int> result;
    HeapElement *tmp_value;

    for (unsigned int iter = 0; iter < slides_amount; ++iter) {
        // moving slide
        if (slide_right_point_array[iter]) {
            tmp_value = this->all_numbers_[this->iterator_right_];

            tmp_value->which_heap_in = placement::smallest_numbers;
            this->smallest_numbers_.Insert(tmp_value);

            while (this->smallest_numbers_.GetSize() >= this->offset_) {
                tmp_value = this->smallest_numbers_.GetTopValue();
                this->smallest_numbers_.Remove(tmp_value);

                tmp_value->which_heap_in = placement::non_allocated_numbers;
                this->non_allocated_numbers_.Insert(tmp_value);
            }
            ++this->iterator_right_;
        } else {
            tmp_value = this->all_numbers_[this->iterator_left_];

            if (tmp_value->which_heap_in == placement::non_allocated_numbers) {
                this->non_allocated_numbers_.Remove(tmp_value);
            } else if (tmp_value->which_heap_in == placement::smallest_numbers) {
                this->smallest_numbers_.Remove(tmp_value);

                if (this->non_allocated_numbers_.GetSize() > 0) {
                    tmp_value = this->non_allocated_numbers_.GetTopValue();
                    this->non_allocated_numbers_.Remove(tmp_value);

                    tmp_value->which_heap_in = placement::smallest_numbers;
                    this->smallest_numbers_.Insert(tmp_value);
                }
            } else {
                std::cout << "Error! Can't remove item " << tmp_value->value
                          << " - it's not locatted in any heap." << std::endl;
            }

            ++this->iterator_left_;
        }

        // getting the smallest number
        tmp_value = this->non_allocated_numbers_.GetTopValue();
        if (tmp_value && tmp_value->value) {
            result.push_back(tmp_value->value);
        } else {
            result.push_back(-1);
        }
    }

    return result;
}


inline void TestFile(std::string file_to_run = kTestFileA) {
    double elapsed;
    std::vector<int> result;
    std::vector<unsigned int> tmp_integers;
    std::vector<bool> tmp_bools;
    unsigned int numbers_amount, slides_amount;
    SlidingStatistics sliding_statistics;
    RFiler filer(file_to_run);

    tmp_integers = filer.ReadNumbers(3);
    numbers_amount = tmp_integers[0];
    slides_amount = tmp_integers[1];
    sliding_statistics.SetOffset(tmp_integers[2]);

    tmp_integers = filer.ReadNumbers(numbers_amount);
    tmp_bools = filer.ReadBools(slides_amount);

    std::cout << "Testing file '" << file_to_run << "'" << std::endl;
    auto begin = std::chrono::steady_clock::now();

    sliding_statistics.ReadNumbers(tmp_integers);
    result = sliding_statistics.MoveSlides(tmp_bools);

    std::cout << "Result:   " << std::endl;
    for (auto element : result) {
        std::cout << element << std::endl;
    }
    result.clear();

    elapsed = std::chrono::duration_cast<std::chrono::microseconds>
                      (std::chrono::steady_clock::now() - begin).count() * 0.000001;

    std::cout << "Expected: " << std::endl;
    filer.Read();
    filer.Close();

    std::cout << "Proccess finished in " << elapsed << " seconds." << std::endl;
}

inline void RunTest() {
    TestFile(kTestFileA);
    TestFile(kTestFileB);
    TestFile(kTestFileC);
    TestFile(kTestFileD);
    TestFile(kTestFileE);
}

int main(int argc, char *argv[]) {
    ReaderIo reader_io;
    RFiler filer;
    std::string file_name;
    std::vector<int> result;
    std::vector<unsigned int> tmp_integers;
    std::vector<bool> tmp_bools;
    unsigned int numbers_amount, slides_amount;
    SlidingStatistics sliding_statistics;

    std::ios_base::sync_with_stdio(false);

    if (argc == 1) {
        if (kUseIoByDefault) {
            tmp_integers = reader_io.ReadNumbers(3);
            numbers_amount = tmp_integers[0];
            slides_amount = tmp_integers[1];
            sliding_statistics.SetOffset(tmp_integers[2]);

            tmp_integers = reader_io.ReadNumbers(numbers_amount);
            tmp_bools = reader_io.ReadBools(slides_amount);
            sliding_statistics.ReadNumbers(tmp_integers);

            result = sliding_statistics.MoveSlides(tmp_bools);
            for (auto element : result) {
                std::cout << element << std::endl;
            }
        } else {
            RunTest();
        }
    } else {
        if (strcmp(argv[1], "--test") == 0) {
            RunTest();
        } else {
            if (strcmp(argv[1], "--file") == 0) {
                if (argc == 3) {
                    file_name = argv[2];
                } else {
                    file_name = kTestFileA;
                }
                filer.Open(file_name);
                tmp_integers = filer.ReadNumbers(3);
                numbers_amount = tmp_integers[0];
                slides_amount = tmp_integers[1];
                sliding_statistics.SetOffset(tmp_integers[2]);

                tmp_integers = filer.ReadNumbers(numbers_amount);
                tmp_bools = filer.ReadBools(slides_amount);
                filer.Close();
            } else if (strcmp(argv[1], "--io") == 0) {
                tmp_integers = reader_io.ReadNumbers(3);
                numbers_amount = tmp_integers[0];
                slides_amount = tmp_integers[1];
                sliding_statistics.SetOffset(tmp_integers[2]);

                tmp_integers = reader_io.ReadNumbers(numbers_amount);
                tmp_bools = reader_io.ReadBools(slides_amount);
            } else {
                std::cout << "No programm input specified." << std::endl;
                if (kStopConsoleProgramBeforeExit) {
                    std::cout << "Press enter to exit program.";
                    std::cin.get();
                }
                return 0;
            }

            sliding_statistics.ReadNumbers(tmp_integers);
            result = sliding_statistics.MoveSlides(tmp_bools);
            for (auto element : result) {
                std::cout << element << std::endl;
            }
        }
    }
    if (kStopConsoleProgramBeforeExit) {
        std::cout << "Press enter to exit program.";
        std::cin.get();
    }
    return 0;
}