lib/3rdparty/stlport/stlport/stl/_set.h

   1 /*
   2  *
   3  * Copyright (c) 1994
   4  * Hewlett-Packard Company
   5  *
   6  * Copyright (c) 1996,1997
   7  * Silicon Graphics Computer Systems, Inc.
   8  *
   9  * Copyright (c) 1997
  10  * Moscow Center for SPARC Technology
  11  *
  12  * Copyright (c) 1999
  13  * Boris Fomitchev
  14  *
  15  * This material is provided "as is", with absolutely no warranty expressed
  16  * or implied. Any use is at your own risk.
  17  *
  18  * Permission to use or copy this software for any purpose is hereby granted
  19  * without fee, provided the above notices are retained on all copies.
  20  * Permission to modify the code and to distribute modified code is granted,
  21  * provided the above notices are retained, and a notice that the code was
  22  * modified is included with the above copyright notice.
  23  *
  24  */
  25
  26 /* NOTE: This is an internal header file, included by other STL headers.
  27  *   You should not attempt to use it directly.
  28  */
  29
  30 #ifndef _STLP_INTERNAL_SET_H
  31 #define _STLP_INTERNAL_SET_H
  32
  33 #ifndef _STLP_INTERNAL_TREE_H
  34 #  include <stl/_tree.h>
  35 #endif
  36
  37 #if !defined (_STLP_USE_PTR_SPECIALIZATIONS)
  38
  39 _STLP_BEGIN_NAMESPACE
  40
  41 //Specific iterator traits creation
  42 _STLP_CREATE_ITERATOR_TRAITS(SetTraitsT, Const_traits)
  43
  44 template <class _Key, _STLP_DFL_TMPL_PARAM(_Compare, less<_Key>),
  45                       _STLP_DFL_TMPL_PARAM(_Alloc, allocator<_Key>) >
  46 class set
  47 #if defined (_STLP_USE_PARTIAL_SPEC_WORKAROUND)
  48           : public __stlport_class<set<_Key, _Compare, _Alloc> >
  49 #endif
  50 {
  51   typedef set<_Key, _Compare, _Alloc> _Self;
  52 public:
  53 // typedefs:
  54   typedef _Key     key_type;
  55   typedef _Key     value_type;
  56   typedef _Compare key_compare;
  57   typedef _Compare value_compare;
  58
  59 private:
  60   //Specific iterator traits creation
  61   typedef _STLP_PRIV _SetTraitsT<value_type> _SetTraits;
  62
  63 public:
  64   //Following typedef have to be public for __move_traits specialization.
  65   typedef _STLP_PRIV _Rb_tree<key_type, key_compare,
  66                               value_type, _STLP_PRIV _Identity<value_type>,
  67                               _SetTraits, _Alloc> _Rep_type;
  68
  69   typedef typename _Rep_type::pointer pointer;
  70   typedef typename _Rep_type::const_pointer const_pointer;
  71   typedef typename _Rep_type::reference reference;
  72   typedef typename _Rep_type::const_reference const_reference;
  73   typedef typename _Rep_type::iterator iterator;
  74   typedef typename _Rep_type::const_iterator const_iterator;
  75   typedef typename _Rep_type::reverse_iterator reverse_iterator;
  76   typedef typename _Rep_type::const_reverse_iterator const_reverse_iterator;
  77   typedef typename _Rep_type::size_type size_type;
  78   typedef typename _Rep_type::difference_type difference_type;
  79   typedef typename _Rep_type::allocator_type allocator_type;
  80
  81 private:
  82   _Rep_type _M_t;  // red-black tree representing set
  83   _STLP_KEY_TYPE_FOR_CONT_EXT(key_type)
  84
  85 public:
  86
  87   // allocation/deallocation
  88 #if !defined (_STLP_DONT_SUP_DFLT_PARAM)
  89   explicit set(const _Compare& __comp = _Compare(),
  90                const allocator_type& __a = allocator_type())
  91 #else
  92   set()
  93     : _M_t(_Compare(), allocator_type()) {}
  94   explicit set(const _Compare& __comp)
  95     : _M_t(__comp, allocator_type()) {}
  96   set(const _Compare& __comp, const allocator_type& __a)
  97 #endif
  98     : _M_t(__comp, __a) {}
  99
 100 #if defined (_STLP_MEMBER_TEMPLATES)
 101   template <class _InputIterator>
 102   set(_InputIterator __first, _InputIterator __last)
 103     : _M_t(_Compare(), allocator_type())
 104     { _M_t.insert_unique(__first, __last); }
 105
 106 #  if defined (_STLP_NEEDS_EXTRA_TEMPLATE_CONSTRUCTORS)
 107   template <class _InputIterator>
 108   set(_InputIterator __first, _InputIterator __last, const _Compare& __comp)
 109     : _M_t(__comp, allocator_type()) { _M_t.insert_unique(__first, __last); }
 110 #  endif
 111   template <class _InputIterator>
 112   set(_InputIterator __first, _InputIterator __last, const _Compare& __comp,
 113       const allocator_type& __a _STLP_ALLOCATOR_TYPE_DFL)
 114     : _M_t(__comp, __a) { _M_t.insert_unique(__first, __last); }
 115 #else
 116   set(const value_type* __first, const value_type* __last)
 117     : _M_t(_Compare(), allocator_type())
 118     { _M_t.insert_unique(__first, __last); }
 119
 120   set(const value_type* __first,
 121       const value_type* __last, const _Compare& __comp,
 122       const allocator_type& __a = allocator_type())
 123     : _M_t(__comp, __a) { _M_t.insert_unique(__first, __last); }
 124
 125   set(const_iterator __first, const_iterator __last)
 126     : _M_t(_Compare(), allocator_type())
 127     { _M_t.insert_unique(__first, __last); }
 128
 129   set(const_iterator __first, const_iterator __last, const _Compare& __comp,
 130       const allocator_type& __a = allocator_type())
 131     : _M_t(__comp, __a) { _M_t.insert_unique(__first, __last); }
 132 #endif /* _STLP_MEMBER_TEMPLATES */
 133
 134   set(const _Self& __x) : _M_t(__x._M_t) {}
 135
 136 #if !defined (_STLP_NO_MOVE_SEMANTIC)
 137   set(__move_source<_Self> src)
 138     : _M_t(__move_source<_Rep_type>(src.get()._M_t)) {}
 139 #endif
 140
 141   _Self& operator=(const _Self& __x) {
 142     _M_t = __x._M_t;
 143     return *this;
 144   }
 145
 146   // accessors:
 147   key_compare key_comp() const { return _M_t.key_comp(); }
 148   value_compare value_comp() const { return _M_t.key_comp(); }
 149   allocator_type get_allocator() const { return _M_t.get_allocator(); }
 150
 151   iterator begin() { return _M_t.begin(); }
 152   iterator end() { return _M_t.end(); }
 153   const_iterator begin() const { return _M_t.begin(); }
 154   const_iterator end() const { return _M_t.end(); }
 155   reverse_iterator rbegin() { return _M_t.rbegin(); }
 156   reverse_iterator rend() { return _M_t.rend(); }
 157   const_reverse_iterator rbegin() const { return _M_t.rbegin(); }
 158   const_reverse_iterator rend() const { return _M_t.rend(); }
 159   bool empty() const { return _M_t.empty(); }
 160   size_type size() const { return _M_t.size(); }
 161   size_type max_size() const { return _M_t.max_size(); }
 162   void swap(_Self& __x) { _M_t.swap(__x._M_t); }
 163 #if defined (_STLP_USE_PARTIAL_SPEC_WORKAROUND) && !defined (_STLP_FUNCTION_TMPL_PARTIAL_ORDER)
 164   void _M_swap_workaround(_Self& __x) { swap(__x); }
 165 #endif
 166
 167   // insert/erase
 168   pair<iterator,bool> insert(const value_type& __x)
 169   { return _M_t.insert_unique(__x); }
 170   iterator insert(iterator __pos, const value_type& __x)
 171   { return _M_t.insert_unique( __pos , __x); }
 172 #if defined (_STLP_MEMBER_TEMPLATES)
 173   template <class _InputIterator>
 174   void insert(_InputIterator __first, _InputIterator __last)
 175   { _M_t.insert_unique(__first, __last); }
 176 #else
 177   void insert(const_iterator __first, const_iterator __last)
 178   { _M_t.insert_unique(__first, __last); }
 179   void insert(const value_type* __first, const value_type* __last)
 180   { _M_t.insert_unique(__first, __last); }
 181 #endif /* _STLP_MEMBER_TEMPLATES */
 182   void erase(iterator __pos) { _M_t.erase( __pos ); }
 183   size_type erase(const key_type& __x) { return _M_t.erase_unique(__x); }
 184   void erase(iterator __first, iterator __last) { _M_t.erase(__first, __last ); }
 185   void clear() { _M_t.clear(); }
 186
 187   // set operations:
 188   _STLP_TEMPLATE_FOR_CONT_EXT
 189   const_iterator find(const _KT& __x) const { return _M_t.find(__x); }
 190   _STLP_TEMPLATE_FOR_CONT_EXT
 191   iterator find(const _KT& __x) { return _M_t.find(__x); }
 192   _STLP_TEMPLATE_FOR_CONT_EXT
 193   size_type count(const _KT& __x) const
 194   { return _M_t.find(__x) == _M_t.end() ? 0 : 1 ; }
 195   _STLP_TEMPLATE_FOR_CONT_EXT
 196   iterator lower_bound(const _KT& __x) { return _M_t.lower_bound(__x); }
 197   _STLP_TEMPLATE_FOR_CONT_EXT
 198   const_iterator lower_bound(const _KT& __x) const { return _M_t.lower_bound(__x); }
 199   _STLP_TEMPLATE_FOR_CONT_EXT
 200   iterator upper_bound(const _KT& __x) { return _M_t.upper_bound(__x); }
 201   _STLP_TEMPLATE_FOR_CONT_EXT
 202   const_iterator upper_bound(const _KT& __x) const { return _M_t.upper_bound(__x); }
 203   _STLP_TEMPLATE_FOR_CONT_EXT
 204   pair<iterator, iterator> equal_range(const _KT& __x)
 205   { return _M_t.equal_range_unique(__x); }
 206   _STLP_TEMPLATE_FOR_CONT_EXT
 207   pair<const_iterator, const_iterator> equal_range(const _KT& __x) const
 208   { return _M_t.equal_range_unique(__x); }
 209 };
 210
 211 //Specific iterator traits creation
 212 _STLP_CREATE_ITERATOR_TRAITS(MultisetTraitsT, Const_traits)
 213
 214 template <class _Key, _STLP_DFL_TMPL_PARAM(_Compare, less<_Key>),
 215                       _STLP_DFL_TMPL_PARAM(_Alloc, allocator<_Key>) >
 216 class multiset
 217 #if defined (_STLP_USE_PARTIAL_SPEC_WORKAROUND)
 218                : public __stlport_class<multiset<_Key, _Compare, _Alloc> >
 219 #endif
 220 {
 221   typedef multiset<_Key, _Compare, _Alloc> _Self;
 222 public:
 223   // typedefs:
 224
 225   typedef _Key     key_type;
 226   typedef _Key     value_type;
 227   typedef _Compare key_compare;
 228   typedef _Compare value_compare;
 229
 230 private:
 231   //Specific iterator traits creation
 232   typedef _STLP_PRIV _MultisetTraitsT<value_type> _MultisetTraits;
 233
 234 public:
 235   //Following typedef have to be public for __move_traits specialization.
 236   typedef _STLP_PRIV _Rb_tree<key_type, key_compare,
 237                               value_type, _STLP_PRIV _Identity<value_type>,
 238                               _MultisetTraits, _Alloc> _Rep_type;
 239
 240   typedef typename _Rep_type::pointer pointer;
 241   typedef typename _Rep_type::const_pointer const_pointer;
 242   typedef typename _Rep_type::reference reference;
 243   typedef typename _Rep_type::const_reference const_reference;
 244   typedef typename _Rep_type::iterator iterator;
 245   typedef typename _Rep_type::const_iterator const_iterator;
 246   typedef typename _Rep_type::reverse_iterator reverse_iterator;
 247   typedef typename _Rep_type::const_reverse_iterator const_reverse_iterator;
 248   typedef typename _Rep_type::size_type size_type;
 249   typedef typename _Rep_type::difference_type difference_type;
 250   typedef typename _Rep_type::allocator_type allocator_type;
 251
 252 private:
 253   _Rep_type _M_t;  // red-black tree representing multiset
 254   _STLP_KEY_TYPE_FOR_CONT_EXT(key_type)
 255
 256 public:
 257 #if !defined (_STLP_DONT_SUP_DFLT_PARAM)
 258   explicit multiset(const _Compare& __comp = _Compare(),
 259                     const allocator_type& __a = allocator_type())
 260 #else
 261   multiset()
 262     : _M_t(_Compare(), allocator_type()) {}
 263   explicit multiset(const _Compare& __comp)
 264     : _M_t(__comp, allocator_type()) {}
 265   multiset(const _Compare& __comp, const allocator_type& __a)
 266 #endif
 267     : _M_t(__comp, __a) {}
 268
 269 #if defined (_STLP_MEMBER_TEMPLATES)
 270   template <class _InputIterator>
 271   multiset(_InputIterator __first, _InputIterator __last)
 272     : _M_t(_Compare(), allocator_type())
 273     { _M_t.insert_equal(__first, __last); }
 274
 275   template <class _InputIterator>
 276   multiset(_InputIterator __first, _InputIterator __last,
 277            const _Compare& __comp,
 278            const allocator_type& __a _STLP_ALLOCATOR_TYPE_DFL)
 279     : _M_t(__comp, __a) { _M_t.insert_equal(__first, __last); }
 280 #  if defined (_STLP_NEEDS_EXTRA_TEMPLATE_CONSTRUCTORS)
 281   template <class _InputIterator>
 282   multiset(_InputIterator __first, _InputIterator __last,
 283            const _Compare& __comp)
 284     : _M_t(__comp, allocator_type()) { _M_t.insert_equal(__first, __last); }
 285 #  endif
 286 #else
 287   multiset(const value_type* __first, const value_type* __last)
 288     : _M_t(_Compare(), allocator_type())
 289     { _M_t.insert_equal(__first, __last); }
 290
 291   multiset(const value_type* __first, const value_type* __last,
 292            const _Compare& __comp,
 293            const allocator_type& __a = allocator_type())
 294     : _M_t(__comp, __a) { _M_t.insert_equal(__first, __last); }
 295
 296   multiset(const_iterator __first, const_iterator __last)
 297     : _M_t(_Compare(), allocator_type())
 298     { _M_t.insert_equal(__first, __last); }
 299
 300   multiset(const_iterator __first, const_iterator __last,
 301            const _Compare& __comp,
 302            const allocator_type& __a = allocator_type())
 303     : _M_t(__comp, __a) { _M_t.insert_equal(__first, __last); }
 304 #endif /* _STLP_MEMBER_TEMPLATES */
 305
 306   multiset(const _Self& __x) : _M_t(__x._M_t) {}
 307   _Self& operator=(const _Self& __x) {
 308     _M_t = __x._M_t;
 309     return *this;
 310   }
 311
 312 #if !defined (_STLP_NO_MOVE_SEMANTIC)
 313   multiset(__move_source<_Self> src)
 314     : _M_t(__move_source<_Rep_type>(src.get()._M_t)) {}
 315 #endif
 316
 317   // accessors:
 318   key_compare key_comp() const { return _M_t.key_comp(); }
 319   value_compare value_comp() const { return _M_t.key_comp(); }
 320   allocator_type get_allocator() const { return _M_t.get_allocator(); }
 321
 322   iterator begin() { return _M_t.begin(); }
 323   iterator end() { return _M_t.end(); }
 324   const_iterator begin() const { return _M_t.begin(); }
 325   const_iterator end() const { return _M_t.end(); }
 326   reverse_iterator rbegin() { return _M_t.rbegin(); }
 327   reverse_iterator rend() { return _M_t.rend(); }
 328   const_reverse_iterator rbegin() const { return _M_t.rbegin(); }
 329   const_reverse_iterator rend() const { return _M_t.rend(); }
 330   bool empty() const { return _M_t.empty(); }
 331   size_type size() const { return _M_t.size(); }
 332   size_type max_size() const { return _M_t.max_size(); }
 333   void swap(_Self& __x) { _M_t.swap(__x._M_t); }
 334 #if defined (_STLP_USE_PARTIAL_SPEC_WORKAROUND) && !defined (_STLP_FUNCTION_TMPL_PARTIAL_ORDER)
 335   void _M_swap_workaround(_Self& __x) { swap(__x); }
 336 #endif
 337
 338   // insert/erase
 339   iterator insert(const value_type& __x)
 340   { return _M_t.insert_equal(__x); }
 341   iterator insert(iterator __pos, const value_type& __x)
 342   { return _M_t.insert_equal(__pos, __x); }
 343
 344 #if defined (_STLP_MEMBER_TEMPLATES)
 345   template <class _InputIterator>
 346   void insert(_InputIterator __first, _InputIterator __last)
 347   { _M_t.insert_equal(__first, __last); }
 348 #else
 349   void insert(const value_type* __first, const value_type* __last)
 350   { _M_t.insert_equal(__first, __last); }
 351   void insert(const_iterator __first, const_iterator __last)
 352   { _M_t.insert_equal(__first, __last); }
 353 #endif /* _STLP_MEMBER_TEMPLATES */
 354   void erase(iterator __pos) { _M_t.erase( __pos ); }
 355   size_type erase(const key_type& __x) { return _M_t.erase(__x); }
 356   void erase(iterator __first, iterator __last) { _M_t.erase( __first, __last ); }
 357   void clear() { _M_t.clear(); }
 358
 359   // multiset operations:
 360   _STLP_TEMPLATE_FOR_CONT_EXT
 361   iterator find(const _KT& __x) { return _M_t.find(__x); }
 362   _STLP_TEMPLATE_FOR_CONT_EXT
 363   const_iterator find(const _KT& __x) const { return _M_t.find(__x); }
 364   _STLP_TEMPLATE_FOR_CONT_EXT
 365   size_type count(const _KT& __x) const { return _M_t.count(__x); }
 366   _STLP_TEMPLATE_FOR_CONT_EXT
 367   iterator lower_bound(const _KT& __x) { return _M_t.lower_bound(__x); }
 368   _STLP_TEMPLATE_FOR_CONT_EXT
 369   const_iterator lower_bound(const _KT& __x) const { return _M_t.lower_bound(__x); }
 370   _STLP_TEMPLATE_FOR_CONT_EXT
 371   iterator upper_bound(const _KT& __x) { return _M_t.upper_bound(__x); }
 372   _STLP_TEMPLATE_FOR_CONT_EXT
 373   const_iterator upper_bound(const _KT& __x) const { return _M_t.upper_bound(__x); }
 374   _STLP_TEMPLATE_FOR_CONT_EXT
 375   pair<iterator, iterator> equal_range(const _KT& __x) { return _M_t.equal_range(__x); }
 376   _STLP_TEMPLATE_FOR_CONT_EXT
 377   pair<const_iterator, const_iterator> equal_range(const _KT& __x) const { return _M_t.equal_range(__x); }
 378 };
 379
 380 #else
 381 #  include <stl/pointers/_set.h>
 382 _STLP_BEGIN_NAMESPACE
 383 #endif /* _STLP_USE_PTR_SPECIALIZATIONS */
 384
 385 #define _STLP_TEMPLATE_HEADER template <class _Key, class _Compare, class _Alloc>
 386 #define _STLP_TEMPLATE_CONTAINER set<_Key,_Compare,_Alloc>
 387 #include <stl/_relops_cont.h>
 388 #undef  _STLP_TEMPLATE_CONTAINER
 389 #define _STLP_TEMPLATE_CONTAINER multiset<_Key,_Compare,_Alloc>
 390 #include <stl/_relops_cont.h>
 391 #undef  _STLP_TEMPLATE_CONTAINER
 392 #undef  _STLP_TEMPLATE_HEADER
 393
 394 #if defined (_STLP_CLASS_PARTIAL_SPECIALIZATION) && !defined (_STLP_NO_MOVE_SEMANTIC)
 395 template <class _Key, class _Compare, class _Alloc>
 396 struct __move_traits<set<_Key,_Compare,_Alloc> > :
 397   _STLP_PRIV __move_traits_aux<typename set<_Key,_Compare,_Alloc>::_Rep_type>
 398 {};
 399
 400 template <class _Key, class _Compare, class _Alloc>
 401 struct __move_traits<multiset<_Key,_Compare,_Alloc> > :
 402   _STLP_PRIV __move_traits_aux<typename multiset<_Key,_Compare,_Alloc>::_Rep_type>
 403 {};
 404 #endif
 405
 406 _STLP_END_NAMESPACE
 407
 408 #endif /* _STLP_INTERNAL_SET_H */
 409
 410 // Local Variables:
 411 // mode:C++
 412 // End: