use crate::io::{Value, TWO};
use std::ops::{Index, IndexMut};

pub fn encode<X: Index<usize, Output = Value> + IndexMut<usize, Output = Value>>(
    size: usize,
    a: &mut X,
    b: &mut X,
) {
    let mut k = size;
    while k != 1 {
        k /= 2;
        for i in 0..k {
            let x = a[i * 2];
            let y = a[i * 2 + 1];
            b[i] = x + y;
            b[k + i] = x - y;
        }
        for i in 0..k {
            a[i] = b[i]
        }
    }
}

pub fn decode<X: Index<usize, Output = Value> + IndexMut<usize, Output = Value>>(
    size: usize,
    a: &mut X,
    b: &mut X,
) {
    let mut k = 1;
    while k != size {
        for i in 0..k {
            let avr = a[i] / TWO;
            let spread = a[i + k] / TWO;
            b[i * 2] = avr + spread;
            b[i * 2 + 1] = avr - spread;
        }
        k *= 2;
        for i in 0..k {
            a[i] = b[i]
        }
    }
}