Select Git revision
splay_operation_test.cpp
-
David Mareček authoredDavid Mareček authored
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) {