overclocked_sort 0.2.1

use overclocked_sort::{overclocked_kp_sort, KeyPtr};
use std::time::Instant;

#[derive(Clone, Eq, PartialEq)]
pub struct MonsterStruct {
    pub tier: u16,      // 0 - 500
    pub power: u16,     // 0 - 2000
    pub padding: [u64; 4], // Mô phỏng dữ liệu nặng (Payload 32 bytes)
}

struct Lcg { seed: u64 }
impl Lcg {
    fn next(&mut self) -> u32 {
        self.seed = self.seed.wrapping_mul(6364136223846793005).wrapping_add(1);
        (self.seed >> 32) as u32
    }
}

fn main() {
    let n = 5_000_000;
    println!("=== SO SÁNH: HÀM CMP (CỬA TẮT O(N log N)) VÀ PACKED KEY (O(N + M)) ===\n");
    
    let mut rng = Lcg { seed: 101010 };
    let mut data = Vec::with_capacity(n);
    for _ in 0..n {
        data.push(MonsterStruct {
            tier: (rng.next() % 500) as u16,
            power: (rng.next() % 2000) as u16,
            padding: [0, 0, 0, 0],
        });
    }

    let mut d_cmp = data.clone();
    let d_key = data.clone(); // Không cần mut rải rác vì Overclock tạo bản sao gián tiếp
    
    // =========================================================================
    // PHƯƠNG ÁN 1 (ĐI CỬA TẮT): Dùng hàm Compare tùy ý -> Uỷ quyền O(N log N)
    // =========================================================================
    // Bản chất của hàm CMP (a < b) là nó không cho ta biết "Khoảng cách M" là bao nhiêu.
    // Toán học không cho phép lập Histogram (Bộ đếm) chỉ từ phép (<, >, =).
    // Nên "Cửa tắt thông minh nhất" là quăng thẳng cho Pattern-Defeating Quicksort.
    println!("▶ 1. Phương án CMP: Đi cửa tắt bằng PDQ-Sort O(N log N) In-place");
    let start = Instant::now();
    // Hàm cmp() đầy đủ:
    d_cmp.sort_unstable_by(|a, b| {
        a.tier.cmp(&b.tier).then(a.power.cmp(&b.power))
    });
    let elapsed_cmp = start.elapsed();
    println!("⏱ Thời gian (CMP Shortcut): {:?}", elapsed_cmp);


    // =========================================================================
    // PHƯƠNG ÁN 2: Ép xung - Gộp Packed Key (32-bit) + Trích xuất mảng chỉ mục (Double Indirection)
    // =========================================================================
    // Thay vì Sort vác cả bộ Struct 40-Bytes đi đổi chỗ, ta lật bài "Rút thẻ căn cước"
    println!("\n▶ 2. Phương án KeyPtr: Trích xuất Packed Key -> Overclocked Sort -> Reconstruct");
    let start = Instant::now();
    
    // Bước 2.1: Phân mảnh ID (Trích xuất thẻ bài chỉ nặng 16 Bytes)
    let max_val = (500 << 16) | 2000; // max_val ~ 32.000.000 (32 Triệu - Vẫn an toàn cho RAM)
    let mut key_pointers = Vec::with_capacity(n);
    for (i, item) in d_key.iter().enumerate() {
        let packed_key = ((item.tier as i32) << 16) | (item.power as i32);
        key_pointers.push(KeyPtr {
            key: packed_key,
            ptr: i as u64, // Nhớ ID gốc
        });
    }

    // Bước 2.2: Đưa dàn thẻ bài siêu nhẹ vào lò phản ứng L2-Cache O(N + M)
    let sorted_kps = overclocked_kp_sort(&key_pointers, max_val as usize);

    // Bước 2.3: Reconstruct (Tái tạo lại mảng kết quả bằng cách đọc chéo RAM theo Pointer)
    let mut result_ovc = Vec::with_capacity(n);
    for kp in sorted_kps.iter() {
        // clone() payload từ Index gốc
        result_ovc.push(d_key[kp.ptr as usize].clone());
    }
    let elapsed_ovc_key = start.elapsed();
    
    println!("⏱ Thời gian (Overclocked KeyPtr + Reconstruct): {:?}", elapsed_ovc_key);
    
    // Kiểm định chéo xem Hai phương pháp có ra đúng 1 kết quả không
    assert_eq!(d_cmp[444].tier, result_ovc[444].tier);
    assert_eq!(d_cmp[444].power, result_ovc[444].power);
    
    println!("\n=================================");
    println!("⭐ Nhận xét:");
    if elapsed_cmp < elapsed_ovc_key {
        println!("🚀 O(N log N) Bằng hàm CMP đã chiến thắng nhờ Không tốn chi phí Copy/Reconstruct!");
    } else {
        println!("🚀 Kiến trúc đếm O(N) KeyPtr đã đè bẹp CMP bất chấp chi phí Reconstruct!");
    }
}