File indexing completed on 2025-02-25 09:35:04
0001
0002
0003
0004
0005
0006
0007
0008
0009
0010 #ifndef BOOST_ALGORITHM_SEARCH_DETAIL_BM_TRAITS_HPP
0011 #define BOOST_ALGORITHM_SEARCH_DETAIL_BM_TRAITS_HPP
0012
0013 #include <climits> // for CHAR_BIT
0014 #include <vector>
0015 #include <iterator> // for std::iterator_traits
0016
0017 #include <boost/type_traits/make_unsigned.hpp>
0018 #include <boost/type_traits/is_integral.hpp>
0019 #include <boost/type_traits/remove_pointer.hpp>
0020 #include <boost/type_traits/remove_const.hpp>
0021
0022 #include <boost/array.hpp>
0023 #ifdef BOOST_NO_CXX11_HDR_UNORDERED_MAP
0024 #include <boost/unordered_map.hpp>
0025 #else
0026 #include <unordered_map>
0027 #endif
0028
0029 #include <boost/algorithm/searching/detail/debugging.hpp>
0030
0031 namespace boost { namespace algorithm { namespace detail {
0032
0033
0034
0035
0036 template<typename key_type, typename value_type, bool > class skip_table;
0037
0038
0039 template<typename key_type, typename value_type>
0040 class skip_table<key_type, value_type, false> {
0041 private:
0042 #ifdef BOOST_NO_CXX11_HDR_UNORDERED_MAP
0043 typedef boost::unordered_map<key_type, value_type> skip_map;
0044 #else
0045 typedef std::unordered_map<key_type, value_type> skip_map;
0046 #endif
0047 const value_type k_default_value;
0048 skip_map skip_;
0049
0050 public:
0051 skip_table ( std::size_t patSize, value_type default_value )
0052 : k_default_value ( default_value ), skip_ ( patSize ) {}
0053
0054 void insert ( key_type key, value_type val ) {
0055 skip_ [ key ] = val;
0056 }
0057
0058 value_type operator [] ( key_type key ) const {
0059 typename skip_map::const_iterator it = skip_.find ( key );
0060 return it == skip_.end () ? k_default_value : it->second;
0061 }
0062
0063 void PrintSkipTable () const {
0064 std::cout << "BM(H) Skip Table <unordered_map>:" << std::endl;
0065 for ( typename skip_map::const_iterator it = skip_.begin (); it != skip_.end (); ++it )
0066 if ( it->second != k_default_value )
0067 std::cout << " " << it->first << ": " << it->second << std::endl;
0068 std::cout << std::endl;
0069 }
0070 };
0071
0072
0073
0074 template<typename key_type, typename value_type>
0075 class skip_table<key_type, value_type, true> {
0076 private:
0077 typedef typename boost::make_unsigned<key_type>::type unsigned_key_type;
0078 typedef boost::array<value_type, 1U << (CHAR_BIT * sizeof(key_type))> skip_map;
0079 skip_map skip_;
0080 const value_type k_default_value;
0081 public:
0082 skip_table ( std::size_t , value_type default_value ) : k_default_value ( default_value ) {
0083 std::fill_n ( skip_.begin(), skip_.size(), default_value );
0084 }
0085
0086 void insert ( key_type key, value_type val ) {
0087 skip_ [ static_cast<unsigned_key_type> ( key ) ] = val;
0088 }
0089
0090 value_type operator [] ( key_type key ) const {
0091 return skip_ [ static_cast<unsigned_key_type> ( key ) ];
0092 }
0093
0094 void PrintSkipTable () const {
0095 std::cout << "BM(H) Skip Table <boost:array>:" << std::endl;
0096 for ( typename skip_map::const_iterator it = skip_.begin (); it != skip_.end (); ++it )
0097 if ( *it != k_default_value )
0098 std::cout << " " << std::distance (skip_.begin (), it) << ": " << *it << std::endl;
0099 std::cout << std::endl;
0100 }
0101 };
0102
0103 template<typename Iterator>
0104 struct BM_traits {
0105 typedef typename std::iterator_traits<Iterator>::difference_type value_type;
0106 typedef typename std::iterator_traits<Iterator>::value_type key_type;
0107 typedef boost::algorithm::detail::skip_table<key_type, value_type,
0108 boost::is_integral<key_type>::value && (sizeof(key_type)==1)> skip_table_t;
0109 };
0110
0111 }}}
0112
0113 #endif