Skip to content
Snippets Groups Projects
Select Git revision
  • 305c73b10435c6fce26f2d2cfe9f6eda95e552bf
  • master default protected
2 results

splay_operation_test.cpp

Blame
  • splay_operation_test.cpp 6.00 KiB
    #include <algorithm>
    #include <cassert>
    #include <fstream>
    #include <functional>
    #include <string>
    #include <utility>
    #include <vector>
    
    #include "splay_operation.h"
    
    using namespace std;
    
    // If the condition is not true, report an error and halt.
    #define EXPECT(condition, message) do { if (!(condition)) expect_failed(message); } while (0)
    void expect_failed(const string& message);
    
    // Flatten the tree: return a sorted list of all keys in the tree.
    vector<int> flatten(const Tree& tree) {
        constexpr int L = 0, R = 1, F = 2;
    
        Node* node = tree.root;
        vector<int> flattened, stack = {L};
        while (!stack.empty()) {
            if (stack.back() == L) {
                stack.back() = R;
                if (node->left) {
                    node = node->left;
                    stack.push_back(L);
                }
            } else if (stack.back() == R) {
                flattened.push_back(node->key);
                stack.back() = F;
                if (node->right) {
                    node = node->right;
                    stack.push_back(L);
                }
            } else {
                node = node->parent;
                stack.pop_back();
            }
        }
        return flattened;
    }
    
    // Test for splay operation with required helpers
    class TestSplay {
      public:
        static Node* deserialize_node(const string& text, int& index) {
            EXPECT(text[index++] == '(', "Internal error during example deserialization");
            if (text[index] == ')') {
                index++;
                return nullptr;
            } else {
                int comma = text.find(',', index);
                int key = stoi(text.substr(index, comma - index));
                Node* left = deserialize_node(text, (index=comma + 1));
                Node* right = deserialize_node(text, ++index);
                EXPECT(text[index++] == ')', "Internal error during example deserialization");
                return new Node(key, nullptr, left, right);
            }
        }
    
        static Node* deserialize_root(const string& text) {
            int index = 0;
            Node* root = deserialize_node(text, index);
            assert(index == text.size());
            return root;
        }
    
        static string compare(Node* system, Node* gold) {