[Boost-commit] svn:boost r60198 - in trunk/boost: graph graph/detail pending

Subject: [Boost-commit] svn:boost r60198 - in trunk/boost: graph graph/detail pending
From: jewillco_at_[hidden]
Date: 2010-03-05 13:27:44

Author: jewillco
Date: 2010-03-05 13:27:43 EST (Fri, 05 Mar 2010)
New Revision: 60198
URL: http://svn.boost.org/trac/boost/changeset/60198

Log:
Added in container_traits and adjacency_list patches to fix unordered container issues (patch from #3972); fixes #3972
Text files modified: 
   trunk/boost/graph/adjacency_list.hpp        |    13 ++++++                                  
   trunk/boost/graph/detail/adjacency_list.hpp |    11 +++--                                   
   trunk/boost/pending/container_traits.hpp    |    74 ++++++++++++++++++++++++++++++++++++--- 
   3 files changed, 86 insertions(+), 12 deletions(-)

Modified: trunk/boost/graph/adjacency_list.hpp
==============================================================================
--- trunk/boost/graph/adjacency_list.hpp	(original)
+++ trunk/boost/graph/adjacency_list.hpp	2010-03-05 13:27:43 EST (Fri, 05 Mar 2010)
@@ -1,6 +1,7 @@
 //=======================================================================
 // Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
-// Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
+// Copyright 2010 Thomas Claveirole
+// Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek, Thomas Claveirole
 //
 // Distributed under the Boost Software License, Version 1.0. (See
 // accompanying file LICENSE_1_0.txt or copy at
@@ -254,6 +255,16 @@
     typedef disallow_parallel_edge_tag type;
   };
 
+  template <>
+  struct parallel_edge_traits<hash_multisetS> {
+    typedef allow_parallel_edge_tag type;
+  };
+
+  template <>
+  struct parallel_edge_traits<hash_multimapS> {
+    typedef allow_parallel_edge_tag type;
+  };
+
   namespace detail {
     template <class Directed> struct is_random_access {
       enum { value = false};

Modified: trunk/boost/graph/detail/adjacency_list.hpp
==============================================================================
--- trunk/boost/graph/detail/adjacency_list.hpp	(original)
+++ trunk/boost/graph/detail/adjacency_list.hpp	2010-03-05 13:27:43 EST (Fri, 05 Mar 2010)
@@ -1,7 +1,8 @@
 // -*- c++ -*-
 //=======================================================================
 // Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
-// Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
+// Copyright 2010 Thomas Claveirole
+// Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek, Thomas Claveirole
 //
 // Distributed under the Boost Software License, Version 1.0. (See
 // accompanying file LICENSE_1_0.txt or copy at
@@ -1633,6 +1634,7 @@
       const Graph& g = static_cast<const Graph&>(g_);
       return g_.edge_dispatch(g, u, v, Cat());
     }
+
     template <class Config, class Base>
     inline std::pair<typename Config::out_edge_iterator,
                      typename Config::out_edge_iterator>
@@ -1648,10 +1650,9 @@
       typename Config::OutEdgeList& el = g.out_edge_list(u);
       typename Config::OutEdgeList::iterator first, last;
       typename Config::EdgeContainer fake_edge_container;
-      tie(first, last) =
-        std::equal_range(el.begin(), el.end(),
-                         StoredEdge(v, fake_edge_container.end(),
-                                    &fake_edge_container));
+      tie(first, last) = graph_detail::
+        equal_range(el, StoredEdge(v, fake_edge_container.end(),
+                                   &fake_edge_container));
       return std::make_pair(out_edge_iterator(first, u),
                             out_edge_iterator(last, u));
     }

Modified: trunk/boost/pending/container_traits.hpp
==============================================================================
--- trunk/boost/pending/container_traits.hpp	(original)
+++ trunk/boost/pending/container_traits.hpp	2010-03-05 13:27:43 EST (Fri, 05 Mar 2010)
@@ -1,4 +1,5 @@
 //  (C) Copyright Jeremy Siek 2004 
+//  (C) Copyright Thomas Claveirole 2010
 //  Distributed under the Boost Software License, Version 1.0. (See
 //  accompanying file LICENSE_1_0.txt or copy at
 //  http://www.boost.org/LICENSE_1_0.txt)
@@ -267,12 +268,22 @@
   template <class Key, class Eq, class Hash, class Alloc> 
   struct container_traits< boost::unordered_set<Key,Eq,Hash,Alloc> > {
     typedef set_tag category;
-    typedef stable_tag iterator_stability; // is this right?
+    typedef unstable_tag iterator_stability;
   };
   template <class Key, class T, class Eq, class Hash, class Alloc>
   struct container_traits< boost::unordered_map<Key,T,Eq,Hash,Alloc> > {
     typedef map_tag category;
-    typedef stable_tag iterator_stability; // is this right?
+    typedef unstable_tag iterator_stability;
+  };
+  template <class Key, class Eq, class Hash, class Alloc>
+  struct container_traits< boost::unordered_multiset<Key,Eq,Hash,Alloc> > {
+    typedef multiset_tag category;
+    typedef unstable_tag iterator_stability;
+  };
+  template <class Key, class T, class Eq, class Hash, class Alloc>
+  struct container_traits< boost::unordered_multimap<Key,T,Eq,Hash,Alloc> > {
+    typedef multimap_tag category;
+    typedef unstable_tag iterator_stability;
   };
 #endif
   template <class Key, class Eq, class Hash, class Alloc>
@@ -284,12 +295,31 @@
   { return map_tag(); }
 
   template <class Key, class Eq, class Hash, class Alloc>
-  stable_tag iterator_stability(const boost::unordered_set<Key,Eq,Hash,Alloc>&)
-  { return stable_tag(); }
+  unstable_tag iterator_stability(const boost::unordered_set<Key,Eq,Hash,Alloc>&)
+  { return unstable_tag(); }
 
   template <class Key, class T, class Eq, class Hash, class Alloc>
-  stable_tag iterator_stability(const boost::unordered_map<Key,T,Eq,Hash,Alloc>&)
-  { return stable_tag(); }
+  unstable_tag iterator_stability(const boost::unordered_map<Key,T,Eq,Hash,Alloc>&)
+  { return unstable_tag(); }
+  template <class Key, class Eq, class Hash, class Alloc>
+  multiset_tag
+  container_category(const boost::unordered_multiset<Key,Eq,Hash,Alloc>&)
+  { return multiset_tag(); }
+
+  template <class Key, class T, class Eq, class Hash, class Alloc>
+  multimap_tag
+  container_category(const boost::unordered_multimap<Key,T,Eq,Hash,Alloc>&)
+  { return multimap_tag(); }
+
+  template <class Key, class Eq, class Hash, class Alloc>
+  unstable_tag
+  iterator_stability(const boost::unordered_multiset<Key,Eq,Hash,Alloc>&)
+  { return unstable_tag(); }
+
+  template <class Key, class T, class Eq, class Hash, class Alloc>
+  unstable_tag
+  iterator_stability(const boost::unordered_multimap<Key,T,Eq,Hash,Alloc>&)
+  { return unstable_tag(); }
 #endif
 
 
@@ -403,6 +433,38 @@
     return push_dispatch(c, v, container_category(c));
   }
 
+  // Equal range
+  template <class Container,
+            class LessThanComparable,
+            class ContainerCategory>
+  std::pair<typename Container::iterator, typename Container::iterator>
+  equal_range_dispatch(Container& c,
+                       const LessThanComparable& value,
+                       const ContainerCategory&)
+  {
+    // c must be sorted for std::equal_range to behave properly.
+    return std::equal_range(c.begin(), c.end(), value);
+  }
+
+  template <class AssociativeContainer, class LessThanComparable>
+  std::pair<typename AssociativeContainer::iterator,
+            typename AssociativeContainer::iterator>
+  equal_range_dispatch(AssociativeContainer& c,
+                       const LessThanComparable& value,
+                       const associative_container_tag&)
+  {
+    return c.equal_range(value);
+  }
+
+  template <class Container, class LessThanComparable>
+  std::pair<typename Container::iterator, typename Container::iterator>
+  equal_range(Container& c,
+              const LessThanComparable& value)
+  {
+    return equal_range_dispatch(c, value,
+                                graph_detail::container_category(c));
+  }
+
 }} // namespace boost::graph_detail
 
 #if BOOST_WORKAROUND(BOOST_MSVC, < 1300)