From f86c2ebb3c6f878d65ef32217adc956057ac9649 Mon Sep 17 00:00:00 2001 From: Gil Date: Wed, 2 May 2018 13:32:00 -0700 Subject: Add Immutable SortedSet in C++ (#1206) * Add SortedSet * Add document_key_set.h * Add equality to SortedSet --- .../firebase/firestore/immutable/CMakeLists.txt | 1 + .../firestore/immutable/sorted_map_test.cc | 4 + .../firestore/immutable/sorted_set_test.cc | 182 +++++++++++++++++++++ .../test/firebase/firestore/immutable/testing.h | 50 +++++- 4 files changed, 235 insertions(+), 2 deletions(-) create mode 100644 Firestore/core/test/firebase/firestore/immutable/sorted_set_test.cc (limited to 'Firestore/core/test') diff --git a/Firestore/core/test/firebase/firestore/immutable/CMakeLists.txt b/Firestore/core/test/firebase/firestore/immutable/CMakeLists.txt index 753e2d0..aa8643b 100644 --- a/Firestore/core/test/firebase/firestore/immutable/CMakeLists.txt +++ b/Firestore/core/test/firebase/firestore/immutable/CMakeLists.txt @@ -18,6 +18,7 @@ cc_test( array_sorted_map_test.cc testing.h sorted_map_test.cc + sorted_set_test.cc tree_sorted_map_test.cc DEPENDS firebase_firestore_immutable 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 bcacb50..75353d9 100644 --- a/Firestore/core/test/firebase/firestore/immutable/sorted_map_test.cc +++ b/Firestore/core/test/firebase/firestore/immutable/sorted_map_test.cc @@ -18,6 +18,7 @@ #include #include +#include #include #include @@ -297,6 +298,9 @@ TYPED_TEST(SortedMapTest, MinMax) { } TYPED_TEST(SortedMapTest, IteratorsAreDefaultConstructible) { + ASSERT_TRUE( + std::is_default_constructible::value); + // If this compiles the test has succeeded typename TypeParam::const_iterator iter; (void)iter; diff --git a/Firestore/core/test/firebase/firestore/immutable/sorted_set_test.cc b/Firestore/core/test/firebase/firestore/immutable/sorted_set_test.cc new file mode 100644 index 0000000..a4b337c --- /dev/null +++ b/Firestore/core/test/firebase/firestore/immutable/sorted_set_test.cc @@ -0,0 +1,182 @@ +/* + * 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. + */ + +#include "Firestore/core/src/firebase/firestore/immutable/sorted_set.h" + +#include +#include + +#include "Firestore/core/test/firebase/firestore/immutable/testing.h" + +using firebase::firestore::immutable::impl::SortedMapBase; +using SizeType = SortedMapBase::size_type; + +namespace firebase { +namespace firestore { +namespace immutable { + +template +SortedSet ToSet(const std::vector& container) { + SortedSet result; + for (auto&& entry : container) { + result = result.insert(entry); + } + return result; +} + +static const int kLargeNumber = 100; + +TEST(SortedSetTest, EmptyBehavior) { + SortedSet set; + + EXPECT_TRUE(set.empty()); + EXPECT_EQ(0u, set.size()); + + EXPECT_TRUE(NotFound(set, 1)); +} + +TEST(SortedSetTest, Size) { + std::mt19937 rand; + std::uniform_int_distribution dist(0, 999); + + std::unordered_set expected; + + SortedSet set; + for (int i = 0; i < kLargeNumber; ++i) { + int value = dist(rand); + + // The random number sequence can generate duplicates, so the expected size + // won't necessarily depend upon `i`. + expected.insert(value); + + set = set.insert(value); + EXPECT_EQ(expected.size(), set.size()); + } + + for (int i = 0; i < kLargeNumber; ++i) { + int value = dist(rand); + + // The random number sequence can generate duplicates, so the expected size + // won't necessarily depend upon `i`. + expected.erase(value); + + set = set.erase(value); + EXPECT_EQ(expected.size(), set.size()); + } +} + +TEST(SortedSetSet, Find) { + SortedSet set = SortedSet{}.insert(1).insert(2).insert(4); + + EXPECT_TRUE(NotFound(set, 0)); + EXPECT_TRUE(Found(set, 1)); + EXPECT_TRUE(Found(set, 2)); + EXPECT_TRUE(NotFound(set, 3)); + EXPECT_TRUE(Found(set, 4)); + EXPECT_TRUE(NotFound(set, 5)); +} + +TEST(SortedSetTest, IteratorsAreDefaultConstructible) { + static_assert( + std::is_default_constructible::const_iterator>::value, + "is default constructible"); +} + +TEST(SortedSetTest, CanBeConstructedFromSortedMap) { + using Map = SortedMap; + + Map map = Map{}.insert(1, 2).insert(3, 4); + auto set = MakeSortedSet(map); + + ASSERT_TRUE(Found(set, 1)); + ASSERT_TRUE(NotFound(set, 2)); + + // Set insertion does not modify the underlying map + set = set.insert(2); + ASSERT_TRUE(Found(set, 2)); + ASSERT_TRUE(NotFound(map, 2)); +} + +TEST(SortedSetTest, Iterator) { + std::vector all = Sequence(kLargeNumber); + SortedSet set = ToSet(Shuffled(all)); + + auto begin = set.begin(); + ASSERT_EQ(0, *begin); + + auto end = set.end(); + ASSERT_EQ(all.size(), static_cast(std::distance(begin, end))); + + ASSERT_SEQ_EQ(all, set); +} + +TEST(SortedSetTest, ValuesFrom) { + std::vector all = Sequence(2, 42, 2); + SortedSet set = ToSet(Shuffled(all)); + ASSERT_EQ(20u, set.size()); + + // Test from before keys. + ASSERT_SEQ_EQ(all, set.values_from(0)); + + // Test from after keys. + ASSERT_SEQ_EQ(Empty(), set.values_from(100)); + + // Test from a key in the set: should start at that key. + ASSERT_SEQ_EQ(Sequence(10, 42, 2), set.values_from(10)); + + // Test from in between keys: should start just after that key. + ASSERT_SEQ_EQ(Sequence(12, 42, 2), set.values_from(11)); +} + +TEST(SortedSetTest, ValuesIn) { + std::vector all = Sequence(2, 42, 2); + SortedSet set = ToSet(Shuffled(all)); + ASSERT_EQ(20u, set.size()); + + // Constructs a sequence from `start` up to but not including `end` by 2. + auto Seq = [](int start, int end) { return Sequence(start, end, 2); }; + + ASSERT_SEQ_EQ(Empty(), set.values_in(0, 1)); // before to before + ASSERT_SEQ_EQ(all, set.values_in(0, 100)) // before to after + ASSERT_SEQ_EQ(Seq(2, 6), set.values_in(0, 6)) // before to in set + ASSERT_SEQ_EQ(Seq(2, 8), set.values_in(0, 7)) // before to in between + + ASSERT_SEQ_EQ(Empty(), set.values_in(100, 0)); // after to before + ASSERT_SEQ_EQ(Empty(), set.values_in(100, 110)); // after to after + ASSERT_SEQ_EQ(Empty(), set.values_in(100, 6)); // after to in set + ASSERT_SEQ_EQ(Empty(), set.values_in(100, 7)); // after to in between + + ASSERT_SEQ_EQ(Empty(), set.values_in(6, 0)); // in set to before + ASSERT_SEQ_EQ(Seq(6, 42), set.values_in(6, 100)); // in set to after + ASSERT_SEQ_EQ(Seq(6, 10), set.values_in(6, 10)); // in set to in set + ASSERT_SEQ_EQ(Seq(6, 12), set.values_in(6, 11)); // in set to in between + + ASSERT_SEQ_EQ(Empty(), set.values_in(7, 0)); // in between to before + ASSERT_SEQ_EQ(Seq(8, 42), set.values_in(7, 100)); // in between to after + ASSERT_SEQ_EQ(Seq(8, 10), set.values_in(7, 10)); // in between to key in set + ASSERT_SEQ_EQ(Seq(8, 14), set.values_in(7, 13)); // in between to in between +} + +TEST(SortedSetTest, HashesStdHashable) { + SortedSet set; + + size_t result = util::Hash(set); + (void)result; +} + +} // namespace immutable +} // namespace firestore +} // namespace firebase diff --git a/Firestore/core/test/firebase/firestore/immutable/testing.h b/Firestore/core/test/firebase/firestore/immutable/testing.h index 9e839c6..8e496dd 100644 --- a/Firestore/core/test/firebase/firestore/immutable/testing.h +++ b/Firestore/core/test/firebase/firestore/immutable/testing.h @@ -18,16 +18,33 @@ #define FIRESTORE_CORE_TEST_FIREBASE_FIRESTORE_IMMUTABLE_TESTING_H_ #include +#include +#include #include #include #include "Firestore/core/src/firebase/firestore/util/secure_random.h" +#include "absl/strings/str_cat.h" #include "gtest/gtest.h" namespace firebase { namespace firestore { namespace immutable { +template +std::string Describe(const std::pair& pair) { + return absl::StrCat("(", pair.first, ", ", pair.second, ")"); +} + +// Describes the given item by its std::to_string implementation (if +// std::to_string is defined for V). The return type is not defined directly +// in terms of std::string in order to allow specialization failure to select +// a different overload. +template +auto Describe(const V& item) -> decltype(std::to_string(item)) { + return std::to_string(item); +} + template testing::AssertionResult NotFound(const Container& map, const K& key) { if (map.contains(key)) { @@ -40,11 +57,15 @@ testing::AssertionResult NotFound(const Container& map, const K& key) { return testing::AssertionSuccess(); } else { return testing::AssertionFailure() - << "Should not have found (" << found->first << ", " << found->second - << ")"; + << "Should not have found " << Describe(*found); } } +/** + * Asserts that the given key is found in the given container and that it maps + * to the given value. This only works with map-type containers where value_type + * is `std::pair`. + */ template testing::AssertionResult Found(const Container& map, const K& key, @@ -67,6 +88,31 @@ testing::AssertionResult Found(const Container& map, } } +/** + * Asserts that the given key is found in the given container without + * necessarily checking that the key maps to any value. This also makes + * this compatible with non-mapped containers where K is the value_type. + */ +template +testing::AssertionResult Found(const Container& container, const K& key) { + if (!container.contains(key)) { + return testing::AssertionFailure() + << "Did not find key " << key << " using contains()"; + } + + auto found = container.find(key); + if (found == container.end()) { + return testing::AssertionFailure() + << "Did not find key " << key << " using find()"; + } + if (*found == key) { + return testing::AssertionSuccess(); + } else { + return testing::AssertionFailure() + << "Found entry was " << Describe(*found); + } +} + /** Creates an empty vector (for readability). */ inline std::vector Empty() { return {}; -- cgit v1.2.3