gray_codes/lib.rs
1// gray-codes-rs: src/lib.rs
2//
3// Copyright 2017 David Creswick
4//
5// Licensed under the Apache License, Version 2.0, <LICENSE-APACHE or
6// http://apache.org/licenses/LICENSE-2.0> or the MIT license
7// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
8// option. This file may not be copied, modified, or distributed
9// except according to those terms.
10//
11// Unless required by applicable law or agreed to in writing, software
12// distributed under the License is distributed on an "AS IS" BASIS,
13// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or
14// implied. See the License for the specific language governing
15// permissions and limitations under the License.
16
17//! Gray code iterators and related utilities.
18//!
19//! A Gray code is a reordering of the integers such that adjacent
20//! codes differ by exactly one bit.
21//!
22//! The `GrayCode{8,16,32,64}` structs provide iterators over binary
23//! reflected Gray codes in various unsigned integer sizes as well as
24//! direct conversions to and from the codes. The `Subsets` struct
25//! provides a convenient way to iterate over subsets of a slice. The
26//! `InclusionExclusion` struct provides a building block for visiting
27//! all subsets more efficiently.
28use std::iter::{self, FromIterator};
29use std::option;
30use std::ops::Range;
31
32
33// FIXME: write tests that cover all the "Panics" sections
34
35
36macro_rules! gray_code_impl {
37 (#[$doc:meta] $nm:ident, $uint_ty:ty, $bits:expr, $test_name:ident, $test_bits:expr) => {
38 #[$doc]
39 ///
40 ///# Examples
41 ///
42 /// Generate all four-bit Gray codes.
43 ///
44 /// ```
45 /// use gray_codes::GrayCode32;
46 ///
47 /// assert_eq!(GrayCode32::with_bits(4).collect::<Vec<u32>>(),
48 /// vec![0b0000,
49 /// 0b0001,
50 /// 0b0011,
51 /// 0b0010,
52 /// 0b0110,
53 /// 0b0111,
54 /// 0b0101,
55 /// 0b0100,
56 /// 0b1100,
57 /// 0b1101,
58 /// 0b1111,
59 /// 0b1110,
60 /// 0b1010,
61 /// 0b1011,
62 /// 0b1001,
63 /// 0b1000]);
64 /// ```
65 ///
66 /// This could also be done with either of the other two constructors.
67 ///
68 /// ```
69 /// # use gray_codes::GrayCode32;
70 /// #
71 /// for (x,y) in Iterator::zip(GrayCode32::with_bits(4),
72 /// GrayCode32::over_range(0..(1<<4))) {
73 /// assert!(x == y);
74 /// }
75 ///
76 /// for (x,y) in Iterator::zip(GrayCode32::with_bits(4),
77 /// GrayCode32::all().take(1<<4)) {
78 /// assert!(x == y);
79 /// }
80 /// ```
81 #[derive(Clone, Debug)] // FIXME: it might be nice if this were PartialEq+Eq
82 pub struct $nm {
83 range: iter::Chain<Range<$uint_ty>, option::IntoIter<$uint_ty>>
84 }
85
86 impl $nm {
87 /// Construct an iterator over n-bit Gray codes.
88 ///
89 /// # Panics
90 ///
91 /// Panics if `bits` exceeds the bit-width of the unsigned
92 /// integer type.
93 pub fn with_bits(bits: usize) -> $nm {
94 assert!(bits <= $bits);
95 $nm {
96 range: if bits == $bits {
97 (0..<$uint_ty>::max_value()).chain(Some(<$uint_ty>::max_value()).into_iter())
98 } else {
99 (0..((1 as $uint_ty) << bits)).chain(None.into_iter())
100 }
101 }
102 }
103
104 /// Construct an iterator over a specific range of Gray codes.
105 ///
106 /// The range bounds need not be powers of 2.
107 pub fn over_range(range: Range<$uint_ty>) -> $nm {
108 $nm {
109 range: range.chain(None.into_iter())
110 }
111 }
112
113 /// Construct an iterator over all Gray codes.
114 ///
115 /// This iterator yields all codes that fit in the
116 /// unsigned integer type.
117 #[inline]
118 pub fn all() -> $nm {
119 $nm::with_bits($bits)
120 }
121
122 /// Convert a binary value to the corresponding Gray code.
123 #[inline]
124 pub fn from_index(val: $uint_ty) -> $uint_ty {
125 val ^ (val >> 1)
126 }
127
128 /// Convert a Gray code from the corresponding binary value.
129 #[inline]
130 pub fn to_index(code: $uint_ty) -> $uint_ty {
131 let mut val = code;
132 // After macro expansion, these conditionals are
133 // constant and so will be optimized out, depending on
134 // the size of the unsigned integer type.
135 if $bits > 32 {
136 val = val ^ val.wrapping_shr(32);
137 }
138 if $bits > 16 {
139 val = val ^ val.wrapping_shr(16);
140 }
141 if $bits > 8 {
142 val = val ^ val.wrapping_shr(8);
143 }
144 val = val ^ (val >> 4);
145 val = val ^ (val >> 2);
146 val = val ^ (val >> 1);
147 val
148 }
149
150 /// Compute the next Gray code by flipping a single bit of
151 /// the argument.
152 pub fn next_code(code: $uint_ty) -> Option<$uint_ty> {
153 let j;
154 if code.count_ones() & 1 == 0 {
155 j = 0;
156 } else {
157 j = code.trailing_zeros() + 1;
158 if j == $bits {
159 return None;
160 }
161 }
162 return Some(code ^ (1<<j));
163 }
164 }
165
166 impl Iterator for $nm {
167 type Item = $uint_ty;
168
169 fn next(&mut self) -> Option<$uint_ty> {
170 self.range.next().map($nm::from_index)
171 }
172
173 fn size_hint(&self) -> (usize, Option<usize>) {
174 self.range.size_hint()
175 }
176 }
177
178 impl DoubleEndedIterator for $nm {
179 fn next_back(&mut self) -> Option<$uint_ty> {
180 self.range.next_back().map($nm::from_index)
181 }
182 }
183
184 #[test]
185 fn $test_name() {
186 // Each Gray code differs from the previous code by one bit.
187 {
188 let mut it = $nm::with_bits($test_bits);
189 let mut prev = it.next().unwrap();
190 for this in it {
191 assert!((this ^ prev).count_ones() == 1);
192 prev = this;
193 }
194 }
195 // And every code in 0..(1<<N) is returned exactly once.
196 let codes: Vec<$uint_ty> = $nm::with_bits($test_bits).collect();
197 assert!(codes.len() == (1<<$test_bits));
198 assert!((0..(1<<$test_bits)).all(|n| codes.contains(&(n as $uint_ty))));
199
200 // test the .from_index() and .to_index() methods
201 for (idx, code) in $nm::with_bits($test_bits).enumerate() {
202 let idx = idx as $uint_ty;
203 assert_eq!($nm::from_index(idx), code);
204 assert_eq!($nm::to_index(code), idx);
205 }
206
207 // test the .next_code() method
208 for (code, next_code) in Iterator::zip($nm::with_bits($test_bits),
209 $nm::all().skip(1)) {
210 assert!($nm::next_code(code) == Some(next_code));
211 }
212 }
213 }
214}
215
216gray_code_impl!(#[doc="Iterator over binary reflected Gray codes as u8 values"]
217 GrayCode8, u8, 8, gray_code_8, 8);
218gray_code_impl!(#[doc="Iterator over binary reflected Gray codes as u16 values"]
219 GrayCode16, u16, 16, gray_code_16, 10);
220gray_code_impl!(#[doc="Iterator over binary reflected Gray codes as u32 values"]
221 GrayCode32, u32, 32, gray_code_32, 11);
222gray_code_impl!(#[doc="Iterator over binary reflected Gray codes as u64 values"]
223 GrayCode64, u64, 64, gray_code_64, 12);
224
225
226/// Set mutation operations.
227///
228/// See the `InclusionExclusion` struct.
229#[derive(Clone, Copy, Debug, Eq, PartialEq)]
230pub enum SetMutation {
231 /// Add the item with the given index to the set.
232 Insert(usize),
233 /// Remove the item with the given index from the set.
234 Remove(usize)
235}
236
237
238/// Iterator yielding `SetMutation`s that can be used to efficiently
239/// visit all subsets of n items
240///
241/// The pattern of use is to in-place mutate a working set by
242/// following the `SetMutation` instructions, starting from an
243/// initially empty set. Every subset will be generated, none will be
244/// repeated, and only a single mutation per iteration is necessary.
245///
246/// # Examples
247///
248/// Visit every subset of a set of strings by mutating a `HashSet`.
249///
250/// ```
251/// use std::collections::HashSet;
252/// use gray_codes::{InclusionExclusion, SetMutation};
253///
254/// static STRINGS: &[&str] = &["apple", "moon", "pie"];
255///
256/// let mut subset = HashSet::new();
257/// // Visit the empty set here, if desired.
258/// println!("{:?}", subset);
259/// for mutation in InclusionExclusion::of_len(STRINGS.len()) {
260/// // Mutate the set, according to instructions.
261/// match mutation {
262/// SetMutation::Insert(i) => { subset.insert(STRINGS[i]); },
263/// SetMutation::Remove(i) => { subset.remove(STRINGS[i]); },
264/// }
265/// // Visit the unique subset here.
266/// println!("{:?}", subset);
267/// }
268/// ```
269///
270/// Iterate over the 15 possible ways to sum four numbers using only a
271/// single addition or subtraction per iteration. This technique can
272/// be used to brute-force [the subset sum
273/// problem](https://en.wikipedia.org/wiki/Subset_sum_problem) faster
274/// than the naive, obvious way.
275///
276/// ```
277/// use gray_codes::{InclusionExclusion, SetMutation};
278///
279/// let addends = [235, 63, 856, 967];
280///
281/// let mut sum = 0;
282/// for mutation in InclusionExclusion::of_len(addends.len()) {
283/// match mutation {
284/// SetMutation::Insert(i) => { sum += addends[i]; },
285/// SetMutation::Remove(i) => { sum -= addends[i]; }
286/// }
287/// // Process the sum somehow.
288/// println!("{}", sum);
289/// }
290/// ```
291#[derive(Clone, Debug, Eq, PartialEq)]
292pub struct InclusionExclusion {
293 focus_ptrs: Vec<u16>,
294 current_set: Vec<bool>
295}
296
297impl InclusionExclusion {
298 /// Constructor for an `InclusionExclusion` iterator over the
299 /// given number of objects.
300 ///
301 /// See the struct documentation for examples.
302 ///
303 /// # Panics
304 ///
305 /// This method panics if either of the following conditions are
306 /// true:
307 ///
308 /// - `item_count` is zero.
309 /// - `item_count` uses more than 16 bits.
310 ///
311 pub fn of_len(item_count: usize) -> InclusionExclusion {
312 assert!(item_count > 0);
313 assert!(item_count <= u16::max_value() as usize);
314 InclusionExclusion {
315 focus_ptrs: (0..item_count as u16).collect(),
316 current_set: vec![false; item_count]
317 }
318 }
319}
320
321impl Iterator for InclusionExclusion {
322 type Item = SetMutation;
323
324 fn next(&mut self) -> Option<SetMutation> {
325 let j = self.focus_ptrs[0] as usize;
326 if j == self.focus_ptrs.len() {
327 None
328 } else {
329 self.focus_ptrs[0] = 0;
330 if j+1 == self.focus_ptrs.len() {
331 self.focus_ptrs[j] = self.focus_ptrs.len() as u16;
332 } else {
333 self.focus_ptrs[j] = self.focus_ptrs[j+1];
334 self.focus_ptrs[j+1] = j as u16 + 1;
335 }
336 // Flip an internal bit and return the corresponding
337 // instruction.
338 self.current_set[j] ^= true;
339 if self.current_set[j] {
340 Some(SetMutation::Insert(j))
341 } else {
342 Some(SetMutation::Remove(j))
343 }
344 }
345 }
346}
347
348#[test]
349fn inclusion_exclusion() {
350 const N: usize = 12;
351 assert!(InclusionExclusion::of_len(N).count() == (1<<N)-1);
352 // Use the bits of a u32 to represent set inclusion/exclusion.
353 // This should match integer-valued gray codes exactly.
354 let mut x: u32 = 0;
355 let mut gray_codes = GrayCode32::with_bits(N);
356 assert!(gray_codes.next() == Some(0));
357 for (op, code) in Iterator::zip(InclusionExclusion::of_len(N),
358 gray_codes) {
359 match op {
360 SetMutation::Insert(i) => {
361 // Make sure it *isn't* already included first.
362 assert!(x & (1<<i) == 0);
363 x |= 1<<i;
364 },
365 SetMutation::Remove(i) => {
366 // Make sure it *is* already included first.
367 assert!(x & (1<<i) != 0);
368 x &= !(1<<i);
369 }
370 }
371 assert!(x == code);
372 }
373}
374
375
376/// Iterator yielding subsets of a slice
377///
378/// Use the static method `Subsets::of(...)` to construct this
379/// iterator.
380///
381/// The input is a slice of type `&'a [T]` and the output is any
382/// container `C` that is `FromIterator<&'a T>`. In many cases, it's
383/// good enough for the collection `C` to be `Vec<&'a T>`, in which
384/// case you can use the convenient `VecSubsets` type alias.
385///
386/// Note that a new container of type `C` is created each iteration,
387/// which is an O(set_len) operation. It can be more efficient to use
388/// the `InclusionExclusion` iterator to mutate your own container.
389///
390/// # Examples
391///
392/// Collect every subset of `0..4` into a `Vec` of `Vec`s.
393///
394/// ```
395/// use gray_codes::VecSubsets;
396/// static NUMBERS: &[u32] = &[0,1,2,3];
397/// let mut subsets: Vec<_> = VecSubsets::of(NUMBERS).collect();
398/// assert!(subsets.len() == 16);
399/// assert!(subsets == vec![vec![],
400/// vec![&0],
401/// vec![&0,&1],
402/// vec![&1],
403/// vec![&1,&2],
404/// vec![&0,&1,&2],
405/// vec![&0,&2],
406/// vec![&2],
407/// vec![&2,&3],
408/// vec![&0,&2,&3],
409/// vec![&0,&1,&2, &3],
410/// vec![&1,&2,&3],
411/// vec![&1,&3],
412/// vec![&0,&1,&3],
413/// vec![&0,&3],
414/// vec![&3]]);
415/// ```
416///
417/// Collect every subset of characters from the word "cat" into a
418/// `HashSet` of `String`s.
419///
420/// ```
421/// # use gray_codes::Subsets;
422/// # use std::collections::HashSet;
423/// static CHARS: &[char] = &['c', 'a', 't'];
424/// let subsets: HashSet<String> = Subsets::of(CHARS).collect();
425/// assert!(subsets.len() == 8);
426/// assert!(subsets.contains(""));
427/// assert!(subsets.contains("c"));
428/// assert!(subsets.contains("ca"));
429/// assert!(subsets.contains("a"));
430/// assert!(subsets.contains("at"));
431/// assert!(subsets.contains("cat"));
432/// assert!(subsets.contains("ct"));
433/// assert!(subsets.contains("t"));
434/// ```
435#[derive(Clone, Debug)]
436pub struct Subsets<'a, T:'a, C> {
437 items: &'a [T],
438 next: Option<C>,
439 inc_ex: InclusionExclusion
440}
441
442impl<'a, T:'a, C: FromIterator<&'a T>> Subsets<'a, T, C> {
443 /// Constructor.
444 pub fn of(items: &'a [T]) -> Subsets<'a, T, C> {
445 Subsets {
446 items: items,
447 next: Some(iter::empty().collect()),
448 inc_ex: InclusionExclusion::of_len(items.len())
449 }
450 }
451}
452
453impl<'a, T:'a, C: FromIterator<&'a T>> Iterator for Subsets<'a, T, C> {
454 type Item = C;
455
456 fn next(&mut self) -> Option<C> {
457 let ret = self.next.take();
458 if let Some(_) = self.inc_ex.next() {
459 let collection = self.inc_ex.current_set.iter().enumerate().flat_map(|(i,&b)| {
460 if b {
461 Some(&self.items[i])
462 } else {
463 None
464 }
465 }).collect();
466 self.next = Some(collection);
467 }
468 return ret;
469 }
470}
471
472/// Alias for iterating over `Vec`-valued subsets of a slice.
473pub type VecSubsets<'a,T> = Subsets<'a, T, Vec<&'a T>>;
474
475#[test]
476fn subsets() {
477 static ITEMS: &[char] = &['a', 'b', 'c', 'd', 'e'];
478 let mut subsets_seen = Vec::new();
479 for subset in VecSubsets::of(ITEMS) {
480 assert!(!subsets_seen.contains(&subset));
481 subsets_seen.push(subset);
482 }
483 assert!(subsets_seen.len() == 1<<ITEMS.len());
484}