cds/opt/compare.h

   1 //$$CDS-header$$
   2
   3 #ifndef CDSLIB_OPT_COMPARE_H
   4 #define CDSLIB_OPT_COMPARE_H
   5
   6 /*
   7     Editions:
   8         2011.05.05 khizmax  Created
   9 */
  10
  11 #include <type_traits>
  12 #include <functional>
  13 #include <string>
  14 #include <cds/opt/options.h>
  15
  16 namespace cds { namespace opt {
  17
  18     /// [type-option] Option setter for key comparing
  19     /**
  20         The option sets a type of a functor to compare keys.
  21         For comparing two keys \p k1 and \p k2 the functor must return:
  22         - 1 if k1 > k2
  23         - 0 if k1 == k2
  24         - -1 if k1 < k2
  25
  26         \p Functor is a functor with following interface:
  27         \code
  28         template <typename T>
  29         struct Comparator {
  30             int operator ()(const T& r1, const T& r2)
  31             {
  32                 // Comparator body
  33             }
  34         };
  35         \endcode
  36         Note that the functor must return \p int, not a \p bool value.
  37
  38         There are predefined type for \p Functor:
  39         - the functor v::less_comparator that implements comparing functor through \p std::less predicate.
  40         - the specialization of v::less_comparator functor intended for the string comparison
  41
  42         You may implement your own comparing functor that satisfies \p Functor interface.
  43
  44         About relation between \ref opt::less and \ref opt::compare option setters see opt::less description.
  45     */
  46     template <typename Functor>
  47     struct compare {
  48         //@cond
  49         template <typename Base> struct pack: public Base
  50         {
  51             typedef Functor compare;
  52         };
  53         //@endcond
  54     };
  55
  56     namespace v {
  57
  58         /// Comparator based on \p std::less predicate
  59         /**
  60             This functor is predefined type for \p opt::compare option setter.
  61             It is based on \p std::less predicate.
  62         */
  63         template <typename T>
  64         struct less_comparator {
  65             /// Operator that compares two value of type \p T
  66             int operator()(T const& v1, T const& v2)
  67             {
  68                 if ( std::less<T>()( v1, v2 ) )
  69                     return -1;
  70                 if ( std::less<T>()( v2, v1 ))
  71                     return 1;
  72                 return 0;
  73             }
  74         };
  75
  76         /// Comparator specialization for \p std::string
  77         /**
  78             This functor uses \p std::string::compare method instead of \p std::less predicate.
  79         */
  80         template <typename T, typename Traits, typename Alloc>
  81         struct less_comparator< std::basic_string<T, Traits, Alloc> >
  82         {
  83             //@cond
  84             typedef std::basic_string<T, Traits, Alloc> string_type;
  85             int operator()(string_type const& v1, string_type const& v2)
  86             {
  87                 return v1.compare( v2 );
  88             }
  89             //@endcond
  90         };
  91     }   // namespace v
  92
  93     /// [type-option] Option setter for \p less predicate
  94     /**
  95         The option sets a binary predicate that tests whether a value of a specified type is less than another value of that type.
  96         \p Functor interface is similar to \p std::less predicate interface.
  97         The standard predicate \p std::less can act as \p Functor:
  98         \code typedef cds::opt::less< std::less< int > > opt_less \endcode
  99
 100         In addition, the option setter may sets non-standard 2-type predicate (\p std::binary_function):
 101         \code
 102
 103         struct foo {
 104             int n;
 105         };
 106
 107         template <typename T, typename Q>
 108         struct pred_less {
 109             bool operator ()( const T& t, const Q& q )
 110             { return t.n < q ; }
 111             bool operator ()( const Q& q, const T& t )
 112             { return q < t.n ; }
 113             bool operator ()( const T& t1, const T& t2 )
 114             { return t1.n < t2.n ; }
 115             bool operator ()( const Q& q1, const Q& q2 )
 116             { return q1 < q2 ; }
 117         };
 118
 119         typedef cds::opt::less< pred_less< foo, int > > opt_less;
 120         \endcode
 121
 122         Generally, the default type for \p Functor is \p std::less but it depends on the container used.
 123
 124         \par Relation between \p opt::less and opt::compare option setters
 125         Unless otherwise specified, \p compare option setter has high priority. If opt::compare and opt::less options are specified
 126         for a container, the opt::compare option is used:
 127         \code
 128         // Suppose, hypothetical map_type allows to specify
 129         // cds::opt::less and cds::opt::compare options
 130
 131         typedef map_type< std::string, int,
 132             cds::opt::compare< cds::opt::v::less_comparator< std::string > >,
 133             cds::opt::less< std::less< std::string > >
 134         > my_map_type;
 135
 136         // For my_map_type, the cds::opt::compare comparator will be used,
 137         // the cds::opt::less option is ignored without any warnings.
 138         \endcode
 139     */
 140     template <typename Functor>
 141     struct less {
 142         //@cond
 143         template <typename Base> struct pack: public Base
 144         {
 145             typedef Functor less;
 146         };
 147         //@endcond
 148     };
 149
 150     //@cond
 151     namespace details {
 152         template <typename Less>
 153         struct make_comparator_from_less
 154         {
 155             typedef Less less_functor;
 156
 157             template <typename T, typename Q>
 158             int operator ()( T const& t, Q const& q ) const
 159             {
 160                 less_functor f;
 161                 if ( f( t, q ) )
 162                     return -1;
 163                 if ( f( q, t ) )
 164                     return 1;
 165                 return 0;
 166             }
 167         };
 168
 169         template <typename T, typename Traits, typename DefaultCmp = make_comparator_from_less< std::less<T>>::type >
 170         struct make_comparator_from
 171         {
 172             typedef typename Traits::compare compare;
 173             typedef typename Traits::less less;
 174
 175             typedef typename std::conditional<
 176                 std::is_same< compare, opt::none >::value,
 177                 typename std::conditional<
 178                     std::is_same< less, opt::none >::value,
 179                     DefaultCmp,
 180                     make_comparator_from_less< less >
 181                 >::type,
 182                 compare
 183             >::type type;
 184         };
 185
 186
 187         template <typename T, typename Traits, bool Forced = true >
 188         using make_comparator = make_comparator_from< T, Traits, typename std::conditional< Forced, make_comparator_from_less< std::less<T>>, opt::none >::type >;
 189
 190         template <typename T, typename... Options>
 191         struct make_comparator_from_option_list
 192         {
 193             struct default_traits {
 194                 typedef opt::none   compare;
 195                 typedef opt::none   less;
 196             };
 197
 198             typedef typename make_comparator< T,
 199                 typename opt::make_options<
 200                     typename opt::find_type_traits< default_traits, Options... >::type
 201                     ,Options...
 202                 >::type
 203             >::type type;
 204         };
 205     }   // namespace details
 206     //@endcond
 207
 208     /// [type-option] Option setter for \p equal_to predicate
 209     /**
 210         The option sets a binary predicate that tests whether a value of a specified type is equal to another value of that type.
 211         \p Functor interface is similar to \p std::equal_to predicate interface.
 212         The standard predicate \p std::equal_to can act as \p Functor:
 213         \code typedef cds::opt::equal_to< std::equal_to< int > > opt_equal_to \endcode
 214
 215         In addition, the option setter may sets non-standard 2-type (or even N-type) predicate (\p std::binary_function):
 216         \code
 217
 218         struct foo {
 219             int n;
 220         };
 221
 222         template <typename T, typename Q>
 223         struct pred_equal_to {
 224             bool operator ()( const T& t, const Q& q )
 225             { return t.n == q ; }
 226             bool operator ()( const Q& q, const T& t )
 227             { return q == t.n ; }
 228             bool operator ()( const T& t1, const T& t2 )
 229             { return t1.n == t2.n ; }
 230             bool operator ()( const Q& q1, const Q& q2 )
 231             { return q1 == q2 ; }
 232         };
 233
 234         typedef cds::opt::equal_to< pred_equal_to< foo, int > > opt_equal_to;
 235         \endcode
 236
 237         Generally, the default type for \p Functor is \p std::equal_to but it depends on the container used.
 238     */
 239     template <typename Functor>
 240     struct equal_to {
 241         //@cond
 242         template <typename Base> struct pack: public Base
 243         {
 244             typedef Functor equal_to;
 245         };
 246         //@endcond
 247     };
 248
 249     //@cond
 250     namespace details {
 251         template <typename Compare>
 252         struct make_equal_to_from_compare
 253         {
 254             typedef Compare compare_functor;
 255
 256             template <typename T, typename Q>
 257             bool operator()( T const& t, Q const& q ) const
 258             {
 259                 return compare_functor()(t, q) == 0;
 260             }
 261         };
 262
 263         template <typename Less>
 264         struct make_equal_to_from_less
 265         {
 266             typedef Less less_functor;
 267
 268             template <typename T, typename Q>
 269             bool operator()( T const& t, Q const& q ) const
 270             {
 271                 less_functor less;
 272                 return !less(t, q) && !less(q, t);
 273             }
 274         };
 275
 276         template <typename T, typename Traits, bool Forced = true>
 277         struct make_equal_to
 278         {
 279             typedef typename Traits::equal_to equal_to;
 280             typedef typename Traits::compare  compare;
 281             typedef typename Traits::less     less;
 282
 283             typedef typename std::conditional<
 284                 std::is_same< equal_to, opt::none >::value,
 285                 typename std::conditional<
 286                     std::is_same< compare, opt::none >::value,
 287                     typename std::conditional<
 288                         std::is_same< less, opt::none >::value,
 289                         typename std::conditional<
 290                             Forced,
 291                             std::equal_to<T>,
 292                             opt::none >::type,
 293                         make_equal_to_from_less< less > >::type,
 294                     make_equal_to_from_compare< compare > >::type,
 295                 equal_to
 296             >::type type;
 297         };
 298     }
 299     //@endcond
 300
 301 }}  // namespace cds::opt
 302
 303 #endif // #ifndef CDSLIB_OPT_COMPARE_H