#include <iostream>
#include <sys/ipc.h>
#include <sys/shm.h>
#include <sys/wait.h>
#include <sys/time.h>
#include <unistd.h>
#include <ctime>
#include <iomanip>
#include <random>
#include <sstream>

constexpr int NIL = -1; // маркер пустого указателя
constexpr int MAX_PROCS = 1024; // лимит ячеек для результатов

struct Node {
    int value;
    int next; // индекс следующего узла
};

struct SharedData {
    int head; // индекс начала списка
    int results[MAX_PROCS]; // таблица для возврата индексов от потомков
    Node nodes[1]; // массив узлов в памяти
};

// получение текущего времени для логов
std::string now() {
    timeval tv{};
    gettimeofday(&tv, nullptr);
    std::ostringstream oss;
    oss << tv.tv_sec << "." << std::setfill('0') << std::setw(6) << tv.tv_usec;
    return oss.str();
}

// логирование старта процесса
void log_start(int head, int depth) {
    std::cout << "PROC_START pid=" << getpid()
              << " ppid=" << getppid()
              << " depth=" << depth
              << " l=" << head
              << " r=0"
              << " ts=" << now()
              << '\n' << std::flush;
}

// логирование завершения процесса
void log_end(int head, int depth) {
    std::cout << "PROC_END pid=" << getpid()
              << " ppid=" << getppid()
              << " depth=" << depth
              << " l=" << head
              << " r=0"
              << " ts=" << now()
              << '\n' << std::flush;
}

// слияние двух отсортированных списков
int merge_lists(Node* pool, int left_head, int right_head) {
    if (left_head == NIL) return right_head;
    if (right_head == NIL) return left_head;

    int res_head = NIL;
    int tail = NIL;

    // лямбда для добавления узла в хвост
    auto append = [&](int node_idx) {
        if (res_head == NIL) {
            res_head = node_idx;
            tail = node_idx;
        } else {
            pool[tail].next = node_idx;
            tail = node_idx;
        }
    };

    while (left_head != NIL && right_head != NIL) {
        if (pool[left_head].value <= pool[right_head].value) {
            int next = pool[left_head].next;
            append(left_head);
            left_head = next;
        } else {
            int next = pool[right_head].next;
            append(right_head);
            right_head = next;
        }
    }
    if (left_head != NIL) pool[tail].next = left_head;
    if (right_head != NIL) pool[tail].next = right_head;
    return res_head;
}

// разделение списка пополам (черепаха и заяц)
void split_list(Node* pool, int head, int& left, int& right) {
    if (head == NIL || pool[head].next == NIL) {
        left = head;
        right = NIL;
        return;
    }
    int slow = head;
    int fast = pool[head].next;
    while (fast != NIL) {
        fast = pool[fast].next;
        if (fast != NIL) {
            slow = pool[slow].next;
            fast = pool[fast].next;
        }
    }
    left = head;
    right = pool[slow].next;
    pool[slow].next = NIL; // разрыв связи
}

// обычная рекурсивная сортировка в одном процессе
int local_list_sort(Node* pool, int head) {
    if (head == NIL || pool[head].next == NIL) return head;
    int left, right;
    split_list(pool, head, left, right);
    left = local_list_sort(pool, left);
    right = local_list_sort(pool, right);
    return merge_lists(pool, left, right);
}

// параллельная сортировка через fork
int parallel_list_sort(SharedData* data, int head, int depth, int max_depth, int proc_idx) {
    log_start(head, depth);

    if (head == NIL || data->nodes[head].next == NIL) {
        log_end(head, depth);
        return head;
    }

    // если глубина достигнута, сортируем локально
    if (depth >= max_depth) {
        int result = local_list_sort(data->nodes, head);
        log_end(result, depth);
        return result;
    }

    int left_part, right_part;
    split_list(data->nodes, head, left_part, right_part);

    // индексы для записи результатов в массив shm
    int left_child_idx = 2 * proc_idx + 1;
    int right_child_idx = 2 * proc_idx + 2;

    pid_t pid_l = fork();
    if (pid_l == 0) {
        int res = parallel_list_sort(data, left_part, depth + 1, max_depth, left_child_idx);
        data->results[left_child_idx] = res; // запись головы в общую память
        _exit(0);
    }

    pid_t pid_r = fork();
    if (pid_r == 0) {
        int res = parallel_list_sort(data, right_part, depth + 1, max_depth, right_child_idx);
        data->results[right_child_idx] = res; // запись головы в общую память
        _exit(0);
    }

    // ждем завершения обоих детей
    waitpid(pid_l, nullptr, 0);
    waitpid(pid_r, nullptr, 0);

    // читаем головы отсортированных частей из памяти
    int sorted_l = data->results[left_child_idx];
    int sorted_r = data->results[right_child_idx];

    int final_head = merge_lists(data->nodes, sorted_l, sorted_r);
    log_end(final_head, depth);
    return final_head;
}

int main(int argc, char* argv[]) {
    int n = 10000;
    int max_depth = 3;
    if (argc > 1) n = std::atoi(argv[1]);
    if (argc > 2) max_depth = std::atoi(argv[2]);

    // создание сегмента разделяемой памяти
    size_t shm_size = sizeof(SharedData) + sizeof(Node) * (n - 1);
    int shmid = shmget(IPC_PRIVATE, shm_size, IPC_CREAT | 0666);
    SharedData* data = (SharedData*)shmat(shmid, nullptr, 0);

    // зачистка таблицы результатов
    for(int i = 0; i < MAX_PROCS; ++i) data->results[i] = NIL;

    data->head = 0;
    std::mt19937 rng(time(0));
    std::uniform_int_distribution<int> dist(0, 999);

    // заполнение списка случайными числами
    for (int i = 0; i < n; ++i) {
        data->nodes[i].value = dist(rng);
        data->nodes[i].next = (i == n - 1) ? NIL : i + 1;
    }

    // запуск параллельной сортировки (корень — индекс 0)
    data->head = parallel_list_sort(data, data->head, 0, max_depth, 0);

    // вывод результата
    std::cout << "\nSorted list (first 20 elements): ";
    int curr = data->head;
    for(int i = 0; i < 20 && curr != NIL; ++i) {
        std::cout << data->nodes[curr].value << " ";
        curr = data->nodes[curr].next;
    }
    std::cout << std::endl;

    // отсоединение и удаление памяти
    shmdt(data);
    shmctl(shmid, IPC_RMID, nullptr);
    return 0;
}