graph/detail/set_adaptor.hpp

0001 // (C) Copyright Jeremy Siek 2001.
0002 // Distributed under the Boost Software License, Version 1.0. (See
0003 // accompanying file LICENSE_1_0.txt or copy at
0004 // http://www.boost.org/LICENSE_1_0.txt)
0005
0006 #ifndef BOOST_SET_ADAPTOR_HPP
0007 #define BOOST_SET_ADAPTOR_HPP
0008
0009 #include <set>
0010 #include <boost/unordered_set.hpp>
0011
0012 namespace boost
0013 {
0014
0015 template < class K, class C, class A, class T >
0016 bool set_contains(const std::set< K, C, A >& s, const T& x)
0017 {
0018     return s.find(x) != s.end();
0019 }
0020
0021 template < class K, class H, class C, class A, class T >
0022 bool set_contains(const boost::unordered_set< K, H, C, A >& s, const T& x)
0023 {
0024     return s.find(x) != s.end();
0025 }
0026
0027 template < class K, class C, class A >
0028 bool set_equal(const std::set< K, C, A >& x, const std::set< K, C, A >& y)
0029 {
0030     return x == y;
0031 }
0032
0033 // Not the same as lexicographical_compare_3way applied to std::set.
0034 // this is equivalent semantically to bitset::operator<()
0035 template < class K, class C, class A >
0036 int set_lex_order(const std::set< K, C, A >& x, const std::set< K, C, A >& y)
0037 {
0038     typename std::set< K, C, A >::iterator xi = x.begin(), yi = y.begin(),
0039                                            xend = x.end(), yend = y.end();
0040     for (; xi != xend && yi != yend; ++xi, ++yi)
0041     {
0042         if (*xi < *yi)
0043             return 1;
0044         else if (*yi < *xi)
0045             return -1;
0046     }
0047     if (xi == xend)
0048         return (yi == yend) ? 0 : -1;
0049     else
0050         return 1;
0051 }
0052
0053 template < class K, class C, class A > void set_clear(std::set< K, C, A >& x)
0054 {
0055     x.clear();
0056 }
0057
0058 template < class K, class C, class A >
0059 bool set_empty(const std::set< K, C, A >& x)
0060 {
0061     return x.empty();
0062 }
0063
0064 template < class K, class C, class A, class T >
0065 void set_insert(std::set< K, C, A >& x, const T& a)
0066 {
0067     x.insert(a);
0068 }
0069
0070 template < class K, class C, class A, class T >
0071 void set_remove(std::set< K, C, A >& x, const T& a)
0072 {
0073     x.erase(a);
0074 }
0075
0076 template < class K, class C, class A >
0077 void set_intersect(const std::set< K, C, A >& x, const std::set< K, C, A >& y,
0078     std::set< K, C, A >& z)
0079 {
0080     z.clear();
0081     std::set_intersection(
0082         x.begin(), x.end(), y.begin(), y.end(), std::inserter(z));
0083 }
0084
0085 template < class K, class C, class A >
0086 void set_union(const std::set< K, C, A >& x, const std::set< K, C, A >& y,
0087     std::set< K, C, A >& z)
0088 {
0089     z.clear();
0090     std::set_union(x.begin(), x.end(), y.begin(), y.end(), std::inserter(z));
0091 }
0092
0093 template < class K, class C, class A >
0094 void set_difference(const std::set< K, C, A >& x, const std::set< K, C, A >& y,
0095     std::set< K, C, A >& z)
0096 {
0097     z.clear();
0098     std::set_difference(
0099         x.begin(), x.end(), y.begin(), y.end(), std::inserter(z, z.begin()));
0100 }
0101
0102 template < class K, class C, class A >
0103 bool set_subset(const std::set< K, C, A >& x, const std::set< K, C, A >& y)
0104 {
0105     return std::includes(x.begin(), x.end(), y.begin(), y.end());
0106 }
0107
0108 // Shit, can't implement this without knowing the size of the
0109 // universe.
0110 template < class K, class C, class A >
0111 void set_compliment(const std::set< K, C, A >& /*x*/, std::set< K, C, A >& z)
0112 {
0113     z.clear();
0114 }
0115
0116 } // namespace boost
0117
0118 #endif // BOOST_SET_ADAPTOR_HPP