/**
 * @file compact.hpp
 * @brief Memory-Efficient Representations for Gate5000
 *
 * ═══════════════════════════════════════════════════════════════════════════════
 * I. QUANTIZATION
 * ═══════════════════════════════════════════════════════════════════════════════
 *
 * INT8 QUANTIZATION:
 *   q = round((x - zero_point) / scale)
 *   x = q * scale + zero_point
 *
 * INT4 QUANTIZATION:
 *   4-bit weights packed 2 per byte
 *   16 levels: [-7, 7] or [0, 15]
 *
 * BINARY QUANTIZATION:
 *   w ∈ {-1, +1}
 *   sign(w) stored as single bit
 *
 * ═══════════════════════════════════════════════════════════════════════════════
 * II. SPARSE REPRESENTATIONS
 * ═══════════════════════════════════════════════════════════════════════════════
 *
 * CSR FORMAT:
 *   Compressed Sparse Row for matrices
 *
 * TOP-K SPARSITY:
 *   Only store k largest values
 *
 * BLOOM FILTERS:
 *   Probabilistic membership testing
 *
 * ═══════════════════════════════════════════════════════════════════════════════
 * III. COMPRESSION
 * ═══════════════════════════════════════════════════════════════════════════════
 *
 * DELTA ENCODING:
 *   Store differences from previous value
 *
 * RUN-LENGTH ENCODING:
 *   Compress repeated values
 *
 * HUFFMAN-LIKE:
 *   Variable-length coding for frequent values
 *
 * ═══════════════════════════════════════════════════════════════════════════════
 */

#pragma once

#include <cstdint>
#include <array>
#include <algorithm>
#include <cstring>
#include "constants.hpp"
#include "fast_math.hpp"

namespace mind_farm {
namespace compact {

// ═══════════════════════════════════════════════════════════════════════════════
// I. QUANTIZATION
// ═══════════════════════════════════════════════════════════════════════════════

/**
 * @brief INT8 quantization parameters
 */
struct QuantParams {
    float scale;
    float zero_point;
    float inv_scale;

    QuantParams() : scale(1.0f / 127.0f), zero_point(0.0f), inv_scale(127.0f) {}

    QuantParams(float min_val, float max_val) {
        scale = (max_val - min_val) / 254.0f;
        zero_point = min_val;
        inv_scale = fast::fast_rcp(scale);
    }
};

/**
 * @brief Quantize float to int8
 */
inline int8_t quantize_int8(float x, const QuantParams& p) {
    float scaled = (x - p.zero_point) * p.inv_scale;
    int val = static_cast<int>(scaled + 0.5f);
    return static_cast<int8_t>(std::max(-127, std::min(127, val)));
}

/**
 * @brief Dequantize int8 to float
 */
inline float dequantize_int8(int8_t q, const QuantParams& p) {
    return q * p.scale + p.zero_point;
}

/**
 * @brief INT8 quantized vector (16 elements, 16 bytes)
 */
struct QuantVec16 {
    alignas(16) std::array<int8_t, 16> data;
    QuantParams params;

    void quantize(const float* input) {
        // Find range
        float min_val = input[0], max_val = input[0];
        for (int i = 1; i < 16; ++i) {
            min_val = std::min(min_val, input[i]);
            max_val = std::max(max_val, input[i]);
        }
        params = QuantParams(min_val, max_val);

        // Quantize
        for (int i = 0; i < 16; ++i) {
            data[i] = quantize_int8(input[i], params);
        }
    }

    void dequantize(float* output) const {
        for (int i = 0; i < 16; ++i) {
            output[i] = dequantize_int8(data[i], params);
        }
    }

    /**
     * @brief Fast dot product (stays in int domain)
     */
    int32_t dot_int(const QuantVec16& other) const {
        int32_t sum = 0;
        for (int i = 0; i < 16; ++i) {
            sum += static_cast<int32_t>(data[i]) * static_cast<int32_t>(other.data[i]);
        }
        return sum;
    }

    /**
     * @brief Dot product with dequantization
     */
    float dot(const QuantVec16& other) const {
        int32_t isum = dot_int(other);
        return isum * params.scale * other.params.scale;
    }
};

/**
 * @brief INT4 quantized vector (16 elements, 8 bytes!)
 */
struct QuantVec16_Int4 {
    alignas(8) std::array<uint8_t, 8> data;  // 2 values per byte
    float scale;
    float zero_point;

    void quantize(const float* input) {
        // Find range
        float min_val = input[0], max_val = input[0];
        for (int i = 1; i < 16; ++i) {
            min_val = std::min(min_val, input[i]);
            max_val = std::max(max_val, input[i]);
        }
        scale = (max_val - min_val) / 15.0f;
        zero_point = min_val;
        float inv_scale = fast::fast_rcp(scale + 1e-10f);

        // Pack 2 values per byte
        for (int i = 0; i < 8; ++i) {
            int q0 = static_cast<int>((input[2*i] - zero_point) * inv_scale + 0.5f);
            int q1 = static_cast<int>((input[2*i+1] - zero_point) * inv_scale + 0.5f);
            q0 = std::max(0, std::min(15, q0));
            q1 = std::max(0, std::min(15, q1));
            data[i] = static_cast<uint8_t>((q0 << 4) | q1);
        }
    }

    void dequantize(float* output) const {
        for (int i = 0; i < 8; ++i) {
            output[2*i] = ((data[i] >> 4) & 0xF) * scale + zero_point;
            output[2*i+1] = (data[i] & 0xF) * scale + zero_point;
        }
    }

    // Size: 8 bytes data + 8 bytes params = 16 bytes total vs 64 bytes for float[16]
};

/**
 * @brief Binary quantized vector (16 elements, 2 bytes!)
 */
struct BinaryVec16 {
    uint16_t signs;  // Sign bits
    float magnitude; // Shared magnitude

    void quantize(const float* input) {
        signs = 0;
        magnitude = 0.0f;

        for (int i = 0; i < 16; ++i) {
            magnitude += fast::fast_abs(input[i]);
            if (input[i] >= 0) {
                signs |= (1u << i);
            }
        }
        magnitude /= 16.0f;
    }

    void dequantize(float* output) const {
        for (int i = 0; i < 16; ++i) {
            output[i] = (signs & (1u << i)) ? magnitude : -magnitude;
        }
    }

    /**
     * @brief Ultra-fast binary dot product (popcount)
     */
    float dot(const BinaryVec16& other) const {
        uint16_t xnor = ~(signs ^ other.signs);  // XNOR = same sign
        int same = __builtin_popcount(xnor);
        int diff = 16 - same;
        return magnitude * other.magnitude * (same - diff);
    }

    // Size: 2 bytes + 4 bytes = 6 bytes vs 64 bytes for float[16]!
};

// ═══════════════════════════════════════════════════════════════════════════════
// II. SPARSE REPRESENTATIONS
// ═══════════════════════════════════════════════════════════════════════════════

/**
 * @brief Sparse vector with top-k storage
 */
template<int K = 4>
struct SparseVec16 {
    std::array<uint8_t, K> indices;
    std::array<float, K> values;

    void from_dense(const float* input) {
        // Find top-k by magnitude
        std::array<std::pair<float, int>, 16> pairs;
        for (int i = 0; i < 16; ++i) {
            pairs[i] = {fast::fast_abs(input[i]), i};
        }
        std::partial_sort(pairs.begin(), pairs.begin() + K, pairs.end(),
                          [](auto& a, auto& b) { return a.first > b.first; });

        for (int i = 0; i < K; ++i) {
            indices[i] = static_cast<uint8_t>(pairs[i].second);
            values[i] = input[pairs[i].second];
        }
    }

    void to_dense(float* output) const {
        for (int i = 0; i < 16; ++i) {
            output[i] = 0.0f;
        }
        for (int i = 0; i < K; ++i) {
            output[indices[i]] = values[i];
        }
    }

    float dot(const SparseVec16<K>& other) const {
        float sum = 0.0f;
        for (int i = 0; i < K; ++i) {
            for (int j = 0; j < K; ++j) {
                if (indices[i] == other.indices[j]) {
                    sum += values[i] * other.values[j];
                }
            }
        }
        return sum;
    }

    // Size: K bytes + K*4 bytes = 5K bytes (K=4: 20 bytes vs 64)
};

/**
 * @brief Bloom filter for set membership (64-bit, ~4% false positive)
 */
struct BloomFilter64 {
    uint64_t bits;
    static constexpr int K = 4;  // Number of hash functions

    BloomFilter64() : bits(0) {}

    uint64_t hash(uint32_t x, int seed) const {
        x ^= seed * 0x9E3779B9;
        x = ((x >> 16) ^ x) * 0x45d9f3b;
        x = ((x >> 16) ^ x) * 0x45d9f3b;
        return (x >> 16) ^ x;
    }

    void add(uint32_t item) {
        for (int i = 0; i < K; ++i) {
            bits |= (1ULL << (hash(item, i) & 63));
        }
    }

    bool maybe_contains(uint32_t item) const {
        for (int i = 0; i < K; ++i) {
            if (!(bits & (1ULL << (hash(item, i) & 63)))) {
                return false;
            }
        }
        return true;
    }

    void clear() { bits = 0; }
    int count() const { return __builtin_popcountll(bits); }
};

// ═══════════════════════════════════════════════════════════════════════════════
// III. COMPRESSION
// ═══════════════════════════════════════════════════════════════════════════════

/**
 * @brief Delta-encoded vector
 */
struct DeltaVec16 {
    float base;
    std::array<int8_t, 15> deltas;  // 15 deltas (first value is base)
    float scale;

    void encode(const float* input) {
        base = input[0];

        // Find max delta for scaling
        float max_delta = 0.0f;
        for (int i = 1; i < 16; ++i) {
            max_delta = std::max(max_delta, fast::fast_abs(input[i] - input[i-1]));
        }
        scale = max_delta / 127.0f;
        float inv_scale = fast::fast_rcp(scale + 1e-10f);

        // Encode deltas
        for (int i = 1; i < 16; ++i) {
            float delta = input[i] - input[i-1];
            int q = static_cast<int>(delta * inv_scale + 0.5f);
            deltas[i-1] = static_cast<int8_t>(std::max(-127, std::min(127, q)));
        }
    }

    void decode(float* output) const {
        output[0] = base;
        for (int i = 1; i < 16; ++i) {
            output[i] = output[i-1] + deltas[i-1] * scale;
        }
    }

    // Size: 4 + 15 + 4 = 23 bytes (vs 64)
};

/**
 * @brief Run-length encoded binary vector (for sparse binary patterns)
 */
struct RLEBinary {
    std::array<uint8_t, 16> runs;  // Alternating run lengths
    uint8_t num_runs;
    bool starts_with_one;

    void encode(const uint64_t* state, size_t num_words) {
        num_runs = 0;
        uint8_t current_run = 0;
        bool current_bit = (state[0] & 1);
        starts_with_one = current_bit;

        for (size_t w = 0; w < num_words && num_runs < 16; ++w) {
            for (int b = 0; b < 64 && num_runs < 16; ++b) {
                bool bit = (state[w] >> b) & 1;
                if (bit == current_bit) {
                    if (current_run < 255) ++current_run;
                } else {
                    runs[num_runs++] = current_run;
                    current_bit = bit;
                    current_run = 1;
                }
            }
        }
        if (num_runs < 16) {
            runs[num_runs++] = current_run;
        }
    }

    // Useful for compressing sparse activation patterns
};

// ═══════════════════════════════════════════════════════════════════════════════
// IV. COMPACT WEIGHT MATRICES
// ═══════════════════════════════════════════════════════════════════════════════

/**
 * @brief Compact 16x16 matrix using int8 quantization (256 bytes vs 1024)
 */
struct CompactMatrix16x16 {
    alignas(64) std::array<int8_t, 256> data;
    QuantParams row_params[16];  // Per-row quantization

    void quantize(const float* input) {
        for (int i = 0; i < 16; ++i) {
            // Find row range
            float min_val = input[i * 16], max_val = input[i * 16];
            for (int j = 1; j < 16; ++j) {
                min_val = std::min(min_val, input[i * 16 + j]);
                max_val = std::max(max_val, input[i * 16 + j]);
            }
            row_params[i] = QuantParams(min_val, max_val);

            // Quantize row
            for (int j = 0; j < 16; ++j) {
                data[i * 16 + j] = quantize_int8(input[i * 16 + j], row_params[i]);
            }
        }
    }

    /**
     * @brief Matrix-vector multiply with dequantization
     */
    void matvec(const float* x, float* y) const {
        for (int i = 0; i < 16; ++i) {
            int32_t sum = 0;
            for (int j = 0; j < 16; ++j) {
                // Approximate: assume x is roughly in [-1, 1]
                sum += static_cast<int32_t>(data[i * 16 + j]) *
                       static_cast<int32_t>(x[j] * 127.0f);
            }
            y[i] = sum * row_params[i].scale / 127.0f + row_params[i].zero_point;
        }
    }

    // Size: 256 + 16*8 = 384 bytes (vs 1024 for float)
};

/**
 * @brief Ultra-compact binary matrix (256 bits = 32 bytes!)
 */
struct BinaryMatrix16x16 {
    std::array<uint16_t, 16> rows;  // Each row is 16 bits

    void from_signs(const float* input) {
        for (int i = 0; i < 16; ++i) {
            rows[i] = 0;
            for (int j = 0; j < 16; ++j) {
                if (input[i * 16 + j] >= 0) {
                    rows[i] |= (1u << j);
                }
            }
        }
    }

    /**
     * @brief Binary matrix-vector multiply (XNOR + popcount)
     */
    void matvec_binary(uint16_t x_signs, int8_t* y) const {
        for (int i = 0; i < 16; ++i) {
            uint16_t xnor = ~(rows[i] ^ x_signs);
            int same = __builtin_popcount(xnor);
            y[i] = static_cast<int8_t>(2 * same - 16);  // Range: [-16, 16]
        }
    }

    // Size: 32 bytes (vs 1024 for float!)
};

// ═══════════════════════════════════════════════════════════════════════════════
// V. MEMORY POOL FOR COMPACT ALLOCATIONS
// ═══════════════════════════════════════════════════════════════════════════════

/**
 * @brief Simple bump allocator for compact structures
 */
template<size_t SIZE = 4096>
struct CompactPool {
    alignas(64) std::array<uint8_t, SIZE> data;
    size_t offset;

    CompactPool() : offset(0) {}

    void* alloc(size_t bytes, size_t align = 8) {
        // Align offset
        offset = (offset + align - 1) & ~(align - 1);
        if (offset + bytes > SIZE) return nullptr;
        void* ptr = &data[offset];
        offset += bytes;
        return ptr;
    }

    template<typename T>
    T* alloc_type() {
        return static_cast<T*>(alloc(sizeof(T), alignof(T)));
    }

    void reset() { offset = 0; }
    size_t used() const { return offset; }
    size_t available() const { return SIZE - offset; }
};

} // namespace compact
} // namespace mind_farm