typenum_prime/lib.rs
1// src/lib.rs
2//
3// Copyright (c) 2018 David Creswick
4//
5// Licensed under the Apache License, Version 2.0
6// <LICENSE-APACHE or http://www.apache.org/licenses/LICENSE-2.0> or the MIT
7// license <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
8// option. All files in the project carrying such notice may not be copied,
9// modified, or distributed except according to those terms.
10
11//! Compile-time primality testing of `typenum` integers.
12//!
13//! The current algorithm is trial division by every prime number from
14//! `2` up to `next_integer_power_of_two(sqrt(n))`. The default
15//! compiler recursion limit could sometimes be insufficient,
16//! depending on the magnitude of the integer being tested. When
17//! necessary, raise it using a crate attribute:
18//!
19//! ```
20//! #![recursion_limit="128"]
21//! ```
22//!
23//! ## Example
24//!
25//! The intended use of this crate is to put a bound on type-level
26//! integer parameters so the compiler enforces their primality. For
27//! instance, you might want the number of buckets in a
28//! statically-sized hash table to always be a prime number so that
29//! hash collisions are reduced. Now you can let the compiler enforce
30//! this constraint.
31//!
32//! ```ignore
33//! pub struct StaticHashTable<K,V,N>
34//! where N: Prime + ArrayLength<Option<(K,V)>> {
35//! buckets: GenericArray<Option<(K,V)>,N>
36//! }
37//! ```
38
39#![no_std]
40#![warn(missing_docs)]
41
42#[cfg_attr(test, macro_use)] pub extern crate typenum;
43
44use typenum::marker_traits::{Bit, Unsigned};
45use typenum::consts::True;
46
47use private::PrivateIsPrime;
48
49
50#[doc(hidden)]
51pub mod private;
52
53
54// Test all integers from 0 through 1024, inclusive.
55#[cfg(test)] pub mod test_small_constants;
56
57
58/// **Type operator** for primality testing.
59///
60/// This trait is implemented for all unsignd integers from the
61/// `typenum` crate.
62pub trait IsPrime: Unsigned {
63 /// A boolean indicating the result of the primality test.
64 type Output: Bit;
65}
66
67impl<N> IsPrime for N where N: Unsigned + PrivateIsPrime {
68 type Output = <N as PrivateIsPrime>::Output;
69}
70
71
72/// **Marker trait** for prime, unsigned integers; equivalent to `IsPrime<Output=True>`
73///
74/// This trait is automatically implemented for unsigned integers from
75/// the `typenum` crate that are prime. It is not defined for 0, 1,
76/// and composite integers.
77pub trait Prime: Unsigned {}
78
79impl<N> Prime for N where N: Unsigned + IsPrime<Output=True> {}