/*   HW #4 - Solution 1                                              */

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

/*   The idea is to maintain a pointer to the last filter.           */
/*   In this solution such pointer if defined as a member            */
/*   of Counter. When a filter detects a new prime number,           */
/*   it creates the corresponding new filter and it returns          */
/*   the pointer to it to the previous item. When such pointer       */
/*   is finally returned to the Counter, the counter sets the        */
/*   last element to be this new filter.                              */

#include <iostream.h> 
        
class Item { 
   protected:
      Item* destination; 
   public:
      ~Item(){ delete destination; }
      void set_destination(Item* dst){ destination = dst; }
      virtual Item* in(int n){};
};

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

class Counter: public Item { 
      Item* last_filter;
      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) { 
              Item* temp = destination->in(value++);
              if (temp != NULL){ 
                 last_filter -> set_destination(temp);
                 last_filter = temp;
              }
           }
      } 
}; 

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

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