Skip to content
Snippets Groups Projects
Select Git revision
  • 1cfe7fb0ce8279c6cb1025f08fee371cb7531c9e
  • master default protected
2 results

splay_experiment.cpp

Blame
  • 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;
        }
    };