From 0df8378971553a203cc6982a298f342baecae543 Mon Sep 17 00:00:00 2001 From: Gil Date: Thu, 19 Apr 2018 11:30:29 -0700 Subject: Implement iterators for our immutable maps (#1132) * Add a minimal LlrbNodeIterator * Remove fixed_size type parameter from FixedArray The parameter wasn't that useful and caused problems in trying to define dependent iterator types. * Add begin()/end() to SortedMap. --- .../firebase/firestore/immutable/CMakeLists.txt | 2 + .../firestore/immutable/array_sorted_map.h | 11 +- .../src/firebase/firestore/immutable/llrb_node.h | 2 + .../firestore/immutable/llrb_node_iterator.h | 181 +++++++++++++++++++ .../src/firebase/firestore/immutable/sorted_map.h | 37 +++- .../firestore/immutable/sorted_map_iterator.h | 191 +++++++++++++++++++++ .../firebase/firestore/immutable/tree_sorted_map.h | 18 ++ .../firestore/immutable/sorted_map_test.cc | 111 ++++++++++++ .../test/firebase/firestore/immutable/testing.h | 16 +- 9 files changed, 558 insertions(+), 11 deletions(-) create mode 100644 Firestore/core/src/firebase/firestore/immutable/llrb_node_iterator.h create mode 100644 Firestore/core/src/firebase/firestore/immutable/sorted_map_iterator.h (limited to 'Firestore/core') diff --git a/Firestore/core/src/firebase/firestore/immutable/CMakeLists.txt b/Firestore/core/src/firebase/firestore/immutable/CMakeLists.txt index 543f912..accf5c5 100644 --- a/Firestore/core/src/firebase/firestore/immutable/CMakeLists.txt +++ b/Firestore/core/src/firebase/firestore/immutable/CMakeLists.txt @@ -17,10 +17,12 @@ cc_library( SOURCES array_sorted_map.h llrb_node.h + llrb_node_iterator.h map_entry.h sorted_map.h sorted_map_base.h sorted_map_base.cc + sorted_map_iterator.h tree_sorted_map.h DEPENDS firebase_firestore_util diff --git a/Firestore/core/src/firebase/firestore/immutable/array_sorted_map.h b/Firestore/core/src/firebase/firestore/immutable/array_sorted_map.h index adba962..6808297 100644 --- a/Firestore/core/src/firebase/firestore/immutable/array_sorted_map.h +++ b/Firestore/core/src/firebase/firestore/immutable/array_sorted_map.h @@ -47,13 +47,12 @@ namespace impl { * to a FixedArray. * * @tparam T The type of an element in the array. - * @tparam fixed_size the fixed size to use in creating the FixedArray. */ -template +template class FixedArray { public: using size_type = SortedMapBase::size_type; - using array_type = std::array; + using array_type = std::array; using iterator = typename array_type::iterator; using const_iterator = typename array_type::const_iterator; @@ -73,7 +72,7 @@ class FixedArray { void append(SourceIterator src_begin, SourceIterator src_end) { auto appending = static_cast(src_end - src_begin); auto new_size = size_ + appending; - FIREBASE_ASSERT(new_size <= fixed_size); + FIREBASE_ASSERT(new_size <= SortedMapBase::kFixedSize); std::copy(src_begin, src_end, end()); size_ = new_size; @@ -84,7 +83,7 @@ class FixedArray { */ void append(T&& value) { size_type new_size = size_ + 1; - FIREBASE_ASSERT(new_size <= fixed_size); + FIREBASE_ASSERT(new_size <= SortedMapBase::kFixedSize); *end() = std::move(value); size_ = new_size; @@ -132,7 +131,7 @@ class ArraySortedMap : public SortedMapBase { /** * The type of the fixed-size array containing entries of value_type. */ - using array_type = FixedArray; + using array_type = FixedArray; using const_iterator = typename array_type::const_iterator; using array_pointer = std::shared_ptr; diff --git a/Firestore/core/src/firebase/firestore/immutable/llrb_node.h b/Firestore/core/src/firebase/firestore/immutable/llrb_node.h index bfd0f8a..0294efe 100644 --- a/Firestore/core/src/firebase/firestore/immutable/llrb_node.h +++ b/Firestore/core/src/firebase/firestore/immutable/llrb_node.h @@ -20,6 +20,7 @@ #include #include +#include "Firestore/core/src/firebase/firestore/immutable/llrb_node_iterator.h" #include "Firestore/core/src/firebase/firestore/immutable/sorted_map_base.h" namespace firebase { @@ -48,6 +49,7 @@ class LlrbNode : public SortedMapBase { * The type of the entries stored in the map. */ using value_type = std::pair; + using const_iterator = LlrbNodeIterator>; /** * Constructs an empty node. 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 +#include +#include + +#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 +class LlrbNodeIterator { + public: + using node_type = N; + using key_type = typename node_type::first_type; + + using stack_type = std::stack; + + 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_ diff --git a/Firestore/core/src/firebase/firestore/immutable/sorted_map.h b/Firestore/core/src/firebase/firestore/immutable/sorted_map.h index b7729b3..7c8c832 100644 --- a/Firestore/core/src/firebase/firestore/immutable/sorted_map.h +++ b/Firestore/core/src/firebase/firestore/immutable/sorted_map.h @@ -21,6 +21,7 @@ #include "Firestore/core/src/firebase/firestore/immutable/array_sorted_map.h" #include "Firestore/core/src/firebase/firestore/immutable/sorted_map_base.h" +#include "Firestore/core/src/firebase/firestore/immutable/sorted_map_iterator.h" #include "Firestore/core/src/firebase/firestore/immutable/tree_sorted_map.h" #include "Firestore/core/src/firebase/firestore/util/comparison.h" @@ -40,6 +41,11 @@ class SortedMap : public impl::SortedMapBase { using array_type = impl::ArraySortedMap; using tree_type = impl::TreeSortedMap; + using const_iterator = impl::SortedMapIterator< + value_type, + typename impl::FixedArray::const_iterator, + typename impl::LlrbNode::const_iterator>; + /** * Creates an empty SortedMap. */ @@ -71,7 +77,7 @@ class SortedMap : public impl::SortedMapBase { } } - SortedMap(SortedMap&& other) : tag_{other.tag_} { + SortedMap(SortedMap&& other) noexcept : tag_{other.tag_} { switch (tag_) { case Tag::Array: new (&array_) array_type{std::move(other.array_)}; @@ -110,7 +116,7 @@ class SortedMap : public impl::SortedMapBase { return *this; } - SortedMap& operator=(SortedMap&& other) { + SortedMap& operator=(SortedMap&& other) noexcept { if (tag_ == other.tag_) { switch (tag_) { case Tag::Array: @@ -195,6 +201,33 @@ class SortedMap : public impl::SortedMapBase { FIREBASE_UNREACHABLE(); } + /** + * Returns an iterator pointing to the first entry in the map. If there are + * no entries in the map, begin() == end(). + */ + const_iterator begin() const { + switch (tag_) { + case Tag::Array: + return const_iterator{array_.begin()}; + case Tag::Tree: + return const_iterator{tree_.begin()}; + } + FIREBASE_UNREACHABLE(); + } + + /** + * Returns an iterator pointing past the last entry in the map. + */ + const_iterator end() const { + switch (tag_) { + case Tag::Array: + return const_iterator{array_.end()}; + case Tag::Tree: + return const_iterator{tree_.end()}; + } + FIREBASE_UNREACHABLE(); + } + private: explicit SortedMap(array_type&& array) : tag_{Tag::Array}, array_{std::move(array)} { diff --git a/Firestore/core/src/firebase/firestore/immutable/sorted_map_iterator.h b/Firestore/core/src/firebase/firestore/immutable/sorted_map_iterator.h new file mode 100644 index 0000000..36f3967 --- /dev/null +++ b/Firestore/core/src/firebase/firestore/immutable/sorted_map_iterator.h @@ -0,0 +1,191 @@ +/* + * 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_SORTED_MAP_ITERATOR_H_ +#define FIRESTORE_CORE_SRC_FIREBASE_FIRESTORE_IMMUTABLE_SORTED_MAP_ITERATOR_H_ + +#include + +#include "Firestore/core/src/firebase/firestore/immutable/array_sorted_map.h" +#include "Firestore/core/src/firebase/firestore/immutable/tree_sorted_map.h" + +namespace firebase { +namespace firestore { +namespace immutable { +namespace impl { + +template +class SortedMapIterator { + public: + using iterator_category = std::forward_iterator_tag; + using value_type = V; + using pointer = const value_type*; + using reference = const value_type&; + using difference_type = std::ptrdiff_t; + + public: + // Default constructor to conform to the requirements of ForwardIterator + SortedMapIterator() : tag_{Tag::Array}, array_iter_{} { + } + + explicit SortedMapIterator(ArrayIter&& delegate) + : tag_{Tag::Array}, array_iter_{std::move(delegate)} { + } + + explicit SortedMapIterator(TreeIter&& delegate) + : tag_{Tag::Tree}, tree_iter_{std::move(delegate)} { + } + + SortedMapIterator(const SortedMapIterator& other) : tag_(other.tag_) { + switch (tag_) { + case Tag::Array: + new (&array_iter_) ArrayIter{other.array_iter_}; + break; + case Tag::Tree: + new (&tree_iter_) TreeIter{other.tree_iter_}; + break; + } + } + + SortedMapIterator(SortedMapIterator&& other) : tag_(other.tag_) { + switch (tag_) { + case Tag::Array: + new (&array_iter_) ArrayIter{std::move(other.array_iter_)}; + break; + case Tag::Tree: + new (&tree_iter_) TreeIter{std::move(other.tree_iter_)}; + break; + } + } + + ~SortedMapIterator() { + switch (tag_) { + case Tag::Array: + array_iter_.~ArrayIter(); + break; + case Tag::Tree: + tree_iter_.~TreeIter(); + break; + } + } + + SortedMapIterator& operator=(const SortedMapIterator& other) { + if (tag_ == other.tag_) { + switch (tag_) { + case Tag::Array: + array_iter_ = other.array_iter_; + break; + case Tag::Tree: + tree_iter_ = other.tree_iter_; + break; + } + } else { + this->~SortedMapIterator(); + new (this) SortedMapIterator(other); + } + return *this; + } + + SortedMapIterator& operator=(SortedMapIterator&& other) { + if (tag_ == other.tag_) { + switch (tag_) { + case Tag::Array: + array_iter_ = std::move(other.array_iter_); + break; + case Tag::Tree: + tree_iter_ = std::move(other.tree_iter_); + break; + } + } else { + this->~SortedMapIterator(); + new (this) SortedMapIterator(std::move(other)); + } + return *this; + } + + pointer get() const { + switch (tag_) { + case Tag::Array: + return array_iter_; + case Tag::Tree: + return tree_iter_.get(); + } + } + + reference operator*() const { + return *get(); + } + + pointer operator->() const { + return get(); + } + + SortedMapIterator& operator++() { + switch (tag_) { + case Tag::Array: + ++array_iter_; + break; + case Tag::Tree: + ++tree_iter_; + break; + } + return *this; + } + + SortedMapIterator operator++(int /*unused*/) { + SortedMapIterator result = *this; + ++*this; + return result; + } + + friend bool operator==(const SortedMapIterator& a, + const SortedMapIterator& b) { + if (a.tag_ != b.tag_) { + return false; + } + + switch (a.tag_) { + case Tag::Array: + return a.array_iter_ == b.array_iter_; + case Tag::Tree: + return a.tree_iter_ == b.tree_iter_; + } + FIREBASE_UNREACHABLE(); + } + + bool operator!=(const SortedMapIterator& b) const { + return !(*this == b); + } + + private: + enum class Tag { + Array, + Tree, + }; + + Tag tag_; + union { + ArrayIter array_iter_; + TreeIter tree_iter_; + }; +}; + +} // namespace impl +} // namespace immutable +} // namespace firestore +} // namespace firebase + +#endif // FIRESTORE_CORE_SRC_FIREBASE_FIRESTORE_IMMUTABLE_SORTED_MAP_ITERATOR_H_ diff --git a/Firestore/core/src/firebase/firestore/immutable/tree_sorted_map.h b/Firestore/core/src/firebase/firestore/immutable/tree_sorted_map.h index ff8c9f9..c5eddc2 100644 --- a/Firestore/core/src/firebase/firestore/immutable/tree_sorted_map.h +++ b/Firestore/core/src/firebase/firestore/immutable/tree_sorted_map.h @@ -51,6 +51,7 @@ class TreeSortedMap : public SortedMapBase, private util::ComparatorHolder { * The type of the node containing entries of value_type. */ using node_type = LlrbNode; + using const_iterator = typename node_type::const_iterator; /** * Creates an empty TreeSortedMap. @@ -110,6 +111,23 @@ class TreeSortedMap : public SortedMapBase, private util::ComparatorHolder { return root_; } + /** + * Returns a forward iterator pointing to the first entry in the map. If there + * are no entries in the map, begin() == end(). + * + * See LlrbNodeIterator for details + */ + const_iterator begin() const { + return const_iterator::Begin(&root_); + } + + /** + * Returns an iterator pointing past the last entry in the map. + */ + const_iterator end() const { + return const_iterator::End(); + } + private: TreeSortedMap(node_type&& root, const C& comparator) noexcept : util::ComparatorHolder{comparator}, root_{std::move(root)} { diff --git a/Firestore/core/test/firebase/firestore/immutable/sorted_map_test.cc b/Firestore/core/test/firebase/firestore/immutable/sorted_map_test.cc index 3253509..f6d00eb 100644 --- a/Firestore/core/test/firebase/firestore/immutable/sorted_map_test.cc +++ b/Firestore/core/test/firebase/firestore/immutable/sorted_map_test.cc @@ -19,6 +19,7 @@ #include #include #include +#include #include "Firestore/core/src/firebase/firestore/immutable/array_sorted_map.h" #include "Firestore/core/src/firebase/firestore/immutable/tree_sorted_map.h" @@ -110,6 +111,116 @@ TYPED_TEST(SortedMapTest, Increasing) { map = map.erase(i); } ASSERT_EQ(0u, map.size()); + + std::vector empty; + ASSERT_EQ(Pairs(empty), Collect(map)); +} + +TYPED_TEST(SortedMapTest, IteratorsAreDefaultConstructible) { + // If this compiles the test has succeeded + typename TypeParam::const_iterator iter; + (void)iter; +} + +TYPED_TEST(SortedMapTest, BeginEndEmpty) { + TypeParam map; + ASSERT_EQ(map.begin(), map.end()); +} + +TYPED_TEST(SortedMapTest, BeginEndOne) { + TypeParam map = ToMap(Sequence(1)); + auto begin = map.begin(); + auto end = map.end(); + + ASSERT_NE(begin, end); + ASSERT_EQ(0, begin->first); + + ++begin; + ASSERT_EQ(begin, end); +} + +TYPED_TEST(SortedMapTest, Iterates) { + std::vector to_insert = Sequence(this->large_number()); + TypeParam map = ToMap(to_insert); + auto iter = map.begin(); + auto end = map.end(); + + std::vector actual; + for (; iter != end; ++iter) { + actual.push_back(iter->first); + } + ASSERT_EQ(to_insert, actual); +} + +TYPED_TEST(SortedMapTest, IteratorsUsingRangeBasedForLoop) { + std::vector to_insert = Sequence(this->large_number()); + TypeParam map = ToMap(to_insert); + + std::vector actual = Keys(map); + ASSERT_EQ(to_insert, actual); +} + +TYPED_TEST(SortedMapTest, CompatibleWithStdDistance) { + int n = this->large_number(); + TypeParam map = ToMap(Sequence(n)); + + auto iter = map.begin(); + ASSERT_EQ(map.size(), static_cast(std::distance(iter, map.end()))); + + std::advance(iter, 1); + ASSERT_EQ(map.size() - 1, + static_cast(std::distance(iter, map.end()))); + + std::advance(iter, map.size() - 1); + ASSERT_EQ(0u, static_cast(std::distance(iter, map.end()))); +} + +TYPED_TEST(SortedMapTest, CompatibleWithStdAccumulate) { + // World's worst way to compute triangular numbers... + auto add = [](int lhs, const typename TypeParam::value_type& rhs) { + return lhs + rhs.first; + }; + + TypeParam map = ToMap(Sequence(6)); + int result = std::accumulate(map.begin(), map.end(), 0, add); + ASSERT_EQ(15, result); +} + +TYPED_TEST(SortedMapTest, CompatibleWithStdMismatch) { + TypeParam lhs = TypeParam{}.insert(1, 1).insert(3, 3).insert(4, 4); + TypeParam rhs = TypeParam{}.insert(1, 1).insert(2, 2).insert(4, 4); + + using Iter = typename TypeParam::const_iterator; + + // C++11 does not define an overload of std::mismatch that takes the end of + // rhs, so rhs must be a sequence at least as long as lhs. + std::pair miss = + std::mismatch(lhs.begin(), lhs.end(), rhs.begin()); + + auto lhs_miss = lhs.begin(); + std::advance(lhs_miss, 1); + + auto rhs_miss = rhs.begin(); + std::advance(rhs_miss, 1); + + ASSERT_EQ(std::make_pair(lhs_miss, rhs_miss), miss); +} + +TYPED_TEST(SortedMapTest, IteratorInvalidation) { + // Tests that iterators are not invalidated by changes + int n = this->large_number(); + TypeParam map = ToMap(Sequence(0, n - 1, 2)); + size_t size = static_cast(n) / 2; + ASSERT_EQ(size, map.size()); + + // Insert elements ahead of the current iteration position + TypeParam result = map; + for (const auto& element : map) { + result = result.insert(element.first + 1, element.second + 1); + } + size *= 2; + + ASSERT_EQ(size, result.size()); } } // namespace immutable diff --git a/Firestore/core/test/firebase/firestore/immutable/testing.h b/Firestore/core/test/firebase/firestore/immutable/testing.h index 337140f..0b25b66 100644 --- a/Firestore/core/test/firebase/firestore/immutable/testing.h +++ b/Firestore/core/test/firebase/firestore/immutable/testing.h @@ -144,16 +144,26 @@ Container ToMap(const std::vector& values) { return result; } +template +std::vector Keys(const Container& container) { + std::vector keys; + for (const auto& element : container) { + keys.push_back(element.first); + } + return keys; +} + /** * Appends the contents of the given container to a new vector. */ template -std::vector Append(const Container& container) { +std::vector Collect( + const Container& container) { return {container.begin(), container.end()}; } -#define ASSERT_SEQ_EQ(x, y) ASSERT_EQ((x), Append(y)); -#define EXPECT_SEQ_EQ(x, y) EXPECT_EQ((x), Append(y)); +#define ASSERT_SEQ_EQ(x, y) ASSERT_EQ((x), Collect(y)); +#define EXPECT_SEQ_EQ(x, y) EXPECT_EQ((x), Collect(y)); } // namespace immutable } // namespace firestore -- cgit v1.2.3