boost/graph/two_bit_color_map.hpp

0001 // Copyright (C) 2005-2006 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 // Two bit per color property map
0012
0013 #ifndef BOOST_TWO_BIT_COLOR_MAP_HPP
0014 #define BOOST_TWO_BIT_COLOR_MAP_HPP
0015
0016 #include <boost/property_map/property_map.hpp>
0017 #include <boost/graph/properties.hpp>
0018 #include <boost/graph/detail/mpi_include.hpp>
0019 #include <boost/shared_array.hpp>
0020 #include <boost/config.hpp>
0021 #include <boost/assert.hpp>
0022 #include <algorithm>
0023 #include <limits>
0024
0025 namespace boost
0026 {
0027
0028 enum two_bit_color_type
0029 {
0030     two_bit_white = 0,
0031     two_bit_gray = 1,
0032     two_bit_green = 2,
0033     two_bit_black = 3
0034 };
0035
0036 template <> struct color_traits< two_bit_color_type >
0037 {
0038     static two_bit_color_type white() { return two_bit_white; }
0039     static two_bit_color_type gray() { return two_bit_gray; }
0040     static two_bit_color_type green() { return two_bit_green; }
0041     static two_bit_color_type black() { return two_bit_black; }
0042 };
0043
0044 template < typename IndexMap = identity_property_map > struct two_bit_color_map
0045 {
0046     std::size_t n;
0047     IndexMap index;
0048     shared_array< unsigned char > data;
0049
0050     BOOST_STATIC_CONSTANT(
0051         int, bits_per_char = std::numeric_limits< unsigned char >::digits);
0052     BOOST_STATIC_CONSTANT(int, elements_per_char = bits_per_char / 2);
0053     typedef typename property_traits< IndexMap >::key_type key_type;
0054     typedef two_bit_color_type value_type;
0055     typedef void reference;
0056     typedef read_write_property_map_tag category;
0057
0058     explicit two_bit_color_map(
0059         std::size_t n, const IndexMap& index = IndexMap())
0060     : n(n)
0061     , index(index)
0062     , data(new unsigned char[(n + elements_per_char - 1) / elements_per_char]())
0063     {
0064     }
0065 };
0066
0067 template < typename IndexMap >
0068 inline two_bit_color_type get(const two_bit_color_map< IndexMap >& pm,
0069     typename property_traits< IndexMap >::key_type key)
0070 {
0071     BOOST_STATIC_CONSTANT(int,
0072         elements_per_char = two_bit_color_map< IndexMap >::elements_per_char);
0073     typename property_traits< IndexMap >::value_type i = get(pm.index, key);
0074     BOOST_ASSERT((std::size_t)i < pm.n);
0075     std::size_t byte_num = i / elements_per_char;
0076     std::size_t bit_position = ((i % elements_per_char) * 2);
0077     return two_bit_color_type((pm.data.get()[byte_num] >> bit_position) & 3);
0078 }
0079
0080 template < typename IndexMap >
0081 inline void put(const two_bit_color_map< IndexMap >& pm,
0082     typename property_traits< IndexMap >::key_type key,
0083     two_bit_color_type value)
0084 {
0085     BOOST_STATIC_CONSTANT(int,
0086         elements_per_char = two_bit_color_map< IndexMap >::elements_per_char);
0087     typename property_traits< IndexMap >::value_type i = get(pm.index, key);
0088     BOOST_ASSERT((std::size_t)i < pm.n);
0089     BOOST_ASSERT(value >= 0 && value < 4);
0090     std::size_t byte_num = i / elements_per_char;
0091     std::size_t bit_position = ((i % elements_per_char) * 2);
0092     pm.data.get()[byte_num]
0093         = (unsigned char)((pm.data.get()[byte_num] & ~(3 << bit_position))
0094             | (value << bit_position));
0095 }
0096
0097 template < typename IndexMap >
0098 inline two_bit_color_map< IndexMap > make_two_bit_color_map(
0099     std::size_t n, const IndexMap& index_map)
0100 {
0101     return two_bit_color_map< IndexMap >(n, index_map);
0102 }
0103
0104 } // end namespace boost
0105
0106 #include BOOST_GRAPH_MPI_INCLUDE(<boost/graph/distributed/two_bit_color_map.hpp>)
0107
0108 #endif // BOOST_TWO_BIT_COLOR_MAP_HPP