1/*
2 *
3 * Copyright (c) 1994
4 * Hewlett-Packard Company
5 *
6 * Permission to use, copy, modify, distribute and sell this software
7 * and its documentation for any purpose is hereby granted without fee,
8 * provided that the above copyright notice appear in all copies and
9 * that both that copyright notice and this permission notice appear
10 * in supporting documentation.  Hewlett-Packard Company makes no
11 * representations about the suitability of this software for any
12 * purpose.  It is provided "as is" without express or implied warranty.
13 *
14 *
15 * Copyright (c) 1996,1997
16 * Silicon Graphics Computer Systems, Inc.
17 *
18 * Permission to use, copy, modify, distribute and sell this software
19 * and its documentation for any purpose is hereby granted without fee,
20 * provided that the above copyright notice appear in all copies and
21 * that both that copyright notice and this permission notice appear
22 * in supporting documentation.  Silicon Graphics makes no
23 * representations about the suitability of this software for any
24 * purpose.  It is provided "as is" without express or implied warranty.
25 */
26
27/* NOTE: This is an internal header file, included by other STL headers.
28 *   You should not attempt to use it directly.
29 */
30
31#ifndef __SGI_STL_INTERNAL_MULTIMAP_H
32#define __SGI_STL_INTERNAL_MULTIMAP_H
33
34__STL_BEGIN_NAMESPACE
35
36#if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
37#pragma set woff 1174
38#pragma set woff 1375
39#endif
40
41#ifndef __STL_LIMITED_DEFAULT_TEMPLATES
42template <class _Key, class _Tp, class _Compare = less<_Key>,
43          class _Alloc = __STL_DEFAULT_ALLOCATOR(_Tp) >
44#else
45template <class _Key, class _Tp, class _Compare,
46          class _Alloc = __STL_DEFAULT_ALLOCATOR(_Tp) >
47#endif
48class multimap {
49public:
50
51// typedefs:
52
53  typedef _Key                  key_type;
54  typedef _Tp                   data_type;
55  typedef _Tp                   mapped_type;
56  typedef pair<const _Key, _Tp> value_type;
57  typedef _Compare              key_compare;
58
59  class value_compare : public binary_function<value_type, value_type, bool> {
60  friend class multimap<_Key,_Tp,_Compare,_Alloc>;
61  protected:
62    _Compare _M_comp;
63    value_compare(_Compare __c) : _M_comp(__c) {}
64  public:
65    bool operator()(const value_type& __x, const value_type& __y) const {
66      return _M_comp(__x.first, __y.first);
67    }
68  };
69
70private:
71  typedef _Rb_tree<key_type, value_type,
72                  _Select1st<value_type>, key_compare, _Alloc> _Rep_type;
73  _Rep_type _M_t;  // red-black tree representing multimap
74public:
75  typedef typename _Rep_type::pointer pointer;
76  typedef typename _Rep_type::const_pointer const_pointer;
77  typedef typename _Rep_type::reference reference;
78  typedef typename _Rep_type::const_reference const_reference;
79  typedef typename _Rep_type::iterator iterator;
80  typedef typename _Rep_type::const_iterator const_iterator;
81  typedef typename _Rep_type::reverse_iterator reverse_iterator;
82  typedef typename _Rep_type::const_reverse_iterator const_reverse_iterator;
83  typedef typename _Rep_type::size_type size_type;
84  typedef typename _Rep_type::difference_type difference_type;
85  typedef typename _Rep_type::allocator_type allocator_type;
86
87// allocation/deallocation
88
89  multimap() : _M_t(_Compare(), allocator_type()) { }
90  explicit multimap(const _Compare& __comp,
91                    const allocator_type& __a = allocator_type())
92    : _M_t(__comp, __a) { }
93
94#ifdef __STL_MEMBER_TEMPLATES
95  template <class _InputIterator>
96  multimap(_InputIterator __first, _InputIterator __last)
97    : _M_t(_Compare(), allocator_type())
98    { _M_t.insert_equal(__first, __last); }
99
100  template <class _InputIterator>
101  multimap(_InputIterator __first, _InputIterator __last,
102           const _Compare& __comp,
103           const allocator_type& __a = allocator_type())
104    : _M_t(__comp, __a) { _M_t.insert_equal(__first, __last); }
105#else
106  multimap(const value_type* __first, const value_type* __last)
107    : _M_t(_Compare(), allocator_type())
108    { _M_t.insert_equal(__first, __last); }
109  multimap(const value_type* __first, const value_type* __last,
110           const _Compare& __comp,
111           const allocator_type& __a = allocator_type())
112    : _M_t(__comp, __a) { _M_t.insert_equal(__first, __last); }
113
114  multimap(const_iterator __first, const_iterator __last)
115    : _M_t(_Compare(), allocator_type())
116    { _M_t.insert_equal(__first, __last); }
117  multimap(const_iterator __first, const_iterator __last,
118           const _Compare& __comp,
119           const allocator_type& __a = allocator_type())
120    : _M_t(__comp, __a) { _M_t.insert_equal(__first, __last); }
121#endif /* __STL_MEMBER_TEMPLATES */
122
123  multimap(const multimap<_Key,_Tp,_Compare,_Alloc>& __x) : _M_t(__x._M_t) { }
124  multimap<_Key,_Tp,_Compare,_Alloc>&
125  operator=(const multimap<_Key,_Tp,_Compare,_Alloc>& __x) {
126    _M_t = __x._M_t;
127    return *this;
128  }
129
130  // accessors:
131
132  key_compare key_comp() const { return _M_t.key_comp(); }
133  value_compare value_comp() const { return value_compare(_M_t.key_comp()); }
134  allocator_type get_allocator() const { return _M_t.get_allocator(); }
135
136  iterator begin() { return _M_t.begin(); }
137  const_iterator begin() const { return _M_t.begin(); }
138  iterator end() { return _M_t.end(); }
139  const_iterator end() const { return _M_t.end(); }
140  reverse_iterator rbegin() { return _M_t.rbegin(); }
141  const_reverse_iterator rbegin() const { return _M_t.rbegin(); }
142  reverse_iterator rend() { return _M_t.rend(); }
143  const_reverse_iterator rend() const { return _M_t.rend(); }
144  bool empty() const { return _M_t.empty(); }
145  size_type size() const { return _M_t.size(); }
146  size_type max_size() const { return _M_t.max_size(); }
147  void swap(multimap<_Key,_Tp,_Compare,_Alloc>& __x) { _M_t.swap(__x._M_t); }
148
149  // insert/erase
150
151  iterator insert(const value_type& __x) { return _M_t.insert_equal(__x); }
152  iterator insert(iterator __position, const value_type& __x) {
153    return _M_t.insert_equal(__position, __x);
154  }
155#ifdef __STL_MEMBER_TEMPLATES
156  template <class _InputIterator>
157  void insert(_InputIterator __first, _InputIterator __last) {
158    _M_t.insert_equal(__first, __last);
159  }
160#else
161  void insert(const value_type* __first, const value_type* __last) {
162    _M_t.insert_equal(__first, __last);
163  }
164  void insert(const_iterator __first, const_iterator __last) {
165    _M_t.insert_equal(__first, __last);
166  }
167#endif /* __STL_MEMBER_TEMPLATES */
168  void erase(iterator __position) { _M_t.erase(__position); }
169  size_type erase(const key_type& __x) { return _M_t.erase(__x); }
170  void erase(iterator __first, iterator __last)
171    { _M_t.erase(__first, __last); }
172  void clear() { _M_t.clear(); }
173
174  // multimap operations:
175
176  iterator find(const key_type& __x) { return _M_t.find(__x); }
177  const_iterator find(const key_type& __x) const { return _M_t.find(__x); }
178  size_type count(const key_type& __x) const { return _M_t.count(__x); }
179  iterator lower_bound(const key_type& __x) {return _M_t.lower_bound(__x); }
180  const_iterator lower_bound(const key_type& __x) const {
181    return _M_t.lower_bound(__x);
182  }
183  iterator upper_bound(const key_type& __x) {return _M_t.upper_bound(__x); }
184  const_iterator upper_bound(const key_type& __x) const {
185    return _M_t.upper_bound(__x);
186  }
187   pair<iterator,iterator> equal_range(const key_type& __x) {
188    return _M_t.equal_range(__x);
189  }
190  pair<const_iterator,const_iterator> equal_range(const key_type& __x) const {
191    return _M_t.equal_range(__x);
192  }
193  friend bool operator== __STL_NULL_TMPL_ARGS (const multimap&,
194                                               const multimap&);
195  friend bool operator< __STL_NULL_TMPL_ARGS (const multimap&,
196                                              const multimap&);
197};
198
199template <class _Key, class _Tp, class _Compare, class _Alloc>
200inline bool operator==(const multimap<_Key,_Tp,_Compare,_Alloc>& __x,
201                       const multimap<_Key,_Tp,_Compare,_Alloc>& __y) {
202  return __x._M_t == __y._M_t;
203}
204
205template <class _Key, class _Tp, class _Compare, class _Alloc>
206inline bool operator<(const multimap<_Key,_Tp,_Compare,_Alloc>& __x,
207                      const multimap<_Key,_Tp,_Compare,_Alloc>& __y) {
208  return __x._M_t < __y._M_t;
209}
210
211#ifdef __STL_FUNCTION_TMPL_PARTIAL_ORDER
212
213template <class _Key, class _Tp, class _Compare, class _Alloc>
214inline void swap(multimap<_Key,_Tp,_Compare,_Alloc>& __x,
215                 multimap<_Key,_Tp,_Compare,_Alloc>& __y) {
216  __x.swap(__y);
217}
218
219#endif /* __STL_FUNCTION_TMPL_PARTIAL_ORDER */
220
221#if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
222#pragma reset woff 1174
223#pragma reset woff 1375
224#endif
225
226__STL_END_NAMESPACE
227
228#endif /* __SGI_STL_INTERNAL_MULTIMAP_H */
229
230// Local Variables:
231// mode:C++
232// End:
233