API tools faq
paste
Advertisement
LegoSosiska

Untitled

LegoSosiska
Apr 20th, 2022
947
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 50.10 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.         if (search == nullptr) {
  523.             return nullptr;
  524.         }
  525.         if (search->key == key) {
  526.             return search;
  527.         }
  528.         if (key > search->key) {
  529.             return find(key, search->right);
  530.         }
  531.         if (key < search->key) {
  532.             return find(key, search->left);
  533.         }
  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) return;
  558.             if (p->prev->color == 0) return;
  559.             Node* par = p->prev, * gpa = p->prev->prev;
  560.             Node* bro = (par == gpa->left ? gpa->right : gpa->left);
  561.             if (bro != nullptr && bro->color == 1) {
  562.                 par->color = 0;
  563.                 bro->color = 0;
  564.                 gpa->color = 1;
  565.                 p = gpa;
  566.                 continue;
  567.             }
  568.             if (CheckColor(bro)) {
  569.                 if (p == par->right && par == gpa->left) {
  570.                     p->prev = gpa;
  571.                     par->prev = p;
  572.                     par->right = p->left;
  573.                     p->left = par;
  574.                     gpa->left = p;
  575.                     std::swap(par, p);
  576.                 }
  577.                 else if (p == par->left && par == gpa->right) {
  578.                     p->prev = gpa;
  579.                     par->prev = p;
  580.                     par->left = p->right;
  581.                     p->right = par;
  582.                     gpa->right = p;
  583.                     std::swap(par, p);
  584.                 }
  585.                 if (gpa->left == par) {
  586.                     if (gpa->prev == nullptr) {
  587.                         root = par;
  588.                     }
  589.                     else {
  590.                         if (gpa->prev->left == gpa) {
  591.                             gpa->prev->left = par;
  592.                         }
  593.                         else {
  594.                             gpa->prev->right = par;
  595.                         }
  596.                     }
  597.                     par->prev = gpa->prev;
  598.                     gpa->prev = par;
  599.                     gpa->left = par->right;
  600.                     if (par->right != nullptr) {
  601.                         par->right->prev = gpa;
  602.                     }
  603.                     par->right = gpa;
  604.                 }
  605.                 else {
  606.                     if (gpa->prev == nullptr) {
  607.                         root = par;
  608.                     }
  609.                     else {
  610.                         if (gpa->prev->left == gpa) {
  611.                             gpa->prev->left = par;
  612.                         }
  613.                         else {
  614.                             gpa->prev->right = par;
  615.                         }
  616.                     }
  617.                     par->prev = gpa->prev;
  618.                     gpa->prev = par;
  619.                     gpa->right = par->left;
  620.                     if (par->left != nullptr) {
  621.                         par->left->prev = gpa;
  622.                     }
  623.                     par->left = gpa;
  624.                 }
  625.                 par->color = 0;
  626.                 gpa->color = 1;
  627.                 return;
  628.             }
  629.         }
  630.         if (p == root) {
  631.             p->color = 0;
  632.         }
  633.     }
  634.  
  635.     bool erase(int key) {
  636.         Node* q = find(key, root);
  637.         if (q == nullptr) {
  638.             return false;
  639.         }
  640.         Node* min = findMin(q->right);
  641.         if (min == nullptr) {
  642.             min = findMax(q->left);
  643.             if (min == nullptr) {
  644.                 min = q;
  645.             }
  646.         }
  647.         if (!CheckColor(min)) {
  648.             q->key = min->key;
  649.             if (min->prev->left == min) {
  650.                 min->prev->left = nullptr;
  651.             }
  652.             else {
  653.                 min->prev->right = nullptr;
  654.             }
  655.             delete min;
  656.             return true;
  657.         }
  658.         else {
  659.             q->key = min->key;
  660.             if (min->right != nullptr) {
  661.                 min->key = min->right->key;
  662.                 delete min->right;
  663.                 min->right = nullptr;
  664.                 return true;
  665.             }
  666.             else if (min->left != nullptr) {
  667.                 min->key = min->left->key;
  668.                 delete min->left;
  669.                 min->left = nullptr;
  670.                 return true;
  671.             }
  672.             if (min->prev == nullptr) {
  673.                 delete min;
  674.                 root = nullptr;
  675.                 return true;
  676.             }
  677.             rbalance(min, min->prev,
  678.                 (min == min->prev->left ? min->prev->right : min->prev->left));
  679.             if (min->prev->left == min) {
  680.                 min->prev->left = nullptr;
  681.             }
  682.             else {
  683.                 min->prev->right = nullptr;
  684.             }
  685.             delete min;
  686.         }
  687.         // if (min == nullptr) min = q;
  688.         /*
  689.         q->key = min->key;
  690.         if (!CheckColor(min)) {
  691.           if (min->prev->left == min) {
  692.             min->prev->left = nullptr;
  693.           } else {
  694.             min->prev->right = nullptr;
  695.           }
  696.           delete min;
  697.           return true;
  698.         }
  699.         if (!CheckColor(min->right)) {
  700.           if (min->right != nullptr) {
  701.             min->right->prev = q->prev;
  702.             if (min->prev->left == min) {
  703.               min->prev->left = min->right;
  704.             } else {
  705.               min->prev->right = min->right;
  706.             }
  707.             min->left->color = 0;
  708.             delete min;
  709.             return true;
  710.           }
  711.         }
  712.  
  713.         Node* toDelete = min;
  714.         if (min->prev == nullptr) {
  715.           root = nullptr;
  716.           delete min;
  717.           return true;
  718.         }
  719.         if (min->prev->left == min) {
  720.           min->prev->left = min->right;
  721.         } else {
  722.           min->prev->right = min->right;
  723.         }
  724.         min = min->right;
  725.         delete toDelete;
  726.         rbalance(min);
  727.         return true;
  728.         */
  729.     }
  730.  
  731.     void rbalance(Node* p, Node* par, Node* bro) {
  732.        
  733.         while (p != root) {
  734.             Node* d1, * d2;
  735.             if (p == par->left) {
  736.                 d1 = bro->left;
  737.                 d2 = bro->right;
  738.             }
  739.             else {
  740.                 d1 = bro->right;
  741.                 d2 = bro->left;
  742.             }
  743.             if (CheckColor(par) && CheckColor(bro) && CheckColor(d1) &&
  744.                 CheckColor(d2)) {
  745.                 bro->color = 1;
  746.                 if (par->prev == nullptr) {
  747.                     return;
  748.                 }
  749.                 p = par;
  750.                 par = par->prev;
  751.                 bro = (p == par->right ? par->left : par->right);
  752.                 continue;
  753.             }
  754.             if (!CheckColor(par) && CheckColor(bro) && CheckColor(d1) &&
  755.                 CheckColor(d2)) {
  756.                 par->color = 0;
  757.                 bro->color = 1;
  758.                 return;
  759.             }
  760.             if (CheckColor(bro) && !CheckColor(d2)) {
  761.                 bro->prev = par->prev;
  762.                 if (par->prev != nullptr) {
  763.                     if (par->prev->right == par) {
  764.                         par->prev->right = bro;
  765.                     }
  766.                     else {
  767.                         par->prev->left = bro;
  768.                     }
  769.                 }
  770.                 else {
  771.                     root = bro;
  772.                 }
  773.                 d2->color = 0;
  774.                 if (p == par->left) {
  775.                     par->right = d1;
  776.                     bro->left = par;
  777.                 }
  778.                 else {
  779.                     par->left = d1;
  780.                     bro->right = par;
  781.                 }
  782.                 par->prev = bro;
  783.                 int color = par->color;
  784.                 par->color = bro->color;
  785.                 bro->color = par->color;
  786.                 return;
  787.             }
  788.             if (CheckColor(bro) && !CheckColor(d1) && CheckColor(d2)) {
  789.                 if (p == par->left) {
  790.                     par->right = d1;
  791.                     bro->left = d1->right;
  792.                     d1->right = bro;
  793.                     par->right = d1;
  794.                 }
  795.                 else {
  796.                     par->left = d1;
  797.                     bro->right = d1->left;
  798.                     d1->left = bro;
  799.                     par->left = d1;
  800.                 }
  801.                 d1->prev = par;
  802.                 bro->prev = d1;
  803.                 d1->color = 0;
  804.                 bro->color = 1;
  805.                 bro = d1;
  806.                 continue;
  807.             }
  808.             if (!CheckColor(bro)) {
  809.                 if (par->prev != nullptr) {
  810.                     if (par->prev->right == par) {
  811.                         par->prev->right = bro;
  812.                     }
  813.                     else {
  814.                         par->prev->left = bro;
  815.                     }
  816.                 }
  817.                 else {
  818.                     root = bro;
  819.                 }
  820.                 bro->prev = par->prev;
  821.                 par->prev = bro;
  822.                 if (p == par->left) {
  823.                     par->right = d1;
  824.                     bro->left = par;
  825.                 }
  826.                 else {
  827.                     par->left = d1;
  828.                     bro->right = par;
  829.                 }
  830.                 par->color = 1;
  831.                 bro->color = 0;
  832.                 if (d2 != nullptr) {
  833.                     d2->color = 1;
  834.                 }
  835.                 bro = d1;
  836.                 continue;
  837.             }
  838.             return;
  839.         }
  840.     }
  841.  
  842.     Node* findMin(Node* p) {
  843.         if (p == nullptr) {
  844.             return nullptr;
  845.         }
  846.         if (p->left == nullptr) {
  847.             return p;
  848.         }
  849.         return findMin(p->left);
  850.     }
  851.  
  852.     Node* findMax(Node* p) {
  853.         if (p == nullptr) {
  854.             return nullptr;
  855.         }
  856.         if (p->right == nullptr) {
  857.             return p;
  858.         }
  859.         return findMin(p->right);
  860.     }
  861. };
  862.  
  863. void InOrder(Node* p, int layer = 0) {
  864.   if (p == nullptr) return;
  865.   InOrder(p->left, layer + 1);
  866.   std::cout << p->key << " ";
  867.   InOrder(p->right, layer + 1);
  868. }
  869.  
  870. void TreeOrder(Node* p) {
  871.   int layer = 0;
  872.   std::queue<std::pair<Node*, int>> queue;
  873.   std::pair<Node*, int> blank;
  874.   if (p != nullptr) {
  875.     blank = {p, layer};
  876.     queue.push(blank);
  877.   }
  878.   while (!queue.empty()) {
  879.     if (queue.front().second > layer) {
  880.       std::cout << "\n";
  881.       ++layer;
  882.     }
  883.     Node* q = queue.front().first;
  884.     std::cout << q->key << " ";
  885.     queue.pop();
  886.     if (q->left != nullptr) {
  887.       blank.second = layer + 1;
  888.       blank.first = q->left;
  889.       queue.push(blank);
  890.     }
  891.     if (q->right != nullptr) {
  892.       blank.second = layer + 1;
  893.       blank.first = q->right;
  894.       queue.push(blank);
  895.     }
  896.   }
  897. }
  898.  
  899. sf::Font* font;
  900.  
  901. sf::Color textColor = sf::Color(232, 197, 71),
  902.           backgroundColor = sf::Color(34, 40, 49),
  903.           elementColor = sf::Color(254, 233, 225),
  904.           fillColor = sf::Color(57, 62, 70),
  905.           reactColor = sf::Color(217, 3, 104),
  906.           redFillColor = sf::Color(157, 62, 70);
  907.  
  908. struct RenderNode {
  909.     sf::RectangleShape rect;
  910.     sf::Text text;
  911.     int height = 0;
  912.     Node* node = nullptr;
  913.     int key = 0;
  914.     sf::Vector2f scale;
  915.     RenderNode* left = nullptr, * right = nullptr;
  916.  
  917.     void create(Node* node, int key, int height, float scale) {
  918.         this->node = node;
  919.         this->key = key;
  920.         this->text.setString(std::to_string(key));
  921.         this->height = height;
  922.  
  923.         sf::Vector2f sc = { scale, scale };
  924.         this->scale = sc;
  925.  
  926.         rect.setSize(sf::Vector2f(150, 60));
  927.  
  928.         // text.setOrigin(text.getGlobalBounds().width / 2,
  929.         // text.getGlobalBounds().height / 2);
  930.         rect.setOrigin(75, 30);
  931.         text.setOrigin(75, 20);
  932.  
  933.         text.setFont(*font);
  934.         rect.setOutlineThickness(1);
  935.  
  936.         if (node->color) {
  937.             rect.setFillColor(redFillColor);
  938.         }
  939.         else {
  940.             rect.setFillColor(fillColor);
  941.         }
  942.         text.setFillColor(textColor);
  943.         rect.setOutlineColor(elementColor);
  944.  
  945.         text.setScale(this->scale);
  946.         rect.setScale(this->scale);
  947.     }
  948.  
  949.     void grow(sf::Vector2f scale) {
  950.         this->scale = scale;
  951.         text.setScale(scale);
  952.         rect.setScale(scale);
  953.     }
  954.  
  955.     void setPos(sf::Vector2f pos) {
  956.         rect.setPosition(pos);
  957.         text.setPosition(pos);
  958.     }
  959.  
  960.     void draw(sf::RenderWindow& window) {
  961.         window.draw(rect);
  962.         window.draw(text);
  963.     }
  964.  
  965.     bool contains(float x, float y) {
  966.         return rect.getGlobalBounds().contains(x, y);
  967.     }
  968. };
  969.  
  970. struct RenderTree {
  971.   std::vector<sf::Vertex> connections;
  972.   RenderNode* root = nullptr;
  973.   int height;
  974.  
  975.   void create(Node* tree, sf::Vector2f pos, float scale) {
  976.     int height = 0;
  977.     RenderNode* rend = createNodes(tree, height, scale);
  978.     root = rend;
  979.     positionNodes(rend, pos, height);
  980.     this->height = height;
  981.   }
  982.  
  983.   void positionNodes(RenderNode* rend, sf::Vector2f pos, int height) {
  984.     if (rend == nullptr) return;
  985.     rend->setPos(pos);
  986.     positionNodes(rend->left,
  987.                   {pos.x - 80 * (int)pow(2, height - 2) * rend->scale.x,
  988.                    pos.y + 200 * rend->scale.x},
  989.                   height - 1);
  990.     positionNodes(rend->right,
  991.                   {pos.x + 80 * (int)pow(2, height - 2) * rend->scale.x,
  992.                    pos.y + 200 * rend->scale.x},
  993.                   height - 1);
  994.     return;
  995.   }
  996.  
  997.   RenderNode* createNodes(Node* tree, int& height, float scale) {
  998.     if (tree == nullptr) {
  999.       return nullptr;
  1000.     }
  1001.  
  1002.     int h1 = height, h2 = height;
  1003.     RenderNode* rend = new RenderNode;
  1004.     rend->left = createNodes(tree->left, h1, scale);
  1005.     rend->right = createNodes(tree->right, h2, scale);
  1006.     height = std::max(h1, h2) + 1;
  1007.     rend->create(tree, tree->key, height, scale);
  1008.     return rend;
  1009.   }
  1010.  
  1011.   void scale(RenderNode* rend, float scaleNum) {
  1012.     if (rend == nullptr) return;
  1013.     sf::Vector2f s = {scaleNum, scaleNum};
  1014.     rend->grow(s);
  1015.     scale(rend->left, scaleNum);
  1016.     scale(rend->right, scaleNum);
  1017.   }
  1018.  
  1019.   void draw(sf::RenderWindow& window) { drawNodes(window, root); }
  1020.  
  1021.   void drawNodes(sf::RenderWindow& window, RenderNode* rend) {
  1022.     if (rend == nullptr) return;
  1023.     if (rend->left != nullptr) {
  1024.       sf::Vector2f pos1, pos2;
  1025.       pos1 = {rend->rect.getPosition().x, rend->rect.getPosition().y};
  1026.       pos2 = {rend->left->rect.getPosition().x,
  1027.               rend->left->rect.getPosition().y};
  1028.       sf::Vertex line[] = {sf::Vertex(pos1), sf::Vertex(pos2)};
  1029.       window.draw(line, 2, sf::Lines);
  1030.     }
  1031.     if (rend->right != nullptr) {
  1032.       sf::Vector2f pos1, pos2;
  1033.       pos1 = {rend->rect.getPosition().x, rend->rect.getPosition().y};
  1034.       pos2 = {rend->right->rect.getPosition().x,
  1035.               rend->right->rect.getPosition().y};
  1036.       sf::Vertex line[] = {sf::Vertex(pos1), sf::Vertex(pos2)};
  1037.       window.draw(line, 2, sf::Lines);
  1038.     }
  1039.     rend->draw(window);
  1040.     drawNodes(window, rend->left);
  1041.     drawNodes(window, rend->right);
  1042.   }
  1043.  
  1044.   void clear() {
  1045.     connections.clear();
  1046.     clearNodes(root);
  1047.     root = nullptr;
  1048.   }
  1049.  
  1050.   void clearNodes(RenderNode* rend) {
  1051.     if (rend == nullptr) {
  1052.       return;
  1053.     }
  1054.     clearNodes(rend->left);
  1055.     clearNodes(rend->right);
  1056.     delete rend;
  1057.   }
  1058.  
  1059.   /* bool contains(float x, float y, int type, RenderNode* node = nullptr, bool
  1060.    first = false) { if (node == nullptr && !first) { node = root; first = true;
  1061.        }
  1062.        if (node == nullptr) return;
  1063.        if (node->rect.getGlobalBounds().contains(x, y)) {
  1064.            erase()
  1065.        }
  1066.    }*/
  1067. };
  1068.  
  1069. void InOrder2(RenderNode* p, int layer = 0) {
  1070.   if (p == nullptr) return;
  1071.   InOrder2(p->left, layer + 1);
  1072.   std::cout << p->key << " ";
  1073.   InOrder2(p->right, layer + 1);
  1074. }
  1075.  
  1076. void UpdateText(sf::Text& text, std::string s) { text.setString(s); }
  1077.  
  1078. RenderNode* MousePressed(float x, float y, RenderNode* node) {
  1079.     if (node == nullptr) return nullptr;
  1080.     if (node->contains(x, y)) {
  1081.         return node;
  1082.     }
  1083.     RenderNode* left = MousePressed(x, y, node->left);
  1084.     RenderNode* right = MousePressed(x, y, node->right);
  1085.     if (left != nullptr) return left;
  1086.     return right;
  1087. }
  1088.  
  1089. int Convetr(std::string s) {
  1090.   bool minus = false;
  1091.   int i = 0, ans = 0;
  1092.   if (s[i] == '-') {
  1093.     minus = true;
  1094.     ++i;
  1095.   }
  1096.   while (i < s.size()) {
  1097.     ans *= 10;
  1098.     ans += s[i] - '0';
  1099.     ++i;
  1100.   }
  1101.   if (minus) {
  1102.     ans = ans * -1;
  1103.   }
  1104.   return ans;
  1105. }
  1106.  
  1107. int main() {
  1108.     sf::RenderWindow window(sf::VideoMode(1000, 1000), "FUNKY GROOVY");
  1109.  
  1110.     // RedBlack splay;
  1111.     RenderTree renderTree;
  1112.     sf::Vertex line[] = { sf::Vertex(sf::Vector2f(10.f, 10.f)),
  1113.                          sf::Vertex(sf::Vector2f(150.f, 150.f)) };
  1114.  
  1115.     std::string addText, delText, addNtext;
  1116.     sf::RectangleShape addNodeBox, removeNodeBox, addNBox, addNodeButton, removeNodeButton, treetype1, treetype2, treetype3,
  1117.         treetype4;
  1118.     sf::Text addDisplayText, delDisplayText, addNDisplayText, addButtonText, delButtonText, treetext1, treetext2, treetext3, treetext4;
  1119.  
  1120.     addDisplayText.setPosition(402, 944);
  1121.     delDisplayText.setPosition(702, 944);
  1122.     addNDisplayText.setPosition(402, 892);
  1123.     addButtonText.setPosition(562, 944);
  1124.     delButtonText.setPosition(862, 944);
  1125.  
  1126.     treetext1.setPosition(52, 944);
  1127.     treetext2.setPosition(132, 944);
  1128.     treetext3.setPosition(212, 944);
  1129.     treetext4.setPosition(292, 944);
  1130.  
  1131.     addNDisplayText.setOutlineThickness(2);
  1132.     addDisplayText.setOutlineThickness(2);
  1133.     addButtonText.setFillColor(textColor);
  1134.     delButtonText.setFillColor(textColor);
  1135.     addDisplayText.setFillColor(textColor);
  1136.     addNDisplayText.setFillColor(textColor);
  1137.     delDisplayText.setOutlineThickness(2);
  1138.     addButtonText.setOutlineThickness(2);
  1139.     delButtonText.setOutlineThickness(2);
  1140.     delDisplayText.setFillColor(textColor);
  1141.  
  1142.     treetext1.setOutlineThickness(2);
  1143.     treetext3.setFillColor(textColor);
  1144.     treetext4.setFillColor(textColor);
  1145.     treetext1.setFillColor(textColor);
  1146.     treetext2.setOutlineThickness(2);
  1147.     treetext3.setOutlineThickness(2);
  1148.     treetext4.setOutlineThickness(2);
  1149.     treetext2.setFillColor(textColor);
  1150.  
  1151.     addNodeBox.setSize(sf::Vector2f(150, 30));
  1152.     removeNodeBox.setSize(sf::Vector2f(150, 30));
  1153.     addNBox.setSize(sf::Vector2f(150, 30));
  1154.  
  1155.     addNodeBox.setPosition(400, 950);
  1156.     removeNodeBox.setPosition(700, 950);
  1157.     addNBox.setPosition(400, 898);
  1158.  
  1159.     addNodeBox.setOutlineThickness(2);
  1160.     addNodeBox.setOutlineColor(elementColor);
  1161.     addNodeBox.setFillColor(fillColor);
  1162.     removeNodeBox.setOutlineThickness(2);
  1163.     removeNodeBox.setOutlineColor(elementColor);
  1164.     removeNodeBox.setFillColor(fillColor);
  1165.     addNBox.setOutlineThickness(2);
  1166.     addNBox.setOutlineColor(elementColor);
  1167.     addNBox.setFillColor(fillColor);
  1168.  
  1169.     addNodeButton.setSize(sf::Vector2f(50, 30));
  1170.     removeNodeButton.setSize(sf::Vector2f(50, 30));
  1171.  
  1172.     addNodeButton.setPosition(560, 950);
  1173.     removeNodeButton.setPosition(860, 950);
  1174.  
  1175.     addNodeButton.setOutlineThickness(2);
  1176.     addNodeButton.setOutlineColor(elementColor);
  1177.     addNodeButton.setFillColor(fillColor);
  1178.     removeNodeButton.setOutlineThickness(2);
  1179.     removeNodeButton.setOutlineColor(elementColor);
  1180.     removeNodeButton.setFillColor(fillColor);
  1181.  
  1182.     treetype1.setSize(sf::Vector2f(50, 30));
  1183.     treetype2.setSize(sf::Vector2f(50, 30));
  1184.     treetype3.setSize(sf::Vector2f(50, 30));
  1185.     treetype4.setSize(sf::Vector2f(50, 30));
  1186.  
  1187.     treetype1.setPosition(50, 950);
  1188.     treetype2.setPosition(130, 950);
  1189.     treetype3.setPosition(210, 950);
  1190.     treetype4.setPosition(290, 950);
  1191.  
  1192.     treetype1.setOutlineThickness(2);
  1193.     treetype1.setOutlineColor(elementColor);
  1194.     treetype1.setFillColor(fillColor);
  1195.     treetype2.setOutlineThickness(2);
  1196.     treetype2.setOutlineColor(elementColor);
  1197.     treetype2.setFillColor(fillColor);
  1198.     treetype3.setOutlineThickness(2);
  1199.     treetype3.setOutlineColor(elementColor);
  1200.     treetype3.setFillColor(fillColor);
  1201.     treetype4.setOutlineThickness(2);
  1202.     treetype4.setOutlineColor(elementColor);
  1203.     treetype4.setFillColor(fillColor);
  1204.  
  1205.     font = new sf::Font;
  1206.     if (!font->loadFromFile("UbuntuMono-Regular.ttf")) {
  1207.         std::cout << "err\n";
  1208.     }
  1209.  
  1210.     addNDisplayText.setFont(*font);
  1211.     addDisplayText.setFont(*font);
  1212.     delDisplayText.setFont(*font);
  1213.     addButtonText.setFont(*font);
  1214.     delButtonText.setFont(*font);
  1215.  
  1216.     treetext1.setFont(*font);
  1217.     treetext2.setFont(*font);
  1218.     treetext3.setFont(*font);
  1219.     treetext4.setFont(*font);
  1220.  
  1221.     addButtonText.setString("ADD");
  1222.     delButtonText.setString("DEL");
  1223.  
  1224.     treetext1.setString("AVL");
  1225.     treetext2.setString("R/B");
  1226.     treetext3.setString("TRP");
  1227.     treetext4.setString("SPL");
  1228.  
  1229.     sf::Vector2f treePos = { 500, 50 };
  1230.     float scale = 1;
  1231.     int selected = 0;
  1232.     bool minus1 = false, minus2 = false;
  1233.  
  1234.     int treeType = 0;
  1235.     Avl avl;
  1236.     RedBlack redBlack;
  1237.     Treap treap;
  1238.     Splay splay;
  1239.  
  1240.     while (window.isOpen()) {
  1241.         sf::Event event;
  1242.         while (window.pollEvent(event)) {
  1243.             if (event.type == sf::Event::Closed) {
  1244.                 window.close();
  1245.             }
  1246.             if (event.type == sf::Event::KeyPressed) {
  1247.                 if (event.key.code == sf::Keyboard::Enter) {
  1248.                     if (selected == 1 || selected == 3) {
  1249.                         if (selected == 3) {
  1250.                             int n = Convetr(addNtext);
  1251.                             addNtext.clear();
  1252.                             UpdateText(addNDisplayText, addNtext);
  1253.                             for (int i = 0; i < n; ++i) {
  1254.                                 int ans = std::rand() % 1000000000;
  1255.                                 avl.insert(ans, avl.root);
  1256.                                 redBlack.insert(ans);
  1257.                                 treap.insert(ans);
  1258.                                 splay.insert(ans);
  1259.                             }
  1260.                         }
  1261.                         else if (selected == 1) {
  1262.                             int ans = Convetr(addText);
  1263.                             addText.clear();
  1264.                             UpdateText(addDisplayText, addText);
  1265.                             avl.insert(ans, avl.root);
  1266.                             redBlack.insert(ans);
  1267.                             treap.insert(ans);
  1268.                             splay.insert(ans);
  1269.                         }
  1270.                         if (treeType == 0) {
  1271.                             renderTree.create(avl.root, treePos, scale);
  1272.                         }
  1273.                         if (treeType == 1) {
  1274.                             renderTree.create(redBlack.root, treePos, scale);
  1275.                         }
  1276.                         if (treeType == 2) {
  1277.                             renderTree.create(treap.root, treePos, scale);
  1278.                         }
  1279.                         if (treeType == 3) {
  1280.                             renderTree.create(splay.root, treePos, scale);
  1281.                         }
  1282.                     }
  1283.                     if (selected == 2) {
  1284.                         int ans = Convetr(delText);
  1285.                         delText.clear();
  1286.                         UpdateText(delDisplayText, delText);
  1287.                         avl.remove(ans, avl.root);
  1288.                         redBlack.erase(ans);
  1289.                         treap.remove(ans);
  1290.                         splay.remove(ans);
  1291.                         if (treeType == 0) {
  1292.                             renderTree.create(avl.root, treePos, scale);
  1293.                         }
  1294.                         if (treeType == 1) {
  1295.                             renderTree.create(redBlack.root, treePos, scale);
  1296.                         }
  1297.                         if (treeType == 2) {
  1298.                             renderTree.create(treap.root, treePos, scale);
  1299.                         }
  1300.                         if (treeType == 3) {
  1301.                             renderTree.create(splay.root, treePos, scale);
  1302.                         }
  1303.                     }
  1304.                 }
  1305.                 if (event.key.code == sf::Keyboard::P) {
  1306.                     if (scale <= 0.2) {
  1307.                         scale += 0.02;
  1308.                     }
  1309.                     else {
  1310.                         scale += 0.1;
  1311.                     }
  1312.  
  1313.                     renderTree.scale(renderTree.root, scale);
  1314.                     renderTree.positionNodes(renderTree.root, treePos, renderTree.height);
  1315.                 }
  1316.                 if (event.key.code == sf::Keyboard::O) {
  1317.                     if (scale <= 0.2 && scale > 0.02) {
  1318.                         scale -= 0.02;
  1319.                         renderTree.scale(renderTree.root, scale);
  1320.                         renderTree.positionNodes(renderTree.root, treePos,
  1321.                             renderTree.height);
  1322.                     }
  1323.                     else if (scale > 0.2) {
  1324.                         scale -= 0.1;
  1325.                         renderTree.scale(renderTree.root, scale);
  1326.                         renderTree.positionNodes(renderTree.root, treePos,
  1327.                             renderTree.height);
  1328.                     }
  1329.                 }
  1330.                 if (event.key.code == sf::Keyboard::Up) {
  1331.                     if (scale <= 0.2) {
  1332.                         treePos.y += 5 * scale * 100;
  1333.                     }
  1334.                     else {
  1335.                         treePos.y += 5 * scale * 10;
  1336.                     }
  1337.                    
  1338.                     renderTree.positionNodes(renderTree.root, treePos, renderTree.height);
  1339.                 }
  1340.                 if (event.key.code == sf::Keyboard::Down) {
  1341.                     if (scale <= 0.2) {
  1342.                         treePos.y -= 5 * scale * 100;
  1343.                     }
  1344.                     else {
  1345.                         treePos.y -= 5 * scale * 10;
  1346.                     }
  1347.                     renderTree.positionNodes(renderTree.root, treePos, renderTree.height);
  1348.                 }
  1349.                 if (event.key.code == sf::Keyboard::Left) {
  1350.                     if (scale <= 0.2) {
  1351.                         treePos.x += 5 * scale * 100;
  1352.                     }
  1353.                     else {
  1354.                         treePos.x += 5 * scale * 10;
  1355.                     }
  1356.                     renderTree.positionNodes(renderTree.root, treePos, renderTree.height);
  1357.                 }
  1358.                 if (event.key.code == sf::Keyboard::Right) {
  1359.                     if (scale <= 0.2) {
  1360.                         treePos.x -= 5 * scale * 100;
  1361.                     }
  1362.                     else {
  1363.                         treePos.x -= 5 * scale * 10;
  1364.                     }
  1365.                     renderTree.positionNodes(renderTree.root, treePos, renderTree.height);
  1366.                 }
  1367.                 if (event.key.code == sf::Keyboard::BackSpace) {
  1368.                     if (selected == 1) {
  1369.                         if (addText.size() > 0) {
  1370.                             addText.pop_back();
  1371.                             UpdateText(addDisplayText, addText);
  1372.                         }
  1373.                     }
  1374.                     if (selected == 2) {
  1375.                         if (delText.size() > 0) {
  1376.                             delText.pop_back();
  1377.                             UpdateText(delDisplayText, delText);
  1378.                         }
  1379.                     }
  1380.                     if (selected == 3) {
  1381.                         if (addNtext.size() > 0) {
  1382.                             addNtext.pop_back();
  1383.                             UpdateText(addNDisplayText, addNtext);
  1384.                         }
  1385.                     }
  1386.                 }
  1387.             }
  1388.             if (event.type == sf::Event::TextEntered) {
  1389.                 if (selected == 1) {
  1390.                     if (addText.size() == 0) {
  1391.                         if (event.text.unicode == '-') {
  1392.                             minus1 = true;
  1393.                             addText += event.text.unicode;
  1394.                         }
  1395.                         else {
  1396.                             minus1 = false;
  1397.                         }
  1398.                     }
  1399.                     if (event.text.unicode >= '0' && event.text.unicode <= '9' &&
  1400.                         (addText.size() < 9 || addText.size() < 10 && minus1)) {
  1401.                         addText += event.text.unicode;
  1402.                     }
  1403.                     UpdateText(addDisplayText, addText);
  1404.                 }
  1405.                 if (selected == 2) {
  1406.                     if (event.text.unicode == '-') {
  1407.                         minus2 = true;
  1408.                         delText += event.text.unicode;
  1409.                     }
  1410.                     else {
  1411.                         minus2 = false;
  1412.                     }
  1413.                     if (event.text.unicode >= '0' && event.text.unicode <= '9' &&
  1414.                         (delText.size() < 9 || delText.size() < 10 && minus2)) {
  1415.                         delText += event.text.unicode;
  1416.                     }
  1417.                     UpdateText(delDisplayText, delText);
  1418.                 }
  1419.                 if (selected == 3) {
  1420.                     if (event.text.unicode >= '0' && event.text.unicode <= '9' &&
  1421.                         (addNtext.size() < 9)) {
  1422.                         addNtext += event.text.unicode;
  1423.                     }
  1424.                     UpdateText(addNDisplayText, addNtext);
  1425.                 }
  1426.             }
  1427.             if (event.type == sf::Event::MouseButtonPressed) {
  1428.                 if (addNodeBox.getGlobalBounds().contains(event.mouseButton.x,
  1429.                     event.mouseButton.y)) {
  1430.                     selected = 1;
  1431.                     addNodeBox.setOutlineColor(reactColor);
  1432.                     removeNodeBox.setOutlineColor(elementColor);
  1433.                     addNBox.setOutlineColor(elementColor);
  1434.                 }
  1435.                 else if (removeNodeBox.getGlobalBounds().contains(event.mouseButton.x,
  1436.                     event.mouseButton.y)) {
  1437.                     selected = 2;
  1438.                     removeNodeBox.setOutlineColor(reactColor);
  1439.                     addNodeBox.setOutlineColor(elementColor);
  1440.                     addNBox.setOutlineColor(elementColor);
  1441.                 }
  1442.                 else if (addNBox.getGlobalBounds().contains(event.mouseButton.x,
  1443.                     event.mouseButton.y)) {
  1444.                     selected = 3;
  1445.                     addNBox.setOutlineColor(reactColor);
  1446.                     addNodeBox.setOutlineColor(elementColor);
  1447.                     removeNodeBox.setOutlineColor(elementColor);
  1448.                 }
  1449.                 else {
  1450.                     selected = 0;
  1451.                     removeNodeBox.setOutlineColor(elementColor);
  1452.                     addNodeBox.setOutlineColor(elementColor);
  1453.                     addNBox.setOutlineColor(elementColor);
  1454.                 }
  1455.                 if (addNodeButton.getGlobalBounds().contains(event.mouseButton.x,
  1456.                     event.mouseButton.y)) {
  1457.                     if (selected == 3) {
  1458.                         int n = Convetr(addNtext);
  1459.                         addNtext.clear();
  1460.                         UpdateText(addNDisplayText, addNtext);
  1461.                         for (int i = 0; i < n; ++i) {
  1462.                             int ans = std::rand() % 1000000000;
  1463.                             avl.insert(ans, avl.root);
  1464.                             redBlack.insert(ans);
  1465.                             treap.insert(ans);
  1466.                             splay.insert(ans);
  1467.                         }
  1468.                     }
  1469.                     else if (selected == 1) {
  1470.                         int ans = Convetr(addText);
  1471.                         addText.clear();
  1472.                         UpdateText(addDisplayText, addText);
  1473.                         avl.insert(ans, avl.root);
  1474.                         redBlack.insert(ans);
  1475.                         treap.insert(ans);
  1476.                         splay.insert(ans);
  1477.                     }
  1478.                     if (treeType == 0) {
  1479.                         renderTree.create(avl.root, treePos, scale);
  1480.                     }
  1481.                     if (treeType == 1) {
  1482.                         renderTree.create(redBlack.root, treePos, scale);
  1483.                     }
  1484.                     if (treeType == 2) {
  1485.                         renderTree.create(treap.root, treePos, scale);
  1486.                     }
  1487.                     if (treeType == 3) {
  1488.                         renderTree.create(splay.root, treePos, scale);
  1489.                     }
  1490.                 }
  1491.                 if (removeNodeButton.getGlobalBounds().contains(event.mouseButton.x,
  1492.                     event.mouseButton.y)) {
  1493.                     int ans = Convetr(delText);
  1494.                     delText.clear();
  1495.                     UpdateText(delDisplayText, delText);
  1496.                     avl.remove(ans, avl.root);
  1497.                     redBlack.erase(ans);
  1498.                     treap.remove(ans);
  1499.                     splay.remove(ans);
  1500.                     if (treeType == 0) {
  1501.                         renderTree.create(avl.root, treePos, scale);
  1502.                     }
  1503.                     if (treeType == 1) {
  1504.                         renderTree.create(redBlack.root, treePos, scale);
  1505.                     }
  1506.                     if (treeType == 2) {
  1507.                         renderTree.create(treap.root, treePos, scale);
  1508.                     }
  1509.                     if (treeType == 3) {
  1510.                         renderTree.create(splay.root, treePos, scale);
  1511.                     }
  1512.                 }
  1513.                 if (treetype1.getGlobalBounds().contains(event.mouseButton.x,
  1514.                     event.mouseButton.y)) {
  1515.                     treeType = 0;
  1516.                     treetype1.setOutlineColor(reactColor);
  1517.                     treetype2.setOutlineColor(elementColor);
  1518.                     treetype3.setOutlineColor(elementColor);
  1519.                     treetype4.setOutlineColor(elementColor);
  1520.                     renderTree.create(avl.root, treePos, scale);
  1521.                 }
  1522.                 if (treetype2.getGlobalBounds().contains(event.mouseButton.x,
  1523.                     event.mouseButton.y)) {
  1524.                     treeType = 1;
  1525.                     treetype2.setOutlineColor(reactColor);
  1526.                     treetype1.setOutlineColor(elementColor);
  1527.                     treetype3.setOutlineColor(elementColor);
  1528.                     treetype4.setOutlineColor(elementColor);
  1529.                     renderTree.create(redBlack.root, treePos, scale);
  1530.                 }
  1531.                 if (treetype3.getGlobalBounds().contains(event.mouseButton.x,
  1532.                     event.mouseButton.y)) {
  1533.                     treeType = 2;
  1534.                     treetype3.setOutlineColor(reactColor);
  1535.                     treetype2.setOutlineColor(elementColor);
  1536.                     treetype1.setOutlineColor(elementColor);
  1537.                     treetype4.setOutlineColor(elementColor);
  1538.                     renderTree.create(treap.root, treePos, scale);
  1539.                 }
  1540.                 if (treetype4.getGlobalBounds().contains(event.mouseButton.x,
  1541.                     event.mouseButton.y)) {
  1542.                     treeType = 3;
  1543.                     treetype4.setOutlineColor(reactColor);
  1544.                     treetype2.setOutlineColor(elementColor);
  1545.                     treetype3.setOutlineColor(elementColor);
  1546.                     treetype1.setOutlineColor(elementColor);
  1547.                     renderTree.create(splay.root, treePos, scale);
  1548.                 }
  1549.                 RenderNode* mbNode = MousePressed(event.mouseButton.x, event.mouseButton.y, renderTree.root);
  1550.                 if (mbNode != nullptr) {
  1551.                     int ans = mbNode->key;
  1552.                     avl.remove(ans, avl.root);
  1553.                     redBlack.erase(ans);
  1554.                     treap.remove(ans);
  1555.                     splay.remove(ans);
  1556.                     if (treeType == 0) {
  1557.                         renderTree.create(avl.root, treePos, scale);
  1558.                     }
  1559.                     if (treeType == 1) {
  1560.                         renderTree.create(redBlack.root, treePos, scale);
  1561.                     }
  1562.                     if (treeType == 2) {
  1563.                         renderTree.create(treap.root, treePos, scale);
  1564.                     }
  1565.                     if (treeType == 3) {
  1566.                         renderTree.create(splay.root, treePos, scale);
  1567.                     }
  1568.                 }
  1569.                 else {
  1570.  
  1571.                 }
  1572.             }
  1573.         }
  1574.  
  1575.         window.clear(backgroundColor);
  1576.  
  1577.         renderTree.draw(window);
  1578.  
  1579.         window.draw(addNodeBox);
  1580.         window.draw(addNBox);
  1581.         window.draw(removeNodeButton);
  1582.         window.draw(addNodeButton);
  1583.         window.draw(removeNodeBox);
  1584.  
  1585.         window.draw(treetype1);
  1586.         window.draw(treetype2);
  1587.         window.draw(treetype3);
  1588.         window.draw(treetype4);
  1589.  
  1590.         window.draw(addDisplayText);
  1591.         window.draw(addNDisplayText);
  1592.         window.draw(addButtonText);
  1593.         window.draw(delButtonText);
  1594.         window.draw(delDisplayText);
  1595.  
  1596.         window.draw(treetext1);
  1597.         window.draw(treetext3);
  1598.         window.draw(treetext4);
  1599.         window.draw(treetext2);
  1600.  
  1601.  
  1602.  
  1603.         window.display();
  1604.     }
  1605. }
  1606.  
  1607. /*
  1608. Avl avl;
  1609.     while (true) {
  1610.         int a;
  1611.         std::cin >> a;
  1612.         if (a == 0) {
  1613.             InOrder(avl.root);
  1614.             std::cout << "\n";
  1615.             TreeOrder(avl.root);
  1616.         }
  1617.         if (a == 1) {
  1618.             int key;
  1619.             std::cin >> key;
  1620.             std::cout << avl.insert(key, avl.root) << "\n";
  1621.         }
  1622.         if (a == 2) {
  1623.             int key;
  1624.             std::cin >> key;
  1625.             std::cout << avl.remove(key, avl.root) << "\n";
  1626.         }
  1627.         if (a >= 3) {
  1628.             for (int i = 0; i < a; ++i) {
  1629.                 int k;
  1630.                 int key;
  1631.                 std::cin >> key;
  1632.                 std::cout << avl.insert(key, avl.root) << "\n";
  1633.             }
  1634.         }
  1635.     }
  1636. */
  1637.  
  1638. /*
  1639. 5
  1640. 3 10 15 30 29
  1641.  
  1642.  
  1643. 437
  1644. 3485
  1645. 238
  1646. 483
  1647. 285
  1648. 22
  1649. 355
  1650. 348
  1651. 345
  1652. 23
  1653. 25699
  1654. 8346867
  1655. 934988
  1656. 483276
  1657. 2931
  1658. 59328528
  1659. 283582385
  1660. 38723
  1661. 237582358
  1662. 2
  1663. 32735285
  1664. 69
  1665. 1585
  1666. 3382
  1667. 384
  1668. 23415
  1669. 2643
  1670. 523
  1671. 247724
  1672. 999999999
  1673. 556
  1674. */
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!