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

#include <map>
#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:
    std::map< T, int>  m_map;
};


template <class T>
int bag<T>::mul( const T& t) const
{
    typename std::map<T,int>::const_iterator ci = m_map.find(t);
    return  ci == m_map.end() ? 0 : ci->second;
}

template <class T>
void bag<T>::put( const T& t)
{
/*    typename std::map<T,int>::const_iterator ci = m_map.find(t);

    if ( ci == m_map.end() )
    {
    m_map[t] = 1;
    }
    else
    {
    ++ m_map[t];
    }
*/ 
    ++ m_map[t];
}

template <class T>
bool bag<T>::remove( const T& t)
{
    typename std::map<T,int>::const_iterator ci = m_map.find(t);

    if ( ci != m_map.end() )
    {
    if ( 0 == -- m_map[t] )
        m_map.erase(t);
    return true;
    }
    return false;
}

template <class T>
bool bag<T>::remove_all( const T& t)
{
    typename std::map<T,int>::const_iterator ci = m_map.find(t);

    if ( ci != m_map.end() )
    {
    m_map.erase(t);
    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);
}