home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / stlpt453.zip / STLport-4.5.3 / stlport / stl / _set.h < prev    next >
C/C++ Source or Header  |  2001-04-08  |  13KB  |  373 lines
  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. #define set __WORKAROUND_RENAME(set)
  38. #define multiset __WORKAROUND_RENAME(multiset)
  39.  
  40. _STLP_BEGIN_NAMESPACE
  41.  
  42. template <class _Key, __DFL_TMPL_PARAM(_Compare,less<_Key>), 
  43.                      _STLP_DEFAULT_ALLOCATOR_SELECT(_Key) >
  44. class set {
  45. public:
  46. // typedefs:
  47.   typedef _Key     key_type;
  48.   typedef _Key     value_type;
  49.   typedef _Compare key_compare;
  50.   typedef _Compare value_compare;
  51. private:
  52.   typedef _Rb_tree<key_type, value_type, 
  53.     _Identity<value_type>, key_compare, _Alloc> _Rep_type;
  54. public:
  55.   typedef typename _Rep_type::pointer pointer;
  56.   typedef typename _Rep_type::const_pointer const_pointer;
  57.   typedef typename _Rep_type::reference reference;
  58.   typedef typename _Rep_type::const_reference const_reference;
  59.   typedef typename _Rep_type::const_iterator const_iterator;
  60.   typedef const_iterator iterator;
  61.   typedef typename _Rep_type::const_reverse_iterator reverse_iterator;
  62.   typedef typename _Rep_type::const_reverse_iterator const_reverse_iterator;
  63.   typedef typename _Rep_type::size_type size_type;
  64.   typedef typename _Rep_type::difference_type difference_type;
  65.   typedef typename _Rep_type::allocator_type allocator_type;
  66.  
  67. private:
  68.   _Rep_type _M_t;  // red-black tree representing set
  69. public:
  70.  
  71.   // allocation/deallocation
  72.  
  73.   set() : _M_t(_Compare(), allocator_type()) {}
  74.   explicit set(const _Compare& __comp,
  75.            const allocator_type& __a = allocator_type())
  76.     : _M_t(__comp, __a) {}
  77.  
  78. #ifdef _STLP_MEMBER_TEMPLATES
  79.   template <class _InputIterator>
  80.   set(_InputIterator __first, _InputIterator __last)
  81.     : _M_t(_Compare(), allocator_type())
  82.     { _M_t.insert_unique(__first, __last); }
  83.  
  84. # ifdef _STLP_NEEDS_EXTRA_TEMPLATE_CONSTRUCTORS
  85.   template <class _InputIterator>
  86.   set(_InputIterator __first, _InputIterator __last, const _Compare& __comp)
  87.     : _M_t(__comp, allocator_type()) { _M_t.insert_unique(__first, __last); }
  88. # endif
  89.   template <class _InputIterator>
  90.   set(_InputIterator __first, _InputIterator __last, const _Compare& __comp,
  91.       const allocator_type& __a _STLP_ALLOCATOR_TYPE_DFL)
  92.     : _M_t(__comp, __a) { _M_t.insert_unique(__first, __last); }
  93. #else
  94.   set(const value_type* __first, const value_type* __last) 
  95.     : _M_t(_Compare(), allocator_type()) 
  96.     { _M_t.insert_unique(__first, __last); }
  97.  
  98.   set(const value_type* __first, 
  99.       const value_type* __last, const _Compare& __comp,
  100.       const allocator_type& __a = allocator_type())
  101.     : _M_t(__comp, __a) { _M_t.insert_unique(__first, __last); }
  102.  
  103.   set(const_iterator __first, const_iterator __last)
  104.     : _M_t(_Compare(), allocator_type()) 
  105.     { _M_t.insert_unique(__first, __last); }
  106.  
  107.   set(const_iterator __first, const_iterator __last, const _Compare& __comp,
  108.       const allocator_type& __a = allocator_type())
  109.     : _M_t(__comp, __a) { _M_t.insert_unique(__first, __last); }
  110. #endif /* _STLP_MEMBER_TEMPLATES */
  111.  
  112.   set(const set<_Key,_Compare,_Alloc>& __x) : _M_t(__x._M_t) {}
  113.   set<_Key,_Compare,_Alloc>& operator=(const set<_Key, _Compare, _Alloc>& __x)
  114.   { 
  115.     _M_t = __x._M_t; 
  116.     return *this;
  117.   }
  118.  
  119.   // accessors:
  120.  
  121.   key_compare key_comp() const { return _M_t.key_comp(); }
  122.   value_compare value_comp() const { return _M_t.key_comp(); }
  123.   allocator_type get_allocator() const { return _M_t.get_allocator(); }
  124.  
  125.   iterator begin() const { return _M_t.begin(); }
  126.   iterator end() const { return _M_t.end(); }
  127.   reverse_iterator rbegin() const { return _M_t.rbegin(); } 
  128.   reverse_iterator rend() const { return _M_t.rend(); }
  129.   bool empty() const { return _M_t.empty(); }
  130.   size_type size() const { return _M_t.size(); }
  131.   size_type max_size() const { return _M_t.max_size(); }
  132.   void swap(set<_Key,_Compare,_Alloc>& __x) { _M_t.swap(__x._M_t); }
  133.  
  134.   // insert/erase
  135.   pair<iterator,bool> insert(const value_type& __x) { 
  136.     typedef typename _Rep_type::iterator _Rep_iterator;
  137.     pair<_Rep_iterator, bool> __p = _M_t.insert_unique(__x); 
  138.     return pair<iterator, bool>(__REINTERPRET_CAST(const iterator&,__p.first), __p.second);
  139.   }
  140.   iterator insert(iterator __position, const value_type& __x) {
  141.     typedef typename _Rep_type::iterator _Rep_iterator;
  142.     return _M_t.insert_unique((_Rep_iterator&)__position, __x);
  143.   }
  144. #ifdef _STLP_MEMBER_TEMPLATES
  145.   template <class _InputIterator>
  146.   void insert(_InputIterator __first, _InputIterator __last) {
  147.     _M_t.insert_unique(__first, __last);
  148.   }
  149. #else
  150.   void insert(const_iterator __first, const_iterator __last) {
  151.     _M_t.insert_unique(__first, __last);
  152.   }
  153.   void insert(const value_type* __first, const value_type* __last) {
  154.     _M_t.insert_unique(__first, __last);
  155.   }
  156. #endif /* _STLP_MEMBER_TEMPLATES */
  157.   void erase(iterator __position) { 
  158.     typedef typename _Rep_type::iterator _Rep_iterator;
  159.     _M_t.erase((_Rep_iterator&)__position); 
  160.   }
  161.   size_type erase(const key_type& __x) { 
  162.     return _M_t.erase(__x); 
  163.   }
  164.   void erase(iterator __first, iterator __last) { 
  165.     typedef typename _Rep_type::iterator _Rep_iterator;
  166.     _M_t.erase((_Rep_iterator&)__first, (_Rep_iterator&)__last); 
  167.   }
  168.   void clear() { _M_t.clear(); }
  169.  
  170.   // set operations:
  171. # if defined(_STLP_MEMBER_TEMPLATES) && ! defined ( _STLP_NO_EXTENSIONS )
  172.   template <class _KT>
  173.   iterator find(const _KT& __x) const { return _M_t.find(__x); }
  174. # else
  175.   iterator find(const key_type& __x) const { return _M_t.find(__x); }
  176. # endif
  177.   size_type count(const key_type& __x) const { 
  178.     return _M_t.find(__x) == _M_t.end() ? 0 : 1 ; 
  179.   }
  180.   iterator lower_bound(const key_type& __x) const {
  181.     return _M_t.lower_bound(__x);
  182.   }
  183.   iterator upper_bound(const key_type& __x) const {
  184.     return _M_t.upper_bound(__x); 
  185.   }
  186.   pair<iterator,iterator> equal_range(const key_type& __x) const {
  187.     return _M_t.equal_range(__x);
  188.   }
  189. };
  190.  
  191. template <class _Key, __DFL_TMPL_PARAM(_Compare,less<_Key>), 
  192.                      _STLP_DEFAULT_ALLOCATOR_SELECT(_Key) >
  193. class multiset {
  194. public:
  195.   // typedefs:
  196.  
  197.   typedef _Key     key_type;
  198.   typedef _Key     value_type;
  199.   typedef _Compare key_compare;
  200.   typedef _Compare value_compare;
  201. private:
  202.   typedef _Rb_tree<key_type, value_type, 
  203.                   _Identity<value_type>, key_compare, _Alloc> _Rep_type;
  204. public:
  205.   typedef typename _Rep_type::pointer pointer;
  206.   typedef typename _Rep_type::const_pointer const_pointer;
  207.   typedef typename _Rep_type::reference reference;
  208.   typedef typename _Rep_type::const_reference const_reference;
  209.   typedef typename _Rep_type::const_iterator const_iterator;
  210.   typedef const_iterator iterator;
  211.   typedef typename _Rep_type::const_reverse_iterator reverse_iterator;
  212.   typedef typename _Rep_type::const_reverse_iterator const_reverse_iterator;
  213.   typedef typename _Rep_type::size_type size_type;
  214.   typedef typename _Rep_type::difference_type difference_type;
  215.   typedef typename _Rep_type::allocator_type allocator_type;
  216.  
  217. private:
  218.   _Rep_type _M_t;  // red-black tree representing multiset
  219. public:
  220.   // allocation/deallocation
  221.  
  222.   multiset() : _M_t(_Compare(), allocator_type()) {}
  223.   explicit multiset(const _Compare& __comp,
  224.                     const allocator_type& __a = allocator_type())
  225.     : _M_t(__comp, __a) {}
  226.  
  227. #ifdef _STLP_MEMBER_TEMPLATES
  228.  
  229.   template <class _InputIterator>
  230.   multiset(_InputIterator __first, _InputIterator __last)
  231.     : _M_t(_Compare(), allocator_type())
  232.     { _M_t.insert_equal(__first, __last); }
  233.  
  234. # ifdef _STLP_NEEDS_EXTRA_TEMPLATE_CONSTRUCTORS
  235.   template <class _InputIterator>
  236.   multiset(_InputIterator __first, _InputIterator __last,
  237.            const _Compare& __comp)
  238.     : _M_t(__comp, allocator_type()) { _M_t.insert_equal(__first, __last); }
  239. # endif
  240.   template <class _InputIterator>
  241.   multiset(_InputIterator __first, _InputIterator __last,
  242.            const _Compare& __comp,
  243.            const allocator_type& __a _STLP_ALLOCATOR_TYPE_DFL)
  244.     : _M_t(__comp, __a) { _M_t.insert_equal(__first, __last); }
  245.  
  246. #else
  247.  
  248.   multiset(const value_type* __first, const value_type* __last)
  249.     : _M_t(_Compare(), allocator_type())
  250.     { _M_t.insert_equal(__first, __last); }
  251.  
  252.   multiset(const value_type* __first, const value_type* __last,
  253.            const _Compare& __comp,
  254.            const allocator_type& __a = allocator_type())
  255.     : _M_t(__comp, __a) { _M_t.insert_equal(__first, __last); }
  256.  
  257.   multiset(const_iterator __first, const_iterator __last)
  258.     : _M_t(_Compare(), allocator_type())
  259.     { _M_t.insert_equal(__first, __last); }
  260.  
  261.   multiset(const_iterator __first, const_iterator __last,
  262.            const _Compare& __comp,
  263.            const allocator_type& __a = allocator_type())
  264.     : _M_t(__comp, __a) { _M_t.insert_equal(__first, __last); }
  265.    
  266. #endif /* _STLP_MEMBER_TEMPLATES */
  267.  
  268.   multiset(const multiset<_Key,_Compare,_Alloc>& __x) : _M_t(__x._M_t) {}
  269.   multiset<_Key,_Compare,_Alloc>&
  270.   operator=(const multiset<_Key,_Compare,_Alloc>& __x) {
  271.     _M_t = __x._M_t; 
  272.     return *this;
  273.   }
  274.  
  275.   // accessors:
  276.  
  277.   key_compare key_comp() const { return _M_t.key_comp(); }
  278.   value_compare value_comp() const { return _M_t.key_comp(); }
  279.   allocator_type get_allocator() const { return _M_t.get_allocator(); }
  280.  
  281.   iterator begin() const { return _M_t.begin(); }
  282.   iterator end() const { return _M_t.end(); }
  283.   reverse_iterator rbegin() const { return _M_t.rbegin(); } 
  284.   reverse_iterator rend() const { return _M_t.rend(); }
  285.   bool empty() const { return _M_t.empty(); }
  286.   size_type size() const { return _M_t.size(); }
  287.   size_type max_size() const { return _M_t.max_size(); }
  288.   void swap(multiset<_Key,_Compare,_Alloc>& __x) { _M_t.swap(__x._M_t); }
  289.  
  290.   // insert/erase
  291.   iterator insert(const value_type& __x) { 
  292.     return _M_t.insert_equal(__x);
  293.   }
  294.   iterator insert(iterator __position, const value_type& __x) {
  295.     typedef typename _Rep_type::iterator _Rep_iterator;
  296.     return _M_t.insert_equal((_Rep_iterator&)__position, __x);
  297.   }
  298.  
  299. #ifdef _STLP_MEMBER_TEMPLATES  
  300.   template <class _InputIterator>
  301.   void insert(_InputIterator __first, _InputIterator __last) {
  302.     _M_t.insert_equal(__first, __last);
  303.   }
  304. #else
  305.   void insert(const value_type* __first, const value_type* __last) {
  306.     _M_t.insert_equal(__first, __last);
  307.   }
  308.   void insert(const_iterator __first, const_iterator __last) {
  309.     _M_t.insert_equal(__first, __last);
  310.   }
  311. #endif /* _STLP_MEMBER_TEMPLATES */
  312.   void erase(iterator __position) { 
  313.     typedef typename _Rep_type::iterator _Rep_iterator;
  314.     _M_t.erase((_Rep_iterator&)__position); 
  315.   }
  316.   size_type erase(const key_type& __x) { 
  317.     return _M_t.erase(__x); 
  318.   }
  319.   void erase(iterator __first, iterator __last) { 
  320.     typedef typename _Rep_type::iterator _Rep_iterator;
  321.     _M_t.erase((_Rep_iterator&)__first, (_Rep_iterator&)__last); 
  322.   }
  323.   void clear() { _M_t.clear(); }
  324.  
  325.   // multiset operations:
  326.  
  327. # if defined(_STLP_MEMBER_TEMPLATES) && ! defined ( _STLP_NO_EXTENSIONS )
  328.   template <class _KT>
  329.   iterator find(const _KT& __x) const { return _M_t.find(__x); }
  330. # else
  331.   iterator find(const key_type& __x) const { return _M_t.find(__x); }
  332. # endif
  333.   size_type count(const key_type& __x) const { return _M_t.count(__x); }
  334.   iterator lower_bound(const key_type& __x) const {
  335.     return _M_t.lower_bound(__x);
  336.   }
  337.   iterator upper_bound(const key_type& __x) const {
  338.     return _M_t.upper_bound(__x); 
  339.   }
  340.   pair<iterator,iterator> equal_range(const key_type& __x) const {
  341.     return _M_t.equal_range(__x);
  342.   }
  343. };
  344.  
  345. # define _STLP_TEMPLATE_HEADER template <class _Key, class _Compare, class _Alloc>
  346. # define _STLP_TEMPLATE_CONTAINER set<_Key,_Compare,_Alloc>
  347. # include <stl/_relops_cont.h>
  348. # undef  _STLP_TEMPLATE_CONTAINER
  349. # define _STLP_TEMPLATE_CONTAINER multiset<_Key,_Compare,_Alloc>
  350. # include <stl/_relops_cont.h>
  351. # undef  _STLP_TEMPLATE_CONTAINER
  352. # undef  _STLP_TEMPLATE_HEADER
  353.  
  354. _STLP_END_NAMESPACE
  355.  
  356. // do a cleanup
  357. # undef set
  358. # undef multiset
  359. // provide a way to access full funclionality 
  360. # define __set__  __FULL_NAME(set)
  361. # define __multiset__  __FULL_NAME(multiset)
  362.  
  363. # ifdef _STLP_USE_WRAPPER_FOR_ALLOC_PARAM
  364. # include <stl/wrappers/_set.h>
  365. # endif
  366.  
  367. #endif /* _STLP_INTERNAL_SET_H */
  368.  
  369. // Local Variables:
  370. // mode:C++
  371. // End:
  372.  
  373.