open-standards/wai/wai-vector/tests/canonical.rs

//! §2.5: one encoding per scene. Every payload the parser reads back writes the same
//! bytes, the authoring form round-trips, and duplicates are found by sorting.

use std::cell::Cell;
use std::cmp::Ordering;

use wai_vector::vectors::all_vectors;
use wai_vector::wvg1::{self, Doc, Key, Track, cmp_tracks, has_duplicate};
use wai_vector::{form, wos1};

#[test]
fn canonical_round_trip_on_every_vector() {
    let (mut n, mut forms) = (0, 0);
    for v in all_vectors() {
        match v.ext {
            "wvg1" => {
                // Every payload the form can split goes to the form and back unchanged.
                let f = form::to_json(&v.bytes, "");
                assert_eq!(form::to_bytes(&f).as_deref(), Ok(&v.bytes[..]), "{}: form round trip", v.name);
                forms += 1;
                if let Ok(d) = wvg1::parse(&v.bytes) {
                    assert_eq!(d.write(), v.bytes, "{}: parse then write", v.name);
                    n += 1;
                }
            }
            "wos1" => {
                if let Ok(w) = wos1::parse(&v.bytes) {
                    assert_eq!(w.write(), v.bytes, "{}: parse then write", v.name);
                    n += 1;
                }
            }
            _ => {}
        }
    }
    assert!(n > 25 && forms > 200, "{n} round trips, {forms} forms");
}

/// Review A's F10 shape: 65,535 tracks of 64 keys, equal but for the last key, in a
/// fixed shuffle. Detection sorts, so it compares at most 2·n·⌈log2 n⌉ times, never
/// every pair (about 2^31).
#[test]
fn duplicates_by_sorting_comparison_count() {
    let n = 65_535usize;
    let k = 64u32;
    let mut order: Vec<u32> = (0..n as u32).collect();
    let mut s = 0x9E37_79B9_7F4A_7C15u64;
    for i in (1..n).rev() {
        s ^= s << 13;
        s ^= s >> 7;
        s ^= s << 17;
        order.swap(i, (s % (i as u64 + 1)) as usize);
    }
    let mut d = Doc::default();
    for &v in &order {
        d.tracks.push(Track { kind: 2, zero1: 0, zero2: 0, n_keys: k });
        for j in 0..k {
            let value = if j + 1 == k { v as i32 } else { 0 };
            d.keys.push(Key { t: j, value, interp: 0, zero: [0; 3] });
        }
    }
    d.index();
    let bound = 2 * n as u64 * u64::from(usize::BITS - (n - 1).leading_zeros());
    assert_eq!(bound, 2 * 65_535 * 16);
    let count = Cell::new(0u64);
    let cmp = |a: usize, b: usize| -> Ordering {
        count.set(count.get() + 1);
        assert!(count.get() <= bound, "more than {bound} comparisons");
        cmp_tracks(&d, a, b)
    };
    assert!(!has_duplicate(n, cmp), "no two tracks are equal");
    assert!(count.get() <= bound);
    eprintln!("{n} tracks: {} comparisons, bound {bound}, pairs {}", count.get(), n as u64 * (n as u64 - 1) / 2);
    // Two equal tracks are found within the same bound.
    let last = d.ix.track_key0[n - 1] as usize + k as usize - 1;
    let other = d.ix.track_key0[n - 2] as usize + k as usize - 1;
    d.keys[last].value = d.keys[other].value;
    count.set(0);
    let cmp = |a: usize, b: usize| -> Ordering {
        count.set(count.get() + 1);
        assert!(count.get() <= bound, "more than {bound} comparisons");
        cmp_tracks(&d, a, b)
    };
    assert!(has_duplicate(n, cmp), "the two equal tracks are found");
}