/*
 * Copyright (c) 23rd January 2011, Luca Risolia
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are met:
 *     * Redistributions of source code must retain the above copyright
 *       notice, this list of conditions and the following disclaimer.
 *     * Redistributions in binary form must reproduce the above copyright
 *       notice, this list of conditions and the following disclaimer in the
 *       documentation and/or other materials provided with the distribution.
 *     * Neither the name of the <organization> nor the
 *       names of its contributors may be used to endorse or promote products
 *       derived from this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY <copyright holder> ``AS IS'' AND ANY
 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
 * DISCLAIMED. IN NO EVENT SHALL <copyright holder> BE LIABLE FOR ANY
 * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */

#include <iostream>
#include <cstdlib>

using namespace std;

class Intset {
public:

    Intset(size_t capacity = 1) : capacity_(capacity), delta(capacity > 0 ? capacity : 1),
    size(0), a(new int[capacity]) { }

    Intset(const Intset& s) : capacity_(s.capacity_), delta(s.delta), size(s.size),
    a(new int[capacity_]) {
        for (size_t i = 0; i < size; i++)
            a[i] = s.a[i];
    }

    Intset & operator=(const Intset& s) {
        if (this != &s) {
            delete[] a;
            a = new int[s.capacity_];
            for (size_t i = 0; i < s.size; i++)
                a[i] = s.a[i];
            capacity_ = s.capacity_;
            size = s.size;
            delta = s.delta;
        }
        return *this;
    }

    ~Intset() {
        delete[] a;
    }

    void insert(int x) {
        for (size_t i = 0; i < size; i++)
            if (a[i] == x)
                return;
        if (size >= capacity_) {
            int* b = new int[capacity_ + delta];
            for (size_t i = 0; i < size; i++)
                b[i] = a[i];
            delete[] a;
            a = b;
            capacity_ += delta;
        }
        a[size++] = x;
    }

    void remove(int x) {
        for (size_t i = 0; i < size; i++) {
            if (a[i] == x) {
                a[i] = a[--size];
                if (capacity_ - size >= delta) {
                    int* b = new int[capacity_ - delta];
                    for (size_t i = 0; i < size; i++)
                        b[i] = a[i];
                    delete[] a;
                    a = b;
                    capacity_ -= delta;
                }
                return;
            }
        }
    }

    Intset& insert(const Intset& s) {
        if (this != &s) {
            for (size_t i = 0; i < s.size; i++)
                insert(s.a[i]);
        }
        return *this;
    }

    Intset& remove(const Intset& s) {
        if (this != &s) {
            for (size_t i = 0; i < s.size; i++)
                remove(s.a[i]);
        } else {
            delete[] a;
            capacity_ = 0;
            size = 0;
            a = 0;
        }
        return *this;
    }

    Intset& intersect(const Intset& s) {
        if (this != &s) {
            remove(Intset(*this).remove(s));
        }
        return *this;
    }

    int at(size_t i) const {
        if (i < size)
            return a[i];
        else
            throw int(-1);
    }

    size_t get_size() const {
        return size;
    }

    size_t get_capacity() const {
        return capacity_;
    }

private:
    size_t capacity_, delta, size;
    int* a;
};

void print(const Intset& s) {
    for (size_t i = 0; i < s.get_size(); i++)
        cout << s.at(i) << ", ";
    cout << endl;
}

int main(int argc, char** argv) {
    Intset s(10);
    s.insert(1);
    s.insert(2);
    s.insert(3);
    s.insert(4);
    s.insert(5);
    s.insert(6);
    s.remove(1);
    print(s);
    cout << s.get_size() << "\n";
    Intset p = s;
    print(p);
    cout << p.get_size() << "\n";
    p.remove(s);
    print(p);
    p.insert(7);
    p.insert(8);
    p.insert(9);
    p.insert(10);
    p.insert(11);
    p.insert(2);
    print(p);
    cout << p.get_size() << "\n";
    cout << p.get_capacity() << "\n";
    p.insert(s);
    p.insert(s);
    print(p);
    Intset q;
    q.insert(90);
    q.insert(78);
    p.intersect(q);
    print(p);
    cout << p.get_size() << "\n";
    cout << p.get_capacity() << "\n";
    return 0;
}