SERVER-7174 Add a new algorithm to de-duplicate children

2 files changed, 69 insertions, 0 deletions

diff --git a/src/mongo/bson/mutable/algorithm.h b/src/mongo/bson/mutable/algorithm.h
index 4b3e993a0c4..1f82497abb8 100644
--- a/src/mongo/bson/mutable/algorithm.h
+++ b/src/mongo/bson/mutable/algorithm.h
@@ -111,6 +111,68 @@ namespace mutablebson {
         }
     }
 
+    /** Remove any consecutive children that compare as identical according to 'comp'. The
+     *  children must be sorted (see sortChildren, above), and the equality comparator here
+     *  must be compatible with the comparator used for the sort.
+     */
+    template<typename EqualityComparator>
+    void deduplicateChildren(Element parent, EqualityComparator equal) {
+        Element current = parent.leftChild();
+        while (current.ok()) {
+            Element next = current.rightSibling();
+            if (next.ok() && equal(current, next)) {
+                next.remove();
+            } else {
+                current = next;
+            }
+        }
+    }
+
+    /** A less-than ordering for Elements that compares based on woCompare */
+    class woLess {
+        // TODO: This should possibly derive from std::binary_function.
+    public:
+        woLess(bool considerFieldName = true)
+            : _considerFieldName(considerFieldName) {
+        }
+
+        inline bool operator()(const ConstElement& left, const ConstElement& right) const {
+            return left.compareWithElement(right, _considerFieldName) < 0;
+        }
+    private:
+        const bool _considerFieldName;
+    };
+
+    /** A greater-than ordering for Elements that compares based on woCompare */
+    class woGreater {
+        // TODO: This should possibly derive from std::binary_function.
+    public:
+        woGreater(bool considerFieldName = true)
+            : _considerFieldName(considerFieldName) {
+        }
+
+        inline bool operator()(const ConstElement& left, const ConstElement& right) const {
+            return left.compareWithElement(right, _considerFieldName) > 0;
+        }
+    private:
+        const bool _considerFieldName;
+    };
+
+    /** An equality predicate for elements that compares based on woCompare */
+    class woEqual {
+        // TODO: This should possibly derive from std::binary_function.
+    public:
+        woEqual(bool considerFieldName = true)
+            : _considerFieldName(considerFieldName) {
+        }
+
+        inline bool operator()(const ConstElement& left, const ConstElement& right) const {
+            return left.compareWithElement(right, _considerFieldName) == 0;
+        }
+    private:
+        const bool _considerFieldName;
+    };
+
     /** Return the element that is 'n' Elements to the left in the sibling chain of 'element'. */
     template<typename ElementType>
     ElementType getNthLeftSibling(ElementType element, std::size_t n) {
diff --git a/src/mongo/bson/mutable/mutable_bson_algo_test.cpp b/src/mongo/bson/mutable/mutable_bson_algo_test.cpp
index 8ca7658f4e6..900f6aa8f0a 100644
--- a/src/mongo/bson/mutable/mutable_bson_algo_test.cpp
+++ b/src/mongo/bson/mutable/mutable_bson_algo_test.cpp
@@ -19,6 +19,7 @@
 
 #include "mongo/bson/mutable/document.h"
 #include "mongo/bson/mutable/mutable_bson_test_utils.h"
+#include "mongo/db/json.h"
 #include "mongo/platform/basic.h"
 #include "mongo/unittest/unittest.h"
 
@@ -258,4 +259,10 @@ namespace {
         ASSERT_EQUALS(countChildren(threeChildren), 3u);
     }
 
+    TEST(DeduplicateTest, ManyDuplicates) {
+        Document doc(mongo::fromjson("{ x : [ 1, 2, 2, 3, 3, 3, 4, 4, 4 ] }"));
+        deduplicateChildren(doc.root().leftChild(), woEqual(false));
+        ASSERT_TRUE(checkDoc(doc, mongo::fromjson("{x : [ 1, 2, 3, 4 ]}")));
+    }
+
 } // namespace