Line data Source code
1 : // Copyright (C) 2005-2006 The Trustees of Indiana University. 2 : 3 : // Distributed under the Boost Software License, Version 1.0. 4 : // (See accompanying file LICENSE_1_0.txt or copy at 5 : // http://www.boost.org/LICENSE_1_0.txt) 6 : 7 : // Authors: Jeremiah Willcock 8 : // Douglas Gregor 9 : // Andrew Lumsdaine 10 : 11 : // Two bit per color property map 12 : 13 : #ifndef BOOST_TWO_BIT_COLOR_MAP_HPP 14 : #define BOOST_TWO_BIT_COLOR_MAP_HPP 15 : 16 : #include <boost/property_map/property_map.hpp> 17 : #include <boost/graph/properties.hpp> 18 : #include <boost/graph/detail/mpi_include.hpp> 19 : #include <boost/shared_array.hpp> 20 : #include <boost/config.hpp> 21 : #include <boost/assert.hpp> 22 : #include <algorithm> 23 : #include <limits> 24 : 25 : namespace boost { 26 : 27 : enum two_bit_color_type { 28 : two_bit_white = 0, 29 : two_bit_gray = 1, 30 : two_bit_green = 2, 31 : two_bit_black = 3 32 : }; 33 : 34 : template <> 35 : struct color_traits<two_bit_color_type> 36 : { 37 0 : static two_bit_color_type white() { return two_bit_white; } 38 0 : static two_bit_color_type gray() { return two_bit_gray; } 39 : static two_bit_color_type green() { return two_bit_green; } 40 0 : static two_bit_color_type black() { return two_bit_black; } 41 : }; 42 : 43 : 44 : template<typename IndexMap = identity_property_map> 45 0 : struct two_bit_color_map 46 : { 47 : std::size_t n; 48 : IndexMap index; 49 : shared_array<unsigned char> data; 50 : 51 : BOOST_STATIC_CONSTANT(int, bits_per_char = std::numeric_limits<unsigned char>::digits); 52 : BOOST_STATIC_CONSTANT(int, elements_per_char = bits_per_char / 2); 53 : typedef typename property_traits<IndexMap>::key_type key_type; 54 : typedef two_bit_color_type value_type; 55 : typedef void reference; 56 : typedef read_write_property_map_tag category; 57 : 58 0 : explicit two_bit_color_map(std::size_t n, const IndexMap& index = IndexMap()) 59 0 : : n(n), index(index), data(new unsigned char[(n + elements_per_char - 1) / elements_per_char]) 60 : { 61 : // Fill to white 62 0 : std::fill(data.get(), data.get() + (n + elements_per_char - 1) / elements_per_char, 0); 63 0 : } 64 : }; 65 : 66 : template<typename IndexMap> 67 : inline two_bit_color_type 68 0 : get(const two_bit_color_map<IndexMap>& pm, 69 : typename property_traits<IndexMap>::key_type key) 70 : { 71 : BOOST_STATIC_CONSTANT(int, elements_per_char = two_bit_color_map<IndexMap>::elements_per_char); 72 0 : typename property_traits<IndexMap>::value_type i = get(pm.index, key); 73 0 : BOOST_ASSERT ((std::size_t)i < pm.n); 74 0 : std::size_t byte_num = i / elements_per_char; 75 0 : std::size_t bit_position = ((i % elements_per_char) * 2); 76 0 : return two_bit_color_type((pm.data.get()[byte_num] >> bit_position) & 3); 77 : } 78 : 79 : template<typename IndexMap> 80 : inline void 81 0 : put(const two_bit_color_map<IndexMap>& pm, 82 : typename property_traits<IndexMap>::key_type key, 83 : two_bit_color_type value) 84 : { 85 : BOOST_STATIC_CONSTANT(int, elements_per_char = two_bit_color_map<IndexMap>::elements_per_char); 86 0 : typename property_traits<IndexMap>::value_type i = get(pm.index, key); 87 0 : BOOST_ASSERT ((std::size_t)i < pm.n); 88 0 : BOOST_ASSERT (value >= 0 && value < 4); 89 0 : std::size_t byte_num = i / elements_per_char; 90 0 : std::size_t bit_position = ((i % elements_per_char) * 2); 91 0 : pm.data.get()[byte_num] = 92 : (unsigned char) 93 0 : ((pm.data.get()[byte_num] & ~(3 << bit_position)) 94 0 : | (value << bit_position)); 95 0 : } 96 : 97 : template<typename IndexMap> 98 : inline two_bit_color_map<IndexMap> 99 : make_two_bit_color_map(std::size_t n, const IndexMap& index_map) 100 : { 101 : return two_bit_color_map<IndexMap>(n, index_map); 102 : } 103 : 104 : } // end namespace boost 105 : 106 : #include BOOST_GRAPH_MPI_INCLUDE(<boost/graph/distributed/two_bit_color_map.hpp>) 107 : 108 : #endif // BOOST_TWO_BIT_COLOR_MAP_HPP