module huffman

// The worked example from RFC 1951 §3.2.2: symbols A..H with these lengths
// produce these exact canonical (MSB-first) codes.
fn test_rfc1951_canonical_example() {
	lengths := [3, 3, 3, 3, 3, 2, 4, 4] // A B C D E F G H
	t := build(lengths: lengths, max_bits: 4, bit_order: .msb_first)!
	expected := [u32(0b010), 0b011, 0b100, 0b101, 0b110, 0b00, 0b1110, 0b1111]
	assert t.codes == expected
	assert t.lengths == lengths
	assert t.max_bits == 4
}

fn test_lsb_first_reverses_each_code() {
	lengths := [3, 3, 3, 3, 3, 2, 4, 4]
	msb := build(lengths: lengths, max_bits: 4, bit_order: .msb_first)!
	lsb := build(lengths: lengths, max_bits: 4, bit_order: .lsb_first)!
	// Each LSB code is the MSB code bit-reversed within its length.
	for sym, l in lengths {
		assert lsb.codes[sym] == bit_reverse(msb.codes[sym], l)
	}
	// e.g. F (len 2, code 00) is unchanged; A (len 3, 010) -> 010 reversed.
	assert lsb.codes[5] == 0b00
	assert lsb.codes[0] == 0b010 // 010 reversed is still 010
	assert lsb.codes[6] == bit_reverse(u32(0b1110), 4) // 1110 -> 0111
}

fn test_flat_table_round_trips_lsb() {
	lengths := [3, 3, 3, 3, 3, 2, 4, 4]
	t := build(lengths: lengths, max_bits: 4, bit_order: .lsb_first)!
	table := flat_table(lengths: lengths, max_bits: 4, bit_order: .lsb_first)!
	assert table.len == 1 << 4
	// Every symbol must decode back from its code in every don't-care variant.
	for sym, l in lengths {
		step := 1 << l
		mut idx := int(t.codes[sym])
		for idx < table.len {
			entry := table[idx]
			assert entry != flat_invalid_entry
			assert int(entry & ((u32(1) << flat_length_bits) - 1)) == l
			assert int(entry >> flat_length_bits) == sym
			idx += step
		}
	}
}

fn test_flat_table_round_trips_msb() {
	// MSB-first flat table: a code of length l fills the contiguous block whose
	// high l bits equal the code (the low max_bits-l bits are don't-cares).
	lengths := [3, 3, 3, 3, 3, 2, 4, 4]
	t := build(lengths: lengths, max_bits: 4, bit_order: .msb_first)!
	table := flat_table(lengths: lengths, max_bits: 4, bit_order: .msb_first)!
	assert table.len == 1 << 4
	for sym, l in lengths {
		block := 1 << (t.max_bits - l)
		base := int(t.codes[sym]) * block
		for k in 0 .. block {
			entry := table[base + k]
			assert entry != flat_invalid_entry
			assert int(entry & ((u32(1) << flat_length_bits) - 1)) == l
			assert int(entry >> flat_length_bits) == sym
		}
	}
}

fn test_flat_table_incomplete_marks_gaps() {
	// A single length-1 code under-subscribes a 2-bit table: half the indices
	// belong to no code and must read back as flat_invalid_entry. This is the
	// path the complete-code fast path must NOT take.
	table := flat_table(lengths: [1], max_bits: 2, bit_order: .lsb_first)!
	assert table.len == 4
	// code 0, len 1, lsb stride 2 -> indices 0 and 2 are the symbol; 1 and 3 gaps.
	assert int(table[0] >> flat_length_bits) == 0
	assert int(table[0] & ((u32(1) << flat_length_bits) - 1)) == 1
	assert table[2] == table[0]
	assert table[1] == flat_invalid_entry
	assert table[3] == flat_invalid_entry
}

fn test_decode_map_msb() {
	lengths := [3, 3, 3, 3, 3, 2, 4, 4]
	t := build(lengths: lengths, max_bits: 4, bit_order: .msb_first)!
	m := t.decode_map()!
	for sym, l in lengths {
		key := (u64(l) << 32) | u64(t.codes[sym])
		assert m[key] == sym
	}
}

fn test_decode_map_rejects_lsb() {
	t := build(lengths: [1, 1], max_bits: 1, bit_order: .lsb_first)!
	if _ := t.decode_map() {
		assert false, 'decode_map should reject lsb_first tables'
	}
}

fn test_unused_symbols_get_zero_code() {
	// A length-0 symbol is unused; it must not consume a code.
	t := build(lengths: [1, 0, 1], max_bits: 1, bit_order: .msb_first)!
	assert t.codes[1] == 0
	assert t.codes[0] == 0
	assert t.codes[2] == 1
}

fn test_error_length_exceeds_max_bits() {
	if _ := build(lengths: [5], max_bits: 4, bit_order: .msb_first) {
		assert false, 'length > max_bits must error'
	}
}

fn test_error_negative_length() {
	if _ := build(lengths: [-1], max_bits: 4, bit_order: .msb_first) {
		assert false, 'negative length must error'
	}
}

fn test_error_max_bits_too_small() {
	if _ := build(lengths: [1], max_bits: 0, bit_order: .msb_first) {
		assert false, 'max_bits < 1 must error'
	}
}

fn test_error_over_subscribed() {
	// Three length-1 codes cannot coexist (only two 1-bit codes exist).
	if _ := build(lengths: [1, 1, 1], max_bits: 1, bit_order: .msb_first) {
		assert false, 'over-subscribed code must error'
	}
}

fn test_incomplete_code_is_allowed() {
	// A single length-2 code under-subscribes the space; that is permitted.
	t := build(lengths: [2], max_bits: 2, bit_order: .msb_first)!
	assert t.codes[0] == 0
}

fn test_flat_table_rejects_wide_codes() {
	if _ := flat_table(
		lengths:   [max_flat_bits + 1]
		max_bits:  max_flat_bits + 1
		bit_order: .lsb_first
	)
	{
		assert false, 'flat table must reject max_bits > max_flat_bits'
	}
}