Skip to content
Snippets Groups Projects
Select Git revision
  • cbf0c8db53e3ee33059d8cc9be0dde4fd00480b0
  • devel default
  • master
  • fo
  • jirka/typing
  • fo-base
  • mj/submit-images
  • jk/issue-96
  • jk/issue-196
  • honza/add-contestant
  • honza/mr7
  • honza/mrf
  • honza/mrd
  • honza/mra
  • honza/mr6
  • honza/submit-images
  • honza/kolo-vs-soutez
  • jh-stress-test-wip
  • shorten-schools
19 results

org_users.py

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