lib.rs

use test::Bencher;

#[derive(Debug)]
pub struct Rate {
    pub id: u8,
    pub from: String,
    pub to: String,
    pub exchange: String,
    pub rate: f64,
    pub vol: f64,
}

impl PartialEq for Rate {
    fn eq(&self, other: &Self) -> bool {
        self.id == other.id
    }
}

pub fn arb_from_rates<'a>(rates: &[&'a Rate], depth: u32) -> Vec<Vec<Vec<&'a Rate>>> {
    arb_from_combos(combos_from_rates(rates, depth))
}

fn arb_from_combos(mut combos: Vec<Vec<Vec<&Rate>>>) -> Vec<Vec<Vec<&Rate>>> {
    combos.iter_mut().for_each(|x| {
        x.retain(|j| is_arb(&j));
        x.iter_mut().for_each(|x| x.sort_unstable_by_key(|r| r.id));
        // Relying on the fact that each array will be unique once sorted
        x.dedup();
    });
    combos
}

fn is_arb(list: &[&Rate]) -> bool {
    if list.len() < 2 {
        return false;
    }

    if list[0].from != list[list.len() - 1].to {
        return false;
    }

    list.windows(2)
        .try_fold(list[0].rate, |prod, rates| {
            if rates[0].to != rates[1].from {
                return None;
            }
            Some(prod * rates[1].rate)
        })
        .map_or(false, |prod| prod > 1.0)
}

fn combos_from_rates<'a>(rates: &[&'a Rate], depth: u32) -> Vec<Vec<Vec<&'a Rate>>> {
    let mut ret = Vec::with_capacity(depth as usize + 1);
    ret.push(build_base(rates));

    for i in 1..(depth as usize) {
        let mut tmp = Vec::new();
        for j in 0..ret[i - 1].len() {
            for k in 0..rates.len() {
                if ret[i - 1][j].last().unwrap().to == rates[k].from
                    && !is_rate_in_list(&ret[i - 1][j], rates[k])
                    && !is_list_closing(&ret[i - 1][j])
                {
                    tmp.push(
                        ret[i - 1][j]
                            .iter()
                            .chain(iter::once(&rates[k]))
                            .copied()
                            .collect(),
                    );
                }
            }
        }
        ret.push(tmp);
    }

    ret
}

fn is_list_closing(list: &Vec<&Rate>) -> bool {
    list[0].from == list.last().unwrap().to
}

fn build_base<'a>(rates: &[&'a Rate]) -> Vec<Vec<&'a Rate>> {
    rates
        .iter()
        .enumerate()
        .flat_map(|(i, &rate_a)| {
            rates[(i + 1)..].iter().filter_map(move |&rate_b| {
                if rate_a.to == rate_b.from {
                    Some(vec![rate_a, rate_b])
                } else {
                    None
                }
            })
        })
        .collect()
}

fn is_rate_in_list(list: &[&Rate], r: &Rate) -> bool {
    list.iter().any(|&rate| rate == r)
}