[Boost-commit] svn:boost r71354 - in trunk: boost/unordered/detail libs/unordered/test/unordered

Subject: [Boost-commit] svn:boost r71354 - in trunk: boost/unordered/detail libs/unordered/test/unordered
From: dnljms_at_[hidden]
Date: 2011-04-17 12:23:26

Author: danieljames
Date: 2011-04-17 12:23:25 EDT (Sun, 17 Apr 2011)
New Revision: 71354
URL: http://svn.boost.org/trac/boost/changeset/71354

Log:
Unordered: Implement C++0x equality.
Text files modified: 
   trunk/boost/unordered/detail/equivalent.hpp            |    71 +++++++++++++++++++++++++++++++++------ 
   trunk/boost/unordered/detail/table.hpp                 |     2 +                                       
   trunk/boost/unordered/detail/unique.hpp                |     4 -                                       
   trunk/libs/unordered/test/unordered/equality_tests.cpp |     8 ++-                                     
   4 files changed, 68 insertions(+), 17 deletions(-)

Modified: trunk/boost/unordered/detail/equivalent.hpp
==============================================================================
--- trunk/boost/unordered/detail/equivalent.hpp	(original)
+++ trunk/boost/unordered/detail/equivalent.hpp	2011-04-17 12:23:25 EDT (Sun, 17 Apr 2011)
@@ -55,23 +55,72 @@
             for(node_ptr n1 = this->buckets_[this->bucket_count_].next_; n1;)
             {
                 node_ptr n2 = other.find_matching_node(n1);
-                if(!n2) return false;
-    
+                if (!n2) return false;
                 node_ptr end1 = node::next_group(n1);
                 node_ptr end2 = node::next_group(n2);
-    
-                do {
-                    if(!extractor::compare_mapped(
-                        node::get_value(n1), node::get_value(n2)))
-                        return false;
-                    n1 = n1->next_;
-                    n2 = n2->next_;
-                } while(n1 != end1 && n2 != end2);
-                if(n1 != end1 || n2 != end2) return false;
+                if (!group_equals(n1, end1, n2, end2)) return false;
+                n1 = end1;    
             }
     
             return true;
         }
+        
+        static bool group_equals(node_ptr n1, node_ptr end1,
+                node_ptr n2, node_ptr end2)
+        {
+            for(;;)
+            {
+                if (node::get_value(n1) != node::get_value(n2))
+                    break;
+
+                n1 = n1->next_;
+                n2 = n2->next_;
+            
+                if (n1 == end1) return n2 == end2;
+                if (n2 == end2) return false;
+            }
+            
+            for(node_ptr n1a = n1, n2a = n2;;)
+            {
+                n1a = n1a->next_;
+                n2a = n2a->next_;
+
+                if (n1a == end1)
+                {
+                    if (n2a == end2) break;
+                    else return false;
+                }
+                if (n2a == end2) return false;
+            }
+
+            node_ptr start = n1;
+            for(;n1 != end2; n1 = n1->next_)
+            {
+                value_type const& v = node::get_value(n1);
+                if (find(start, n1, v)) continue;
+                std::size_t matches = count(n2, end2, v);
+                if (!matches or matches != 1 + count(n1->next_, end1, v))
+                    return false;
+            }
+            
+            return true;
+        }
+        
+        static bool find(node_ptr n, node_ptr end, value_type const& v)
+        {
+            for(;n != end; n = n->next_)
+                if (node::get_value(n) == v)
+                    return true;
+            return false;
+        }
+        
+        static std::size_t count(node_ptr n, node_ptr end, value_type const& v)
+        {
+            std::size_t count = 0;
+            for(;n != end; n = n->next_)
+                if (node::get_value(n) == v) ++count;
+            return count;
+        }
 
         ////////////////////////////////////////////////////////////////////////
         // A convenience method for adding nodes.

Modified: trunk/boost/unordered/detail/table.hpp
==============================================================================
--- trunk/boost/unordered/detail/table.hpp	(original)
+++ trunk/boost/unordered/detail/table.hpp	2011-04-17 12:23:25 EDT (Sun, 17 Apr 2011)
@@ -625,6 +625,7 @@
         typedef cl_iterator<A, Unique> const_local_iterator;
 
         friend class cl_iterator<A, Unique>;
+        
         node_ptr ptr_;
         std::size_t bucket_;
         std::size_t bucket_count_;
@@ -683,6 +684,7 @@
         typedef BOOST_DEDUCED_TYPENAME buckets::node_ptr node_ptr;
         typedef BOOST_DEDUCED_TYPENAME buckets::node node;
         typedef l_iterator<A, Unique> local_iterator;
+
         friend class l_iterator<A, Unique>;
 
         node_ptr ptr_;

Modified: trunk/boost/unordered/detail/unique.hpp
==============================================================================
--- trunk/boost/unordered/detail/unique.hpp	(original)
+++ trunk/boost/unordered/detail/unique.hpp	2011-04-17 12:23:25 EDT (Sun, 17 Apr 2011)
@@ -57,9 +57,7 @@
                 n1; n1 = n1->next_)
             {
                 node_ptr n2 = other.find_matching_node(n1);
-                if(!BOOST_UNORDERED_BORLAND_BOOL(n2)) return false;
-                if(!extractor::compare_mapped(
-                    node::get_value(n1), node::get_value(n2)))
+                if(!n2 || node::get_value(n1) != node::get_value(n2))
                     return false;
             }
     

Modified: trunk/libs/unordered/test/unordered/equality_tests.cpp
==============================================================================
--- trunk/libs/unordered/test/unordered/equality_tests.cpp	(original)
+++ trunk/libs/unordered/test/unordered/equality_tests.cpp	2011-04-17 12:23:25 EDT (Sun, 17 Apr 2011)
@@ -136,15 +136,17 @@
         UNORDERED_EQUALITY_MULTIMAP_TEST(
             ((1)(1))((1)(1)), !=, ((1)(1))((1)(2)))
         UNORDERED_EQUALITY_MULTIMAP_TEST(
-            ((1)(2))((1)(1)), !=, ((1)(1))((1)(2)))
+            ((1)(2))((1)(1)), ==, ((1)(1))((1)(2)))
+        UNORDERED_EQUALITY_MULTIMAP_TEST(
+            ((1)(2))((1)(1)), !=, ((1)(1))((1)(3)))
     }
 
     UNORDERED_AUTO_TEST(equality_predicate_test)
     {
         UNORDERED_EQUALITY_SET_TEST(
-            (1), ==, (1001))
+            (1), !=, (1001))
         UNORDERED_EQUALITY_MAP_TEST(
-            ((1)(2))((1001)(1)), ==, ((1001)(2))((1)(1)))
+            ((1)(2))((1001)(1)), !=, ((1001)(2))((1)(1)))
     }
 
     // Test that equality still works when the two containers have