use std::collections::BTreeSet;

/// Return only those sets that are not strict subsets of any other set in the
/// slice -- i.e. the ⊆-maximal antichain of the input.
///
/// Useful for computing preferred-style semantics where only ⊆-maximal
/// admissible / complete extensions are retained.
///
/// # Complexity
///
/// O(n² · m) where n = `sets.len()` and m = average set size (each pair
/// requires an O(m) subset check).
pub fn maximal_by_inclusion<T: Ord + Clone>(sets: &[BTreeSet<T>]) -> Vec<BTreeSet<T>> {
    sets.iter()
        .filter(|s| !sets.iter().any(|other| *other != **s && s.is_subset(other)))
        .cloned()
        .collect()
}

/// Keep only items whose projected key-set is ⊆-maximal among all items.
///
/// `key` extracts the `BTreeSet` used for the subset comparison; items whose
/// key is a strict subset of another item's key are discarded. The key
/// function is called exactly once per item (all keys are pre-collected before
/// comparison begins).
///
/// # Complexity
///
/// n calls to `key` followed by O(n² · m) pairwise subset checks, where
/// n = `items.len()` and m = average key-set size.
pub fn retain_maximal_by<T, K: Ord>(items: Vec<T>, key: impl Fn(&T) -> BTreeSet<K>) -> Vec<T> {
    let keys: Vec<BTreeSet<K>> = items.iter().map(&key).collect();
    items
        .into_iter()
        .enumerate()
        .filter(|(i, _)| {
            !keys
                .iter()
                .enumerate()
                .any(|(j, other)| *i != j && keys[*i].is_subset(other) && keys[*i] != *other)
        })
        .map(|(_, item)| item)
        .collect()
}
