1 files changed, 181 insertions, 0 deletions
diff --git a/Firestore/core/src/firebase/firestore/immutable/llrb_node_iterator.h b/Firestore/core/src/firebase/firestore/immutable/llrb_node_iterator.h
new file mode 100644
index 0000000..d113d34
--- /dev/null
+++ b/Firestore/core/src/firebase/firestore/immutable/llrb_node_iterator.h
@@ -0,0 +1,181 @@
+/*
+ * Copyright 2018 Google
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#ifndef FIRESTORE_CORE_SRC_FIREBASE_FIRESTORE_IMMUTABLE_LLRB_NODE_ITERATOR_H_
+#define FIRESTORE_CORE_SRC_FIREBASE_FIRESTORE_IMMUTABLE_LLRB_NODE_ITERATOR_H_
+
+#include <iterator>
+#include <stack>
+#include <utility>
+
+#include "Firestore/core/src/firebase/firestore/immutable/llrb_node.h"
+#include "Firestore/core/src/firebase/firestore/util/comparison.h"
+#include "Firestore/core/src/firebase/firestore/util/firebase_assert.h"
+
+namespace firebase {
+namespace firestore {
+namespace immutable {
+namespace impl {
+
+/**
+ * A forward iterator for traversing LlrbNodes. LlrbNodes represent the nodes
+ * in a tree implementing a sorted map so iterating with LlrbNodeIterator is
+ * an in-order traversal of the map.
+ *
+ * ## Complexity
+ *
+ * LlrbNode is an immutable tree, where mutations create new trees without
+ * invalidating any of the old instances. This means the tree cannot contain
+ * parent pointers and thus this iterator implementation must keep an explicit
+ * stack.
+ *
+ * For an underlying tree of size `n`:
+ *
+ *   * LlrbNodeIterator uses `O(lg(n))` memory for its stack, and
+ *   * incrementing an iterator is an `O(lg(n))` operation.
+ *
+ * ## Invalidation and Comparison
+ *
+ * LlrbNodeIterators compare based on the identity of the nodes themselves,
+ * not based on the values of the keys in the nodes. When adding and removing
+ * the same key and iterator obtained before and after will not compare equal.
+ *
+ * LlrbNodeIterators are not invalidated in any conventional sense because
+ * mutations of the underlying tree create new trees. Together this means that
+ * any given version of the tree can be iterated over from the same iterator
+ * repeatedly, but a "mutable view" of the tree kept by replacing the pointer
+ * to the root is effectively invalidated on each mutation.
+ *
+ * Note: LlrbNodeIterator does not extend the lifetime of its underlying tree.
+ */
+template <typename N>
+class LlrbNodeIterator {
+ public:
+  using node_type = N;
+  using key_type = typename node_type::first_type;
+
+  using stack_type = std::stack<const node_type*>;
+
+  using iterator_category = std::forward_iterator_tag;
+  using value_type = typename node_type::value_type;
+
+  using pointer = typename node_type::value_type const*;
+  using reference = typename node_type::value_type const&;
+  using difference_type = std::ptrdiff_t;
+
+  /**
+   * Constructs an iterator starting at the first node in the iteration
+   * sequence of the tree represented by the given root node (i.e. it points at
+   * the left-most node).
+   */
+  static LlrbNodeIterator Begin(const node_type* root) {
+    stack_type stack;
+    AccumulateLeft(root, &stack);
+    return LlrbNodeIterator{std::move(stack)};
+  }
+
+  /**
+   * Constructs an iterator pointing at the end of the iteration sequence of the
+   * tree pointed to by the given node (i.e. one past the right-most node)
+   */
+  static LlrbNodeIterator End() {
+    return LlrbNodeIterator{stack_type{}};
+  }
+
+  // Default constructor to conform to the requirements of ForwardIterator
+  LlrbNodeIterator() {
+  }
+
+  /**
+   * Returns true if this iterator points at the end of the iteration sequence.
+   */
+  bool is_end() const {
+    return stack_.empty();
+  }
+
+  /**
+   * Returns the address of the entry in the node that this iterator points to.
+   * This can only be called if `end()` is false.
+   */
+  pointer get() const {
+    FIREBASE_ASSERT(!is_end());
+    return &(stack_.top()->entry());
+  }
+
+  reference operator*() const {
+    return *get();
+  }
+
+  pointer operator->() const {
+    return get();
+  }
+
+  LlrbNodeIterator& operator++() {
+    FIREBASE_ASSERT(!is_end());
+
+    // Pop the stack, moving the currently pointed to node to the parent.
+    const node_type* node = stack_.top();
+    stack_.pop();
+
+    // If the popped node has a right subtree that has to precede the parent in
+    // the iteration order so push those on.
+    node = &node->right();
+    AccumulateLeft(node, &stack_);
+
+    return *this;
+  }
+
+  LlrbNodeIterator operator++(int /*unused*/) {
+    LlrbNodeIterator result = *this;
+    ++*this;
+    return result;
+  }
+
+  friend bool operator==(const LlrbNodeIterator& a, const LlrbNodeIterator& b) {
+    if (a.is_end()) {
+      return b.is_end();
+    } else if (b.is_end()) {
+      return false;
+    } else {
+      const key_type& left_key = a.get()->first;
+      const key_type& right_key = b.get()->first;
+      return left_key == right_key;
+    }
+  }
+
+  bool operator!=(const LlrbNodeIterator& b) const {
+    return !(*this == b);
+  }
+
+ private:
+  explicit LlrbNodeIterator(stack_type&& stack) : stack_(std::move(stack)) {
+  }
+
+  static void AccumulateLeft(const node_type* node, stack_type* stack) {
+    for (; !node->empty(); node = &node->left()) {
+      stack->push(node);
+    }
+  }
+
+  stack_type stack_;
+};
+
+}  // namespace impl
+}  // namespace immutable
+}  // namespace firestore
+}  // namespace firebase
+
+#endif  // FIRESTORE_CORE_SRC_FIREBASE_FIRESTORE_IMMUTABLE_LLRB_NODE_ITERATOR_H_