1-ShadowMaster-1

Untitled

Feb 17th, 2022
636
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 19.88 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. template <class T>
  6. class LinkedList{
  7. public:
  8.         virtual void push_back(T val) = 0;
  9.         virtual void push_front(T val) = 0;
  10.         virtual int size() = 0;
  11.         virtual bool isempty() = 0;
  12.         virtual void clear() = 0;
  13.         virtual T back() = 0;
  14.         virtual T front() = 0;
  15.         virtual T pop_front() = 0;
  16.         virtual void pop_back() = 0;
  17.         virtual T get(int index) = 0;
  18. };
  19.  
  20. template<class K>
  21. class Node{
  22. public:
  23.         K value;
  24.         Node* next = nullptr;
  25.         Node* previus = nullptr;
  26.         Node(K value){
  27.                 this->value = value;
  28.         }
  29. };
  30.  
  31. template<class T>
  32. class DoubleLinkedList : public LinkedList<T>{
  33.  
  34. int length = 0;
  35. Node<T>* head = nullptr;
  36. Node<T>* tail = nullptr;
  37.  
  38. public:
  39.         void push_back(T val) override
  40.         {
  41.                 Node<T>* new_val = (new Node<T>(val));
  42.                 if(length == 0){
  43.                         head = new_val;
  44.                         tail = new_val;
  45.                 }else{
  46.                         auto x = head;
  47.                         head = new_val;
  48.                         new_val = x;
  49.                         new_val->next = head;
  50.                         head->previus = new_val;
  51.                 }
  52.                 length++;
  53.         }
  54.  
  55.         void push_front(T val)override
  56.         {
  57.                 auto new_val = new Node<T>(val);
  58.                 if(length == 0){
  59.                         head = new_val;
  60.                         tail = new_val;
  61.                 }else{
  62.                         auto x = tail;
  63.                         tail = new_val;
  64.                         new_val = x;
  65.                         new_val->previus = tail;
  66.                         tail->next = new_val;
  67.                 }
  68.                 length++;
  69.         }
  70.  
  71.         int size() override
  72.         {
  73.                 return length;
  74.         }
  75.  
  76.         bool isempty()override
  77.         {
  78.                 return (length == 0);
  79.         }
  80.  
  81.         void clear()override
  82.         {
  83.                 length = 0;
  84.                 delete tail->next;
  85.                 delete tail->previus;
  86.                 delete head->next;
  87.                 delete head->previus;
  88.                 head = nullptr;
  89.                 tail = nullptr;
  90.         }
  91.  
  92.         T front()override
  93.         {
  94.                 assert(tail != nullptr);
  95.                 return tail->value;
  96.         }
  97.  
  98.         T back()override
  99.         {
  100.                 assert(head != nullptr);
  101.                 return head->value;
  102.         }
  103.  
  104.         T pop_front()override
  105.         {
  106.                 if(isempty()){
  107.                         throw std::runtime_error("eee be ota list kholihay, kjo pop_front() mekni");
  108.                 }
  109.                 T res = tail->value;
  110.                 if(tail->next != nullptr){
  111.                         assert(tail->next != nullptr);
  112.                         auto x = tail;
  113.                         tail = tail->next;
  114.                         tail->previus = nullptr;
  115.                         delete x;
  116.                 }else{
  117.                         delete tail->next;
  118.                         delete tail->previus;
  119.                         delete head->next;
  120.                         delete head->previus;
  121.                         tail = nullptr;
  122.                         head = nullptr;
  123.                 }
  124.                 length--;
  125.                 return res;
  126.         }
  127.  
  128.         void pop_back()override
  129.         {
  130.                 if(length == 0){
  131.                         throw std::runtime_error("eee be ota list kholihay, kjo pop_back() mekni");
  132.                 }
  133.                 else if(head->previus == nullptr){
  134.                         delete tail->next;
  135.                         delete tail->previus;
  136.                         delete head->next;
  137.                         delete head->previus;
  138.                         tail = nullptr;
  139.                         head = nullptr;
  140.                 }else{
  141.                         assert(head->previus != nullptr);
  142.                         auto x = head;
  143.                         head = head->previus;
  144.                         head->next = nullptr;
  145.                         delete x;
  146.                 }
  147.                 length--;
  148.         }
  149.         virtual T get(int index){
  150.                 if(index < 0 || index >= length){
  151.                     throw std::runtime_error("out of bounded array index");
  152.                 }else{
  153.                     Node<T>* current_node = tail;
  154.                     for(int i = 0; i < index; i ++){
  155.                         current_node = current_node->next;
  156.                     }
  157.                     return current_node->value;
  158.                 }
  159.             }
  160. };
  161.  
  162. template<class T>
  163. class ICircularBoundedQueue
  164. {
  165.         public:
  166.         virtual void offer(T value) = 0;
  167.         // insert an element to the rear of the queue
  168.         // overwrite the oldest elements
  169.         // when the queue is full
  170.         virtual T poll() = 0;// remove an element from the front of the queue and return removed element
  171.         virtual T peek() = 0;// look at the element at the front of the queue
  172.         // (without removing it)
  173.         virtual void flush() = 0;// remove all elements from the queue
  174.         virtual bool isEmpty() = 0;// is the queue empty?
  175.         virtual bool isFull() = 0;// is the queue full?
  176.         virtual int size() = 0;// number of elements
  177.         virtual int capacity() = 0;// maximum capacity
  178. };
  179.  
  180. template <class T>
  181. class CircularBoundedQueue : public ICircularBoundedQueue<T>{
  182.  
  183.         DoubleLinkedList <T> q;
  184.         int Capacity;
  185. public:
  186.         CircularBoundedQueue(int C=100) : Capacity(C){}
  187.         void init(int C)
  188.         {
  189.                 Capacity = C;
  190.         }
  191.         virtual void offer(T new_variable)override
  192.         {
  193.                 if(q.size() >= capacity()){
  194.                         auto x = q.front();
  195.                         q.pop_front();
  196.                         delete[] x.first.a;
  197.                         delete[] x.first.b;
  198.                         delete[] x.second.a;
  199.                         delete[] x.second.b;
  200.                 }
  201.                 q.push_back(new_variable);
  202.         }
  203.  
  204.         virtual T poll()override
  205.         {
  206.                 T x = q.front();
  207.                 q.pop_front();
  208.                 return x;
  209.         }
  210.  
  211.         virtual T peek()override
  212.         {
  213.                 return q.front();
  214.         }
  215.  
  216.         virtual void flush()override
  217.         {
  218.                 q.clear();
  219.         }
  220.  
  221.         virtual bool isFull() override
  222.         {
  223.                 return (q.size() == capacity());
  224.         }
  225.  
  226.         virtual bool isEmpty() override
  227.         {
  228.                 return q.isempty();
  229.         }
  230.  
  231.         virtual int size() override
  232.         {
  233.                 return q.size();
  234.         }
  235.  
  236.         virtual int capacity() override
  237.         {
  238.                 return Capacity;
  239.         }
  240.  
  241. };
  242.  
  243.  
  244. template<class T>
  245. class Stack{
  246.         virtual void push(T value) = 0;// push an element onto the stack
  247.                                         // remove the oldest element
  248.                                         // when if stack is full
  249.         virtual T pop() = 0;    // remove an element from the top of the stack
  250.         virtual T top() = 0;    // look at the element at the top of the stack
  251.                                 // (without removing it)
  252.         virtual void flush() = 0;// remove all elements from the stack
  253.         virtual bool isEmpty() = 0;// is the stack empty?
  254.         virtual bool isFull() = 0;// is the stack full?
  255.         virtual int size() = 0; // number of elements
  256.         virtual int capacity() = 0; // maximum capacity
  257. };
  258.  
  259. template<class T>
  260. class BoundedStack : public Stack<T>{
  261.         CircularBoundedQueue<T> q1;
  262.         CircularBoundedQueue<T> q2;
  263.         int Capacity;
  264. public:
  265.         void init(int val){
  266.                 Capacity = val;
  267.                 q1.init(val);
  268.                 q2.init(val);
  269.         }
  270.  
  271.         void push(T value) override
  272.         {
  273.                 if(q1.isEmpty()){
  274.                         q1.offer(value);
  275.                 }else{
  276.                         if(q1.size() == capacity()){
  277.                                 while(!q1.isEmpty()){
  278.                                         if(q1.size() == 1){
  279.                                                 auto x = q1.peek();
  280.                                                 q1.poll();
  281.                                                 delete[] x.first.a;
  282.                                                 delete[] x.first.b;
  283.                                                 delete[] x.second.a;
  284.                                                 delete[] x.second.b;
  285.                                                 break;
  286.                                         }
  287.                                         q2.offer(q1.poll());
  288.                                 }
  289.                         }else{
  290.                                 while(!q1.isEmpty()){
  291.                                         q2.offer(q1.poll());
  292.                                 }
  293.                         }
  294.                         q1.offer(value);
  295.                         while(!q2.isEmpty()){
  296.                                 q1.offer(q2.poll());
  297.                         }
  298.                 }
  299.         }
  300.  
  301.         int capacity()override
  302.         {
  303.             return Capacity;
  304.         }
  305.  
  306.         T pop()override
  307.         {
  308.                 return q1.poll();
  309.         }
  310.  
  311.         T top()override
  312.         {
  313.                 assert(!q1.isEmpty());
  314.                 return q1.peek();
  315.         }
  316.  
  317.         void flush()override
  318.         {
  319.                 while(!q1.isEmpty()){
  320.                         q1.poll();
  321.                 }
  322.         }
  323.  
  324.         int size()override
  325.         {
  326.                 return q1.size();
  327.         }
  328.  
  329.         bool isEmpty()override
  330.         {
  331.                 return (q1.size() == 0);
  332.         }
  333.  
  334.         bool isFull() override
  335.         {
  336.                 return (q1.size() == capacity());
  337.         }
  338. };
  339.  
  340. template<class T>
  341. class Iset{
  342.         virtual void add(T item) = 0; // add item in the set
  343.         virtual void remove(T item) = 0; // remove an item from a set
  344.         virtual bool contains(T item) = 0; // check if a item belongs to a set
  345.         virtual int size() = 0; // number of elements in a set
  346.         virtual bool isEmpty() = 0; // check if the set is empty
  347. };
  348.  
  349. template <class T>
  350. class DoubleHasSet : public Iset<T>{
  351. public:
  352.         int* a;
  353.         T* b;
  354.         int length = 0;
  355.         int Capacity = 2;
  356.         DoubleHasSet()
  357.         {
  358.                 Capacity = 2;
  359.                 a = new int[2];
  360.                 b = new T[2];
  361.                 a[0] = a[1] = 0;
  362.                 length = 0;
  363.         }
  364.  
  365.         int getHash(T key, int j)
  366.         {
  367.                 auto hashfunc = std::hash<T>();
  368.                 int val = hashfunc(key);
  369.                 val = abs(val);
  370.                 int res = val % capacity();
  371.                 res += j;
  372.                 res %= capacity();
  373.                 if(res < 0)res += capacity();
  374.                 return res;
  375.         }
  376.  
  377.         void resize()
  378.         {
  379.                 int old_capacity = capacity();
  380.                 Capacity *= 2;
  381.                 auto x = b;
  382.                 auto y = a;
  383.                 b = new T[Capacity];
  384.                 a = new int[Capacity];
  385.                 for(int i = 0; i < Capacity; i++){
  386.                         a[i] = 0;
  387.                 }
  388.                 length = 0;
  389.                 for(int i = 0; i < old_capacity; i++){
  390.                         if(y[i] == 1){
  391.                                 add(x[i]);
  392.                         }
  393.                 }
  394.                 delete[] x;
  395.                 delete[] y;
  396.         }
  397.  
  398.         void add(T item) override
  399.         {
  400.                 if(capacity() == size()){
  401.                         resize();
  402.                 }
  403.                 if(contains(item))return;
  404.                 int j = 0;
  405.                 while(j <= capacity() && a[getHash(item, j)] == 1){
  406.                         j++;
  407.                 }
  408.                 if(a[getHash(item, j)] == 1){
  409.                         throw runtime_error("You can not add new element, because of capacity");
  410.                 }
  411.                 a[getHash(item, j)] = 1;
  412.                 b[getHash(item, j)] = item;
  413.                 length++;
  414.         }
  415.  
  416.         bool contains(T item)override
  417.         {
  418.                 int j = 0;
  419.                 while(j <= capacity() && a[getHash(item, j)] != 0){
  420.                         if(a[getHash(item, j)] == 1 && b[getHash(item, j)] == item){
  421.                                 return true;
  422.                         }
  423.                         j++;
  424.                 }
  425.                 return false;
  426.         }
  427.  
  428.         void remove(T item)override
  429.         {
  430.                 int j = 0;
  431.                 while(j <= capacity() && a[getHash(item, j)] != 0){
  432.                         if(a[getHash(item, j)] == 1 && b[getHash(item, j)] == item){
  433.                                 a[getHash(item, j)] = 2;
  434.                                 length--;
  435.                                 break;
  436.                         }
  437.                         j++;
  438.                 }
  439.         }
  440.  
  441.         int size()override
  442.         {
  443.                 return length;
  444.         }
  445.  
  446.         bool isEmpty()override
  447.         {
  448.                 return size() == 0;
  449.         }
  450.  
  451.         int capacity()
  452.         {
  453.                 return Capacity;
  454.         }
  455. };
  456.  
  457.  
  458.  
  459. int main()
  460. {
  461.         //freopen("input.txt", "r", stdin);
  462.         string A;
  463.         int n,k;
  464.         cin >> n >> k;
  465.         BoundedStack<pair<DoubleHasSet<string>, DoubleHasSet<string>>> st;
  466.         getline(cin, A);
  467.         st.init(k);
  468.         DoubleHasSet<string> a,b;
  469.         st.push({a, b});// empty set
  470.         while(n--){
  471.                 getline(cin, A);
  472.                 string s = "",t = "";
  473.                 for(int i = 0, j = 0; i < (int)A.size(); i++){
  474.                         if(A[i] == ' '){
  475.                                 if(j == 1){
  476.                                         s = "N";
  477.                                         break;
  478.                                 }
  479.                                 j = 1;
  480.                         }else if(j){
  481.                                 t += A[i];
  482.                         }else{
  483.                                 s += A[i];
  484.                         }
  485.                 }
  486.                 if(s == "NEW"){
  487.                         auto File = st.top().first;
  488.                         auto Directory = st.top().second;
  489.                         auto x = new int[File.capacity()];
  490.                         auto y = new string[File.capacity()];
  491.                         for(int i = 0; i < File.capacity(); i++){
  492.                                 x[i] = File.a[i];
  493.                                 y[i] = File.b[i];
  494.                         }
  495.                         auto xx = new int[Directory.capacity()];
  496.                         auto yy = new string[Directory.capacity()];
  497.                         for(int i = 0; i < Directory.capacity(); i++){
  498.                                 xx[i] = Directory.a[i];
  499.                                 yy[i] = Directory.b[i];
  500.                         }
  501.                         File.a = x;
  502.                         File.b = y;
  503.                         Directory.a = xx;
  504.                         Directory.b = yy;
  505.                         if(t.back() == '/'){
  506.                                 t.pop_back();
  507.                                 if(Directory.contains(t) || File.contains(t)){
  508.                                         cout << "ERROR: cannot execute " << A << endl;
  509.                                         continue;
  510.                                 }
  511.                                 Directory.add(t);
  512.                         }else{
  513.                                if(Directory.contains(t) || File.contains(t)){
  514.                                         cout << "ERROR: cannot execute " << A << endl;
  515.                                         continue;
  516.                                 }
  517.                                 File.add(t);
  518.                         }
  519.                         st.push({File, Directory});
  520.                 }else if(s == "REMOVE"){
  521.                         auto File = st.top().first;
  522.                         auto Directory = st.top().second;
  523.                         auto x = new int[File.capacity()];
  524.                         auto y = new string[File.capacity()];
  525.                         for(int i = 0; i < File.capacity(); i++){
  526.                                 x[i] = File.a[i];
  527.                                 y[i] = File.b[i];
  528.                         }
  529.                         auto xx = new int[Directory.capacity()];
  530.                         auto yy = new string[Directory.capacity()];
  531.                         for(int i = 0; i < Directory.capacity(); i++){
  532.                                 xx[i] = Directory.a[i];
  533.                                 yy[i] = Directory.b[i];
  534.                         }
  535.                         File.a = x;
  536.                         File.b = y;
  537.                         Directory.a = xx;
  538.                         Directory.b = yy;
  539.                         if(t.back() == '/'){
  540.                                 t.pop_back();
  541.                                 if(!Directory.contains(t)){
  542.                                         cout << "ERROR: cannot execute " << A << endl;
  543.                                         continue;
  544.                                 }
  545.                                 Directory.remove(t);
  546.                         }else{
  547.                                if(!File.contains(t)){
  548.                                         cout << "ERROR: cannot execute " << A << endl;
  549.                                         continue;
  550.                                 }
  551.                                 File.remove(t);
  552.                         }
  553.                         st.push({File, Directory});
  554.                 }else if(s == "UNDO"){
  555.                         int n1 = 1;
  556.                         bool f = false;
  557.                         if((int)t.size() > 0){
  558.                                 n1 = 0;
  559.                                 for(int i = 0; i < (int)t.size(); i++){
  560.                                         if(!('0' <= t[i] && t[i] <= '9')){
  561.                                                 cout << "ERROR: cannot execute " << A << endl;
  562.                                                 f = true;
  563.                                                 break;
  564.                                         }
  565.                                         n1 *= 10;
  566.                                         n1 += t[i] - '0';
  567.                                 }
  568.                         }
  569.                         if(f)continue;
  570.                         if(n1 >= st.size()){
  571.                                 cout << "ERROR: cannot execute " << A << endl;
  572.                                 continue;
  573.                         }
  574.                         for(int i = 1; i <= n1; i++){
  575.                                 delete[] st.top().first.a;
  576.                                 delete[] st.top().first.b;
  577.                                 delete[] st.top().second.a;
  578.                                 delete[] st.top().second.b;
  579.                                 st.pop();
  580.                         }
  581.                 }else if(s == "LIST"){
  582.                         auto File = st.top().first;
  583.                         auto Directory = st.top().second;
  584.                         for(int i = 0; i < File.capacity(); i++){
  585.                                 if(File.a[i] == 1){
  586.                                         cout << File.b[i] << " ";
  587.                                 }
  588.                         }
  589.                         for(int i = 0; i < Directory.capacity(); i++){
  590.                                 if(Directory.a[i] == 1){
  591.                                         cout << Directory.b[i] << "/ ";
  592.                                 }
  593.                         }
  594.                         cout << endl;
  595.                 }else{
  596.                         cout << "ERROR: cannot execute " << A << endl;
  597.                 }
  598.         }
  599. }
  600.  
Advertisement
Add Comment
Please, Sign In to add comment