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/shared_array.hpp>
19#include <boost/config.hpp>
20#include <boost/assert.hpp>
21#include <algorithm>
22#include <limits>
23
24namespace boost {
25
26enum two_bit_color_type {
27 two_bit_white = 0,
28 two_bit_gray = 1,
29 two_bit_green = 2,
30 two_bit_black = 3
31};
32
33template <>
34struct color_traits<two_bit_color_type>
35{
36 static two_bit_color_type white() { return two_bit_white; }
37 static two_bit_color_type gray() { return two_bit_gray; }
38 static two_bit_color_type green() { return two_bit_green; }
39 static two_bit_color_type black() { return two_bit_black; }
40};
41
42
43template<typename IndexMap = identity_property_map>
44struct two_bit_color_map
45{
46 std::size_t n;
47 IndexMap index;
48 shared_array<unsigned char> data;
49
50 BOOST_STATIC_CONSTANT(int, bits_per_char = std::numeric_limits<unsigned char>::digits);
51 BOOST_STATIC_CONSTANT(int, elements_per_char = bits_per_char / 2);
52 typedef typename property_traits<IndexMap>::key_type key_type;
53 typedef two_bit_color_type value_type;
54 typedef void reference;
55 typedef read_write_property_map_tag category;
56
57 explicit two_bit_color_map(std::size_t n, const IndexMap& index = IndexMap())
58 : n(n), index(index), data(new unsigned char[(n + elements_per_char - 1) / elements_per_char])
59 {
60 // Fill to white
61 std::fill(data.get(), data.get() + (n + elements_per_char - 1) / elements_per_char, 0);
62 }
63};
64
65template<typename IndexMap>
66inline two_bit_color_type
67get(const two_bit_color_map<IndexMap>& pm,
68 typename property_traits<IndexMap>::key_type key)
69{
70 BOOST_STATIC_CONSTANT(int, elements_per_char = two_bit_color_map<IndexMap>::elements_per_char);
71 typename property_traits<IndexMap>::value_type i = get(pm.index, key);
72 BOOST_ASSERT ((std::size_t)i < pm.n);
73 std::size_t byte_num = i / elements_per_char;
74 std::size_t bit_position = ((i % elements_per_char) * 2);
75 return two_bit_color_type((pm.data.get()[byte_num] >> bit_position) & 3);
76}
77
78template<typename IndexMap>
79inline void
80put(const two_bit_color_map<IndexMap>& pm,
81 typename property_traits<IndexMap>::key_type key,
82 two_bit_color_type value)
83{
84 BOOST_STATIC_CONSTANT(int, elements_per_char = two_bit_color_map<IndexMap>::elements_per_char);
85 typename property_traits<IndexMap>::value_type i = get(pm.index, key);
86 BOOST_ASSERT ((std::size_t)i < pm.n);
87 BOOST_ASSERT (value >= 0 && value < 4);
88 std::size_t byte_num = i / elements_per_char;
89 std::size_t bit_position = ((i % elements_per_char) * 2);
90 pm.data.get()[byte_num] =
91 (unsigned char)
92 ((pm.data.get()[byte_num] & ~(3 << bit_position))
93 | (value << bit_position));
94}
95
96template<typename IndexMap>
97inline two_bit_color_map<IndexMap>
98make_two_bit_color_map(std::size_t n, const IndexMap& index_map)
99{
100 return two_bit_color_map<IndexMap>(n, index_map);
101}
102
103} // end namespace boost
104
105#endif // BOOST_TWO_BIT_COLOR_MAP_HPP
106
107#ifdef BOOST_GRAPH_USE_MPI
108# include <boost/graph/distributed/two_bit_color_map.hpp>
109#endif
110

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