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