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


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:
    bag() : head(0) { }
    ~bag();
    bag( const bag& rhs);
    const bag& operator=( const bag& rhs);

    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 node
    {
        node( const T& t, int m, node *p, node *n) 
                   : value(t), cnt(m), prev(p), next(n) { } 
        ~node() 
        { 
            if ( prev ) prev->next = next; 
            if ( next ) next->prev = prev;
        }
        node *clone() 
        {
            return new node( this->value, this->cnt, 0, 0);
        }
        T value;
        int cnt;
        node* prev;
        node* next;
    };
    node* head;
    node* find( const T& t);
    const node* find( const T& t) const;
    void copy( const bag& rhs);
    void destroy();
};

template <class T>
bag<T>::~bag()
{
    destroy();
}

template <class T>
void bag<T>::destroy()
{
    node *r = head;
    while ( r )
    {
        head = r->next;
        delete r;
        r = head;
    }
}

template <class T>
bag<T>::bag( const bag& rhs)
{
    copy(rhs);
}

template <class T>
const bag<T>& bag<T>::operator=( const bag& rhs)
{
    if ( this != &rhs )
    {
        destroy();
        copy(rhs);
    }
    return *this;
}

template <class T>
bag<T>::node* bag<T>::find(const T& t)
{
    node *r = head;
    while ( r  &&  r->value != t )
        r = r->next;
    return r;
}

template <class T>
const bag<T>::node* bag<T>::find(const T& t) const 
{
    node *r = head;
    while ( r  &&  r->value != t )
        r = r->next;
    return r;
}

template <class T>
void bag<T>::copy(const bag& rhs)
{
    node *r = rhs.head; node *last;
    if ( r ) 
    {
        last = head = r->clone(); last->prev = 0; r = r->next;
    }
    while ( r )
    {
        last->next = r->clone(); last = last->next; last->prev = 0; r = r->next;
    }
}

template <class T>
int bag<T>::mul( const T& t) const
{
    if( const node<T>* np = find(t) )
    {
        return np->cnt;
    }
    else
    {
        return 0;
    }
}

template <class T>
void bag<T>::put( const T& t)
{
    if( node<T>* np = find(t) )
    {
        ++np->cnt;
    }
    else
    {
         head = new node(t,1,0,head);
         if (head->next) head->next->prev = head;
    }
}

template <class T>
bool bag<T>::remove( const T& t)
{
    if( node<T>* np = find(t) )
    {
        --np->cnt;
        if ( 0 == np->cnt ) delete np;
        return true;
    }
    else
    {
        return false;
    }
}

template <class T>
bool bag<T>::remove_all( const T& t)
{
    if( node<T>* np = find(t) )
    {
        delete np;
        return true;
    }
    else
    {
        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);
}