Subversion Repositories openrisc

// This file is part of the uSTL library, an STL implementation.

//

// Copyright (c) 2005-2009 by Mike Sharov <msharov@users.sourceforge.net>

// This file is free software, distributed under the MIT License.

#ifndef UMULTIMAP_H_45743F516E02A87A3FCEA5024052A6F5

#define UMULTIMAP_H_45743F516E02A87A3FCEA5024052A6F5

#include "uvector.h"

#include "ufunction.h"

namespace ustl {

/// \class multimap umultimap.h ustl.h

/// \ingroup AssociativeContainers

///

/// \brief A sorted associative container that may container multiple entries for each key.

///

template <typename K, typename V>

class multimap : public vector<pair<K,V> > {

public:

    typedef K                                           key_type;

    typedef V                                           data_type;

    typedef const K&                                    const_key_ref;

    typedef const V&                                    const_data_ref;

    typedef const multimap<K,V>&                        rcself_t;

    typedef vector<pair<K,V> >                          base_class;

    typedef typename base_class::value_type     value_type;

    typedef typename base_class::size_type      size_type;

    typedef typename base_class::pointer        pointer;

    typedef typename base_class::const_pointer  const_pointer;

    typedef typename base_class::reference      reference;

    typedef typename base_class::const_reference        const_reference;

    typedef typename base_class::const_iterator         const_iterator;

    typedef typename base_class::iterator               iterator;

    typedef typename base_class::reverse_iterator       reverse_iterator;

    typedef typename base_class::const_reverse_iterator const_reverse_iterator;

    typedef pair<const_iterator,const_iterator>         const_range_t;

    typedef pair<iterator,iterator>                     range_t;

public:

    inline                      multimap (void)         : vector<pair<K,V> > () {}

    explicit inline             multimap (size_type n)  : vector<pair<K,V> > (n) {}

    inline                      multimap (rcself_t v)   : vector<pair<K,V> > (v) {}

    inline                      multimap (const_iterator i1, const_iterator i2) : vector<pair<K,V> > () { insert (i1, i2); }

    inline rcself_t             operator= (rcself_t v)  { base_class::operator= (v); return (*this); }

    inline size_type            size (void) const       { return (base_class::size()); }

    inline iterator             begin (void)            { return (base_class::begin()); }

    inline const_iterator       begin (void) const      { return (base_class::begin()); }

    inline iterator             end (void)              { return (base_class::end()); }

    inline const_iterator       end (void) const        { return (base_class::end()); }

    inline void                 assign (const_iterator i1, const_iterator i2) { clear(); insert (i1, i2); }

    inline size_type            count (const_key_ref k) const           { return (upper_bound(k) - lower_bound(k)); }

    inline void                 push_back (const_reference v)           { insert (v); }

    inline const_range_t        equal_range (const_key_ref k) const     { return (make_pair (lower_bound(k), upper_bound(k))); }

    inline range_t              equal_range (const_key_ref k)           { return (make_pair (const_cast<iterator>(lower_bound(k)), const_cast<iterator>(upper_bound(k)))); }

    const_iterator              lower_bound (const_key_ref k) const;

    const_iterator              upper_bound (const_key_ref k) const;

    inline iterator             insert (const_reference v);

    void                        insert (const_iterator i1, const_iterator i2);

    inline void                 erase (const_key_ref k)                 { erase (const_cast<iterator>(lower_bound(k)), const_cast<iterator>(upper_bound(k))); }

    inline iterator             erase (iterator ep)                     { return (base_class::erase (ep)); }

    inline iterator             erase (iterator ep1, iterator ep2)      { return (base_class::erase (ep1, ep2)); }

    inline void                 clear (void)                            { base_class::clear(); }

};

/// Returns an iterator to the first element with key value \p k.

template <typename K, typename V>

typename multimap<K,V>::const_iterator multimap<K,V>::lower_bound (const_key_ref k) const

{

    const_iterator first (begin()), last (end());

    while (first != last) {

        const_iterator mid = advance (first, distance (first,last) / 2);

        if (mid->first < k)

            first = advance (mid, 1);

        else

            last = mid;

    }

    return (first);

}

/// Returns an iterator to the first element with key value \p k.

template <typename K, typename V>

typename multimap<K,V>::const_iterator multimap<K,V>::upper_bound (const_key_ref k) const

{

    const_iterator first (begin()), last (end());

    while (first != last) {

        const_iterator mid = advance (first, distance (first,last) / 2);

        if (k < mid->first)

            last = mid;

        else

            first = advance (mid, 1);

    }

    return (last);

}

/// Inserts the pair into the container.

template <typename K, typename V>

inline typename multimap<K,V>::iterator multimap<K,V>::insert (const_reference v)

{

    iterator ip = const_cast<iterator> (upper_bound (v.first));

    return (base_class::insert (ip, v));

}

/// Inserts elements from range [i1,i2) into the container.

template <typename K, typename V>

void multimap<K,V>::insert (const_iterator i1, const_iterator i2)

{

    assert (i1 <= i2);

    reserve (size() + distance (i1, i2));

    for (; i1 != i2; ++i1)

        insert (*i1);

}

} // namespace ustl

#endif