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

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 maplit::hashmap;
use std::collections::HashMap;
use std::hash::Hash;
use std::iter::Cloned;
use std::slice::Iter;

#[derive(Clone, Debug)]
pub 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()
    }
}

// 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)]
);