summaryrefslogtreecommitdiff
path: root/src/mongo/bson/mutable/algorithm.h
diff options
context:
space:
mode:
Diffstat (limited to 'src/mongo/bson/mutable/algorithm.h')
-rw-r--r--src/mongo/bson/mutable/algorithm.h453
1 files changed, 222 insertions, 231 deletions
diff --git a/src/mongo/bson/mutable/algorithm.h b/src/mongo/bson/mutable/algorithm.h
index 8646e429a0b..66cec29956a 100644
--- a/src/mongo/bson/mutable/algorithm.h
+++ b/src/mongo/bson/mutable/algorithm.h
@@ -38,264 +38,255 @@
namespace mongo {
namespace mutablebson {
- /** For an overview of mutable BSON, please see the file document.h in this directory.
- *
- * This file defines, in analogy with <algorithm>, a collection of useful algorithms for
- * use with mutable BSON classes. In particular, algorithms for searching, sorting,
- * indexed access, and counting are included.
- */
-
- /** 'findElement' searches rightward among the sibiling Elements of 'first', returning an
- * Element representing the first item matching the predicate 'predicate'. If no Element
- * matches, then the 'ok' method on the returned Element will return false.
- */
- template<typename ElementType, typename Predicate>
- inline ElementType findElement(ElementType first, Predicate predicate) {
- while (first.ok() && !predicate(first))
- first = first.rightSibling();
- return first;
- }
-
- /** A predicate for findElement that matches on the field name of Elements. */
- struct FieldNameEquals {
- // The lifetime of this object must be a subset of the lifetime of 'fieldName'.
- explicit FieldNameEquals(StringData fieldName)
- : fieldName(fieldName) {}
+/** For an overview of mutable BSON, please see the file document.h in this directory.
+ *
+ * This file defines, in analogy with <algorithm>, a collection of useful algorithms for
+ * use with mutable BSON classes. In particular, algorithms for searching, sorting,
+ * indexed access, and counting are included.
+ */
- bool operator()(const ConstElement& element) const {
- return (fieldName == element.getFieldName());
- }
+/** 'findElement' searches rightward among the sibiling Elements of 'first', returning an
+ * Element representing the first item matching the predicate 'predicate'. If no Element
+ * matches, then the 'ok' method on the returned Element will return false.
+ */
+template <typename ElementType, typename Predicate>
+inline ElementType findElement(ElementType first, Predicate predicate) {
+ while (first.ok() && !predicate(first))
+ first = first.rightSibling();
+ return first;
+}
+
+/** A predicate for findElement that matches on the field name of Elements. */
+struct FieldNameEquals {
+ // The lifetime of this object must be a subset of the lifetime of 'fieldName'.
+ explicit FieldNameEquals(StringData fieldName) : fieldName(fieldName) {}
+
+ bool operator()(const ConstElement& element) const {
+ return (fieldName == element.getFieldName());
+ }
- StringData fieldName;
- };
+ StringData fieldName;
+};
- /** An overload of findElement that delegates to the special implementation
- * Element::findElementNamed to reduce traffic across the Element API.
- */
- template<typename ElementType>
- inline ElementType findElement(ElementType first, FieldNameEquals predicate) {
- return first.ok() ? first.findElementNamed(predicate.fieldName) : first;
- }
+/** An overload of findElement that delegates to the special implementation
+ * Element::findElementNamed to reduce traffic across the Element API.
+ */
+template <typename ElementType>
+inline ElementType findElement(ElementType first, FieldNameEquals predicate) {
+ return first.ok() ? first.findElementNamed(predicate.fieldName) : first;
+}
+
+/** A convenience wrapper around findElement<ElementType, FieldNameEquals>. */
+template <typename ElementType>
+inline ElementType findElementNamed(ElementType first, StringData fieldName) {
+ return findElement(first, FieldNameEquals(fieldName));
+}
+
+/** Finds the first child under 'parent' that matches the given predicate. If no such child
+ * Element is found, the returned Element's 'ok' method will return false.
+ */
+template <typename ElementType, typename Predicate>
+inline ElementType findFirstChild(ElementType parent, Predicate predicate) {
+ return findElement(parent.leftchild(), predicate);
+}
- /** A convenience wrapper around findElement<ElementType, FieldNameEquals>. */
- template<typename ElementType>
- inline ElementType findElementNamed(ElementType first, StringData fieldName) {
- return findElement(first, FieldNameEquals(fieldName));
- }
+/** An overload of findFirstChild that delegates to the special implementation
+ * Element::findFirstChildNamed to reduce traffic across the Element API.
+ */
+template <typename ElementType>
+inline ElementType findFirstChild(ElementType parent, FieldNameEquals predicate) {
+ return parent.ok() ? parent.findFirstChildNamed(predicate.fieldName) : parent;
+}
- /** Finds the first child under 'parent' that matches the given predicate. If no such child
- * Element is found, the returned Element's 'ok' method will return false.
- */
- template<typename ElementType, typename Predicate>
- inline ElementType findFirstChild(ElementType parent, Predicate predicate) {
- return findElement(parent.leftchild(), predicate);
+/** Finds the first child under 'parent' that matches the given field name. If no such child
+ * Element is found, the returned Element's 'ok' method will return false.
+ */
+template <typename ElementType>
+inline ElementType findFirstChildNamed(ElementType parent, StringData fieldName) {
+ return findFirstChild(parent, FieldNameEquals(fieldName));
+}
+
+/** A less-than ordering for Elements that compares based on the Element field names. */
+class FieldNameLessThan {
+ // TODO: This should possibly derive from std::binary_function.
+public:
+ inline bool operator()(const ConstElement& left, const ConstElement& right) const {
+ return left.getFieldName() < right.getFieldName();
}
+};
- /** An overload of findFirstChild that delegates to the special implementation
- * Element::findFirstChildNamed to reduce traffic across the Element API.
- */
- template<typename ElementType>
- inline ElementType findFirstChild(ElementType parent, FieldNameEquals predicate) {
- return parent.ok() ? parent.findFirstChildNamed(predicate.fieldName) : parent;
+/** Sort any children of Element 'parent' by way of Comparator 'comp', which should provide
+ * an operator() that takes two const Element&'s and implements a strict weak ordering.
+ */
+template <typename Comparator>
+void sortChildren(Element parent, Comparator comp) {
+ // TODO: The following works, but obviously is not ideal.
+
+ // First, build a vector of the children.
+ std::vector<Element> children;
+ Element current = parent.leftChild();
+ while (current.ok()) {
+ children.push_back(current);
+ current = current.rightSibling();
}
- /** Finds the first child under 'parent' that matches the given field name. If no such child
- * Element is found, the returned Element's 'ok' method will return false.
- */
- template<typename ElementType>
- inline ElementType findFirstChildNamed(ElementType parent, StringData fieldName) {
- return findFirstChild(parent, FieldNameEquals(fieldName));
+ // Then, sort the child vector with our comparator.
+ std::sort(children.begin(), children.end(), comp);
+
+ // Finally, reorder the children of parent according to the ordering established in
+ // 'children'.
+ std::vector<Element>::iterator where = children.begin();
+ const std::vector<Element>::iterator end = children.end();
+ for (; where != end; ++where) {
+ // Detach from its current location.
+ where->remove();
+ // Make it the new rightmost element.
+ parent.pushBack(*where);
}
+}
- /** A less-than ordering for Elements that compares based on the Element field names. */
- class FieldNameLessThan {
- // TODO: This should possibly derive from std::binary_function.
- public:
- inline bool operator()(const ConstElement& left, const ConstElement& right) const {
- return left.getFieldName() < right.getFieldName();
- }
- };
-
- /** Sort any children of Element 'parent' by way of Comparator 'comp', which should provide
- * an operator() that takes two const Element&'s and implements a strict weak ordering.
- */
- template<typename Comparator>
- void sortChildren(Element parent, Comparator comp) {
- // TODO: The following works, but obviously is not ideal.
-
- // First, build a vector of the children.
- std::vector<Element> children;
- Element current = parent.leftChild();
- while (current.ok()) {
- children.push_back(current);
- current = current.rightSibling();
- }
-
- // Then, sort the child vector with our comparator.
- std::sort(children.begin(), children.end(), comp);
-
- // Finally, reorder the children of parent according to the ordering established in
- // 'children'.
- std::vector<Element>::iterator where = children.begin();
- const std::vector<Element>::iterator end = children.end();
- for( ; where != end; ++where ) {
- // Detach from its current location.
- where->remove();
- // Make it the new rightmost element.
- parent.pushBack(*where);
- }
- }
-
- /** 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;
- }
+/** 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) {
- }
+/** 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;
+ }
- 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) {
- }
+private:
+ const bool _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 woEqualTo {
- // TODO: This should possibly derive from std::binary_function.
- public:
- woEqualTo(const ConstElement& value, bool considerFieldName = true)
- : _value(value)
- , _considerFieldName(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& elt) const {
- return _value.compareWithElement(elt, _considerFieldName) == 0;
- }
- private:
- const ConstElement& _value;
- const bool _considerFieldName;
- };
-
- // NOTE: Originally, these truly were algorithms, in that they executed the loop over a
- // generic ElementType. However, these operations were later made intrinsic to
- // Element/Document for performance reasons. These functions hare here for backward
- // compatibility, and just delegate to the appropriate Element or ConstElement method of
- // the same name.
-
- /** 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) {
- return element.leftSibling(n);
+ inline bool operator()(const ConstElement& left, const ConstElement& right) const {
+ return left.compareWithElement(right, _considerFieldName) > 0;
}
- /** Return the element that is 'n' Elements to the right in the sibling chain of 'element'. */
- template<typename ElementType>
- ElementType getNthRightSibling(ElementType element, std::size_t n) {
- return element.rightSibling(n);
- }
+private:
+ const bool _considerFieldName;
+};
- /** Move 'n' Elements left or right in the sibling chain of 'element' */
- template<typename ElementType>
- ElementType getNthSibling(ElementType element, int n) {
- return (n < 0) ?
- getNthLeftSibling(element, -n) :
- getNthRightSibling(element, n);
- }
+/** 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) {}
- /** Get the child that is 'n' Elements to the right of 'element's left child. */
- template<typename ElementType>
- ElementType getNthChild(ElementType element, std::size_t n) {
- return element.findNthChild(n);
+ inline bool operator()(const ConstElement& left, const ConstElement& right) const {
+ return left.compareWithElement(right, _considerFieldName) == 0;
}
- /** Returns the number of valid siblings to the left of 'element'. */
- template<typename ElementType>
- std::size_t countSiblingsLeft(ElementType element) {
- return element.countSiblingsLeft();
- }
+private:
+ const bool _considerFieldName;
+};
- /** Returns the number of valid siblings to the right of 'element'. */
- template<typename ElementType>
- std::size_t countSiblingsRight(ElementType element) {
- return element.countSiblingsRight();
- }
+/** An equality predicate for elements that compares based on woCompare */
+class woEqualTo {
+ // TODO: This should possibly derive from std::binary_function.
+public:
+ woEqualTo(const ConstElement& value, bool considerFieldName = true)
+ : _value(value), _considerFieldName(considerFieldName) {}
- /** Return the number of children of 'element'. */
- template<typename ElementType>
- std::size_t countChildren(ElementType element) {
- return element.countChildren();
+ inline bool operator()(const ConstElement& elt) const {
+ return _value.compareWithElement(elt, _considerFieldName) == 0;
}
- /** Return the full (path) name of this element separating each name with the delim string. */
- template<typename ElementType>
- std::string getFullName(ElementType element, char delim = '.') {
- std::vector<StringData> names;
- ElementType curr = element;
- while(curr.ok() && curr.parent().ok()) {
- names.push_back(curr.getFieldName());
- curr = curr.parent();
- }
+private:
+ const ConstElement& _value;
+ const bool _considerFieldName;
+};
+
+// NOTE: Originally, these truly were algorithms, in that they executed the loop over a
+// generic ElementType. However, these operations were later made intrinsic to
+// Element/Document for performance reasons. These functions hare here for backward
+// compatibility, and just delegate to the appropriate Element or ConstElement method of
+// the same name.
+
+/** 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) {
+ return element.leftSibling(n);
+}
+
+/** Return the element that is 'n' Elements to the right in the sibling chain of 'element'. */
+template <typename ElementType>
+ElementType getNthRightSibling(ElementType element, std::size_t n) {
+ return element.rightSibling(n);
+}
+
+/** Move 'n' Elements left or right in the sibling chain of 'element' */
+template <typename ElementType>
+ElementType getNthSibling(ElementType element, int n) {
+ return (n < 0) ? getNthLeftSibling(element, -n) : getNthRightSibling(element, n);
+}
+
+/** Get the child that is 'n' Elements to the right of 'element's left child. */
+template <typename ElementType>
+ElementType getNthChild(ElementType element, std::size_t n) {
+ return element.findNthChild(n);
+}
+
+/** Returns the number of valid siblings to the left of 'element'. */
+template <typename ElementType>
+std::size_t countSiblingsLeft(ElementType element) {
+ return element.countSiblingsLeft();
+}
+
+/** Returns the number of valid siblings to the right of 'element'. */
+template <typename ElementType>
+std::size_t countSiblingsRight(ElementType element) {
+ return element.countSiblingsRight();
+}
+
+/** Return the number of children of 'element'. */
+template <typename ElementType>
+std::size_t countChildren(ElementType element) {
+ return element.countChildren();
+}
+
+/** Return the full (path) name of this element separating each name with the delim string. */
+template <typename ElementType>
+std::string getFullName(ElementType element, char delim = '.') {
+ std::vector<StringData> names;
+ ElementType curr = element;
+ while (curr.ok() && curr.parent().ok()) {
+ names.push_back(curr.getFieldName());
+ curr = curr.parent();
+ }
- mongoutils::str::stream name;
- bool first = true;
- for(std::vector<StringData>::reverse_iterator it = names.rbegin();
- it != names.rend();
- ++it) {
- if (!first)
- name << delim;
- name << *it;
- first = false;
- }
- return name;
+ mongoutils::str::stream name;
+ bool first = true;
+ for (std::vector<StringData>::reverse_iterator it = names.rbegin(); it != names.rend(); ++it) {
+ if (!first)
+ name << delim;
+ name << *it;
+ first = false;
}
-} // namespace mutablebson
-} // namespace mongo
+ return name;
+}
+} // namespace mutablebson
+} // namespace mongo