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_MAP_H
32#define __SGI_STL_INTERNAL_MAP_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 map {
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
60    : public binary_function<value_type, value_type, bool> {
61  friend class map<_Key,_Tp,_Compare,_Alloc>;
62  protected :
63    _Compare _M_comp;
64    value_compare(_Compare __c) : _M_comp(__c) {}
65  public:
66    bool operator()(const value_type& __x, const value_type& __y) const {
67      return _M_comp(__x.first, __y.first);
68    }
69  };
70
71private:
72  typedef _Rb_tree<key_type, value_type,
73                   _Select1st<value_type>, key_compare, _Alloc> _Rep_type;
74  _Rep_type _M_t;  // red-black tree representing map
75public:
76  typedef typename _Rep_type::pointer pointer;
77  typedef typename _Rep_type::const_pointer const_pointer;
78  typedef typename _Rep_type::reference reference;
79  typedef typename _Rep_type::const_reference const_reference;
80  typedef typename _Rep_type::iterator iterator;
81  typedef typename _Rep_type::const_iterator const_iterator;
82  typedef typename _Rep_type::reverse_iterator reverse_iterator;
83  typedef typename _Rep_type::const_reverse_iterator const_reverse_iterator;
84  typedef typename _Rep_type::size_type size_type;
85  typedef typename _Rep_type::difference_type difference_type;
86  typedef typename _Rep_type::allocator_type allocator_type;
87
88  // allocation/deallocation
89
90  map() : _M_t(_Compare(), allocator_type()) {}
91  explicit map(const _Compare& __comp,
92               const allocator_type& __a = allocator_type())
93    : _M_t(__comp, __a) {}
94
95#ifdef __STL_MEMBER_TEMPLATES
96  template <class _InputIterator>
97  map(_InputIterator __first, _InputIterator __last)
98    : _M_t(_Compare(), allocator_type())
99    { _M_t.insert_unique(__first, __last); }
100
101  template <class _InputIterator>
102  map(_InputIterator __first, _InputIterator __last, const _Compare& __comp,
103      const allocator_type& __a = allocator_type())
104    : _M_t(__comp, __a) { _M_t.insert_unique(__first, __last); }
105#else
106  map(const value_type* __first, const value_type* __last)
107    : _M_t(_Compare(), allocator_type())
108    { _M_t.insert_unique(__first, __last); }
109
110  map(const value_type* __first,
111      const value_type* __last, const _Compare& __comp,
112      const allocator_type& __a = allocator_type())
113    : _M_t(__comp, __a) { _M_t.insert_unique(__first, __last); }
114
115  map(const_iterator __first, const_iterator __last)
116    : _M_t(_Compare(), allocator_type())
117    { _M_t.insert_unique(__first, __last); }
118
119  map(const_iterator __first, const_iterator __last, const _Compare& __comp,
120      const allocator_type& __a = allocator_type())
121    : _M_t(__comp, __a) { _M_t.insert_unique(__first, __last); }
122
123#endif /* __STL_MEMBER_TEMPLATES */
124
125  map(const map<_Key,_Tp,_Compare,_Alloc>& __x) : _M_t(__x._M_t) {}
126  map<_Key,_Tp,_Compare,_Alloc>&
127  operator=(const map<_Key, _Tp, _Compare, _Alloc>& __x)
128  {
129    _M_t = __x._M_t;
130    return *this;
131  }
132
133  // accessors:
134
135  key_compare key_comp() const { return _M_t.key_comp(); }
136  value_compare value_comp() const { return value_compare(_M_t.key_comp()); }
137  allocator_type get_allocator() const { return _M_t.get_allocator(); }
138
139  iterator begin() { return _M_t.begin(); }
140  const_iterator begin() const { return _M_t.begin(); }
141  iterator end() { return _M_t.end(); }
142  const_iterator end() const { return _M_t.end(); }
143  reverse_iterator rbegin() { return _M_t.rbegin(); }
144  const_reverse_iterator rbegin() const { return _M_t.rbegin(); }
145  reverse_iterator rend() { return _M_t.rend(); }
146  const_reverse_iterator rend() const { return _M_t.rend(); }
147  bool empty() const { return _M_t.empty(); }
148  size_type size() const { return _M_t.size(); }
149  size_type max_size() const { return _M_t.max_size(); }
150  _Tp& operator[](const key_type& __k) {
151    iterator __i = lower_bound(__k);
152    // __i->first is greater than or equivalent to __k.
153    if (__i == end() || key_comp()(__k, (*__i).first))
154      __i = insert(__i, value_type(__k, _Tp()));
155    return (*__i).second;
156  }
157  void swap(map<_Key,_Tp,_Compare,_Alloc>& __x) { _M_t.swap(__x._M_t); }
158
159  // insert/erase
160
161  pair<iterator,bool> insert(const value_type& __x)
162    { return _M_t.insert_unique(__x); }
163  iterator insert(iterator position, const value_type& __x)
164    { return _M_t.insert_unique(position, __x); }
165#ifdef __STL_MEMBER_TEMPLATES
166  template <class _InputIterator>
167  void insert(_InputIterator __first, _InputIterator __last) {
168    _M_t.insert_unique(__first, __last);
169  }
170#else
171  void insert(const value_type* __first, const value_type* __last) {
172    _M_t.insert_unique(__first, __last);
173  }
174  void insert(const_iterator __first, const_iterator __last) {
175    _M_t.insert_unique(__first, __last);
176  }
177#endif /* __STL_MEMBER_TEMPLATES */
178
179  void erase(iterator __position) { _M_t.erase(__position); }
180  size_type erase(const key_type& __x) { return _M_t.erase(__x); }
181  void erase(iterator __first, iterator __last)
182    { _M_t.erase(__first, __last); }
183  void clear() { _M_t.clear(); }
184
185  // map operations:
186
187  iterator find(const key_type& __x) { return _M_t.find(__x); }
188  const_iterator find(const key_type& __x) const { return _M_t.find(__x); }
189  size_type count(const key_type& __x) const { return _M_t.count(__x); }
190  iterator lower_bound(const key_type& __x) {return _M_t.lower_bound(__x); }
191  const_iterator lower_bound(const key_type& __x) const {
192    return _M_t.lower_bound(__x);
193  }
194  iterator upper_bound(const key_type& __x) {return _M_t.upper_bound(__x); }
195  const_iterator upper_bound(const key_type& __x) const {
196    return _M_t.upper_bound(__x);
197  }
198
199  pair<iterator,iterator> equal_range(const key_type& __x) {
200    return _M_t.equal_range(__x);
201  }
202  pair<const_iterator,const_iterator> equal_range(const key_type& __x) const {
203    return _M_t.equal_range(__x);
204  }
205  friend bool operator== __STL_NULL_TMPL_ARGS (const map&, const map&);
206  friend bool operator< __STL_NULL_TMPL_ARGS (const map&, const map&);
207};
208
209template <class _Key, class _Tp, class _Compare, class _Alloc>
210inline bool operator==(const map<_Key,_Tp,_Compare,_Alloc>& __x,
211                       const map<_Key,_Tp,_Compare,_Alloc>& __y) {
212  return __x._M_t == __y._M_t;
213}
214
215template <class _Key, class _Tp, class _Compare, class _Alloc>
216inline bool operator<(const map<_Key,_Tp,_Compare,_Alloc>& __x,
217                      const map<_Key,_Tp,_Compare,_Alloc>& __y) {
218  return __x._M_t < __y._M_t;
219}
220
221#ifdef __STL_FUNCTION_TMPL_PARTIAL_ORDER
222
223template <class _Key, class _Tp, class _Compare, class _Alloc>
224inline void swap(map<_Key,_Tp,_Compare,_Alloc>& __x,
225                 map<_Key,_Tp,_Compare,_Alloc>& __y) {
226  __x.swap(__y);
227}
228
229#endif /* __STL_FUNCTION_TMPL_PARTIAL_ORDER */
230
231#if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
232#pragma reset woff 1174
233#pragma reset woff 1375
234#endif
235
236__STL_END_NAMESPACE
237
238#endif /* __SGI_STL_INTERNAL_MAP_H */
239
240// Local Variables:
241// mode:C++
242// End:
243