third_party/pigweed/repo/pw_containers/flat_map_test.cc

   1 // Copyright 2020 The Pigweed Authors
   2 //
   3 // Licensed under the Apache License, Version 2.0 (the "License"); you may not
   4 // use this file except in compliance with the License. You may obtain a copy of
   5 // the License at
   6 //
   7 //     https://www.apache.org/licenses/LICENSE-2.0
   8 //
   9 // Unless required by applicable law or agreed to in writing, software
  10 // distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
  11 // WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
  12 // License for the specific language governing permissions and limitations under
  13 // the License.
  14
  15 #include "pw_containers/flat_map.h"
  16
  17 #include <limits>
  18
  19 #include "gtest/gtest.h"
  20
  21 namespace pw::containers {
  22 namespace {
  23 constexpr FlatMap<int, char, 5> kOddMap({{
  24     {-3, 'a'},
  25     {0, 'b'},
  26     {1, 'c'},
  27     {50, 'd'},
  28     {100, 'e'},
  29 }});
  30 }  // namespace
  31
  32 TEST(FlatMap, Size) { EXPECT_EQ(kOddMap.size(), static_cast<uint32_t>(5)); }
  33
  34 TEST(FlatMap, EmptyFlatMapSize) {
  35   constexpr FlatMap<int, char, 0> kEmpty({{}});
  36   EXPECT_EQ(kEmpty.size(), static_cast<uint32_t>(0));
  37 }
  38
  39 TEST(FlatMap, Empty) {
  40   constexpr FlatMap<int, char, 0> kEmpty({{}});
  41   EXPECT_TRUE(kEmpty.empty());
  42 }
  43
  44 TEST(FlatMap, NotEmpty) {
  45   constexpr FlatMap<int, char, 1> kNotEmpty({{}});
  46   EXPECT_FALSE(kNotEmpty.empty());
  47 }
  48
  49 TEST(FlatMap, EmptyFlatMapFind) {
  50   constexpr FlatMap<int, char, 0> kEmpty({{}});
  51   EXPECT_EQ(kEmpty.find(0), kEmpty.end());
  52 }
  53
  54 TEST(FlatMap, EmptyFlatMapLowerBound) {
  55   constexpr FlatMap<int, char, 0> kEmpty({{}});
  56   EXPECT_EQ(kEmpty.lower_bound(0), kEmpty.end());
  57 }
  58
  59 TEST(FlatMap, EmptyFlatMapUpperBound) {
  60   constexpr FlatMap<int, char, 0> kEmpty({{}});
  61   EXPECT_EQ(kEmpty.upper_bound(0), kEmpty.end());
  62 }
  63
  64 TEST(FlatMap, EmptyEqualRange) {
  65   constexpr FlatMap<int, char, 0> kEmpty({{}});
  66   EXPECT_EQ(kEmpty.equal_range(0).first, kEmpty.end());
  67   EXPECT_EQ(kEmpty.equal_range(0).second, kEmpty.end());
  68 }
  69
  70 TEST(FlatMap, Contains) {
  71   EXPECT_TRUE(kOddMap.contains(0));
  72   EXPECT_FALSE(kOddMap.contains(10));
  73 }
  74
  75 TEST(FlatMap, Iterate) {
  76   char value = 'a';
  77   for (const auto& item : kOddMap) {
  78     EXPECT_EQ(value, item.second);
  79     EXPECT_EQ(&item, kOddMap.find(item.first));
  80     value += 1;
  81   }
  82 }
  83
  84 TEST(FlatMap, EqualRange) {
  85   auto pair = kOddMap.equal_range(1);
  86   EXPECT_EQ(1, pair.first->first);
  87   EXPECT_EQ(50, pair.second->first);
  88
  89   pair = kOddMap.equal_range(75);
  90   EXPECT_EQ(100, pair.first->first);
  91   EXPECT_EQ(100, pair.second->first);
  92 }
  93
  94 TEST(FlatMap, Find) {
  95   auto it = kOddMap.find(50);
  96   EXPECT_EQ(50, it->first);
  97   EXPECT_EQ('d', it->second);
  98
  99   auto not_found = kOddMap.find(-1);
 100   EXPECT_EQ(kOddMap.cend(), not_found);
 101 }
 102
 103 TEST(FlatMap, UpperBoundLessThanSmallestKey) {
 104   EXPECT_EQ(-3, kOddMap.upper_bound(std::numeric_limits<int>::min())->first);
 105   EXPECT_EQ(-3, kOddMap.upper_bound(-123)->first);
 106   EXPECT_EQ(-3, kOddMap.upper_bound(-4)->first);
 107 }
 108
 109 TEST(FlatMap, UpperBoundBetweenTheTwoSmallestKeys) {
 110   EXPECT_EQ(0, kOddMap.upper_bound(-3)->first);
 111   EXPECT_EQ(0, kOddMap.upper_bound(-2)->first);
 112   EXPECT_EQ(0, kOddMap.upper_bound(-1)->first);
 113 }
 114
 115 TEST(FlatMap, UpperBoundIntermediateKeys) {
 116   EXPECT_EQ(1, kOddMap.upper_bound(0)->first);
 117   EXPECT_EQ('c', kOddMap.upper_bound(0)->second);
 118   EXPECT_EQ(50, kOddMap.upper_bound(1)->first);
 119   EXPECT_EQ('d', kOddMap.upper_bound(1)->second);
 120   EXPECT_EQ(50, kOddMap.upper_bound(2)->first);
 121   EXPECT_EQ(50, kOddMap.upper_bound(49)->first);
 122   EXPECT_EQ(100, kOddMap.upper_bound(51)->first);
 123 }
 124
 125 TEST(FlatMap, UpperBoundGreaterThanLargestKey) {
 126   EXPECT_EQ(kOddMap.end(), kOddMap.upper_bound(100));
 127   EXPECT_EQ(kOddMap.end(), kOddMap.upper_bound(2384924));
 128   EXPECT_EQ(kOddMap.end(),
 129             kOddMap.upper_bound(std::numeric_limits<int>::max()));
 130 }
 131
 132 TEST(FlatMap, LowerBoundLessThanSmallestKey) {
 133   EXPECT_EQ(-3, kOddMap.lower_bound(std::numeric_limits<int>::min())->first);
 134   EXPECT_EQ(-3, kOddMap.lower_bound(-123)->first);
 135   EXPECT_EQ(-3, kOddMap.lower_bound(-4)->first);
 136 }
 137
 138 TEST(FlatMap, LowerBoundBetweenTwoSmallestKeys) {
 139   EXPECT_EQ(-3, kOddMap.lower_bound(-3)->first);
 140   EXPECT_EQ(0, kOddMap.lower_bound(-2)->first);
 141   EXPECT_EQ(0, kOddMap.lower_bound(-1)->first);
 142 }
 143
 144 TEST(FlatMap, LowerBoundIntermediateKeys) {
 145   EXPECT_EQ(0, kOddMap.lower_bound(0)->first);
 146   EXPECT_EQ('b', kOddMap.lower_bound(0)->second);
 147   EXPECT_EQ(1, kOddMap.lower_bound(1)->first);
 148   EXPECT_EQ('c', kOddMap.lower_bound(1)->second);
 149   EXPECT_EQ(50, kOddMap.lower_bound(2)->first);
 150   EXPECT_EQ(50, kOddMap.lower_bound(49)->first);
 151   EXPECT_EQ(100, kOddMap.lower_bound(51)->first);
 152 }
 153
 154 TEST(FlatMap, LowerBoundGreaterThanLargestKey) {
 155   EXPECT_EQ(100, kOddMap.lower_bound(100)->first);
 156   EXPECT_EQ(kOddMap.end(), kOddMap.lower_bound(2384924));
 157   EXPECT_EQ(kOddMap.end(),
 158             kOddMap.lower_bound(std::numeric_limits<int>::max()));
 159 }
 160
 161 TEST(FlatMap, ForEachIteration) {
 162   for (const auto& item : kOddMap) {
 163     EXPECT_NE(item.first, 2);
 164   }
 165 }
 166
 167 TEST(FlatMap, MapsWithUnsortedKeys) {
 168   constexpr FlatMap<int, const char*, 2> bad_array({{
 169       {2, "hello"},
 170       {1, "goodbye"},
 171   }});
 172
 173   EXPECT_EQ(bad_array.begin()->first, 1);
 174
 175   constexpr FlatMap<int, const char*, 2> too_short({{
 176       {1, "goodbye"},
 177   }});
 178   EXPECT_EQ(too_short.begin()->first, 0);
 179 }
 180
 181 }  // namespace pw::containers