home *** CD-ROM | disk | FTP | other *** search
/ Beginning C++ Through Gam…rogramming (2nd Edition) / BCGP2E.ISO / bloodshed / devcpp-4.9.9.2_setup.exe / set.h < prev    next >
C/C++ Source or Header  |  2005-01-29  |  10KB  |  326 lines
  1. // Debugging set implementation -*- C++ -*-
  2.  
  3. // Copyright (C) 2003, 2004
  4. // Free Software Foundation, Inc.
  5. //
  6. // This file is part of the GNU ISO C++ Library.  This library is free
  7. // software; you can redistribute it and/or modify it under the
  8. // terms of the GNU General Public License as published by the
  9. // Free Software Foundation; either version 2, or (at your option)
  10. // any later version.
  11.  
  12. // This library is distributed in the hope that it will be useful,
  13. // but WITHOUT ANY WARRANTY; without even the implied warranty of
  14. // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15. // GNU General Public License for more details.
  16.  
  17. // You should have received a copy of the GNU General Public License along
  18. // with this library; see the file COPYING.  If not, write to the Free
  19. // Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
  20. // USA.
  21.  
  22. // As a special exception, you may use this file as part of a free software
  23. // library without restriction.  Specifically, if other files instantiate
  24. // templates or use macros or inline functions from this file, or you compile
  25. // this file and link it with other files to produce an executable, this
  26. // file does not by itself cause the resulting executable to be covered by
  27. // the GNU General Public License.  This exception does not however
  28. // invalidate any other reasons why the executable file might be covered by
  29. // the GNU General Public License.
  30.  
  31. #ifndef _GLIBCXX_DEBUG_SET_H
  32. #define _GLIBCXX_DEBUG_SET_H 1
  33.  
  34. #include <debug/safe_sequence.h>
  35. #include <debug/safe_iterator.h>
  36. #include <utility>
  37.  
  38. namespace __gnu_debug_def
  39. {
  40.   template<typename _Key, typename _Compare = std::less<_Key>,
  41.        typename _Allocator = std::allocator<_Key> >
  42.     class set
  43.     : public _GLIBCXX_STD::set<_Key,_Compare,_Allocator>,
  44.       public __gnu_debug::_Safe_sequence<set<_Key, _Compare, _Allocator> >
  45.     {
  46.       typedef _GLIBCXX_STD::set<_Key,_Compare,_Allocator> _Base;
  47.       typedef __gnu_debug::_Safe_sequence<set> _Safe_base;
  48.  
  49.     public:
  50.       // types:
  51.       typedef _Key                    key_type;
  52.       typedef _Key                    value_type;
  53.       typedef _Compare                    key_compare;
  54.       typedef _Compare                    value_compare;
  55.       typedef _Allocator                allocator_type;
  56.       typedef typename _Allocator::reference        reference;
  57.       typedef typename _Allocator::const_reference  const_reference;
  58.  
  59.       typedef __gnu_debug::_Safe_iterator<typename _Base::iterator, set>
  60.                                                     iterator;
  61.       typedef __gnu_debug::_Safe_iterator<typename _Base::const_iterator, set>
  62.                                                     const_iterator;
  63.  
  64.       typedef typename _Base::size_type             size_type;
  65.       typedef typename _Base::difference_type       difference_type;
  66.       typedef typename _Allocator::pointer          pointer;
  67.       typedef typename _Allocator::const_pointer    const_pointer;
  68.       typedef std::reverse_iterator<iterator>       reverse_iterator;
  69.       typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
  70.  
  71.       // 23.3.3.1 construct/copy/destroy:
  72.       explicit set(const _Compare& __comp = _Compare(),
  73.            const _Allocator& __a = _Allocator())
  74.       : _Base(__comp, __a) { }
  75.  
  76.       template<typename _InputIterator>
  77.         set(_InputIterator __first, _InputIterator __last,
  78.         const _Compare& __comp = _Compare(),
  79.         const _Allocator& __a = _Allocator())
  80.     : _Base(__gnu_debug::__check_valid_range(__first, __last), __last,
  81.         __comp, __a) { }
  82.  
  83.       set(const set<_Key,_Compare,_Allocator>& __x)
  84.       : _Base(__x), _Safe_base() { }
  85.  
  86.       set(const _Base& __x) : _Base(__x), _Safe_base() { }
  87.  
  88.       ~set() { }
  89.  
  90.       set<_Key,_Compare,_Allocator>&
  91.       operator=(const set<_Key,_Compare,_Allocator>& __x)
  92.       {
  93.     *static_cast<_Base*>(this) = __x;
  94.     this->_M_invalidate_all();
  95.     return *this;
  96.       }
  97.  
  98.       using _Base::get_allocator;
  99.  
  100.       // iterators:
  101.       iterator
  102.       begin()
  103.       { return iterator(_Base::begin(), this); }
  104.  
  105.       const_iterator
  106.       begin() const
  107.       { return const_iterator(_Base::begin(), this); }
  108.  
  109.       iterator
  110.       end()
  111.       { return iterator(_Base::end(), this); }
  112.  
  113.       const_iterator
  114.       end() const
  115.       { return const_iterator(_Base::end(), this); }
  116.  
  117.       reverse_iterator
  118.       rbegin()
  119.       { return reverse_iterator(end()); }
  120.  
  121.       const_reverse_iterator
  122.       rbegin() const
  123.       { return const_reverse_iterator(end()); }
  124.  
  125.       reverse_iterator
  126.       rend()
  127.       { return reverse_iterator(begin()); }
  128.  
  129.       const_reverse_iterator
  130.       rend() const
  131.       { return const_reverse_iterator(begin()); }
  132.  
  133.       // capacity:
  134.       using _Base::empty;
  135.       using _Base::size;
  136.       using _Base::max_size;
  137.  
  138.       // modifiers:
  139.       std::pair<iterator, bool>
  140.       insert(const value_type& __x)
  141.       {
  142.     typedef typename _Base::iterator _Base_iterator;
  143.     std::pair<_Base_iterator, bool> __res = _Base::insert(__x);
  144.     return std::pair<iterator, bool>(iterator(__res.first, this),
  145.                      __res.second);
  146.       }
  147.  
  148.       iterator
  149.       insert(iterator __position, const value_type& __x)
  150.       {
  151.     __glibcxx_check_insert(__position);
  152.     return iterator(_Base::insert(__position.base(), __x), this);
  153.       }
  154.  
  155.       template <typename _InputIterator>
  156.         void
  157.         insert(_InputIterator __first, _InputIterator __last)
  158.         {
  159.       __glibcxx_check_valid_range(__first, __last);
  160.       _Base::insert(__first, __last);
  161.     }
  162.  
  163.       void
  164.       erase(iterator __position)
  165.       {
  166.     __glibcxx_check_erase(__position);
  167.     __position._M_invalidate();
  168.     _Base::erase(__position.base());
  169.       }
  170.  
  171.       size_type
  172.       erase(const key_type& __x)
  173.       {
  174.     iterator __victim = find(__x);
  175.     if (__victim == end())
  176.           return 0;
  177.     else
  178.         {
  179.       __victim._M_invalidate();
  180.       _Base::erase(__victim.base());
  181.       return 1;
  182.         }
  183.       }
  184.  
  185.       void
  186.       erase(iterator __first, iterator __last)
  187.       {
  188.     // _GLIBCXX_RESOLVE_LIB_DEFECTS
  189.     // 151. can't currently clear() empty container
  190.     __glibcxx_check_erase_range(__first, __last);
  191.  
  192.     while (__first != __last)
  193.         this->erase(__first++);
  194.       }
  195.  
  196.       void
  197.       swap(set<_Key,_Compare,_Allocator>& __x)
  198.       {
  199.     _Base::swap(__x);
  200.     this->_M_swap(__x);
  201.       }
  202.  
  203.       void
  204.       clear()
  205.       { this->erase(begin(), end()); }
  206.  
  207.       // observers:
  208.       using _Base::key_comp;
  209.       using _Base::value_comp;
  210.  
  211.       // set operations:
  212.       iterator
  213.       find(const key_type& __x)
  214.       { return iterator(_Base::find(__x), this); }
  215.  
  216.       // _GLIBCXX_RESOLVE_LIB_DEFECTS
  217.       // 214. set::find() missing const overload
  218.       const_iterator
  219.       find(const key_type& __x) const
  220.       { return const_iterator(_Base::find(__x), this); }
  221.  
  222.       using _Base::count;
  223.  
  224.       iterator
  225.       lower_bound(const key_type& __x)
  226.       { return iterator(_Base::lower_bound(__x), this); }
  227.  
  228.       // _GLIBCXX_RESOLVE_LIB_DEFECTS
  229.       // 214. set::find() missing const overload
  230.       const_iterator
  231.       lower_bound(const key_type& __x) const
  232.       { return const_iterator(_Base::lower_bound(__x), this); }
  233.  
  234.       iterator
  235.       upper_bound(const key_type& __x)
  236.       { return iterator(_Base::upper_bound(__x), this); }
  237.  
  238.       // _GLIBCXX_RESOLVE_LIB_DEFECTS
  239.       // 214. set::find() missing const overload
  240.       const_iterator
  241.       upper_bound(const key_type& __x) const
  242.       { return const_iterator(_Base::upper_bound(__x), this); }
  243.  
  244.       std::pair<iterator,iterator>
  245.       equal_range(const key_type& __x)
  246.       {
  247.     typedef typename _Base::iterator _Base_iterator;
  248.     std::pair<_Base_iterator, _Base_iterator> __res =
  249.         _Base::equal_range(__x);
  250.     return std::make_pair(iterator(__res.first, this),
  251.                   iterator(__res.second, this));
  252.       }
  253.  
  254.       // _GLIBCXX_RESOLVE_LIB_DEFECTS
  255.       // 214. set::find() missing const overload
  256.       std::pair<const_iterator,const_iterator>
  257.       equal_range(const key_type& __x) const
  258.       {
  259.     typedef typename _Base::const_iterator _Base_iterator;
  260.     std::pair<_Base_iterator, _Base_iterator> __res =
  261.         _Base::equal_range(__x);
  262.     return std::make_pair(const_iterator(__res.first, this),
  263.                   const_iterator(__res.second, this));
  264.       }
  265.  
  266.       _Base&
  267.       _M_base() { return *this; }
  268.  
  269.       const _Base&
  270.       _M_base() const { return *this; }
  271.  
  272.     private:
  273.       void
  274.       _M_invalidate_all()
  275.       {
  276.     typedef typename _Base::const_iterator _Base_const_iterator;
  277.     typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal;
  278.     this->_M_invalidate_if(_Not_equal(_M_base().end()));
  279.       }
  280.     };
  281.  
  282.   template<typename _Key, typename _Compare, typename _Allocator>
  283.     inline bool
  284.     operator==(const set<_Key,_Compare,_Allocator>& __lhs,
  285.            const set<_Key,_Compare,_Allocator>& __rhs)
  286.     { return __lhs._M_base() == __rhs._M_base(); }
  287.  
  288.   template<typename _Key, typename _Compare, typename _Allocator>
  289.     inline bool
  290.     operator!=(const set<_Key,_Compare,_Allocator>& __lhs,
  291.            const set<_Key,_Compare,_Allocator>& __rhs)
  292.     { return __lhs._M_base() != __rhs._M_base(); }
  293.  
  294.   template<typename _Key, typename _Compare, typename _Allocator>
  295.     inline bool
  296.     operator<(const set<_Key,_Compare,_Allocator>& __lhs,
  297.           const set<_Key,_Compare,_Allocator>& __rhs)
  298.     { return __lhs._M_base() < __rhs._M_base(); }
  299.  
  300.   template<typename _Key, typename _Compare, typename _Allocator>
  301.     inline bool
  302.     operator<=(const set<_Key,_Compare,_Allocator>& __lhs,
  303.            const set<_Key,_Compare,_Allocator>& __rhs)
  304.     { return __lhs._M_base() <= __rhs._M_base(); }
  305.  
  306.   template<typename _Key, typename _Compare, typename _Allocator>
  307.     inline bool
  308.     operator>=(const set<_Key,_Compare,_Allocator>& __lhs,
  309.            const set<_Key,_Compare,_Allocator>& __rhs)
  310.     { return __lhs._M_base() >= __rhs._M_base(); }
  311.  
  312.   template<typename _Key, typename _Compare, typename _Allocator>
  313.     inline bool
  314.     operator>(const set<_Key,_Compare,_Allocator>& __lhs,
  315.           const set<_Key,_Compare,_Allocator>& __rhs)
  316.     { return __lhs._M_base() > __rhs._M_base(); }
  317.  
  318.   template<typename _Key, typename _Compare, typename _Allocator>
  319.     void
  320.     swap(set<_Key,_Compare,_Allocator>& __x,
  321.      set<_Key,_Compare,_Allocator>& __y)
  322.     { return __x.swap(__y); }
  323. } // namespace __gnu_debug_def
  324.  
  325. #endif
  326.