[Boost-commit] svn:boost r60079 - in trunk/boost/graph: . distributed

Subject: [Boost-commit] svn:boost r60079 - in trunk/boost/graph: . distributed
From: jewillco_at_[hidden]
Date: 2010-03-02 14:53:49

Author: jewillco
Date: 2010-03-02 14:53:47 EST (Tue, 02 Mar 2010)
New Revision: 60079
URL: http://svn.boost.org/trac/boost/changeset/60079

Log:
Changed to allow characters that are not 8-bit; added one-bit-per-color color map
Added:
   trunk/boost/graph/distributed/one_bit_color_map.hpp
      - copied, changed from r60077, /trunk/boost/graph/distributed/two_bit_color_map.hpp
   trunk/boost/graph/one_bit_color_map.hpp
      - copied, changed from r60077, /trunk/boost/graph/two_bit_color_map.hpp
Text files modified: 
   trunk/boost/graph/distributed/one_bit_color_map.hpp |    56 ++++++++++++++--------------            
   trunk/boost/graph/one_bit_color_map.hpp             |    75 +++++++++++++++++++++------------------ 
   trunk/boost/graph/two_bit_color_map.hpp             |    20 ++++++++--                              
   3 files changed, 83 insertions(+), 68 deletions(-)

Copied: trunk/boost/graph/distributed/one_bit_color_map.hpp (from r60077, /trunk/boost/graph/distributed/two_bit_color_map.hpp)
==============================================================================
--- /trunk/boost/graph/distributed/two_bit_color_map.hpp	(original)
+++ trunk/boost/graph/distributed/one_bit_color_map.hpp	2010-03-02 14:53:47 EST (Tue, 02 Mar 2010)
@@ -1,4 +1,4 @@
-// Copyright (C) 2006 The Trustees of Indiana University.
+// Copyright (C) 2006-2010 The Trustees of Indiana University.
 
 // Use, modification and distribution is subject to the Boost Software
 // License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
@@ -8,26 +8,26 @@
 //           Jeremiah Willcock
 //           Andrew Lumsdaine
 
-// Distributed version of the two-bit color map
-#ifndef BOOST_DISTRIBUTED_TWO_BIT_COLOR_MAP_HPP
-#define BOOST_DISTRIBUTED_TWO_BIT_COLOR_MAP_HPP
+// Distributed version of the one-bit color map
+#ifndef BOOST_DISTRIBUTED_ONE_BIT_COLOR_MAP_HPP
+#define BOOST_DISTRIBUTED_ONE_BIT_COLOR_MAP_HPP
 
 #ifndef BOOST_GRAPH_USE_MPI
 #error "Parallel BGL files should not be included unless <boost/graph/use_mpi.hpp> has been included"
 #endif
 
-#include <boost/graph/two_bit_color_map.hpp>
+#include <boost/graph/one_bit_color_map.hpp>
 #include <boost/property_map/parallel/distributed_property_map.hpp>
 #include <boost/property_map/parallel/local_property_map.hpp>
 
 namespace boost {
 
 template<typename ProcessGroup, typename GlobalMap, typename StorageMap>
-class two_bit_color_map<local_property_map<ProcessGroup,GlobalMap,StorageMap> >
+class one_bit_color_map<local_property_map<ProcessGroup,GlobalMap,StorageMap> >
   : public parallel::distributed_property_map<ProcessGroup, GlobalMap,
-                                              two_bit_color_map<StorageMap> >
+                                              one_bit_color_map<StorageMap> >
 {
-  typedef two_bit_color_map<StorageMap> local_map;
+  typedef one_bit_color_map<StorageMap> local_map;
 
   typedef parallel::distributed_property_map<ProcessGroup, GlobalMap, 
                                              local_map >
@@ -37,7 +37,7 @@
     index_map_type;
 
 public:
-  two_bit_color_map(std::size_t inital_size, 
+  one_bit_color_map(std::size_t inital_size, 
                     const index_map_type& index = index_map_type())
     : inherited(index.process_group(),  index.global(),
                 local_map(inital_size, index.base())) { }
@@ -47,31 +47,31 @@
 };
 
 template<typename ProcessGroup, typename GlobalMap, typename StorageMap>
-inline two_bit_color_type
-get(two_bit_color_map<local_property_map<ProcessGroup,GlobalMap,StorageMap> >
+inline one_bit_color_type
+get(one_bit_color_map<local_property_map<ProcessGroup,GlobalMap,StorageMap> >
       const& pm,
-    typename two_bit_color_map<GlobalMap>::key_type key)
+    typename one_bit_color_map<GlobalMap>::key_type key)
 {
   return get(pm.base(), key);
 }
 
 template<typename ProcessGroup, typename GlobalMap, typename StorageMap>
 inline void
-put(two_bit_color_map<local_property_map<ProcessGroup,GlobalMap,StorageMap> >
+put(one_bit_color_map<local_property_map<ProcessGroup,GlobalMap,StorageMap> >
       const& pm, 
-    typename two_bit_color_map<GlobalMap>::key_type key,
-    two_bit_color_type value)
+    typename one_bit_color_map<GlobalMap>::key_type key,
+    one_bit_color_type value)
 {
   put(pm.base(), key, value);
 }
 
 template<typename ProcessGroup, typename GlobalMap, typename StorageMap>
-class two_bit_color_map<parallel::distributed_property_map<
+class one_bit_color_map<parallel::distributed_property_map<
                           ProcessGroup, GlobalMap, StorageMap> > 
   : public parallel::distributed_property_map<
-             ProcessGroup, GlobalMap, two_bit_color_map<StorageMap> >
+             ProcessGroup, GlobalMap, one_bit_color_map<StorageMap> >
 {
-  typedef two_bit_color_map<StorageMap> local_map;
+  typedef one_bit_color_map<StorageMap> local_map;
 
   typedef parallel::distributed_property_map<ProcessGroup,GlobalMap,local_map>
     inherited;
@@ -81,7 +81,7 @@
     index_map_type;
 
 public:
-  two_bit_color_map(std::size_t inital_size, 
+  one_bit_color_map(std::size_t inital_size, 
                     const index_map_type& index = index_map_type())
     : inherited(index.process_group(),  index.global(),
                 local_map(inital_size, index.base())) { }
@@ -91,26 +91,26 @@
 };
 
 template<typename ProcessGroup, typename GlobalMap, typename StorageMap>
-inline two_bit_color_type
-get(two_bit_color_map<
+inline one_bit_color_type
+get(one_bit_color_map<
       parallel::distributed_property_map<
-        ProcessGroup, GlobalMap, two_bit_color_map<StorageMap> > > const& pm,
-    typename two_bit_color_map<GlobalMap>::key_type key)
+        ProcessGroup, GlobalMap, one_bit_color_map<StorageMap> > > const& pm,
+    typename one_bit_color_map<GlobalMap>::key_type key)
 {
   return get(pm.base(), key);
 }
 
 template<typename ProcessGroup, typename GlobalMap, typename StorageMap>
 inline void
-put(two_bit_color_map<
+put(one_bit_color_map<
       parallel::distributed_property_map<
-        ProcessGroup, GlobalMap, two_bit_color_map<StorageMap> > > const& pm, 
-    typename two_bit_color_map<GlobalMap>::key_type key,
-    two_bit_color_type value)
+        ProcessGroup, GlobalMap, one_bit_color_map<StorageMap> > > const& pm, 
+    typename one_bit_color_map<GlobalMap>::key_type key,
+    one_bit_color_type value)
 {
   put(pm.base(), key, value);
 }
 
 } // end namespace boost
 
-#endif // BOOST_DISTRIBUTED_TWO_BIT_COLOR_MAP_HPP
+#endif // BOOST_DISTRIBUTED_ONE_BIT_COLOR_MAP_HPP

Copied: trunk/boost/graph/one_bit_color_map.hpp (from r60077, /trunk/boost/graph/two_bit_color_map.hpp)
==============================================================================
--- /trunk/boost/graph/two_bit_color_map.hpp	(original)
+++ trunk/boost/graph/one_bit_color_map.hpp	2010-03-02 14:53:47 EST (Tue, 02 Mar 2010)
@@ -1,4 +1,4 @@
-// Copyright (C) 2005-2006 The Trustees of Indiana University.
+// Copyright (C) 2005-2010 The Trustees of Indiana University.
 
 // Distributed under the Boost Software License, Version 1.0.
 // (See accompanying file LICENSE_1_0.txt or copy at
@@ -8,93 +8,98 @@
 //           Douglas Gregor
 //           Andrew Lumsdaine
 
-// Two bit per color property map
+// One bit per color property map (gray and black are the same, green is not
+// supported)
 
-#ifndef BOOST_TWO_BIT_COLOR_MAP_HPP
-#define BOOST_TWO_BIT_COLOR_MAP_HPP
+#ifndef BOOST_ONE_BIT_COLOR_MAP_HPP
+#define BOOST_ONE_BIT_COLOR_MAP_HPP
 
 #include <boost/property_map/property_map.hpp>
 #include <boost/graph/properties.hpp>
 #include <boost/shared_array.hpp>
+#include <boost/config.hpp>
 #include <algorithm>
+#include <limits>
 
 namespace boost {
 
-enum two_bit_color_type { 
-  two_bit_white = 0, 
-  two_bit_gray  = 1, 
-  two_bit_green = 2, 
-  two_bit_black = 3 
+enum one_bit_color_type { 
+  one_bit_white     = 0, 
+  one_bit_not_white  = 1
 };
 
 template <>
-struct color_traits<two_bit_color_type>
+struct color_traits<one_bit_color_type>
 {
-  static two_bit_color_type white() { return two_bit_white; }
-  static two_bit_color_type gray()  { return two_bit_gray; }
-  static two_bit_color_type green() { return two_bit_green; }
-  static two_bit_color_type black() { return two_bit_black; }
+  static one_bit_color_type white() { return one_bit_white; }
+  static one_bit_color_type gray()  { return one_bit_not_white; }
+  static one_bit_color_type black() { return one_bit_not_white; }
 };
 
 
 template<typename IndexMap = identity_property_map>
-struct two_bit_color_map 
+struct one_bit_color_map 
 {
+  BOOST_STATIC_CONSTANT(int, bits_per_char = std::numeric_limits<unsigned char>::digits);
+  BOOST_STATIC_ASSERT(std::numeric_limits<unsigned char>::radix == 2);
+  BOOST_STATIC_ASSERT(bits_per_char > 0);
   std::size_t n;
   IndexMap index;
   shared_array<unsigned char> data;
 
   typedef typename property_traits<IndexMap>::key_type key_type;
-  typedef two_bit_color_type value_type;
+  typedef one_bit_color_type value_type;
   typedef void reference;
   typedef read_write_property_map_tag category;
 
-  explicit two_bit_color_map(std::size_t n, const IndexMap& index = IndexMap())
-    : n(n), index(index), data(new unsigned char[(n + 3) / 4])
+  explicit one_bit_color_map(std::size_t n, const IndexMap& index = IndexMap())
+    : n(n), index(index), data(new unsigned char[(n + bits_per_char - 1) / bits_per_char])
   {
     // Fill to white
-    std::fill(data.get(), data.get() + (n + 3) / 4, 0);
+    std::fill(data.get(), data.get() + (n + bits_per_char - 1) / bits_per_char, 0);
   }
 };
 
 template<typename IndexMap>
-inline two_bit_color_type
-get(const two_bit_color_map<IndexMap>& pm, 
-    typename two_bit_color_map<IndexMap>::key_type key) 
+inline one_bit_color_type
+get(const one_bit_color_map<IndexMap>& pm, 
+    typename one_bit_color_map<IndexMap>::key_type key) 
 {
+  BOOST_STATIC_CONSTANT(int, bits_per_char = one_bit_color_map<IndexMap>::bits_per_char);
   typename property_traits<IndexMap>::value_type i = get(pm.index, key);
   assert ((std::size_t)i < pm.n);
-  return two_bit_color_type((pm.data.get()[i / 4] >> ((i % 4) * 2)) & 3);
+  return one_bit_color_type((pm.data.get()[i / bits_per_char] >> (i % bits_per_char)) & 1);
 }
 
 template<typename IndexMap>
 inline void
-put(const two_bit_color_map<IndexMap>& pm, 
-    typename two_bit_color_map<IndexMap>::key_type key,
-    two_bit_color_type value)
+put(const one_bit_color_map<IndexMap>& pm, 
+    typename one_bit_color_map<IndexMap>::key_type key,
+    one_bit_color_type value)
 {
+  BOOST_STATIC_CONSTANT(int, bits_per_char = one_bit_color_map<IndexMap>::bits_per_char);
   typename property_traits<IndexMap>::value_type i = get(pm.index, key);
   assert ((std::size_t)i < pm.n);
-  assert (value >= 0 && value < 4);
-  std::size_t byte_num = i / 4;
-  std::size_t bit_position = ((i % 4) * 2);
+  assert (value >= 0 && value < 2);
+  std::size_t byte_num = i / bits_per_char;
+  std::size_t bit_position = (i % bits_per_char);
     pm.data.get()[byte_num] =
       (unsigned char)
-        ((pm.data.get()[byte_num] & ~(3 << bit_position))
+        ((pm.data.get()[byte_num] & ~(1 << bit_position))
          | (value << bit_position));
 }
 
 template<typename IndexMap>
-inline two_bit_color_map<IndexMap>
-make_two_bit_color_map(std::size_t n, const IndexMap& index_map)
+inline one_bit_color_map<IndexMap>
+make_one_bit_color_map(std::size_t n, const IndexMap& index_map)
 {
-  return two_bit_color_map<IndexMap>(n, index_map);
+  return one_bit_color_map<IndexMap>(n, index_map);
 }
 
 } // end namespace boost
 
-#endif // BOOST_TWO_BIT_COLOR_MAP_HPP
+#endif // BOOST_ONE_BIT_COLOR_MAP_HPP
 
 #ifdef BOOST_GRAPH_USE_MPI
-#  include <boost/graph/distributed/two_bit_color_map.hpp>
+#  include <boost/graph/distributed/one_bit_color_map.hpp>
 #endif

Modified: trunk/boost/graph/two_bit_color_map.hpp
==============================================================================
--- trunk/boost/graph/two_bit_color_map.hpp	(original)
+++ trunk/boost/graph/two_bit_color_map.hpp	2010-03-02 14:53:47 EST (Tue, 02 Mar 2010)
@@ -16,7 +16,9 @@
 #include <boost/property_map/property_map.hpp>
 #include <boost/graph/properties.hpp>
 #include <boost/shared_array.hpp>
+#include <boost/config.hpp>
 #include <algorithm>
+#include <limits>
 
 namespace boost {
 
@@ -44,16 +46,20 @@
   IndexMap index;
   shared_array<unsigned char> data;
 
+  BOOST_STATIC_CONSTANT(int, bits_per_char = std::numeric_limits<unsigned char>::digits);
+  BOOST_STATIC_CONSTANT(int, elements_per_char = bits_per_char / 2);
+  BOOST_STATIC_ASSERT(std::numeric_limits<unsigned char>::radix == 2);
+  BOOST_STATIC_ASSERT(elements_per_char > 0);
   typedef typename property_traits<IndexMap>::key_type key_type;
   typedef two_bit_color_type value_type;
   typedef void reference;
   typedef read_write_property_map_tag category;
 
   explicit two_bit_color_map(std::size_t n, const IndexMap& index = IndexMap())
-    : n(n), index(index), data(new unsigned char[(n + 3) / 4])
+    : n(n), index(index), data(new unsigned char[(n + elements_per_char - 1) / elements_per_char])
   {
     // Fill to white
-    std::fill(data.get(), data.get() + (n + 3) / 4, 0);
+    std::fill(data.get(), data.get() + (n + elements_per_char - 1) / elements_per_char, 0);
   }
 };
 
@@ -62,9 +68,12 @@
 get(const two_bit_color_map<IndexMap>& pm, 
     typename two_bit_color_map<IndexMap>::key_type key) 
 {
+  BOOST_STATIC_CONSTANT(int, elements_per_char = two_bit_color_map<IndexMap>::elements_per_char);
   typename property_traits<IndexMap>::value_type i = get(pm.index, key);
   assert ((std::size_t)i < pm.n);
-  return two_bit_color_type((pm.data.get()[i / 4] >> ((i % 4) * 2)) & 3);
+  std::size_t byte_num = i / elements_per_char;
+  std::size_t bit_position = ((i % elements_per_char) * 2);
+  return two_bit_color_type((pm.data.get()[byte_num] >> bit_position) & 3);
 }
 
 template<typename IndexMap>
@@ -73,11 +82,12 @@
     typename two_bit_color_map<IndexMap>::key_type key,
     two_bit_color_type value)
 {
+  BOOST_STATIC_CONSTANT(int, elements_per_char = two_bit_color_map<IndexMap>::elements_per_char);
   typename property_traits<IndexMap>::value_type i = get(pm.index, key);
   assert ((std::size_t)i < pm.n);
   assert (value >= 0 && value < 4);
-  std::size_t byte_num = i / 4;
-  std::size_t bit_position = ((i % 4) * 2);
+  std::size_t byte_num = i / elements_per_char;
+  std::size_t bit_position = ((i % elements_per_char) * 2);
     pm.data.get()[byte_num] =
       (unsigned char)
         ((pm.data.get()[byte_num] & ~(3 << bit_position))