Back to home page

EIC code displayed by LXR

 
 

    


File indexing completed on 2025-02-25 09:35:04

0001 /* 
0002    Copyright (c) Marshall Clow 2010-2012.
0003 
0004    Distributed under the Boost Software License, Version 1.0. (See accompanying
0005    file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
0006 
0007     For more information, see http://www.boost.org
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 //  Default implementations of the skip tables for B-M and B-M-H
0035 //
0036     template<typename key_type, typename value_type, bool /*useArray*/> class skip_table;
0037 
0038 //  General case for data searching other than bytes; use a map
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;    // Would skip_.insert (val) be better here?
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 //  Special case small numeric values; use an array
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 /*patSize*/, 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 }}} // namespaces
0112 
0113 #endif  //  BOOST_ALGORITHM_SEARCH_DETAIL_BM_TRAITS_HPP