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
25namespace boost {
26
27enum one_bit_color_type {
28 one_bit_white = 0,
29 one_bit_not_white = 1
30};
31
32template <>
33struct 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
41template<typename IndexMap = identity_property_map>
42struct 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
62template<typename IndexMap>
63inline one_bit_color_type
64get(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
73template<typename IndexMap>
74inline void
75put(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
91template<typename IndexMap>
92inline one_bit_color_map<IndexMap>
93make_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

source code of boost/boost/graph/one_bit_color_map.hpp