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
31namespace 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
114

source code of boost/libs/algorithm/include/boost/algorithm/searching/detail/bm_traits.hpp