notebook/code/Treap_test.cpp

#include <bits/stdc++.h>
using namespace std;

#include "Treap.cpp"

int main() {
  int values[] = {6,5,4,1,2,3}, n = sizeof(values)/sizeof(int);
  Node *r = NULL;
  for(int i = 0; i < n; i++)
    merge(r, r, new Node(values[i]));
  assert(query(r, 1, 6) == 21);
  assert(query(r, 1, 3) == 15);
  assert(query(r, 3, 4) == 5);
  reverse(r, 1, 3); // 4 5 6 1 2 3
  assert(query(r, 1, 3) == 15);
  assert(query(r, 3, 4) == 7);
  reverse(r, 1, 6); // 3 2 1 6 5 4
  assert(query(r, 1, 6) == 21);
  assert(query(r, 5, 6) == 9);
  insert(r, 2, 8); // 3 8 2 1 6 5 4
  assert(query(r, 2, 2) == 8);
  assert(query(r, 1, 3) == 13);
  insert(r, 3, 2); // 3 8 2 2 1 6 5 4
  assert(query(r, 1, 4) == 15);
  del(r, 3); // 3 8 2 1 6 5 4
  assert(query(r, 2, 2) == 8);
  assert(query(r, 1, 3) == 13);
  del(r, 1); // 8 2 1 6 5 4
  assert(query(r, 2, 5) == 14);
  del(r, 2);
  del(r, 3);
  del(r, 2);
  del(r, 2);
  del(r, 1);
  del(r, 1); //
  assert(query(r, 1, 5) == 0);

  r = NULL;
  insert(r, 1, 10); // 10
  insert(r, 1, 2); // 2 10
  assert(query(r, 1, 1) == 2);
  assert(query(r, 1, 2) == 12);
  del(r, 2);
  del(r, 1); //

  r = NULL;
  insert(r, 1, 3); // 3
  assert(query(r, 1, 1) == 3);
  insert(r, 2, 2); // 3 2
  assert(query(r, 1, 2) == 5);
  assert(query(r, 2, 2) == 2);
  return 0;
}