1 /*
2    Copyright (c) Marshall Clow 2010-2012.
3 
4    Distributed under the Boost Software License, Version 1.0. (See accompanying
5    file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
6 
7     For more information, see http://www.boost.org
8 */
9 
10 #ifndef BOOST_ALGORITHM_SEARCH_DETAIL_BM_TRAITS_HPP
11 #define BOOST_ALGORITHM_SEARCH_DETAIL_BM_TRAITS_HPP
12 
13 #include <climits>      // for CHAR_BIT
14 #include <vector>
15 #include <iterator>     // for std::iterator_traits
16 
17 #include <boost/type_traits/make_unsigned.hpp>
18 #include <boost/type_traits/is_integral.hpp>
19 #include <boost/type_traits/remove_pointer.hpp>
20 #include <boost/type_traits/remove_const.hpp>
21 
22 #include <boost/array.hpp>
23 #ifdef BOOST_NO_CXX11_HDR_UNORDERED_MAP
24 #include <boost/unordered_map.hpp>
25 #else
26 #include <unordered_map>
27 #endif
28 
29 #include <boost/algorithm/searching/detail/debugging.hpp>
30 
31 namespace boost { namespace algorithm { namespace detail {
32 
33 //
34 //  Default implementations of the skip tables for B-M and B-M-H
35 //
36     template<typename key_type, typename value_type, bool /*useArray*/> class skip_table;
37 
38 //  General case for data searching other than bytes; use a map
39     template<typename key_type, typename value_type>
40     class skip_table<key_type, value_type, false> {
41     private:
42 #ifdef BOOST_NO_CXX11_HDR_UNORDERED_MAP
43         typedef boost::unordered_map<key_type, value_type> skip_map;
44 #else
45         typedef std::unordered_map<key_type, value_type> skip_map;
46 #endif
47         const value_type k_default_value;
48         skip_map skip_;
49 
50     public:
skip_table(std::size_t patSize,value_type default_value)51         skip_table ( std::size_t patSize, value_type default_value )
52             : k_default_value ( default_value ), skip_ ( patSize ) {}
53 
insert(key_type key,value_type val)54         void insert ( key_type key, value_type val ) {
55             skip_ [ key ] = val;    // Would skip_.insert (val) be better here?
56             }
57 
operator [](key_type key) const58         value_type operator [] ( key_type key ) const {
59             typename skip_map::const_iterator it = skip_.find ( key );
60             return it == skip_.end () ? k_default_value : it->second;
61             }
62 
PrintSkipTable() const63         void PrintSkipTable () const {
64             std::cout << "BM(H) Skip Table <unordered_map>:" << std::endl;
65             for ( typename skip_map::const_iterator it = skip_.begin (); it != skip_.end (); ++it )
66                 if ( it->second != k_default_value )
67                     std::cout << "  " << it->first << ": " << it->second << std::endl;
68             std::cout << std::endl;
69             }
70         };
71 
72 
73 //  Special case small numeric values; use an array
74     template<typename key_type, typename value_type>
75     class skip_table<key_type, value_type, true> {
76     private:
77         typedef typename boost::make_unsigned<key_type>::type unsigned_key_type;
78         typedef boost::array<value_type, 1U << (CHAR_BIT * sizeof(key_type))> skip_map;
79         skip_map skip_;
80         const value_type k_default_value;
81     public:
skip_table(std::size_t,value_type default_value)82         skip_table ( std::size_t /*patSize*/, value_type default_value ) : k_default_value ( default_value ) {
83             std::fill_n ( skip_.begin(), skip_.size(), default_value );
84             }
85 
insert(key_type key,value_type val)86         void insert ( key_type key, value_type val ) {
87             skip_ [ static_cast<unsigned_key_type> ( key ) ] = val;
88             }
89 
operator [](key_type key) const90         value_type operator [] ( key_type key ) const {
91             return skip_ [ static_cast<unsigned_key_type> ( key ) ];
92             }
93 
PrintSkipTable() const94         void PrintSkipTable () const {
95             std::cout << "BM(H) Skip Table <boost:array>:" << std::endl;
96             for ( typename skip_map::const_iterator it = skip_.begin (); it != skip_.end (); ++it )
97                 if ( *it != k_default_value )
98                     std::cout << "  " << std::distance (skip_.begin (), it) << ": " << *it << std::endl;
99             std::cout << std::endl;
100             }
101         };
102 
103     template<typename Iterator>
104     struct BM_traits {
105         typedef typename std::iterator_traits<Iterator>::difference_type value_type;
106         typedef typename std::iterator_traits<Iterator>::value_type key_type;
107         typedef boost::algorithm::detail::skip_table<key_type, value_type,
108                 boost::is_integral<key_type>::value && (sizeof(key_type)==1)> skip_table_t;
109         };
110 
111 }}} // namespaces
112 
113 #endif  //  BOOST_ALGORITHM_SEARCH_DETAIL_BM_TRAITS_HPP
114