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


// implementation with list

#include <list>
#include <algorithm>

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;
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;
}


//////////////////////////////////////////////////////////

// implementation with map


#include <map>
#include <algorithm>

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;
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];
}

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;
}



//////////////////////////////////////////////////////////

// improvements



template <class T>
void bag<T>::put( const T& 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 == -- ci->second )   // m_map[t]
            m_map.erase(ci);        // 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(ci);
        return true;
    }
    return false;
}