cds/opt/compare.h

   1 /*
   2     This file is a part of libcds - Concurrent Data Structures library
   3
   4     (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2017
   5
   6     Source code repo: http://github.com/khizmax/libcds/
   7     Download: http://sourceforge.net/projects/libcds/files/
   8
   9     Redistribution and use in source and binary forms, with or without
  10     modification, are permitted provided that the following conditions are met:
  11
  12     * Redistributions of source code must retain the above copyright notice, this
  13       list of conditions and the following disclaimer.
  14
  15     * Redistributions in binary form must reproduce the above copyright notice,
  16       this list of conditions and the following disclaimer in the documentation
  17       and/or other materials provided with the distribution.
  18
  19     THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
  20     AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  21     IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
  22     DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
  23     FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  24     DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
  25     SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
  26     CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
  27     OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  28     OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  29 */
  30
  31 #ifndef CDSLIB_OPT_COMPARE_H
  32 #define CDSLIB_OPT_COMPARE_H
  33
  34 /*
  35     Editions:
  36         2011.05.05 khizmax  Created
  37 */
  38
  39 #include <type_traits>
  40 #include <functional>
  41 #include <string>
  42 #include <cds/opt/options.h>
  43
  44 namespace cds { namespace opt {
  45
  46     /// [type-option] Option setter for key comparing
  47     /**
  48         The option sets a type of a functor to compare keys.
  49         For comparing two keys \p k1 and \p k2 the functor must return:
  50         - 1 if <tt> k1 > k2 </tt>
  51         - 0 if <tt> k1 == k2 </tt>
  52         - -1 if <tt> k1 < k2 </tt>
  53
  54         \p Functor is a functor with following interface:
  55         \code
  56         template <typename T>
  57         struct Comparator {
  58             int operator ()(const T& r1, const T& r2)
  59             {
  60                 // Comparator body
  61             }
  62         };
  63         \endcode
  64         Note that the functor must return \p int, not a \p bool value.
  65
  66         There are predefined type for \p Functor:
  67         - the functor \p opt::v::less_comparator that implements comparing functor through \p std::less predicate.
  68         - the specialization of \p opt::v::less_comparator functor intended for the string comparison
  69
  70         You may implement your own comparing functor that satisfies \p Functor interface.
  71
  72         About relation between \p %opt::less and \p %opt::compare option setters see \p opt::less description.
  73     */
  74     template <typename Functor>
  75     struct compare {
  76         //@cond
  77         template <typename Base> struct pack: public Base
  78         {
  79             typedef Functor compare;
  80         };
  81         //@endcond
  82     };
  83
  84     namespace v {
  85
  86         /// Comparator based on \p std::less predicate
  87         /**
  88             This functor is predefined type for \p opt::compare option setter.
  89             It is based on \p std::less predicate.
  90         */
  91         template <typename T>
  92         struct less_comparator {
  93             /// Operator that compares two value of type \p T
  94             int operator()(T const& v1, T const& v2)
  95             {
  96                 if ( std::less<T>()( v1, v2 ))
  97                     return -1;
  98                 if ( std::less<T>()( v2, v1 ))
  99                     return 1;
 100                 return 0;
 101             }
 102         };
 103
 104         /// Comparator specialization for \p std::string
 105         /**
 106             This functor uses \p std::string::compare() method instead of \p std::less predicate.
 107         */
 108         template <typename T, typename Traits, typename Alloc>
 109         struct less_comparator< std::basic_string<T, Traits, Alloc> >
 110         {
 111             //@cond
 112             typedef std::basic_string<T, Traits, Alloc> string_type;
 113             int operator()(string_type const& v1, string_type const& v2)
 114             {
 115                 return v1.compare( v2 );
 116             }
 117             //@endcond
 118         };
 119     }   // namespace v
 120
 121     /// [type-option] Option setter for \p less predicate
 122     /**
 123         The option sets a binary predicate that tests whether a value of a specified type is less than another value of that type.
 124         \p Functor interface is similar to \p std::less predicate interface.
 125         The standard predicate \p std::less can act as \p Functor:
 126         \code typedef cds::opt::less< std::less< int > > opt_less \endcode
 127
 128         In addition, the option setter may sets non-standard 2-type predicate (\p std::binary_function):
 129         \code
 130
 131         struct foo {
 132             int n;
 133         };
 134
 135         template <typename T, typename Q>
 136         struct pred_less {
 137             bool operator ()( const T& t, const Q& q )
 138             { return t.n < q ; }
 139             bool operator ()( const Q& q, const T& t )
 140             { return q < t.n ; }
 141             bool operator ()( const T& t1, const T& t2 )
 142             { return t1.n < t2.n ; }
 143             bool operator ()( const Q& q1, const Q& q2 )
 144             { return q1 < q2 ; }
 145         };
 146
 147         typedef cds::opt::less< pred_less< foo, int > > opt_less;
 148         \endcode
 149
 150         Generally, the default type for \p Functor is \p std::less but it depends on the container used.
 151
 152         \par Relation between opt::less and opt::compare option setters
 153         Unless otherwise specified, \p opt::compare option setter has high priority.
 154         If \p %opt::compare and \p %opt::less options are specified for a container, the \p %opt::compare option is used:
 155         \code
 156         // Suppose, a hypothetical map_type allows to specify
 157         // cds::opt::less and cds::opt::compare options
 158
 159         typedef map_type< std::string, int,
 160             cds::opt::compare< cds::opt::v::less_comparator< std::string > >,
 161             cds::opt::less< std::less< std::string > >
 162         > my_map_type;
 163
 164         // For my_map_type, the cds::opt::compare comparator will be used,
 165         // the cds::opt::less option is ignored without any warnings.
 166         \endcode
 167     */
 168     template <typename Functor>
 169     struct less {
 170         //@cond
 171         template <typename Base> struct pack: public Base
 172         {
 173             typedef Functor less;
 174         };
 175         //@endcond
 176     };
 177
 178     //@cond
 179     namespace details {
 180         template <typename Less>
 181         struct make_comparator_from_less
 182         {
 183             typedef Less less_functor;
 184
 185             template <typename T, typename Q>
 186             int operator ()( T const& t, Q const& q ) const
 187             {
 188                 less_functor f;
 189                 if ( f( t, q ))
 190                     return -1;
 191                 if ( f( q, t ))
 192                     return 1;
 193                 return 0;
 194             }
 195         };
 196
 197         template <typename T, typename Traits, typename DefaultCmp = make_comparator_from_less< std::less<T>> >
 198         struct make_comparator_from
 199         {
 200             typedef typename Traits::compare compare;
 201             typedef typename Traits::less less;
 202
 203             typedef typename std::conditional<
 204                 std::is_same< compare, opt::none >::value,
 205                 typename std::conditional<
 206                     std::is_same< less, opt::none >::value,
 207                     DefaultCmp,
 208                     make_comparator_from_less< less >
 209                 >::type,
 210                 compare
 211             >::type type;
 212         };
 213
 214
 215         template <typename T, typename Traits, bool Forced = true >
 216         using make_comparator = make_comparator_from< T, Traits,
 217             typename std::conditional<
 218                 Forced,
 219                 make_comparator_from_less< std::less<T>>,
 220                 opt::none
 221             >::type >;
 222
 223         template <typename T, typename... Options>
 224         struct make_comparator_from_option_list
 225         {
 226             struct default_traits {
 227                 typedef opt::none   compare;
 228                 typedef opt::none   less;
 229             };
 230
 231             typedef typename make_comparator< T,
 232                 typename opt::make_options<
 233                     typename opt::find_type_traits< default_traits, Options... >::type
 234                     ,Options...
 235                 >::type
 236             >::type type;
 237         };
 238     }   // namespace details
 239     //@endcond
 240
 241     /// [type-option] Option setter for \p opt::equal_to predicate
 242     /**
 243         The option sets a binary predicate that tests whether a value of a specified type is equal to another value of that type.
 244         \p Functor interface is similar to \p std::equal_to predicate interface.
 245         The standard predicate \p std::equal_to can act as \p Functor:
 246         \code typedef cds::opt::equal_to< std::equal_to< int > > opt_equal_to \endcode
 247
 248         In addition, the option setter may sets non-standard 2-type (or even N-type) predicate (\p std::binary_function):
 249         \code
 250
 251         struct foo {
 252             int n;
 253         };
 254
 255         template <typename T, typename Q>
 256         struct pred_equal_to {
 257             bool operator ()( const T& t, const Q& q )
 258             { return t.n == q ; }
 259             bool operator ()( const Q& q, const T& t )
 260             { return q == t.n ; }
 261             bool operator ()( const T& t1, const T& t2 )
 262             { return t1.n == t2.n ; }
 263             bool operator ()( const Q& q1, const Q& q2 )
 264             { return q1 == q2 ; }
 265         };
 266
 267         typedef cds::opt::equal_to< pred_equal_to< foo, int > > opt_equal_to;
 268         \endcode
 269
 270         Generally, the default type for \p Functor is \p std::equal_to but it depends on the container used.
 271     */
 272     template <typename Functor>
 273     struct equal_to {
 274         //@cond
 275         template <typename Base> struct pack: public Base
 276         {
 277             typedef Functor equal_to;
 278         };
 279         //@endcond
 280     };
 281
 282     //@cond
 283     namespace details {
 284         template <typename Compare>
 285         struct make_equal_to_from_compare
 286         {
 287             typedef Compare compare_functor;
 288
 289             template <typename T, typename Q>
 290             bool operator()( T const& t, Q const& q ) const
 291             {
 292                 return compare_functor()(t, q) == 0;
 293             }
 294         };
 295
 296         template <typename Less>
 297         struct make_equal_to_from_less
 298         {
 299             typedef Less less_functor;
 300
 301             template <typename T, typename Q>
 302             bool operator()( T const& t, Q const& q ) const
 303             {
 304                 less_functor less;
 305                 return !less(t, q) && !less(q, t);
 306             }
 307         };
 308
 309         template <typename T, typename Traits, bool Forced = true>
 310         struct make_equal_to
 311         {
 312             typedef typename Traits::equal_to equal_to;
 313             typedef typename Traits::compare  compare;
 314             typedef typename Traits::less     less;
 315
 316             typedef typename std::conditional<
 317                 std::is_same< equal_to, opt::none >::value,
 318                 typename std::conditional<
 319                     std::is_same< compare, opt::none >::value,
 320                     typename std::conditional<
 321                         std::is_same< less, opt::none >::value,
 322                         typename std::conditional<
 323                             Forced,
 324                             std::equal_to<T>,
 325                             opt::none >::type,
 326                         make_equal_to_from_less< less > >::type,
 327                     make_equal_to_from_compare< compare > >::type,
 328                 equal_to
 329             >::type type;
 330         };
 331     }
 332     //@endcond
 333
 334 }}  // namespace cds::opt
 335
 336 #endif // #ifndef CDSLIB_OPT_COMPARE_H