Function malachite_base::tuples::exhaustive::lex_dependent_pairs

pub const fn lex_dependent_pairs<X: Clone, Y, S: ExhaustiveDependentPairsYsGenerator<X, Y, J>, I: Iterator<Item = X>, J: Iterator<Item = Y>>(
    xs: I, 
    ys_generator: S
) -> LexDependentPairs<X, Y, S, I, J>

Generates pairs $(x, y)$, where the possible values of $y$ depend on the value of $x$. All $y$ values are output before proceeding to the next $x$.

This function takes an iterator xs that produces $x$ values, along with a ys_generator that creates an iterator of $y$ values when given a reference to an $x$ value. The resulting iterator first generates all pairs generated by the first $x$ value, then all pairs generated by the second $x$ value, and so on.

It’s called lex_dependent_pairs because if the xs iterator produces elements in some order, and each ys iterator produces elements in some order (uniform across all ys), then the resulting pairs are output in lexicographic order with respect to the $x$ and $y$ orders.

Each ys iterator produced by ys_generator must be finite; if some ys is infinite, then no further xs value will be used. For a similar function that works with infinite ys, see exhaustive_dependent_pairs.

If, after a certain point, all the generated ys are empty, the output iterator will hang trying to find another $(x, y)$ to output. To get around this, try lex_dependent_pairs_stop_after_empty_ys.

Examples

extern crate itertools;
#[macro_use]
extern crate maplit;

use itertools::Itertools;
use malachite_base::tuples::exhaustive::{
    lex_dependent_pairs, ExhaustiveDependentPairsYsGenerator,
};
use std::collections::HashMap;
use std::hash::Hash;
use std::iter::Cloned;
use std::slice::Iter;

#[derive(Clone, Debug)]
struct DPGeneratorFromMap<X: Clone + Eq + Hash, Y: 'static + Clone> {
    map: HashMap<X, &'static [Y]>,
}

impl<X: Clone + Eq + Hash, Y: 'static + Clone>
    ExhaustiveDependentPairsYsGenerator<X, Y, Cloned<Iter<'static, Y>>>
    for DPGeneratorFromMap<X, Y>
{
    #[inline]
    fn get_ys(&self, x: &X) -> Cloned<Iter<'static, Y>> {
        self.map[x].iter().cloned()
    }
}

fn main() {
    let xs = ["a", "b", "c", "b", "a"].iter().cloned();
    let xss = lex_dependent_pairs(
        xs,
        DPGeneratorFromMap {
            map: hashmap! {
                "a" => &[2, 3, 4][..],
                "b" => &[20][..],
                "c" => &[30, 40][..]
            },
        },
    )
    .take(20)
    .collect_vec();
    assert_eq!(
        xss.as_slice(),
        &[
            ("a", 2),
            ("a", 3),
            ("a", 4),
            ("b", 20),
            ("c", 30),
            ("c", 40),
            ("b", 20),
            ("a", 2),
            ("a", 3),
            ("a", 4)
        ]
    );

    let xs = [1, 2, 3, 2, 3, 2, 2].iter().cloned();
    let xss = lex_dependent_pairs(
        xs,
        DPGeneratorFromMap {
            map: hashmap! {
                1 => &[100, 101, 102][..],
                2 => &[][..],
                3 => &[300, 301, 302][..]
            },
        },
    )
    .take(20)
    .collect_vec();
    assert_eq!(
        xss.as_slice(),
        &[
            (1, 100),
            (1, 101),
            (1, 102),
            (3, 300),
            (3, 301),
            (3, 302),
            (3, 300),
            (3, 301),
            (3, 302),
        ]
    );
}