#pragma warning(disable:4820)
#pragma warning(disable:4668)
#pragma warning(disable:4514)
#pragma warning(disable:4710)
#include <conio.h>
#include <iostream>
// *******************************************************
#include <string>

char bit_extract(char const& byte, unsigned int const& index) {         // Extracts the bit from the byte "byte" at the position "index".
    return ( (char) ( (unsigned int)byte << (24 + index) >> 31 ) );
}

void bit_flip(char & byte, unsigned int const& index) {             // Flips the bit from the byte "byte" at the position "index".
    byte ^= 0x0080 >> index;
}

void swap(unsigned int & left, unsigned int & right) {
    /*
    left += right;
    right = left - right;
    left -= right;
    */
    left -= right = (left += right) - right;                // This crazy one-liner is equivalent with the previous 3 lines (that are commented).
}

void array_sort_increasing(unsigned int *arr, unsigned int const& length) {
    for (unsigned int left = 0; left <= length - 2; ++left) {
        for (unsigned right = left + 1; right <= length - 1; ++right) {
            if (arr[left] > arr[right]) {               // If comparation is true.
                swap(arr[left], arr[right]);            // Than arr[right] is the new minimum.
            }
        }
    }
}

void bit_insert(char &byte, unsigned int const &index, char const &BitVal) {    // Inserts the bit "BitVal" into the byte "byte" at the position "index".
    if (BitVal == 0) {
        byte &= 0xFF7F >> index;
    }
    else if (BitVal == 1) {
        byte |= 0x0080 >> index;
    }
}

void perfect_encode(std::string const& message, std::string & result, unsigned int const& input_bits_number) {  // Bit i from "message" is gonna flip all bits from closed range: [i; i + half] from "result".
    unsigned int is_range_odd = 0;                      // The range, from input, is of the form [i; i + half]. If this range is odd, than the bit, from output, on position (i + half) is gonna be flipped.
    unsigned int const half_position = input_bits_number / 2;
    for (unsigned int index = 0; index <= half_position; ++index) {
        if (bit_extract(message[index / 8], index % 8)) {
            is_range_odd = is_range_odd ^ 0x01;
        }
    }
    if (is_range_odd) {
        bit_flip(result[half_position / 8], half_position % 8);
    }

    char LeftFromPair_VALUE, RightFromPair_VALUE;               // The pairs are of the form { i ; i + (half + 1) }.
    unsigned int RightFromPair_POSITION = half_position + 1;
    unsigned int LeftFromPair_POSITION;

    while (RightFromPair_POSITION != half_position) {
        RightFromPair_VALUE = bit_extract(message[RightFromPair_POSITION / 8], RightFromPair_POSITION % 8);
        LeftFromPair_POSITION = ((RightFromPair_POSITION - (half_position + 1)) + input_bits_number) % input_bits_number;
        LeftFromPair_VALUE = bit_extract(message[LeftFromPair_POSITION / 8], LeftFromPair_POSITION % 8);

        if (LeftFromPair_VALUE != RightFromPair_VALUE) {        // When we move, inside input, from 1 range to the next range: we replace LeftFromPair_VALUE with RightFromPair_VALUE.
            is_range_odd = is_range_odd ^ 0x01;
        }
        if (is_range_odd) {
            bit_flip(result[RightFromPair_POSITION / 8], RightFromPair_POSITION % 8);
        }
        RightFromPair_POSITION = (RightFromPair_POSITION + 1) % input_bits_number;
    }
}

void perfect_decode(std::string const& output, std::string & input, unsigned int const& input_bits_number) {
    input.resize(0);
    unsigned int *FirstTeam = new unsigned int[input_bits_number];
    FirstTeam[0] = 0;
    unsigned int FirstTeam_COUNTER = 1;
    bool previous_InputBit_position_TEAM = 0;
    unsigned int *SecondTeam = new unsigned int[input_bits_number - 1];
    unsigned int SecondTeam_COUNTER = 0;
    unsigned int const half_position_plus_one = input_bits_number / 2 + 1;
    unsigned int InputBit_position = half_position_plus_one;
    while (InputBit_position) {
        char OutputBit_value = bit_extract(output[InputBit_position / 8], InputBit_position % 8);
        char PREV_OutputBit_value = bit_extract(output[(InputBit_position - 1) / 8], (InputBit_position - 1) % 8);

        if (OutputBit_value == PREV_OutputBit_value) {
            if (previous_InputBit_position_TEAM == 0) {
                FirstTeam[FirstTeam_COUNTER] = InputBit_position;
                ++FirstTeam_COUNTER;
            }
            else {
                SecondTeam[SecondTeam_COUNTER] = InputBit_position;
                ++SecondTeam_COUNTER;
            }
        }
        else {                              // OutputBit_value != PREV_OutputBit_value .
            if (previous_InputBit_position_TEAM == 0) {
                SecondTeam[SecondTeam_COUNTER] = InputBit_position;
                ++SecondTeam_COUNTER;
                previous_InputBit_position_TEAM = 1;
            }
            else {
                FirstTeam[FirstTeam_COUNTER] = InputBit_position;
                ++FirstTeam_COUNTER;
                previous_InputBit_position_TEAM = 0;
            }
        }

        InputBit_position = (InputBit_position + half_position_plus_one) % input_bits_number;
    }   // END while.
    std::cout << "FirstTeam: ";
    for (unsigned int i = 0; i < FirstTeam_COUNTER; ++i) {
        std::cout << FirstTeam[i] << " ";
    }
    std::cout << "\nSecondTeam: ";
    for (unsigned int i = 0; i < SecondTeam_COUNTER; ++i) {
        std::cout << SecondTeam[i] << " ";
    }
    /*
    std::cout << "\nAfter sorting ###\n";
    array_sort_increasing(FirstTeam, FirstTeam_COUNTER);            // Sorting is NOT necessary !
    array_sort_increasing(SecondTeam, SecondTeam_COUNTER);          // idem.
    std::cout << "FirstTeam: ";
    for (unsigned int i = 0; i < FirstTeam_COUNTER; ++i) {
        std::cout << FirstTeam[i] << " ";
    }
    std::cout << "\nSecondTeam: ";
    for (unsigned int i = 0; i < SecondTeam_COUNTER; ++i) {
        std::cout << SecondTeam[i] << " ";
    }
    */
    std::cout << "\n\n";
    char belongs_first_InputRange = 0;
    for (unsigned int i = 0; i < FirstTeam_COUNTER; ++i) {
        if (FirstTeam[i] < half_position_plus_one) {            // If element 'i' from "FirstTeam" belongs inside [0 ; half_position] closed range (from input/message).
            belongs_first_InputRange ^= 0x01;
        }
    }
    char output_half_position_VALUE = bit_extract(output[(half_position_plus_one - 1) / 8], (half_position_plus_one - 1) % 8);
    input.resize(input_bits_number / 8);

    if (output_half_position_VALUE == belongs_first_InputRange) {
        std::cout << "FirstTeam is bit 1\n";
        std::cout << "SecondTeam is bit 0\n";
        for (unsigned int i = 0; i < FirstTeam_COUNTER; ++i) {
            bit_insert(input[FirstTeam[i] / 8], FirstTeam[i] % 8, 1);       // insert '1' for each bit position from first team.
        }
        for (unsigned int i = 0; i < SecondTeam_COUNTER; ++i) {
            bit_insert(input[SecondTeam[i] / 8], SecondTeam[i] % 8, 0);     // insert '0' for each bit position from second team.
        }
    }
    else {
        std::cout << "FirstTeam is bit 0\n";
        std::cout << "SecondTeam is bit 1\n";
        for (unsigned int i = 0; i < FirstTeam_COUNTER; ++i) {
            bit_insert(input[FirstTeam[i] / 8], FirstTeam[i] % 8, 0);       // insert '0' for each bit position from first team.
        }
        for (unsigned int i = 0; i < SecondTeam_COUNTER; ++i) {             // insert '1' for each bit position from second team.
            bit_insert(input[SecondTeam[i] / 8], SecondTeam[i] % 8, 1);
        }
    }

    delete[] FirstTeam;
    delete[] SecondTeam;
}

int main() {
    std::cout << "no of bits inside input = ";
    unsigned int input_bits_number;
    std::cin >> input_bits_number;                      // "input_bits_number" must be: (power of 2) bits  AND at least 8 bits.
    unsigned int const letter_no = input_bits_number / 8;
    std::string message, result;
    message.resize(letter_no);
    result.resize(letter_no);
    message[0] = static_cast<unsigned char>(0x62);
    message[1] = static_cast<unsigned char>(0x1c);
    message[2] = static_cast<unsigned char>(0x7c);
    message[3] = static_cast<unsigned char>(0x76);
    for (unsigned int i = 0; i < letter_no; ++i) {
        result[i] = '\0';                       // '\0' <=> 0 <=> NULL.
    }
    perfect_encode(message, result, input_bits_number);
    std::cout << "result: " << std::hex;
    for (unsigned int i = 0; i < letter_no; ++i) {
        if (static_cast<unsigned char>(result[i]) < 16) {
            std::cout << '0';
        }
        std::cout << (int)static_cast<unsigned char>(result[i]);
    }
    std::cout << std::dec << '\n';
    // -------------------------------------------------------      END ENcoding.
    for (unsigned int i = 0; i < letter_no; ++i) {
        message[i] = NULL;
    }
    perfect_decode(result, message, input_bits_number);
    std::cout << "back to message: " << std::hex;
    for (unsigned int i = 0; i < letter_no; ++i) {
        if (static_cast<unsigned char>(message[i]) < 16) {
            std::cout << "0";
        }
        std::cout << (int)static_cast<unsigned char>(message[i]);
    }
    std::cout << std::dec << '\n';
    // -------------------------------------------------------      END DEcoding.
    std::cout << "\n\nWaiting for any Key ...\n";
    _getch();
}