#include <iostream>
#include <list>
#include <boost/foreach.hpp>
#include <time.h>


struct Base{
 int idLev1;
 int idLev2;
 Base(int a, int b)
 {
    idLev1 = a;
    idLev2 = b;
 }
 // just for dynamic cast
 virtual ~Base(){}
};

struct DerivedA : public  Base
{
   DerivedA(): Base(1,1){}
};

struct DerivedB : public  Base
{
   DerivedB(): Base(2,1){}
};

struct DerivedC : public  Base
{
   DerivedC(): Base(3,1){}
   DerivedC(int a, int b): Base(a,b){}
};

struct DerivedX : public  DerivedC
{
   DerivedX(): DerivedC(3,2){}
};

struct DerivedY : public  DerivedC
{
DerivedY(): DerivedC(3,3){}
};


template<class T>
void findDerived(const std::list<Base*> &base, int& c, double& itime)
{
  double tstart, tend;
  tstart = (double)clock()/CLOCKS_PER_SEC;
  BOOST_FOREACH(Base* x,base)
  {
  
   if(dynamic_cast<T>(x)) ++c;
  
  }

  tend = (double)clock()/CLOCKS_PER_SEC;
  itime += tend - tstart;

}

void findNumber(const std::list<Base*> &base, const int a, const int b, int &c, double& itime)
{
  
  double tstart, tend;
  tstart= (double)clock()/CLOCKS_PER_SEC;
  BOOST_FOREACH(Base* x,base)
  {
   if(x->idLev1 == a && x->idLev2 == b) ++c;
  }
  tend = (double)clock()/CLOCKS_PER_SEC;
  itime += tend - tstart;

}
int main() {
        std::list <Base*> b;
	for (int i = 1; i<1999000; ++i){
	 if (rand()%2) b.push_back(new DerivedA());
	 if (rand()%2) b.push_back(new DerivedB());
	 if (rand()%2) b.push_back(new DerivedC());
	 if (rand()%2) b.push_back(new DerivedX());
	 if (rand()%2) b.push_back(new DerivedY());
       }

       int c=0;int d=0;
       double itime1=0; double itime2=0;
       std::cout << "Method a\n";

       findDerived<DerivedA*>(b, c, itime1);
       findDerived<DerivedB*>(b, c, itime1);
       findDerived<DerivedC*>(b, c, itime1);
       findDerived<DerivedX*>(b, c, itime1);
       findDerived<DerivedY*>(b, c, itime1);
       std::cout << "Method a\n";
       findNumber<DerivedA*>(b, d, itime2);
       findNumber<DerivedB*>(b, d, itime2);
       findNumber<DerivedC*>(b, d, itime2);
       findNumber<DerivedX*>(b, d, itime2);
       findNumber<DerivedY*>(b, d, itime2);
       std::cout << "Time method a " << itime1 << "count " << c << std::endl;
       std::cout << "Time method b " << itime2 << "count " << d << std::endl;
	return 0;
}