MongoDB  2.7.0
algorithm.h
1 /* Copyright 2013 10gen Inc.
2  *
3  * Licensed under the Apache License, Version 2.0 (the "License");
4  * you may not use this file except in compliance with the License.
5  * You may obtain a copy of the License at
6  *
7  * http://www.apache.org/licenses/LICENSE-2.0
8  *
9  * Unless required by applicable law or agreed to in writing, software
10  * distributed under the License is distributed on an "AS IS" BASIS,
11  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12  * See the License for the specific language governing permissions and
13  * limitations under the License.
14  */
15 
16 #pragma once
17 
18 #include <cstddef>
19 #include <algorithm>
20 #include <vector>
21 
22 #include "mongo/bson/mutable/const_element.h"
23 #include "mongo/bson/mutable/element.h"
24 #include "mongo/util/mongoutils/str.h"
25 
26 namespace mongo {
27 namespace mutablebson {
28 
40  template<typename ElementType, typename Predicate>
41  inline ElementType findElement(ElementType first, Predicate predicate) {
42  while (first.ok() && !predicate(first))
43  first = first.rightSibling();
44  return first;
45  }
46 
48  struct FieldNameEquals {
49  // The lifetime of this object must be a subset of the lifetime of 'fieldName'.
50  explicit FieldNameEquals(const StringData& fieldName)
51  : fieldName(fieldName) {}
52 
53  bool operator()(const ConstElement& element) const {
54  return (fieldName == element.getFieldName());
55  }
56 
57  const StringData& fieldName;
58  };
59 
63  template<typename ElementType>
64  inline ElementType findElement(ElementType first, FieldNameEquals predicate) {
65  return first.ok() ? first.findElementNamed(predicate.fieldName) : first;
66  }
67 
69  template<typename ElementType>
70  inline ElementType findElementNamed(ElementType first, const StringData& fieldName) {
71  return findElement(first, FieldNameEquals(fieldName));
72  }
73 
77  template<typename ElementType, typename Predicate>
78  inline ElementType findFirstChild(ElementType parent, Predicate predicate) {
79  return findElement(parent.leftchild(), predicate);
80  }
81 
85  template<typename ElementType>
86  inline ElementType findFirstChild(ElementType parent, FieldNameEquals predicate) {
87  return parent.ok() ? parent.findFirstChildNamed(predicate.fieldName) : parent;
88  }
89 
93  template<typename ElementType>
94  inline ElementType findFirstChildNamed(ElementType parent, const StringData& fieldName) {
95  return findFirstChild(parent, FieldNameEquals(fieldName));
96  }
97 
100  // TODO: This should possibly derive from std::binary_function.
101  public:
102  inline bool operator()(const ConstElement& left, const ConstElement& right) const {
103  return left.getFieldName() < right.getFieldName();
104  }
105  };
106 
110  template<typename Comparator>
111  void sortChildren(Element parent, Comparator comp) {
112  // TODO: The following works, but obviously is not ideal.
113 
114  // First, build a vector of the children.
115  std::vector<Element> children;
116  Element current = parent.leftChild();
117  while (current.ok()) {
118  children.push_back(current);
119  current = current.rightSibling();
120  }
121 
122  // Then, sort the child vector with our comparator.
123  std::sort(children.begin(), children.end(), comp);
124 
125  // Finally, reorder the children of parent according to the ordering established in
126  // 'children'.
127  std::vector<Element>::iterator where = children.begin();
128  const std::vector<Element>::iterator end = children.end();
129  for( ; where != end; ++where ) {
130  // Detach from its current location.
131  where->remove();
132  // Make it the new rightmost element.
133  parent.pushBack(*where);
134  }
135  }
136 
141  template<typename EqualityComparator>
142  void deduplicateChildren(Element parent, EqualityComparator equal) {
143  Element current = parent.leftChild();
144  while (current.ok()) {
145  Element next = current.rightSibling();
146  if (next.ok() && equal(current, next)) {
147  next.remove();
148  } else {
149  current = next;
150  }
151  }
152  }
153 
155  class woLess {
156  // TODO: This should possibly derive from std::binary_function.
157  public:
158  woLess(bool considerFieldName = true)
159  : _considerFieldName(considerFieldName) {
160  }
161 
162  inline bool operator()(const ConstElement& left, const ConstElement& right) const {
163  return left.compareWithElement(right, _considerFieldName) < 0;
164  }
165  private:
166  const bool _considerFieldName;
167  };
168 
170  class woGreater {
171  // TODO: This should possibly derive from std::binary_function.
172  public:
173  woGreater(bool considerFieldName = true)
174  : _considerFieldName(considerFieldName) {
175  }
176 
177  inline bool operator()(const ConstElement& left, const ConstElement& right) const {
178  return left.compareWithElement(right, _considerFieldName) > 0;
179  }
180  private:
181  const bool _considerFieldName;
182  };
183 
185  class woEqual {
186  // TODO: This should possibly derive from std::binary_function.
187  public:
188  woEqual(bool considerFieldName = true)
189  : _considerFieldName(considerFieldName) {
190  }
191 
192  inline bool operator()(const ConstElement& left, const ConstElement& right) const {
193  return left.compareWithElement(right, _considerFieldName) == 0;
194  }
195  private:
196  const bool _considerFieldName;
197  };
198 
200  class woEqualTo {
201  // TODO: This should possibly derive from std::binary_function.
202  public:
203  woEqualTo(const ConstElement& value, bool considerFieldName = true)
204  : _value(value)
205  , _considerFieldName(considerFieldName) {
206  }
207 
208  inline bool operator()(const ConstElement& elt) const {
209  return _value.compareWithElement(elt, _considerFieldName) == 0;
210  }
211  private:
212  const ConstElement& _value;
213  const bool _considerFieldName;
214  };
215 
216  // NOTE: Originally, these truly were algorithms, in that they executed the loop over a
217  // generic ElementType. However, these operations were later made intrinsic to
218  // Element/Document for performance reasons. These functions hare here for backward
219  // compatibility, and just delegate to the appropriate Element or ConstElement method of
220  // the same name.
221 
223  template<typename ElementType>
224  ElementType getNthLeftSibling(ElementType element, std::size_t n) {
225  return element.leftSibling(n);
226  }
227 
229  template<typename ElementType>
230  ElementType getNthRightSibling(ElementType element, std::size_t n) {
231  return element.rightSibling(n);
232  }
233 
235  template<typename ElementType>
236  ElementType getNthSibling(ElementType element, int n) {
237  return (n < 0) ?
238  getNthLeftSibling(element, -n) :
239  getNthRightSibling(element, n);
240  }
241 
243  template<typename ElementType>
244  ElementType getNthChild(ElementType element, std::size_t n) {
245  return element.findNthChild(n);
246  }
247 
249  template<typename ElementType>
250  std::size_t countSiblingsLeft(ElementType element) {
251  return element.countSiblingsLeft();
252  }
253 
255  template<typename ElementType>
256  std::size_t countSiblingsRight(ElementType element) {
257  return element.countSiblingsRight();
258  }
259 
261  template<typename ElementType>
262  std::size_t countChildren(ElementType element) {
263  return element.countChildren();
264  }
265 
267  template<typename ElementType>
268  std::string getFullName(ElementType element, char delim = '.') {
269  std::vector<StringData> names;
270  ElementType curr = element;
271  while(curr.ok() && curr.parent().ok()) {
272  names.push_back(curr.getFieldName());
273  curr = curr.parent();
274  }
275 
277  bool first = true;
278  for(std::vector<StringData>::reverse_iterator it = names.rbegin();
279  it != names.rend();
280  ++it) {
281  if (!first)
282  name << delim;
283  name << *it;
284  first = false;
285  }
286  return name;
287  }
288 } // namespace mutablebson
289 } // namespace mongo
Status pushBack(Element e)
If this Element is empty, add 'e' as the first child.
Definition: element.cpp:33
the idea here is to make one liners easy.
Definition: str.h:48
bool ok() const
Returns true if this Element represents a valid part of the Document.
Definition: element-inl.h:100
A predicate for findElement that matches on the field name of Elements.
Definition: algorithm.h:48
A less-than ordering for Elements that compares based on the Element field names. ...
Definition: algorithm.h:99
A greater-than ordering for Elements that compares based on woCompare.
Definition: algorithm.h:170
Element represents a BSON value or object in a mutable BSON Document.
Definition: element.h:99
An equality predicate for elements that compares based on woCompare.
Definition: algorithm.h:185
An equality predicate for elements that compares based on woCompare.
Definition: algorithm.h:200
Element rightSibling(size_t distance=1) const
Returns either this Element's sibling 'distance' Elements to the right, or a non-ok Element if no suc...
Definition: document.cpp:1361
Status remove()
'Remove' this Element by detaching it from its parent and siblings.
Definition: document.cpp:1215
For an overview of mutable BSON, please see the file document.h in this directory.
Definition: const_element.h:36
A less-than ordering for Elements that compares based on woCompare.
Definition: algorithm.h:155
Element leftChild() const
Returns either this Element's left child, or a non-ok Element if no left child exists.
Definition: document.cpp:1317