1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
//! A primitive integer [`BitSet`] for high-performance combinatorics involving small numbers.
//!
//! # Scope
//!
//! This crate offers
//!
//! - zero-cost abstraction over bitwise operations without allocation or block management and
//! - a rich interface for mathematics/combinatorics involving integer sets.
//!
//! *pibs* is best suited when the bitset should abstract a mathematical set, the performance of set
//! operations is your primary concern, and the elements naturally lie in the representable range
//! (`0..128` for [`Set128`]). See [Alternatives](#alternatives) if this is not the case.
//!
//! The ambition of *pibs* is that you can't write faster code for any of its operations. If you
//! can, please open an issue!
//!
//! # Examples
//!
//! All examples assume the following import, which gives access to [`Set`] = [`BitSet<usize>`] and
//! [`set!`].
//!
//! ```
//! use pibs::prelude::*;
//! ```
//!
//! ## Subset sum problem
//!
//! The [subset sum problem](https://en.wikipedia.org/wiki/Subset_sum_problem) asks: does a given
//! set of integers have a subset with a particular sum?
//!
//! ### By bruteforce
//!
//! The following solves the problem by bruteforce. This is not efficient, but showcases the
//! [`subsets`](BitSet::subsets) iterator.
//!
//! ```
//! # use pibs::prelude::*;
//! fn subset_with_sum(set: Set, sum: usize) -> Option<Set> {
//! set.subsets().find(|subset| subset.sum() == sum)
//! }
//!
//! let set = set![4, 7, 10, 13, 18, 22, 27];
//! let solution = subset_with_sum(set, 30).unwrap();
//! assert_eq!(solution, set![7, 10, 13]);
//! ```
//!
//! ### Fast check for small sums
//!
//! For deciding the problem without recovering the subset, a faster implementation uses
//! [`truncating_subset_sums`](BitSet::truncating_subset_sums), which produces the set of
//! representable sums of all subsets of a set.
//!
//! ```
//! # use pibs::prelude::*;
//! fn has_subset_with_sum(set: Set, sum: usize) -> bool {
//! if sum > Set::MAX {
//! unimplemented!("the target sum must be representable");
//! }
//! set.truncating_subset_sums().contains(sum)
//! }
//!
//! let set = set![4, 7, 10, 13, 18, 22, 27];
//! assert_eq!(has_subset_with_sum(set, 30), true);
//! assert_eq!(has_subset_with_sum(set, 15), false);
//! ```
//!
//! ## Testing Sidon sets
//!
//! A set is a [Sidon set](https://en.wikipedia.org/wiki/Sidon_sequence) if every unordered pair of
//! elements (repetition allowed) has a unique sum. One can use the [`sumset`](BitSet::sumset)
//! operator (also known as Minkowski sum) to check this property given that every pair sum is
//! representable.
//!
//! ```
//! # use pibs::prelude::*;
//! use pibs::Error;
//!
//! fn is_sidon(set: Set) -> Result<bool, Error> {
//! let n = set.len();
//! Ok(set.sumset(set)?.len() == n * (n + 1) / 2)
//! }
//!
//! assert_eq!(is_sidon(set![1, 2, 3]), Ok(false)); // 2 + 2 = 1 + 3
//! assert_eq!(is_sidon(set![1, 2, 4, 8, 16]), Ok(true));
//! assert_eq!(is_sidon(set![1, 2, 4, 8, 16] + Set::MAX), Err(Error::Irrepresentable));
//! ```
//!
//! ## Minimum generating set
//!
//! The following computes by brute force a minimum-cardinality set of positive integers that
//! generate (by taking any subset of the numbers and summing them) all elements of a target set.
//! This is done using the [`iter_combinations(n, k)`](Set::iter_combinations) generator, which
//! yields all subsets of `0..n` of size `k`, and the
//! [`truncating_map_add`](BitSet::truncating_map_add) operation (`<<`), to shift these subsets to
//! `1..=n`.
//!
//! ```
//! # use pibs::prelude::*;
//! fn min_generating_set(set: Set) -> Set {
//! let max: usize = set.max().unwrap_or(0);
//! let bit_length = (usize::BITS - max.leading_zeros()) as usize; // ⌈log₂(max + 1)⌉
//!
//! // Test all subsets of 1..=max, grouped by increasing cardinality.
//! for size in 0..bit_length {
//! for generator in Set::iter_combinations(max, size).map(|g| g << 1) {
//! if set.is_subset(generator.truncating_subset_sums()) {
//! return generator;
//! }
//! }
//! }
//!
//! // If no small generator was found, fall back to powers of two.
//! Set::from_unchecked((0..bit_length).map(|b| 1 << b))
//! }
//!
//! // To generate {0, ..., 9}, we need a generating set of size four.
//! assert_eq!(min_generating_set(set![0..=9]), set![1, 2, 4, 8]);
//!
//! // But if we don't need to generate 2 and 7, three numbers suffice.
//! assert_eq!(min_generating_set(set![0..=9] - set![2, 7]), set![1, 3, 5]);
//! ```
//!
//! # Usage
//! ## Cheat Sheet
//!
//! M denotes the largest representable element [`BitSet::MAX`].
//!
//! ### Creation
//!
//! For using [`u128`]/`W` instead of [`usize`], replace [`Set`] with [`Set128`]/[`BitSet<W>`] and
//! [`set!`] with [`set128!`]/[`bitset![W; ...]`](bitset!).
//!
//! | set | short form | long form | checked variant
//! | --------------- | --------------- | --------- | ---------------
//! | ∅ | `set![]` | [`Set::new()`]
//! | {0} | `set![0]` | [`Set::singleton(0)`](BitSet::singleton)
//! | {a, b, c} | `set![a, b, c]` | [`Set::from_unchecked([a, b, c])`](BitSet::from_unchecked) | [`Set::try_from([a, b, c])`](BitSet::try_from)
//! | from `iter` | | [`Set::from_unchecked(iter)`](BitSet::from_unchecked) | [`Set::try_from_iter(iter)`](BitSet::try_from_iter)
//! | {m, ..., n} | `set![m..=n]` | [`Set::interval(m, n)`](BitSet::interval)
//! | {0, ..., n - 1} | `set![0..n]` | [`Set::range(n)`](BitSet::range)
//! | {0, ..., M} | | [`Set::full()`]
//!
//! ### Queries
//!
//! | set | short form | long form | unchecked variant | note
//! | --------------- | ---------- | --------- | ----------------- | ----
//! | \|A\| | | [`a.len()`](BitSet::len)
//! | min A, max A | | [`a.min()`](BitSet::min), [`a.max()`](BitSet::max)
//! | ∑(x : x ∈ A) | | [`a.sum()`](BitSet::sum)
//! | A = ∅ | | [`a.is_empty()`](BitSet::is_empty)
//! | A ⊆ B | `a <= b` | [`a.is_subset(b)`](BitSet::is_subset)
//! | A ⊇ B | `a >= b` | [`a.is_superset(b)`](BitSet::is_superset)
//! | A ⊂ B | `a < b` | [`a.is_strict_subset(b)`](BitSet::is_strict_subset)
//! | A ⊃ B | `a > b` | [`a.is_strict_superset(b)`](BitSet::is_strict_superset)
//! | A ∩ B ≠ ∅ | | [`a.intersects(b)`](BitSet::intersects)
//! | A ∩ B = ∅ | | [`a.is_disjoint(b)`](BitSet::is_disjoint)
//! | x ∈ A | | [`a.contains(x)`](BitSet::contains)
//! | A = {m, ..., n} | | [`a.is_interval()`](BitSet::is_interval)
//! | pos(x) | | [`a.position(x)`](BitSet::position) | [`a.position_unchecked(x)`](BitSet::position_unchecked) | indexed from zero
//! | rank(x) | | [`a.rank(x)`](BitSet::rank) | [`a.rank_unchecked(x)`](BitSet::rank_unchecked) | indexed from one
//!
//! ### Set operations
//!
//! | operation | short form | long form | mutating | mutating long form
//! | ----------- | ---------- | ----------------------------------------------------------- | --------- | ------------------
//! | A ∪ B | `a \| b` | [`a.union(b)`](BitSet::union) | `a \|= b` | [`a.union_update(b)`](BitSet::union_update)
//! | A ∩ B | `a & b` | [`a.intersection(b)`](BitSet::intersection) | `a &= b` | [`a.intersection_update(b)`](BitSet::intersection_update)
//! | A ∖ B | `a - b` | [`a.difference(b)`](BitSet::difference) | `a -= b` | [`a.difference_update(b)`](BitSet::difference_update)
//! | A ∆ B | `a ^ b` | [`a.symmetric_difference(b)`](BitSet::symmetric_difference) | `a ^= b` | [`a.symmetric_difference_update(b)`](BitSet::symmetric_difference_update)
//! | A ∪ {x} | `a + x` | [`a.with(x)`](BitSet::with) | `a += x` | [`a.insert(x)`](BitSet::insert)
//! | A ∖ {x} | `a - x` | [`a.without(x)`](BitSet::without) | `a -= x` | [`a.remove(x)`](BitSet::remove)
//! | A ← A ∆ {x} | | | | [`a.toggle(x)`](BitSet::toggle)
//! | A ← ∅ | | | | [`a.clear()`](BitSet::clear)
//!
//! ### Arithmetic operations
//!
//! Checked variants return [`Err(Irrepresentable)`](Error::Irrepresentable) if an output element
//! cannot be represented; truncating variants instead drop any values `< 0` or `> M`. The short
//! forms are truncating.
//!
//! | operation | definition | short form | mutating | checked variant | truncating variant
//! | --------- | ------------------------ | ---------- | --------- | ---------------------------------------- | ------------------
//! | A + B | {a + b \| a ∈ A ∧ b ∈ B} | `a + b` | `a += b` | [`a.sumset(b)`](BitSet::sumset) | [`a.truncating_sumset(b)`](BitSet::truncating_sumset)
//! | A + {x} | {a + x \| a ∈ A} | `a << x` | `a <<= x` | [`a.map_add(x)`](BitSet::map_add) | [`a.truncating_map_add(x)`](BitSet::truncating_map_add)
//! | A - {x} | {a - x \| a ∈ A} | `a >> x` | `a >>= x` | [`a.map_sub(x)`](BitSet::map_sub) | [`a.truncating_map_sub(x)`](BitSet::truncating_map_sub)
//! | A ± {x} | {a ± x \| a ∈ A} | | | [`a.translate(x)`](BitSet::translate) | [`a.truncating_translate(x)`](BitSet::truncating_translate)
//! | | {∑(x : x ∈ X) \| X ⊆ A} | | | [`a.subset_sums()`](BitSet::subset_sums) | [`a.truncating_subset_sums()`](BitSet::truncating_subset_sums)
//!
//! ### Generation
//!
//! Generation ordered "by size" (cardinality grows slowly) is slower by a factor of about 10.
//!
//! | example | iterator yields
//! | ---------------------------------------------------------- | ---------------
//! | [`Set::iter_all()`] | ∅, {0}, {1}, {0, 1}, {2}, {0, 2}, {1, 2}, {0, 1, 2}, {3}, ...
//! | [`Set::iter_all_by_size()`] | ∅, {0}, {1}, {2}, ..., {M}, {0, 1}, {0, 2}, {1, 2}, ..., {M, M - 1}, {0, 1, 2}, ...
//! | [`Set::iter_all_below(3)`](Set::iter_all_below) | ∅, {0}, {1}, {2}, {0, 1}, {0, 2}, {1, 2}, {0, 1, 2}
//! | [`Set::iter_combinations(4, 2)`](Set::iter_combinations) | {0, 1}, {0, 2}, {1, 2}, {0, 3}, {1, 3}, {2, 3}
//! | [`set![2, 4, 6].subsets()`](Set::subsets) | ∅, {2}, {4}, {2, 4}, {6}, {2, 6}, {4, 6}, {2, 4, 6}
//! | [`set![2, 4, 6].subsets_by_size()`](Set::subsets_by_size) | ∅, {2}, {4}, {6}, {2, 4}, {2, 6}, {4, 6}, {2, 4, 6}
//! | [`set![2, 4, 6].subsets_of_size(2)`](Set::subsets_of_size) | {2, 4}, {2, 6}, {4, 6}
//!
//! ## Installation
//!
//! Via one of the following `cargo` commands:
//!
//! ```sh
//! cargo add pibs # with default features
//! cargo add pibs --no-default-features # without default features
//! cargo add pibs -F serde # with 'serde' feature
//! ```
//!
//! Or by adding one of the following lines to `Cargo.toml` (replace `0.1` with the latest version):
//!
//! ```toml
//! [dependencies]
//! pibs = "0.1" # with default features
//! pibs = { version = "0.1", default-features = false } # without default features
//! pibs = { version = "0.1", features = ["serde"] } # with 'serde' feature
//! ```
//!
//! ## Features and dependencies
//!
//! | feature | default | implements
//! | ------- | ------- | ----------
//! | `alloc` | yes | conversion to and from [`Vec`](https://doc.rust-lang.org/alloc/vec/struct.Vec.html)
//! | `serde` | no | (de)serialization via [`serde`](https://serde.rs/)
//!
//! *pibs* is [no_std](https://docs.rust-embedded.org/book/intro/no-std.html)-compatible and its
//! only non-optional dependency is [`num_traits`].
//!
//! # Discussion
//! ## Pitfalls
//! ### Two overloads for the plus operator
//!
//! The `+` operator has two different meanings: for sets `a` and `b` and an element `x`, `a + b`
//! denotes the sumset (Minkowski sum) of `a` and `b`, whereas `a + x` denotes the union of `a` with
//! the singleton set containing `x`:
//!
//! ```
//! # use pibs::prelude::*;
//! let a = set![1, 2, 3];
//! let b = set![4];
//! let x = 4;
//! assert_eq!(a + b, set![5, 6, 7]); // sumset
//! assert_eq!(a + x, set![1, 2, 3, 4]); // singleton union
//! ```
//!
//! ### Bit-length precondition for non-builtin word types
//!
//! Currently, [`num_traits`] provides no trait that exposes the logical bit length of a [`Word`]
//! `W` at compile time. For this reason, *pibs* infers the logical bit length from the physical
//! one. This results in a precondition to using `BitSet<W>` that:
//!
//! ```
//! # use num_traits::Zero;
//! # type W = usize;
//! assert_eq!(size_of::<W>() * 8, W::zero().count_zeros() as usize);
//! ```
//!
//! ## Support for non-builtin word types
//!
//! The storage word trait [`Word`] has a blanket implementation and allows [`BitSet<W>`] to be used
//! with some non-builtin types `W`, say
//! [`bnum::types::U256`](https://docs.rs/bnum/latest/bnum/types/type.U256.html). This is partially
//! supported, with the following limitations:
//!
//! - There is a precondition on the word type `W`; see
//! [above](#bit-length-precondition-for-non-builtin-word-types).
//! - The [`Word`] trait may change in the future as new features are added.
//! - [`subsets_of_size`](BitSet::subsets_of_size) has a hard limit of 128 on the subset size,
//! regardless of [`Word`] type.
//! - [`subsets_by_size`](BitSet::subsets_by_size) would, in theory, stop after generating all
//! subsets of size 128.
//! - [`From<BitSet<W>>`](From::from) is only implemented for
//! [`Vec<T>`](https://doc.rust-lang.org/alloc/vec/struct.Vec.html) when `W` is a builtin type.
//! - Testing of non-builtin word types is very limited; benchmarking is non-existent.
//!
//! ## Performance
//! ### Impact of word size
//!
//! Benchmarking suggests that on a 64 bit system, [`BitSet`] operations are often equally fast for
//! the primitives [`u32`] and [`u64`], while using [`u8`], [`u16`], or [`u128`] for storage can
//! make them slower by a factor of about two. It is thus recommended to use [`Set128`] only when
//! needed for capacity, and [`BitSet<u8>`] to [`<u32>`](BitSet<u32>) only when memory use is a
//! concern or the platform has registers of the corresponding size. The default [`Set`] uses a
//! [`usize`] for best performance.
//!
//! ### Checks and preconditions
//!
//! As *pibs* aims for zero-cost abstraction, it prefers preconditions over runtime checks. In a
//! debug build, violating a stated precondition always panics. In a release build, no guarantees
//! with respect to the method's behavior are made: it may panic or produce unexpected results.
//! Runtime checks are only performed
//!
//! 1. if a foreign trait dictates it, or
//! 2. if a precondition on a method's arguments alone is not sufficient to ensure correct
//! operation.
//!
//! An example of the first condition is [`try_from`](TryFrom::try_from), which needs to ensure that
//! every number obtained from the source collection is at most [`BitSet::MAX`]. The second rule
//! applies to [`translate`](BitSet::translate): testing whether the outcome is representable
//! requires knowledge of the set's extremal elements in addition to the number being added, so the
//! method takes care of this check and returns a [`Result`]. On the other hand, a successful
//! [`insert`](BitSet::insert) only requires the argument to be within bounds, which is imposed by
//! a precondition.
//!
//! Whenever such runtime checks would occur in a release build, *pibs* offers alternative methods
//! that omit them. For example, [`from_unchecked`](BitSet::from_unchecked) has the precondition
//! that the source collection only contains representable elements, while
//! [`truncating_translate`](BitSet::truncating_translate) discards irrepresentable sums as a
//! zero-cost side effect of the shift used to compute the result.
//!
//! Creation macros such as [`set!`] bounds-check relevant arguments at compile time. This
//! introduces no runtime cost but requires those arguments to be constant expressions.
//!
//! ## Alternatives
//!
//! The obvious limitation of *pibs* is that its [`BitSet`] can only store numbers less than the bit
//! length of the underlying primitive. If your numbers can be larger than this but you know a
//! bound, consider using [fixedbitset](https://docs.rs/fixedbitset) (SIMD-optimized set
//! abstraction) or [bittle](https://docs.rs/bittle) (low-level bit manipulation) instead. If you
//! don't know your largest number ahead of time, then [bit-set](https://docs.rs/bit_set) (based on
//! [bit-vec](https://docs.rs/bit_vec)) or [roaring](https://docs.rs/roaring) (compressed
//! representation) may suit you.
// -------
// Modules
// -------
// -------
// Imports
// -------
use ;
use ;
// -------
// Exports
// -------
/// Hygienic re-exports used in creation macros.
/// Re-exports [`BitSet`], [`Set`], [`Set128`], and their creation macros.
pub use BitSet;
pub use Error;
pub use ;
/// Alias for [`BitSet<usize>`]; the set offering the best performance.
///
/// On 64 bit systems, this set can store integers between 0 and 63 (inclusive).
/// For numbers up to 127, use [`Set128`] at a possible performance cost.
pub type Set = ;
/// Alias for [`BitSet<u128>`]; the set with the highest capacity among builtin word types.
///
/// This set can store integers between 0 and 127 (inclusive).
/// For numbers smaller than the number of bits in a usize, use [`Set`] for best performance.
pub type Set128 = ;
/// Alias for [`usize`], the default input and output type for the numbers stored in a [`BitSet`].
pub type Element = usize;
/// A primitive unsigned integer that [`BitSet`] can use for storage.
// TODO: Once they are stable, turn Word into a trait alias.