1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/epoc32/include/tools/stlport/stl/_map.h Wed Mar 31 12:33:34 2010 +0100
1.3 @@ -0,0 +1,425 @@
1.4 +/*
1.5 + *
1.6 + * Copyright (c) 1994
1.7 + * Hewlett-Packard Company
1.8 + *
1.9 + * Copyright (c) 1996,1997
1.10 + * Silicon Graphics Computer Systems, Inc.
1.11 + *
1.12 + * Copyright (c) 1997
1.13 + * Moscow Center for SPARC Technology
1.14 + *
1.15 + * Copyright (c) 1999
1.16 + * Boris Fomitchev
1.17 + *
1.18 + * This material is provided "as is", with absolutely no warranty expressed
1.19 + * or implied. Any use is at your own risk.
1.20 + *
1.21 + * Permission to use or copy this software for any purpose is hereby granted
1.22 + * without fee, provided the above notices are retained on all copies.
1.23 + * Permission to modify the code and to distribute modified code is granted,
1.24 + * provided the above notices are retained, and a notice that the code was
1.25 + * modified is included with the above copyright notice.
1.26 + *
1.27 + */
1.28 +
1.29 +/* NOTE: This is an internal header file, included by other STL headers.
1.30 + * You should not attempt to use it directly.
1.31 + */
1.32 +
1.33 +#ifndef _STLP_INTERNAL_MAP_H
1.34 +#define _STLP_INTERNAL_MAP_H
1.35 +
1.36 +#ifndef _STLP_INTERNAL_TREE_H
1.37 +# include <stl/_tree.h>
1.38 +#endif
1.39 +
1.40 +_STLP_BEGIN_NAMESPACE
1.41 +
1.42 +//Specific iterator traits creation
1.43 +_STLP_CREATE_ITERATOR_TRAITS(MapTraitsT, traits)
1.44 +
1.45 +template <class _Key, class _Tp, _STLP_DFL_TMPL_PARAM(_Compare, less<_Key> ),
1.46 + _STLP_DEFAULT_PAIR_ALLOCATOR_SELECT(const _Key, _Tp) >
1.47 +class map
1.48 +#if defined (_STLP_USE_PARTIAL_SPEC_WORKAROUND)
1.49 + : public __stlport_class<map<_Key, _Tp, _Compare, _Alloc> >
1.50 +#endif
1.51 +{
1.52 + typedef map<_Key, _Tp, _Compare, _Alloc> _Self;
1.53 +public:
1.54 +
1.55 +// typedefs:
1.56 +
1.57 + typedef _Key key_type;
1.58 + typedef _Tp data_type;
1.59 + typedef _Tp mapped_type;
1.60 + typedef pair<const _Key, _Tp> value_type;
1.61 + typedef _Compare key_compare;
1.62 +
1.63 + class value_compare
1.64 + : public binary_function<value_type, value_type, bool> {
1.65 + friend class map<_Key,_Tp,_Compare,_Alloc>;
1.66 + protected :
1.67 + //c is a Standard name (23.3.1), do no make it STLport naming convention compliant.
1.68 + _Compare comp;
1.69 + value_compare(_Compare __c) : comp(__c) {}
1.70 + public:
1.71 + bool operator()(const value_type& __x, const value_type& __y) const
1.72 + { return comp(__x.first, __y.first); }
1.73 + };
1.74 +
1.75 +protected:
1.76 + typedef _STLP_PRIV _MapTraitsT<value_type> _MapTraits;
1.77 +
1.78 +public:
1.79 + //Following typedef have to be public for __move_traits specialization.
1.80 + typedef _STLP_PRIV _Rb_tree<key_type, key_compare,
1.81 + value_type, _STLP_SELECT1ST(value_type, _Key),
1.82 + _MapTraits, _Alloc> _Rep_type;
1.83 +
1.84 + typedef typename _Rep_type::pointer pointer;
1.85 + typedef typename _Rep_type::const_pointer const_pointer;
1.86 + typedef typename _Rep_type::reference reference;
1.87 + typedef typename _Rep_type::const_reference const_reference;
1.88 + typedef typename _Rep_type::iterator iterator;
1.89 + typedef typename _Rep_type::const_iterator const_iterator;
1.90 + typedef typename _Rep_type::reverse_iterator reverse_iterator;
1.91 + typedef typename _Rep_type::const_reverse_iterator const_reverse_iterator;
1.92 + typedef typename _Rep_type::size_type size_type;
1.93 + typedef typename _Rep_type::difference_type difference_type;
1.94 + typedef typename _Rep_type::allocator_type allocator_type;
1.95 +
1.96 +private:
1.97 + _Rep_type _M_t; // red-black tree representing map
1.98 + _STLP_KEY_TYPE_FOR_CONT_EXT(key_type)
1.99 +
1.100 +public:
1.101 + // allocation/deallocation
1.102 + map() : _M_t(_Compare(), allocator_type()) {}
1.103 +#if !defined (_STLP_DONT_SUP_DFLT_PARAM)
1.104 + explicit map(const _Compare& __comp,
1.105 + const allocator_type& __a = allocator_type())
1.106 +#else
1.107 + explicit map(const _Compare& __comp)
1.108 + : _M_t(__comp, allocator_type()) {}
1.109 + explicit map(const _Compare& __comp, const allocator_type& __a)
1.110 +#endif
1.111 + : _M_t(__comp, __a) {}
1.112 +
1.113 +#if defined (_STLP_MEMBER_TEMPLATES)
1.114 + template <class _InputIterator>
1.115 + map(_InputIterator __first, _InputIterator __last)
1.116 + : _M_t(_Compare(), allocator_type())
1.117 + { _M_t.insert_unique(__first, __last); }
1.118 +
1.119 + template <class _InputIterator>
1.120 + map(_InputIterator __first, _InputIterator __last, const _Compare& __comp,
1.121 + const allocator_type& __a _STLP_ALLOCATOR_TYPE_DFL)
1.122 + : _M_t(__comp, __a) { _M_t.insert_unique(__first, __last); }
1.123 +
1.124 +# if defined (_STLP_NEEDS_EXTRA_TEMPLATE_CONSTRUCTORS)
1.125 + template <class _InputIterator>
1.126 + map(_InputIterator __first, _InputIterator __last, const _Compare& __comp)
1.127 + : _M_t(__comp, allocator_type()) { _M_t.insert_unique(__first, __last); }
1.128 +# endif
1.129 +
1.130 +#else
1.131 + map(const value_type* __first, const value_type* __last)
1.132 + : _M_t(_Compare(), allocator_type())
1.133 + { _M_t.insert_unique(__first, __last); }
1.134 +
1.135 + map(const value_type* __first,
1.136 + const value_type* __last, const _Compare& __comp,
1.137 + const allocator_type& __a = allocator_type())
1.138 + : _M_t(__comp, __a) { _M_t.insert_unique(__first, __last); }
1.139 +
1.140 + map(const_iterator __first, const_iterator __last)
1.141 + : _M_t(_Compare(), allocator_type())
1.142 + { _M_t.insert_unique(__first, __last); }
1.143 +
1.144 + map(const_iterator __first, const_iterator __last, const _Compare& __comp,
1.145 + const allocator_type& __a = allocator_type())
1.146 + : _M_t(__comp, __a) { _M_t.insert_unique(__first, __last); }
1.147 +#endif /* _STLP_MEMBER_TEMPLATES */
1.148 +
1.149 + map(const _Self& __x) : _M_t(__x._M_t) {}
1.150 +
1.151 + map(__move_source<_Self> src)
1.152 + : _M_t(__move_source<_Rep_type>(src.get()._M_t)) {}
1.153 +
1.154 + _Self& operator=(const _Self& __x) {
1.155 + _M_t = __x._M_t;
1.156 + return *this;
1.157 + }
1.158 +
1.159 + // accessors:
1.160 + key_compare key_comp() const { return _M_t.key_comp(); }
1.161 + value_compare value_comp() const { return value_compare(_M_t.key_comp()); }
1.162 + allocator_type get_allocator() const { return _M_t.get_allocator(); }
1.163 +
1.164 + iterator begin() { return _M_t.begin(); }
1.165 + const_iterator begin() const { return _M_t.begin(); }
1.166 + iterator end() { return _M_t.end(); }
1.167 + const_iterator end() const { return _M_t.end(); }
1.168 + reverse_iterator rbegin() { return _M_t.rbegin(); }
1.169 + const_reverse_iterator rbegin() const { return _M_t.rbegin(); }
1.170 + reverse_iterator rend() { return _M_t.rend(); }
1.171 + const_reverse_iterator rend() const { return _M_t.rend(); }
1.172 + bool empty() const { return _M_t.empty(); }
1.173 + size_type size() const { return _M_t.size(); }
1.174 + size_type max_size() const { return _M_t.max_size(); }
1.175 + _STLP_TEMPLATE_FOR_CONT_EXT
1.176 + _Tp& operator[](const _KT& __k) {
1.177 + iterator __i = lower_bound(__k);
1.178 + // __i->first is greater than or equivalent to __k.
1.179 + if (__i == end() || key_comp()(__k, (*__i).first))
1.180 + __i = insert(__i, value_type(__k, _STLP_DEFAULT_CONSTRUCTED(_Tp)));
1.181 + return (*__i).second;
1.182 + }
1.183 + void swap(_Self& __x) { _M_t.swap(__x._M_t); }
1.184 +
1.185 + // insert/erase
1.186 + pair<iterator,bool> insert(const value_type& __x)
1.187 + { return _M_t.insert_unique(__x); }
1.188 + iterator insert(iterator __pos, const value_type& __x)
1.189 + { return _M_t.insert_unique(__pos, __x); }
1.190 +#ifdef _STLP_MEMBER_TEMPLATES
1.191 + template <class _InputIterator>
1.192 + void insert(_InputIterator __first, _InputIterator __last)
1.193 + { _M_t.insert_unique(__first, __last); }
1.194 +#else
1.195 + void insert(const value_type* __first, const value_type* __last)
1.196 + { _M_t.insert_unique(__first, __last); }
1.197 + void insert(const_iterator __first, const_iterator __last)
1.198 + { _M_t.insert_unique(__first, __last); }
1.199 +#endif /* _STLP_MEMBER_TEMPLATES */
1.200 +
1.201 + void erase(iterator __pos) { _M_t.erase(__pos); }
1.202 + size_type erase(const key_type& __x) { return _M_t.erase_unique(__x); }
1.203 + void erase(iterator __first, iterator __last) { _M_t.erase(__first, __last); }
1.204 + void clear() { _M_t.clear(); }
1.205 +
1.206 + // map operations:
1.207 + _STLP_TEMPLATE_FOR_CONT_EXT
1.208 + iterator find(const _KT& __x) { return _M_t.find(__x); }
1.209 + _STLP_TEMPLATE_FOR_CONT_EXT
1.210 + const_iterator find(const _KT& __x) const { return _M_t.find(__x); }
1.211 + _STLP_TEMPLATE_FOR_CONT_EXT
1.212 + size_type count(const _KT& __x) const { return _M_t.find(__x) == _M_t.end() ? 0 : 1; }
1.213 + _STLP_TEMPLATE_FOR_CONT_EXT
1.214 + iterator lower_bound(const _KT& __x) { return _M_t.lower_bound(__x); }
1.215 + _STLP_TEMPLATE_FOR_CONT_EXT
1.216 + const_iterator lower_bound(const _KT& __x) const { return _M_t.lower_bound(__x); }
1.217 + _STLP_TEMPLATE_FOR_CONT_EXT
1.218 + iterator upper_bound(const _KT& __x) { return _M_t.upper_bound(__x); }
1.219 + _STLP_TEMPLATE_FOR_CONT_EXT
1.220 + const_iterator upper_bound(const _KT& __x) const { return _M_t.upper_bound(__x); }
1.221 +
1.222 + _STLP_TEMPLATE_FOR_CONT_EXT
1.223 + pair<iterator,iterator> equal_range(const _KT& __x)
1.224 + { return _M_t.equal_range_unique(__x); }
1.225 + _STLP_TEMPLATE_FOR_CONT_EXT
1.226 + pair<const_iterator,const_iterator> equal_range(const _KT& __x) const
1.227 + { return _M_t.equal_range_unique(__x); }
1.228 +};
1.229 +
1.230 +//Specific iterator traits creation
1.231 +_STLP_CREATE_ITERATOR_TRAITS(MultimapTraitsT, traits)
1.232 +
1.233 +template <class _Key, class _Tp, _STLP_DFL_TMPL_PARAM(_Compare, less<_Key> ),
1.234 + _STLP_DEFAULT_PAIR_ALLOCATOR_SELECT(const _Key, _Tp) >
1.235 +class multimap
1.236 +#if defined (_STLP_USE_PARTIAL_SPEC_WORKAROUND)
1.237 + : public __stlport_class<multimap<_Key, _Tp, _Compare, _Alloc> >
1.238 +#endif
1.239 +{
1.240 + typedef multimap<_Key, _Tp, _Compare, _Alloc> _Self;
1.241 +public:
1.242 +
1.243 +// typedefs:
1.244 +
1.245 + typedef _Key key_type;
1.246 + typedef _Tp data_type;
1.247 + typedef _Tp mapped_type;
1.248 + typedef pair<const _Key, _Tp> value_type;
1.249 + typedef _Compare key_compare;
1.250 +
1.251 + class value_compare : public binary_function<value_type, value_type, bool> {
1.252 + friend class multimap<_Key,_Tp,_Compare,_Alloc>;
1.253 + protected:
1.254 + //comp is a Standard name (23.3.2), do no make it STLport naming convention compliant.
1.255 + _Compare comp;
1.256 + value_compare(_Compare __c) : comp(__c) {}
1.257 + public:
1.258 + bool operator()(const value_type& __x, const value_type& __y) const
1.259 + { return comp(__x.first, __y.first); }
1.260 + };
1.261 +
1.262 +protected:
1.263 + //Specific iterator traits creation
1.264 + typedef _STLP_PRIV _MultimapTraitsT<value_type> _MultimapTraits;
1.265 +
1.266 +public:
1.267 + //Following typedef have to be public for __move_traits specialization.
1.268 + typedef _STLP_PRIV _Rb_tree<key_type, key_compare,
1.269 + value_type, _STLP_SELECT1ST(value_type, _Key),
1.270 + _MultimapTraits, _Alloc> _Rep_type;
1.271 +
1.272 + typedef typename _Rep_type::pointer pointer;
1.273 + typedef typename _Rep_type::const_pointer const_pointer;
1.274 + typedef typename _Rep_type::reference reference;
1.275 + typedef typename _Rep_type::const_reference const_reference;
1.276 + typedef typename _Rep_type::iterator iterator;
1.277 + typedef typename _Rep_type::const_iterator const_iterator;
1.278 + typedef typename _Rep_type::reverse_iterator reverse_iterator;
1.279 + typedef typename _Rep_type::const_reverse_iterator const_reverse_iterator;
1.280 + typedef typename _Rep_type::size_type size_type;
1.281 + typedef typename _Rep_type::difference_type difference_type;
1.282 + typedef typename _Rep_type::allocator_type allocator_type;
1.283 +
1.284 +private:
1.285 + _Rep_type _M_t; // red-black tree representing multimap
1.286 + _STLP_KEY_TYPE_FOR_CONT_EXT(key_type)
1.287 +
1.288 +public:
1.289 + // allocation/deallocation
1.290 + multimap() : _M_t(_Compare(), allocator_type()) { }
1.291 + explicit multimap(const _Compare& __comp,
1.292 + const allocator_type& __a = allocator_type())
1.293 + : _M_t(__comp, __a) { }
1.294 +
1.295 +#ifdef _STLP_MEMBER_TEMPLATES
1.296 + template <class _InputIterator>
1.297 + multimap(_InputIterator __first, _InputIterator __last)
1.298 + : _M_t(_Compare(), allocator_type())
1.299 + { _M_t.insert_equal(__first, __last); }
1.300 +# ifdef _STLP_NEEDS_EXTRA_TEMPLATE_CONSTRUCTORS
1.301 + template <class _InputIterator>
1.302 + multimap(_InputIterator __first, _InputIterator __last,
1.303 + const _Compare& __comp)
1.304 + : _M_t(__comp, allocator_type()) { _M_t.insert_equal(__first, __last); }
1.305 +# endif
1.306 + template <class _InputIterator>
1.307 + multimap(_InputIterator __first, _InputIterator __last,
1.308 + const _Compare& __comp,
1.309 + const allocator_type& __a _STLP_ALLOCATOR_TYPE_DFL)
1.310 + : _M_t(__comp, __a) { _M_t.insert_equal(__first, __last); }
1.311 +#else
1.312 + multimap(const value_type* __first, const value_type* __last)
1.313 + : _M_t(_Compare(), allocator_type())
1.314 + { _M_t.insert_equal(__first, __last); }
1.315 + multimap(const value_type* __first, const value_type* __last,
1.316 + const _Compare& __comp,
1.317 + const allocator_type& __a = allocator_type())
1.318 + : _M_t(__comp, __a) { _M_t.insert_equal(__first, __last); }
1.319 +
1.320 + multimap(const_iterator __first, const_iterator __last)
1.321 + : _M_t(_Compare(), allocator_type())
1.322 + { _M_t.insert_equal(__first, __last); }
1.323 + multimap(const_iterator __first, const_iterator __last,
1.324 + const _Compare& __comp,
1.325 + const allocator_type& __a = allocator_type())
1.326 + : _M_t(__comp, __a) { _M_t.insert_equal(__first, __last); }
1.327 +#endif /* _STLP_MEMBER_TEMPLATES */
1.328 +
1.329 + multimap(const _Self& __x) : _M_t(__x._M_t) {}
1.330 +
1.331 + multimap(__move_source<_Self> src)
1.332 + : _M_t(__move_source<_Rep_type>(src.get()._M_t)) {}
1.333 +
1.334 + _Self& operator=(const _Self& __x) {
1.335 + _M_t = __x._M_t;
1.336 + return *this;
1.337 + }
1.338 +
1.339 + // accessors:
1.340 +
1.341 + key_compare key_comp() const { return _M_t.key_comp(); }
1.342 + value_compare value_comp() const { return value_compare(_M_t.key_comp()); }
1.343 + allocator_type get_allocator() const { return _M_t.get_allocator(); }
1.344 +
1.345 + iterator begin() { return _M_t.begin(); }
1.346 + const_iterator begin() const { return _M_t.begin(); }
1.347 + iterator end() { return _M_t.end(); }
1.348 + const_iterator end() const { return _M_t.end(); }
1.349 + reverse_iterator rbegin() { return _M_t.rbegin(); }
1.350 + const_reverse_iterator rbegin() const { return _M_t.rbegin(); }
1.351 + reverse_iterator rend() { return _M_t.rend(); }
1.352 + const_reverse_iterator rend() const { return _M_t.rend(); }
1.353 + bool empty() const { return _M_t.empty(); }
1.354 + size_type size() const { return _M_t.size(); }
1.355 + size_type max_size() const { return _M_t.max_size(); }
1.356 + void swap(_Self& __x) { _M_t.swap(__x._M_t); }
1.357 +
1.358 + // insert/erase
1.359 + iterator insert(const value_type& __x) { return _M_t.insert_equal(__x); }
1.360 + iterator insert(iterator __pos, const value_type& __x) { return _M_t.insert_equal(__pos, __x); }
1.361 +#if defined (_STLP_MEMBER_TEMPLATES)
1.362 + template <class _InputIterator>
1.363 + void insert(_InputIterator __first, _InputIterator __last)
1.364 + { _M_t.insert_equal(__first, __last); }
1.365 +#else
1.366 + void insert(const value_type* __first, const value_type* __last)
1.367 + { _M_t.insert_equal(__first, __last); }
1.368 + void insert(const_iterator __first, const_iterator __last)
1.369 + { _M_t.insert_equal(__first, __last); }
1.370 +#endif /* _STLP_MEMBER_TEMPLATES */
1.371 + void erase(iterator __pos) { _M_t.erase(__pos); }
1.372 + size_type erase(const key_type& __x) { return _M_t.erase(__x); }
1.373 + void erase(iterator __first, iterator __last) { _M_t.erase(__first, __last); }
1.374 + void clear() { _M_t.clear(); }
1.375 +
1.376 + // multimap operations:
1.377 +
1.378 + _STLP_TEMPLATE_FOR_CONT_EXT
1.379 + iterator find(const _KT& __x) { return _M_t.find(__x); }
1.380 + _STLP_TEMPLATE_FOR_CONT_EXT
1.381 + const_iterator find(const _KT& __x) const { return _M_t.find(__x); }
1.382 + _STLP_TEMPLATE_FOR_CONT_EXT
1.383 + size_type count(const _KT& __x) const { return _M_t.count(__x); }
1.384 + _STLP_TEMPLATE_FOR_CONT_EXT
1.385 + iterator lower_bound(const _KT& __x) { return _M_t.lower_bound(__x); }
1.386 + _STLP_TEMPLATE_FOR_CONT_EXT
1.387 + const_iterator lower_bound(const _KT& __x) const { return _M_t.lower_bound(__x); }
1.388 + _STLP_TEMPLATE_FOR_CONT_EXT
1.389 + iterator upper_bound(const _KT& __x) { return _M_t.upper_bound(__x); }
1.390 + _STLP_TEMPLATE_FOR_CONT_EXT
1.391 + const_iterator upper_bound(const _KT& __x) const { return _M_t.upper_bound(__x); }
1.392 + _STLP_TEMPLATE_FOR_CONT_EXT
1.393 + pair<iterator,iterator> equal_range(const _KT& __x)
1.394 + { return _M_t.equal_range(__x); }
1.395 + _STLP_TEMPLATE_FOR_CONT_EXT
1.396 + pair<const_iterator,const_iterator> equal_range(const _KT& __x) const
1.397 + { return _M_t.equal_range(__x); }
1.398 +};
1.399 +
1.400 +#define _STLP_TEMPLATE_HEADER template <class _Key, class _Tp, class _Compare, class _Alloc>
1.401 +#define _STLP_TEMPLATE_CONTAINER map<_Key,_Tp,_Compare,_Alloc>
1.402 +#include <stl/_relops_cont.h>
1.403 +#undef _STLP_TEMPLATE_CONTAINER
1.404 +#define _STLP_TEMPLATE_CONTAINER multimap<_Key,_Tp,_Compare,_Alloc>
1.405 +#include <stl/_relops_cont.h>
1.406 +#undef _STLP_TEMPLATE_CONTAINER
1.407 +#undef _STLP_TEMPLATE_HEADER
1.408 +
1.409 +#if defined (_STLP_CLASS_PARTIAL_SPECIALIZATION)
1.410 +template <class _Key, class _Tp, class _Compare, class _Alloc>
1.411 +struct __move_traits<map<_Key,_Tp,_Compare,_Alloc> > :
1.412 + _STLP_PRIV __move_traits_aux<typename map<_Key,_Tp,_Compare,_Alloc>::_Rep_type>
1.413 +{};
1.414 +
1.415 +template <class _Key, class _Tp, class _Compare, class _Alloc>
1.416 +struct __move_traits<multimap<_Key,_Tp,_Compare,_Alloc> > :
1.417 + _STLP_PRIV __move_traits_aux<typename multimap<_Key,_Tp,_Compare,_Alloc>::_Rep_type>
1.418 +{};
1.419 +#endif
1.420 +
1.421 +_STLP_END_NAMESPACE
1.422 +
1.423 +#endif /* _STLP_INTERNAL_MAP_H */
1.424 +
1.425 +// Local Variables:
1.426 +// mode:C++
1.427 +// End:
1.428 +