/* 
 *  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;       // T -> int
};


template <class T>
int bag<T>::mul( const T& t) const
{
    // asszociatív adatszerkezeteken van O(log n) -es find
    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]; // csak map-en, és nincsen const verziója:
                 // ha korábban nam létezett, akkor létrehozza a bejegyzést
}

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égegyszer O(lon n)
            m_map.erase(t);         // harmadszorra is O(log n)
     */
        if ( 0 == -- ci->second )   // konstans
            m_map.erase(ci);        // konstans
        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(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);
}