//
// @file:
//  bsieve.cc
//
// @description:
//
//        Bounded Buffer Seive of Erastophenes.
//
//        Most implementations of the Seive use
//      a simple buffer O(n) in size.  This
//      buffer corresponds to an integer.
//      Starting from 2 on, all multiples
//      of 2 are marked as composite.  Then
//      the next prime 3 on, all multiples
//      of 3 are marked as composite.  And
//      so on.  This approach has a major
//      limitation in that in order to generate
//      n primes, it needs n sized memory buffer.
//      In this implementation, we use
//      a buffer whose size is fixed, i.e.,
//      bounded, and implement the seive
//      in this manner.  The bound on the memory
//      buffer does not limit our ability to
//      generate n primes.
//
// @author:
//
//      rdoss.com
//
#include <iostream>
#include <cstring>
using std::cout;
using std::cerr;
using std::endl;

#include "integer.h"
#include "types.h"
#include "esieve.h"

static const int unit = (1<<20);
static bool prime_tab  [unit];
static integer UNIT = CASTINT(unit);

#define P(symbol) cerr << symbol << endl

//
// esieve:
//
//    Generate primes using a sieve and a list
//  of discovered primes.  Unlike traditional
//  sieve implementations, this approach requires
//  a limited array to mark that the number
//  is a multiple, and a limited by system
//  memory list of primes which is constructed
//  during the sieving process.
//
void esieve( integer max, list_int_t *prime_list )
{
        integer start = TWO;
        bool found= false;
        integer next  = ONE;

        memset(prime_tab,0x0,unit);                    
        prime_list->push_back(TWO);
        prime_tab[0] = true;
        prime_tab[1] = true;

        do {
                /* Eliminate all duplicates. */
                for(integer i = start + start; i < UNIT; i += start) {
                        prime_tab[i.toUlong()] = true;
                }
                /* Find another number. */
                for(integer i = start+ONE; i < UNIT; i++) {
                        if(prime_tab[i.toUlong()] == false) {
                                if(i > max) {
                                        return;
                                }
                                prime_list->push_back(i);
                                start = i;
                                found = true;
                                break;
                        }
                }
                if(!found) {
                        break;
                } else {
                        found = false;
                }
        } while(start < max );

        if(start >= max) {
                /* We are done. */
                return;
        }

CONTINUE:

        memset(prime_tab,0x0,unit);
        /* We have a list of primes up to unit. */
        next++;
        /* We have to mark this as being
         * composite because its a multiple
         * of 2048 which is divisible by two.
         * Thus, looking at the algorithm
         * below, we always skip marking this
         * in our prime number generation.
         */
        prime_tab[0] = true;
        for(list_int_t::iterator i = prime_list->begin();
                                i != prime_list->end();
                                i++ ) {
                /* Mark which ones in unit * next
                 * space are multiples of known primes.
                 */
                for(integer j = (((UNIT * (next-ONE))/(*i)) + ONE) * (*i);
                                (j - (UNIT * (next-ONE))) < UNIT; j += (*i) ) {
            integer index = j - (UNIT * (next-ONE));
                        prime_tab[index.toUlong()] = true;
                }
        }
        /* So long as the square root of
         * (unit * next) is less than
         * the largest number in (unit * (next-1))
         * we can just grab all the numbers
         * marked false.  This is because
         * we are working linearly not
         * exponentially.  If we were working
         * exponentially, we would have
         * to write code that would
         * take the first 'false' element,
         * place it in the prime_list and
         * mark out its multiples.
         * However, the purpose of this
         * is to implement a seive that does
         * not require O(N) sized memory buffer
         * to determine the primes.
         * Therefore, expanding the
         * field exponentially is not
         * valid.
         */
        for(integer i = ZERO; i < UNIT; i++) {
                if(prime_tab[i.toUlong()] == false) {
                        prime_list->push_back(i + (UNIT * (next-ONE)));
                        if(i + (UNIT * (next-ONE)) > max) {
                                return;
                        }
                }
        }
        goto CONTINUE;

}// esieve
//
// EOF
//