API tools faq
paste
Advertisement
Guest User

Untitled

a guest
Oct 19th, 2017
73
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 23.79 KB | None | 0 0
raw download clone embed print report
  1. #include <stdio.h>
  2. #include "SplayTree.h"
  3. #include <gtest\gtest.h>
  4.  
  5. TEST(Rotations, basic_left) {
  6.     SplayTree<int> tree;
  7.     SplayTree<int>::Node * x = new SplayTree<int>::Node(66);
  8.     SplayTree<int>::Node * y = new SplayTree<int>::Node(67);
  9.     SplayTree<int>::Node * up = new SplayTree<int>::Node(512);
  10.  
  11.     SplayTree<int>::Node * A = new SplayTree<int>::Node(256);
  12.     SplayTree<int>::Node * B = new SplayTree<int>::Node(257);
  13.     SplayTree<int>::Node * C = new SplayTree<int>::Node(258);
  14.  
  15.     x->left = A;
  16.     x->right = B;
  17.     x->up = y;
  18.  
  19.     y->left = x;
  20.     y->right = C;
  21.     y->up = up;
  22.  
  23.     A->up = x;
  24.     B->up = x;
  25.     C->up = y;
  26.  
  27.     up->right = y;
  28.  
  29.     tree.left(x);
  30.  
  31.     EXPECT_EQ(x->up, up);
  32.     EXPECT_EQ(x->left, A);
  33.     EXPECT_EQ(x->right, y);
  34.  
  35.     EXPECT_EQ(y->up, x);
  36.     EXPECT_EQ(y->left, B);
  37.     EXPECT_EQ(y->right, C);
  38.  
  39.     EXPECT_EQ(C->up, y);
  40.     EXPECT_EQ(B->up, y);
  41.     EXPECT_EQ(A->up, x);
  42.  
  43.     EXPECT_EQ(up->right, x);
  44. }
  45. TEST(Rotations, basic_right) {
  46.     SplayTree<int> tree;
  47.     SplayTree<int>::Node * x = new SplayTree<int>::Node(66);
  48.     SplayTree<int>::Node * y = new SplayTree<int>::Node(67);
  49.     SplayTree<int>::Node * up = new SplayTree<int>::Node(1337);
  50.  
  51.     SplayTree<int>::Node * A = new SplayTree<int>::Node(256);
  52.     SplayTree<int>::Node * B = new SplayTree<int>::Node(257);
  53.     SplayTree<int>::Node * C = new SplayTree<int>::Node(258);
  54.  
  55.  
  56.     x->left = B; // B
  57.     x->right = A; // A
  58.     x->up = y;
  59.  
  60.     y->right = x;
  61.     y->left = C; // C
  62.     y->up = up; // U
  63.    
  64.     A->up = x;
  65.     B->up = x;
  66.     C->up = y;
  67.  
  68.     up->right = y;
  69.  
  70.     tree.right(x);
  71.  
  72.     EXPECT_EQ(x->up, up);
  73.     EXPECT_EQ(x->right, A);
  74.     EXPECT_EQ(x->left, y);
  75.  
  76.     EXPECT_EQ(y->up, x);
  77.     EXPECT_EQ(y->right, B);
  78.     EXPECT_EQ(y->left, C);
  79.  
  80.     EXPECT_EQ(C->up, y);
  81.     EXPECT_EQ(B->up, y);
  82.     EXPECT_EQ(A->up, x);
  83.  
  84.     EXPECT_EQ(up->right, x);
  85. }
  86. TEST(Rotations, leftleft_equals_two_lefts) {
  87.     SplayTree<int>::Node * A = new SplayTree<int>::Node(256);
  88.     SplayTree<int>::Node * B = new SplayTree<int>::Node(257);
  89.     SplayTree<int>::Node * C = new SplayTree<int>::Node(258);
  90.     SplayTree<int>::Node * D = new SplayTree<int>::Node(259);
  91.    
  92.     SplayTree<int> tree;
  93.     SplayTree<int>::Node * x = new SplayTree<int>::Node(66);
  94.     SplayTree<int>::Node * y = new SplayTree<int>::Node(67);
  95.     SplayTree<int>::Node * z = new SplayTree<int>::Node(68);
  96.     SplayTree<int>::Node * up = new SplayTree<int>::Node(1337);
  97.  
  98.     A->up = x;
  99.     B->up = x;
  100.     C->up = y;
  101.     D->up = z;
  102.  
  103.     x->left = A; // A
  104.     x->right = B; // B
  105.     x->up = y;
  106.  
  107.     y->left = x;
  108.     y->right = C; // C
  109.     y->up = z;
  110.  
  111.     z->left = y;
  112.     z->right = D; // D
  113.     z->up = up;
  114.  
  115.     up->right = z;
  116.  
  117.     tree.left(x->up);
  118.     tree.left(x);
  119.  
  120.     SplayTree<int>::Node * All = new SplayTree<int>::Node(256);
  121.     SplayTree<int>::Node * Bll = new SplayTree<int>::Node(257);
  122.     SplayTree<int>::Node * Cll = new SplayTree<int>::Node(258);
  123.     SplayTree<int>::Node * Dll = new SplayTree<int>::Node(259);
  124.  
  125.     SplayTree<int>::Node * xll = new SplayTree<int>::Node(66);
  126.     SplayTree<int>::Node * yll = new SplayTree<int>::Node(67);
  127.     SplayTree<int>::Node * zll = new SplayTree<int>::Node(68);
  128.     SplayTree<int>::Node * ull = new SplayTree<int>::Node(1337);
  129.  
  130.     xll->left = All; // A
  131.     xll->right = Bll; // B
  132.     xll->up = yll;
  133.  
  134.     yll->left = xll;
  135.     yll->right = Cll; // C
  136.     yll->up = zll;
  137.  
  138.     zll->left = yll;
  139.     zll->right = Dll; // D
  140.     zll->up = ull; // U
  141.  
  142.     ull->right = zll;
  143.  
  144.     tree.leftLeft(xll);
  145.  
  146.     EXPECT_EQ(xll->left->val,256);
  147.     EXPECT_EQ(yll->left->val,257);
  148.     EXPECT_EQ(zll->left->val,258);
  149.     EXPECT_EQ(zll->right->val,259);
  150.  
  151.     EXPECT_EQ(x->left->val, xll->left->val);
  152.     EXPECT_EQ(x->right->val, xll->right->val);
  153.     EXPECT_EQ(x->up->val, xll->up->val);
  154.  
  155.     EXPECT_EQ(y->left->val, yll->left->val);
  156.     EXPECT_EQ(y->right->val, yll->right->val);
  157.     EXPECT_EQ(y->up->val, yll->up->val);
  158.  
  159.     EXPECT_EQ(z->left->val, zll->left->val); // C
  160.     EXPECT_EQ(z->right->val, zll->right->val); // D
  161.     EXPECT_EQ(z->up->val, zll->up->val);
  162. }
  163. TEST(Rotations, leftLeft_hard_check) {
  164.     SplayTree<int>::Node * A = new SplayTree<int>::Node(256);
  165.     SplayTree<int>::Node * B = new SplayTree<int>::Node(257);
  166.     SplayTree<int>::Node * C = new SplayTree<int>::Node(258);
  167.     SplayTree<int>::Node * D = new SplayTree<int>::Node(259);
  168.     SplayTree<int> tree;
  169.  
  170.     SplayTree<int>::Node * x = new SplayTree<int>::Node(66);
  171.     SplayTree<int>::Node * y = new SplayTree<int>::Node(67);
  172.     SplayTree<int>::Node * z = new SplayTree<int>::Node(68);
  173.     SplayTree<int>::Node * up = new SplayTree<int>::Node(1337);
  174.  
  175.     x->left = A; // A
  176.     x->right = B; // B
  177.     x->up = y;
  178.  
  179.     y->left = x;
  180.     y->right = C; // C
  181.     y->up = z;
  182.  
  183.     z->left = y;
  184.     z->right = D; // D
  185.     z->up = up; // U
  186.  
  187.     up->right = z;
  188.    
  189.     A->up = x;
  190.     B->up = x;
  191.     C->up = y;
  192.     D->up = z;
  193.  
  194.     tree.leftLeft(x);
  195.  
  196.     EXPECT_EQ(x->left->val, A->val);
  197.     EXPECT_EQ(x->right->val, y->val);
  198.     EXPECT_EQ(x->up, up);
  199.  
  200.     EXPECT_EQ(up->right, x);
  201.  
  202.     EXPECT_EQ(y->up, x);
  203.     EXPECT_EQ(y->left, B);
  204.     EXPECT_EQ(y->right, z);
  205.  
  206.     EXPECT_EQ(z->up, y);
  207.     EXPECT_EQ(z->left, C);
  208.     EXPECT_EQ(z->right, D);
  209.  
  210.     EXPECT_EQ(A->up, x);
  211.     EXPECT_EQ(B->up, y);
  212.     EXPECT_EQ(C->up, z);
  213.     EXPECT_EQ(D->up, z);
  214. }
  215. TEST(Rotations, rightLeft_hard_check) {
  216.     SplayTree<int>::Node * A = new SplayTree<int>::Node(256);
  217.     SplayTree<int>::Node * B = new SplayTree<int>::Node(257);
  218.     SplayTree<int>::Node * C = new SplayTree<int>::Node(258);
  219.     SplayTree<int>::Node * D = new SplayTree<int>::Node(259);
  220.  
  221.     SplayTree<int> tree;
  222.     SplayTree<int>::Node * x = new SplayTree<int>::Node(66);
  223.     SplayTree<int>::Node * y = new SplayTree<int>::Node(67);
  224.     SplayTree<int>::Node * w = new SplayTree<int>::Node(68);
  225.     SplayTree<int>::Node * up = new SplayTree<int>::Node(1337);
  226.  
  227.     y->left = w;
  228.     y->right = D;
  229.     y->up = up;
  230.  
  231.     w->left = A;
  232.     w->right = x;
  233.     w->up = y;
  234.  
  235.     x->left = B;
  236.     x->right = C;
  237.     x->up = w;
  238.  
  239.     B->up = x;
  240.     C->up = x;
  241.     A->up = w;
  242.     D->up = y;
  243.  
  244.     up->left = y;
  245.  
  246.     tree.rightLeft(x);
  247.  
  248.     EXPECT_EQ(x->left->val, 68);
  249.     EXPECT_EQ(x->right->val, 67);
  250.     EXPECT_EQ(x->up, up);
  251.  
  252.     EXPECT_EQ(up->left, x);
  253.    
  254.     EXPECT_EQ(w->up, x);
  255.     EXPECT_EQ(w->left, A);
  256.     EXPECT_EQ(w->right, B);
  257.  
  258.     EXPECT_EQ(y->up, x);
  259.     EXPECT_EQ(y->left, C);
  260.     EXPECT_EQ(y->right, D);
  261.  
  262.     EXPECT_EQ(A->up, w);
  263.     EXPECT_EQ(B->up, w);
  264.     EXPECT_EQ(C->up, y);
  265.     EXPECT_EQ(D->up, y);
  266. }
  267. TEST(Rotations, rightLeft_equals_right_left) {
  268.     SplayTree<int>::Node * A = new SplayTree<int>::Node(256);
  269.     SplayTree<int>::Node * B = new SplayTree<int>::Node(257);
  270.     SplayTree<int>::Node * C = new SplayTree<int>::Node(258);
  271.     SplayTree<int>::Node * D = new SplayTree<int>::Node(259);
  272.     SplayTree<int> tree;
  273.  
  274.     SplayTree<int>::Node * x = new SplayTree<int>::Node(66);
  275.     SplayTree<int>::Node * y = new SplayTree<int>::Node(67);
  276.     SplayTree<int>::Node * w = new SplayTree<int>::Node(68);
  277.     SplayTree<int>::Node * up = new SplayTree<int>::Node(1337);
  278.  
  279.     y->left = w;
  280.     y->right = D;
  281.     y->up = up;
  282.  
  283.     w->left = A;
  284.     w->right = x;
  285.     w->up = y;
  286.  
  287.     x->left = B;
  288.     x->right = C;
  289.     x->up = w;
  290.  
  291.     B->up = x;
  292.     C->up = x;
  293.     A->up = w;
  294.     D->up = y;
  295.  
  296.     up->left = y;
  297.  
  298.     tree.right(x);
  299.     tree.left(x);
  300.  
  301.     EXPECT_EQ(x->left->val, 68);
  302.     EXPECT_EQ(x->right->val, 67);
  303.     EXPECT_EQ(x->up, up);
  304.  
  305.     EXPECT_EQ(up->left, x);
  306.  
  307.     EXPECT_EQ(w->up, x);
  308.     EXPECT_EQ(w->left, A);
  309.     EXPECT_EQ(w->right, B);
  310.  
  311.     EXPECT_EQ(y->up, x);
  312.     EXPECT_EQ(y->left, C);
  313.     EXPECT_EQ(y->right, D);
  314.  
  315.     EXPECT_EQ(A->up, w);
  316.     EXPECT_EQ(B->up, w);
  317.     EXPECT_EQ(C->up, y);
  318.     EXPECT_EQ(D->up, y);
  319. }
  320. TEST(Rotations, rightRight_hard_check) {
  321.     SplayTree<int>::Node * A = new SplayTree<int>::Node(256);
  322.     SplayTree<int>::Node * B = new SplayTree<int>::Node(257);
  323.     SplayTree<int>::Node * C = new SplayTree<int>::Node(258);
  324.     SplayTree<int>::Node * D = new SplayTree<int>::Node(259);
  325.  
  326.     SplayTree<int> tree;
  327.     SplayTree<int>::Node * x = new SplayTree<int>::Node(66);
  328.     SplayTree<int>::Node * y = new SplayTree<int>::Node(67);
  329.     SplayTree<int>::Node * z = new SplayTree<int>::Node(68);
  330.     SplayTree<int>::Node * up = new SplayTree<int>::Node(1337);
  331.  
  332.     up->left = z;
  333.  
  334.     z->up = up;
  335.     z->left = D;
  336.     z->right = y;
  337.  
  338.     y->left = C;
  339.     y->right = x;
  340.     y->up = z;
  341.  
  342.     x->up = y;
  343.     x->left = B;
  344.     x->right = A;
  345.  
  346.     A->up = x;
  347.     B->up = x;
  348.     C->up = y;
  349.     D->up = z;
  350.  
  351.     tree.rightRight(x);
  352.  
  353.     EXPECT_EQ(x->up, up);
  354.     EXPECT_EQ(x->left, y);
  355.     EXPECT_EQ(x->right, A);
  356.  
  357.     EXPECT_EQ(up->left, x);
  358.  
  359.     EXPECT_EQ(y->up, x);
  360.     EXPECT_EQ(y->left, z);
  361.     EXPECT_EQ(y->right, B);
  362.  
  363.     EXPECT_EQ(z->up, y);
  364.     EXPECT_EQ(z->left, D);
  365.     EXPECT_EQ(z->right, C);
  366.  
  367.     EXPECT_EQ(A->up, x);
  368.     EXPECT_EQ(B->up, y);
  369.     EXPECT_EQ(C->up, z);
  370.     EXPECT_EQ(D->up, z);
  371. }
  372. TEST(Rotations, right_right_equals_rightRight) {
  373.     SplayTree<int>::Node * A = new SplayTree<int>::Node(256);
  374.     SplayTree<int>::Node * B = new SplayTree<int>::Node(257);
  375.     SplayTree<int>::Node * C = new SplayTree<int>::Node(258);
  376.     SplayTree<int>::Node * D = new SplayTree<int>::Node(259);
  377.  
  378.     SplayTree<int> tree;
  379.     SplayTree<int>::Node * x = new SplayTree<int>::Node(66);
  380.     SplayTree<int>::Node * y = new SplayTree<int>::Node(67);
  381.     SplayTree<int>::Node * z = new SplayTree<int>::Node(68);
  382.     SplayTree<int>::Node * up = new SplayTree<int>::Node(1337);
  383.  
  384.     up->left = z;
  385.  
  386.     z->up = up;
  387.     z->left = D;
  388.     z->right = y;
  389.  
  390.     y->left = C;
  391.     y->right = x;
  392.     y->up = z;
  393.  
  394.     x->up = y;
  395.     x->left = B;
  396.     x->right = A;
  397.  
  398.     A->up = x;
  399.     B->up = x;
  400.     C->up = y;
  401.     D->up = z;
  402.  
  403.     tree.right(x->up);
  404.     tree.right(x);
  405.  
  406.     EXPECT_EQ(x->up, up);
  407.     EXPECT_EQ(x->left, y);
  408.     EXPECT_EQ(x->right, A);
  409.  
  410.     EXPECT_EQ(up->left, x);
  411.  
  412.     EXPECT_EQ(y->up, x);
  413.     EXPECT_EQ(y->left, z);
  414.     EXPECT_EQ(y->right, B);
  415.  
  416.     EXPECT_EQ(z->up, y);
  417.     EXPECT_EQ(z->left, D);
  418.     EXPECT_EQ(z->right, C);
  419.  
  420.     EXPECT_EQ(A->up, x);
  421.     EXPECT_EQ(B->up, y);
  422.     EXPECT_EQ(C->up, z);
  423.     EXPECT_EQ(D->up, z);
  424. }
  425. TEST(Rotations, leftRight_hard_check) {
  426.     SplayTree<int>::Node * A = new SplayTree<int>::Node(256);
  427.     SplayTree<int>::Node * B = new SplayTree<int>::Node(257);
  428.     SplayTree<int>::Node * C = new SplayTree<int>::Node(258);
  429.     SplayTree<int>::Node * D = new SplayTree<int>::Node(259);
  430.  
  431.     SplayTree<int> tree;
  432.     SplayTree<int>::Node * x = new SplayTree<int>::Node(66);
  433.     SplayTree<int>::Node * y = new SplayTree<int>::Node(67);
  434.     SplayTree<int>::Node * w = new SplayTree<int>::Node(68);
  435.     SplayTree<int>::Node * up = new SplayTree<int>::Node(1337);
  436.  
  437.     y->left = D;
  438.     y->right = w;
  439.     y->up = up;
  440.  
  441.     w->left = x;
  442.     w->right = A;
  443.     w->up = y;
  444.  
  445.     x->left = C;
  446.     x->right = B;
  447.     x->up = w;
  448.  
  449.     B->up = x;
  450.     C->up = x;
  451.     A->up = w;
  452.     D->up = y;
  453.  
  454.     up->left = y;
  455.  
  456.     tree.leftRight(x);
  457.  
  458.     EXPECT_EQ(x->left, y);
  459.     EXPECT_EQ(x->right, w);
  460.     EXPECT_EQ(x->up, up);
  461.  
  462.     EXPECT_EQ(up->left, x);
  463.  
  464.     EXPECT_EQ(w->up, x);
  465.     EXPECT_EQ(w->left, B);
  466.     EXPECT_EQ(w->right, A);
  467.  
  468.     EXPECT_EQ(y->up, x);
  469.     EXPECT_EQ(y->left, D);
  470.     EXPECT_EQ(y->right, C);
  471.  
  472.     EXPECT_EQ(A->up, w);
  473.     EXPECT_EQ(B->up, w);
  474.     EXPECT_EQ(C->up, y);
  475.     EXPECT_EQ(D->up, y);
  476. }
  477. TEST(Rotations, left_right_equals_leftRight) {
  478.     SplayTree<int>::Node * A = new SplayTree<int>::Node(256);
  479.     SplayTree<int>::Node * B = new SplayTree<int>::Node(257);
  480.     SplayTree<int>::Node * C = new SplayTree<int>::Node(258);
  481.     SplayTree<int>::Node * D = new SplayTree<int>::Node(259);
  482.  
  483.     SplayTree<int> tree;
  484.     SplayTree<int>::Node * x = new SplayTree<int>::Node(66);
  485.     SplayTree<int>::Node * y = new SplayTree<int>::Node(67);
  486.     SplayTree<int>::Node * w = new SplayTree<int>::Node(68);
  487.     SplayTree<int>::Node * up = new SplayTree<int>::Node(1337);
  488.  
  489.     y->left = D;
  490.     y->right = w;
  491.     y->up = up;
  492.  
  493.     w->left = x;
  494.     w->right = A;
  495.     w->up = y;
  496.  
  497.     x->left = C;
  498.     x->right = B;
  499.     x->up = w;
  500.  
  501.     B->up = x;
  502.     C->up = x;
  503.     A->up = w;
  504.     D->up = y;
  505.  
  506.     up->left = y;
  507.  
  508.     tree.left(x);
  509.     tree.right(x);
  510.  
  511.     EXPECT_EQ(x->left, y);
  512.     EXPECT_EQ(x->right, w);
  513.     EXPECT_EQ(x->up, up);
  514.  
  515.     EXPECT_EQ(up->left, x);
  516.  
  517.     EXPECT_EQ(w->up, x);
  518.     EXPECT_EQ(w->left, B);
  519.     EXPECT_EQ(w->right, A);
  520.  
  521.     EXPECT_EQ(y->up, x);
  522.     EXPECT_EQ(y->left, D);
  523.     EXPECT_EQ(y->right, C);
  524.  
  525.     EXPECT_EQ(A->up, w);
  526.     EXPECT_EQ(B->up, w);
  527.     EXPECT_EQ(C->up, y);
  528.     EXPECT_EQ(D->up, y);
  529. }
  530.  
  531. TEST(Insert, insert_counts_size) {
  532.     SplayTree<int> tree;
  533.     tree.insert(1);
  534.     tree.insert(2);
  535.     tree.insert(1337);
  536.     EXPECT_EQ(tree.size(), 3);
  537. }
  538. TEST(Insert, insert_on_empty_changes_root) {
  539.     SplayTree<int> tree;
  540.     EXPECT_EQ(tree.mRoot, nullptr);
  541.     tree.insert(1);
  542.     tree.insert(2);
  543.     tree.insert(3);
  544.     EXPECT_NE(tree.mRoot, nullptr);
  545. }
  546. TEST(Insert, tree_is_in_correct_order_after_insert1) {
  547.     SplayTree<int> tree;
  548.     tree.insert(1);
  549.     tree.insert(2);
  550.     tree.insert(3);
  551.    
  552.     EXPECT_EQ(tree.mRoot->val, 3);
  553.     EXPECT_EQ(tree.mRoot->right, nullptr);
  554.     EXPECT_EQ(tree.mRoot->left->val, 2);
  555.     EXPECT_EQ(tree.mRoot->left->right, nullptr);
  556.     EXPECT_EQ(tree.mRoot->left->left->val, 1);
  557.     EXPECT_EQ(tree.mRoot->left->left->right, nullptr);
  558. }
  559. TEST(Insert, tree_is_in_correct_order_after_insert2) {
  560.     SplayTree<int> tree;
  561.     tree.insert(3);
  562.     tree.insert(1);
  563.     tree.insert(2);
  564.  
  565.     EXPECT_EQ(tree.mRoot->val, 2);
  566.     EXPECT_EQ(tree.mRoot->left->val, 1);
  567.     EXPECT_EQ(tree.mRoot->right->val, 3);
  568.     EXPECT_EQ(tree.mRoot->left->left, nullptr);
  569.     EXPECT_EQ(tree.mRoot->left->right, nullptr);
  570.     EXPECT_EQ(tree.mRoot->right->left, nullptr);
  571.     EXPECT_EQ(tree.mRoot->right->right, nullptr);
  572. }
  573. TEST(Insert, tree_is_in_correct_order_after_insert3) {
  574.     SplayTree<int> tree;
  575.     tree.insert(5);
  576.     tree.insert(7);
  577.     tree.insert(1);
  578.     tree.insert(6);
  579.     tree.insert(4);
  580.     tree.insert(3);
  581.  
  582.     EXPECT_EQ(tree.mRoot->val, 3);
  583.     EXPECT_EQ(tree.mRoot->up, nullptr);
  584.    
  585.     EXPECT_EQ(tree.mRoot->left->val, 1);
  586.     EXPECT_EQ(tree.mRoot->left->left, nullptr);
  587.     EXPECT_EQ(tree.mRoot->left->up, tree.mRoot);
  588.     EXPECT_EQ(tree.mRoot->left->right, nullptr);
  589.  
  590.     EXPECT_EQ(tree.mRoot->right->val, 4);
  591.     EXPECT_EQ(tree.mRoot->right->left, nullptr);
  592.     EXPECT_EQ(tree.mRoot->right->up, tree.mRoot);
  593.     EXPECT_EQ(tree.mRoot->right->right->val, 6);
  594.    
  595.     EXPECT_EQ(tree.mRoot->right->right->left->val, 5);
  596.     EXPECT_EQ(tree.mRoot->right->right->left->up, tree.mRoot->right->right);
  597.     EXPECT_EQ(tree.mRoot->right->right->left->left, nullptr);
  598.     EXPECT_EQ(tree.mRoot->right->right->left->right, nullptr);
  599.  
  600.     EXPECT_EQ(tree.mRoot->right->right->right->val, 7);
  601.     EXPECT_EQ(tree.mRoot->right->right->right->up, tree.mRoot->right->right);
  602.     EXPECT_EQ(tree.mRoot->right->right->right->left, nullptr);
  603.     EXPECT_EQ(tree.mRoot->right->right->right->right, nullptr);
  604. }
  605. TEST(Insert, duplicate_value) {
  606.     SplayTree<int> tree;
  607.     SplayTree<int>::Node* firstZero = tree.insert(0);
  608.     SplayTree<int>::Node* firstOne = tree.insert(1);
  609.     EXPECT_EQ(tree.insert(0), firstZero);
  610.     EXPECT_EQ(tree.insert(1), firstOne);
  611.     EXPECT_EQ(tree.insert(1), firstOne);
  612. }
  613.  
  614. TEST(Find, find_finds_correct_value) {
  615.     SplayTree<int> tree;
  616.     tree.insert(1);
  617.     tree.insert(2);
  618.     int dummy;
  619.     EXPECT_EQ(tree.find(1, dummy)->val, 1);
  620.     EXPECT_EQ(dummy, 1);
  621.     EXPECT_EQ(tree.find(2, dummy)->val, 2);
  622.     EXPECT_EQ(dummy, 1);
  623.     EXPECT_EQ(tree.find(2, dummy)->val, 2);
  624.     EXPECT_EQ(dummy, 0);
  625. }
  626. TEST(Find, find_splays_tree1) {
  627.     SplayTree<int> tree;
  628.     int dummy;
  629.     tree.insert(1);
  630.     tree.insert(2);
  631.     tree.insert(3);
  632.     EXPECT_EQ(tree.mRoot->val, 3);
  633.     EXPECT_EQ(tree.mRoot->right, nullptr);
  634.     EXPECT_EQ(tree.mRoot->left->val, 2);
  635.     EXPECT_EQ(tree.mRoot->left->right, nullptr);
  636.     EXPECT_EQ(tree.mRoot->left->left->val, 1);
  637.     EXPECT_EQ(tree.mRoot->left->left->right, nullptr);
  638.  
  639.     tree.find(2, dummy);
  640.     EXPECT_EQ(dummy, 1);
  641.  
  642.     EXPECT_EQ(tree.mRoot->val, 2);
  643.     EXPECT_EQ(tree.mRoot->left->val, 1);
  644.     EXPECT_EQ(tree.mRoot->right->val, 3);
  645.     EXPECT_EQ(tree.mRoot->left->left, nullptr);
  646.     EXPECT_EQ(tree.mRoot->left->right, nullptr);
  647.     EXPECT_EQ(tree.mRoot->right->left, nullptr);
  648.     EXPECT_EQ(tree.mRoot->right->right, nullptr);
  649.  
  650.     tree.find(3, dummy);
  651.     EXPECT_EQ(dummy, 1);
  652.  
  653.     EXPECT_EQ(tree.mRoot->val, 3);
  654.     EXPECT_EQ(tree.mRoot->right, nullptr);
  655.     EXPECT_EQ(tree.mRoot->left->val, 2);
  656.     EXPECT_EQ(tree.mRoot->left->right, nullptr);
  657.     EXPECT_EQ(tree.mRoot->left->left->val, 1);
  658.     EXPECT_EQ(tree.mRoot->left->left->right, nullptr);
  659. }
  660. TEST(Find, find_splays_tree2) {
  661.     SplayTree<int> tree;
  662.     int dummy;
  663.     tree.insert(3);
  664.     tree.insert(1);
  665.     tree.insert(2);
  666.  
  667.     EXPECT_EQ(tree.mRoot->val, 2);
  668.     EXPECT_EQ(tree.mRoot->left->val, 1);
  669.     EXPECT_EQ(tree.mRoot->right->val, 3);
  670.     EXPECT_EQ(tree.mRoot->left->left, nullptr);
  671.     EXPECT_EQ(tree.mRoot->left->right, nullptr);
  672.     EXPECT_EQ(tree.mRoot->right->left, nullptr);
  673.     EXPECT_EQ(tree.mRoot->right->right, nullptr);
  674.  
  675.     tree.find(1, dummy);
  676.     EXPECT_EQ(dummy, 1);
  677.  
  678.     EXPECT_EQ(tree.mRoot->val, 1);
  679.     EXPECT_EQ(tree.mRoot->left, nullptr);
  680.     EXPECT_EQ(tree.mRoot->right->val, 2);
  681.     EXPECT_EQ(tree.mRoot->right->left, nullptr);
  682.     EXPECT_EQ(tree.mRoot->right->right->val, 3);
  683.     EXPECT_EQ(tree.mRoot->right->right->left, nullptr);
  684.  
  685.     tree.find(3, dummy);
  686.     EXPECT_EQ(dummy, 2);
  687.  
  688.     EXPECT_EQ(tree.mRoot->val, 3);
  689.     EXPECT_EQ(tree.mRoot->right, nullptr);
  690.     EXPECT_EQ(tree.mRoot->left->val, 2);
  691.     EXPECT_EQ(tree.mRoot->left->right, nullptr);
  692.     EXPECT_EQ(tree.mRoot->left->left->val, 1);
  693.     EXPECT_EQ(tree.mRoot->left->left->right, nullptr);
  694. }
  695. TEST(Find, find_splays_tree_big) {
  696.     SplayTree<int> tree;
  697.     tree.insert(5);
  698.     tree.insert(7);
  699.     tree.insert(1);
  700.     tree.insert(6);
  701.     tree.insert(4);
  702.     tree.insert(3);
  703.  
  704.     EXPECT_EQ(tree.mRoot->val, 3);
  705.     EXPECT_EQ(tree.mRoot->up, nullptr);
  706.  
  707.     EXPECT_EQ(tree.mRoot->left->val, 1);
  708.     EXPECT_EQ(tree.mRoot->left->left, nullptr);
  709.     EXPECT_EQ(tree.mRoot->left->up, tree.mRoot);
  710.     EXPECT_EQ(tree.mRoot->left->right, nullptr);
  711.  
  712.     EXPECT_EQ(tree.mRoot->right->val, 4);
  713.     EXPECT_EQ(tree.mRoot->right->left, nullptr);
  714.     EXPECT_EQ(tree.mRoot->right->up, tree.mRoot);
  715.     EXPECT_EQ(tree.mRoot->right->right->val, 6);
  716.  
  717.     EXPECT_EQ(tree.mRoot->right->right->left->val, 5);
  718.     EXPECT_EQ(tree.mRoot->right->right->left->up, tree.mRoot->right->right);
  719.     EXPECT_EQ(tree.mRoot->right->right->left->left, nullptr);
  720.     EXPECT_EQ(tree.mRoot->right->right->left->right, nullptr);
  721.  
  722.     EXPECT_EQ(tree.mRoot->right->right->right->val, 7);
  723.     EXPECT_EQ(tree.mRoot->right->right->right->up, tree.mRoot->right->right);
  724.     EXPECT_EQ(tree.mRoot->right->right->right->left, nullptr);
  725.     EXPECT_EQ(tree.mRoot->right->right->right->right, nullptr);
  726.  
  727.     int dummy;
  728.     tree.find(5, dummy);
  729.     EXPECT_EQ(dummy, 3);
  730.  
  731.     EXPECT_EQ(tree.mRoot->val, 5);
  732.     EXPECT_EQ(tree.mRoot->up, nullptr);
  733.  
  734.     SplayTree<int>::Node* left = tree.mRoot->left;
  735.     SplayTree<int>::Node* right = tree.mRoot->right;
  736.  
  737.     EXPECT_EQ(left->val, 3);
  738.     EXPECT_EQ(left->left->val, 1);
  739.     EXPECT_EQ(left->right->val, 4);
  740.     EXPECT_EQ(left->up, tree.mRoot);
  741.  
  742.     EXPECT_EQ(left->left->up, left);
  743.     EXPECT_EQ(left->right->up, left);
  744.  
  745.     EXPECT_EQ(right->up, tree.mRoot);
  746.     EXPECT_EQ(right->val, 6);
  747.     EXPECT_EQ(right->left, nullptr);
  748.    
  749.     EXPECT_EQ(right->right->up, right);
  750.     EXPECT_EQ(right->right->val, 7);
  751. }
  752.  
  753. TEST(Splay, splay_on_one) {
  754.     SplayTree<int> tree;
  755.     tree.insert(0);
  756.     tree.splay(tree.mRoot);
  757.     EXPECT_EQ(tree.mRoot->val, 0);
  758.     EXPECT_EQ(tree.mRoot->left, nullptr);
  759.     EXPECT_EQ(tree.mRoot->right, nullptr);
  760.     EXPECT_EQ(tree.mRoot->up, nullptr);
  761. }
  762.  
  763. TEST(FindMax, repeated_max) {
  764.     SplayTree<int> tree;
  765.     tree.insert(0);
  766.     SplayTree<int>::Node* max = tree.insert(10);
  767.     tree.insert(1);
  768.     tree.insert(4);
  769.     EXPECT_EQ(tree.maximum(), max);
  770.     SplayTree<int>::Node* newMax = tree.insert(11);
  771.     EXPECT_EQ(tree.maximum(), newMax);
  772.     int dummy;
  773.     tree.find(0, dummy);
  774.     EXPECT_EQ(dummy, 4);
  775.     tree.find(1, dummy);
  776.     EXPECT_EQ(dummy, 2);
  777.     tree.find(4, dummy);
  778.     EXPECT_EQ(dummy, 2);
  779.     EXPECT_EQ(tree.maximum(), newMax);
  780. }
  781.  
  782. TEST(InsertFind, comprehensive_1) {
  783.     SplayTree<int> tree;
  784.  
  785.     tree.insert(10);
  786.     tree.insert(4);
  787.     tree.insert(6);
  788.     tree.insert(9);
  789.     tree.insert(13);
  790.     tree.insert(2);
  791.     tree.insert(7);
  792.     tree.insert(16);
  793.  
  794.     EXPECT_EQ(tree.mRoot->val, 16);
  795.     EXPECT_EQ(tree.mRoot->right, nullptr);
  796.     auto sedm = tree.mRoot->left;
  797.  
  798.     EXPECT_EQ(sedm->val, 7);
  799.  
  800.     auto dva  = sedm->left;
  801.     EXPECT_EQ(sedm->left->val, 2);
  802.    
  803.     auto trinc = sedm->right;
  804.     EXPECT_EQ(sedm->right->val, 13);
  805.    
  806.    
  807.     EXPECT_EQ(dva->right->val, 6);
  808.     EXPECT_EQ(trinc->left->val, 9);
  809.  
  810.     EXPECT_EQ(dva->right->left->val, 4);
  811.  
  812.     EXPECT_EQ(trinc->left->right->val, 10);
  813.     int dummy;
  814.     tree.find(7, dummy);
  815.     tree.find(9, dummy);
  816.     tree.find(4, dummy);
  817.     tree.find(10, dummy);
  818.     tree.find(13, dummy);
  819.     tree.find(2, dummy);
  820.     tree.find(9, dummy);
  821.     tree.find(2, dummy);
  822.     tree.find(4, dummy);
  823.     tree.find(16, dummy);
  824.     tree.find(7, dummy);
  825.     tree.find(4, dummy);
  826.     tree.find(9, dummy);
  827.     tree.find(13, dummy);
  828.  
  829.     trinc = tree.mRoot;
  830.  
  831.     EXPECT_EQ(trinc->val, 13);
  832.  
  833.     EXPECT_EQ(trinc->right->val, 16);
  834.    
  835.     auto devet = trinc->left;
  836.  
  837.     EXPECT_EQ(devet->val, 9);
  838.     EXPECT_EQ(devet->right->val, 10);
  839.  
  840.     auto ctyri = devet->left;
  841.     EXPECT_EQ(ctyri->val, 4);
  842.     EXPECT_EQ(ctyri->left->val, 2);
  843.     EXPECT_EQ(ctyri->right->val, 7);
  844.     EXPECT_EQ(ctyri->right->left->val, 6);
  845. }
  846.  
  847. TEST(Delete, deletes_all_simple)
  848. {
  849.     SplayTree<int> tree;
  850.     int dummy;
  851.     tree.insert(3);
  852.     tree.insert(4);
  853.     tree.insert(5);
  854.     tree.find(4, dummy);
  855.     EXPECT_EQ(dummy, 1);
  856.  
  857.     EXPECT_EQ(3, tree.reset());
  858. }
  859.  
  860. TEST(Delete, deletes_all)
  861. {
  862.     SplayTree<int> tree;
  863.  
  864.     tree.insert(10);
  865.     tree.insert(4);
  866.     tree.insert(6);
  867.     tree.insert(9);
  868.     tree.insert(13);
  869.     tree.insert(2);
  870.     tree.insert(7);
  871.     tree.insert(16);
  872.  
  873.     EXPECT_EQ(8, tree.reset());
  874. }
  875.  
  876. TEST(Delete, deletes_big) {
  877.     srand(1337);
  878.     SplayTree<int> tree;
  879.  
  880.     int vertCount = 300000;
  881.     for (int i = 0; i < vertCount; ++i) {
  882.         tree.insert(vertCount - i);
  883.     }
  884.  
  885.     EXPECT_EQ(tree.reset(), vertCount);
  886. }
  887.  
  888. TEST(ERASE, erase1) {
  889.     SplayTree<int> tree;
  890.     tree.insert(3);
  891.     tree.insert(4);
  892.     tree.insert(5);
  893.  
  894.     tree.erase(3);
  895.     int dummy;
  896.     EXPECT_EQ(tree.size(), 2);
  897.  
  898.     EXPECT_TRUE(tree.mRoot->val == 4 || tree.mRoot->val == 5);
  899.    
  900.     if (tree.mRoot->val == 4) {
  901.         EXPECT_TRUE(tree.mRoot->right->val == 5);
  902.         EXPECT_EQ(tree.mRoot->right->up, tree.mRoot);
  903.     }
  904.     else {
  905.         EXPECT_TRUE(tree.mRoot->left->val == 4);
  906.         EXPECT_EQ(tree.mRoot->left->up, tree.mRoot);
  907.     }
  908.     EXPECT_TRUE(tree.find(5, dummy));
  909.     EXPECT_EQ(tree.find(3, dummy), nullptr);
  910.     EXPECT_NE(tree.find(4, dummy), nullptr);
  911.  
  912.     tree.insert(3);
  913.     EXPECT_NE(tree.find(3, dummy), nullptr);
  914.     tree.erase(3);
  915.     EXPECT_EQ(tree.find(3, dummy), nullptr);
  916.     EXPECT_FALSE(tree.erase(3));
  917.     EXPECT_TRUE(tree.erase(4));
  918.     EXPECT_TRUE(tree.erase(5));
  919.     EXPECT_TRUE(tree.empty());
  920. }
  921.  
  922. struct instr
  923. {
  924.     char instruct;
  925.     int elem;
  926. };
  927.  
  928. class Executer {
  929.  
  930.     #define BATCH_SIZE 50000
  931.  
  932.     int currentN;
  933.  
  934.     int findCount;
  935.  
  936.     int avgFindLen;
  937.  
  938.     bool read1k(std::vector<std::string>& instructions)
  939.     {
  940.         instructions.clear();
  941.  
  942.         instructions.reserve(BATCH_SIZE);
  943.         std::string line;
  944.         for (int i = 0; i < BATCH_SIZE; ++i) {
  945.             if (!std::getline(std::cin, line))
  946.                 return false;
  947.             instructions.push_back(line);
  948.         }
  949.         return true;
  950.     }
  951.  
  952.     void execute(const std::vector<std::string>& instructions, SplayTree<int>& tree)
  953.     {
  954.         for (const auto& instruction : instructions) {
  955.             if (instruction[0] == 'I') {
  956.                 tree.insert(atoi(instruction.c_str() + 2));
  957.                 //std::cout << "I " << atoi(instruction.c_str() + 2) << "\n";
  958.             }
  959.             else if (instruction[0] == 'F') {
  960.                 int pathLen;
  961.                 tree.find(atoi(instruction.c_str() + 2), pathLen);
  962.                 avgFindLen += pathLen;
  963.                 findCount++;
  964.                 //std::cout << "F " << atoi(instruction.c_str() + 2) << ", len: " << pathLen << "\n";
  965.             }
  966.             else if (instruction[0] == '#') {
  967.                 if (!tree.empty()) {
  968.                     tree.reset();
  969.  
  970.                     std::cout << "N;" << currentN <<
  971.                         ";AvgLen;" << float(float(avgFindLen) / findCount) <<
  972.                         ";CumulLen;" << avgFindLen <<
  973.                         ";findCount;" << findCount << "\n";
  974.                 }
  975.                 currentN = atoi(instruction.c_str() + 2);
  976.                 avgFindLen = 0;
  977.                 findCount = 0;         
  978.             }
  979.         }
  980.     }
  981. public:
  982.     Executer() : currentN(0), findCount(0), avgFindLen(0) {};
  983.  
  984.     void readInput() {
  985.         SplayTree<int> tree;
  986.  
  987.         std::vector<std::string> instructions;
  988.         bool contRead = true;
  989.         while (contRead) {
  990.             contRead = read1k(instructions);
  991.             execute(instructions, tree);
  992.         }
  993.         tree.reset();
  994.         std::cout << "N;" << currentN <<
  995.             ";AvgLen;" << float(float(avgFindLen) / findCount) <<
  996.             ";CumulLen;" << avgFindLen <<
  997.             ";findCount;" << findCount << "\n";
  998.     }
  999.  
  1000. };
  1001.  
  1002. int main(int argc, wchar_t** argv) {   
  1003.     //// Google test
  1004.     //::testing::InitGoogleTest(&argc, argv);
  1005.     //RUN_ALL_TESTS();
  1006.  
  1007. #ifdef LAZY_SPLAY
  1008.     std::cout << "LAZY SPLAY\n";
  1009. #endif
  1010.  
  1011.     // Runtime
  1012.     Executer exec;
  1013.     exec.readInput();
  1014.     std::cout << "end";
  1015. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!