use std::collections::HashSet;
use crate::game::{Coalition, ExplicitGame, PlayerSet, SetFunction, excess_table};
pub trait OracleGame: SetFunction {
fn excess_order<'a>(&'a self, x: &'a [f64]) -> Box<dyn Iterator<Item = (PlayerSet, f64)> + 'a>;
fn scale(&self) -> f64;
}
pub trait Separation: SetFunction {
fn violated(
&self,
x: &[f64],
bound: f64,
skip: &dyn Fn(&PlayerSet) -> bool,
limit: usize,
) -> Vec<(PlayerSet, f64)>;
fn value_scale(&self) -> f64;
}
impl<G: OracleGame + ?Sized> Separation for G {
fn violated(
&self,
x: &[f64],
bound: f64,
skip: &dyn Fn(&PlayerSet) -> bool,
limit: usize,
) -> Vec<(PlayerSet, f64)> {
let mut found = Vec::new();
for (coalition, excess) in self.excess_order(x) {
if excess <= bound || found.len() >= limit {
break;
}
if !skip(&coalition) {
found.push((coalition, excess));
}
}
found
}
fn value_scale(&self) -> f64 {
self.scale()
}
}
impl OracleGame for ExplicitGame {
fn excess_order<'a>(&'a self, x: &'a [f64]) -> Box<dyn Iterator<Item = (PlayerSet, f64)> + 'a> {
let n = ExplicitGame::players(self);
assert_eq!(
x.len(),
n,
"配分の長さ {} がプレイヤー数 {n} と異なる",
x.len()
);
let full = (1u64 << n) - 1;
let excess = excess_table(self, x);
let mut order: Vec<u64> = (1..full).collect();
order.sort_by(|a, b| {
excess[*b as usize]
.total_cmp(&excess[*a as usize])
.then(a.cmp(b))
});
Box::new(order.into_iter().map(move |mask| {
(
PlayerSet::from_coalition(n, Coalition(mask)),
excess[mask as usize],
)
}))
}
fn scale(&self) -> f64 {
self.max_abs_value()
}
}
pub(crate) struct MaxMerge<A, B>
where
A: Iterator<Item = (PlayerSet, f64)>,
B: Iterator<Item = (PlayerSet, f64)>,
{
first: std::iter::Peekable<A>,
second: std::iter::Peekable<B>,
seen: HashSet<PlayerSet>,
}
impl<A, B> MaxMerge<A, B>
where
A: Iterator<Item = (PlayerSet, f64)>,
B: Iterator<Item = (PlayerSet, f64)>,
{
pub fn new(first: A, second: B) -> MaxMerge<A, B> {
MaxMerge {
first: first.peekable(),
second: second.peekable(),
seen: HashSet::new(),
}
}
}
impl<A, B> Iterator for MaxMerge<A, B>
where
A: Iterator<Item = (PlayerSet, f64)>,
B: Iterator<Item = (PlayerSet, f64)>,
{
type Item = (PlayerSet, f64);
fn next(&mut self) -> Option<Self::Item> {
loop {
let take_first = match (self.first.peek(), self.second.peek()) {
(None, None) => return None,
(Some(_), None) => true,
(None, Some(_)) => false,
(Some(a), Some(b)) => a.1 >= b.1,
};
let item = if take_first {
self.first.next()
} else {
self.second.next()
}?;
if self.seen.insert(item.0.clone()) {
return Some(item);
}
}
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn explicit_excess_order_is_sorted() {
let game = crate::generators::bnf(1, 5, 2).unwrap();
let x = crate::kernel::equal_surplus_division(&game);
let order: Vec<(PlayerSet, f64)> = game.excess_order(&x).collect();
assert_eq!(order.len(), 30);
assert!(order.windows(2).all(|w| w[0].1 >= w[1].1));
for (set, e) in &order {
assert!((SetFunction::value(&game, set) - set.sum(&x) - e).abs() < 1e-12);
}
}
}