Function malachite_base::tuples::exhaustive::exhaustive_dependent_pairs

pub const fn exhaustive_dependent_pairs<X: Clone, Y, G: Iterator<Item = usize>, S: ExhaustiveDependentPairsYsGenerator<X, Y, J>, I: Iterator<Item = X>, J: Iterator<Item = Y>>(
    index_generator: G, 
    xs: I, 
    ys_generator: S
) -> ExhaustiveDependentPairs<X, Y, G, S, I, J>

Generates pairs $(x, y)$, where the possible values of $y$ depend on the value of $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 does not use all of an $x$’s $y$s immediately. Instead, it uses an index_generator (an iterator of usizes) to determine which $x$ value’s iterator should be advanced. This arrangement allows for an $x$ to map to infinitely many ys.

index_generator must generate every natural number infinitely many times. Good generators can be created using ruler_sequence or bit_distributor_sequence. The slower the sequence’s growth rate, the more this iterator will prefer to use initial $x$ values before exploring later ones.

If you want all of an $x$ value’s $y$s to be used before moving on to the next $x$, use lex_dependent_pairs instead.

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 exhaustive_dependent_pairs_stop_after_empty_ys.

Examples

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

use itertools::Itertools;
use malachite_base::num::exhaustive::exhaustive_positive_primitive_ints;
use malachite_base::num::iterators::ruler_sequence;
use malachite_base::tuples::exhaustive::{
    exhaustive_dependent_pairs, ExhaustiveDependentPairsYsGenerator,
};
use std::collections::HashMap;
use std::hash::Hash;
use std::iter::Cloned;
use std::slice::Iter;

#[derive(Clone, Debug)]
struct MultiplesGeneratorHelper {
    u: u64,
    step: u64,
}

impl Iterator for MultiplesGeneratorHelper {
    type Item = u64;

    fn next(&mut self) -> Option<u64> {
        let next = self.u;
        self.u += self.step;
        Some(next)
    }
}

#[derive(Clone, Debug)]
struct MultiplesGenerator {}

impl ExhaustiveDependentPairsYsGenerator<u64, u64, MultiplesGeneratorHelper>
    for MultiplesGenerator
{
    #[inline]
    fn get_ys(&self, x: &u64) -> MultiplesGeneratorHelper {
        MultiplesGeneratorHelper { u: *x, step: *x }
    }
}

#[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() {
    // All (x, y) where x is a positive natural and y is a positive multiple of x. It would be
    // easier to do
    //
    // exhaustive_pairs_from_single(exhaustive_positive_primitive_ints::<u64>())
    //      .map(|(x, y)| (x, x * y))
    //
    // in this case.
    let xs = exhaustive_positive_primitive_ints::<u64>();
    let xss = exhaustive_dependent_pairs(ruler_sequence(), xs.clone(), MultiplesGenerator {})
        .take(50)
        .collect_vec();
    assert_eq!(
        xss.as_slice(),
        &[
            (1, 1),
            (2, 2),
            (1, 2),
            (3, 3),
            (1, 3),
            (2, 4),
            (1, 4),
            (4, 4),
            (1, 5),
            (2, 6),
            (1, 6),
            (3, 6),
            (1, 7),
            (2, 8),
            (1, 8),
            (5, 5),
            (1, 9),
            (2, 10),
            (1, 10),
            (3, 9),
            (1, 11),
            (2, 12),
            (1, 12),
            (4, 8),
            (1, 13),
            (2, 14),
            (1, 14),
            (3, 12),
            (1, 15),
            (2, 16),
            (1, 16),
            (6, 6),
            (1, 17),
            (2, 18),
            (1, 18),
            (3, 15),
            (1, 19),
            (2, 20),
            (1, 20),
            (4, 12),
            (1, 21),
            (2, 22),
            (1, 22),
            (3, 18),
            (1, 23),
            (2, 24),
            (1, 24),
            (5, 10),
            (1, 25),
            (2, 26)
        ]
    );

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