boost/graph/one_bit_color_map.hpp

0001 // Copyright (C) 2005-2010 The Trustees of Indiana University.
0002
0003 // Distributed under the Boost Software License, Version 1.0.
0004 // (See accompanying file LICENSE_1_0.txt or copy at
0005 // http://www.boost.org/LICENSE_1_0.txt)
0006
0007 //  Authors: Jeremiah Willcock
0008 //           Douglas Gregor
0009 //           Andrew Lumsdaine
0010
0011 // One bit per color property map (gray and black are the same, green is not
0012 // supported)
0013
0014 #ifndef BOOST_ONE_BIT_COLOR_MAP_HPP
0015 #define BOOST_ONE_BIT_COLOR_MAP_HPP
0016
0017 #include <boost/property_map/property_map.hpp>
0018 #include <boost/graph/properties.hpp>
0019 #include <boost/graph/detail/mpi_include.hpp>
0020 #include <boost/shared_array.hpp>
0021 #include <boost/config.hpp>
0022 #include <boost/assert.hpp>
0023 #include <algorithm>
0024 #include <limits>
0025
0026 namespace boost
0027 {
0028
0029 enum one_bit_color_type
0030 {
0031     one_bit_white = 0,
0032     one_bit_not_white = 1
0033 };
0034
0035 template <> struct color_traits< one_bit_color_type >
0036 {
0037     static one_bit_color_type white() { return one_bit_white; }
0038     static one_bit_color_type gray() { return one_bit_not_white; }
0039     static one_bit_color_type black() { return one_bit_not_white; }
0040 };
0041
0042 template < typename IndexMap = identity_property_map > struct one_bit_color_map
0043 {
0044     BOOST_STATIC_CONSTANT(
0045         int, bits_per_char = std::numeric_limits< unsigned char >::digits);
0046     std::size_t n;
0047     IndexMap index;
0048     shared_array< unsigned char > data;
0049
0050     typedef typename property_traits< IndexMap >::key_type key_type;
0051     typedef one_bit_color_type value_type;
0052     typedef void reference;
0053     typedef read_write_property_map_tag category;
0054
0055     explicit one_bit_color_map(
0056         std::size_t n, const IndexMap& index = IndexMap())
0057     : n(n)
0058     , index(index)
0059     , data(new unsigned char[(n + bits_per_char - 1) / bits_per_char]())
0060     {
0061     }
0062 };
0063
0064 template < typename IndexMap >
0065 inline one_bit_color_type get(const one_bit_color_map< IndexMap >& pm,
0066     typename property_traits< IndexMap >::key_type key)
0067 {
0068     BOOST_STATIC_CONSTANT(
0069         int, bits_per_char = one_bit_color_map< IndexMap >::bits_per_char);
0070     typename property_traits< IndexMap >::value_type i = get(pm.index, key);
0071     BOOST_ASSERT((std::size_t)i < pm.n);
0072     return one_bit_color_type(
0073         (pm.data.get()[i / bits_per_char] >> (i % bits_per_char)) & 1);
0074 }
0075
0076 template < typename IndexMap >
0077 inline void put(const one_bit_color_map< IndexMap >& pm,
0078     typename property_traits< IndexMap >::key_type key,
0079     one_bit_color_type value)
0080 {
0081     BOOST_STATIC_CONSTANT(
0082         int, bits_per_char = one_bit_color_map< IndexMap >::bits_per_char);
0083     typename property_traits< IndexMap >::value_type i = get(pm.index, key);
0084     BOOST_ASSERT((std::size_t)i < pm.n);
0085     BOOST_ASSERT(value >= 0 && value < 2);
0086     std::size_t byte_num = i / bits_per_char;
0087     std::size_t bit_position = (i % bits_per_char);
0088     pm.data.get()[byte_num]
0089         = (unsigned char)((pm.data.get()[byte_num] & ~(1 << bit_position))
0090             | (value << bit_position));
0091 }
0092
0093 template < typename IndexMap >
0094 inline one_bit_color_map< IndexMap > make_one_bit_color_map(
0095     std::size_t n, const IndexMap& index_map)
0096 {
0097     return one_bit_color_map< IndexMap >(n, index_map);
0098 }
0099
0100 } // end namespace boost
0101
0102 #include BOOST_GRAPH_MPI_INCLUDE(<boost/graph/distributed/one_bit_color_map.hpp>)
0103
0104 #endif // BOOST_ONE_BIT_COLOR_MAP_HPP