Select Git revision
splay_experiment.cpp
-
Ondřej Mička authoredOndřej Mička authored
splay_experiment.cpp 4.93 KiB
#include <algorithm>
#include <functional>
#include <string>
#include <utility>
#include <vector>
#include <iostream>
#include <cmath>
#include "splay_operation.h"
#include "random.h"
using namespace std;
/*
* A modified Splay tree for benchmarking.
*
* We inherit the implementation of operations from the Tree class
* and extend it by keeping statistics on the number of splay operations
* and the total number of rotations. Also, if naive is turned on,
* splay uses only single rotations.
*
* Please make sure that your Tree class defines the rotate() and splay()
* methods as virtual.
*/
class BenchmarkingTree : public Tree {
public:
int num_operations;
int num_rotations;
bool do_naive;
BenchmarkingTree(bool naive=false)
{
do_naive = naive;
reset();
}
void reset()
{
num_operations = 0;
num_rotations = 0;
}
void rotate(Node *node) override
{
num_rotations++;
Tree::rotate(node);
}
void splay(Node *node) override
{
num_operations++;
if (do_naive) {
while (node->parent)
rotate(node);
} else {
Tree::splay(node);
}
}
// Return the average number of rotations per operation.
double rot_per_op()
{
if (num_operations > 0)
return (double) num_rotations / num_operations;
else
return 0;
}
};