boost/graph/two_bit_color_map.hpp

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