#include <nstl/balloc.hpp>
#include <boost/pool/pool_alloc.hpp>
#include <list>
#include <map>
#include <algorithm>
#include <nstl/timer.hpp>
#include <cstdlib>
#include <iostream>

using namespace std;

using nstd::bitmap_allocator;


int main ()
{
  nstd::timer t;

  typedef std::list<int, bitmap_allocator<int> > My_List;
  //typedef std::map <int, int, bitmap_allocator<int> > My_List;

  //typedef std::list<int> My_List;
  //  typedef std::list<int, boost::fast_pool_allocator<int> > My_List;

  //typedef std::map <int, int> My_List;


  //std::list<int, nstd::node_allocator<int> > il1;
  //  nstd::node_allocator<int> ba;

  My_List il1;

  int ctr = 3;
  while (ctr--)
    {

  t.start ();

  for (int i = 0; i < 650000; ++i)
    //  il1.insert (make_pair (rand()%10001, i));
    il1.push_back (rand()%50001);

  t.stop ();

  cout<<"Time Taken to Insert: "<<t.difference()<<" Seconds."<<endl;

  //Search for random values that may or may not belong to the list.
  t.start ();
  for (int i = 0; i < 50; ++i)
    //il1.find (rand()%20001);
    std::find (il1.begin(), il1.end(), rand()%100001);

  t.stop ();
  cout<<"Time Taken to Search: "<<t.difference()<<" Seconds."<<endl;


  My_List::iterator i = il1.begin();

  int LSize = il1.size ();
  std::advance (i, LSize/2);

  cout<<"Size is: "<<LSize<<endl;

  t.start ();
  il1.sort ();
  t.stop ();

  cout<<"Time Taken to Sort: "<<t.difference()<<" Seconds."<<endl;

  //Search for random values that may or may not belong to the list.
  t.start ();
  for (int i = 0; i < 50; ++i)
    //    il1.find (rand()%20001);
    std::find (il1.begin(), il1.end(), rand()%100001);

  t.stop ();
  cout<<"Time Taken to Search: "<<t.difference()<<" Seconds."<<endl;


  //  il1.clear ();
  il1.erase (il1.begin(), i);

  cout<<"Size is: "<<il1.size ()<<endl<<endl;
    }


  il1.clear ();
  int x;
  cin>>x;


}