/* 
 *  bag:  T -> N bag
 *  (C) Porkolab Zoltan, ELTE, Budapest, Hungary
 *  (C) 2001
 */

#include <list>
#include <algorithm>

template <class T>
class bad_value
{
public:
    bad_value( const T& t) : m_value(t) { }
    T value() { return m_value; }
private:
    T m_value;
};

template <class T>
class bag
{
public:
    void put( const T& t);
    bool remove( const T& t);
    bool remove_all( const T& t);
    int  mul( const T& t) const;
    int  operator[]( const T& t) const;
private:
    struct my_pair 
    {
        my_pair(T f, int s) : first(f), second(s) { }
        T   first;
        int second;
        int operator==(const my_pair& x) const { return first == x.first; }
    };
    std::list<my_pair> lst;
};

template <class T>
int bag<T>::mul( const T& t) const
{
    my_pair mp(t,1);
    typename std::list<my_pair>::const_iterator ci = 
                find(lst.begin(), lst.end(), mp);

    return  ci == lst.end() ? 0 : ci->second;
}

template <class T>
void bag<T>::put( const T& t)
{
    my_pair mp(t,1);
    typename std::list<my_pair>::iterator ci = 
                find(lst.begin(), lst.end(), mp);

    if ( ci == lst.end() )
    {
        lst.push_back(mp);
    }
    else
    {
        ++ ci->second;  
    }
}

template <class T>
bool bag<T>::remove( const T& t)
{
    my_pair mp(t,1);
    typename std::list<my_pair>::iterator ci = 
                find(lst.begin(), lst.end(), mp);

    if ( ci != lst.end() )
    {
        if( 0  ==  -- ci->second )
            lst.erase(ci);
        return true;
    }
    return false;
}

template <class T>
bool bag<T>::remove_all( const T& t)
{
    my_pair mp(t,1);
    typename std::list<my_pair>::iterator ci = 
                find(lst.begin(), lst.end(), mp);

    if ( ci != lst.end() )
    {
        lst.erase(ci);
        return true;
    }
    return false;
}


template <class T>
int bag<T>::operator[]( const T& t) const
{
    if( int i = mul(t) )
        return i;
    else
        throw bad_value<long>(t);
}