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>> >
 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,
 189             typename std::conditional<
 190                 Forced,
 191                 make_comparator_from_less< std::less<T>>,
 192                 opt::none
 193             >::type >;
 194
 195         template <typename T, typename... Options>
 196         struct make_comparator_from_option_list
 197         {
 198             struct default_traits {
 199                 typedef opt::none   compare;
 200                 typedef opt::none   less;
 201             };
 202
 203             typedef typename make_comparator< T,
 204                 typename opt::make_options<
 205                     typename opt::find_type_traits< default_traits, Options... >::type
 206                     ,Options...
 207                 >::type
 208             >::type type;
 209         };
 210     }   // namespace details
 211     //@endcond
 212
 213     /// [type-option] Option setter for \p equal_to predicate
 214     /**
 215         The option sets a binary predicate that tests whether a value of a specified type is equal to another value of that type.
 216         \p Functor interface is similar to \p std::equal_to predicate interface.
 217         The standard predicate \p std::equal_to can act as \p Functor:
 218         \code typedef cds::opt::equal_to< std::equal_to< int > > opt_equal_to \endcode
 219
 220         In addition, the option setter may sets non-standard 2-type (or even N-type) predicate (\p std::binary_function):
 221         \code
 222
 223         struct foo {
 224             int n;
 225         };
 226
 227         template <typename T, typename Q>
 228         struct pred_equal_to {
 229             bool operator ()( const T& t, const Q& q )
 230             { return t.n == q ; }
 231             bool operator ()( const Q& q, const T& t )
 232             { return q == t.n ; }
 233             bool operator ()( const T& t1, const T& t2 )
 234             { return t1.n == t2.n ; }
 235             bool operator ()( const Q& q1, const Q& q2 )
 236             { return q1 == q2 ; }
 237         };
 238
 239         typedef cds::opt::equal_to< pred_equal_to< foo, int > > opt_equal_to;
 240         \endcode
 241
 242         Generally, the default type for \p Functor is \p std::equal_to but it depends on the container used.
 243     */
 244     template <typename Functor>
 245     struct equal_to {
 246         //@cond
 247         template <typename Base> struct pack: public Base
 248         {
 249             typedef Functor equal_to;
 250         };
 251         //@endcond
 252     };
 253
 254     //@cond
 255     namespace details {
 256         template <typename Compare>
 257         struct make_equal_to_from_compare
 258         {
 259             typedef Compare compare_functor;
 260
 261             template <typename T, typename Q>
 262             bool operator()( T const& t, Q const& q ) const
 263             {
 264                 return compare_functor()(t, q) == 0;
 265             }
 266         };
 267
 268         template <typename Less>
 269         struct make_equal_to_from_less
 270         {
 271             typedef Less less_functor;
 272
 273             template <typename T, typename Q>
 274             bool operator()( T const& t, Q const& q ) const
 275             {
 276                 less_functor less;
 277                 return !less(t, q) && !less(q, t);
 278             }
 279         };
 280
 281         template <typename T, typename Traits, bool Forced = true>
 282         struct make_equal_to
 283         {
 284             typedef typename Traits::equal_to equal_to;
 285             typedef typename Traits::compare  compare;
 286             typedef typename Traits::less     less;
 287
 288             typedef typename std::conditional<
 289                 std::is_same< equal_to, opt::none >::value,
 290                 typename std::conditional<
 291                     std::is_same< compare, opt::none >::value,
 292                     typename std::conditional<
 293                         std::is_same< less, opt::none >::value,
 294                         typename std::conditional<
 295                             Forced,
 296                             std::equal_to<T>,
 297                             opt::none >::type,
 298                         make_equal_to_from_less< less > >::type,
 299                     make_equal_to_from_compare< compare > >::type,
 300                 equal_to
 301             >::type type;
 302         };
 303     }
 304     //@endcond
 305
 306 }}  // namespace cds::opt
 307
 308 #endif // #ifndef CDSLIB_OPT_COMPARE_H