]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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: | |
51 | skip_table ( std::size_t patSize, value_type default_value ) | |
52 | : k_default_value ( default_value ), skip_ ( patSize ) {} | |
53 | ||
54 | void insert ( key_type key, value_type val ) { | |
55 | skip_ [ key ] = val; // Would skip_.insert (val) be better here? | |
56 | } | |
57 | ||
58 | 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 | ||
63 | 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: | |
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 | ||
86 | void insert ( key_type key, value_type val ) { | |
87 | skip_ [ static_cast<unsigned_key_type> ( key ) ] = val; | |
88 | } | |
89 | ||
90 | value_type operator [] ( key_type key ) const { | |
91 | return skip_ [ static_cast<unsigned_key_type> ( key ) ]; | |
92 | } | |
93 | ||
94 | 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 |