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// umap.h
7//
8
9#ifndef UMAP_H_45643F516E02A87A3DCEA5024052A6F5
10#define UMAP_H_45643F516E02A87A3DCEA5024052A6F5
11
12#include "uassert.h"
13#include "ufunction.h"
14#include "uvector.h"
15
16namespace ustl {
17
18/// \class map umap.h ustl.h
19/// \ingroup AssociativeContainers
20///
21/// \brief A sorted associative container of pair<K,V>
22///
23template <typename K, typename V>
24class map : 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 map<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			map (void)			: vector<pair<K,V> > () {}
46    explicit inline		map (size_type n)		: vector<pair<K,V> > (n) {}
47    inline			map (rcself_t v)		: vector<pair<K,V> > (v) {}
48    inline			map (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 const_data_ref	operator[] (const_key_ref i) const;
51    data_type&			operator[] (const_key_ref i);
52    inline size_type		size (void) const		{ return (base_class::size()); }
53    inline iterator		begin (void)			{ return (base_class::begin()); }
54    inline const_iterator	begin (void) const		{ return (base_class::begin()); }
55    inline iterator		end (void)			{ return (base_class::end()); }
56    inline const_iterator	end (void) const		{ return (base_class::end()); }
57    inline void			assign (const_iterator i1, const_iterator i2)	{ clear(); insert (i1, i2); }
58    inline void			push_back (const_reference v)			{ insert (v); }
59    inline const_iterator	find (const_key_ref k) const;
60    inline iterator		find (const_key_ref k)	{ return (const_cast<iterator> (const_cast<rcself_t>(*this).find (k))); }
61    inline const_iterator	find_data (const_data_ref v, const_iterator first = NULL, const_iterator last = NULL) const;
62    inline iterator		find_data (const_data_ref v, iterator first = NULL, iterator last = NULL);
63    iterator			insert (const_reference v);
64    void			insert (const_iterator i1, const_iterator i2);
65    inline void			erase (const_key_ref k);
66    inline iterator		erase (iterator ep)	{ return (base_class::erase (ep)); }
67    inline iterator		erase (iterator ep1, iterator ep2) { return (base_class::erase (ep1, ep2)); }
68    inline void			clear (void)		{ base_class::clear(); }
69private:
70    const_iterator		lower_bound (const_key_ref k) const;
71    inline iterator		lower_bound (const_key_ref k) { return (const_cast<iterator>(const_cast<rcself_t>(*this).lower_bound (k))); }
72};
73
74template <typename K, typename V>
75typename map<K,V>::const_iterator map<K,V>::lower_bound (const_key_ref k) const
76{
77    const_iterator first (begin()), last (end());
78    while (first != last) {
79	const_iterator mid = advance (first, distance (first,last) / 2);
80	if (mid->first < k)
81	    first = advance (mid, 1);
82	else
83	    last = mid;
84    }
85    return (first);
86}
87
88/// Returns the pair<K,V> where K = \p k.
89template <typename K, typename V>
90inline typename map<K,V>::const_iterator map<K,V>::find (const_key_ref k) const
91{
92    const_iterator i = lower_bound (k);
93    return ((i < end() && k < i->first) ? end() : i);
94}
95
96/// Returns the pair<K,V> where V = \p v, occuring in range [first,last).
97template <typename K, typename V>
98inline typename map<K,V>::const_iterator map<K,V>::find_data (const_data_ref v, const_iterator first, const_iterator last) const
99{
100    if (!first) first = begin();
101    if (!last) last = end();
102    for (; first != last && first->second != v; ++first);
103    return (first);
104}
105
106/// Returns the pair<K,V> where V = \p v, occuring in range [first,last).
107template <typename K, typename V>
108inline typename map<K,V>::iterator map<K,V>::find_data (const_data_ref v, iterator first, iterator last)
109{
110    return (const_cast<iterator> (find_data (v, const_cast<const_iterator>(first), const_cast<const_iterator>(last))));
111}
112
113/// Returns data associated with key \p k.
114template <typename K, typename V>
115inline const typename map<K,V>::data_type& map<K,V>::operator[] (const_key_ref k) const
116{
117    assert (find(k) != end() && "operator[] const can not insert non-existent keys");
118    return (find(k)->second);
119}
120
121/// Returns data associated with key \p k.
122template <typename K, typename V>
123typename map<K,V>::data_type& map<K,V>::operator[] (const_key_ref k)
124{
125    iterator ip = lower_bound (k);
126    if (ip == end() || k < ip->first)
127	ip = base_class::insert (ip, make_pair (k, V()));
128    return (ip->second);
129}
130
131/// Inserts the pair into the container.
132template <typename K, typename V>
133typename map<K,V>::iterator map<K,V>::insert (const_reference v)
134{
135    iterator ip = lower_bound (v.first);
136    if (ip == end() || v.first < ip->first)
137	ip = base_class::insert (ip, v);
138    else
139	*ip = v;
140    return (ip);
141}
142
143/// Inserts elements from range [i1,i2) into the container.
144template <typename K, typename V>
145void map<K,V>::insert (const_iterator i1, const_iterator i2)
146{
147    assert (i1 <= i2);
148    reserve (size() + distance (i1, i2));
149    for (; i1 != i2; ++i1)
150	insert (*i1);
151}
152
153/// Erases the element with key value \p k.
154template <typename K, typename V>
155inline void map<K,V>::erase (const_key_ref k)
156{
157    iterator ip = find (k);
158    if (ip != end())
159	erase (ip);
160}
161
162} // namespace ustl
163
164#endif
165
166