Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- template <class T>
- class LinkedList{
- public:
- virtual void push_back(T val) = 0;
- virtual void push_front(T val) = 0;
- virtual int size() = 0;
- virtual bool isempty() = 0;
- virtual void clear() = 0;
- virtual T back() = 0;
- virtual T front() = 0;
- virtual T pop_front() = 0;
- virtual void pop_back() = 0;
- virtual T get(int index) = 0;
- };
- template<class K>
- class Node{
- public:
- K value;
- Node* next = nullptr;
- Node* previus = nullptr;
- Node(K value){
- this->value = value;
- }
- };
- template<class T>
- class DoubleLinkedList : public LinkedList<T>{
- int length = 0;
- Node<T>* head = nullptr;
- Node<T>* tail = nullptr;
- public:
- void push_back(T val) override
- {
- Node<T>* new_val = (new Node<T>(val));
- if(length == 0){
- head = new_val;
- tail = new_val;
- }else{
- auto x = head;
- head = new_val;
- new_val = x;
- new_val->next = head;
- head->previus = new_val;
- }
- length++;
- }
- void push_front(T val)override
- {
- auto new_val = new Node<T>(val);
- if(length == 0){
- head = new_val;
- tail = new_val;
- }else{
- auto x = tail;
- tail = new_val;
- new_val = x;
- new_val->previus = tail;
- tail->next = new_val;
- }
- length++;
- }
- int size() override
- {
- return length;
- }
- bool isempty()override
- {
- return (length == 0);
- }
- void clear()override
- {
- length = 0;
- delete tail->next;
- delete tail->previus;
- delete head->next;
- delete head->previus;
- head = nullptr;
- tail = nullptr;
- }
- T front()override
- {
- assert(tail != nullptr);
- return tail->value;
- }
- T back()override
- {
- assert(head != nullptr);
- return head->value;
- }
- T pop_front()override
- {
- if(isempty()){
- throw std::runtime_error("eee be ota list kholihay, kjo pop_front() mekni");
- }
- T res = tail->value;
- if(tail->next != nullptr){
- assert(tail->next != nullptr);
- auto x = tail;
- tail = tail->next;
- tail->previus = nullptr;
- delete x;
- }else{
- delete tail->next;
- delete tail->previus;
- delete head->next;
- delete head->previus;
- tail = nullptr;
- head = nullptr;
- }
- length--;
- return res;
- }
- void pop_back()override
- {
- if(length == 0){
- throw std::runtime_error("eee be ota list kholihay, kjo pop_back() mekni");
- }
- else if(head->previus == nullptr){
- delete tail->next;
- delete tail->previus;
- delete head->next;
- delete head->previus;
- tail = nullptr;
- head = nullptr;
- }else{
- assert(head->previus != nullptr);
- auto x = head;
- head = head->previus;
- head->next = nullptr;
- delete x;
- }
- length--;
- }
- virtual T get(int index){
- if(index < 0 || index >= length){
- throw std::runtime_error("out of bounded array index");
- }else{
- Node<T>* current_node = tail;
- for(int i = 0; i < index; i ++){
- current_node = current_node->next;
- }
- return current_node->value;
- }
- }
- };
- /*
- template<class T>
- class ICircularBoundedQueue
- {
- public:
- virtual void offer(T value) = 0;
- // insert an element to the rear of the queue
- // overwrite the oldest elements
- // when the queue is full
- virtual T poll() = 0;// remove an element from the front of the queue and return removed element
- virtual T peek() = 0;// look at the element at the front of the queue
- // (without removing it)
- virtual void flush() = 0;// remove all elements from the queue
- virtual bool isEmpty() = 0;// is the queue empty?
- virtual bool isFull() = 0;// is the queue full?
- virtual int size() = 0;// number of elements
- virtual int capacity() = 0;// maximum capacity
- };
- template <class T>
- class CircularBoundedQueue : public ICircularBoundedQueue<T>{
- DoubleLinkedList <T> q;
- int Capacity;
- public:
- CircularBoundedQueue(int C=100) : Capacity(C){}
- void init(int C)
- {
- Capacity = C;
- }
- virtual void offer(T new_variable)override
- {
- if(q.size() >= capacity()){
- auto x = q.front();
- q.pop_front();
- delete[] x.first.a;
- delete[] x.first.b;
- delete[] x.second.a;
- delete[] x.second.b;
- }
- q.push_back(new_variable);
- }
- virtual T poll()override
- {
- T x = q.front();
- q.pop_front();
- return x;
- }
- virtual T peek()override
- {
- return q.front();
- }
- virtual void flush()override
- {
- q.clear();
- }
- virtual bool isFull() override
- {
- return (q.size() == capacity());
- }
- virtual bool isEmpty() override
- {
- return q.isempty();
- }
- virtual int size() override
- {
- return q.size();
- }
- virtual int capacity() override
- {
- return Capacity;
- }
- };
- */
- template<class T>
- class ICircularBoundedQueue
- {
- public:
- virtual void offer(T value) = 0;
- virtual T poll() = 0;
- virtual T peek() = 0;
- virtual void flush() = 0;
- virtual bool isEmpty() const = 0;
- virtual bool isFull() const = 0;
- virtual int size() const = 0;
- virtual int capacity() const = 0;
- virtual ~ICircularBoundedQueue() = default;
- };
- template <class T>
- class CircularBoundedQueue : public ICircularBoundedQueue<T>{
- T* a;
- int Capacity;
- int l = 0, r = -1;
- public:
- void init(int C)
- {
- Capacity = C;
- delete a;
- a = new T[C];
- }
- void add(int &x, int val){
- x += val;
- x %= Capacity;
- x += Capacity;
- x %= Capacity;
- }
- virtual void offer(T new_variable)override
- {
- if(r != -1 && (r + 1) % Capacity == l){
- add(l, 1);
- }
- add(r, 1);
- a[r] = new_variable;
- }
- virtual T poll()override
- {
- T x = a[l];
- if(l == r){
- r = -1;
- l = 0;
- }else add(l, 1);
- return x;
- }
- virtual T peek()override
- {
- return a[l];
- }
- virtual void flush()override
- {
- l = 0, r = -1;
- }
- virtual bool isFull() const override
- {
- return (r + 1) % Capacity == l;
- }
- virtual bool isEmpty() const override
- {
- return (r == -1);
- }
- virtual int size() const override
- {
- if(r == -1)return 0;
- if(l <= r)return r - l + 1;
- return Capacity - l + r + 1;
- }
- virtual int capacity() const override
- {
- return Capacity;
- }
- };
- template<class T>
- class Stack{
- virtual void push(T value) = 0;// push an element onto the stack
- // remove the oldest element
- // when if stack is full
- virtual T pop() = 0; // remove an element from the top of the stack
- virtual T top() = 0; // look at the element at the top of the stack
- // (without removing it)
- virtual void flush() = 0;// remove all elements from the stack
- virtual bool isEmpty() = 0;// is the stack empty?
- virtual bool isFull() = 0;// is the stack full?
- virtual int size() = 0; // number of elements
- virtual int capacity() = 0; // maximum capacity
- };
- template<class T>
- class BoundedStack : public Stack<T>{
- CircularBoundedQueue<T> q1;
- CircularBoundedQueue<T> q2;
- int Capacity;
- public:
- void init(int val){
- Capacity = val;
- q1.init(val);
- q2.init(val);
- }
- void push(T value) override
- {
- if(q1.isEmpty()){
- q1.offer(value);
- }else{
- if(q1.size() == capacity()){
- while(!q1.isEmpty()){
- if(q1.size() == 1){
- auto x = q1.peek();
- q1.poll();
- delete[] x.first.a;
- delete[] x.first.b;
- delete[] x.second.a;
- delete[] x.second.b;
- break;
- }
- q2.offer(q1.poll());
- }
- }else{
- while(!q1.isEmpty()){
- q2.offer(q1.poll());
- }
- }
- q1.offer(value);
- while(!q2.isEmpty()){
- q1.offer(q2.poll());
- }
- }
- }
- int capacity()override
- {
- return Capacity;
- }
- T pop()override
- {
- return q1.poll();
- }
- T top()override
- {
- assert(!q1.isEmpty());
- return q1.peek();
- }
- void flush()override
- {
- while(!q1.isEmpty()){
- q1.poll();
- }
- }
- int size()override
- {
- return q1.size();
- }
- bool isEmpty()override
- {
- return (q1.size() == 0);
- }
- bool isFull() override
- {
- return (q1.size() == capacity());
- }
- };
- template<class T>
- class Iset{
- virtual void add(T item) = 0; // add item in the set
- virtual void remove(T item) = 0; // remove an item from a set
- virtual bool contains(T item) = 0; // check if a item belongs to a set
- virtual int size() = 0; // number of elements in a set
- virtual bool isEmpty() = 0; // check if the set is empty
- };
- template <class T>
- class DoubleHasSet : public Iset<T>{
- public:
- int* a;
- T* b;
- int length = 0;
- int Capacity = 2;
- DoubleHasSet()
- {
- Capacity = 2;
- a = new int[2];
- b = new T[2];
- a[0] = a[1] = 0;
- length = 0;
- }
- int getHash(T key, int j)
- {
- auto hashfunc = std::hash<T>();
- int val = hashfunc(key);
- val = abs(val);
- int res = val % capacity();
- res += j;
- res %= capacity();
- if(res < 0)res += capacity();
- return res;
- }
- void resize()
- {
- int old_capacity = capacity();
- Capacity *= 2;
- auto x = b;
- auto y = a;
- b = new T[Capacity];
- a = new int[Capacity];
- for(int i = 0; i < Capacity; i++){
- a[i] = 0;
- }
- length = 0;
- for(int i = 0; i < old_capacity; i++){
- if(y[i] == 1){
- add(x[i]);
- }
- }
- delete[] x;
- delete[] y;
- }
- void add(T item) override
- {
- if(capacity() == size()){
- resize();
- }
- if(contains(item))return;
- int j = 0;
- while(j <= capacity() && a[getHash(item, j)] == 1){
- j++;
- }
- if(a[getHash(item, j)] == 1){
- throw runtime_error("You can not add new element, because of capacity");
- }
- a[getHash(item, j)] = 1;
- b[getHash(item, j)] = item;
- length++;
- }
- bool contains(T item)override
- {
- int j = 0;
- while(j <= capacity() && a[getHash(item, j)] != 0){
- if(a[getHash(item, j)] == 1 && b[getHash(item, j)] == item){
- return true;
- }
- j++;
- }
- return false;
- }
- void remove(T item)override
- {
- int j = 0;
- while(j <= capacity() && a[getHash(item, j)] != 0){
- if(a[getHash(item, j)] == 1 && b[getHash(item, j)] == item){
- a[getHash(item, j)] = 2;
- length--;
- break;
- }
- j++;
- }
- }
- int size()override
- {
- return length;
- }
- bool isEmpty()override
- {
- return size() == 0;
- }
- int capacity()
- {
- return Capacity;
- }
- };
- int main()
- {
- //freopen("input.txt", "r", stdin);
- string A;
- int n,k;
- cin >> n >> k;
- BoundedStack<pair<DoubleHasSet<string>, DoubleHasSet<string>>> st;
- getline(cin, A);
- st.init(k);
- DoubleHasSet<string> a,b;
- st.push({a, b});// empty set
- while(n--){
- getline(cin, A);
- string s = "",t = "";
- for(int i = 0, j = 0; i < (int)A.size(); i++){
- if(A[i] == ' '){
- if(j == 1){
- s = "N";
- break;
- }
- j = 1;
- }else if(j){
- t += A[i];
- }else{
- s += A[i];
- }
- }
- if(s == "NEW"){
- auto File = st.top().first;
- auto Directory = st.top().second;
- auto x = new int[File.capacity()];
- auto y = new string[File.capacity()];
- for(int i = 0; i < File.capacity(); i++){
- x[i] = File.a[i];
- y[i] = File.b[i];
- }
- auto xx = new int[Directory.capacity()];
- auto yy = new string[Directory.capacity()];
- for(int i = 0; i < Directory.capacity(); i++){
- xx[i] = Directory.a[i];
- yy[i] = Directory.b[i];
- }
- File.a = x;
- File.b = y;
- Directory.a = xx;
- Directory.b = yy;
- if(t.back() == '/'){
- t.pop_back();
- if(Directory.contains(t) || File.contains(t)){
- cout << "ERROR: cannot execute " << A << endl;
- continue;
- }
- Directory.add(t);
- }else{
- if(Directory.contains(t) || File.contains(t)){
- cout << "ERROR: cannot execute " << A << endl;
- continue;
- }
- File.add(t);
- }
- st.push({File, Directory});
- }else if(s == "REMOVE"){
- auto File = st.top().first;
- auto Directory = st.top().second;
- auto x = new int[File.capacity()];
- auto y = new string[File.capacity()];
- for(int i = 0; i < File.capacity(); i++){
- x[i] = File.a[i];
- y[i] = File.b[i];
- }
- auto xx = new int[Directory.capacity()];
- auto yy = new string[Directory.capacity()];
- for(int i = 0; i < Directory.capacity(); i++){
- xx[i] = Directory.a[i];
- yy[i] = Directory.b[i];
- }
- File.a = x;
- File.b = y;
- Directory.a = xx;
- Directory.b = yy;
- if(t.back() == '/'){
- t.pop_back();
- if(!Directory.contains(t)){
- cout << "ERROR: cannot execute " << A << endl;
- continue;
- }
- Directory.remove(t);
- }else{
- if(!File.contains(t)){
- cout << "ERROR: cannot execute " << A << endl;
- continue;
- }
- File.remove(t);
- }
- st.push({File, Directory});
- }else if(s == "UNDO"){
- int n1 = 1;
- bool f = false;
- if((int)t.size() > 0){
- n1 = 0;
- for(int i = 0; i < (int)t.size(); i++){
- if(!('0' <= t[i] && t[i] <= '9')){
- cout << "ERROR: cannot execute " << A << endl;
- f = true;
- break;
- }
- n1 *= 10;
- n1 += t[i] - '0';
- }
- }
- if(f)continue;
- if(n1 >= st.size()){
- cout << "ERROR: cannot execute " << A << endl;
- continue;
- }
- for(int i = 1; i <= n1; i++){
- delete[] st.top().first.a;
- delete[] st.top().first.b;
- delete[] st.top().second.a;
- delete[] st.top().second.b;
- st.pop();
- }
- }else if(s == "LIST"){
- auto File = st.top().first;
- auto Directory = st.top().second;
- for(int i = 0; i < File.capacity(); i++){
- if(File.a[i] == 1){
- cout << File.b[i] << " ";
- }
- }
- for(int i = 0; i < Directory.capacity(); i++){
- if(Directory.a[i] == 1){
- cout << Directory.b[i] << "/ ";
- }
- }
- cout << endl;
- }else{
- cout << "ERROR: cannot execute " << A << endl;
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment