# Run
#  csplit -k <this file> "/FILE/" "{4}"
#  source xx01

mv xx02 anti-optimization.cc
mv xx03 perf.cc
mv xx04 SConstruct
mv xx05 timer.hpp
rm xx00
rm xx01


//// FILE anti-optimization.cc

#include <vector>
#include <list>
using namespace std;

typedef vector<int> Vector;
typedef list<int>   List;

void anti_optimization(Vector & v) {}
void anti_optimization(List & l)   {}

void anti_optimization(Vector::iterator & v) {}
void anti_optimization(List::iterator & l)   {}


//// FILE perf.cc

#include <vector>
#include <list>
#include <cerrno>
#include <cassert>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <functional>


#include "timer.hpp"

using namespace std;

typedef vector<int> Vector;
typedef list<int>   List;

extern void anti_optimization(Vector & v);
extern void anti_optimization(List & l);
extern void anti_optimization(Vector::iterator & v);
extern void anti_optimization(List::iterator & l);


template<typename T>
typename T::iterator
get_random_removal_point(T & container)
{
    assert(container.size() < RAND_MAX);

    typename T::iterator place = container.begin();
    int index = rand() % container.size();
    
    for(int i=0; i<index; ++i) {
        ++place;
        anti_optimization(place);
    }

    return place;
}


template<typename T>
void
remove_n_random_elements(T & container, int n)
{
    for(int i=0; i<n; ++i) {
        container.erase(get_random_removal_point(container));
    }
}


template<typename T>
void
setup_container(T & container, int size, bool random_order)
{
    typedef typename T::iterator iterator;
    for(int i=0; i<size; ++i) {
        if (random_order) {
            int number_to_insert = rand();
            iterator place = lower_bound(container.begin(), container.end(), number_to_insert);
            container.insert(place, number_to_insert);
        }
        else {
            container.push_back(i);
        }
    }
}


template<typename T>
void
run_tests(int container_size, int number_of_removals, bool random_order)
{
    T container;

    number_of_removals = min(number_of_removals, container_size);

    {
        srand(0);
        BlockTimer timer("container setup time");
        setup_container(container, container_size, random_order);
    }

    assert(adjacent_find(container.begin(), container.end(), greater<int>())
           == container.end());

    {
        srand(1);
        BlockTimer timer("removal time");
        remove_n_random_elements(container, number_of_removals);
    }

    anti_optimization(container);
}


int main(int argc, char** argv)
{
    if (argc != 4) {
        cout << "usage: " << argv[0] << " <container size> <number of removals> <random order? (0 or 1)>\n";
        exit(1);
    }

    errno = 0;
    
    int container_size = strtol(argv[1], NULL, 10);
    int number_of_removals = strtol(argv[2], NULL, 10);
    bool random_order = strtol(argv[3], NULL, 10) != 0;

    if (errno != 0) {
        cout << "All arguments must be numbers\n";
        exit(1);
    }

    {
        cout << "Vector:\n";
        BlockTimer timer("total vector time");
        run_tests<Vector>(container_size, number_of_removals, random_order);
    }

    {
        cout << "List:\n";
        BlockTimer timer("total list time");
        run_tests<List>(container_size, number_of_removals, random_order);
    }
    
}

# FILE SConstruct
Program("time-removals", ["anti-optimization.cc", "perf.cc"], CCFLAGS="-O2")

//// FILE timer.hpp

#ifndef TIMER_HPP
#define TIMER_HPP

#include <iostream>

#if defined(__WIN32) || defined(_MSC_VER)
#  define WIN32_LEAN_AND_MEAN
#  include <windows.h>

class BlockTimer
{
    unsigned long long start_time;
    std::string description;
    
public:
    BlockTimer() {}
    
    BlockTimer(std::string const & desc)
    {
        start(desc);
    }

    void start(std::string const & desc)
    {
        description = desc;
        start_time = GetTickCount();
    }

    void finish() {
        unsigned long long ms = GetTickCount() - start_time;
        std::cout << "> Timer " << description << ": " << ms/1000 << "." << ms % 1000 << "\n";
        start_time = 0;
    }

    ~BlockTimer() {
        if (start_time != 0) finish();
    }
};

#else // Unix version

#include <sys/time.h>

inline unsigned long long timevaldiff(struct timeval *starttime, struct timeval *finishtime)
{
  unsigned long long msec;
  msec=(finishtime->tv_sec-starttime->tv_sec)*1000;
  msec+=(finishtime->tv_usec-starttime->tv_usec)/1000;
  return msec;
}

class BlockTimer
{
    timeval start_time;
    std::string description;
    
public:
    BlockTimer() {}
    
    BlockTimer(std::string const & desc)
    {
        start(desc);
    }

    void start(std::string const & desc)
    {
        description = desc;
	gettimeofday(&start_time, NULL);
	// start_time = GetTickCount();
    }

    void finish() {
        //unsigned long long ms = GetTickCount() - start_time;
        timeval end_time;
	gettimeofday(&end_time, NULL);
        unsigned long long ms = timevaldiff(&start_time, &end_time);
        std::cout << "> Timer " << description << ": " << ms/1000 << "." << ms % 1000 << "\n";
        start_time.tv_sec = 0;
    }

    ~BlockTimer() {
        if (start_time.tv_sec != 0) finish();
    }
};

#endif


// Yo emacs!
// Local Variables:
//     c-basic-offset: 4
//     indent-tabs-mode: nil
// End:

#endif