From 13ff01e20ca796676ba74d0b99065199eca9d309 Mon Sep 17 00:00:00 2001 From: Gil Date: Thu, 29 Mar 2018 08:31:47 -0700 Subject: Initial TreeSortedMap and SortedMap in C++ (#980) * Prepare for TreeSortedMap * Factor out SortedMapBase * Move ArraySortedMap to impl * Factor out SortedMap testing utilities * Add a minimal TreeSortedMap * Add the public SortedMap type --- .../firebase/firestore/immutable/CMakeLists.txt | 3 + .../firestore/immutable/array_sorted_map_test.cc | 142 ++---------------- .../firestore/immutable/sorted_map_test.cc | 76 ++++++++++ .../test/firebase/firestore/immutable/testing.h | 162 +++++++++++++++++++++ .../firestore/immutable/tree_sorted_map_test.cc | 40 +++++ 5 files changed, 291 insertions(+), 132 deletions(-) create mode 100644 Firestore/core/test/firebase/firestore/immutable/sorted_map_test.cc create mode 100644 Firestore/core/test/firebase/firestore/immutable/testing.h create mode 100644 Firestore/core/test/firebase/firestore/immutable/tree_sorted_map_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 e7b0b6e..753e2d0 100644 --- a/Firestore/core/test/firebase/firestore/immutable/CMakeLists.txt +++ b/Firestore/core/test/firebase/firestore/immutable/CMakeLists.txt @@ -16,6 +16,9 @@ cc_test( firebase_firestore_immutable_test SOURCES array_sorted_map_test.cc + testing.h + sorted_map_test.cc + tree_sorted_map_test.cc DEPENDS firebase_firestore_immutable firebase_firestore_util diff --git a/Firestore/core/test/firebase/firestore/immutable/array_sorted_map_test.cc b/Firestore/core/test/firebase/firestore/immutable/array_sorted_map_test.cc index 260506b..fceab7d 100644 --- a/Firestore/core/test/firebase/firestore/immutable/array_sorted_map_test.cc +++ b/Firestore/core/test/firebase/firestore/immutable/array_sorted_map_test.cc @@ -20,127 +20,18 @@ #include #include "Firestore/core/src/firebase/firestore/util/secure_random.h" + +#include "Firestore/core/test/firebase/firestore/immutable/testing.h" #include "gtest/gtest.h" namespace firebase { namespace firestore { namespace immutable { +namespace impl { typedef ArraySortedMap IntMap; constexpr IntMap::size_type kFixedSize = IntMap::kFixedSize; -template -testing::AssertionResult NotFound(const ArraySortedMap& set, - const K& key) { - auto found = set.find(key); - if (found == set.end()) { - return testing::AssertionSuccess(); - } else { - return testing::AssertionFailure() - << "Should not have found (" << found->first << ", " << found->second - << ") @ " << found; - } -} - -template -testing::AssertionResult Found(const ArraySortedMap& map, - const K& key, - const V& expected) { - auto found = map.find(key); - if (found == map.end()) { - return testing::AssertionFailure() << "Did not find key " << key; - } - if (found->second == expected) { - return testing::AssertionSuccess(); - } else { - return testing::AssertionFailure() << "Found entry was (" << found->first - << ", " << found->second << ")"; - } -} - -/** - * Creates a vector containing a sequence of integers from the given starting - * element up to, but not including, the given end element, with values - * incremented by the given step. - * - * If step is negative the sequence is in descending order (but still starting - * at start and ending before end). - */ -std::vector Sequence(int start, int end, int step = 1) { - std::vector result; - if (step > 0) { - for (int i = start; i < end; i += step) { - result.push_back(i); - } - } else { - for (int i = start; i > end; i += step) { - result.push_back(i); - } - } - return result; -} - -/** - * Creates a vector containing a sequence of integers with the given number of - * elements, from zero up to, but not including the given value. - */ -std::vector Sequence(int num_elements) { - return Sequence(0, num_elements); -} - -/** - * Creates a copy of the given vector with contents shuffled randomly. - */ -std::vector Shuffled(const std::vector& values) { - std::vector result(values); - util::SecureRandom rng; - std::shuffle(result.begin(), result.end(), rng); - return result; -} - -/** - * Creates a copy of the given vector with contents sorted. - */ -std::vector Sorted(const std::vector& values) { - std::vector result(values); - std::sort(result.begin(), result.end()); - return result; -} - -/** - * Creates a vector of pairs where each pair has the same first and second - * corresponding to an element in the given vector. - */ -std::vector> Pairs(const std::vector& values) { - std::vector> result; - for (auto&& value : values) { - result.emplace_back(value, value); - } - return result; -} - -/** - * Creates an ArraySortedMap by inserting a pair for each value in the vector. - * Each pair will have the same key and value. - */ -IntMap ToMap(const std::vector& values) { - IntMap result; - for (auto&& value : values) { - result = result.insert(value, value); - } - return result; -} - -/** - * Appends the contents of the given container to a new vector. - */ -template -std::vector Append(const Container& container) { - std::vector result; - result.insert(result.begin(), container.begin(), container.end()); - return result; -} - // TODO(wilhuff): ReverseTraversal #define ASSERT_SEQ_EQ(x, y) ASSERT_EQ((x), Append(y)); @@ -167,7 +58,7 @@ TEST(ArraySortedMap, RemoveKeyValuePair) { } TEST(ArraySortedMap, MoreRemovals) { - IntMap map = IntMap() + IntMap map = IntMap{} .insert(1, 1) .insert(50, 50) .insert(3, 3) @@ -230,7 +121,7 @@ TEST(ArraySortedMap, Increasing) { } TEST(ArraySortedMap, Override) { - IntMap map = IntMap().insert(10, 10).insert(10, 8); + IntMap map = IntMap{}.insert(10, 10).insert(10, 8); ASSERT_TRUE(Found(map, 10, 8)); ASSERT_FALSE(Found(map, 10, 10)); @@ -238,7 +129,7 @@ TEST(ArraySortedMap, Override) { TEST(ArraySortedMap, ChecksSize) { std::vector to_insert = Sequence(kFixedSize); - IntMap map = ToMap(to_insert); + IntMap map = ToMap(to_insert); // Replacing an existing entry should not hit increase size map = map.insert(5, 10); @@ -247,25 +138,11 @@ TEST(ArraySortedMap, ChecksSize) { ASSERT_ANY_THROW(map.insert(next, next)); } -TEST(ArraySortedMap, Empty) { - IntMap map = IntMap().insert(10, 10).erase(10); - EXPECT_TRUE(map.empty()); - EXPECT_EQ(0u, map.size()); - EXPECT_TRUE(NotFound(map, 1)); - EXPECT_TRUE(NotFound(map, 10)); -} - TEST(ArraySortedMap, EmptyGet) { IntMap map; EXPECT_TRUE(NotFound(map, 10)); } -TEST(ArraySortedMap, EmptySize) { - IntMap map; - EXPECT_TRUE(map.empty()); - EXPECT_EQ(0u, map.size()); -} - TEST(ArraySortedMap, EmptyRemoval) { IntMap map; IntMap new_map = map.erase(1); @@ -281,7 +158,7 @@ TEST(ArraySortedMap, InsertionAndRemovalOfMaxItems) { std::vector to_remove = Shuffled(to_insert); // Add them to the map - IntMap map = ToMap(to_insert); + IntMap map = ToMap(to_insert); ASSERT_EQ(expected_size, map.size()) << "Check if all N objects are in the map"; @@ -297,7 +174,7 @@ TEST(ArraySortedMap, InsertionAndRemovalOfMaxItems) { TEST(ArraySortedMap, BalanceProblem) { std::vector to_insert{1, 7, 8, 5, 2, 6, 4, 0, 3}; - IntMap map = ToMap(to_insert); + IntMap map = ToMap(to_insert); ASSERT_SEQ_EQ(Pairs(Sorted(to_insert)), map); } @@ -306,7 +183,7 @@ TEST(ArraySortedMap, BalanceProblem) { // TODO(wilhuff): IndexOf TEST(ArraySortedMap, AvoidsCopying) { - IntMap map = IntMap().insert(10, 20); + IntMap map = IntMap{}.insert(10, 20); auto found = map.find(10); ASSERT_NE(found, map.end()); EXPECT_EQ(20, found->second); @@ -321,6 +198,7 @@ TEST(ArraySortedMap, AvoidsCopying) { EXPECT_EQ(found, duped_found); } +} // namespace impl } // namespace immutable } // namespace firestore } // namespace firebase diff --git a/Firestore/core/test/firebase/firestore/immutable/sorted_map_test.cc b/Firestore/core/test/firebase/firestore/immutable/sorted_map_test.cc new file mode 100644 index 0000000..44dca50 --- /dev/null +++ b/Firestore/core/test/firebase/firestore/immutable/sorted_map_test.cc @@ -0,0 +1,76 @@ +/* + * 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_map.h" + +#include +#include + +#include "Firestore/core/src/firebase/firestore/immutable/array_sorted_map.h" +#include "Firestore/core/src/firebase/firestore/immutable/tree_sorted_map.h" +#include "Firestore/core/src/firebase/firestore/util/secure_random.h" + +#include "Firestore/core/test/firebase/firestore/immutable/testing.h" +#include "gtest/gtest.h" + +using firebase::firestore::immutable::impl::SortedMapBase; + +namespace firebase { +namespace firestore { +namespace immutable { + +using SizeType = SortedMapBase::size_type; + +template +struct TestPolicy { + // TODO(mcg): increase beyond what ArraySortedMap supports + static const SizeType kFixedSize = SortedMapBase::kFixedSize; +}; + +template +class SortedMapTest : public ::testing::Test { + public: + template + Integer fixed_size() { + return static_cast(TestPolicy::kFixedSize); + } +}; + +typedef ::testing::Types, + impl::ArraySortedMap, + impl::TreeSortedMap> + TestedTypes; +TYPED_TEST_CASE(SortedMapTest, TestedTypes); + +TYPED_TEST(SortedMapTest, EmptySize) { + TypeParam map; + EXPECT_TRUE(map.empty()); + EXPECT_EQ(0u, map.size()); +} + +TYPED_TEST(SortedMapTest, Empty) { + TypeParam map = TypeParam{}.insert(10, 10).erase(10); + EXPECT_TRUE(map.empty()); + EXPECT_EQ(0u, map.size()); + + // TODO(wilhuff): re-add find + // EXPECT_TRUE(NotFound(map, 1)); + // EXPECT_TRUE(NotFound(map, 10)); +} + +} // 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 new file mode 100644 index 0000000..337140f --- /dev/null +++ b/Firestore/core/test/firebase/firestore/immutable/testing.h @@ -0,0 +1,162 @@ +/* + * 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_TEST_FIREBASE_FIRESTORE_IMMUTABLE_TESTING_H_ +#define FIRESTORE_CORE_TEST_FIREBASE_FIRESTORE_IMMUTABLE_TESTING_H_ + +#include +#include +#include + +#include "Firestore/core/src/firebase/firestore/util/secure_random.h" +#include "gtest/gtest.h" + +namespace firebase { +namespace firestore { +namespace immutable { + +template +testing::AssertionResult NotFound(const Container& map, const K& key) { + auto found = map.find(key); + if (found == map.end()) { + return testing::AssertionSuccess(); + } else { + return testing::AssertionFailure() + << "Should not have found (" << found->first << ", " << found->second + << ")"; + } +} + +template +testing::AssertionResult Found(const Container& map, + const K& key, + const V& expected) { + auto found = map.find(key); + if (found == map.end()) { + return testing::AssertionFailure() << "Did not find key " << key; + } + if (found->second == expected) { + return testing::AssertionSuccess(); + } else { + return testing::AssertionFailure() << "Found entry was (" << found->first + << ", " << found->second << ")"; + } +} + +/** Creates an empty vector (for readability). */ +inline std::vector Empty() { + return {}; +} + +/** + * Creates a vector containing a sequence of integers from the given starting + * element up to, but not including, the given end element, with values + * incremented by the given step. + * + * If step is negative the sequence is in descending order (but still starting + * at start and ending before end). + */ +inline std::vector Sequence(int start, int end, int step = 1) { + std::vector result; + if (step > 0) { + for (int i = start; i < end; i += step) { + result.push_back(i); + } + } else { + for (int i = start; i > end; i += step) { + result.push_back(i); + } + } + return result; +} + +/** + * Creates a vector containing a sequence of integers with the given number of + * elements, from zero up to, but not including the given value. + */ +inline std::vector Sequence(int num_elements) { + return Sequence(0, num_elements); +} + +/** + * Creates a copy of the given vector with contents shuffled randomly. + */ +inline std::vector Shuffled(const std::vector& values) { + std::vector result{values}; + util::SecureRandom rng; + std::shuffle(result.begin(), result.end(), rng); + return result; +} + +/** + * Creates a copy of the given vector with contents sorted. + */ +inline std::vector Sorted(const std::vector& values) { + std::vector result{values}; + std::sort(result.begin(), result.end()); + return result; +} + +/** + * Creates a copy of the given vector with contents reversed. + */ +inline std::vector Reversed(const std::vector& values) { + std::vector result{values}; + std::reverse(result.begin(), result.end()); + return result; +} + +/** + * Creates a vector of pairs where each pair has the same first and second + * corresponding to an element in the given vector. + */ +inline std::vector> Pairs(const std::vector& values) { + std::vector> result; + for (auto&& value : values) { + result.emplace_back(value, value); + } + return result; +} + +/** + * Creates a SortedMap by inserting a pair for each value in the vector. + * Each pair will have the same key and value. + */ +template +Container ToMap(const std::vector& values) { + Container result; + for (auto&& value : values) { + result = result.insert(value, value); + } + return result; +} + +/** + * Appends the contents of the given container to a new vector. + */ +template +std::vector Append(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)); + +} // namespace immutable +} // namespace firestore +} // namespace firebase + +#endif // FIRESTORE_CORE_TEST_FIREBASE_FIRESTORE_IMMUTABLE_TESTING_H_ diff --git a/Firestore/core/test/firebase/firestore/immutable/tree_sorted_map_test.cc b/Firestore/core/test/firebase/firestore/immutable/tree_sorted_map_test.cc new file mode 100644 index 0000000..7a96b67 --- /dev/null +++ b/Firestore/core/test/firebase/firestore/immutable/tree_sorted_map_test.cc @@ -0,0 +1,40 @@ +/* + * 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/tree_sorted_map.h" + +#include "Firestore/core/src/firebase/firestore/util/secure_random.h" +#include "Firestore/core/test/firebase/firestore/immutable/testing.h" +#include "gtest/gtest.h" + +namespace firebase { +namespace firestore { +namespace immutable { +namespace impl { + +typedef TreeSortedMap IntMap; + +TEST(TreeSortedMap, EmptySize) { + IntMap map; + EXPECT_TRUE(map.empty()); + EXPECT_EQ(0u, map.size()); + EXPECT_EQ(Color::Black, map.root().color()); +} + +} // namespace impl +} // namespace immutable +} // namespace firestore +} // namespace firebase -- cgit v1.2.3