diff options
Diffstat (limited to 'test/source/TestMap.h')
| -rw-r--r-- | test/source/TestMap.h | 1392 |
1 files changed, 1392 insertions, 0 deletions
diff --git a/test/source/TestMap.h b/test/source/TestMap.h new file mode 100644 index 0000000..09353cd --- /dev/null +++ b/test/source/TestMap.h @@ -0,0 +1,1392 @@ +///////////////////////////////////////////////////////////////////////////// +// Copyright (c) Electronic Arts Inc. All rights reserved. +///////////////////////////////////////////////////////////////////////////// + + +#include "EASTLTest.h" +#include <EASTL/vector.h> +#include <EASTL/algorithm.h> +#include <EASTL/type_traits.h> +#include <EASTL/scoped_ptr.h> +#include <EASTL/random.h> +#include <EASTL/tuple.h> + +#ifndef EA_COMPILER_NO_STANDARD_CPP_LIBRARY + EA_DISABLE_ALL_VC_WARNINGS() + #include <algorithm> + EA_RESTORE_ALL_VC_WARNINGS() +#endif + + +/////////////////////////////////////////////////////////////////////////////// +// TestMapConstruction +// +// This test compares eastl::map/multimap to std::map/multimap. It could possibly +// work for comparing eastl::hash_map to C++11 std::unordered_map, but we would +// rather move towards making this test be independent of any std comparisons. +// +// Requires a container that can hold at least 1000 items. +// +template <typename T1, typename T2, bool bMultimap> +int TestMapConstruction() +{ + int nErrorCount = 0; + + TestObject::Reset(); + + { + // We use new because fixed-size versions these objects might be too big for declaration on a stack. + eastl::scoped_ptr<T1> pt1A(new T1); + eastl::scoped_ptr<T2> pt2A(new T2); + T1& t1A = *pt1A; + T2& t2A = *pt2A; + nErrorCount += CompareContainers(t1A, t2A, "Map ctor", eastl::use_first<typename T1::value_type>(), eastl::use_first<typename T2::value_type>()); + EATEST_VERIFY(t1A.validate()); + + + eastl::scoped_ptr<T1> pt1B(new T1); + eastl::scoped_ptr<T2> pt2B(new T2); + T1& t1B = *pt1B; + T2& t2B = *pt2B; + nErrorCount += CompareContainers(t1B, t2B, "Map ctor", eastl::use_first<typename T1::value_type>(), eastl::use_first<typename T2::value_type>()); + + + eastl::scoped_ptr<T1> pt1C(new T1); + eastl::scoped_ptr<T2> pt2C(new T2); + T1& t1C = *pt1C; + T2& t2C = *pt2C; + for(int i = 0; i < 1000; i++) + { + t1C.insert(typename T1::value_type(typename T1::key_type(i), typename T1::mapped_type(i))); + t2C.insert(typename T2::value_type(typename T2::key_type(i), typename T2::mapped_type(i))); + EATEST_VERIFY(t1C.validate()); + nErrorCount += CompareContainers(t1C, t2C, "Map insert", eastl::use_first<typename T1::value_type>(), eastl::use_first<typename T2::value_type>()); + } + + + eastl::scoped_ptr<T1> pt1D(new T1); + eastl::scoped_ptr<T2> pt2D(new T2); + T1& t1D = *pt1D; + T2& t2D = *pt2D; + nErrorCount += CompareContainers(t1D, t2D, "Map ctor", eastl::use_first<typename T1::value_type>(), eastl::use_first<typename T2::value_type>()); + + + eastl::scoped_ptr<T1> pt1E(new T1(t1C)); + eastl::scoped_ptr<T2> pt2E(new T2(t2C)); + T1& t1E = *pt1E; + T2& t2E = *pt2E; + EATEST_VERIFY(t1E.validate()); + nErrorCount += CompareContainers(t1E, t2E, "Map ctor", eastl::use_first<typename T1::value_type>(), eastl::use_first<typename T2::value_type>()); + + + eastl::scoped_ptr<T1> pt1F(new T1(t1C.begin(), t1C.end())); + eastl::scoped_ptr<T2> pt2F(new T2(t2C.begin(), t2C.end())); + T1& t1F = *pt1F; + T2& t2F = *pt2F; + EATEST_VERIFY(t1F.validate()); + nErrorCount += CompareContainers(t1F, t2F, "Map ctor", eastl::use_first<typename T1::value_type>(), eastl::use_first<typename T2::value_type>()); + + + // operator=(const map&) + t1E = t1D; + t2E = t2D; + nErrorCount += CompareContainers(t1D, t2D, "Map operator=", eastl::use_first<typename T1::value_type>(), eastl::use_first<typename T2::value_type>()); + nErrorCount += CompareContainers(t1E, t2E, "Map operator=", eastl::use_first<typename T1::value_type>(), eastl::use_first<typename T2::value_type>()); + + + // operator=(map&&) + // We test just the EASTL container here. + eastl::scoped_ptr<T1> pT1P(new T1); + eastl::scoped_ptr<T1> pT1Q(new T1); + T1& t1P = *pT1P; + T1& t1Q = *pT1Q; + + typename T1::key_type k10(0); + typename T1::key_type k11(1); + typename T1::key_type k12(2); + typename T1::key_type k13(3); + typename T1::key_type k14(4); + typename T1::key_type k15(5); + + typename T1::value_type v10(k10, typename T1::mapped_type(0)); + typename T1::value_type v11(k11, typename T1::mapped_type(1)); + typename T1::value_type v12(k12, typename T1::mapped_type(2)); + typename T1::value_type v13(k13, typename T1::mapped_type(3)); + typename T1::value_type v14(k14, typename T1::mapped_type(4)); + typename T1::value_type v15(k15, typename T1::mapped_type(5)); + + t1P.insert(v10); + t1P.insert(v11); + t1P.insert(v12); + + t1Q.insert(v13); + t1Q.insert(v14); + t1Q.insert(v15); + + t1Q = eastl::move(t1P); // We are effectively requesting to swap t1A with t1B. + //EATEST_VERIFY((t1P.size() == 3) && (t1P.find(k13) != t1P.end()) && (t1P.find(k14) != t1P.end()) && (t1P.find(k15) != t1P.end())); // Currently operator=(this_type&& x) clears x instead of swapping with it. + EATEST_VERIFY((t1Q.size() == 3) && (t1Q.find(k10) != t1Q.end()) && (t1Q.find(k11) != t1Q.end()) && (t1Q.find(k12) != t1Q.end())); + + + // swap + t1E.swap(t1D); + t2E.swap(t2D); + EATEST_VERIFY(t1D.validate()); + EATEST_VERIFY(t1E.validate()); + nErrorCount += CompareContainers(t1D, t2D, "Map swap", eastl::use_first<typename T1::value_type>(), eastl::use_first<typename T2::value_type>()); + nErrorCount += CompareContainers(t1E, t2E, "Map swap", eastl::use_first<typename T1::value_type>(), eastl::use_first<typename T2::value_type>()); + + + // clear + t1A.clear(); + t2A.clear(); + EATEST_VERIFY(t1A.validate()); + nErrorCount += CompareContainers(t1A, t2A, "Map clear", eastl::use_first<typename T1::value_type>(), eastl::use_first<typename T2::value_type>()); + + t1B.clear(); + t2B.clear(); + EATEST_VERIFY(t1B.validate()); + nErrorCount += CompareContainers(t1B, t2B, "Map clear", eastl::use_first<typename T1::value_type>(), eastl::use_first<typename T2::value_type>()); + + + // global operators (==, !=, <, etc.) + t1A.clear(); + t1B.clear(); + // Make t1A equal to t1B + t1A.insert(typename T1::value_type(typename T1::key_type(0), typename T1::mapped_type(0))); + t1A.insert(typename T1::value_type(typename T1::key_type(1), typename T1::mapped_type(1))); + t1A.insert(typename T1::value_type(typename T1::key_type(2), typename T1::mapped_type(2))); + + t1B.insert(typename T1::value_type(typename T1::key_type(0), typename T1::mapped_type(0))); + t1B.insert(typename T1::value_type(typename T1::key_type(1), typename T1::mapped_type(1))); + t1B.insert(typename T1::value_type(typename T1::key_type(2), typename T1::mapped_type(2))); + + EATEST_VERIFY( (t1A == t1B)); + EATEST_VERIFY(!(t1A != t1B)); + EATEST_VERIFY( (t1A <= t1B)); + EATEST_VERIFY( (t1A >= t1B)); + EATEST_VERIFY(!(t1A < t1B)); + EATEST_VERIFY(!(t1A > t1B)); + // Make t1A less than t1B + t1A.insert(typename T1::value_type(typename T1::key_type(3), typename T1::mapped_type(3))); + t1B.insert(typename T1::value_type(typename T1::key_type(4), typename T1::mapped_type(4))); + + EATEST_VERIFY(!(t1A == t1B)); + EATEST_VERIFY( (t1A != t1B)); + EATEST_VERIFY( (t1A <= t1B)); + EATEST_VERIFY(!(t1A >= t1B)); + EATEST_VERIFY( (t1A < t1B)); + EATEST_VERIFY(!(t1A > t1B)); + } + + EATEST_VERIFY(TestObject::IsClear()); + TestObject::Reset(); + + return nErrorCount; +} + + + + +/////////////////////////////////////////////////////////////////////////////// +// TestMapMutation +// +// Requires a container that can hold at least 1000 items. +// +template <typename T1, typename T2, bool bMultimap> +int TestMapMutation() +{ + int nErrorCount = 0; + + TestObject::Reset(); + + { + eastl::scoped_ptr<T1> pt1A(new T1); // We use a pointers instead of concrete object because it's size may be huge. + eastl::scoped_ptr<T2> pt2A(new T2); + T1& t1A = *pt1A; + T2& t2A = *pt2A; + int i, iEnd, p; + + // Set up an array of values to randomize / permute. + eastl::vector<typename T1::key_type> valueArrayInsert; + + if(gEASTL_TestLevel >= kEASTL_TestLevelLow) + { + EASTLTest_Rand rng(EA::UnitTest::GetRandSeed()); + + valueArrayInsert.clear(); + + for(i = 0; i < 1000; i++) + { + valueArrayInsert.push_back(typename T1::key_type(i)); + + // Occasionally attempt to duplicate an element, both for map and multimap. + if(((i + 1) < 1000) && (rng.RandLimit(4) == 0)) + { + valueArrayInsert.push_back(typename T1::key_type(i)); + i++; + } + } + + for(p = 0; p < gEASTL_TestLevel * 100; p++) // For each permutation... + { + eastl::random_shuffle(valueArrayInsert.begin(), valueArrayInsert.end(), rng); + + // insert + for(i = 0, iEnd = (int)valueArrayInsert.size(); i < iEnd; i++) + { + typename T1::key_type& k = valueArrayInsert[i]; + + t1A.insert(typename T1::value_type(k, k)); // We expect that both arguments are the same. + t2A.insert(typename T2::value_type(k, k)); + + EATEST_VERIFY(t1A.validate()); + nErrorCount += CompareContainers(t1A, t2A, "Map insert", eastl::use_first<typename T1::value_type>(), eastl::use_first<typename T2::value_type>()); + } + + + // reverse iteration + typename T1::reverse_iterator r1 = t1A.rbegin(); + typename T2::reverse_iterator r2 = t2A.rbegin(); + + while(r1 != t1A.rend()) + { + typename T1::key_type k1 = (*r1).first; + typename T2::key_type k2 = (*r2).first; + EATEST_VERIFY(k1 == k2); + } + + + // erase + for(i = 0, iEnd = (int)valueArrayInsert.size(); i < iEnd; i++) + { + typename T1::key_type& k = valueArrayInsert[i]; + + typename T1::size_type n1 = t1A.erase(k); + typename T2::size_type n2 = t2A.erase(k); + + EATEST_VERIFY(n1 == n2); + EATEST_VERIFY(t1A.validate()); + nErrorCount += CompareContainers(t1A, t2A, "Map erase", eastl::use_first<typename T1::value_type>(), eastl::use_first<typename T2::value_type>()); + } + + EATEST_VERIFY((TestObject::sTOCount == 0) || (TestObject::sTOCount == (int64_t)valueArrayInsert.size())); // This test will only have meaning when T1 contains TestObject. + } + } + + + EATEST_VERIFY(TestObject::IsClear()); + TestObject::Reset(); + + + // Possibly do extended testing. + if(gEASTL_TestLevel > 6) + { + #ifndef EA_COMPILER_NO_STANDARD_CPP_LIBRARY + + valueArrayInsert.clear(); + + for(i = 0; i < 9; i++) // Much more than this count would take too long to test all permutations. + valueArrayInsert.push_back(typename T1::key_type(i)); + + // Insert these values into the map in every existing permutation. + for(p = 0; std::next_permutation(valueArrayInsert.begin(), valueArrayInsert.end()); p++) // For each permutation... + { + for(i = 0, iEnd = (int)valueArrayInsert.size(); i < iEnd; i++) + { + typename T1::key_type& k = valueArrayInsert[i]; + + t1A.insert(typename T1::value_type(k, k)); // We expect that both arguments are the same. + t2A.insert(typename T2::value_type(k, k)); + + EATEST_VERIFY(t1A.validate()); + nErrorCount += CompareContainers(t1A, t2A, "Map insert", eastl::use_first<typename T1::value_type>(), eastl::use_first<typename T2::value_type>()); + } + + for(i = 0, iEnd = (int)valueArrayInsert.size(); i < iEnd; i++) + { + typename T1::key_type& k = valueArrayInsert[i]; + + t1A.erase(k); + t2A.erase(k); + + EATEST_VERIFY(t1A.validate()); + nErrorCount += CompareContainers(t1A, t2A, "Map erase", eastl::use_first<typename T1::value_type>(), eastl::use_first<typename T2::value_type>()); + } + + EATEST_VERIFY((TestObject::sTOCount == 0) || (TestObject::sTOCount == (int64_t)valueArrayInsert.size())); // This test will only have meaning when T1 contains TestObject. + + } + + #endif // EA_COMPILER_NO_STANDARD_CPP_LIBRARY + } + } + + + EATEST_VERIFY(TestObject::IsClear()); + TestObject::Reset(); + + + { // Other insert and erase operations + + #ifndef EA_COMPILER_NO_STANDARD_CPP_LIBRARY + eastl::scoped_ptr<T1> pt1A(new T1); // We use a pointers instead of concrete object because it's size may be huge. + eastl::scoped_ptr<T2> pt2A(new T2); + T1& t1A = *pt1A; + T2& t2A = *pt2A; + int i; + + // Set up an array of values to randomize / permute. + eastl::vector<eastl::pair<typename T1::key_type, typename T1::mapped_type> > valueArrayInsert1; + eastl::vector< std::pair<typename T2::key_type, typename T2::mapped_type> > valueArrayInsert2; + + EA::UnitTest::Rand rng(EA::UnitTest::GetRandSeed()); + + for(i = 0; i < 100; i++) + { + valueArrayInsert1.push_back(typename T1::value_type(typename T1::key_type(i), typename T1::mapped_type(i))); + valueArrayInsert2.push_back(typename T2::value_type(typename T2::key_type(i), typename T2::mapped_type(i))); + + if(rng.RandLimit(3) == 0) + { + valueArrayInsert1.push_back(typename T1::value_type(typename T1::key_type(i), typename T1::mapped_type(i))); + valueArrayInsert2.push_back(typename T2::value_type(typename T2::key_type(i), typename T2::mapped_type(i))); + } + } + + + // insert(InputIterator first, InputIterator last) + t1A.insert(valueArrayInsert1.begin(), valueArrayInsert1.end()); + t2A.insert(valueArrayInsert2.begin(), valueArrayInsert2.end()); + EATEST_VERIFY(t1A.validate()); + nErrorCount += CompareContainers(t1A, t2A, "Map insert", eastl::use_first<typename T1::value_type>(), eastl::use_first<typename T2::value_type>()); + + + // insert_return_type insert(const Key& key); + t1A.insert(typename T1::key_type(8888)); + t2A.insert(typename T2::value_type(typename T2::key_type(8888), typename T2::mapped_type(0))); + EATEST_VERIFY(t1A.validate()); + nErrorCount += CompareContainers(t1A, t2A, "Map insert", eastl::use_first<typename T1::value_type>(), eastl::use_first<typename T2::value_type>()); + + + // iterator insert(iterator position, const value_type& value); + // + // If bMultimap == true, then the insertions below should fail due to the + // item being present. But they should return the correct iterator value. + typename T1::iterator it1 = t1A.insert(t1A.find(typename T1::key_type(2)), typename T1::value_type(typename T1::key_type(1), typename T1::mapped_type(1))); + typename T2::iterator it2 = t2A.insert(t2A.find(typename T2::key_type(2)), typename T2::value_type(typename T2::key_type(1), typename T2::mapped_type(1))); + EATEST_VERIFY(t1A.validate()); + EATEST_VERIFY(it1->first == typename T1::key_type(1)); + EATEST_VERIFY(it2->first == typename T2::key_type(1)); + nErrorCount += CompareContainers(t1A, t2A, "Map insert", eastl::use_first<typename T1::value_type>(), eastl::use_first<typename T2::value_type>()); + + it1 = t1A.insert(t1A.end(), typename T1::value_type(typename T1::key_type(5), typename T1::mapped_type(5))); + it2 = t2A.insert(t2A.end(), typename T2::value_type(typename T2::key_type(5), typename T2::mapped_type(5))); + EATEST_VERIFY(t1A.validate()); + EATEST_VERIFY(it1->first == typename T1::key_type(5)); + EATEST_VERIFY(it2->first == typename T2::key_type(5)); + nErrorCount += CompareContainers(t1A, t2A, "Map insert", eastl::use_first<typename T1::value_type>(), eastl::use_first<typename T2::value_type>()); + + // Now we remove these items so that the insertions above can succeed. + t1A.erase(t1A.find(typename T1::key_type(1))); + t2A.erase(t2A.find(typename T2::key_type(1))); + it1 = t1A.insert(t1A.find(typename T1::key_type(2)), typename T1::value_type(typename T1::key_type(1), typename T1::mapped_type(1))); + it2 = t2A.insert(t2A.find(typename T2::key_type(2)), typename T2::value_type(typename T2::key_type(1), typename T2::mapped_type(1))); + EATEST_VERIFY(t1A.validate()); + EATEST_VERIFY(it1->first == typename T1::key_type(1)); + EATEST_VERIFY(it2->first == typename T2::key_type(1)); + nErrorCount += CompareContainers(t1A, t2A, "Map insert", eastl::use_first<typename T1::value_type>(), eastl::use_first<typename T2::value_type>()); + + t1A.erase(t1A.find(typename T1::key_type(5))); + t2A.erase(t2A.find(typename T2::key_type(5))); + it1 = t1A.insert(t1A.end(), typename T1::value_type(typename T1::key_type(5), typename T1::mapped_type(5))); + it2 = t2A.insert(t2A.end(), typename T2::value_type(typename T2::key_type(5), typename T2::mapped_type(5))); + EATEST_VERIFY(t1A.validate()); + EATEST_VERIFY(it1->first == typename T1::key_type(5)); + EATEST_VERIFY(it2->first == typename T2::key_type(5)); + nErrorCount += CompareContainers(t1A, t2A, "Map insert", eastl::use_first<typename T1::value_type>(), eastl::use_first<typename T2::value_type>()); + + + // iterator erase(iterator first, iterator last); + typename T1::iterator it11 = t1A.find(typename T1::key_type(17)); + typename T1::iterator it12 = t1A.find(typename T2::key_type(37)); + t1A.erase(it11, it12); + + typename T2::iterator it21 = t2A.find(typename T1::key_type(17)); + typename T2::iterator it22 = t2A.find(typename T2::key_type(37)); + t2A.erase(it21, it22); + + EATEST_VERIFY(t1A.validate()); + nErrorCount += CompareContainers(t1A, t2A, "Map erase(first, last)", eastl::use_first<typename T1::value_type>(), eastl::use_first<typename T2::value_type>()); + + + // iterator erase(iterator position); + t1A.erase(t1A.find(typename T1::key_type(60))); + t2A.erase(t2A.find(typename T1::key_type(60))); + EATEST_VERIFY(t1A.validate()); + nErrorCount += CompareContainers(t1A, t2A, "Map erase(first, last)", eastl::use_first<typename T1::value_type>(), eastl::use_first<typename T2::value_type>()); + + + // Disabled because this function isn't exposed outside the rbtree yet. + // void erase(const key_type* first, const key_type* last); + //typename T1::key_type keyArray1[3] = { typename T1::key_type(70), typename T1::key_type(71), typename T1::key_type(72) }; + //typename T2::key_type keyArray2[3] = { typename T2::key_type(70), typename T2::key_type(71), typename T2::key_type(72) }; + //t1A.erase(keyArray1 + 0, keyArray1 + 3); + //t2A.erase(keyArray2 + 0, keyArray2 + 3); + //EATEST_VERIFY(t1A.validate()); + //nErrorCount += CompareContainers(t1A, t2A, "Map erase(first, last)", eastl::use_first<typename T1::value_type>(), eastl::use_first<typename T2::value_type>()); + + #endif // EA_COMPILER_NO_STANDARD_CPP_LIBRARY + } + + { + // map(std::initializer_list<value_type> ilist, const Compare& compare = Compare(), const allocator_type& allocator = EASTL_MAP_DEFAULT_ALLOCATOR); + // this_type& operator=(std::initializer_list<T> ilist); + // void insert(std::initializer_list<value_type> ilist); + + // VS2013 has a known issue when dealing with std::initializer_lists + // https://connect.microsoft.com/VisualStudio/feedback/details/792355/compiler-confused-about-whether-to-use-a-initializer-list-assignment-operator + #if !defined(EA_COMPILER_NO_INITIALIZER_LISTS) && !(defined(_MSC_VER) && _MSC_VER == 1800) + T1 myMap = { {typename T1::key_type(10),typename T1::mapped_type(0)}, {typename T1::key_type(11),typename T1::mapped_type(1)} }; + EATEST_VERIFY(myMap.size() == 2); + EATEST_VERIFY(myMap.begin()->first == typename T1::key_type(10)); + typename T1::iterator it = myMap.rbegin().base(); + EATEST_VERIFY((--it)->first == typename T1::key_type(11)); + + myMap = { {typename T1::key_type(20),typename T1::mapped_type(0)}, {typename T1::key_type(21),typename T1::mapped_type(1)} }; + EATEST_VERIFY(myMap.size() == 2); + EATEST_VERIFY(myMap.begin()->first == typename T1::key_type(20)); + it = myMap.rbegin().base(); + EATEST_VERIFY((--it)->first == typename T1::key_type(21)); + + myMap.insert({ {typename T1::key_type(40),typename T1::mapped_type(0)}, {typename T1::key_type(41),typename T1::mapped_type(1)} }); + EATEST_VERIFY(myMap.size() == 4); + it = myMap.rbegin().base(); + EATEST_VERIFY((--it)->first == typename T1::key_type(41)); + #endif + } + + + EATEST_VERIFY(TestObject::IsClear()); + TestObject::Reset(); + + return nErrorCount; +} + + + + +template <typename T1> +int TestMapSpecific(T1& t1A, eastl::false_type) // false_type means this is a map and not a multimap. +{ + int nErrorCount = 0; + + // operator[] (map only) + typename T1::mapped_type m = t1A[typename T1::key_type(0)]; + EATEST_VERIFY(m == typename T1::mapped_type(0)); + + m = t1A[typename T1::key_type(999)]; + EATEST_VERIFY(m == typename T1::mapped_type(999)); + + m = t1A[typename T1::key_type(10000000)]; // Test the creation of an element that isn't present. + EATEST_VERIFY(m == typename T1::mapped_type(0)); // Test for 0 because the default ctor for our test objects assigns 0 to the object. + + return nErrorCount; +} + + +template <typename T1> +int TestMapSpecific(T1& t1A, eastl::true_type) // true_type means this is a multimap and not a map. +{ + int nErrorCount = 0; + + // equal_range_small (multimap only) + eastl::pair<typename T1::iterator, typename T1::iterator> er = t1A.equal_range_small(typename T1::key_type(499)); + EATEST_VERIFY(er.first->first == typename T1::key_type(499)); + EATEST_VERIFY(er.second->first == typename T1::key_type(501)); + + er = t1A.equal_range_small(typename T1::key_type(-1)); + EATEST_VERIFY(er.first == er.second); + EATEST_VERIFY(er.first == t1A.begin()); + + return nErrorCount; +} + + +// Just for the purposes of the map::find_as test below, we declare the following. +// The map::find_as function searches a container of X for a type Y, where the user +// defines the equality of X to Y. The purpose of TMapComparable is to be a generic type Y +// that can be used for any X. We need to make this generic because the whole TestMapSearch +// function below is templated on type T1 and so we don't know what T1 is ahead of time. + +template <typename T> +struct TMapComparable +{ + T b; + + TMapComparable() : b() { } + TMapComparable(const T& a) : b(a){ } + const TMapComparable& operator=(const T& a) { b = a; return *this; } + const TMapComparable& operator=(const TMapComparable& x) { b = x.b; return *this; } + operator const T&() const { return b; } +}; + + +/////////////////////////////////////////////////////////////////////////////// +// TestMapSearch +// +// This function is designed to work with map, fixed_map (and not hash containers). +// Requires a container that can hold at least 1000 items. +// +template <typename T1, bool bMultimap> +int TestMapSearch() +{ + int nErrorCount = 0; + + TestObject::Reset(); + + { // Test find, lower_bound, upper_bound, etc.. + eastl::scoped_ptr<T1> pt1A(new T1); // We use a pointers instead of concrete object because it's size may be huge. + T1& t1A = *pt1A; + int i, iEnd; + typename T1::iterator it; + + // Set up an array of values to randomize / permute. + eastl::vector<typename T1::key_type> valueArrayInsert; + + for(i = 0; i < 1000; i++) + valueArrayInsert.push_back(typename T1::key_type(i)); + + EASTLTest_Rand rng(EA::UnitTest::GetRandSeed()); + eastl::random_shuffle(valueArrayInsert.begin(), valueArrayInsert.end(), rng); + + + // insert + for(i = 0, iEnd = (int)valueArrayInsert.size(); i < iEnd; i++) + { + typename T1::key_type k(i); + t1A.insert(typename T1::value_type(k, k)); + + it = t1A.find(k); + EATEST_VERIFY(it != t1A.end()); + } + + + // find + for(i = 0; i < 1000; i++) + { + typename T1::key_type k(i); + it = t1A.find(k); + + EATEST_VERIFY(it != t1A.end()); + EATEST_VERIFY(it->first == k); + EATEST_VERIFY(it->second == k); + } + + it = t1A.find(typename T1::key_type(-1)); + EATEST_VERIFY(it == t1A.end()); + + it = t1A.find(typename T1::key_type(1001)); + EATEST_VERIFY(it == t1A.end()); + + + // find_as + typedef TMapComparable<typename T1::key_type> TC; + + // Normally we use find_as to find via a different type, but we can test it here like this. + for(i = 0; i < 1000; i++) + { + TC k = typename T1::key_type(i); + it = t1A.find_as(k, eastl::less_2<typename T1::key_type, TC>()); + + EATEST_VERIFY(it != t1A.end()); + EATEST_VERIFY(it->first == k); + EATEST_VERIFY(it->second == k); + } + + it = t1A.find_as(TC(typename T1::key_type(-1)), eastl::less_2<typename T1::key_type, TC>()); + EATEST_VERIFY(it == t1A.end()); + + it = t1A.find_as(TC(typename T1::key_type(1001)), eastl::less_2<typename T1::key_type, TC>()); + EATEST_VERIFY(it == t1A.end()); + + + // lower_bound + it = t1A.lower_bound(typename T1::key_type(0)); + EATEST_VERIFY(it == t1A.begin()); + + it = t1A.lower_bound(typename T1::key_type(-1)); + EATEST_VERIFY(it == t1A.begin()); + + it = t1A.lower_bound(typename T1::key_type(1001)); + EATEST_VERIFY(it == t1A.end()); + + t1A.erase(typename T1::key_type(500)); + it = t1A.lower_bound(typename T1::key_type(500)); + EATEST_VERIFY(it->first == typename T1::key_type(501)); + + + // upper_bound + it = t1A.upper_bound(typename T1::key_type(-1)); + EATEST_VERIFY(it == t1A.begin()); + + it = t1A.upper_bound(typename T1::key_type(499)); + EATEST_VERIFY(it->first == typename T1::key_type(501)); + + it = t1A.upper_bound(typename T1::key_type(-1)); + EATEST_VERIFY(it->first == typename T1::key_type(0)); + + it = t1A.upper_bound(typename T1::key_type(1000)); + EATEST_VERIFY(it == t1A.end()); + + + // count + typename T1::size_type n = t1A.count(typename T1::key_type(-1)); + EATEST_VERIFY(n == 0); + + n = t1A.count(typename T1::key_type(0)); + EATEST_VERIFY(n == 1); + + n = t1A.count(typename T1::key_type(500)); // We removed 500 above. + EATEST_VERIFY(n == 0); + + n = t1A.count(typename T1::key_type(1001)); + EATEST_VERIFY(n == 0); + + + // equal_range + eastl::pair<typename T1::iterator, typename T1::iterator> er = t1A.equal_range(typename T1::key_type(200)); + EATEST_VERIFY(er.first->first == typename T1::key_type(200)); + EATEST_VERIFY(er.first->second == typename T1::key_type(200)); + + er = t1A.equal_range(typename T1::key_type(499)); + EATEST_VERIFY(er.first->first == typename T1::key_type(499)); + EATEST_VERIFY(er.second->first == typename T1::key_type(501)); + + er = t1A.equal_range(typename T1::key_type(-1)); + EATEST_VERIFY(er.first == er.second); + EATEST_VERIFY(er.first == t1A.begin()); + + + // Some tests need to be differently between map and multimap. + nErrorCount += TestMapSpecific(t1A, eastl::integral_constant<bool, bMultimap>()); + } + + EATEST_VERIFY(TestObject::IsClear()); + TestObject::Reset(); + + return nErrorCount; +} + +/////////////////////////////////////////////////////////////////////////////// +// TestMapCpp11 +// +// This function is designed to work with map, fixed_map, hash_map, fixed_hash_map. +// +template <typename T1> +int TestMapCpp11() +{ + int nErrorCount = 0; + + // template <class... Args> + // insert_return_type emplace(Args&&... args); + // + // template <class... Args> + // iterator emplace_hint(const_iterator position, Args&&... args); + // + // insert_return_type insert(value_type&& value); + // iterator insert(const_iterator position, value_type&& value); + // void insert(std::initializer_list<value_type> ilist); + TestObject::Reset(); + + typedef T1 TOMap; + typedef typename TOMap::value_type value_type; + typename TOMap::insert_return_type toMapInsertResult; + typename TOMap::iterator toMapIterator; + + TOMap toMap; + TestObject to0(0); + TestObject to1(1); + + toMapInsertResult = toMap.emplace(value_type(0, to0)); + EATEST_VERIFY(toMapInsertResult.second == true); + //EATEST_VERIFY((TestObject::sTOCopyCtorCount == 2) && (TestObject::sTOMoveCtorCount == 1)); // Disabled until we can guarantee its behavior and deal with how it's different between compilers of differing C++11 support. + + toMapInsertResult = toMap.emplace(value_type(1, eastl::move(to1))); + EATEST_VERIFY(toMapInsertResult.second == true); + + // insert_return_type t1A.emplace(value_type&& value); + TestObject to4(4); + value_type value40(4, to4); + EATEST_VERIFY(toMap.find(4) == toMap.end()); + EATEST_VERIFY(value40.second.mX == 4); // It should change to 0 below during the move swap. + toMapInsertResult = toMap.emplace(eastl::move(value40)); + EATEST_VERIFY(toMapInsertResult.second == true); + EATEST_VERIFY(toMap.find(4) != toMap.end()); + EATEST_VERIFY(value40.second.mX == 0); + + value_type value41(4, TestObject(41)); + toMapInsertResult = toMap.emplace(eastl::move(value41)); + EATEST_VERIFY(toMapInsertResult.second == false); + EATEST_VERIFY(toMapInsertResult.first->second.mX == 4); + EATEST_VERIFY(toMap.find(4) != toMap.end()); + + // iterator t1A.emplace_hint(const_iterator position, value_type&& value); + TestObject to5(5); + value_type value50(5, to5); + EATEST_VERIFY(toMap.find(5) == toMap.end()); + toMapInsertResult = toMap.emplace(eastl::move(value50)); + EATEST_VERIFY(toMapInsertResult.second == true); + EATEST_VERIFY(toMap.find(5) != toMap.end()); + + value_type value51(5, TestObject(51)); + toMapIterator = toMap.emplace_hint(toMapInsertResult.first, eastl::move(value51)); + EATEST_VERIFY(toMapIterator->first == 5); + EATEST_VERIFY(toMapIterator->second.mX == 5); + EATEST_VERIFY(toMap.find(5) != toMap.end()); + + TestObject to6(6); + value_type value6(6, to6); + EATEST_VERIFY(toMap.find(6) == toMap.end()); + toMapIterator = toMap.emplace_hint(toMap.begin(), eastl::move(value6)); // specify a bad hint. Insertion should still work. + EATEST_VERIFY(toMapIterator->first == 6); + EATEST_VERIFY(toMap.find(6) != toMap.end()); + + TestObject to2(2); + EATEST_VERIFY(toMap.find(2) == toMap.end()); + toMapInsertResult = toMap.emplace(value_type(2, to2)); + EATEST_VERIFY(toMapInsertResult.second == true); + EATEST_VERIFY(toMap.find(2) != toMap.end()); + toMapInsertResult = toMap.emplace(value_type(2, to2)); + EATEST_VERIFY(toMapInsertResult.second == false); + EATEST_VERIFY(toMap.find(2) != toMap.end()); + + // iterator t1A.emplace_hint(const_iterator position, const value_type& value); + TestObject to7(7); + value_type value70(7, to7); + EATEST_VERIFY(toMap.find(7) == toMap.end()); + toMapInsertResult = toMap.emplace(value70); + EATEST_VERIFY(toMapInsertResult.second == true); + EATEST_VERIFY(toMap.find(7) != toMap.end()); + + value_type value71(7, TestObject(71)); + toMapIterator = toMap.emplace_hint(toMapInsertResult.first, value71); + EATEST_VERIFY(toMapIterator->first == 7); + EATEST_VERIFY(toMapIterator->second.mX == 7); + EATEST_VERIFY(toMap.find(7) != toMap.end()); + + TestObject to8(8); + value_type value8(8, to8); + EATEST_VERIFY(toMap.find(8) == toMap.end()); + toMapIterator = toMap.emplace_hint(toMap.begin(), value8); // specify a bad hint. Insertion should still work. + EATEST_VERIFY(toMapIterator->first == 8); + EATEST_VERIFY(toMap.find(8) != toMap.end()); + + // insert_return_type t1A.insert(value_type&& value); + TestObject to3(3); + EATEST_VERIFY(toMap.find(3) == toMap.end()); + toMapInsertResult = toMap.insert(value_type(3, to3)); + EATEST_VERIFY(toMapInsertResult.second == true); + EATEST_VERIFY(toMap.find(3) != toMap.end()); + toMapInsertResult = toMap.insert(value_type(3, to3)); + EATEST_VERIFY(toMapInsertResult.second == false); + EATEST_VERIFY(toMap.find(3) != toMap.end()); + + + // iterator t1A.insert(const_iterator position, value_type&& value); + TestObject to9(9); + value_type value90(9, to9); + EATEST_VERIFY(toMap.find(9) == toMap.end()); + toMapInsertResult = toMap.emplace(eastl::move(value90)); + EATEST_VERIFY(toMapInsertResult.second == true); + EATEST_VERIFY(toMap.find(9) != toMap.end()); + + value_type value91(9, TestObject(91)); + toMapIterator = toMap.insert(toMapInsertResult.first, eastl::move(value91)); + EATEST_VERIFY(toMapIterator->first == 9); + EATEST_VERIFY(toMapIterator->second.mX == 9); + EATEST_VERIFY(toMap.find(9) != toMap.end()); + + TestObject to10(10); + value_type value10(10, to10); + EATEST_VERIFY(toMap.find(10) == toMap.end()); + toMapIterator = toMap.insert(toMap.begin(), eastl::move(value10)); // specify a bad hint. Insertion should still work. + EATEST_VERIFY(toMapIterator->first == 10); + EATEST_VERIFY(toMap.find(10) != toMap.end()); + + // insert_return_type t1A.emplace(Args&&... args); + TestObject to11(11); + EATEST_VERIFY(toMap.find(11) == toMap.end()); + toMapInsertResult = toMap.emplace(11, to11); + EATEST_VERIFY(toMapInsertResult.second == true); + EATEST_VERIFY(toMapInsertResult.first->first == 11); + EATEST_VERIFY(toMap.find(11) != toMap.end()); + + TestObject to111(111); + toMapInsertResult = toMap.emplace(11, to111); + EATEST_VERIFY(toMapInsertResult.second == false); + EATEST_VERIFY(toMapInsertResult.first->first == 11); + EATEST_VERIFY(toMapInsertResult.first->second.mX == 11); + EATEST_VERIFY(toMap.find(11) != toMap.end()); + + TestObject to12(12); + EATEST_VERIFY(toMap.find(12) == toMap.end()); + toMapInsertResult = toMap.emplace(12, eastl::move(to12)); + EATEST_VERIFY(toMapInsertResult.second == true); + EATEST_VERIFY(toMapInsertResult.first->first == 12); + EATEST_VERIFY(toMap.find(12) != toMap.end()); + + TestObject to121(121); + toMapInsertResult = toMap.emplace(12, eastl::move(to121)); + EATEST_VERIFY(toMapInsertResult.second == false); + EATEST_VERIFY(toMapInsertResult.first->first == 12); + EATEST_VERIFY(toMapInsertResult.first->second.mX == 12); + EATEST_VERIFY(toMap.find(12) != toMap.end()); + + EATEST_VERIFY(toMap.find(13) == toMap.end()); + toMapInsertResult = toMap.emplace(eastl::piecewise_construct, eastl::make_tuple(13), eastl::make_tuple(1, 2, 10)); // 1 + 2 + 10 = 13 + EATEST_VERIFY(toMapInsertResult.second == true); + EATEST_VERIFY(toMapInsertResult.first->first == 13); + EATEST_VERIFY(toMap.find(13) != toMap.end()); + + toMapInsertResult = toMap.emplace(eastl::piecewise_construct, eastl::make_tuple(13), eastl::make_tuple(1, 30, 100)); // 1 + 30 + 100 = 131 + EATEST_VERIFY(toMapInsertResult.second == false); + EATEST_VERIFY(toMapInsertResult.first->first == 13); + EATEST_VERIFY(toMapInsertResult.first->second.mX == 13); + EATEST_VERIFY(toMap.find(13) != toMap.end()); + + // iterator t1A.emplace_hint(const_iterator position, Args&&... args); + TestObject to14(14); + EATEST_VERIFY(toMap.find(14) == toMap.end()); + toMapInsertResult = toMap.emplace(14, to14); + EATEST_VERIFY(toMapInsertResult.second == true); + EATEST_VERIFY(toMap.find(14) != toMap.end()); + + TestObject to141(141); + toMapIterator = toMap.emplace_hint(toMapInsertResult.first, 14, to141); + EATEST_VERIFY(toMapIterator->first == 14); + EATEST_VERIFY(toMapIterator->second.mX == 14); + EATEST_VERIFY(toMap.find(14) != toMap.end()); + + TestObject to15(15); + EATEST_VERIFY(toMap.find(15) == toMap.end()); + toMapIterator = toMap.emplace_hint(toMap.begin(), 15, to15); // specify a bad hint. Insertion should still work. + EATEST_VERIFY(toMapIterator->first == 15); + EATEST_VERIFY(toMap.find(15) != toMap.end()); + + TestObject to16(16); + EATEST_VERIFY(toMap.find(16) == toMap.end()); + toMapInsertResult = toMap.emplace(16, eastl::move(to16)); + EATEST_VERIFY(toMapInsertResult.second == true); + EATEST_VERIFY(toMap.find(16) != toMap.end()); + + TestObject to161(161); + toMapIterator = toMap.emplace_hint(toMapInsertResult.first, 16, eastl::move(to161)); + EATEST_VERIFY(toMapIterator->first == 16); + EATEST_VERIFY(toMapIterator->second.mX == 16); + EATEST_VERIFY(toMap.find(16) != toMap.end()); + + TestObject to17(17); + EATEST_VERIFY(toMap.find(17) == toMap.end()); + toMapIterator = toMap.emplace_hint(toMap.begin(), 17, eastl::move(to17)); // specify a bad hint. Insertion should still work. + EATEST_VERIFY(toMapIterator->first == 17); + EATEST_VERIFY(toMap.find(17) != toMap.end()); + + EATEST_VERIFY(toMap.find(18) == toMap.end()); + toMapInsertResult = toMap.emplace(eastl::piecewise_construct, eastl::make_tuple(18), eastl::make_tuple(3, 5, 10)); // 3 + 5 + 10 = 18 + EATEST_VERIFY(toMapInsertResult.second == true); + EATEST_VERIFY(toMap.find(18) != toMap.end()); + + toMapIterator = toMap.emplace_hint(toMapInsertResult.first, eastl::piecewise_construct, eastl::make_tuple(18), eastl::make_tuple(1, 80, 100)); // 1 + 80 + 100 = 181 + EATEST_VERIFY(toMapIterator->first == 18); + EATEST_VERIFY(toMapIterator->second.mX == 18); + EATEST_VERIFY(toMap.find(18) != toMap.end()); + + EATEST_VERIFY(toMap.find(19) == toMap.end()); + toMapIterator = toMap.emplace_hint(toMap.begin(), eastl::piecewise_construct, eastl::make_tuple(19), eastl::make_tuple(4, 5, 10)); // 4 + 5 + 10 = 19 // specify a bad hint. Insertion should still work. + EATEST_VERIFY(toMapIterator->first == 19); + EATEST_VERIFY(toMap.find(19) != toMap.end()); + + // iterator t1A.insert(const_iterator position, const value_type& value); + TestObject to20(20); + value_type value20(20, to20); + EATEST_VERIFY(toMap.find(20) == toMap.end()); + toMapInsertResult = toMap.emplace(value20); + EATEST_VERIFY(toMapInsertResult.second == true); + EATEST_VERIFY(toMap.find(20) != toMap.end()); + + value_type value201(20, TestObject(201)); + toMapIterator = toMap.insert(toMapInsertResult.first, value201); + EATEST_VERIFY(toMapIterator->first == 20); + EATEST_VERIFY(toMapIterator->second.mX == 20); + EATEST_VERIFY(toMap.find(20) != toMap.end()); + + TestObject to21(21); + value_type value21(21, to21); + EATEST_VERIFY(toMap.find(21) == toMap.end()); + toMapIterator = toMap.insert(toMap.begin(), value21); // specify a bad hint. Insertion should still work. + EATEST_VERIFY(toMapIterator->first == 21); + EATEST_VERIFY(toMap.find(21) != toMap.end()); + + // void insert(std::initializer_list<value_type> ilist); + toMap.insert({ value_type(22, TestObject(22)), value_type(23, TestObject(23)), value_type(24, TestObject(24)) }); + EATEST_VERIFY(toMap.find(22) != toMap.end()); + EATEST_VERIFY(toMap.find(23) != toMap.end()); + EATEST_VERIFY(toMap.find(24) != toMap.end()); + + return nErrorCount; +} + +struct NonCopyable +{ + NonCopyable() : mX(0) {} + NonCopyable(int x) : mX(x) {} + + int mX; + + EA_NON_COPYABLE(NonCopyable) +}; + +inline bool operator<(const NonCopyable& a, const NonCopyable& b) { return a.mX < b.mX; } + +template <typename T> +int TestMapCpp11NonCopyable() +{ + int nErrorCount = 0; + + // Verify that operator[]() can be called for a type that is default constructible but not copy constructible. C++11 + // relaxed the requirements on operator[]() and so this should compile. + T ncMap; + ncMap[1].mX = 1; + EATEST_VERIFY(ncMap[1].mX == 1); + + return nErrorCount; +} + +/////////////////////////////////////////////////////////////////////////////// +// TestMultimapCpp11 +// +// This function is designed to work with multimap, fixed_multimap, hash_multimap, fixed_hash_multimap +// +// This is similar to the TestSetCpp11 function, with some differences related +// to handling of duplicate entries. +// +template <typename T1> +int TestMultimapCpp11() +{ + int nErrorCount = 0; + + // template <class... Args> + // insert_return_type emplace(Args&&... args); + // + // template <class... Args> + // iterator emplace_hint(const_iterator position, Args&&... args); + // + // insert_return_type insert(value_type&& value); + // iterator insert(const_iterator position, value_type&& value); + // void insert(std::initializer_list<value_type> ilist); + TestObject::Reset(); + + typedef T1 TOMap; + typedef typename TOMap::value_type value_type; + typename TOMap::iterator toMapIterator; + + TOMap toMap; + TestObject to0(0); + TestObject to1(1); + + toMapIterator = toMap.emplace(value_type(0, to0)); + EATEST_VERIFY(toMapIterator->first == 0); + //EATEST_VERIFY((TestObject::sTOCopyCtorCount == 2) && (TestObject::sTOMoveCtorCount == 1)); // Disabled until we can guarantee its behavior and deal with how it's different between compilers of differing C++11 support. + + toMapIterator = toMap.emplace(value_type(1, eastl::move(to1))); + EATEST_VERIFY(toMapIterator->first == 1); + + // insert_return_type t1A.emplace(value_type&& value); + TestObject to4(4); + value_type value40(4, to4); + EATEST_VERIFY(toMap.find(4) == toMap.end()); + EATEST_VERIFY(value40.second.mX == 4); // It should change to 0 below during the move swap. + toMapIterator = toMap.emplace(eastl::move(value40)); + EATEST_VERIFY(toMapIterator->first == 4); + EATEST_VERIFY(toMap.find(4) != toMap.end()); + EATEST_VERIFY(value40.second.mX == 0); + + value_type value41(4, TestObject(41)); + toMapIterator = toMap.emplace(eastl::move(value41)); + EATEST_VERIFY(toMapIterator->first == 4); + EATEST_VERIFY(toMapIterator->second.mX == 41); + EATEST_VERIFY(toMap.count(4) == 2); + + // iterator t1A.emplace_hint(const_iterator position, value_type&& value); + TestObject to5(5); + value_type value50(5, to5); + EATEST_VERIFY(toMap.find(5) == toMap.end()); + toMapIterator = toMap.emplace(eastl::move(value50)); + EATEST_VERIFY(toMapIterator->first == 5); + EATEST_VERIFY(toMap.find(5) != toMap.end()); + + value_type value51(5, TestObject(51)); + toMapIterator = toMap.emplace_hint(toMapIterator, eastl::move(value51)); + EATEST_VERIFY(toMapIterator->first == 5); + EATEST_VERIFY(toMapIterator->second.mX == 51); + EATEST_VERIFY(toMap.count(5) == 2); + + TestObject to6(6); + value_type value6(6, to6); + EATEST_VERIFY(toMap.find(6) == toMap.end()); + toMapIterator = toMap.emplace_hint(toMap.begin(), eastl::move(value6)); // specify a bad hint. Insertion should still work. + EATEST_VERIFY(toMapIterator->first == 6); + EATEST_VERIFY(toMap.find(6) != toMap.end()); + + TestObject to2(2); + EATEST_VERIFY(toMap.find(2) == toMap.end()); + toMapIterator = toMap.emplace(value_type(2, to2)); + EATEST_VERIFY(toMapIterator->first == 2); + EATEST_VERIFY(toMap.find(2) != toMap.end()); + toMapIterator = toMap.emplace(value_type(2, to2)); + EATEST_VERIFY(toMapIterator->first == 2); + EATEST_VERIFY(toMap.find(2) != toMap.end()); + + // iterator t1A.emplace_hint(const_iterator position, const value_type& value); + TestObject to7(7); + value_type value70(7, to7); + EATEST_VERIFY(toMap.find(7) == toMap.end()); + toMapIterator = toMap.emplace(value70); + EATEST_VERIFY(toMapIterator->first == 7); + EATEST_VERIFY(toMap.find(7) != toMap.end()); + + value_type value71(7, TestObject(71)); + toMapIterator = toMap.emplace_hint(toMapIterator, value71); + EATEST_VERIFY(toMapIterator->first == 7); + EATEST_VERIFY(toMapIterator->second.mX == 71); + EATEST_VERIFY(toMap.count(7) == 2); + + TestObject to8(8); + value_type value8(8, to8); + EATEST_VERIFY(toMap.find(8) == toMap.end()); + toMapIterator = toMap.emplace_hint(toMap.begin(), value8); // specify a bad hint. Insertion should still work. + EATEST_VERIFY(toMapIterator->first == 8); + EATEST_VERIFY(toMap.find(8) != toMap.end()); + + // insert_return_type t1A.insert(value_type&& value); + TestObject to3(3); + EATEST_VERIFY(toMap.find(3) == toMap.end()); + toMapIterator = toMap.insert(value_type(3, to3)); + EATEST_VERIFY(toMapIterator->first == 3); + EATEST_VERIFY(toMap.find(3) != toMap.end()); + toMapIterator = toMap.insert(value_type(3, to3)); + EATEST_VERIFY(toMapIterator->first == 3); + EATEST_VERIFY(toMap.find(3) != toMap.end()); + + + // iterator t1A.insert(const_iterator position, value_type&& value); + TestObject to9(9); + value_type value90(9, to9); + EATEST_VERIFY(toMap.find(9) == toMap.end()); + toMapIterator = toMap.emplace(eastl::move(value90)); + EATEST_VERIFY(toMapIterator->first == 9); + EATEST_VERIFY(toMap.find(9) != toMap.end()); + + value_type value91(9, TestObject(91)); + toMapIterator = toMap.insert(toMapIterator, eastl::move(value91)); + EATEST_VERIFY(toMapIterator->first == 9); + EATEST_VERIFY(toMapIterator->second.mX == 91); + EATEST_VERIFY(toMap.count(9) == 2); + + TestObject to10(10); + value_type value10(10, to10); + EATEST_VERIFY(toMap.find(10) == toMap.end()); + toMapIterator = toMap.insert(toMap.begin(), eastl::move(value10)); // specify a bad hint. Insertion should still work. + EATEST_VERIFY(toMapIterator->first == 10); + EATEST_VERIFY(toMap.find(10) != toMap.end()); + + // iterator t1A.emplace(Args&&... args); + TestObject to11(11); + EATEST_VERIFY(toMap.find(11) == toMap.end()); + toMapIterator = toMap.emplace(11, to11); + EATEST_VERIFY(toMapIterator->first == 11); + EATEST_VERIFY(toMap.find(11) != toMap.end()); + + TestObject to111(111); + toMapIterator = toMap.emplace(11, to111); + EATEST_VERIFY(toMapIterator->first == 11); + EATEST_VERIFY(toMapIterator->second.mX == 111); + EATEST_VERIFY(toMap.count(11) == 2); + + TestObject to12(12); + EATEST_VERIFY(toMap.find(12) == toMap.end()); + toMapIterator = toMap.emplace(12, eastl::move(to12)); + EATEST_VERIFY(toMapIterator->first == 12); + EATEST_VERIFY(toMap.find(12) != toMap.end()); + + TestObject to121(121); + toMapIterator = toMap.emplace(12, eastl::move(to121)); + EATEST_VERIFY(toMapIterator->first == 12); + EATEST_VERIFY(toMapIterator->second.mX == 121); + EATEST_VERIFY(toMap.count(12) == 2); + + EATEST_VERIFY(toMap.find(13) == toMap.end()); + toMapIterator = toMap.emplace(eastl::piecewise_construct, eastl::make_tuple(13), eastl::make_tuple(1, 2, 10)); // 1 + 2 + 10 = 13 + EATEST_VERIFY(toMapIterator->first == 13); + EATEST_VERIFY(toMap.find(13) != toMap.end()); + + toMapIterator = toMap.emplace(eastl::piecewise_construct, eastl::make_tuple(13), eastl::make_tuple(1, 30, 100)); // 1 + 30 + 100 = 131 + EATEST_VERIFY(toMapIterator->first == 13); + EATEST_VERIFY(toMapIterator->second.mX == 131); + EATEST_VERIFY(toMap.count(13) == 2); + + // iterator t1A.emplace_hint(const_iterator position, Args&&... args); + TestObject to14(14); + EATEST_VERIFY(toMap.find(14) == toMap.end()); + toMapIterator = toMap.emplace(14, to14); + EATEST_VERIFY(toMap.find(14) != toMap.end()); + + TestObject to141(141); + toMapIterator = toMap.emplace_hint(toMapIterator, 14, to141); + EATEST_VERIFY(toMapIterator->first == 14); + EATEST_VERIFY(toMapIterator->second.mX == 141); + EATEST_VERIFY(toMap.count(14) == 2); + + TestObject to15(15); + EATEST_VERIFY(toMap.find(15) == toMap.end()); + toMapIterator = toMap.emplace_hint(toMap.begin(), 15, to15); // specify a bad hint. Insertion should still work. + EATEST_VERIFY(toMapIterator->first == 15); + EATEST_VERIFY(toMap.find(15) != toMap.end()); + + TestObject to16(16); + EATEST_VERIFY(toMap.find(16) == toMap.end()); + toMapIterator = toMap.emplace(16, eastl::move(to16)); + EATEST_VERIFY(toMap.find(16) != toMap.end()); + + TestObject to161(161); + toMapIterator = toMap.emplace_hint(toMapIterator, 16, eastl::move(to161)); + EATEST_VERIFY(toMapIterator->first == 16); + EATEST_VERIFY(toMapIterator->second.mX == 161); + EATEST_VERIFY(toMap.count(16) == 2); + + TestObject to17(17); + EATEST_VERIFY(toMap.find(17) == toMap.end()); + toMapIterator = toMap.emplace_hint(toMap.begin(), 17, eastl::move(to17)); // specify a bad hint. Insertion should still work. + EATEST_VERIFY(toMapIterator->first == 17); + EATEST_VERIFY(toMap.find(17) != toMap.end()); + + EATEST_VERIFY(toMap.find(18) == toMap.end()); + toMapIterator = toMap.emplace(eastl::piecewise_construct, eastl::make_tuple(18), eastl::make_tuple(3, 5, 10)); // 3 + 5 + 10 = 18 + EATEST_VERIFY(toMap.find(18) != toMap.end()); + + toMapIterator = toMap.emplace_hint(toMapIterator, eastl::piecewise_construct, eastl::make_tuple(18), eastl::make_tuple(1, 80, 100)); // 1 + 80 + 100 = 181 + EATEST_VERIFY(toMapIterator->first == 18); + EATEST_VERIFY(toMapIterator->second.mX == 181); + EATEST_VERIFY(toMap.count(18) == 2); + + EATEST_VERIFY(toMap.find(19) == toMap.end()); + toMapIterator = toMap.emplace_hint(toMap.begin(), eastl::piecewise_construct, eastl::make_tuple(19), eastl::make_tuple(4, 5, 10)); // 4 + 5 + 10 = 19 // specify a bad hint. Insertion should still work. + EATEST_VERIFY(toMapIterator->first == 19); + EATEST_VERIFY(toMap.find(19) != toMap.end()); + + // iterator t1A.insert(const_iterator position, const value_type& value); + TestObject to20(20); + value_type value20(20, to20); + EATEST_VERIFY(toMap.find(20) == toMap.end()); + toMapIterator = toMap.emplace(value20); + EATEST_VERIFY(toMap.find(20) != toMap.end()); + + value_type value201(20, TestObject(201)); + toMapIterator = toMap.insert(toMapIterator, value201); + EATEST_VERIFY(toMapIterator->first == 20); + EATEST_VERIFY(toMapIterator->second.mX == 201); + EATEST_VERIFY(toMap.count(20) == 2); + + TestObject to21(21); + value_type value21(21, to21); + EATEST_VERIFY(toMap.find(21) == toMap.end()); + toMapIterator = toMap.insert(toMap.begin(), value21); // specify a bad hint. Insertion should still work. + EATEST_VERIFY(toMapIterator->first == 21); + EATEST_VERIFY(toMap.find(21) != toMap.end()); + + // void insert(std::initializer_list<value_type> ilist); + toMap.insert({ value_type(22, TestObject(22)), value_type(23, TestObject(23)), value_type(24, TestObject(24)), value_type(24, TestObject(241)) }); + EATEST_VERIFY(toMap.find(22) != toMap.end()); + EATEST_VERIFY(toMap.find(23) != toMap.end()); + EATEST_VERIFY(toMap.count(24) == 2); + + return nErrorCount; +} + + +/////////////////////////////////////////////////////////////////////////////// +// TestMapCpp17 +// +// This function is designed to work with map, fixed_map, hash_map, fixed_hash_map, unordered_map. +// +template <typename T1> +int TestMapCpp17() +{ + + int nErrorCount = 0; + + TestObject::Reset(); + + typedef T1 TOMap; + typedef typename TOMap::mapped_type mapped_type; + typename TOMap::iterator toMapIterator; + + + { + // pair<iterator, bool> try_emplace (const key_type& k, Args&&... args); + // pair<iterator, bool> try_emplace (key_type&& k, Args&&... args); + // iterator try_emplace (const_iterator hint, const key_type& k, Args&&... args); + // iterator try_emplace (const_iterator hint, key_type&& k, Args&&... args); + + TOMap toMap; + + { // do initial insert + auto result = toMap.try_emplace(7, 7); // test fwding to conversion-ctor + VERIFY(result.second); + VERIFY(result.first->second == mapped_type(7)); + VERIFY(toMap.size() == 1); + } + + { // verify duplicate not inserted + auto result = toMap.try_emplace(7, mapped_type(7)); // test fwding to copy-ctor + VERIFY(!result.second); + VERIFY(result.first->second == mapped_type(7)); + VERIFY(toMap.size() == 1); + } + + { // verify duplicate not inserted + auto hint = toMap.find(7); + auto result = toMap.try_emplace(hint, 7, 7); // test fwding to conversion-ctor + VERIFY(result->first == 7); + VERIFY(result->second == mapped_type(7)); + VERIFY(toMap.size() == 1); + } + + { // verify duplicate not inserted + auto hint = toMap.find(7); + auto result = toMap.try_emplace(hint, 7, mapped_type(7)); // test fwding to copy-ctor + VERIFY(result->first == 7); + VERIFY(result->second == mapped_type(7)); + VERIFY(toMap.size() == 1); + } + + { + { + auto result = toMap.try_emplace(8, 8); + VERIFY(result.second); + VERIFY(result.first->second == mapped_type(8)); + VERIFY(toMap.size() == 2); + } + { + auto result = toMap.try_emplace(9, mapped_type(9)); + VERIFY(result.second); + VERIFY(result.first->second == mapped_type(9)); + VERIFY(toMap.size() == 3); + } + } + } + + { + // eastl::pair<iterator, bool> insert_or_assign(const key_type& k, M&& obj); + // eastl::pair<iterator, bool> insert_or_assign(key_type&& k, M&& obj); + // iterator insert_or_assign(const_iterator hint, const key_type& k, M&& obj); + // iterator insert_or_assign(const_iterator hint, key_type&& k, M&& obj); + + TOMap toMap; + + { + // initial rvalue insert + auto result = toMap.insert_or_assign(3, mapped_type(3)); + VERIFY(result.second); + VERIFY(toMap.size() == 1); + VERIFY(result.first->first == 3); + VERIFY(result.first->second == mapped_type(3)); + + // verify rvalue assign occurred + result = toMap.insert_or_assign(3, mapped_type(9)); + VERIFY(!result.second); + VERIFY(toMap.size() == 1); + VERIFY(result.first->first == 3); + VERIFY(result.first->second == mapped_type(9)); + } + + { + mapped_type mt5(5); + mapped_type mt6(6); + mapped_type mt7(7); + + { + // initial lvalue insert + auto result = toMap.insert_or_assign(5, mt5); + VERIFY(result.second); + VERIFY(toMap.size() == 2); + VERIFY(result.first->first == 5); + VERIFY(result.first->second == mt5); + } + + { + // verify lvalue assign occurred + auto result = toMap.insert_or_assign(5, mt7); + VERIFY(!result.second); + VERIFY(toMap.size() == 2); + VERIFY(result.first->first == 5); + VERIFY(result.first->second == mt7); + } + + { + // verify lvalue hints + auto hint = toMap.find(5); + auto result = toMap.insert_or_assign(hint, 6, mt6); + VERIFY(result != toMap.end()); + VERIFY(toMap.size() == 3); + VERIFY(result->first == 6); + VERIFY(result->second == mt6); + } + + { + // verify rvalue hints + auto hint = toMap.find(6); + auto result = toMap.insert_or_assign(hint, 7, mapped_type(7)); + VERIFY(result != toMap.end()); + VERIFY(toMap.size() == 4); + VERIFY(result->first == 7); + VERIFY(result->second == mapped_type(7)); + } + } + } + + EATEST_VERIFY(TestObject::IsClear()); + TestObject::Reset(); + + return nErrorCount; +} + + +template<typename HashContainer> +struct HashContainerReserveTest +{ + int operator()() + { + int nErrorCount = 0; + + HashContainer hashContainer; + + const typename HashContainer::size_type reserve_sizes[] = {16, 128, 4096, 32768}; + for (auto& reserve_size : reserve_sizes) + { + hashContainer.reserve(reserve_size); + + // verify bucket count and hashtable load_factor requirements + VERIFY(hashContainer.bucket_count() >= reserve_size); + VERIFY(hashContainer.load_factor() <= ceilf(reserve_size / hashContainer.get_max_load_factor())); + } + + return nErrorCount; + } +}; + + + + + |