Struct malachite_base::iterators::bit_distributor::BitDistributor

pub struct BitDistributor { /* private fields */ }

Helps generate tuples exhaustively.

Think of counter as the bits of an integer. It’s initialized to zero (all falses), and as it’s repeatedly incremented, it eventually takes on every 64-bit value.

output_types is a list of $n$ configuration structs that, together, specify how to generate an n-element tuple of unsigned integers. Calling get_output repeatedly, passing in 0 through $n - 1$ as index, distributes the bits of counter into a tuple.

This is best shown with an example. If output_types is set to [BitDistributorOutputType::normal(1); 2], the distributor will generate all pairs of unsigned integers. A pair may be extracted by calling get_output(0) and get_output(1); then counter may be incremented to create the next pair. In this case, the pairs will be $(0, 0), (0, 1), (1, 0), (1, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 0), (2, 1), \ldots$.

If you think of these pairs as coordinates in the $xy$-plane, they are traversed along a Z-order curve. Every pair of unsigned integers will be generated exactly once.

In general, setting output_types to [BitDistributorOutputType::normal(1); n] will generate $n$-tuples. The elements of the tuples will be very roughly the same size, in the sense that each element will grow as $O(\sqrt[n]{i})$, where $i$ is the counter. Sometimes we want the elements to grow at different rates. To accomplish this, we can change the weights of the output types. For example, if we set output_types to [BitDistributorOutputType::normal(1), BitDistributorOutputType::normal(2)], the first element of the generated pairs will grow as $O(\sqrt[3]{i})$ and the second as $O(i^{2/3})$. In general, if the weights are $w_0, w_1, \ldots, w_{n-1}$, then the $k$th element of the output tuples will grow as $O(i^{w_i/\sum_{j=0}^{n-1}w_j})$.

Apart from creating normal output types with different weights, we can create tiny output types, which indicate that the corresponding tuple element should grow especially slowly. If output_types contains $m$ tiny output types, each tiny tuple element grows as $O(\sqrt[m]{\log i})$. The growth of the other elements is unaffected. Having only tiny types in output_types is disallowed.

The above discussion of growth rates assumes that max_bits is not specified for any output type. But if max_bits is set to $b$, then the corresponding element will start growing just as if max_bits wasn’t specified, but will stop growing once it reaches $2^b-1$.

Implementations

impl BitDistributor

pub fn new(output_types: &[BitDistributorOutputType]) -> BitDistributor

Creates a new BitDistributor.

Worst-case complexity

$T(n) = O(n)$

$M(n) = O(n)$

where $T$ is time, $M$ is additional memory, and $n$ is output_types.len().

Examples

use malachite_base::iterators::bit_distributor::{BitDistributor, BitDistributorOutputType};

BitDistributor::new(
    &[BitDistributorOutputType::normal(2), BitDistributorOutputType::tiny()]
);

pub fn bit_map_as_slice(&self) -> &[usize]

Returns a reference to the internal bit map as a slice.

The bit map determines which output gets each bit of the counter. For example, if the bit map is $[0, 1, 0, 1, 0, 1, \ldots]$, then the first element of the output pair gets the bits with indices $0, 2, 4, \ldots$ and the second element gets the bits with indices $1, 3, 5, \ldots$.

Worst-case complexity

Constant time and additional memory.

Examples

use malachite_base::iterators::bit_distributor::{BitDistributor, BitDistributorOutputType};

let bd = BitDistributor::new(&[
    BitDistributorOutputType::normal(2),
    BitDistributorOutputType::tiny(),
]);
assert_eq!(
    bd.bit_map_as_slice(),
    &[
        1, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
        0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
        0, 0, 0, 0, 0, 0, 0, 1
    ][..]
);

pub fn set_max_bits(&mut self, output_type_indices: &[usize], max_bits: usize)

Sets the maximum bits for several outputs.

Given slice of output indices, sets the maximum bits for each of the outputs and rebuilds the bit map.

Worst-case complexity

$T(n) = O(n)$

$M(n) = O(1)$

where $T$ is time, $M$ is additional memory, and $n$ is output_type_indices.len().

Panics

Panics if max_bits is 0 or if any index is greater than or equal to self.output_types.len().

Examples

use malachite_base::iterators::bit_distributor::{BitDistributor, BitDistributorOutputType};

let mut bd = BitDistributor::new(&[BitDistributorOutputType::normal(2); 3]);
assert_eq!(
    bd.bit_map_as_slice(),
    &[
        2, 2, 1, 1, 0, 0, 2, 2, 1, 1, 0, 0, 2, 2, 1, 1, 0, 0, 2, 2, 1, 1, 0, 0, 2, 2, 1, 1,
        0, 0, 2, 2, 1, 1, 0, 0, 2, 2, 1, 1, 0, 0, 2, 2, 1, 1, 0, 0, 2, 2, 1, 1, 0, 0, 2, 2,
        1, 1, 0, 0, 2, 2, 1, 1
    ][..]
);

bd.set_max_bits(&[0, 2], 5);
assert_eq!(
    bd.bit_map_as_slice(),
    &[
        2, 2, 1, 1, 0, 0, 2, 2, 1, 1, 0, 0, 2, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
        1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
        1, 1, 1, 1, 1, 1, 1, 1
    ][..]
);

pub fn increment_counter(&mut self)

Increments the counter in preparation for a new set of outputs.

If the counter is incremented $2^{64}$ times, it rolls back to 0.

Worst-case complexity

Constant time and additional memory.

Examples

use malachite_base::iterators::bit_distributor::{BitDistributor, BitDistributorOutputType};

let mut bd = BitDistributor::new(&[BitDistributorOutputType::normal(1)]);
let mut outputs = Vec::new();
for _ in 0..20 {
    outputs.push(bd.get_output(0));
    bd.increment_counter();
}
assert_eq!(
    outputs,
    &[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]
);

pub fn get_output(&self, index: usize) -> usize

Gets the output at a specified index.

Worst-case complexity

Constant time and additional memory.

Panics

Panics if index is greater than or equal to self.output_types.len().

Examples

extern crate itertools;

use itertools::Itertools;
use malachite_base::iterators::bit_distributor::{BitDistributor, BitDistributorOutputType};

let mut bd = BitDistributor::new(&[BitDistributorOutputType::normal(1); 2]);
let mut outputs = Vec::new();
for _ in 0..10 {
    outputs.push((0..2).map(|i| bd.get_output(i)).collect_vec());
    bd.increment_counter();
}
let expected_outputs: &[&[usize]] = &[
    &[0, 0], &[0, 1], &[1, 0], &[1, 1], &[0, 2], &[0, 3], &[1, 2], &[1, 3], &[2, 0], &[2, 1]
];
assert_eq!(outputs, expected_outputs);

Trait Implementations

impl Clone for BitDistributor

fn clone(&self) -> BitDistributor

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Debug for BitDistributor

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl Hash for BitDistributor

fn hash<__H: Hasher>(&self, state: &mut __H)

Feeds this value into the given Hasher.

fn hash_slice<H>(data: &[Self], state: &mut H) where
    H: Hasher, 

Feeds a slice of this type into the given Hasher.

impl PartialEq<BitDistributor> for BitDistributor

fn eq(&self, other: &BitDistributor) -> bool

This method tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &BitDistributor) -> bool

This method tests for !=.

impl Eq for BitDistributor

impl StructuralEq for BitDistributor

impl StructuralPartialEq for BitDistributor