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 --- .../firestore/immutable/sorted_set_test.cc | 182 +++++++++++++++++++++ 1 file changed, 182 insertions(+) create mode 100644 Firestore/core/test/firebase/firestore/immutable/sorted_set_test.cc (limited to 'Firestore/core/test/firebase/firestore/immutable/sorted_set_test.cc') 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 -- cgit v1.2.3