1 | // Copyright (C) 2005-2010 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 | // One bit per color property map (gray and black are the same, green is not |
12 | // supported) |
13 | |
14 | #ifndef BOOST_ONE_BIT_COLOR_MAP_HPP |
15 | #define BOOST_ONE_BIT_COLOR_MAP_HPP |
16 | |
17 | #include <boost/property_map/property_map.hpp> |
18 | #include <boost/graph/properties.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 one_bit_color_type { |
28 | one_bit_white = 0, |
29 | one_bit_not_white = 1 |
30 | }; |
31 | |
32 | template <> |
33 | struct color_traits<one_bit_color_type> |
34 | { |
35 | static one_bit_color_type white() { return one_bit_white; } |
36 | static one_bit_color_type gray() { return one_bit_not_white; } |
37 | static one_bit_color_type black() { return one_bit_not_white; } |
38 | }; |
39 | |
40 | |
41 | template<typename IndexMap = identity_property_map> |
42 | struct one_bit_color_map |
43 | { |
44 | BOOST_STATIC_CONSTANT(int, bits_per_char = std::numeric_limits<unsigned char>::digits); |
45 | std::size_t n; |
46 | IndexMap index; |
47 | shared_array<unsigned char> data; |
48 | |
49 | typedef typename property_traits<IndexMap>::key_type key_type; |
50 | typedef one_bit_color_type value_type; |
51 | typedef void reference; |
52 | typedef read_write_property_map_tag category; |
53 | |
54 | explicit one_bit_color_map(std::size_t n, const IndexMap& index = IndexMap()) |
55 | : n(n), index(index), data(new unsigned char[(n + bits_per_char - 1) / bits_per_char]) |
56 | { |
57 | // Fill to white |
58 | std::fill(first: data.get(), last: data.get() + (n + bits_per_char - 1) / bits_per_char, value: 0); |
59 | } |
60 | }; |
61 | |
62 | template<typename IndexMap> |
63 | inline one_bit_color_type |
64 | get(const one_bit_color_map<IndexMap>& pm, |
65 | typename property_traits<IndexMap>::key_type key) |
66 | { |
67 | BOOST_STATIC_CONSTANT(int, bits_per_char = one_bit_color_map<IndexMap>::bits_per_char); |
68 | typename property_traits<IndexMap>::value_type i = get(pm.index, key); |
69 | BOOST_ASSERT ((std::size_t)i < pm.n); |
70 | return one_bit_color_type((pm.data.get()[i / bits_per_char] >> (i % bits_per_char)) & 1); |
71 | } |
72 | |
73 | template<typename IndexMap> |
74 | inline void |
75 | put(const one_bit_color_map<IndexMap>& pm, |
76 | typename property_traits<IndexMap>::key_type key, |
77 | one_bit_color_type value) |
78 | { |
79 | BOOST_STATIC_CONSTANT(int, bits_per_char = one_bit_color_map<IndexMap>::bits_per_char); |
80 | typename property_traits<IndexMap>::value_type i = get(pm.index, key); |
81 | BOOST_ASSERT ((std::size_t)i < pm.n); |
82 | BOOST_ASSERT (value >= 0 && value < 2); |
83 | std::size_t byte_num = i / bits_per_char; |
84 | std::size_t bit_position = (i % bits_per_char); |
85 | pm.data.get()[byte_num] = |
86 | (unsigned char) |
87 | ((pm.data.get()[byte_num] & ~(1 << bit_position)) |
88 | | (value << bit_position)); |
89 | } |
90 | |
91 | template<typename IndexMap> |
92 | inline one_bit_color_map<IndexMap> |
93 | make_one_bit_color_map(std::size_t n, const IndexMap& index_map) |
94 | { |
95 | return one_bit_color_map<IndexMap>(n, index_map); |
96 | } |
97 | |
98 | } // end namespace boost |
99 | |
100 | #endif // BOOST_ONE_BIT_COLOR_MAP_HPP |
101 | |
102 | #ifdef BOOST_GRAPH_USE_MPI |
103 | # include <boost/graph/distributed/one_bit_color_map.hpp> |
104 | #endif |
105 | |