ostapdontstop

delete minmax

Apr 12th, 2020
277
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <stdio.h>
  2. #include <cmath>
  3.  
  4.  
  5.  
  6. class List
  7. {
  8. public:
  9.     struct queue {
  10.         queue(int x) : value(x) {}
  11.         int value;
  12.         queue *next = 0, *prev = 0, *large = 0, *small = 0;
  13.     } *beg = 0, *end = 0, *max = 0, *min = 0;
  14.  
  15.     void push(int x) {
  16.         queue *p = new queue(x);
  17.  
  18.         if (end) end->next = p;
  19.         if (!beg) beg = p;
  20.  
  21.         p->prev = end;
  22.         end = p;
  23.  
  24.         if (!max || !min) {
  25.             max = min = p;
  26.             return;
  27.         }
  28.  
  29.         queue *s = min;
  30.         while(s) {
  31.             if (x < s->value) {
  32.                 p->large = s;
  33.  
  34.                 if (s->small) {
  35.                     p->small = s->small;
  36.                     s->small->large = p;
  37.                 } else {
  38.                     min = p;
  39.                 }
  40.                
  41.                 s->small = p;
  42.  
  43.                 return;
  44.             }
  45.             s = s->large;
  46.         }
  47.         p->small = max;
  48.         max->large = p;
  49.         max = p;
  50.     }
  51.     void delete_el() {
  52.         if (last_hit()) return;
  53.  
  54.         link_max_large(beg);
  55.  
  56.         queue *p = beg->next;
  57.         delete beg;
  58.         beg = p;
  59.         beg->prev = 0;
  60.     }
  61.     void delete_min() {
  62.         if (last_hit()) return;
  63.  
  64.         link_prev_next(min);
  65.  
  66.         queue *p = min->large;
  67.         delete min;
  68.         min = p;
  69.         min->small = 0;
  70.     }
  71.     void delete_max() {
  72.         if (last_hit()) return;
  73.  
  74.         link_prev_next(max);
  75.  
  76.         queue *p = max->small;
  77.         delete max;
  78.         max = p;
  79.         max->large = 0;
  80.     }
  81.  
  82.     bool last_hit() {
  83.         if (beg == end) {
  84.             delete beg;
  85.             beg = end = min = max = 0;
  86.             return true;
  87.         }
  88.         return false;
  89.     }
  90.  
  91. private:
  92.     void link_prev_next(queue *p) {
  93.  
  94.         if (p->prev && p->next) {
  95.             p->prev->next = p->next;
  96.             p->next->prev = p->prev;
  97.         }
  98.         if (!p->prev) {
  99.             beg = p->next;
  100.             beg->prev = 0;
  101.         }
  102.  
  103.         if (!p->next) {
  104.             end = p->prev;
  105.             end->next = 0;
  106.         }
  107.     }
  108.     void link_max_large(queue *p) {
  109.         if (p->small && p->large) {
  110.             p->small->large = p->large;
  111.             p->large->small = p->small;
  112.         }
  113.         else if (!p->large) {
  114.             max = p->small;
  115.             max->large = 0;
  116.         }
  117.         else if (!p->small) {
  118.             min = p->large;
  119.             min->small = 0;
  120.         }
  121.     }
  122.    
  123. };
  124.  
  125. int main(int argc, char const *argv[])
  126. {
  127.     List list;
  128.  
  129.     list.push(1);
  130.     list.push(12);
  131.     list.push(6);
  132.     list.push(24);
  133.  
  134.     list.delete_min();
  135.     // list.delete_max();
  136.     // list.delete_max();
  137.     // list.delete_max();
  138.  
  139.  
  140.  
  141.  
  142.    
  143.  
  144.     for (List::queue *el = list.min; el; el = el->large)
  145.     // for (List::queue *el = list.max; el; el = el->small)
  146.     // for (List::queue *el = list.beg; el; el = el->next)
  147.     // for (List::queue *el = list.end; el; el = el->prev)
  148.     {
  149.         printf("%i\n", el->value);
  150.     }
  151.  
  152.  
  153.  
  154. }
RAW Paste Data