Sieve of Eratosthenes in RUST

eratosthenes_sieve.rs

//! Simple module to implement [Sieve of Eratosthenes](https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes).
//! It implements both clasical sieve (starting from 2 to given limit) and segmented sieve (from min to max).
//! # Examples
//!
//! Primes under 20:
//!
//! ```
//! use numbers::sieve::{Sieve,Eratosthenes};
//! let s = Eratosthenes::new(20);
//! assert_eq!(s.first(), Some(2));
//! assert_eq!(s.last(), Some(19));
//! assert_eq!(s.count(), 8);
//! let all:Vec<_> = s.iter().collect();
//! assert_eq!(all, [2,3,5,7,11,13,17,19]);
//! ```

#[macro_use]
extern crate quick_error;
extern crate bit_vec;
use self::bit_vec::BitVec;

quick_error! {
#[derive(Debug, PartialEq)]
pub enum SieveError {
    NotInRange{
        description("value is not in seive's range")
    }
}
}
/// Trait for a sieve
pub trait Sieve  {
    /// Returns iterator over all primes in the sieve
    fn iter(&self) -> SieveIter;
    /// Test primarity, number must be in sieve's range
    /// otherwise error is returned
    ///
    /// # Failures
    /// - num is not in sieve's range
    fn is_prime(&self, num: usize) -> Result<bool, SieveError>;
    /// Number of primes in the sieve
    fn count(&self) -> usize {
        self.iter().count()
    }
    /// First/smallet prime in the sieve
    /// None if sieve is empty
    fn first(&self) -> Option<usize> {
        self.iter().nth(0)
    }
    /// Last/biggest prime in the sieve
    /// None if sieve is empty
    fn last(&self) -> Option<usize> {
        self.iter().last()
    }
}

/// Clasical sieve of Erathosthenes stars from 2 up to limit
pub struct Eratosthenes {
    size: usize,
    sieve: BitVec,
}


impl Eratosthenes {
    /// create thieve with all primes lower then max
    ///
    /// # Panics
    /// if max is smaller then 2

    pub fn new(max: usize) -> Self {
        assert!(max >= 2);
        let mut v = BitVec::from_elem(max, true);
        v.set(0, false);
        v.set(1, false);
        let mut s = Eratosthenes {
            size: max,
            sieve: v,
        };
        s.init();
        s
    }

    fn init(&mut self) {
        let mut p = 2;
        while p < 1 + (self.size as f64).sqrt() as usize {
            let mut i = p + p;
            while i < self.size {
                self.sieve.set(i, false);
                i += p;
            }
            p += 1;
            while p < self.size && !self.sieve[p] {
                p += 1;
            }
        }

    }
}

impl Sieve for Eratosthenes {

        fn is_prime(&self, num: usize) -> Result<bool, SieveError> {
        if num >= self.size {
            return Err(SieveError::NotInRange)
        }
        Ok(self.sieve[num])
    }


    fn iter(&self) -> SieveIter {
        SieveIter { curr: 1, s: &self.sieve, offset:0, curr_back: self.sieve.len() }
    }
}

/// Iterator for a sieve
/// can also iterate from end
pub struct SieveIter<'a> {
    curr: usize,
    curr_back: usize,
    offset: usize,
    s: &'a BitVec,
}

impl<'a> Iterator for SieveIter<'a> {
    type Item = usize;

    fn next(&mut self) -> Option<Self::Item> {
        self.curr += 1;
        while self.curr < self.curr_back && !self.s[self.curr] {
            self.curr += 1;
        }
        if self.curr >= self.curr_back {
            None
        } else {
            Some(self.curr+self.offset)
        }
    }
}

impl<'a> DoubleEndedIterator for SieveIter<'a> {
    
    fn next_back(&mut self) -> Option<Self::Item> {
        self.curr_back -= 1;
        while self.curr_back > self.curr && !self.s[self.curr_back] {
            self.curr_back -= 1;
        }
        if self.curr_back <= self.curr {
            None
        } else {
            Some(self.curr_back+self.offset)
        }
    }
}

impl<'a> IntoIterator for &'a Eratosthenes {
    type Item = usize;
    type IntoIter = SieveIter<'a>;
    fn into_iter(self) -> Self::IntoIter {
        self.iter()
    }
}

/// Segmeneted sieve of Eratosthenes
/// contains primes from certain limit
pub struct EratosthenesSegmented {
    min:usize,
    max:usize,
    sieve:BitVec
}

impl EratosthenesSegmented {
    /// creates segmented sieve with primes bigger then min 
    /// and smaller then max
    ///
    /// # Panics
    /// if min>= max
    ///
    pub fn new(min: usize, max:usize)  -> Self {
        assert!(min<max);
        let mut s = EratosthenesSegmented{
            min, max, 
            sieve: BitVec::from_elem(max-min, true)
        };
        s.init();
        s
    }

    fn init(&mut self)  {
        let primes = Eratosthenes::new((self.max as f64).sqrt() as usize);
        for p in primes.into_iter() {
            let start=(self.min/p)*p;
            let mut idx = if start < self.min {
                p - (self.min-start)
                } else {
                    0
                };

            
            while idx < self.max - self.min {
                self.sieve.set(idx,false);
                idx+=p;
            }
        }

    }
}

impl Sieve for EratosthenesSegmented {
    fn is_prime(&self, num: usize) -> Result<bool, SieveError> {
        if num >= self.max || num< self.min {
            return Err(SieveError::NotInRange)
        }
        Ok(self.sieve[num-self.min])
    }


    fn iter(&self) -> SieveIter {
        SieveIter { curr: 0, s: &self.sieve, offset:self.min, curr_back: self.sieve.len() }
    }
}


#[cfg(test)]
mod tests {
    use super::*;
    
    #[test]
    fn twenty_primes() {
        let s = Eratosthenes::new(100);
        let v: Vec<_> = s.into_iter().take(20).collect();
        assert_eq!(
            v,
            [ 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, ]
        );

    }

    #[test]
    fn ten_primes_from_end() {
        let s = Eratosthenes::new(100);
        let v: Vec<_> = s.into_iter().rev().take(10).collect();
        assert_eq!(
            v,
            [ 97, 89, 83, 79, 73, 71, 67, 61, 59, 53, ]
        );

    }


    #[test]
    fn all_primes() {
        let s = Eratosthenes::new(100);
        let v: Vec<_> = s.into_iter().collect();
        assert_eq!(
            v,
            [ 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, ]
        );
        assert_eq!(s.count(), 25)
    }

    #[test]
    fn test_fns() {
        let s = Eratosthenes::new(100);
        assert_eq!(s.first(), Some(2) );
        assert_eq!(s.last(), Some(97));
        assert_eq!(s.count(), 25);
    }

    #[test]
    fn test_sieve() {

        let s = Eratosthenes::new(100);
        assert!(!s.is_prime(1).unwrap());
        assert!(s.is_prime(2).unwrap());
        assert!(s.is_prime(3).unwrap());
        assert!(!s.is_prime(4).unwrap());
        assert!(s.is_prime(5).unwrap());
        assert!(s.is_prime(17).unwrap());
        assert!(s.is_prime(97).unwrap());
        assert!(!s.is_prime(99).unwrap());
        assert_eq!(s.is_prime(100), Err(SieveError::NotInRange));

    }

    
    #[test]
    #[ignore]
    fn test_very_big() {
        let big_prime = 982_451_653;
        let s = Eratosthenes::new(big_prime+1);
        assert_eq!(s.last(), Some(big_prime));
        assert_eq!(s.count(), 50_000_000);
    }

    #[test]
    #[ignore]
    fn test_big() {
        let big_prime = 15_485_863;
        let s = Eratosthenes::new(big_prime+1);
        assert_eq!(s.last(), Some(big_prime));
        assert_eq!(s.count(), 1_000_000);
    }

    #[test]
    fn test_segmented() {
        let s = EratosthenesSegmented::new(100, 200);
        let v: Vec<_> = s.iter().collect();
        assert_eq!(v,
    [101, 103, 107, 109, 113 , 127, 131, 137, 139, 149, 151, 157, 163, 167, 173 , 179, 181, 191, 193, 197, 199]);
        assert!(s.is_prime(101).unwrap());
        assert!(s.is_prime(199).unwrap());
        assert_eq!(s.is_prime(200), Err(SieveError::NotInRange));
    }

    #[test]
    #[ignore]
    fn test_segmented_big() {
        let first = 15_485_867;
        let last = 32_452_843;
        let s = EratosthenesSegmented::new(first-1, last+1);
        assert_eq!(s.first(), Some(first));
        assert_eq!(s.last(), Some(last));
        assert_eq!(s.count(), 1_000_000);
    }
}