1// This file is part of the ustl library, an STL implementation.
2//
3// Copyright (C) 2005 by Mike Sharov <msharov@users.sourceforge.net>
4// This file is free software, distributed under the MIT License.
5//
6// umultimap.h
7//
8
9#ifndef UMULTIMAP_H_45743F516E02A87A3FCEA5024052A6F5
10#define UMULTIMAP_H_45743F516E02A87A3FCEA5024052A6F5
11
12#include "uassert.h"
13#include "ufunction.h"
14#include "uvector.h"
15
16namespace ustl {
17
18/// \class multimap umultimap.h ustl.h
19/// \ingroup AssociativeContainers
20///
21/// \brief A sorted associative container that may container multiple entries for each key.
22///
23template <typename K, typename V>
24class multimap : public vector<pair<K,V> > {
25public:
26    typedef K						key_type;
27    typedef V						data_type;
28    typedef const K&					const_key_ref;
29    typedef const V&					const_data_ref;
30    typedef const multimap<K,V>&			rcself_t;
31    typedef vector<pair<K,V> >				base_class;
32    typedef typename base_class::value_type	value_type;
33    typedef typename base_class::size_type	size_type;
34    typedef typename base_class::pointer	pointer;
35    typedef typename base_class::const_pointer	const_pointer;
36    typedef typename base_class::reference	reference;
37    typedef typename base_class::const_reference	const_reference;
38    typedef typename base_class::const_iterator		const_iterator;
39    typedef typename base_class::iterator		iterator;
40    typedef typename base_class::reverse_iterator	reverse_iterator;
41    typedef typename base_class::const_reverse_iterator	const_reverse_iterator;
42    typedef pair<const_iterator,const_iterator>		const_range_t;
43    typedef pair<iterator,iterator>			range_t;
44public:
45    inline			multimap (void)		: vector<pair<K,V> > () {}
46    explicit inline		multimap (size_type n)	: vector<pair<K,V> > (n) {}
47    inline			multimap (rcself_t v)	: vector<pair<K,V> > (v) {}
48    inline			multimap (const_iterator i1, const_iterator i2)	: vector<pair<K,V> > () { insert (i1, i2); }
49    inline rcself_t		operator= (rcself_t v)	{ base_class::operator= (v); return (*this); }
50    inline size_type		size (void) const	{ return (base_class::size()); }
51    inline iterator		begin (void)		{ return (base_class::begin()); }
52    inline const_iterator	begin (void) const	{ return (base_class::begin()); }
53    inline iterator		end (void)		{ return (base_class::end()); }
54    inline const_iterator	end (void) const	{ return (base_class::end()); }
55    inline void			assign (const_iterator i1, const_iterator i2) { clear(); insert (i1, i2); }
56    inline size_type		count (const_key_ref k) const		{ return (upper_bound(k) - lower_bound(k)); }
57    inline void			push_back (const_reference v)		{ insert (v); }
58    inline const_range_t	equal_range (const_key_ref k) const	{ return (make_pair (lower_bound(k), upper_bound(k))); }
59    inline range_t		equal_range (const_key_ref k)		{ return (make_pair (const_cast<iterator>(lower_bound(k)), const_cast<iterator>(upper_bound(k)))); }
60    const_iterator		lower_bound (const_key_ref k) const;
61    const_iterator		upper_bound (const_key_ref k) const;
62    inline iterator		insert (const_reference v);
63    void			insert (const_iterator i1, const_iterator i2);
64    inline void			erase (const_key_ref k)			{ erase (const_cast<iterator>(lower_bound(k)), const_cast<iterator>(upper_bound(k))); }
65    inline iterator		erase (iterator ep)			{ return (base_class::erase (ep)); }
66    inline iterator		erase (iterator ep1, iterator ep2)	{ return (base_class::erase (ep1, ep2)); }
67    inline void			clear (void)				{ base_class::clear(); }
68};
69
70/// Returns an iterator to the first element with key value \p k.
71template <typename K, typename V>
72typename multimap<K,V>::const_iterator multimap<K,V>::lower_bound (const_key_ref k) const
73{
74    const_iterator first (begin()), last (end());
75    while (first != last) {
76	const_iterator mid = advance (first, distance (first,last) / 2);
77	if (mid->first < k)
78	    first = advance (mid, 1);
79	else
80	    last = mid;
81    }
82    return (first);
83}
84
85/// Returns an iterator to the first element with key value \p k.
86template <typename K, typename V>
87typename multimap<K,V>::const_iterator multimap<K,V>::upper_bound (const_key_ref k) const
88{
89    const_iterator first (begin()), last (end());
90    while (first != last) {
91	const_iterator mid = advance (first, distance (first,last) / 2);
92	if (k < mid->first)
93	    last = mid;
94	else
95	    first = advance (mid, 1);
96    }
97    return (last);
98}
99
100/// Inserts the pair into the container.
101template <typename K, typename V>
102inline typename multimap<K,V>::iterator multimap<K,V>::insert (const_reference v)
103{
104    iterator ip = const_cast<iterator> (upper_bound (v.first));
105    return (base_class::insert (ip, v));
106}
107
108/// Inserts elements from range [i1,i2) into the container.
109template <typename K, typename V>
110void multimap<K,V>::insert (const_iterator i1, const_iterator i2)
111{
112    assert (i1 <= i2);
113    reserve (size() + distance (i1, i2));
114    for (; i1 != i2; ++i1)
115	insert (*i1);
116}
117
118} // namespace ustl
119
120#endif
121
122