// test code for http://stackoverflow.com/questions/24542936/

#include <vector>
#include <set>
#include <algorithm>
#include <chrono>
#include <iostream>
#include <cstdlib>
#include <ctime>

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

const int N = 20000;

// reused from https://i...content-available-to-author-only...e.com/MN7DYK
struct timer
{
	typedef std::chrono::high_resolution_clock clock;
	clock::time_point start_;
	
	timer() : start_(clock::now()) {}
	~timer()
	{
		std::cout
		<< ((double)std::chrono::duration_cast<std::chrono::microseconds>(clock::now() - start_).count() / 1000.)
		<< "ms" << std::endl;
	}
};

void test_vector() {
	timer t;
	std::vector<int> c;
	
	// insert elements randomly while maintaining order
	for(int i = 0; i < N; ++i) {
		int r = rand();
		
		// linear search for insert position
		auto position = c.end();
		for(auto it = c.begin(); it != c.end(); ++it) {
			if(*it >= r) {
				position = it;
				break;
			}
		}
		c.insert(position, r);
	}
	
	// remove randomly while maintaining order
	for(auto i = c.size() - 1; i > 0; --i) {
		auto it = c.begin();
		std::advance(it, rand() % i);
		c.erase(it);
	}
}

void test_bsvector() {
	timer t;
	std::vector<int> c;
	
	// insert elements randomly while maintaining order
	for(int i = 0; i < N; ++i) {
		int r = rand();
		
		// binary search
		c.insert(std::lower_bound(c.begin(), c.end(), r), r);
	}
	
	// remove randomly while maintaining order
	for(auto i = c.size() - 1; i > 0; --i) {
		auto it = c.begin();
		std::advance(it, rand() % i);
		c.erase(it);
	}
}

void test_set() {
	timer t;
	std::set<int> c;
	
	// insert elements randomly while maintaining order
	for(int i = 0; i < N; ++i)
		c.insert(rand()); // logarithmic search
	
	// remove randomly while maintaining order
	// if you have a faster algorithm, please share
	for(auto i = c.size() - 1; i > 0; --i) {
		auto it = c.begin();
		std::advance(it, rand() % i);
		c.erase(it);
	}
}

using namespace __gnu_pbds;

typedef
	tree<
	int,
	int,
	std::less<int>,
	rb_tree_tag,
	tree_order_statistics_node_update>
map_t;

void test_ost() {
	timer t;
	map_t c;
	
	// insert elements randomly while maintaining order
	for(int i = 0; i < N; ++i) {
		int r = rand();
		c.insert(std::make_pair(r, r)); // logarithmic search
	}
		
	// remove randomly while maintaining order
	for(auto i = c.size() - 1; i > 0; --i) {
		c.erase(c.find_by_order(rand() % i));
	}
}

int main() {
	unsigned int seed = std::time(nullptr);
	std::srand(seed);
	std::cout << "order statistics tree: ";
	test_ost();
	std::srand(seed);
	std::cout << "vector binary search: ";
	test_bsvector();
	std::srand(seed);
	std::cout << "vector linear search: ";
	test_vector();
	std::srand(seed);
	std::cout << "set: ";
	test_set();
}