Cod sursa(job #916831)

Utilizator gabipurcaruGabi Purcaru gabipurcaru Data 16 martie 2013 22:09:51
Problema Hashuri Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 5.02 kb
#include <fstream>
using namespace std;


// A node in a doubly-linked list
template<class T>
class Node {
private:
    T val;              // The information in the node
    Node *next, *prev;  // Links to the next/previous nodes
public:
    // We only need standard getters and setters

    T getVal() {
        return val;
    }
    void setVal(T x) {
        val = x;
    }
    Node* getPrev() {
        return prev;
    }
    void setPrev(Node *x) {
        prev = x;
    }
    Node* getNext() {
        return next;
    }
    void setNext(Node *x) {
        next = x;
    }
};


// A doubly-linked list; it contains Node elements
template<class T>
class List {
private:
    int size;              // How many elements the list contains
    Node<T> *start, *end;  // References to the start and end
                           // of the list
public:
    int getSize() {
        return size;
    }
    Node<T>* getStart() {
        return start;
    }
    // Adds an element at the end of the list
    void add(T val) {
        if(size == 0) {
            start = end = new Node<T>;
            start->setVal(val);
        } else {
            Node<T> *n = new Node<T>;
            n->setVal(val);
            n->setPrev(end);
            end->setNext(n);
            end = n;
        }
        size ++;
    }
    // Deletes all occurrences of val from the list
    // this is O(n), should only be used on small
    // lists
    void del(T val) {
        if(size == 0) {
            return;
        } else if(size == 1) {
            if(start->getVal() == val) {
                delete start;
                start = end = NULL;
                size --;
            }
        } else {
            Node<T> *p = start, *q;
            while(p != NULL) {
                if(p->getVal() == val) {
                    if(p->getPrev() != NULL) {
                        p->getPrev()->setNext(p->getNext());
                    }
                    if(p->getNext() != NULL) {
                        p->getNext()->setPrev(p->getPrev());
                    }
                    q = p;
                    p = p->getNext();
                    delete q;
                    size --;
                    continue;
                }
                p = p->getNext();
            }
        }
    }
    // Searches for val in the list; returns 1 if val is in the
    // list, and 0 otherwise
    int search(T val) {
        if(size == 0) {
            return 0;
        } else if(size == 1) {
            return start->getVal() == val;
        } else {
            Node<T> *p = start;
            while(p != NULL) {
                if(p->getVal() == val) {
                    return 1;
                }
                p = p->getNext();
            }
            return 0;
        }
    }
};


// The hash. Internally, it contains two simple hashes,
// and a value is stored in the most convenient of them
template<class T>
class Hash {
private:
    List<T> *H1;
    List<T> *H2;
    int n1;
    int n2;
    int (*hash_func)(int, T);
    int max_size;

    // When a list exceedes a certain length, rehash it
    void rehash(List<T> *l, List<T> *h, int n) {
        Node<T> *p = l->getStart();
        while(p != NULL) {
            h[hash_func(n, p->getVal())].add(p->getVal());
            p = p->getNext();
            delete p->getPrev();
        }
    }
public:
    // A hash is created from two hash sizes and a hash function.
    // The hash function takes (n, val) as arguments,
    // where val is the hashed value, and returns an integer
    // between 0 and n-1, inclusively
    Hash(int n, int m, int (h)(int, T)) {
        max_size = 10;
        hash_func = h;
        H1 = new List<T>[n];
        H2 = new List<T>[m];
        n1 = n;
        n2 = m;
    }
    // An item is added to the hash like this:
    // hash += value
    // This method also rehashes if needed
    void operator+=(T val) {
        List<T> *a = &H1[hash_func(n1, val)], *b = &H2[hash_func(n2, val)];
        if(a->getSize() > max_size) {
            rehash(a, H2, n2);
        }
        if(b->getSize() > max_size) {
            rehash(b, H1, n1);
        }
        if(a->getSize() < b->getSize()) {
            a->add(val);
        } else {
            b->add(val);
        }
    }
    // An item is removed from the hash like this:
    // hash -= value
    void operator-=(T val) {
        H1[hash_func(n1, val)].del(val);
        H2[hash_func(n2, val)].del(val);
    }
    // A hash lookup looks like this:
    // hash[value]  // 1 if value is found, 0 otherwise
    int operator[](T val) {
        return H1[hash_func(n1, val)].search(val)
            || H2[hash_func(n2, val)].search(val);
    }
};


// standard, simple hash function
int hash_int(int n, int val) {
    return val % n;
}


int main() {
    ifstream in("hashuri.in");
    ofstream out("hashuri.out");
    Hash<int> h(66047, 96557, hash_int);
    int n, op, v, i;

    in>>n;
    for(i=0; i<n; i++) {
        in>>op>>v;
        if(op == 1) {
            h += v;
        } else if(op == 2) {
            h -= v;
        } else {
            out<<h[v]<<'\n';
        }
    }
    return 0;
}