use std::iter::{self, FromIterator};
use std::option;
use std::ops::Range;
macro_rules! gray_code_impl {
(#[$doc:meta] $nm:ident, $uint_ty:ty, $bits:expr, $test_name:ident, $test_bits:expr) => {
#[$doc]
#[derive(Clone, Debug)] pub struct $nm {
range: iter::Chain<Range<$uint_ty>, option::IntoIter<$uint_ty>>
}
impl $nm {
pub fn with_bits(bits: usize) -> $nm {
assert!(bits <= $bits);
$nm {
range: if bits == $bits {
(0..<$uint_ty>::max_value()).chain(Some(<$uint_ty>::max_value()).into_iter())
} else {
(0..((1 as $uint_ty) << bits)).chain(None.into_iter())
}
}
}
/// Construct an iterator over a specific range of Gray codes.
///
/// The range bounds need not be powers of 2.
pub fn over_range(range: Range<$uint_ty>) -> $nm {
$nm {
range: range.chain(None.into_iter())
}
}
/// Construct an iterator over all Gray codes.
///
/// This iterator yields all codes that fit in the
/// unsigned integer type.
#[inline]
pub fn all() -> $nm {
$nm::with_bits($bits)
}
/// Convert a binary value to the corresponding Gray code.
#[inline]
pub fn from_index(val: $uint_ty) -> $uint_ty {
val ^ (val >> 1)
}
/// Convert a Gray code from the corresponding binary value.
#[inline]
pub fn to_index(code: $uint_ty) -> $uint_ty {
let mut val = code;
// After macro expansion, these conditionals are
// constant and so will be optimized out, depending on
// the size of the unsigned integer type.
if $bits > 32 {
val = val ^ val.wrapping_shr(32);
}
if $bits > 16 {
val = val ^ val.wrapping_shr(16);
}
if $bits > 8 {
val = val ^ val.wrapping_shr(8);
}
val = val ^ (val >> 4);
val = val ^ (val >> 2);
val = val ^ (val >> 1);
val
}
/// Compute the next Gray code by flipping a single bit of
/// the argument.
pub fn next_code(code: $uint_ty) -> Option<$uint_ty> {
let j;
if code.count_ones() & 1 == 0 {
j = 0;
} else {
j = code.trailing_zeros() + 1;
if j == $bits {
return None;
}
}
return Some(code ^ (1<<j));
}
}
impl Iterator for $nm {
type Item = $uint_ty;
fn next(&mut self) -> Option<$uint_ty> {
self.range.next().map($nm::from_index)
}
fn size_hint(&self) -> (usize, Option<usize>) {
self.range.size_hint()
}
}
impl DoubleEndedIterator for $nm {
fn next_back(&mut self) -> Option<$uint_ty> {
self.range.next_back().map($nm::from_index)
}
}
#[test]
fn $test_name() {
// Each Gray code differs from the previous code by one bit.
{
let mut it = $nm::with_bits($test_bits);
let mut prev = it.next().unwrap();
for this in it {
assert!((this ^ prev).count_ones() == 1);
prev = this;
}
}
// And every code in 0..(1<<N) is returned exactly once.
let codes: Vec<$uint_ty> = $nm::with_bits($test_bits).collect();
assert!(codes.len() == (1<<$test_bits));
assert!((0..(1<<$test_bits)).all(|n| codes.contains(&(n as $uint_ty))));
// test the .from_index() and .to_index() methods
for (idx, code) in $nm::with_bits($test_bits).enumerate() {
let idx = idx as $uint_ty;
assert_eq!($nm::from_index(idx), code);
assert_eq!($nm::to_index(code), idx);
}
// test the .next_code() method
for (code, next_code) in Iterator::zip($nm::with_bits($test_bits),
$nm::all().skip(1)) {
assert!($nm::next_code(code) == Some(next_code));
}
}
}
}
gray_code_impl!(#[doc="Iterator over binary reflected Gray codes as u8 values"]
GrayCode8, u8, 8, gray_code_8, 8);
gray_code_impl!(#[doc="Iterator over binary reflected Gray codes as u16 values"]
GrayCode16, u16, 16, gray_code_16, 10);
gray_code_impl!(#[doc="Iterator over binary reflected Gray codes as u32 values"]
GrayCode32, u32, 32, gray_code_32, 11);
gray_code_impl!(#[doc="Iterator over binary reflected Gray codes as u64 values"]
GrayCode64, u64, 64, gray_code_64, 12);
/// Set mutation operations.
///
/// See the `InclusionExclusion` struct.
#[derive(Clone, Copy, Debug, Eq, PartialEq)]
pub enum SetMutation {
/// Add the item with the given index to the set.
Insert(usize),
/// Remove the item with the given index from the set.
Remove(usize)
}
/// Iterator yielding `SetMutation`s that can be used to efficiently
/// visit all subsets of n items
///
/// The pattern of use is to in-place mutate a working set by
/// following the `SetMutation` instructions, starting from an
/// initially empty set. Every subset will be generated, none will be
/// repeated, and only a single mutation per iteration is necessary.
///
/// # Examples
///
/// Visit every subset of a set of strings by mutating a `HashSet`.
///
/// ```
/// use std::collections::HashSet;
/// use gray_codes::{InclusionExclusion, SetMutation};
///
/// static STRINGS: &[&str] = &["apple", "moon", "pie"];
///
/// let mut subset = HashSet::new();
/// // Visit the empty set here, if desired.
/// println!("{:?}", subset);
/// for mutation in InclusionExclusion::of_len(STRINGS.len()) {
/// // Mutate the set, according to instructions.
/// match mutation {
/// SetMutation::Insert(i) => { subset.insert(STRINGS[i]); },
/// SetMutation::Remove(i) => { subset.remove(STRINGS[i]); },
/// }
/// // Visit the unique subset here.
/// println!("{:?}", subset);
/// }
/// ```
///
/// Iterate over the 15 possible ways to sum four numbers using only a
/// single addition or subtraction per iteration. This technique can
/// be used to brute-force [the subset sum
/// problem](https://en.wikipedia.org/wiki/Subset_sum_problem) faster
/// than the naive, obvious way.
///
/// ```
/// use gray_codes::{InclusionExclusion, SetMutation};
///
/// let addends = [235, 63, 856, 967];
///
/// let mut sum = 0;
/// for mutation in InclusionExclusion::of_len(addends.len()) {
/// match mutation {
/// SetMutation::Insert(i) => { sum += addends[i]; },
/// SetMutation::Remove(i) => { sum -= addends[i]; }
/// }
/// // Process the sum somehow.
/// println!("{}", sum);
/// }
/// ```
#[derive(Clone, Debug, Eq, PartialEq)]
pub struct InclusionExclusion {
focus_ptrs: Vec<u16>,
current_set: Vec<bool>
}
impl InclusionExclusion {
/// Constructor for an `InclusionExclusion` iterator over the
/// given number of objects.
///
/// See the struct documentation for examples.
///
/// # Panics
///
/// This method panics if either of the following conditions are
/// true:
///
/// - `item_count` is zero.
/// - `item_count` uses more than 16 bits.
///
pub fn of_len(item_count: usize) -> InclusionExclusion {
assert!(item_count > 0);
assert!(item_count <= u16::max_value() as usize);
InclusionExclusion {
focus_ptrs: (0..item_count as u16).collect(),
current_set: vec![false; item_count]
}
}
}
impl Iterator for InclusionExclusion {
type Item = SetMutation;
fn next(&mut self) -> Option<SetMutation> {
let j = self.focus_ptrs[0] as usize;
if j == self.focus_ptrs.len() {
None
} else {
self.focus_ptrs[0] = 0;
if j+1 == self.focus_ptrs.len() {
self.focus_ptrs[j] = self.focus_ptrs.len() as u16;
} else {
self.focus_ptrs[j] = self.focus_ptrs[j+1];
self.focus_ptrs[j+1] = j as u16 + 1;
}
// Flip an internal bit and return the corresponding
// instruction.
self.current_set[j] ^= true;
if self.current_set[j] {
Some(SetMutation::Insert(j))
} else {
Some(SetMutation::Remove(j))
}
}
}
}
#[test]
fn inclusion_exclusion() {
const N: usize = 12;
assert!(InclusionExclusion::of_len(N).count() == (1<<N)-1);
// Use the bits of a u32 to represent set inclusion/exclusion.
// This should match integer-valued gray codes exactly.
let mut x: u32 = 0;
let mut gray_codes = GrayCode32::with_bits(N);
assert!(gray_codes.next() == Some(0));
for (op, code) in Iterator::zip(InclusionExclusion::of_len(N),
gray_codes) {
match op {
SetMutation::Insert(i) => {
// Make sure it *isn't* already included first.
assert!(x & (1<<i) == 0);
x |= 1<<i;
},
SetMutation::Remove(i) => {
// Make sure it *is* already included first.
assert!(x & (1<<i) != 0);
x &= !(1<<i);
}
}
assert!(x == code);
}
}
/// Iterator yielding subsets of a slice
///
/// Use the static method `Subsets::of(...)` to construct this
/// iterator.
///
/// The input is a slice of type `&'a [T]` and the output is any
/// container `C` that is `FromIterator<&'a T>`. In many cases, it's
/// good enough for the collection `C` to be `Vec<&'a T>`, in which
/// case you can use the convenient `VecSubsets` type alias.
///
/// Note that a new container of type `C` is created each iteration,
/// which is an O(set_len) operation. It can be more efficient to use
/// the `InclusionExclusion` iterator to mutate your own container.
///
/// # Examples
///
/// Collect every subset of `0..4` into a `Vec` of `Vec`s.
///
/// ```
/// use gray_codes::VecSubsets;
/// static NUMBERS: &[u32] = &[0,1,2,3];
/// let mut subsets: Vec<_> = VecSubsets::of(NUMBERS).collect();
/// assert!(subsets.len() == 16);
/// assert!(subsets == vec![vec![],
/// vec![&0],
/// vec![&0,&1],
/// vec![&1],
/// vec![&1,&2],
/// vec![&0,&1,&2],
/// vec![&0,&2],
/// vec![&2],
/// vec![&2,&3],
/// vec![&0,&2,&3],
/// vec![&0,&1,&2, &3],
/// vec![&1,&2,&3],
/// vec![&1,&3],
/// vec![&0,&1,&3],
/// vec![&0,&3],
/// vec![&3]]);
/// ```
///
/// Collect every subset of characters from the word "cat" into a
/// `HashSet` of `String`s.
///
/// ```
/// # use gray_codes::Subsets;
/// # use std::collections::HashSet;
/// static CHARS: &[char] = &['c', 'a', 't'];
/// let subsets: HashSet<String> = Subsets::of(CHARS).collect();
/// assert!(subsets.len() == 8);
/// assert!(subsets.contains(""));
/// assert!(subsets.contains("c"));
/// assert!(subsets.contains("ca"));
/// assert!(subsets.contains("a"));
/// assert!(subsets.contains("at"));
/// assert!(subsets.contains("cat"));
/// assert!(subsets.contains("ct"));
/// assert!(subsets.contains("t"));
/// ```
#[derive(Clone, Debug)]
pub struct Subsets<'a, T:'a, C> {
items: &'a [T],
next: Option<C>,
inc_ex: InclusionExclusion
}
impl<'a, T:'a, C: FromIterator<&'a T>> Subsets<'a, T, C> {
/// Constructor.
pub fn of(items: &'a [T]) -> Subsets<'a, T, C> {
Subsets {
items: items,
next: Some(iter::empty().collect()),
inc_ex: InclusionExclusion::of_len(items.len())
}
}
}
impl<'a, T:'a, C: FromIterator<&'a T>> Iterator for Subsets<'a, T, C> {
type Item = C;
fn next(&mut self) -> Option<C> {
let ret = self.next.take();
if let Some(_) = self.inc_ex.next() {
let collection = self.inc_ex.current_set.iter().enumerate().flat_map(|(i,&b)| {
if b {
Some(&self.items[i])
} else {
None
}
}).collect();
self.next = Some(collection);
}
return ret;
}
}
/// Alias for iterating over `Vec`-valued subsets of a slice.
pub type VecSubsets<'a,T> = Subsets<'a, T, Vec<&'a T>>;
#[test]
fn subsets() {
static ITEMS: &[char] = &['a', 'b', 'c', 'd', 'e'];
let mut subsets_seen = Vec::new();
for subset in VecSubsets::of(ITEMS) {
assert!(!subsets_seen.contains(&subset));
subsets_seen.push(subset);
}
assert!(subsets_seen.len() == 1<<ITEMS.len());
}