/*   HW #4 - Solution 3                                                    */

/*   Eratosthenes' Sieve, Data driven model, optimized                     */

/*   The idea is to mantain a pointer to the last filter                   */
/*   In this solution such pointer if defined as a static member of Item   */

#include <iostream.h> 
        
class Item { 
   protected:
      static Item* last_filter;
      Item* destination; 
   public:
      ~Item(){ delete destination; }
      void set_destination(Item* dst){ destination = dst; }
      virtual void in(int n){} // to be overriden in the subclasses
};

class Filter: public Item {
      int factor;
   public:
      Filter(int f){ factor = f; destination = NULL; }
      void in(int n) {
           if (n%factor == 0) return;
           if (n < (factor*factor)) {
              Item * temp = new Filter(n);
              last_filter -> set_destination(temp);
              last_filter = temp;
              cout << "The next prime number is " << n << " (detected by filter "<< factor << ")\n";
           } 
           else if (destination != NULL) 
                   destination -> in(n);
                else {   // this case should never occur (cfr. the Prime number Theorem)
                   last_filter = destination = new Filter(n); 
                   cout << "The next prime number is " << n << '\n';
                }
      }
};

class Counter: public Item { 
      int value; 
      int max;
   public: 
      Counter(int m){ max = m; } 
      void start(){
           if (max < 2) return;
           last_filter = destination = new Filter(2);
           cout << "The first prime number is " << 2 << '\n';
           value = 3;
           while (value <= max) destination->in(value++); 
      } 
}; 

class EratostenesSieve{
      int max;
      Counter* gen;
   public:
      EratostenesSieve(int m){ max = m; }
      void start(){     
           gen = new Counter(max);
           gen->start();
      }
      ~EratostenesSieve(){ delete gen; }
};

Item* Item::last_filter = NULL;

void main() {
        int max;
        cout << "Please input the max number to be generated" << '\n';
        cin >> max;
        EratostenesSieve es(max);
        es.start();
        cout << "End\n";
}