powerset.rs - source

Files

addr2line

function.rs lazy.rs lib.rs

adler

aho_corasick

packed

teddy

compile.rs mod.rs runtime.rs

api.rs mod.rs pattern.rs rabinkarp.rs vector.rs

ahocorasick.rs automaton.rs buffer.rs byte_frequencies.rs classes.rs dfa.rs error.rs lib.rs nfa.rs prefilter.rs state_id.rs

arrayvec

array.rs array_string.rs char.rs errors.rs lib.rs maybe_uninit.rs

atty

backtrace

backtrace

libunwind.rs mod.rs

symbolize

gimli

elf.rs libs_dl_iterate_phdr.rs mmap_unix.rs stash.rs

gimli.rs mod.rs

capture.rs lib.rs print.rs types.rs

bitflags

camino

lib.rs serde_impls.rs

cargo_metadata

dependency.rs diagnostic.rs errors.rs lib.rs messages.rs

cargo_nextest

cargo_cli.rs dispatch.rs errors.rs lib.rs output.rs

cargo_platform

cfg.rs error.rs lib.rs

cfg_expr

expr

lexer.rs parser.rs

targets

error.rs expr.rs lib.rs targets.rs

cfg_if

chrono

format

mod.rs parse.rs parsed.rs scan.rs strftime.rs

naive

date.rs datetime.rs internals.rs isoweek.rs time.rs

offset

fixed.rs local.rs mod.rs utc.rs

sys

date.rs datetime.rs div.rs lib.rs round.rs sys.rs

clap

clap_derive

derives

arg_enum.rs args.rs into_app.rs mod.rs parser.rs subcommand.rs

utils

doc_comments.rs mod.rs spanned.rs ty.rs

attrs.rs dummies.rs lib.rs parse.rs

color_eyre

section

config.rs fmt.rs handler.rs lib.rs private.rs writers.rs

config

file

format

source

file.rs mod.rs string.rs

path

mod.rs parser.rs

config.rs de.rs env.rs error.rs lib.rs ser.rs source.rs value.rs

crossbeam_channel

flavors

array.rs at.rs list.rs mod.rs never.rs tick.rs zero.rs

channel.rs context.rs counter.rs err.rs lib.rs select.rs select_macro.rs utils.rs waker.rs

crossbeam_deque

deque.rs lib.rs

crossbeam_epoch

sync

list.rs mod.rs queue.rs

atomic.rs collector.rs default.rs deferred.rs epoch.rs guard.rs internal.rs lib.rs

crossbeam_utils

atomic

atomic_cell.rs consume.rs mod.rs seq_lock.rs

sync

mod.rs parker.rs sharded_lock.rs wait_group.rs

backoff.rs cache_padded.rs lib.rs thread.rs

ctrlc

platform

unix

error.rs lib.rs signal.rs

datatest_stable

lib.rs macros.rs runner.rs utils.rs

debug_ignore

duct

either

enable_ansi_support

env_logger

filter

mod.rs string.rs

fmt

humantime

mod.rs shim_impl.rs

writer

termcolor

mod.rs shim_impl.rs

eyre

backtrace.rs chain.rs context.rs error.rs fmt.rs kind.rs lib.rs macros.rs wrapper.rs

fixedbitset

lib.rs range.rs

gimli

guppy

guppy_workspace_hack

hashbrown

external_trait_impls

raw

alloc.rs bitmask.rs mod.rs sse2.rs

lib.rs macros.rs map.rs scopeguard.rs set.rs

humantime

date.rs duration.rs lib.rs wrapper.rs

humantime_serde

indent_write

fmt.rs indentable.rs io.rs lib.rs

indenter

indexmap

map

core

equivalent.rs lib.rs macros.rs map.rs mutable_keys.rs set.rs util.rs

is_ci

itertools

itoa

lib.rs udiv128.rs

lazy_static

inline_lazy.rs lib.rs

lexical_core

libc

unix

linux_like

linux

arch

generic

gnu

b64

x86_64

align.rs mod.rs not_x32.rs

align.rs mod.rs

align.rs mod.rs non_exhaustive.rs

align.rs mod.rs

fixed_width_ints.rs lib.rs macros.rs

log

lib.rs macros.rs

memchr

memchr

x86

avx.rs mod.rs sse2.rs

fallback.rs iter.rs mod.rs naive.rs

memmem

prefilter

x86

avx.rs mod.rs sse.rs

fallback.rs genericsimd.rs mod.rs

x86

avx.rs mod.rs sse.rs

byte_frequencies.rs genericsimd.rs mod.rs rabinkarp.rs rarebytes.rs twoway.rs util.rs vector.rs

memoffset

lib.rs offset_of.rs raw_field.rs span_of.rs

miniz_oxide

deflate

buffer.rs core.rs mod.rs stream.rs

inflate

core.rs mod.rs output_buffer.rs stream.rs

lib.rs shared.rs

nested

nextest_metadata

errors.rs exit_codes.rs lib.rs test_list.rs

nextest_runner

reporter

test_list

output_format.rs

config.rs errors.rs helpers.rs lib.rs partition.rs reporter.rs runner.rs signal.rs stopwatch.rs test_filter.rs test_list.rs

nix

nom

bits

complete.rs macros.rs mod.rs streaming.rs

branch

macros.rs mod.rs

bytes

complete.rs macros.rs mod.rs streaming.rs

character

complete.rs macros.rs mod.rs streaming.rs

combinator

macros.rs mod.rs

multi

macros.rs mod.rs

number

complete.rs macros.rs mod.rs streaming.rs

sequence

macros.rs mod.rs

error.rs internal.rs lib.rs methods.rs str.rs traits.rs util.rs whitespace.rs

num_cpus

lib.rs linux.rs

num_integer

average.rs lib.rs roots.rs

num_traits

ops

checked.rs inv.rs mod.rs mul_add.rs overflowing.rs saturating.rs wrapping.rs

bounds.rs cast.rs float.rs identities.rs int.rs lib.rs macros.rs pow.rs sign.rs

object

once_cell

imp_std.rs lib.rs race.rs

os_pipe

os_str_bytes

common

iter.rs lib.rs pattern.rs raw_str.rs util.rs

owo_colors

colors

css.rs custom.rs dynamic.rs xterm.rs

colors.rs combo.rs dyn_colors.rs dyn_styles.rs lib.rs overrides.rs styles.rs supports_colors.rs

pathdiff

petgraph

proc_macro2

detection.rs fallback.rs lib.rs marker.rs parse.rs wrapper.rs

proc_macro_error

imp

diagnostic.rs dummy.rs lib.rs macros.rs sealed.rs

proc_macro_error_attr

lib.rs parse.rs settings.rs

quick_junit

lib.rs report.rs serialize.rs

quick_xml

events

attributes.rs mod.rs

errors.rs escapei.rs lib.rs reader.rs utils.rs writer.rs

quote

ext.rs format.rs ident_fragment.rs lib.rs runtime.rs spanned.rs to_tokens.rs

rayon

array.rs delegate.rs lib.rs math.rs option.rs par_either.rs prelude.rs private.rs range.rs range_inclusive.rs result.rs split_producer.rs str.rs string.rs vec.rs

rayon_core

compile_fail

mod.rs quicksort_race1.rs quicksort_race2.rs quicksort_race3.rs rc_return.rs rc_upvar.rs scope_join_bad.rs

join

scope

sleep

counters.rs mod.rs

spawn

thread_pool

job.rs latch.rs lib.rs log.rs private.rs registry.rs unwind.rs

regex

literal

backtrack.rs compile.rs dfa.rs error.rs exec.rs expand.rs find_byte.rs input.rs lib.rs pikevm.rs pool.rs prog.rs re_builder.rs re_bytes.rs re_set.rs re_trait.rs re_unicode.rs sparse.rs utf8.rs

regex_syntax

rustc_demangle

legacy.rs lib.rs v0.rs

ryu

buffer

pretty

exponent.rs mantissa.rs mod.rs

common.rs d2s.rs d2s_full_table.rs d2s_intrinsics.rs digit_table.rs f2s.rs f2s_intrinsics.rs lib.rs

same_file

scopeguard

semver

backport.rs display.rs error.rs eval.rs identifier.rs impls.rs lib.rs parse.rs serde.rs

serde

de

format.rs ignored_any.rs impls.rs mod.rs seed.rs utf8.rs value.rs

private

de.rs doc.rs mod.rs ser.rs size_hint.rs

ser

fmt.rs impls.rs impossible.rs mod.rs

integer128.rs lib.rs macros.rs

serde_derive

internals

ast.rs attr.rs case.rs check.rs ctxt.rs mod.rs receiver.rs respan.rs symbol.rs

bound.rs de.rs dummy.rs fragment.rs lib.rs pretend.rs ser.rs try.rs

serde_json

features_check

io

value

de.rs from.rs index.rs mod.rs partial_eq.rs ser.rs

de.rs error.rs iter.rs lib.rs macros.rs map.rs number.rs read.rs ser.rs

shared_child

sys

shellwords

smallvec

static_assertions

assert_cfg.rs assert_eq_align.rs assert_eq_size.rs assert_fields.rs assert_impl.rs assert_obj_safe.rs assert_trait.rs assert_type.rs const_assert.rs lib.rs

strip_ansi_escapes

strsim

structopt

structopt_derive

attrs.rs doc_comments.rs lib.rs parse.rs spanned.rs ty.rs

supports_color

syn

target_lexicon

data_model.rs host.rs lib.rs parse_error.rs targets.rs triple.rs

target_spec

errors.rs lib.rs platform.rs simple_eval.rs spec.rs triple.rs

termcolor

textwrap

core.rs indentation.rs lib.rs word_separators.rs word_splitters.rs wrap_algorithms.rs

time

display.rs duration.rs lib.rs parse.rs sys.rs

toml

datetime.rs de.rs lib.rs macros.rs map.rs ser.rs spanned.rs tokens.rs value.rs

twox_hash

lib.rs sixty_four.rs thirty_two.rs xxh3.rs

unicode_xid

lib.rs tables.rs

utf8parse

lib.rs types.rs

vte

definitions.rs lib.rs params.rs table.rs

vte_generate_state_changes

walkdir

dent.rs error.rs lib.rs util.rs

use std::fmt;
use std::iter::FusedIterator;
use std::usize;
use alloc::vec::Vec;

use super::combinations::{Combinations, combinations};
use super::size_hint;

/// An iterator to iterate through the powerset of the elements from an iterator.
///
/// See [`.powerset()`](crate::Itertools::powerset) for more
/// information.
#[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
pub struct Powerset<I: Iterator> {
    combs: Combinations<I>,
    // Iterator `position` (equal to count of yielded elements).
    pos: usize,
}

impl<I> Clone for Powerset<I>
    where I: Clone + Iterator,
          I::Item: Clone,
{
    clone_fields!(combs, pos);
}

impl<I> fmt::Debug for Powerset<I>
    where I: Iterator + fmt::Debug,
          I::Item: fmt::Debug,
{
    debug_fmt_fields!(Powerset, combs, pos);
}

/// Create a new `Powerset` from a clonable iterator.
pub fn powerset<I>(src: I) -> Powerset<I>
    where I: Iterator,
          I::Item: Clone,
{
    Powerset {
        combs: combinations(src, 0),
        pos: 0,
    }
}

impl<I> Iterator for Powerset<I>
    where
        I: Iterator,
        I::Item: Clone,
{
    type Item = Vec<I::Item>;

    fn next(&mut self) -> Option<Self::Item> {
        if let Some(elt) = self.combs.next() {
            self.pos = self.pos.saturating_add(1);
            Some(elt)
        } else if self.combs.k() < self.combs.n()
            || self.combs.k() == 0
        {
            self.combs.reset(self.combs.k() + 1);
            self.combs.next().map(|elt| {
                self.pos = self.pos.saturating_add(1);
                elt
            })
        } else {
            None
        }
    }

    fn size_hint(&self) -> (usize, Option<usize>) {
        // Total bounds for source iterator.
        let src_total = size_hint::add_scalar(self.combs.src().size_hint(), self.combs.n());

        // Total bounds for self ( length(powerset(set) == 2 ^ length(set) )
        let self_total = size_hint::pow_scalar_base(2, src_total);

        if self.pos < usize::MAX {
            // Subtract count of elements already yielded from total.
            size_hint::sub_scalar(self_total, self.pos)
        } else {
            // Fallback: self.pos is saturated and no longer reliable.
            (0, self_total.1)
        }
    }
}

impl<I> FusedIterator for Powerset<I>
    where
        I: Iterator,
        I::Item: Clone,
{}