API tools faq
paste
Advertisement
LegoSosiska

LEGENDARY TREES (sfml required)

LegoSosiska
Apr 27th, 2022
729
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 53.96 KB | None | 0 0
raw download clone embed print report
  1. #include <SFML/Graphics.hpp>
  2. #include <SFML/Window.hpp>
  3. #include <algorithm>
  4. #include <cmath>
  5. #include <iostream>
  6. #include <queue>
  7. #include <vector>
  8.  
  9. struct Node {
  10.   Node* left = nullptr;
  11.   Node* right = nullptr;
  12.   Node* prev = nullptr;
  13.   int key = 0;
  14.   int priority = 0;
  15.   int color = 0;
  16.   int height = 1;
  17.   int size = 1;
  18. };
  19.  
  20. void Swap(Node*& a, Node*& b) {}
  21.  
  22. int Size(Node* treap) { return treap == nullptr ? 0 : treap->size; }
  23.  
  24. int Recalc(Node* treap) { return Size(treap->left) + Size(treap->right) + 1; }
  25.  
  26. Node* Create(int key, int color = 0) {
  27.   Node* p = new Node;
  28.   p->key = key;
  29.   p->color = color;
  30.   p->priority = std::rand() % 1000000000;
  31.   return p;
  32. }
  33.  
  34. bool CheckColor(Node* p) {
  35.   if (p == nullptr) return true;
  36.   if (p->color == 0) return true;
  37.   if (p->color == 1) return false;
  38. }
  39.  
  40. struct Avl {
  41.   Node* root = nullptr;
  42.  
  43.   Node* find(int key, Node* search) {
  44.     if (search == nullptr) {
  45.       return nullptr;
  46.     }
  47.     if (search->key == key) {
  48.       return search;
  49.     }
  50.     if (key > search->key) {
  51.       return find(key, search->right);
  52.     }
  53.     if (key < search->key) {
  54.       return find(key, search->left);
  55.     }
  56.   }
  57.  
  58.   void fixHeight(Node* p) {
  59.     if (p == nullptr) {
  60.       return;
  61.     }
  62.     int left = 0, right = 0;
  63.     if (p->left != nullptr) {
  64.       left = p->left->height;
  65.       p->left->prev = p;
  66.     }
  67.     if (p->right != nullptr) {
  68.       right = p->right->height;
  69.       p->right->prev = p;
  70.     }
  71.     p->height = std::max(left, right) + 1;
  72.   }
  73.  
  74.   int dif(Node* p) {
  75.     if (p == nullptr) {
  76.       return 0;
  77.     }
  78.     int left = 0, right = 0;
  79.     if (p->left != nullptr) {
  80.       left = p->left->height;
  81.     }
  82.     if (p->right != nullptr) {
  83.       right = p->right->height;
  84.     }
  85.     return right - left;
  86.   }
  87.  
  88.   void rotateSmall(Node*& p, bool direction) {
  89.     if (p == nullptr) {
  90.       return;
  91.     }
  92.     Node* q;
  93.     if (!direction) {
  94.       q = p->right;
  95.       p->right = q->left;
  96.       q->left = p;
  97.     } else {
  98.       q = p->left;
  99.       p->left = q->right;
  100.       q->right = p;
  101.     }
  102.     fixHeight(p);
  103.     fixHeight(q);
  104.     p = q;
  105.   }
  106.  
  107.   void rotateBig(Node*& p, bool direction) {
  108.     if (p == nullptr) {
  109.       return;
  110.     }
  111.     Node *q, *r;
  112.     if (!direction) {
  113.       q = p->right;
  114.       r = q->left;
  115.       q->left = r->right;
  116.       p->right = r->left;
  117.       r->left = p;
  118.       r->right = q;
  119.     } else {
  120.       q = p->left;
  121.       r = q->right;
  122.       q->right = r->left;
  123.       p->left = r->right;
  124.       r->right = p;
  125.       r->left = q;
  126.     }
  127.     fixHeight(p);
  128.     fixHeight(q);
  129.     fixHeight(r);
  130.     p = r;
  131.   }
  132.  
  133.   void balance(Node*& p) {
  134.     if (p == nullptr) {
  135.       return;
  136.     }
  137.     fixHeight(p);
  138.     if (dif(p) == 2) {
  139.       if (dif(p->right) < 0) {
  140.           rotateBig(p, false);
  141.           return;
  142.       }
  143.       rotateSmall(p, false);
  144.      
  145.     }
  146.     if (dif(p) == -2) {
  147.       if (dif(p->left) > 0) {
  148.           rotateBig(p, true);
  149.           return;
  150.       }
  151.       rotateSmall(p, true);
  152.     }
  153.     return;
  154.   }
  155.  
  156.   bool insert(int key, Node*& p) {
  157.       if (find(key, root) != nullptr) {
  158.           return false;
  159.       }
  160.       if (p == nullptr) {
  161.           p = Create(key);
  162.           if (root == nullptr) {
  163.               root = p;
  164.           }
  165.           balance(p);
  166.           return true;
  167.       }
  168.       if (key < p->key) {
  169.           insert(key, p->left);
  170.       }
  171.       else {
  172.           insert(key, p->right);
  173.       }
  174.       balance(p);
  175.       return true;
  176.   }
  177.  
  178.   Node* findMin(Node* search) {
  179.     if (search == nullptr) {
  180.         return nullptr;
  181.     }
  182.     if (search->left == nullptr) {
  183.       return search;
  184.     }
  185.     return findMin(search->left);
  186.   }
  187.  
  188.   void removeMin(Node*& search) {
  189.     if (search == nullptr) {
  190.       return;
  191.     }
  192.     if (search->left == nullptr) {
  193.       Node* toDelete = search;
  194.       search = search->right;
  195.       delete toDelete;
  196.       return;
  197.     }
  198.     removeMin(search->left);
  199.     balance(search);
  200.   }
  201.  
  202.   bool remove(int key, Node*& p) {
  203.     if (p == nullptr || find(key, root) == nullptr) {
  204.         return false;
  205.     }
  206.     if (key < p->key) {
  207.         remove(key, p->left);
  208.     }
  209.     else if (key > p->key) {
  210.         remove(key, p->right);
  211.     }
  212.     else {
  213.         Node* left = p->left;
  214.         if (p->right == nullptr) {
  215.             if (left == nullptr) {
  216.                 Node* toDelete = p;
  217.                 p = nullptr;
  218.                 delete toDelete;
  219.                 return true;
  220.             }
  221.             else {
  222.                 Node* toDelete = p;
  223.                 p = p->left;
  224.                 delete toDelete;
  225.                 return true;
  226.             }
  227.         }
  228.         Node* min = findMin(p->right);
  229.         p->key = min->key;
  230.         removeMin(p->right);
  231.         balance(p);
  232.         return true;
  233.     }
  234.     balance(p);
  235.     return true;
  236.   }
  237. };
  238.  
  239. struct Treap {
  240.     Node* root = nullptr;
  241.     Node* cur = nullptr;
  242.     Node* splitLeft = nullptr, * splitRight = nullptr;
  243.  
  244.     Node* find(int key, Node* search) {
  245.         if (search == nullptr) {
  246.             return nullptr;
  247.         }
  248.         if (search->key == key) {
  249.             return search;
  250.         }
  251.         if (key > search->key) {
  252.             return find(key, search->right);
  253.         }
  254.         if (key < search->key) {
  255.             return find(key, search->left);
  256.         }
  257.     }
  258.  
  259.     void split(int key, Node* treap, Node*& left, Node*& right) {
  260.         Node* newNode = nullptr;
  261.         if (treap == nullptr) {
  262.             left = nullptr;
  263.             right = nullptr;
  264.             return;
  265.         }
  266.         if (treap->key < key) {
  267.             if (treap->right == nullptr) {
  268.                 right = nullptr;
  269.                 left = treap;
  270.             }
  271.             else {
  272.                 split(key, treap->right, newNode, right);
  273.                 left = treap;
  274.                 left->right = newNode;
  275.             }
  276.         }
  277.         else {
  278.             if (treap->left == nullptr) {
  279.                 left = nullptr;
  280.                 right = treap;
  281.             }
  282.             else {
  283.                 split(key, treap->left, left, newNode);
  284.                 right = treap;
  285.                 right->left = newNode;
  286.             }
  287.         }
  288.     }
  289.  
  290.     Node* merge(Node* left, Node* right) {
  291.         if (left == nullptr) {
  292.             return right;
  293.         }
  294.         if (right == nullptr) {
  295.             return left;
  296.         }
  297.         if (right->priority > left->priority) {
  298.             Node* newNode = merge(left->right, right);
  299.             left->right = newNode;
  300.             return left;
  301.         }
  302.         else {
  303.             Node* newNode = merge(left, right->left);
  304.             right->left = newNode;
  305.             return right;
  306.         }
  307.     }
  308.  
  309.     Node* insert(int key) {
  310.         if (find(key, root) != nullptr) {
  311.             return nullptr;
  312.         }
  313.         Node* node = Create(key);
  314.         if (root == nullptr) {
  315.             root = node;
  316.             return root;
  317.         }
  318.         Node* left, * right;
  319.         split(key, root, left, right);
  320.         left = merge(left, node);
  321.         root = merge(left, right);
  322.         return root;
  323.     }
  324.  
  325.     void remove(int key) {
  326.         if (find(key, root) == nullptr) {
  327.             return;
  328.         }
  329.         Node* left, * right2, * right, * toDelete;
  330.         split(key, root, left, right);
  331.         split(key + 1, right, toDelete, right2);
  332.         if (right2 == nullptr) {
  333.             if (left == nullptr) {
  334.                 delete toDelete;
  335.                 root = nullptr;
  336.                 return;
  337.             }
  338.             else {
  339.                 root = left;
  340.                 return;
  341.             }
  342.         }
  343.         delete toDelete;
  344.         root = merge(left, right2);
  345.     }
  346. };
  347.  
  348. struct Splay {
  349.     Node* root = nullptr;
  350.  
  351.     Node* find(int key, Node* search) {
  352.         if (search == nullptr) {
  353.             return nullptr;
  354.         }
  355.         if (search->key == key) {
  356.             return splay(search);
  357.         }
  358.         if (key > search->key && search->right != nullptr) {
  359.             return find(key, search->right);
  360.         }
  361.         if (key < search->key && search->left != nullptr) {
  362.             return find(key, search->left);
  363.         }
  364.         return splay(search);
  365.     }
  366.  
  367.     void rotate(Node* par, Node* chld) {
  368.         Node* gpa = par->prev;
  369.         if (gpa != nullptr) {
  370.             if (gpa->left == par) {
  371.                 gpa->left = chld;
  372.             }
  373.             else {
  374.                 gpa->right = chld;
  375.             }
  376.         }
  377.         if (par->left == chld) {
  378.             par->left = chld->right;
  379.             if (chld->right != nullptr) {
  380.                 chld->right->prev = par;
  381.             }
  382.             chld->right = par;
  383.             par->prev = chld;
  384.         }
  385.         else {
  386.             par->right = chld->left;
  387.             if (chld->left != nullptr) {
  388.                 chld->left->prev = par;
  389.             }
  390.             chld->left = par;
  391.             par->prev = chld;
  392.         }
  393.         chld->prev = gpa;
  394.     }
  395.  
  396.     Node* splay(Node* p) {
  397.         if (p->prev == nullptr) {
  398.             return p;
  399.         }
  400.         Node* par = p->prev;
  401.         Node* gpa = p->prev->prev;
  402.         if (gpa == nullptr) {
  403.             rotate(par, p);
  404.             return p;
  405.         }
  406.         else {
  407.             if (gpa->left == par && par->left == p) {
  408.                 rotate(gpa, par);
  409.                 rotate(par, p);
  410.             }
  411.             else {
  412.                 rotate(par, p);
  413.                 rotate(gpa, p);
  414.             }
  415.             return splay(p);
  416.         }
  417.     }
  418.  
  419.     void split(Node*& p, Node*& left, Node*& right, int key) {
  420.         if (p == nullptr) {
  421.             left = nullptr;
  422.             right = nullptr;
  423.             return;
  424.         }
  425.         p = find(key, p);
  426.         if (p->key == key) {
  427.             if (p->left != nullptr) {
  428.                 p->left->prev = nullptr;
  429.             }
  430.             if (p->right != nullptr) {
  431.                 p->right->prev = nullptr;
  432.             }
  433.             right = p->right;
  434.             left = p->left;
  435.             return;
  436.         }
  437.         if (p->key < key) {
  438.             right = p->right;
  439.             p->right = nullptr;
  440.             if (right != nullptr) {
  441.                 right->prev = nullptr;
  442.             }
  443.             left = p;
  444.             p = nullptr;
  445.             return;
  446.         }
  447.         if (p->key > key) {
  448.             left = p->left;
  449.             p->left = nullptr;
  450.             if (left != nullptr) {
  451.                 left->prev = nullptr;
  452.             }
  453.             right = p;
  454.             p = nullptr;
  455.             return;
  456.         }
  457.     }
  458.  
  459.     void insert(int key) {
  460.         Node* left, * right;
  461.         split(root, left, right, key);
  462.         if (root == nullptr) {
  463.             root = Create(key);
  464.         }
  465.         root->left = left;
  466.         root->right = right;
  467.         if (left != nullptr) {
  468.             left->prev = root;
  469.         }
  470.         if (right != nullptr) {
  471.             right->prev = root;
  472.         }
  473.     }
  474.  
  475.     Node* merge(Node* left, Node* right) {
  476.         if (left == nullptr) return right;
  477.         if (right == nullptr) return left;
  478.         right = find(left->key, right);
  479.         right->left = left;
  480.         left->prev = right;
  481.         return right;
  482.     }
  483.  
  484.     bool remove(int key) {
  485.         root = find(key, root);
  486.         if (root == nullptr) {
  487.             return false;
  488.         }
  489.         if (root->key != key) {
  490.             return false;
  491.         }
  492.         Node* left = root->left, * right = root->right;
  493.         if (left != nullptr) {
  494.             left->prev = nullptr;
  495.         }
  496.         if (right != nullptr) {
  497.             right->prev = nullptr;
  498.         }
  499.         root = merge(left, right);
  500.         return true;
  501.     }
  502. };
  503.  
  504. struct RedBlack {
  505.     Node* root = nullptr;
  506.  
  507.     void insert(int key) {
  508.         if (find(key, root) != nullptr) {
  509.             return;
  510.         }
  511.         Node* p = Create(key, 1);
  512.         if (root == nullptr) {
  513.             root = p;
  514.             p->color = 0;
  515.             return;
  516.         }
  517.         place(p, root);
  518.         balance(p);
  519.     }
  520.  
  521.     Node* find(int key, Node* search) {
  522.         while (search != nullptr) {
  523.             if (search->key == key) {
  524.                 return search;
  525.             }
  526.             if (key > search->key) {
  527.                 search = search->right;
  528.             }
  529.             else {
  530.                 search = search->left;
  531.             }
  532.         }
  533.         return nullptr;
  534.     }
  535.  
  536.     void place(Node* q, Node* parent) {
  537.         if (q->key > parent->key) {
  538.             if (parent->right == nullptr) {
  539.                 parent->right = q;
  540.                 q->prev = parent;
  541.                 return;
  542.             }
  543.             place(q, parent->right);
  544.         }
  545.         else {
  546.             if (parent->left == nullptr) {
  547.                 parent->left = q;
  548.                 q->prev = parent;
  549.                 return;
  550.             }
  551.             place(q, parent->left);
  552.         }
  553.     }
  554.  
  555.     void balance(Node* p) {
  556.         while (p != root) {
  557.             if (p->prev == nullptr) {
  558.                 p->color = 0;
  559.                 return;
  560.             }
  561.             if (p->prev->color == 0) return;
  562.             Node* par = p->prev, * gpa = p->prev->prev;
  563.             Node* bro = (par == gpa->left ? gpa->right : gpa->left);
  564.             if (!CheckColor(bro)) {
  565.                 par->color = 0;
  566.                 bro->color = 0;
  567.                 gpa->color = 1;
  568.                 p = gpa;
  569.                 continue;
  570.             }
  571.             if (CheckColor(bro)) {
  572.                 if (p == par->right && par == gpa->left) {
  573.                     p->prev = gpa;
  574.                     par->prev = p;
  575.                     if (p->left != nullptr) {
  576.                         p->left->prev = par;
  577.                     }
  578.                     par->right = p->left;
  579.                     p->left = par;
  580.                     gpa->left = p;
  581.                     std::swap(par, p);
  582.                 }
  583.                 else if (p == par->left && par == gpa->right) {
  584.                     p->prev = gpa;
  585.                     par->prev = p;
  586.                     if (p->right != nullptr) {
  587.                         p->right->prev = par;
  588.                     }
  589.                     par->left = p->right;
  590.                     p->right = par;
  591.                     gpa->right = p;
  592.                     std::swap(par, p);
  593.                 }
  594.                 if (gpa->left == par) {
  595.                     if (gpa->prev == nullptr) {
  596.                         root = par;
  597.                     }
  598.                     else {
  599.                         if (gpa->prev->left == gpa) {
  600.                             gpa->prev->left = par;
  601.                         }
  602.                         else {
  603.                             gpa->prev->right = par;
  604.                         }
  605.                     }
  606.                     par->prev = gpa->prev;
  607.                     gpa->prev = par;
  608.                     gpa->left = par->right;
  609.                     if (par->right != nullptr) {
  610.                         par->right->prev = gpa;
  611.                     }
  612.                     par->right = gpa;
  613.                 }
  614.                 else {
  615.                     if (gpa->prev == nullptr) {
  616.                         root = par;
  617.                     }
  618.                     else {
  619.                         if (gpa->prev->left == gpa) {
  620.                             gpa->prev->left = par;
  621.                         }
  622.                         else {
  623.                             gpa->prev->right = par;
  624.                         }
  625.                     }
  626.                     par->prev = gpa->prev;
  627.                     gpa->prev = par;
  628.                     gpa->right = par->left;
  629.                     if (par->left != nullptr) {
  630.                         par->left->prev = gpa;
  631.                     }
  632.                     par->left = gpa;
  633.                 }
  634.                 par->color = 0;
  635.                 gpa->color = 1;
  636.                 return;
  637.             }
  638.         }
  639.         if (p == root) {
  640.             p->color = 0;
  641.         }
  642.     }
  643.  
  644.     bool erase(int key) {
  645.         Node* q = find(key, root);
  646.         if (q == nullptr) {
  647.             return false;
  648.         }
  649.         Node* min = findMin(q->right);
  650.         if (min == nullptr) {
  651.             min = findMax(q->left);
  652.             if (min == nullptr) {
  653.                 min = q;
  654.             }
  655.         }
  656.         if (!CheckColor(min)) {
  657.             q->key = min->key;
  658.             if (min->prev->left == min) {
  659.                 min->prev->left = nullptr;
  660.             }
  661.             else {
  662.                 min->prev->right = nullptr;
  663.             }
  664.             delete min;
  665.             return true;
  666.         }
  667.         else {
  668.             q->key = min->key;
  669.             if (min->right != nullptr) {
  670.                 min->key = min->right->key;
  671.                 delete min->right;
  672.                 min->right = nullptr;
  673.                 return true;
  674.             }
  675.             else if (min->left != nullptr) {
  676.                 min->key = min->left->key;
  677.                 delete min->left;
  678.                 min->left = nullptr;
  679.                 return true;
  680.             }
  681.             if (min->prev == nullptr) {
  682.                 delete min;
  683.                 root = nullptr;
  684.                 return true;
  685.             }
  686.             rbalance(min, min->prev,
  687.                 (min == min->prev->left ? min->prev->right : min->prev->left));
  688.             if (min->prev->left == min) {
  689.                 min->prev->left = nullptr;
  690.             }
  691.             else {
  692.                 min->prev->right = nullptr;
  693.             }
  694.             delete min;
  695.         }
  696.         // if (min == nullptr) min = q;
  697.         /*
  698.         q->key = min->key;
  699.         if (!CheckColor(min)) {
  700.           if (min->prev->left == min) {
  701.             min->prev->left = nullptr;
  702.           } else {
  703.             min->prev->right = nullptr;
  704.           }
  705.           delete min;
  706.           return true;
  707.         }
  708.         if (!CheckColor(min->right)) {
  709.           if (min->right != nullptr) {
  710.             min->right->prev = q->prev;
  711.             if (min->prev->left == min) {
  712.               min->prev->left = min->right;
  713.             } else {
  714.               min->prev->right = min->right;
  715.             }
  716.             min->left->color = 0;
  717.             delete min;
  718.             return true;
  719.           }
  720.         }
  721.  
  722.         Node* toDelete = min;
  723.         if (min->prev == nullptr) {
  724.           root = nullptr;
  725.           delete min;
  726.           return true;
  727.         }
  728.         if (min->prev->left == min) {
  729.           min->prev->left = min->right;
  730.         } else {
  731.           min->prev->right = min->right;
  732.         }
  733.         min = min->right;
  734.         delete toDelete;
  735.         rbalance(min);
  736.         return true;
  737.         */
  738.     }
  739.  
  740.     void rbalance(Node* p, Node* par, Node* bro) {
  741.        
  742.         while (p != root) {
  743.             if (bro == nullptr) {
  744.                 par = p->prev;
  745.                 bro = (par == p->prev->left ? p->prev->right : p->prev->left);
  746.             }
  747.             Node* d1, * d2;
  748.             if (p == par->left) {
  749.                 d1 = bro->left;
  750.                 d2 = bro->right;
  751.             }
  752.             else {
  753.                 d1 = bro->right;
  754.                 d2 = bro->left;
  755.             }
  756.             if (CheckColor(par) && CheckColor(bro) && CheckColor(d1) &&
  757.                 CheckColor(d2)) {
  758.                 bro->color = 1;
  759.                 if (par->prev == nullptr) {
  760.                     return;
  761.                 }
  762.                 p = par;
  763.                 par = par->prev;
  764.                 bro = (p == par->right ? par->left : par->right);
  765.                 continue;
  766.             }
  767.             if (!CheckColor(par) && CheckColor(bro) && CheckColor(d1) &&
  768.                 CheckColor(d2)) {
  769.                 par->color = 0;
  770.                 bro->color = 1;
  771.                 return;
  772.             }
  773.             if (CheckColor(bro) && !CheckColor(d2)) {
  774.                 if (par->prev != nullptr) {
  775.                     if (par->prev->right == par) {
  776.                         par->prev->right = bro;
  777.                     }
  778.                     else {
  779.                         par->prev->left = bro;
  780.                     }
  781.                 }
  782.                 else {
  783.                     root = bro;
  784.                 }
  785.                 bro->prev = par->prev;
  786.                 d2->color = 0;
  787.                 if (p == par->left) {
  788.                     par->right = d1;
  789.                     bro->left = par;
  790.                 }
  791.                 else {
  792.                     par->left = d1;
  793.                     bro->right = par;
  794.                 }
  795.                 if (d1 != nullptr) {
  796.                     d1->prev = par;
  797.                 }  
  798.                 par->prev = bro;
  799.                 bro->color = par->color;
  800.                 par->color = 0;
  801.                 return;
  802.             }
  803.             if (CheckColor(bro) && !CheckColor(d1) && CheckColor(d2)) {
  804.                 if (p == par->left) {
  805.                     par->right = d1;
  806.                     bro->left = d1->right;
  807.                     d1->right = bro;
  808.                     par->right = d1;
  809.                 }
  810.                 else {
  811.                     par->left = d1;
  812.                     bro->right = d1->left;
  813.                     d1->left = bro;
  814.                     par->left = d1;
  815.                 }
  816.                 d1->prev = par;
  817.                 bro->prev = d1;
  818.                 d1->color = 0;
  819.                 bro->color = 1;
  820.                 bro = d1;
  821.                 continue;
  822.             }
  823.             if (!CheckColor(bro)) {
  824.                 if (par->prev != nullptr) {
  825.                     if (par->prev->right == par) {
  826.                         par->prev->right = bro;
  827.                     }
  828.                     else {
  829.                         par->prev->left = bro;
  830.                     }
  831.                 }
  832.                 else {
  833.                     root = bro;
  834.                 }
  835.                 bro->prev = par->prev;
  836.                 par->prev = bro;
  837.                 if (p == par->left) {
  838.                     par->right = d1;
  839.                     bro->left = par;
  840.                 }
  841.                 else {
  842.                     par->left = d1;
  843.                     bro->right = par;
  844.                 }
  845.                 if (d1 != nullptr) {
  846.                     d1->prev = par;
  847.                 }
  848.                 par->color = 1;
  849.                 bro->color = 0;
  850.                 bro = d1;
  851.                 continue;
  852.             }
  853.             return;
  854.         }
  855.     }
  856.  
  857.     Node* findMin(Node* p) {
  858.         if (p == nullptr) {
  859.             return nullptr;
  860.         }
  861.         if (p->left == nullptr) {
  862.             return p;
  863.         }
  864.         return findMin(p->left);
  865.     }
  866.  
  867.     Node* findMax(Node* p) {
  868.         if (p == nullptr) {
  869.             return nullptr;
  870.         }
  871.         if (p->right == nullptr) {
  872.             return p;
  873.         }
  874.         return findMin(p->right);
  875.     }
  876. };
  877.  
  878. void InOrder(Node* p, int layer = 0) {
  879.   if (p == nullptr) return;
  880.   InOrder(p->left, layer + 1);
  881.   std::cout << p->key << " ";
  882.   InOrder(p->right, layer + 1);
  883. }
  884.  
  885. void TreeOrder(Node* p) {
  886.   int layer = 0;
  887.   std::queue<std::pair<Node*, int>> queue;
  888.   std::pair<Node*, int> blank;
  889.   if (p != nullptr) {
  890.     blank = {p, layer};
  891.     queue.push(blank);
  892.   }
  893.   while (!queue.empty()) {
  894.     if (queue.front().second > layer) {
  895.       std::cout << "\n";
  896.       ++layer;
  897.     }
  898.     Node* q = queue.front().first;
  899.     std::cout << q->key << " ";
  900.     queue.pop();
  901.     if (q->left != nullptr) {
  902.       blank.second = layer + 1;
  903.       blank.first = q->left;
  904.       queue.push(blank);
  905.     }
  906.     if (q->right != nullptr) {
  907.       blank.second = layer + 1;
  908.       blank.first = q->right;
  909.       queue.push(blank);
  910.     }
  911.   }
  912. }
  913.  
  914. sf::Font* font;
  915.  
  916. sf::Color textColor = sf::Color(232, 197, 71),
  917.           backgroundColor = sf::Color(34, 40, 49),
  918.           elementColor = sf::Color(254, 233, 225),
  919.           fillColor = sf::Color(57, 62, 70),
  920.           reactColor = sf::Color(217, 3, 104),
  921.           redFillColor = sf::Color(157, 62, 70),
  922.           touchColor = sf::Color::White;
  923.  
  924. struct RenderNode {
  925.     sf::RectangleShape rect;
  926.     sf::Text text;
  927.     sf::Text priority;
  928.     int height = 0;
  929.     Node* node = nullptr;
  930.     int key = 0;
  931.     sf::Vector2f scale;
  932.     RenderNode* left = nullptr, * right = nullptr;
  933.     int level;
  934.     int col;
  935.  
  936.     void create(Node* node, int key, int height, bool treap, float scale = 1) {
  937.         this->node = node;
  938.         this->key = key;
  939.         this->text.setString(std::to_string(key));
  940.         if (treap) {
  941.             priority.setString(std::to_string(node->priority));
  942.         }
  943.         //this->height = height;
  944.         this->level = height;
  945.  
  946.         sf::Vector2f sc = { scale, scale };
  947.         this->scale = sc;
  948.  
  949.         rect.setSize(sf::Vector2f(150, 60));
  950.  
  951.         // text.setOrigin(text.getGlobalBounds().width / 2,
  952.         // text.getGlobalBounds().height / 2);
  953.         rect.setOrigin(75, 30);
  954.         text.setOrigin(75, 20);
  955.         priority.setOrigin(75, -20);
  956.  
  957.         text.setFont(*font);
  958.         priority.setFont(*font);
  959.         rect.setOutlineThickness(1);
  960.  
  961.         if (node->color) {
  962.             rect.setFillColor(redFillColor);
  963.         }
  964.         else {
  965.             rect.setFillColor(fillColor);
  966.         }
  967.         text.setFillColor(textColor);
  968.         priority.setFillColor(reactColor);
  969.         rect.setOutlineColor(elementColor);
  970.  
  971.         text.setScale(this->scale);
  972.         priority.setScale(this->scale);
  973.         rect.setScale(this->scale);
  974.     }
  975.  
  976.     void grow(sf::Vector2f scale) {
  977.         this->scale = scale;
  978.         text.setScale(scale);
  979.         rect.setScale(scale);
  980.     }
  981.  
  982.     void setPos(sf::Vector2f pos) {
  983.         rect.setPosition(pos);
  984.         text.setPosition(pos);
  985.         priority.setPosition(pos);
  986.     }
  987.  
  988.     void draw(sf::RenderWindow& window) {
  989.         window.draw(rect);
  990.         window.draw(text);
  991.         window.draw(priority);
  992.     }
  993.  
  994.     bool contains(float x, float y) {
  995.         return rect.getGlobalBounds().contains(x, y);
  996.     }
  997. };
  998.  
  999. struct RenderTree {
  1000.     std::vector<sf::Vertex> connections;
  1001.     RenderNode* root = nullptr;
  1002.     int height;
  1003.     /*
  1004.     void create(Node* tree, sf::Vector2f pos, float scale) {
  1005.       int height = 0;
  1006.       RenderNode* rend = createNodes(tree, height, scale);
  1007.       root = rend;
  1008.       positionNodes(rend, pos, height);
  1009.       this->height = height;
  1010.     }
  1011.  
  1012.     void positionNodes(RenderNode* rend, sf::Vector2f pos, int height) {
  1013.       if (rend == nullptr) return;
  1014.       rend->setPos(pos);
  1015.       positionNodes(rend->left,
  1016.                     {pos.x - 80 * (int)pow(2, height - 2) * rend->scale.x,
  1017.                      pos.y + 200 * rend->scale.x},
  1018.                     height - 1);
  1019.       positionNodes(rend->right,
  1020.                     {pos.x + 80 * (int)pow(2, height - 2) * rend->scale.x,
  1021.                      pos.y + 200 * rend->scale.x},
  1022.                     height - 1);
  1023.       return;
  1024.     }
  1025.  
  1026.     RenderNode* createNodes(Node* tree, int& height, float scale) {
  1027.       if (tree == nullptr) {
  1028.         return nullptr;
  1029.       }
  1030.  
  1031.       int h1 = height, h2 = height;
  1032.       RenderNode* rend = new RenderNode;
  1033.       rend->left = createNodes(tree->left, h1, scale);
  1034.       rend->right = createNodes(tree->right, h2, scale);
  1035.       height = std::max(h1, h2) + 1;
  1036.       rend->create(tree, tree->key, height, scale);
  1037.       return rend;
  1038.     }
  1039.  
  1040.     void scale(RenderNode* rend, float scaleNum) {
  1041.       if (rend == nullptr) return;
  1042.       sf::Vector2f s = {scaleNum, scaleNum};
  1043.       rend->grow(s);
  1044.       scale(rend->left, scaleNum);
  1045.       scale(rend->right, scaleNum);
  1046.     }
  1047.     */
  1048.     void create(Node* tree, bool treap = false) {
  1049.         int col = 0;
  1050.         root = buildShadowTree(tree, 0, col, treap);
  1051.         positionNodes(root);
  1052.     }
  1053.  
  1054.     RenderNode* buildShadowTree(Node* tree, int level, int& col, bool treap) {
  1055.         if (tree == nullptr) return nullptr;
  1056.         RenderNode* newNode = new RenderNode;
  1057.         newNode->create(tree, tree->key, level, treap);
  1058.  
  1059.         RenderNode* newLeft = buildShadowTree(tree->left, level + 1, col, treap);
  1060.         newNode->left = newLeft;
  1061.  
  1062.         newNode->col = col;
  1063.         ++col;
  1064.  
  1065.         RenderNode* newRight = buildShadowTree(tree->right, level + 1, col, treap);
  1066.         newNode->right = newRight;
  1067.  
  1068.         return newNode;
  1069.     }
  1070.  
  1071.     void positionNodes(RenderNode* rend) {
  1072.         if (rend == nullptr) return;
  1073.         sf::Vector2f pos = { float(rend->col * 200), float(rend->level * 80) };
  1074.         rend->setPos(pos);
  1075.         positionNodes(rend->left);
  1076.         positionNodes(rend->right);
  1077.     }
  1078.  
  1079.     void draw(sf::RenderWindow& window) { drawNodes(window, root); }
  1080.  
  1081.     void drawNodes(sf::RenderWindow& window, RenderNode* rend) {
  1082.         if (rend == nullptr) return;
  1083.         //sf::Vector2f pos = { rend->rect.getPosition().x, rend->rect.getPosition().y };
  1084.         //std::cout << rend->node->key << " " << pos.x << ' ' << pos.y << "\n";
  1085.         if (rend->left != nullptr) {
  1086.             sf::Vector2f pos1, pos2;
  1087.             pos1 = { rend->rect.getPosition().x, rend->rect.getPosition().y };
  1088.             pos2 = { rend->left->rect.getPosition().x,
  1089.                     rend->left->rect.getPosition().y };
  1090.             sf::Vertex line[] = { sf::Vertex(pos1), sf::Vertex(pos2) };
  1091.             window.draw(line, 2, sf::Lines);
  1092.            
  1093.         }
  1094.         if (rend->right != nullptr) {
  1095.             sf::Vector2f pos1, pos2;
  1096.             pos1 = { rend->rect.getPosition().x, rend->rect.getPosition().y };
  1097.             pos2 = { rend->right->rect.getPosition().x,
  1098.                     rend->right->rect.getPosition().y };
  1099.             sf::Vertex line[] = { sf::Vertex(pos1), sf::Vertex(pos2) };
  1100.             window.draw(line, 2, sf::Lines);
  1101.         }
  1102.         rend->draw(window);
  1103.         drawNodes(window, rend->left);
  1104.         drawNodes(window, rend->right);
  1105.     }
  1106.  
  1107.     void clear() {
  1108.         connections.clear();
  1109.         clearNodes(root);
  1110.         root = nullptr;
  1111.     }
  1112.  
  1113.     void clearNodes(RenderNode* rend) {
  1114.         if (rend == nullptr) {
  1115.             return;
  1116.         }
  1117.         clearNodes(rend->left);
  1118.         clearNodes(rend->right);
  1119.         delete rend;
  1120.     }
  1121.  
  1122.     /* bool contains(float x, float y, int type, RenderNode* node = nullptr, bool
  1123.      first = false) { if (node == nullptr && !first) { node = root; first = true;
  1124.          }
  1125.          if (node == nullptr) return;
  1126.          if (node->rect.getGlobalBounds().contains(x, y)) {
  1127.              erase()
  1128.          }
  1129.      }*/
  1130. };
  1131.  
  1132. void InOrder2(RenderNode* p, int layer = 0) {
  1133.     if (p == nullptr) return;
  1134.     InOrder2(p->left, layer + 1);
  1135.     std::cout << p->key << " ";
  1136.     InOrder2(p->right, layer + 1);
  1137. }
  1138.  
  1139. void UpdateText(sf::Text& text, std::string s) { text.setString(s); }
  1140.  
  1141. RenderNode* MousePressed(float x, float y, RenderNode* node) {
  1142.     if (node == nullptr) return nullptr;
  1143.     //std::cout << node->rect.getGlobalBounds().left << "\n";
  1144.     if (node->contains(x, y)) {
  1145.         return node;
  1146.     }
  1147.     RenderNode* left = MousePressed(x, y, node->left);
  1148.     RenderNode* right = MousePressed(x, y, node->right);
  1149.     if (left != nullptr) return left;
  1150.     return right;
  1151. }
  1152.  
  1153. int Convetr(std::string s) {
  1154.     bool minus = false;
  1155.     int i = 0, ans = 0;
  1156.     if (s[i] == '-') {
  1157.         minus = true;
  1158.         ++i;
  1159.     }
  1160.     while (i < s.size()) {
  1161.         ans *= 10;
  1162.         ans += s[i] - '0';
  1163.         ++i;
  1164.     }
  1165.     if (minus) {
  1166.         ans = ans * -1;
  1167.     }
  1168.     return ans;
  1169. }
  1170.  
  1171. int main() {
  1172.     sf::RenderWindow window(sf::VideoMode(1000, 1000), "FUNKY GROOVY");
  1173.  
  1174.     // RedBlack splay;
  1175.     RenderTree renderTree;
  1176.     sf::Vertex line[] = { sf::Vertex(sf::Vector2f(10.f, 10.f)),
  1177.                          sf::Vertex(sf::Vector2f(150.f, 150.f)) };
  1178.  
  1179.     std::string addText, delText, addNtext;
  1180.     sf::RectangleShape addNodeBox, removeNodeBox, addNBox, addNodeButton, removeNodeButton, treetype1, treetype2, treetype3,
  1181.         treetype4;
  1182.     sf::Text addDisplayText, delDisplayText, addNDisplayText, addButtonText, delButtonText, treetext1, treetext2, treetext3, treetext4;
  1183.  
  1184.     addDisplayText.setPosition(402, 944);
  1185.     delDisplayText.setPosition(702, 944);
  1186.     addNDisplayText.setPosition(402, 892);
  1187.     addButtonText.setPosition(562, 944);
  1188.     delButtonText.setPosition(862, 944);
  1189.  
  1190.     treetext1.setPosition(52, 944);
  1191.     treetext2.setPosition(132, 944);
  1192.     treetext3.setPosition(212, 944);
  1193.     treetext4.setPosition(292, 944);
  1194.  
  1195.     addNDisplayText.setOutlineThickness(2);
  1196.     addDisplayText.setOutlineThickness(2);
  1197.     addButtonText.setFillColor(textColor);
  1198.     delButtonText.setFillColor(textColor);
  1199.     addDisplayText.setFillColor(textColor);
  1200.     addNDisplayText.setFillColor(textColor);
  1201.     delDisplayText.setOutlineThickness(2);
  1202.     addButtonText.setOutlineThickness(2);
  1203.     delButtonText.setOutlineThickness(2);
  1204.     delDisplayText.setFillColor(textColor);
  1205.  
  1206.     treetext1.setOutlineThickness(2);
  1207.     treetext3.setFillColor(textColor);
  1208.     treetext4.setFillColor(textColor);
  1209.     treetext1.setFillColor(textColor);
  1210.     treetext2.setOutlineThickness(2);
  1211.     treetext3.setOutlineThickness(2);
  1212.     treetext4.setOutlineThickness(2);
  1213.     treetext2.setFillColor(textColor);
  1214.  
  1215.     addNodeBox.setSize(sf::Vector2f(150, 30));
  1216.     removeNodeBox.setSize(sf::Vector2f(150, 30));
  1217.     addNBox.setSize(sf::Vector2f(150, 30));
  1218.  
  1219.     addNodeBox.setPosition(400, 950);
  1220.     removeNodeBox.setPosition(700, 950);
  1221.     addNBox.setPosition(400, 898);
  1222.  
  1223.     addNodeBox.setOutlineThickness(2);
  1224.     addNodeBox.setOutlineColor(elementColor);
  1225.     addNodeBox.setFillColor(fillColor);
  1226.     removeNodeBox.setOutlineThickness(2);
  1227.     removeNodeBox.setOutlineColor(elementColor);
  1228.     removeNodeBox.setFillColor(fillColor);
  1229.     addNBox.setOutlineThickness(2);
  1230.     addNBox.setOutlineColor(elementColor);
  1231.     addNBox.setFillColor(fillColor);
  1232.  
  1233.     addNodeButton.setSize(sf::Vector2f(50, 30));
  1234.     removeNodeButton.setSize(sf::Vector2f(50, 30));
  1235.  
  1236.     addNodeButton.setPosition(560, 950);
  1237.     removeNodeButton.setPosition(860, 950);
  1238.  
  1239.     addNodeButton.setOutlineThickness(2);
  1240.     addNodeButton.setOutlineColor(elementColor);
  1241.     addNodeButton.setFillColor(fillColor);
  1242.     removeNodeButton.setOutlineThickness(2);
  1243.     removeNodeButton.setOutlineColor(elementColor);
  1244.     removeNodeButton.setFillColor(fillColor);
  1245.  
  1246.     treetype1.setSize(sf::Vector2f(50, 30));
  1247.     treetype2.setSize(sf::Vector2f(50, 30));
  1248.     treetype3.setSize(sf::Vector2f(50, 30));
  1249.     treetype4.setSize(sf::Vector2f(50, 30));
  1250.  
  1251.     treetype1.setPosition(50, 950);
  1252.     treetype2.setPosition(130, 950);
  1253.     treetype3.setPosition(210, 950);
  1254.     treetype4.setPosition(290, 950);
  1255.  
  1256.     treetype1.setOutlineThickness(2);
  1257.     treetype1.setOutlineColor(reactColor);
  1258.     treetype1.setFillColor(fillColor);
  1259.     treetype2.setOutlineThickness(2);
  1260.     treetype2.setOutlineColor(elementColor);
  1261.     treetype2.setFillColor(fillColor);
  1262.     treetype3.setOutlineThickness(2);
  1263.     treetype3.setOutlineColor(elementColor);
  1264.     treetype3.setFillColor(fillColor);
  1265.     treetype4.setOutlineThickness(2);
  1266.     treetype4.setOutlineColor(elementColor);
  1267.     treetype4.setFillColor(fillColor);
  1268.  
  1269.     font = new sf::Font;
  1270.     if (!font->loadFromFile("UbuntuMono-Regular.ttf")) {
  1271.         std::cout << "err\n";
  1272.     }
  1273.  
  1274.     addNDisplayText.setFont(*font);
  1275.     addDisplayText.setFont(*font);
  1276.     delDisplayText.setFont(*font);
  1277.     addButtonText.setFont(*font);
  1278.     delButtonText.setFont(*font);
  1279.  
  1280.     treetext1.setFont(*font);
  1281.     treetext2.setFont(*font);
  1282.     treetext3.setFont(*font);
  1283.     treetext4.setFont(*font);
  1284.  
  1285.     addButtonText.setString("ADD");
  1286.     delButtonText.setString("DEL");
  1287.  
  1288.     treetext1.setString("AVL");
  1289.     treetext2.setString("R/B");
  1290.     treetext3.setString("TRP");
  1291.     treetext4.setString("SPL");
  1292.  
  1293.     sf::Vector2f treePos = { 500, 50 };
  1294.     float scale = 1;
  1295.     int selected = 0;
  1296.     bool minus1 = false, minus2 = false;
  1297.  
  1298.     int treeType = 0;
  1299.     Avl avl;
  1300.     RedBlack redBlack;
  1301.     Treap treap;
  1302.     Splay splay;
  1303.  
  1304.     sf::View view(sf::Vector2f(500, 500), sf::Vector2f(1000, 1000));
  1305.  
  1306.     while (window.isOpen()) {
  1307.         sf::Event event;
  1308.         while (window.pollEvent(event)) {
  1309.             if (event.type == sf::Event::Closed) {
  1310.                 window.close();
  1311.             }
  1312.             if (event.type == sf::Event::KeyPressed) {
  1313.                 if (event.key.code == sf::Keyboard::Enter) {
  1314.                     if (selected == 1 || selected == 3) {
  1315.                         if (selected == 3) {
  1316.                             int n = Convetr(addNtext);
  1317.                             addNtext.clear();
  1318.                             UpdateText(addNDisplayText, addNtext);
  1319.                             for (int i = 0; i < n; ++i) {
  1320.                                 int ans = std::rand() % 1000000000;
  1321.                                 avl.insert(ans, avl.root);
  1322.                                 redBlack.insert(ans);
  1323.                                 treap.insert(ans);
  1324.                                 splay.insert(ans);
  1325.                             }
  1326.                         }
  1327.                         else if (selected == 1) {
  1328.                             int ans = Convetr(addText);
  1329.                             addText.clear();
  1330.                             UpdateText(addDisplayText, addText);
  1331.                             avl.insert(ans, avl.root);
  1332.                             redBlack.insert(ans);
  1333.                             treap.insert(ans);
  1334.                             splay.insert(ans);
  1335.                         }
  1336.                         if (treeType == 0) {
  1337.                             renderTree.create(avl.root);
  1338.                         }
  1339.                         if (treeType == 1) {
  1340.                             renderTree.create(redBlack.root);
  1341.                         }
  1342.                         if (treeType == 2) {
  1343.                             renderTree.create(treap.root, true);
  1344.                         }
  1345.                         if (treeType == 3) {
  1346.                             renderTree.create(splay.root);
  1347.                         }
  1348.                     }
  1349.                     if (selected == 2) {
  1350.                         int ans = Convetr(delText);
  1351.                         delText.clear();
  1352.                         UpdateText(delDisplayText, delText);
  1353.                         avl.remove(ans, avl.root);
  1354.                         redBlack.erase(ans);
  1355.                         treap.remove(ans);
  1356.                         splay.remove(ans);
  1357.                         if (treeType == 0) {
  1358.                             renderTree.create(avl.root);
  1359.                         }
  1360.                         if (treeType == 1) {
  1361.                             renderTree.create(redBlack.root);
  1362.                         }
  1363.                         if (treeType == 2) {
  1364.                             renderTree.create(treap.root, true);
  1365.                         }
  1366.                         if (treeType == 3) {
  1367.                             renderTree.create(splay.root);
  1368.                         }
  1369.                     }
  1370.                     if (renderTree.root != nullptr) {
  1371.                         view.setCenter(renderTree.root->col * 200, 400);
  1372.                     }
  1373.                 }
  1374.                 if (event.key.code == sf::Keyboard::P) {
  1375.                     /*if (scale <= 0.2) {
  1376.                        
  1377.                     }
  1378.                     else {
  1379.                         scale += 0.1;
  1380.                     }*/
  1381.                     //scale += 0.1;
  1382.                     view.zoom(0.9);
  1383.                     //renderTree.scale(renderTree.root, scale);
  1384.                     //renderTree.positionNodes(renderTree.root, treePos, renderTree.height);
  1385.                 }
  1386.                 if (event.key.code == sf::Keyboard::O) {
  1387.                     /*if (scale <= 0.2 && scale > 0.02) {
  1388.                         scale -= 0.02;
  1389.                         //renderTree.scale(renderTree.root, scale);
  1390.                         //renderTree.positionNodes(renderTree.root, treePos, renderTree.height);
  1391.                     }
  1392.                     else if (scale > 0.2) {
  1393.                        
  1394.                         //renderTree.scale(renderTree.root, scale);
  1395.                         //renderTree.positionNodes(renderTree.root, treePos, renderTree.height);
  1396.                     }*/
  1397.                     //scale -= 0.1;
  1398.                     view.zoom(1.1);
  1399.                 }
  1400.                 if (event.key.code == sf::Keyboard::Up) {
  1401.                     /*
  1402.                     if (scale <= 0.2) {
  1403.                         treePos.y += 5 * scale * 100;
  1404.                     }
  1405.                     else {
  1406.                         treePos.y += 5 * scale * 10;
  1407.                     }
  1408.                    
  1409.                     renderTree.positionNodes(renderTree.root, treePos, renderTree.height);
  1410.                     */
  1411.                     view.move(0, -10 * view.getSize().x / 500);
  1412.                    
  1413.                 }
  1414.                 if (event.key.code == sf::Keyboard::Down) {
  1415.                     /*
  1416.                     if (scale <= 0.2) {
  1417.                         treePos.y -= 5 * scale * 100;
  1418.                     }
  1419.                     else {
  1420.                         treePos.y -= 5 * scale * 10;
  1421.                     }
  1422.                     renderTree.positionNodes(renderTree.root, treePos, renderTree.height);
  1423.                     */
  1424.                     view.move(0, 10 * view.getSize().x / 500);
  1425.                 }
  1426.                 if (event.key.code == sf::Keyboard::Left) {
  1427.                     /*
  1428.                     if (scale <= 0.2) {
  1429.                         treePos.x += 5 * scale * 100;
  1430.                     }
  1431.                     else {
  1432.                         treePos.x += 5 * scale * 10;
  1433.                     }
  1434.                     renderTree.positionNodes(renderTree.root, treePos, renderTree.height);
  1435.                     */
  1436.                     view.move(-10 * view.getSize().x / 500, 0);
  1437.                 }
  1438.                 if (event.key.code == sf::Keyboard::Right) {
  1439.                     /*
  1440.                     if (scale <= 0.2) {
  1441.                         treePos.x -= 5 * scale * 100;
  1442.                     }
  1443.                     else {
  1444.                         treePos.x -= 5 * scale * 10;
  1445.                     }
  1446.                     renderTree.positionNodes(renderTree.root, treePos, renderTree.height);
  1447.                     */
  1448.                     view.move(10 * view.getSize().x / 500, 0);
  1449.                 }
  1450.                 if (event.key.code == sf::Keyboard::BackSpace) {
  1451.                     if (selected == 1) {
  1452.                         if (addText.size() > 0) {
  1453.                             addText.pop_back();
  1454.                             UpdateText(addDisplayText, addText);
  1455.                         }
  1456.                     }
  1457.                     if (selected == 2) {
  1458.                         if (delText.size() > 0) {
  1459.                             delText.pop_back();
  1460.                             UpdateText(delDisplayText, delText);
  1461.                         }
  1462.                     }
  1463.                     if (selected == 3) {
  1464.                         if (addNtext.size() > 0) {
  1465.                             addNtext.pop_back();
  1466.                             UpdateText(addNDisplayText, addNtext);
  1467.                         }
  1468.                     }
  1469.                 }
  1470.             }
  1471.             if (event.type == sf::Event::TextEntered) {
  1472.                 if (selected == 1) {
  1473.                     if (addText.size() == 0) {
  1474.                         if (event.text.unicode == '-') {
  1475.                             minus1 = true;
  1476.                             addText += event.text.unicode;
  1477.                         }
  1478.                         else {
  1479.                             minus1 = false;
  1480.                         }
  1481.                     }
  1482.                     if (event.text.unicode >= '0' && event.text.unicode <= '9' &&
  1483.                         (addText.size() < 9 || addText.size() < 10 && minus1)) {
  1484.                         addText += event.text.unicode;
  1485.                     }
  1486.                     UpdateText(addDisplayText, addText);
  1487.                 }
  1488.                 if (selected == 2) {
  1489.                     if (event.text.unicode == '-') {
  1490.                         minus2 = true;
  1491.                         delText += event.text.unicode;
  1492.                     }
  1493.                     else {
  1494.                         minus2 = false;
  1495.                     }
  1496.                     if (event.text.unicode >= '0' && event.text.unicode <= '9' &&
  1497.                         (delText.size() < 9 || delText.size() < 10 && minus2)) {
  1498.                         delText += event.text.unicode;
  1499.                     }
  1500.                     UpdateText(delDisplayText, delText);
  1501.                 }
  1502.                 if (selected == 3) {
  1503.                     if (event.text.unicode >= '0' && event.text.unicode <= '9' &&
  1504.                         (addNtext.size() < 9)) {
  1505.                         addNtext += event.text.unicode;
  1506.                     }
  1507.                     UpdateText(addNDisplayText, addNtext);
  1508.                 }
  1509.             }
  1510.             if (event.type == sf::Event::MouseButtonPressed) {
  1511.                 if (addNodeButton.getGlobalBounds().contains(event.mouseButton.x,
  1512.                     event.mouseButton.y)) {
  1513.                     if (selected == 3) {
  1514.                         int n = Convetr(addNtext);
  1515.                         addNtext.clear();
  1516.                         UpdateText(addNDisplayText, addNtext);
  1517.                         for (int i = 0; i < n; ++i) {
  1518.                             int ans = std::rand() % 1000000000;
  1519.                             avl.insert(ans, avl.root);
  1520.                             redBlack.insert(ans);
  1521.                             treap.insert(ans);
  1522.                             splay.insert(ans);
  1523.                         }
  1524.                     }
  1525.                     else if (selected == 1) {
  1526.                         int ans = Convetr(addText);
  1527.                         addText.clear();
  1528.                         UpdateText(addDisplayText, addText);
  1529.                         avl.insert(ans, avl.root);
  1530.                         redBlack.insert(ans);
  1531.                         treap.insert(ans);
  1532.                         splay.insert(ans);
  1533.                     }
  1534.                     if (treeType == 0) {
  1535.                         renderTree.create(avl.root);
  1536.                     }
  1537.                     if (treeType == 1) {
  1538.                         renderTree.create(redBlack.root);
  1539.                     }
  1540.                     if (treeType == 2) {
  1541.                         renderTree.create(treap.root, true);
  1542.                     }
  1543.                     if (treeType == 3) {
  1544.                         renderTree.create(splay.root);
  1545.                     }
  1546.                     if (renderTree.root != nullptr) {
  1547.                         view.setCenter(renderTree.root->col * 200, 400);
  1548.                     }
  1549.                 }
  1550.                 if (removeNodeButton.getGlobalBounds().contains(event.mouseButton.x,
  1551.                     event.mouseButton.y)) {
  1552.                     int ans = Convetr(delText);
  1553.                     delText.clear();
  1554.                     UpdateText(delDisplayText, delText);
  1555.                     avl.remove(ans, avl.root);
  1556.                     redBlack.erase(ans);
  1557.                     treap.remove(ans);
  1558.                     splay.remove(ans);
  1559.                     if (treeType == 0) {
  1560.                         renderTree.create(avl.root);
  1561.                     }
  1562.                     if (treeType == 1) {
  1563.                         renderTree.create(redBlack.root);
  1564.                     }
  1565.                     if (treeType == 2) {
  1566.                         renderTree.create(treap.root, true);
  1567.                     }
  1568.                     if (treeType == 3) {
  1569.                         renderTree.create(splay.root);
  1570.                     }
  1571.                 }
  1572.                 if (addNodeBox.getGlobalBounds().contains(event.mouseButton.x,
  1573.                     event.mouseButton.y)) {
  1574.                     selected = 1;
  1575.                     addNodeBox.setOutlineColor(reactColor);
  1576.                     removeNodeBox.setOutlineColor(elementColor);
  1577.                     addNBox.setOutlineColor(elementColor);
  1578.                 }
  1579.                 else if (removeNodeBox.getGlobalBounds().contains(event.mouseButton.x,
  1580.                     event.mouseButton.y)) {
  1581.                     selected = 2;
  1582.                     removeNodeBox.setOutlineColor(reactColor);
  1583.                     addNodeBox.setOutlineColor(elementColor);
  1584.                     addNBox.setOutlineColor(elementColor);
  1585.                 }
  1586.                 else if (addNBox.getGlobalBounds().contains(event.mouseButton.x,
  1587.                     event.mouseButton.y)) {
  1588.                     selected = 3;
  1589.                     addNBox.setOutlineColor(reactColor);
  1590.                     addNodeBox.setOutlineColor(elementColor);
  1591.                     removeNodeBox.setOutlineColor(elementColor);
  1592.                 }
  1593.                 else {
  1594.                     selected = 0;
  1595.                     removeNodeBox.setOutlineColor(elementColor);
  1596.                     addNodeBox.setOutlineColor(elementColor);
  1597.                     addNBox.setOutlineColor(elementColor);
  1598.                 }
  1599.                
  1600.                 if (treetype1.getGlobalBounds().contains(event.mouseButton.x,
  1601.                     event.mouseButton.y)) {
  1602.                     treeType = 0;
  1603.                     treetype1.setOutlineColor(reactColor);
  1604.                     treetype2.setOutlineColor(elementColor);
  1605.                     treetype3.setOutlineColor(elementColor);
  1606.                     treetype4.setOutlineColor(elementColor);
  1607.                     renderTree.create(avl.root);
  1608.                     if (renderTree.root != nullptr) {
  1609.                         view.setCenter(renderTree.root->col * 200, 400);
  1610.                     }
  1611.                 }
  1612.                 if (treetype2.getGlobalBounds().contains(event.mouseButton.x,
  1613.                     event.mouseButton.y)) {
  1614.                     treeType = 1;
  1615.                     treetype2.setOutlineColor(reactColor);
  1616.                     treetype1.setOutlineColor(elementColor);
  1617.                     treetype3.setOutlineColor(elementColor);
  1618.                     treetype4.setOutlineColor(elementColor);
  1619.                     renderTree.create(redBlack.root);
  1620.                     if (renderTree.root != nullptr) {
  1621.                         view.setCenter(renderTree.root->col * 200, 400);
  1622.                     }
  1623.                 }
  1624.                 if (treetype3.getGlobalBounds().contains(event.mouseButton.x,
  1625.                     event.mouseButton.y)) {
  1626.                     treeType = 2;
  1627.                     treetype3.setOutlineColor(reactColor);
  1628.                     treetype2.setOutlineColor(elementColor);
  1629.                     treetype1.setOutlineColor(elementColor);
  1630.                     treetype4.setOutlineColor(elementColor);
  1631.                     renderTree.create(treap.root, true);
  1632.                     if (renderTree.root != nullptr) {
  1633.                         view.setCenter(renderTree.root->col * 200, 400);
  1634.                     }
  1635.                 }
  1636.                 if (treetype4.getGlobalBounds().contains(event.mouseButton.x,
  1637.                     event.mouseButton.y)) {
  1638.                     treeType = 3;
  1639.                     treetype4.setOutlineColor(reactColor);
  1640.                     treetype2.setOutlineColor(elementColor);
  1641.                     treetype3.setOutlineColor(elementColor);
  1642.                     treetype1.setOutlineColor(elementColor);
  1643.                     renderTree.create(splay.root);
  1644.                     if (renderTree.root != nullptr) {
  1645.                         view.setCenter(renderTree.root->col * 200, 400);
  1646.                     }
  1647.                 }
  1648.                 sf::Vector2i pixelPos = sf::Mouse::getPosition(window);
  1649.                 sf::Vector2f worldPos = window.mapPixelToCoords(pixelPos, view);
  1650.                 RenderNode* mbNode = MousePressed(worldPos.x, worldPos.y, renderTree.root);
  1651.                 if (mbNode != nullptr) {
  1652.                     int ans = mbNode->key;
  1653.                     avl.remove(ans, avl.root);
  1654.                     redBlack.erase(ans);
  1655.                     treap.remove(ans);
  1656.                     splay.remove(ans);
  1657.                     if (treeType == 0) {
  1658.                         renderTree.create(avl.root);
  1659.                     }
  1660.                     if (treeType == 1) {
  1661.                         renderTree.create(redBlack.root);
  1662.                     }
  1663.                     if (treeType == 2) {
  1664.                         renderTree.create(treap.root, true);
  1665.                     }
  1666.                     if (treeType == 3) {
  1667.                         renderTree.create(splay.root);
  1668.                     }
  1669.                 }
  1670.                 else {
  1671.  
  1672.                 }
  1673.             }
  1674.         }
  1675.  
  1676.         window.clear(backgroundColor);
  1677.  
  1678.         window.setView(view);
  1679.  
  1680.         renderTree.draw(window);
  1681.  
  1682.         window.setView(window.getDefaultView());
  1683.  
  1684.         window.draw(addNodeBox);
  1685.         window.draw(addNBox);
  1686.         window.draw(removeNodeButton);
  1687.         window.draw(addNodeButton);
  1688.         window.draw(removeNodeBox);
  1689.  
  1690.         window.draw(treetype1);
  1691.         window.draw(treetype2);
  1692.         window.draw(treetype3);
  1693.         window.draw(treetype4);
  1694.  
  1695.         window.draw(addDisplayText);
  1696.         window.draw(addNDisplayText);
  1697.         window.draw(addButtonText);
  1698.         window.draw(delButtonText);
  1699.         window.draw(delDisplayText);
  1700.  
  1701.         window.draw(treetext1);
  1702.         window.draw(treetext3);
  1703.         window.draw(treetext4);
  1704.         window.draw(treetext2);
  1705.  
  1706.  
  1707.  
  1708.         window.display();
  1709.     }
  1710. }
  1711.  
  1712. /*
  1713. Avl avl;
  1714.     while (true) {
  1715.         int a;
  1716.         std::cin >> a;
  1717.         if (a == 0) {
  1718.             InOrder(avl.root);
  1719.             std::cout << "\n";
  1720.             TreeOrder(avl.root);
  1721.         }
  1722.         if (a == 1) {
  1723.             int key;
  1724.             std::cin >> key;
  1725.             std::cout << avl.insert(key, avl.root) << "\n";
  1726.         }
  1727.         if (a == 2) {
  1728.             int key;
  1729.             std::cin >> key;
  1730.             std::cout << avl.remove(key, avl.root) << "\n";
  1731.         }
  1732.         if (a >= 3) {
  1733.             for (int i = 0; i < a; ++i) {
  1734.                 int k;
  1735.                 int key;
  1736.                 std::cin >> key;
  1737.                 std::cout << avl.insert(key, avl.root) << "\n";
  1738.             }
  1739.         }
  1740.     }
  1741. */
  1742.  
  1743. /*
  1744. 5
  1745. 3 10 15 30 29
  1746.  
  1747.  
  1748. 437
  1749. 3485
  1750. 238
  1751. 483
  1752. 285
  1753. 22
  1754. 355
  1755. 348
  1756. 345
  1757. 23
  1758. 25699
  1759. 8346867
  1760. 934988
  1761. 483276
  1762. 2931
  1763. 59328528
  1764. 283582385
  1765. 38723
  1766. 237582358
  1767. 2
  1768. 32735285
  1769. 69
  1770. 1585
  1771. 3382
  1772. 384
  1773. 23415
  1774. 2643
  1775. 523
  1776. 247724
  1777. 999999999
  1778. 556
  1779. */
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!