use super::funejson::Value;
use super::money_allocate::allocate;
use super::money_amount::{money, money_from_value, money_to_value, Money};
use super::money_apply_rate::apply_rate;
use super::money_sum::sum_money;

const MAX_COMPETING: usize = 6;

// A unit is (line index, unit price); a group is (unit indices, discount).
type Unit = (usize, i64);
type Group = (Vec<usize>, i64);

fn check_promotion(p: &Promotion, currency: &str) {
    if p.group_size < 1 {
        panic!("promotion \"{}\": groupSize must be 1 or more", p.id);
    }
    match p.kind.as_str() {
        "free-items" => {
            if p.free_items < 1 || p.free_items >= p.group_size {
                panic!("promotion \"{}\": freeItems must be from 1 to groupSize - 1", p.id);
            }
        }
        "percent-off" => {
            if p.basis_points < 1 || p.basis_points > 10000 {
                panic!("promotion \"{}\": basisPoints must be from 1 to 10000", p.id);
            }
        }
        "amount-off" | "group-price" => match &p.amount {
            None => panic!("promotion \"{}\" needs an amount", p.id),
            Some(amount) => {
                if amount.currency != currency {
                    panic!("currency mismatch: {} and {}", currency, amount.currency);
                }
                if amount.minor < 0 {
                    panic!("promotion \"{}\": amount must not be negative", p.id);
                }
            }
        },
        other => panic!("promotion \"{}\": unknown kind \"{}\"", p.id, other),
    }
}

// The qualifying unclaimed units from dearest to cheapest (ties in basket
// order), cut into consecutive groups of group_size. Groups that would save
// nothing are skipped.
fn evaluate(p: &Promotion, units: &[Unit], skus: &[String], claimed: &[bool], currency: &str) -> Vec<Group> {
    let mut pool: Vec<usize> = (0..units.len())
        .filter(|&i| !claimed[i] && p.skus.contains(&skus[units[i].0]))
        .collect();
    pool.sort_by(|&a, &b| units[b].1.cmp(&units[a].1).then(a.cmp(&b)));
    let size = p.group_size as usize;
    let mut groups: Vec<Group> = Vec::new();
    let mut start = 0;
    while start + size <= pool.len() {
        let members: Vec<usize> = pool[start..start + size].to_vec();
        let prices: Vec<i64> = members.iter().map(|&i| units[i].1).collect();
        let total: i64 = prices.iter().sum();
        let discount = match p.kind.as_str() {
            "free-items" => prices[size - p.free_items as usize..].iter().sum(),
            "percent-off" => apply_rate(&money(total, currency), p.basis_points, "half-up").minor,
            "amount-off" => p.amount.as_ref().unwrap().minor.min(total),
            _ => (total - p.amount.as_ref().unwrap().minor).max(0),
        };
        if discount > 0 {
            groups.push((members, discount));
        }
        start += size;
    }
    groups
}

fn run(
    order: &[usize],
    promotions: &[Promotion],
    units: &[Unit],
    skus: &[String],
    claimed: &mut Vec<bool>,
    currency: &str,
) -> (i64, Vec<(usize, Vec<Group>)>) {
    let mut groups: Vec<(usize, Vec<Group>)> = Vec::new();
    let mut total = 0;
    for &index in order {
        let made = evaluate(&promotions[index], units, skus, claimed, currency);
        for (members, discount) in &made {
            for &u in members {
                claimed[u] = true;
            }
            total += discount;
        }
        groups.push((index, made));
    }
    (total, groups)
}

fn next_permutation(a: &mut [usize]) -> bool {
    if a.len() < 2 {
        return false;
    }
    let mut i = a.len() - 1;
    while i > 0 && a[i - 1] >= a[i] {
        i -= 1;
    }
    if i == 0 {
        return false;
    }
    let mut j = a.len() - 1;
    while a[j] <= a[i - 1] {
        j -= 1;
    }
    a.swap(i - 1, j);
    a[i..].reverse();
    true
}

fn find(parent: &[usize], mut i: usize) -> usize {
    while parent[i] != i {
        i = parent[i];
    }
    i
}

/// Price a basket under competing promotions: the customer gets the order of
/// application that saves the most, and each deal's saving is allocated back
/// to the lines in its groups exactly.
///
/// # Panics
/// Panics on an empty basket, mixed currencies, a bad quantity or price, a
/// malformed or duplicate promotion, or more than six competing promotions.
pub fn apply_promotions(lines: &[PromoLine], promotions: &[Promotion]) -> PromotionResult {
    if lines.is_empty() {
        panic!("a basket needs at least one line");
    }
    let currency = lines[0].unit_price.currency.clone();
    let skus: Vec<String> = lines.iter().map(|l| l.sku.clone()).collect();
    let mut units: Vec<Unit> = Vec::new();
    for (index, line) in lines.iter().enumerate() {
        if line.unit_price.currency != currency {
            panic!("currency mismatch: {} and {}", currency, line.unit_price.currency);
        }
        if line.quantity < 1 {
            panic!("quantity must be 1 or more, received {}", line.quantity);
        }
        if line.unit_price.minor < 0 {
            panic!("unitPrice must not be negative, received {}", line.unit_price.minor);
        }
        for _ in 0..line.quantity {
            units.push((index, line.unit_price.minor));
        }
    }
    for (i, p) in promotions.iter().enumerate() {
        if promotions[..i].iter().any(|q| q.id == p.id) {
            panic!("duplicate promotion id \"{}\"", p.id);
        }
        check_promotion(p, &currency);
    }

    // Promotions with something to act on, joined into sets that share a SKU
    // present in the basket. Only promotions in the same set compete.
    let relevant: Vec<usize> = (0..promotions.len())
        .filter(|&i| promotions[i].skus.iter().any(|s| skus.contains(s)))
        .collect();
    let mut parent: Vec<usize> = (0..promotions.len()).collect();
    for x in 0..relevant.len() {
        for y in x + 1..relevant.len() {
            let a = &promotions[relevant[x]];
            let b = &promotions[relevant[y]];
            if a.skus.iter().any(|s| skus.contains(s) && b.skus.contains(s)) {
                let ra = find(&parent, relevant[x]);
                let rb = find(&parent, relevant[y]);
                if ra != rb {
                    parent[ra.max(rb)] = ra.min(rb);
                }
            }
        }
    }
    let mut components: Vec<(usize, Vec<usize>)> = Vec::new();
    for &i in &relevant {
        let root = find(&parent, i);
        match components.iter_mut().find(|(r, _)| *r == root) {
            Some((_, members)) => members.push(i),
            None => components.push((root, vec![i])),
        }
    }

    let mut claimed = vec![false; units.len()];
    let mut chosen: Vec<Vec<Group>> = vec![Vec::new(); promotions.len()];
    for (_, component) in &components {
        if component.len() > MAX_COMPETING {
            let ids: Vec<&str> = component.iter().map(|&i| promotions[i].id.as_str()).collect();
            panic!(
                "more than {} promotions compete for the same items: {}",
                MAX_COMPETING,
                ids.join(", ")
            );
        }
        let mut order = component.clone();
        let mut best_order = order.clone();
        let mut best_total = -1;
        loop {
            let mut trial = claimed.clone();
            let (total, _) = run(&order, promotions, &units, &skus, &mut trial, &currency);
            if total > best_total {
                best_total = total;
                best_order = order.clone();
            }
            if !next_permutation(&mut order) {
                break;
            }
        }
        let (_, groups) = run(&best_order, promotions, &units, &skus, &mut claimed, &currency);
        for (index, made) in groups {
            chosen[index] = made;
        }
    }

    let mut line_discount = vec![0i64; lines.len()];
    let mut applied: Vec<AppliedPromotion> = Vec::new();
    for (index, p) in promotions.iter().enumerate() {
        let made = &chosen[index];
        if made.is_empty() {
            continue;
        }
        let mut saved = 0;
        for (members, discount) in made {
            let ratios: Vec<i64> = members.iter().map(|&u| units[u].1).collect();
            let shares = allocate(&money(*discount, &currency), &ratios);
            for (k, &u) in members.iter().enumerate() {
                line_discount[units[u].0] += shares[k].minor;
            }
            saved += discount;
        }
        applied.push(AppliedPromotion {
            id: p.id.clone(),
            groups: made.len() as i64,
            discount: money(saved, &currency),
        });
    }

    let priced: Vec<PricedLine> = lines
        .iter()
        .enumerate()
        .map(|(index, line)| {
            let gross = line.unit_price.minor * line.quantity;
            PricedLine {
                sku: line.sku.clone(),
                quantity: line.quantity,
                gross: money(gross, &currency),
                discount: money(line_discount[index], &currency),
                net: money(gross - line_discount[index], &currency),
            }
        })
        .collect();
    let grosses: Vec<Money> = priced.iter().map(|l| l.gross.clone()).collect();
    let discounts: Vec<Money> = priced.iter().map(|l| l.discount.clone()).collect();
    let subtotal = sum_money(&grosses, &currency);
    let discount = sum_money(&discounts, &currency);
    PromotionResult {
        lines: priced,
        applied,
        total: money(subtotal.minor - discount.minor, &currency),
        subtotal,
        discount,
    }
}

pub fn promo_line_from_value(v: &Value) -> PromoLine {
    PromoLine {
        sku: v.get("sku").as_str().to_string(),
        unit_price: money_from_value(v.get("unitPrice")),
        quantity: v.get("quantity").as_i64(),
    }
}

pub fn promotion_from_value(v: &Value) -> Promotion {
    Promotion {
        id: v.get("id").as_str().to_string(),
        kind: v.get("kind").as_str().to_string(),
        skus: v.get("skus").as_arr().iter().map(|s| s.as_str().to_string()).collect(),
        group_size: v.get("groupSize").as_i64(),
        free_items: v.get("freeItems").as_i64(),
        basis_points: v.get("basisPoints").as_i64(),
        amount: if v.get("amount").is_null() {
            None
        } else {
            Some(money_from_value(v.get("amount")))
        },
    }
}

pub fn applied_promotion_to_value(a: &AppliedPromotion) -> Value {
    Value::obj(vec![
        ("id", Value::str(&a.id)),
        ("groups", Value::Int(a.groups)),
        ("discount", money_to_value(&a.discount)),
    ])
}

pub fn promotion_result_to_value(r: &PromotionResult) -> Value {
    Value::obj(vec![
        (
            "lines",
            Value::Arr(
                r.lines
                    .iter()
                    .map(|l| {
                        Value::obj(vec![
                            ("sku", Value::str(&l.sku)),
                            ("quantity", Value::Int(l.quantity)),
                            ("gross", money_to_value(&l.gross)),
                            ("discount", money_to_value(&l.discount)),
                            ("net", money_to_value(&l.net)),
                        ])
                    })
                    .collect(),
            ),
        ),
        ("applied", Value::Arr(r.applied.iter().map(applied_promotion_to_value).collect())),
        ("subtotal", money_to_value(&r.subtotal)),
        ("discount", money_to_value(&r.discount)),
        ("total", money_to_value(&r.total)),
    ])
}

pub fn fune_vector(args: &[Value]) -> Value {
    let lines: Vec<PromoLine> = args[0].as_arr().iter().map(promo_line_from_value).collect();
    let promotions: Vec<Promotion> = args[1].as_arr().iter().map(promotion_from_value).collect();
    promotion_result_to_value(&apply_promotions(&lines, &promotions))
}