Quelle  btree_test.cc   Sprache: C

// Copyright 2018 The Abseil Authors.
//
// 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
//
//      https://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 "absl/container/btree_test.h"

#include <algorithm>
#include <array>
#include <cstdint>
#include <functional>
#include <iostream>
#include <iterator>
#include <limits>
#include <map>
#include <memory>
#include <numeric>
#include <stdexcept>
#include <string>
#include <type_traits>
#include <utility>
#include <vector>

#include "gmock/gmock.h"
#include "gtest/gtest.h"
#include "absl/algorithm/container.h"
#include "absl/base/internal/raw_logging.h"
#include "absl/base/macros.h"
#include "absl/container/btree_map.h"
#include "absl/container/btree_set.h"
#include "absl/container/internal/test_allocator.h"
#include "absl/container/internal/test_instance_tracker.h"
#include "absl/flags/flag.h"
#include "absl/hash/hash_testing.h"
#include "absl/memory/memory.h"
#include "absl/random/random.h"
#include "absl/strings/str_cat.h"
#include "absl/strings/str_split.h"
#include "absl/strings/string_view.h"
#include "absl/types/compare.h"
#include "absl/types/optional.h"

ABSL_FLAG(int, test_values, 10000, "The number of values to use for tests");

namespace absl {
ABSL_NAMESPACE_BEGIN
namespace container_internal {
namespace {

using ::absl::test_internal::CopyableMovableInstance;
using ::absl::test_internal::InstanceTracker;
using ::absl::test_internal::MovableOnlyInstance;
using ::testing::ElementsAre;
using ::testing::ElementsAreArray;
using ::testing::IsEmpty;
using ::testing::IsNull;
using ::testing::Pair;
using ::testing::SizeIs;

template <typename T, typename U>
void CheckPairEquals(const T &x, const U &y) {
  ABSL_INTERNAL_CHECK(x == y, "Values are unequal.");
}

template <typename T, typename U, typename V, typename W>
void CheckPairEquals(const std::pair<T, U> &x, const std::pair<V, W> &y) {
  CheckPairEquals(x.first, y.first);
  CheckPairEquals(x.second, y.second);
}
}  // namespace

// The base class for a sorted associative container checker. TreeType is the
// container type to check and CheckerType is the container type to check
// against. TreeType is expected to be btree_{set,map,multiset,multimap} and
// CheckerType is expected to be {set,map,multiset,multimap}.
template <typename TreeType, typename CheckerType>
class base_checker {
 public:
  using key_type = typename TreeType::key_type;
  using value_type = typename TreeType::value_type;
  using key_compare = typename TreeType::key_compare;
  using pointer = typename TreeType::pointer;
  using const_pointer = typename TreeType::const_pointer;
  using reference = typename TreeType::reference;
  using const_reference = typename TreeType::const_reference;
  using size_type = typename TreeType::size_type;
  using difference_type = typename TreeType::difference_type;
  using iterator = typename TreeType::iterator;
  using const_iterator = typename TreeType::const_iterator;
  using reverse_iterator = typename TreeType::reverse_iterator;
  using const_reverse_iterator = typename TreeType::const_reverse_iterator;

 public:
  base_checker() : const_tree_(tree_) {}
  base_checker(const base_checker &other)
      : tree_(other.tree_), const_tree_(tree_), checker_(other.checker_) {}
  template <typename InputIterator>
  base_checker(InputIterator b, InputIterator e)
      : tree_(b, e), const_tree_(tree_), checker_(b, e) {}

  iterator begin() { return tree_.begin(); }
  const_iterator begin() const { return tree_.begin(); }
  iterator end() { return tree_.end(); }
  const_iterator end() const { return tree_.end(); }
  reverse_iterator rbegin() { return tree_.rbegin(); }
  const_reverse_iterator rbegin() const { return tree_.rbegin(); }
  reverse_iterator rend() { return tree_.rend(); }
  const_reverse_iterator rend() const { return tree_.rend(); }

  template <typename IterType, typename CheckerIterType>
  IterType iter_check(IterType tree_iter, CheckerIterType checker_iter) const {
    if (tree_iter == tree_.end()) {
      ABSL_INTERNAL_CHECK(checker_iter == checker_.end(),
                          "Checker iterator not at end.");
    } else {
      CheckPairEquals(*tree_iter, *checker_iter);
    }
    return tree_iter;
  }
  template <typename IterType, typename CheckerIterType>
  IterType riter_check(IterType tree_iter, CheckerIterType checker_iter) const {
    if (tree_iter == tree_.rend()) {
      ABSL_INTERNAL_CHECK(checker_iter == checker_.rend(),
                          "Checker iterator not at rend.");
    } else {
      CheckPairEquals(*tree_iter, *checker_iter);
    }
    return tree_iter;
  }
  void value_check(const value_type &v) {
    typename KeyOfValue<typename TreeType::key_type,
                        typename TreeType::value_type>::type key_of_value;
    const key_type &key = key_of_value(v);
    CheckPairEquals(*find(key), v);
    lower_bound(key);
    upper_bound(key);
    equal_range(key);
    contains(key);
    count(key);
  }
  void erase_check(const key_type &key) {
    EXPECT_FALSE(tree_.contains(key));
    EXPECT_EQ(tree_.find(key), const_tree_.end());
    EXPECT_FALSE(const_tree_.contains(key));
    EXPECT_EQ(const_tree_.find(key), tree_.end());
    EXPECT_EQ(tree_.equal_range(key).first,
              const_tree_.equal_range(key).second);
  }

  iterator lower_bound(const key_type &key) {
    return iter_check(tree_.lower_bound(key), checker_.lower_bound(key));
  }
  const_iterator lower_bound(const key_type &key) const {
    return iter_check(tree_.lower_bound(key), checker_.lower_bound(key));
  }
  iterator upper_bound(const key_type &key) {
    return iter_check(tree_.upper_bound(key), checker_.upper_bound(key));
  }
  const_iterator upper_bound(const key_type &key) const {
    return iter_check(tree_.upper_bound(key), checker_.upper_bound(key));
  }
  std::pair<iterator, iterator> equal_range(const key_type &key) {
    std::pair<typename CheckerType::iterator, typename CheckerType::iterator>
        checker_res = checker_.equal_range(key);
    std::pair<iterator, iterator> tree_res = tree_.equal_range(key);
    iter_check(tree_res.first, checker_res.first);
    iter_check(tree_res.second, checker_res.second);
    return tree_res;
  }
  std::pair<const_iterator, const_iterator> equal_range(
      const key_type &key) const {
    std::pair<typename CheckerType::const_iterator,
              typename CheckerType::const_iterator>
        checker_res = checker_.equal_range(key);
    std::pair<const_iterator, const_iterator> tree_res = tree_.equal_range(key);
    iter_check(tree_res.first, checker_res.first);
    iter_check(tree_res.second, checker_res.second);
    return tree_res;
  }
  iterator find(const key_type &key) {
    return iter_check(tree_.find(key), checker_.find(key));
  }
  const_iterator find(const key_type &key) const {
    return iter_check(tree_.find(key), checker_.find(key));
  }
  bool contains(const key_type &key) const { return find(key) != end(); }
  size_type count(const key_type &key) const {
    size_type res = checker_.count(key);
    EXPECT_EQ(res, tree_.count(key));
    return res;
  }

  base_checker &operator=(const base_checker &other) {
    tree_ = other.tree_;
    checker_ = other.checker_;
    return *this;
  }

  int erase(const key_type &key) {
    int size = tree_.size();
    int res = checker_.erase(key);
    EXPECT_EQ(res, tree_.count(key));
    EXPECT_EQ(res, tree_.erase(key));
    EXPECT_EQ(tree_.count(key), 0);
    EXPECT_EQ(tree_.size(), size - res);
    erase_check(key);
    return res;
  }
  iterator erase(iterator iter) {
    key_type key = iter.key();
    int size = tree_.size();
    int count = tree_.count(key);
    auto checker_iter = checker_.lower_bound(key);
    for (iterator tmp(tree_.lower_bound(key)); tmp != iter; ++tmp) {
      ++checker_iter;
    }
    auto checker_next = checker_iter;
    ++checker_next;
    checker_.erase(checker_iter);
    iter = tree_.erase(iter);
    EXPECT_EQ(tree_.size(), checker_.size());
    EXPECT_EQ(tree_.size(), size - 1);
    EXPECT_EQ(tree_.count(key), count - 1);
    if (count == 1) {
      erase_check(key);
    }
    return iter_check(iter, checker_next);
  }

  void erase(iterator begin, iterator end) {
    int size = tree_.size();
    int count = std::distance(begin, end);
    auto checker_begin = checker_.lower_bound(begin.key());
    for (iterator tmp(tree_.lower_bound(begin.key())); tmp != begin; ++tmp) {
      ++checker_begin;
    }
    auto checker_end =
        end == tree_.end() ? checker_.end() : checker_.lower_bound(end.key());
    if (end != tree_.end()) {
      for (iterator tmp(tree_.lower_bound(end.key())); tmp != end; ++tmp) {
        ++checker_end;
      }
    }
    const auto checker_ret = checker_.erase(checker_begin, checker_end);
    const auto tree_ret = tree_.erase(begin, end);
    EXPECT_EQ(std::distance(checker_.begin(), checker_ret),
              std::distance(tree_.begin(), tree_ret));
    EXPECT_EQ(tree_.size(), checker_.size());
    EXPECT_EQ(tree_.size(), size - count);
  }

  void clear() {
    tree_.clear();
    checker_.clear();
  }
  void swap(base_checker &other) {
    tree_.swap(other.tree_);
    checker_.swap(other.checker_);
  }

  void verify() const {
    tree_.verify();
    EXPECT_EQ(tree_.size(), checker_.size());

    // Move through the forward iterators using increment.
    auto checker_iter = checker_.begin();
    const_iterator tree_iter(tree_.begin());
    for (; tree_iter != tree_.end(); ++tree_iter, ++checker_iter) {
      CheckPairEquals(*tree_iter, *checker_iter);
    }

    // Move through the forward iterators using decrement.
    for (int n = tree_.size() - 1; n >= 0; --n) {
      iter_check(tree_iter, checker_iter);
      --tree_iter;
      --checker_iter;
    }
    EXPECT_EQ(tree_iter, tree_.begin());
    EXPECT_EQ(checker_iter, checker_.begin());

    // Move through the reverse iterators using increment.
    auto checker_riter = checker_.rbegin();
    const_reverse_iterator tree_riter(tree_.rbegin());
    for (; tree_riter != tree_.rend(); ++tree_riter, ++checker_riter) {
      CheckPairEquals(*tree_riter, *checker_riter);
    }

    // Move through the reverse iterators using decrement.
    for (int n = tree_.size() - 1; n >= 0; --n) {
      riter_check(tree_riter, checker_riter);
      --tree_riter;
      --checker_riter;
    }
    EXPECT_EQ(tree_riter, tree_.rbegin());
    EXPECT_EQ(checker_riter, checker_.rbegin());
  }

  const TreeType &tree() const { return tree_; }

  size_type size() const {
    EXPECT_EQ(tree_.size(), checker_.size());
    return tree_.size();
  }
  size_type max_size() const { return tree_.max_size(); }
  bool empty() const {
    EXPECT_EQ(tree_.empty(), checker_.empty());
    return tree_.empty();
  }

 protected:
  TreeType tree_;
  const TreeType &const_tree_;
  CheckerType checker_;
};

namespace {
// A checker for unique sorted associative containers. TreeType is expected to
// be btree_{set,map} and CheckerType is expected to be {set,map}.
template <typename TreeType, typename CheckerType>
class unique_checker : public base_checker<TreeType, CheckerType> {
  using super_type = base_checker<TreeType, CheckerType>;

 public:
  using iterator = typename super_type::iterator;
  using value_type = typename super_type::value_type;

 public:
  unique_checker() : super_type() {}
  unique_checker(const unique_checker &other) : super_type(other) {}
  template <class InputIterator>
  unique_checker(InputIterator b, InputIterator e) : super_type(b, e) {}
  unique_checker &operator=(const unique_checker &) = default;

  // Insertion routines.
  std::pair<iterator, bool> insert(const value_type &v) {
    int size = this->tree_.size();
    std::pair<typename CheckerType::iterator, bool> checker_res =
        this->checker_.insert(v);
    std::pair<iterator, bool> tree_res = this->tree_.insert(v);
    CheckPairEquals(*tree_res.first, *checker_res.first);
    EXPECT_EQ(tree_res.second, checker_res.second);
    EXPECT_EQ(this->tree_.size(), this->checker_.size());
    EXPECT_EQ(this->tree_.size(), size + tree_res.second);
    return tree_res;
  }
  iterator insert(iterator position, const value_type &v) {
    int size = this->tree_.size();
    std::pair<typename CheckerType::iterator, bool> checker_res =
        this->checker_.insert(v);
    iterator tree_res = this->tree_.insert(position, v);
    CheckPairEquals(*tree_res, *checker_res.first);
    EXPECT_EQ(this->tree_.size(), this->checker_.size());
    EXPECT_EQ(this->tree_.size(), size + checker_res.second);
    return tree_res;
  }
  template <typename InputIterator>
  void insert(InputIterator b, InputIterator e) {
    for (; b != e; ++b) {
      insert(*b);
    }
  }
};

// A checker for multiple sorted associative containers. TreeType is expected
// to be btree_{multiset,multimap} and CheckerType is expected to be
// {multiset,multimap}.
template <typename TreeType, typename CheckerType>
class multi_checker : public base_checker<TreeType, CheckerType> {
  using super_type = base_checker<TreeType, CheckerType>;

 public:
  using iterator = typename super_type::iterator;
  using value_type = typename super_type::value_type;

 public:
  multi_checker() : super_type() {}
  multi_checker(const multi_checker &other) : super_type(other) {}
  template <class InputIterator>
  multi_checker(InputIterator b, InputIterator e) : super_type(b, e) {}
  multi_checker &operator=(const multi_checker &) = default;

  // Insertion routines.
  iterator insert(const value_type &v) {
    int size = this->tree_.size();
    auto checker_res = this->checker_.insert(v);
    iterator tree_res = this->tree_.insert(v);
    CheckPairEquals(*tree_res, *checker_res);
    EXPECT_EQ(this->tree_.size(), this->checker_.size());
    EXPECT_EQ(this->tree_.size(), size + 1);
    return tree_res;
  }
  iterator insert(iterator position, const value_type &v) {
    int size = this->tree_.size();
    auto checker_res = this->checker_.insert(v);
    iterator tree_res = this->tree_.insert(position, v);
    CheckPairEquals(*tree_res, *checker_res);
    EXPECT_EQ(this->tree_.size(), this->checker_.size());
    EXPECT_EQ(this->tree_.size(), size + 1);
    return tree_res;
  }
  template <typename InputIterator>
  void insert(InputIterator b, InputIterator e) {
    for (; b != e; ++b) {
      insert(*b);
    }
  }
};

template <typename T, typename V>
void DoTest(const char *name, T *b, const std::vector<V> &values) {
  typename KeyOfValue<typename T::key_type, V>::type key_of_value;

  T &mutable_b = *b;
  const T &const_b = *b;

  // Test insert.
  for (int i = 0; i < values.size(); ++i) {
    mutable_b.insert(values[i]);
    mutable_b.value_check(values[i]);
  }
  ASSERT_EQ(mutable_b.size(), values.size());

  const_b.verify();

  // Test copy constructor.
  T b_copy(const_b);
  EXPECT_EQ(b_copy.size(), const_b.size());
  for (int i = 0; i < values.size(); ++i) {
    CheckPairEquals(*b_copy.find(key_of_value(values[i])), values[i]);
  }

  // Test range constructor.
  T b_range(const_b.begin(), const_b.end());
  EXPECT_EQ(b_range.size(), const_b.size());
  for (int i = 0; i < values.size(); ++i) {
    CheckPairEquals(*b_range.find(key_of_value(values[i])), values[i]);
  }

  // Test range insertion for values that already exist.
  b_range.insert(b_copy.begin(), b_copy.end());
  b_range.verify();

  // Test range insertion for new values.
  b_range.clear();
  b_range.insert(b_copy.begin(), b_copy.end());
  EXPECT_EQ(b_range.size(), b_copy.size());
  for (int i = 0; i < values.size(); ++i) {
    CheckPairEquals(*b_range.find(key_of_value(values[i])), values[i]);
  }

  // Test assignment to self. Nothing should change.
  b_range.operator=(b_range);
  EXPECT_EQ(b_range.size(), b_copy.size());

  // Test assignment of new values.
  b_range.clear();
  b_range = b_copy;
  EXPECT_EQ(b_range.size(), b_copy.size());

  // Test swap.
  b_range.clear();
  b_range.swap(b_copy);
  EXPECT_EQ(b_copy.size(), 0);
  EXPECT_EQ(b_range.size(), const_b.size());
  for (int i = 0; i < values.size(); ++i) {
    CheckPairEquals(*b_range.find(key_of_value(values[i])), values[i]);
  }
  b_range.swap(b_copy);

  // Test non-member function swap.
  swap(b_range, b_copy);
  EXPECT_EQ(b_copy.size(), 0);
  EXPECT_EQ(b_range.size(), const_b.size());
  for (int i = 0; i < values.size(); ++i) {
    CheckPairEquals(*b_range.find(key_of_value(values[i])), values[i]);
  }
  swap(b_range, b_copy);

  // Test erase via values.
  for (int i = 0; i < values.size(); ++i) {
    mutable_b.erase(key_of_value(values[i]));
    // Erasing a non-existent key should have no effect.
    ASSERT_EQ(mutable_b.erase(key_of_value(values[i])), 0);
  }

  const_b.verify();
  EXPECT_EQ(const_b.size(), 0);

  // Test erase via iterators.
  mutable_b = b_copy;
  for (int i = 0; i < values.size(); ++i) {
    mutable_b.erase(mutable_b.find(key_of_value(values[i])));
  }

  const_b.verify();
  EXPECT_EQ(const_b.size(), 0);

  // Test insert with hint.
  for (int i = 0; i < values.size(); i++) {
    mutable_b.insert(mutable_b.upper_bound(key_of_value(values[i])), values[i]);
  }

  const_b.verify();

  // Test range erase.
  mutable_b.erase(mutable_b.begin(), mutable_b.end());
  EXPECT_EQ(mutable_b.size(), 0);
  const_b.verify();

  // First half.
  mutable_b = b_copy;
  typename T::iterator mutable_iter_end = mutable_b.begin();
  for (int i = 0; i < values.size() / 2; ++i) ++mutable_iter_end;
  mutable_b.erase(mutable_b.begin(), mutable_iter_end);
  EXPECT_EQ(mutable_b.size(), values.size() - values.size() / 2);
  const_b.verify();

  // Second half.
  mutable_b = b_copy;
  typename T::iterator mutable_iter_begin = mutable_b.begin();
  for (int i = 0; i < values.size() / 2; ++i) ++mutable_iter_begin;
  mutable_b.erase(mutable_iter_begin, mutable_b.end());
  EXPECT_EQ(mutable_b.size(), values.size() / 2);
  const_b.verify();

  // Second quarter.
  mutable_b = b_copy;
  mutable_iter_begin = mutable_b.begin();
  for (int i = 0; i < values.size() / 4; ++i) ++mutable_iter_begin;
  mutable_iter_end = mutable_iter_begin;
  for (int i = 0; i < values.size() / 4; ++i) ++mutable_iter_end;
  mutable_b.erase(mutable_iter_begin, mutable_iter_end);
  EXPECT_EQ(mutable_b.size(), values.size() - values.size() / 4);
  const_b.verify();

  mutable_b.clear();
}

template <typename T>
void ConstTest() {
  using value_type = typename T::value_type;
  typename KeyOfValue<typename T::key_type, value_type>::type key_of_value;

  T mutable_b;
  const T &const_b = mutable_b;

  // Insert a single value into the container and test looking it up.
  value_type value = Generator<value_type>(2)(2);
  mutable_b.insert(value);
  EXPECT_TRUE(mutable_b.contains(key_of_value(value)));
  EXPECT_NE(mutable_b.find(key_of_value(value)), const_b.end());
  EXPECT_TRUE(const_b.contains(key_of_value(value)));
  EXPECT_NE(const_b.find(key_of_value(value)), mutable_b.end());
  EXPECT_EQ(*const_b.lower_bound(key_of_value(value)), value);
  EXPECT_EQ(const_b.upper_bound(key_of_value(value)), const_b.end());
  EXPECT_EQ(*const_b.equal_range(key_of_value(value)).first, value);

  // We can only create a non-const iterator from a non-const container.
  typename T::iterator mutable_iter(mutable_b.begin());
  EXPECT_EQ(mutable_iter, const_b.begin());
  EXPECT_NE(mutable_iter, const_b.end());
  EXPECT_EQ(const_b.begin(), mutable_iter);
  EXPECT_NE(const_b.end(), mutable_iter);
  typename T::reverse_iterator mutable_riter(mutable_b.rbegin());
  EXPECT_EQ(mutable_riter, const_b.rbegin());
  EXPECT_NE(mutable_riter, const_b.rend());
  EXPECT_EQ(const_b.rbegin(), mutable_riter);
  EXPECT_NE(const_b.rend(), mutable_riter);

  // We can create a const iterator from a non-const iterator.
  typename T::const_iterator const_iter(mutable_iter);
  EXPECT_EQ(const_iter, mutable_b.begin());
  EXPECT_NE(const_iter, mutable_b.end());
  EXPECT_EQ(mutable_b.begin(), const_iter);
  EXPECT_NE(mutable_b.end(), const_iter);
  typename T::const_reverse_iterator const_riter(mutable_riter);
  EXPECT_EQ(const_riter, mutable_b.rbegin());
  EXPECT_NE(const_riter, mutable_b.rend());
  EXPECT_EQ(mutable_b.rbegin(), const_riter);
  EXPECT_NE(mutable_b.rend(), const_riter);

  // Make sure various methods can be invoked on a const container.
  const_b.verify();
  ASSERT_TRUE(!const_b.empty());
  EXPECT_EQ(const_b.size(), 1);
  EXPECT_GT(const_b.max_size(), 0);
  EXPECT_TRUE(const_b.contains(key_of_value(value)));
  EXPECT_EQ(const_b.count(key_of_value(value)), 1);
}

template <typename T, typename C>
void BtreeTest() {
  ConstTest<T>();

  using V = typename remove_pair_const<typename T::value_type>::type;
  const std::vector<V> random_values = GenerateValuesWithSeed<V>(
      absl::GetFlag(FLAGS_test_values), 4 * absl::GetFlag(FLAGS_test_values),
      GTEST_FLAG_GET(random_seed));

  unique_checker<T, C> container;

  // Test key insertion/deletion in sorted order.
  std::vector<V> sorted_values(random_values);
  std::sort(sorted_values.begin(), sorted_values.end());
  DoTest("sorted: ", &container, sorted_values);

  // Test key insertion/deletion in reverse sorted order.
  std::reverse(sorted_values.begin(), sorted_values.end());
  DoTest("rsorted: ", &container, sorted_values);

  // Test key insertion/deletion in random order.
  DoTest("random: ", &container, random_values);
}

template <typename T, typename C>
void BtreeMultiTest() {
  ConstTest<T>();

  using V = typename remove_pair_const<typename T::value_type>::type;
  const std::vector<V> random_values = GenerateValuesWithSeed<V>(
      absl::GetFlag(FLAGS_test_values), 4 * absl::GetFlag(FLAGS_test_values),
      GTEST_FLAG_GET(random_seed));

  multi_checker<T, C> container;

  // Test keys in sorted order.
  std::vector<V> sorted_values(random_values);
  std::sort(sorted_values.begin(), sorted_values.end());
  DoTest("sorted: ", &container, sorted_values);

  // Test keys in reverse sorted order.
  std::reverse(sorted_values.begin(), sorted_values.end());
  DoTest("rsorted: ", &container, sorted_values);

  // Test keys in random order.
  DoTest("random: ", &container, random_values);

  // Test keys in random order w/ duplicates.
  std::vector<V> duplicate_values(random_values);
  duplicate_values.insert(duplicate_values.end(), random_values.begin(),
                          random_values.end());
  DoTest("duplicates:", &container, duplicate_values);

  // Test all identical keys.
  std::vector<V> identical_values(100);
  std::fill(identical_values.begin(), identical_values.end(),
            Generator<V>(2)(2));
  DoTest("identical: ", &container, identical_values);
}

template <typename T>
void BtreeMapTest() {
  using value_type = typename T::value_type;
  using mapped_type = typename T::mapped_type;

  mapped_type m = Generator<mapped_type>(0)(0);
  (void)m;

  T b;

  // Verify we can insert using operator[].
  for (int i = 0; i < 1000; i++) {
    value_type v = Generator<value_type>(1000)(i);
    b[v.first] = v.second;
  }
  EXPECT_EQ(b.size(), 1000);

  // Test whether we can use the "->" operator on iterators and
  // reverse_iterators. This stresses the btree_map_params::pair_pointer
  // mechanism.
  EXPECT_EQ(b.begin()->first, Generator<value_type>(1000)(0).first);
  EXPECT_EQ(b.begin()->second, Generator<value_type>(1000)(0).second);
  EXPECT_EQ(b.rbegin()->first, Generator<value_type>(1000)(999).first);
  EXPECT_EQ(b.rbegin()->second, Generator<value_type>(1000)(999).second);
}

template <typename T>
void BtreeMultiMapTest() {
  using mapped_type = typename T::mapped_type;
  mapped_type m = Generator<mapped_type>(0)(0);
  (void)m;
}

template <typename K, int N = 256>
void SetTest() {
  EXPECT_EQ(
      sizeof(absl::btree_set<K>),
      2 * sizeof(void *) + sizeof(typename absl::btree_set<K>::size_type));
  using BtreeSet = absl::btree_set<K>;
  BtreeTest<BtreeSet, std::set<K>>();
}

template <typename K, int N = 256>
void MapTest() {
  EXPECT_EQ(
      sizeof(absl::btree_map<K, K>),
      2 * sizeof(void *) + sizeof(typename absl::btree_map<K, K>::size_type));
  using BtreeMap = absl::btree_map<K, K>;
  BtreeTest<BtreeMap, std::map<K, K>>();
  BtreeMapTest<BtreeMap>();
}

TEST(Btree, set_int32) { SetTest<int32_t>(); }
TEST(Btree, set_string) { SetTest<std::string>(); }
TEST(Btree, set_cord) { SetTest<absl::Cord>(); }
TEST(Btree, map_int32) { MapTest<int32_t>(); }
TEST(Btree, map_string) { MapTest<std::string>(); }
TEST(Btree, map_cord) { MapTest<absl::Cord>(); }

template <typename K, int N = 256>
void MultiSetTest() {
  EXPECT_EQ(
      sizeof(absl::btree_multiset<K>),
      2 * sizeof(void *) + sizeof(typename absl::btree_multiset<K>::size_type));
  using BtreeMSet = absl::btree_multiset<K>;
  BtreeMultiTest<BtreeMSet, std::multiset<K>>();
}

template <typename K, int N = 256>
void MultiMapTest() {
  EXPECT_EQ(sizeof(absl::btree_multimap<K, K>),
            2 * sizeof(void *) +
                sizeof(typename absl::btree_multimap<K, K>::size_type));
  using BtreeMMap = absl::btree_multimap<K, K>;
  BtreeMultiTest<BtreeMMap, std::multimap<K, K>>();
  BtreeMultiMapTest<BtreeMMap>();
}

TEST(Btree, multiset_int32) { MultiSetTest<int32_t>(); }
TEST(Btree, multiset_string) { MultiSetTest<std::string>(); }
TEST(Btree, multiset_cord) { MultiSetTest<absl::Cord>(); }
TEST(Btree, multimap_int32) { MultiMapTest<int32_t>(); }
TEST(Btree, multimap_string) { MultiMapTest<std::string>(); }
TEST(Btree, multimap_cord) { MultiMapTest<absl::Cord>(); }

struct CompareIntToString {
  bool operator()(const std::string &a, const std::string &b) const {
    return a < b;
  }
  bool operator()(const std::string &a, int b) const {
    return a < absl::StrCat(b);
  }
  bool operator()(int a, const std::string &b) const {
    return absl::StrCat(a) < b;
  }
  using is_transparent = void;
};

struct NonTransparentCompare {
  template <typename T, typename U>
  bool operator()(const T &t, const U &u) const {
    // Treating all comparators as transparent can cause inefficiencies (see
    // N3657 C++ proposal). Test that for comparators without 'is_transparent'
    // alias (like this one), we do not attempt heterogeneous lookup.
    EXPECT_TRUE((std::is_same<T, U>()));
    return t < u;
  }
};

template <typename T>
bool CanEraseWithEmptyBrace(T t, decltype(t.erase({})) *) {
  return true;
}

template <typename T>
bool CanEraseWithEmptyBrace(T, ...) {
  return false;
}

template <typename T>
void TestHeterogeneous(T table) {
  auto lb = table.lower_bound("3");
  EXPECT_EQ(lb, table.lower_bound(3));
  EXPECT_NE(lb, table.lower_bound(4));
  EXPECT_EQ(lb, table.lower_bound({"3"}));
  EXPECT_NE(lb, table.lower_bound({}));

  auto ub = table.upper_bound("3");
  EXPECT_EQ(ub, table.upper_bound(3));
  EXPECT_NE(ub, table.upper_bound(5));
  EXPECT_EQ(ub, table.upper_bound({"3"}));
  EXPECT_NE(ub, table.upper_bound({}));

  auto er = table.equal_range("3");
  EXPECT_EQ(er, table.equal_range(3));
  EXPECT_NE(er, table.equal_range(4));
  EXPECT_EQ(er, table.equal_range({"3"}));
  EXPECT_NE(er, table.equal_range({}));

  auto it = table.find("3");
  EXPECT_EQ(it, table.find(3));
  EXPECT_NE(it, table.find(4));
  EXPECT_EQ(it, table.find({"3"}));
  EXPECT_NE(it, table.find({}));

  EXPECT_TRUE(table.contains(3));
  EXPECT_FALSE(table.contains(4));
  EXPECT_TRUE(table.count({"3"}));
  EXPECT_FALSE(table.contains({}));

  EXPECT_EQ(1, table.count(3));
  EXPECT_EQ(0, table.count(4));
  EXPECT_EQ(1, table.count({"3"}));
  EXPECT_EQ(0, table.count({}));

  auto copy = table;
  copy.erase(3);
  EXPECT_EQ(table.size() - 1, copy.size());
  copy.erase(4);
  EXPECT_EQ(table.size() - 1, copy.size());
  copy.erase({"5"});
  EXPECT_EQ(table.size() - 2, copy.size());
  EXPECT_FALSE(CanEraseWithEmptyBrace(table, nullptr));

  // Also run it with const T&.
  if (std::is_class<T>()) TestHeterogeneous<const T &>(table);
}

TEST(Btree, HeterogeneousLookup) {
  TestHeterogeneous(btree_set<std::string, CompareIntToString>{"1", "3", "5"});
  TestHeterogeneous(btree_map<std::string, int, CompareIntToString>{
      {"1", 1}, {"3", 3}, {"5", 5}});
  TestHeterogeneous(
      btree_multiset<std::string, CompareIntToString>{"1", "3", "5"});
  TestHeterogeneous(btree_multimap<std::string, int, CompareIntToString>{
      {"1", 1}, {"3", 3}, {"5", 5}});

  // Only maps have .at()
  btree_map<std::string, int, CompareIntToString> map{
      {"", -1}, {"1", 1}, {"3", 3}, {"5", 5}};
  EXPECT_EQ(1, map.at(1));
  EXPECT_EQ(3, map.at({"3"}));
  EXPECT_EQ(-1, map.at({}));
  const auto &cmap = map;
  EXPECT_EQ(1, cmap.at(1));
  EXPECT_EQ(3, cmap.at({"3"}));
  EXPECT_EQ(-1, cmap.at({}));
}

TEST(Btree, NoHeterogeneousLookupWithoutAlias) {
  using StringSet = absl::btree_set<std::string, NonTransparentCompare>;
  StringSet s;
  ASSERT_TRUE(s.insert("hello").second);
  ASSERT_TRUE(s.insert("world").second);
  EXPECT_TRUE(s.end() == s.find("blah"));
  EXPECT_TRUE(s.begin() == s.lower_bound("hello"));
  EXPECT_EQ(1, s.count("world"));
  EXPECT_TRUE(s.contains("hello"));
  EXPECT_TRUE(s.contains("world"));
  EXPECT_FALSE(s.contains("blah"));

  using StringMultiSet =
      absl::btree_multiset<std::string, NonTransparentCompare>;
  StringMultiSet ms;
  ms.insert("hello");
  ms.insert("world");
  ms.insert("world");
  EXPECT_TRUE(ms.end() == ms.find("blah"));
  EXPECT_TRUE(ms.begin() == ms.lower_bound("hello"));
  EXPECT_EQ(2, ms.count("world"));
  EXPECT_TRUE(ms.contains("hello"));
  EXPECT_TRUE(ms.contains("world"));
  EXPECT_FALSE(ms.contains("blah"));
}

TEST(Btree, DefaultTransparent) {
  {
    // `int` does not have a default transparent comparator.
    // The input value is converted to key_type.
    btree_set<int> s = {1};
    double d = 1.1;
    EXPECT_EQ(s.begin(), s.find(d));
    EXPECT_TRUE(s.contains(d));
  }

  {
    // `std::string` has heterogeneous support.
    btree_set<std::string> s = {"A"};
    EXPECT_EQ(s.begin(), s.find(absl::string_view("A")));
    EXPECT_TRUE(s.contains(absl::string_view("A")));
  }
}

class StringLike {
 public:
  StringLike() = default;

  StringLike(const char *s) : s_(s) {  // NOLINT
    ++constructor_calls_;
  }

  bool operator<(const StringLike &a) const { return s_ < a.s_; }

  static void clear_constructor_call_count() { constructor_calls_ = 0; }

  static int constructor_calls() { return constructor_calls_; }

 private:
  static int constructor_calls_;
  std::string s_;
};

int StringLike::constructor_calls_ = 0;

TEST(Btree, HeterogeneousLookupDoesntDegradePerformance) {
  using StringSet = absl::btree_set<StringLike>;
  StringSet s;
  for (int i = 0; i < 100; ++i) {
    ASSERT_TRUE(s.insert(absl::StrCat(i).c_str()).second);
  }
  StringLike::clear_constructor_call_count();
  s.find("50");
  ASSERT_EQ(1, StringLike::constructor_calls());

  StringLike::clear_constructor_call_count();
  s.contains("50");
  ASSERT_EQ(1, StringLike::constructor_calls());

  StringLike::clear_constructor_call_count();
  s.count("50");
  ASSERT_EQ(1, StringLike::constructor_calls());

  StringLike::clear_constructor_call_count();
  s.lower_bound("50");
  ASSERT_EQ(1, StringLike::constructor_calls());

  StringLike::clear_constructor_call_count();
  s.upper_bound("50");
  ASSERT_EQ(1, StringLike::constructor_calls());

  StringLike::clear_constructor_call_count();
  s.equal_range("50");
  ASSERT_EQ(1, StringLike::constructor_calls());

  StringLike::clear_constructor_call_count();
  s.erase("50");
  ASSERT_EQ(1, StringLike::constructor_calls());
}

// Verify that swapping btrees swaps the key comparison functors and that we can
// use non-default constructible comparators.
struct SubstringLess {
  SubstringLess() = delete;
  explicit SubstringLess(int length) : n(length) {}
  bool operator()(const std::string &a, const std::string &b) const {
    return absl::string_view(a).substr(0, n) <
           absl::string_view(b).substr(0, n);
  }
  int n;
};

TEST(Btree, SwapKeyCompare) {
  using SubstringSet = absl::btree_set<std::string, SubstringLess>;
  SubstringSet s1(SubstringLess(1), SubstringSet::allocator_type());
  SubstringSet s2(SubstringLess(2), SubstringSet::allocator_type());

  ASSERT_TRUE(s1.insert("a").second);
  ASSERT_FALSE(s1.insert("aa").second);

  ASSERT_TRUE(s2.insert("a").second);
  ASSERT_TRUE(s2.insert("aa").second);
  ASSERT_FALSE(s2.insert("aaa").second);

  swap(s1, s2);

  ASSERT_TRUE(s1.insert("b").second);
  ASSERT_TRUE(s1.insert("bb").second);
  ASSERT_FALSE(s1.insert("bbb").second);

  ASSERT_TRUE(s2.insert("b").second);
  ASSERT_FALSE(s2.insert("bb").second);
}

TEST(Btree, UpperBoundRegression) {
  // Regress a bug where upper_bound would default-construct a new key_compare
  // instead of copying the existing one.
  using SubstringSet = absl::btree_set<std::string, SubstringLess>;
  SubstringSet my_set(SubstringLess(3));
  my_set.insert("aab");
  my_set.insert("abb");
  // We call upper_bound("aaa").  If this correctly uses the length 3
  // comparator, aaa < aab < abb, so we should get aab as the result.
  // If it instead uses the default-constructed length 2 comparator,
  // aa == aa < ab, so we'll get abb as our result.
  SubstringSet::iterator it = my_set.upper_bound("aaa");
  ASSERT_TRUE(it != my_set.end());
  EXPECT_EQ("aab", *it);
}

TEST(Btree, Comparison) {
  const int kSetSize = 1201;
  absl::btree_set<int64_t> my_set;
  for (int i = 0; i < kSetSize; ++i) {
    my_set.insert(i);
  }
  absl::btree_set<int64_t> my_set_copy(my_set);
  EXPECT_TRUE(my_set_copy == my_set);
  EXPECT_TRUE(my_set == my_set_copy);
  EXPECT_FALSE(my_set_copy != my_set);
  EXPECT_FALSE(my_set != my_set_copy);

  my_set.insert(kSetSize);
  EXPECT_FALSE(my_set_copy == my_set);
  EXPECT_FALSE(my_set == my_set_copy);
  EXPECT_TRUE(my_set_copy != my_set);
  EXPECT_TRUE(my_set != my_set_copy);

  my_set.erase(kSetSize - 1);
  EXPECT_FALSE(my_set_copy == my_set);
  EXPECT_FALSE(my_set == my_set_copy);
  EXPECT_TRUE(my_set_copy != my_set);
  EXPECT_TRUE(my_set != my_set_copy);

  absl::btree_map<std::string, int64_t> my_map;
  for (int i = 0; i < kSetSize; ++i) {
    my_map[std::string(i, 'a')] = i;
  }
  absl::btree_map<std::string, int64_t> my_map_copy(my_map);
  EXPECT_TRUE(my_map_copy == my_map);
  EXPECT_TRUE(my_map == my_map_copy);
  EXPECT_FALSE(my_map_copy != my_map);
  EXPECT_FALSE(my_map != my_map_copy);

  ++my_map_copy[std::string(7, 'a')];
  EXPECT_FALSE(my_map_copy == my_map);
  EXPECT_FALSE(my_map == my_map_copy);
  EXPECT_TRUE(my_map_copy != my_map);
  EXPECT_TRUE(my_map != my_map_copy);

  my_map_copy = my_map;
  my_map["hello"] = kSetSize;
  EXPECT_FALSE(my_map_copy == my_map);
  EXPECT_FALSE(my_map == my_map_copy);
  EXPECT_TRUE(my_map_copy != my_map);
  EXPECT_TRUE(my_map != my_map_copy);

  my_map.erase(std::string(kSetSize - 1, 'a'));
  EXPECT_FALSE(my_map_copy == my_map);
  EXPECT_FALSE(my_map == my_map_copy);
  EXPECT_TRUE(my_map_copy != my_map);
  EXPECT_TRUE(my_map != my_map_copy);
}

TEST(Btree, RangeCtorSanity) {
  std::vector<int> ivec;
  ivec.push_back(1);
  std::map<int, int> imap;
  imap.insert(std::make_pair(1, 2));
  absl::btree_multiset<int> tmset(ivec.begin(), ivec.end());
  absl::btree_multimap<int, int> tmmap(imap.begin(), imap.end());
  absl::btree_set<int> tset(ivec.begin(), ivec.end());
  absl::btree_map<int, int> tmap(imap.begin(), imap.end());
  EXPECT_EQ(1, tmset.size());
  EXPECT_EQ(1, tmmap.size());
  EXPECT_EQ(1, tset.size());
  EXPECT_EQ(1, tmap.size());
}

}  // namespace

class BtreeNodePeer {
 public:
  // Yields the size of a leaf node with a specific number of values.
  template <typename ValueType>
  constexpr static size_t GetTargetNodeSize(size_t target_values_per_node) {
    return btree_node<
        set_params<ValueType, std::less<ValueType>, std::allocator<ValueType>,
                   /*TargetNodeSize=*/256,  // This parameter isn't used here.
                   /*Multi=*/false>>::SizeWithNSlots(target_values_per_node);
  }

  // Yields the number of slots in a (non-root) leaf node for this btree.
  template <typename Btree>
  constexpr static size_t GetNumSlotsPerNode() {
    return btree_node<typename Btree::params_type>::kNodeSlots;
  }

  template <typename Btree>
  constexpr static size_t GetMaxFieldType() {
    return std::numeric_limits<
        typename btree_node<typename Btree::params_type>::field_type>::max();
  }

  template <typename Btree>
  constexpr static bool UsesLinearNodeSearch() {
    return btree_node<typename Btree::params_type>::use_linear_search::value;
  }

  template <typename Btree>
  constexpr static bool FieldTypeEqualsSlotType() {
    return std::is_same<
        typename btree_node<typename Btree::params_type>::field_type,
        typename btree_node<typename Btree::params_type>::slot_type>::value;
  }
};

namespace {

class BtreeMapTest : public ::testing::Test {
 public:
  struct Key {};
  struct Cmp {
    template <typename T>
    bool operator()(T, T) const {
      return false;
    }
  };

  struct KeyLin {
    using absl_btree_prefer_linear_node_search = std::true_type;
  };
  struct CmpLin : Cmp {
    using absl_btree_prefer_linear_node_search = std::true_type;
  };

  struct KeyBin {
    using absl_btree_prefer_linear_node_search = std::false_type;
  };
  struct CmpBin : Cmp {
    using absl_btree_prefer_linear_node_search = std::false_type;
  };

  template <typename K, typename C>
  static bool IsLinear() {
    return BtreeNodePeer::UsesLinearNodeSearch<absl::btree_map<K, int, C>>();
  }
};

TEST_F(BtreeMapTest, TestLinearSearchPreferredForKeyLinearViaAlias) {
  // Test requesting linear search by directly exporting an alias.
  EXPECT_FALSE((IsLinear<Key, Cmp>()));
  EXPECT_TRUE((IsLinear<KeyLin, Cmp>()));
  EXPECT_TRUE((IsLinear<Key, CmpLin>()));
  EXPECT_TRUE((IsLinear<KeyLin, CmpLin>()));
}

TEST_F(BtreeMapTest, LinearChoiceTree) {
  // Cmp has precedence, and is forcing binary
  EXPECT_FALSE((IsLinear<Key, CmpBin>()));
  EXPECT_FALSE((IsLinear<KeyLin, CmpBin>()));
  EXPECT_FALSE((IsLinear<KeyBin, CmpBin>()));
  EXPECT_FALSE((IsLinear<int, CmpBin>()));
  EXPECT_FALSE((IsLinear<std::string, CmpBin>()));
  // Cmp has precedence, and is forcing linear
  EXPECT_TRUE((IsLinear<Key, CmpLin>()));
  EXPECT_TRUE((IsLinear<KeyLin, CmpLin>()));
  EXPECT_TRUE((IsLinear<KeyBin, CmpLin>()));
  EXPECT_TRUE((IsLinear<int, CmpLin>()));
  EXPECT_TRUE((IsLinear<std::string, CmpLin>()));
  // Cmp has no preference, Key determines linear vs binary.
  EXPECT_FALSE((IsLinear<Key, Cmp>()));
  EXPECT_TRUE((IsLinear<KeyLin, Cmp>()));
  EXPECT_FALSE((IsLinear<KeyBin, Cmp>()));
  // arithmetic key w/ std::less or std::greater: linear
  EXPECT_TRUE((IsLinear<int, std::less<int>>()));
  EXPECT_TRUE((IsLinear<double, std::greater<double>>()));
  // arithmetic key w/ custom compare: binary
  EXPECT_FALSE((IsLinear<int, Cmp>()));
  // non-arithmetic key: binary
  EXPECT_FALSE((IsLinear<std::string, std::less<std::string>>()));
}

TEST(Btree, BtreeMapCanHoldMoveOnlyTypes) {
  absl::btree_map<std::string, std::unique_ptr<std::string>> m;

  std::unique_ptr<std::string> &v = m["A"];
  EXPECT_TRUE(v == nullptr);
  v = absl::make_unique<std::string>("X");

  auto iter = m.find("A");
  EXPECT_EQ("X", *iter->second);
}

TEST(Btree, InitializerListConstructor) {
  absl::btree_set<std::string> set({"a", "b"});
  EXPECT_EQ(set.count("a"), 1);
  EXPECT_EQ(set.count("b"), 1);

  absl::btree_multiset<int> mset({1, 1, 4});
  EXPECT_EQ(mset.count(1), 2);
  EXPECT_EQ(mset.count(4), 1);

  absl::btree_map<int, int> map({{1, 5}, {2, 10}});
  EXPECT_EQ(map[1], 5);
  EXPECT_EQ(map[2], 10);

  absl::btree_multimap<int, int> mmap({{1, 5}, {1, 10}});
  auto range = mmap.equal_range(1);
  auto it = range.first;
  ASSERT_NE(it, range.second);
  EXPECT_EQ(it->second, 5);
  ASSERT_NE(++it, range.second);
  EXPECT_EQ(it->second, 10);
  EXPECT_EQ(++it, range.second);
}

TEST(Btree, InitializerListInsert) {
  absl::btree_set<std::string> set;
  set.insert({"a", "b"});
  EXPECT_EQ(set.count("a"), 1);
  EXPECT_EQ(set.count("b"), 1);

  absl::btree_multiset<int> mset;
  mset.insert({1, 1, 4});
  EXPECT_EQ(mset.count(1), 2);
  EXPECT_EQ(mset.count(4), 1);

  absl::btree_map<int, int> map;
  map.insert({{1, 5}, {2, 10}});
  // Test that inserting one element using an initializer list also works.
  map.insert({3, 15});
  EXPECT_EQ(map[1], 5);
  EXPECT_EQ(map[2], 10);
  EXPECT_EQ(map[3], 15);

  absl::btree_multimap<int, int> mmap;
  mmap.insert({{1, 5}, {1, 10}});
  auto range = mmap.equal_range(1);
  auto it = range.first;
  ASSERT_NE(it, range.second);
  EXPECT_EQ(it->second, 5);
  ASSERT_NE(++it, range.second);
  EXPECT_EQ(it->second, 10);
  EXPECT_EQ(++it, range.second);
}

template <typename Compare, typename Key>
void AssertKeyCompareStringAdapted() {
  using Adapted = typename key_compare_adapter<Compare, Key>::type;
  static_assert(
      std::is_same<Adapted, StringBtreeDefaultLess>::value ||
          std::is_same<Adapted, StringBtreeDefaultGreater>::value,
      "key_compare_adapter should have string-adapted this comparator.");
}
template <typename Compare, typename Key>
void AssertKeyCompareNotStringAdapted() {
  using Adapted = typename key_compare_adapter<Compare, Key>::type;
  static_assert(
      !std::is_same<Adapted, StringBtreeDefaultLess>::value &&
          !std::is_same<Adapted, StringBtreeDefaultGreater>::value,
      "key_compare_adapter shouldn't have string-adapted this comparator.");
}

TEST(Btree, KeyCompareAdapter) {
  AssertKeyCompareStringAdapted<std::less<std::string>, std::string>();
  AssertKeyCompareStringAdapted<std::greater<std::string>, std::string>();
  AssertKeyCompareStringAdapted<std::less<absl::string_view>,
                                absl::string_view>();
  AssertKeyCompareStringAdapted<std::greater<absl::string_view>,
                                absl::string_view>();
  AssertKeyCompareStringAdapted<std::less<absl::Cord>, absl::Cord>();
  AssertKeyCompareStringAdapted<std::greater<absl::Cord>, absl::Cord>();
  AssertKeyCompareNotStringAdapted<std::less<int>, int>();
  AssertKeyCompareNotStringAdapted<std::greater<int>, int>();
}

TEST(Btree, RValueInsert) {
  InstanceTracker tracker;

  absl::btree_set<MovableOnlyInstance> set;
  set.insert(MovableOnlyInstance(1));
  set.insert(MovableOnlyInstance(3));
  MovableOnlyInstance two(2);
  set.insert(set.find(MovableOnlyInstance(3)), std::move(two));
  auto it = set.find(MovableOnlyInstance(2));
  ASSERT_NE(it, set.end());
  ASSERT_NE(++it, set.end());
  EXPECT_EQ(it->value(), 3);

  absl::btree_multiset<MovableOnlyInstance> mset;
  MovableOnlyInstance zero(0);
  MovableOnlyInstance zero2(0);
  mset.insert(std::move(zero));
  mset.insert(mset.find(MovableOnlyInstance(0)), std::move(zero2));
  EXPECT_EQ(mset.count(MovableOnlyInstance(0)), 2);

  absl::btree_map<int, MovableOnlyInstance> map;
  std::pair<const int, MovableOnlyInstance> p1 = {1, MovableOnlyInstance(5)};
  std::pair<const int, MovableOnlyInstance> p2 = {2, MovableOnlyInstance(10)};
  std::pair<const int, MovableOnlyInstance> p3 = {3, MovableOnlyInstance(15)};
  map.insert(std::move(p1));
  map.insert(std::move(p3));
  map.insert(map.find(3), std::move(p2));
  ASSERT_NE(map.find(2), map.end());
  EXPECT_EQ(map.find(2)->second.value(), 10);

  absl::btree_multimap<int, MovableOnlyInstance> mmap;
  std::pair<const int, MovableOnlyInstance> p4 = {1, MovableOnlyInstance(5)};
  std::pair<const int, MovableOnlyInstance> p5 = {1, MovableOnlyInstance(10)};
  mmap.insert(std::move(p4));
  mmap.insert(mmap.find(1), std::move(p5));
  auto range = mmap.equal_range(1);
  auto it1 = range.first;
  ASSERT_NE(it1, range.second);
  EXPECT_EQ(it1->second.value(), 10);
  ASSERT_NE(++it1, range.second);
  EXPECT_EQ(it1->second.value(), 5);
  EXPECT_EQ(++it1, range.second);

  EXPECT_EQ(tracker.copies(), 0);
  EXPECT_EQ(tracker.swaps(), 0);
}

template <typename Cmp>
struct CheckedCompareOptedOutCmp : Cmp, BtreeTestOnlyCheckedCompareOptOutBase {
  using Cmp::Cmp;
  CheckedCompareOptedOutCmp() {}
  CheckedCompareOptedOutCmp(Cmp cmp) : Cmp(std::move(cmp)) {}  // NOLINT
};

// A btree set with a specific number of values per node. Opt out of
// checked_compare so that we can expect exact numbers of comparisons.
template <typename Key, int TargetValuesPerNode, typename Cmp = std::less<Key>>
class SizedBtreeSet
    : public btree_set_container<btree<
          set_params<Key, CheckedCompareOptedOutCmp<Cmp>, std::allocator<Key>,
                     BtreeNodePeer::GetTargetNodeSize<Key>(TargetValuesPerNode),
                     /*Multi=*/false>>> {
  using Base = typename SizedBtreeSet::btree_set_container;

 public:
  SizedBtreeSet() = default;
  using Base::Base;
};

template <typename Set>
void ExpectOperationCounts(const int expected_moves,
                           const int expected_comparisons,
                           const std::vector<int> &values,
                           InstanceTracker *tracker, Set *set) {
  for (const int v : values) set->insert(MovableOnlyInstance(v));
  set->clear();
  EXPECT_EQ(tracker->moves(), expected_moves);
  EXPECT_EQ(tracker->comparisons(), expected_comparisons);
  EXPECT_EQ(tracker->copies(), 0);
  EXPECT_EQ(tracker->swaps(), 0);
  tracker->ResetCopiesMovesSwaps();
}

#if defined(ABSL_HAVE_ADDRESS_SANITIZER) || \
    defined(ABSL_HAVE_HWADDRESS_SANITIZER)
constexpr bool kAsan = true;
#else
constexpr bool kAsan = false;
#endif

// Note: when the values in this test change, it is expected to have an impact
// on performance.
TEST(Btree, MovesComparisonsCopiesSwapsTracking) {
  if (kAsan) GTEST_SKIP() << "We do extra operations in ASan mode.";

  InstanceTracker tracker;
  // Note: this is minimum number of values per node.
  SizedBtreeSet<MovableOnlyInstance, /*TargetValuesPerNode=*/4> set4;
  // Note: this is the default number of values per node for a set of int32s
  // (with 64-bit pointers).
  SizedBtreeSet<MovableOnlyInstance, /*TargetValuesPerNode=*/61> set61;
  SizedBtreeSet<MovableOnlyInstance, /*TargetValuesPerNode=*/100> set100;

  // Don't depend on flags for random values because then the expectations will
  // fail if the flags change.
  std::vector<int> values =
      GenerateValuesWithSeed<int>(10000, 1 << 22, /*seed=*/23);

  EXPECT_EQ(BtreeNodePeer::GetNumSlotsPerNode<decltype(set4)>(), 4);
  EXPECT_EQ(BtreeNodePeer::GetNumSlotsPerNode<decltype(set61)>(), 61);
  EXPECT_EQ(BtreeNodePeer::GetNumSlotsPerNode<decltype(set100)>(), 100);
  if (sizeof(void *) == 8) {
    EXPECT_EQ(BtreeNodePeer::GetNumSlotsPerNode<absl::btree_set<int32_t>>(),
              // When we have generations, there is one fewer slot.
              BtreeGenerationsEnabled() ? 60 : 61);
  }

  // Test key insertion/deletion in random order.
  ExpectOperationCounts(56540, 134212, values, &tracker, &set4);
  ExpectOperationCounts(386718, 129807, values, &tracker, &set61);
  ExpectOperationCounts(586761, 130310, values, &tracker, &set100);

  // Test key insertion/deletion in sorted order.
  std::sort(values.begin(), values.end());
  ExpectOperationCounts(24972, 85563, values, &tracker, &set4);
  ExpectOperationCounts(20208, 87757, values, &tracker, &set61);
  ExpectOperationCounts(20124, 96583, values, &tracker, &set100);

  // Test key insertion/deletion in reverse sorted order.
  std::reverse(values.begin(), values.end());
  ExpectOperationCounts(54949, 127531, values, &tracker, &set4);
  ExpectOperationCounts(338813, 118266, values, &tracker, &set61);
  ExpectOperationCounts(534529, 125279, values, &tracker, &set100);
}

struct MovableOnlyInstanceThreeWayCompare {
  absl::weak_ordering operator()(const MovableOnlyInstance &a,
                                 const MovableOnlyInstance &b) const {
    return a.compare(b);
  }
};

// Note: when the values in this test change, it is expected to have an impact
// on performance.
TEST(Btree, MovesComparisonsCopiesSwapsTrackingThreeWayCompare) {
  if (kAsan) GTEST_SKIP() << "We do extra operations in ASan mode.";

  InstanceTracker tracker;
  // Note: this is minimum number of values per node.
  SizedBtreeSet<MovableOnlyInstance, /*TargetValuesPerNode=*/4,
                MovableOnlyInstanceThreeWayCompare>
      set4;
  // Note: this is the default number of values per node for a set of int32s
  // (with 64-bit pointers).
  SizedBtreeSet<MovableOnlyInstance, /*TargetValuesPerNode=*/61,
                MovableOnlyInstanceThreeWayCompare>
      set61;
  SizedBtreeSet<MovableOnlyInstance, /*TargetValuesPerNode=*/100,
                MovableOnlyInstanceThreeWayCompare>
      set100;

  // Don't depend on flags for random values because then the expectations will
  // fail if the flags change.
  std::vector<int> values =
      GenerateValuesWithSeed<int>(10000, 1 << 22, /*seed=*/23);

  EXPECT_EQ(BtreeNodePeer::GetNumSlotsPerNode<decltype(set4)>(), 4);
  EXPECT_EQ(BtreeNodePeer::GetNumSlotsPerNode<decltype(set61)>(), 61);
  EXPECT_EQ(BtreeNodePeer::GetNumSlotsPerNode<decltype(set100)>(), 100);
  if (sizeof(void *) == 8) {
    EXPECT_EQ(BtreeNodePeer::GetNumSlotsPerNode<absl::btree_set<int32_t>>(),
              // When we have generations, there is one fewer slot.
              BtreeGenerationsEnabled() ? 60 : 61);
  }

  // Test key insertion/deletion in random order.
  ExpectOperationCounts(56540, 124221, values, &tracker, &set4);
  ExpectOperationCounts(386718, 119816, values, &tracker, &set61);
  ExpectOperationCounts(586761, 120319, values, &tracker, &set100);

  // Test key insertion/deletion in sorted order.
  std::sort(values.begin(), values.end());
  ExpectOperationCounts(24972, 85563, values, &tracker, &set4);
  ExpectOperationCounts(20208, 87757, values, &tracker, &set61);
  ExpectOperationCounts(20124, 96583, values, &tracker, &set100);

  // Test key insertion/deletion in reverse sorted order.
  std::reverse(values.begin(), values.end());
  ExpectOperationCounts(54949, 117532, values, &tracker, &set4);
  ExpectOperationCounts(338813, 108267, values, &tracker, &set61);
  ExpectOperationCounts(534529, 115280, values, &tracker, &set100);
}

struct NoDefaultCtor {
  int num;
  explicit NoDefaultCtor(int i) : num(i) {}

  friend bool operator<(const NoDefaultCtor &a, const NoDefaultCtor &b) {
    return a.num < b.num;
  }
};

TEST(Btree, BtreeMapCanHoldNoDefaultCtorTypes) {
  absl::btree_map<NoDefaultCtor, NoDefaultCtor> m;

  for (int i = 1; i <= 99; ++i) {
    SCOPED_TRACE(i);
    EXPECT_TRUE(m.emplace(NoDefaultCtor(i), NoDefaultCtor(100 - i)).second);
  }
  EXPECT_FALSE(m.emplace(NoDefaultCtor(78), NoDefaultCtor(0)).second);

  auto iter99 = m.find(NoDefaultCtor(99));
  ASSERT_NE(iter99, m.end());
  EXPECT_EQ(iter99->second.num, 1);

  auto iter1 = m.find(NoDefaultCtor(1));
  ASSERT_NE(iter1, m.end());
  EXPECT_EQ(iter1->second.num, 99);

  auto iter50 = m.find(NoDefaultCtor(50));
  ASSERT_NE(iter50, m.end());
  EXPECT_EQ(iter50->second.num, 50);

  auto iter25 = m.find(NoDefaultCtor(25));
  ASSERT_NE(iter25, m.end());
  EXPECT_EQ(iter25->second.num, 75);
}

TEST(Btree, BtreeMultimapCanHoldNoDefaultCtorTypes) {
  absl::btree_multimap<NoDefaultCtor, NoDefaultCtor> m;

  for (int i = 1; i <= 99; ++i) {
    SCOPED_TRACE(i);
    m.emplace(NoDefaultCtor(i), NoDefaultCtor(100 - i));
  }

  auto iter99 = m.find(NoDefaultCtor(99));
  ASSERT_NE(iter99, m.end());
  EXPECT_EQ(iter99->second.num, 1);

  auto iter1 = m.find(NoDefaultCtor(1));
  ASSERT_NE(iter1, m.end());
  EXPECT_EQ(iter1->second.num, 99);

  auto iter50 = m.find(NoDefaultCtor(50));
  ASSERT_NE(iter50, m.end());
  EXPECT_EQ(iter50->second.num, 50);

  auto iter25 = m.find(NoDefaultCtor(25));
  ASSERT_NE(iter25, m.end());
  EXPECT_EQ(iter25->second.num, 75);
}

TEST(Btree, MapAt) {
  absl::btree_map<int, int> map = {{1, 2}, {2, 4}};
  EXPECT_EQ(map.at(1), 2);
  EXPECT_EQ(map.at(2), 4);
  map.at(2) = 8;
  const absl::btree_map<int, int> &const_map = map;
  EXPECT_EQ(const_map.at(1), 2);
  EXPECT_EQ(const_map.at(2), 8);
#ifdef ABSL_HAVE_EXCEPTIONS
  EXPECT_THROW(map.at(3), std::out_of_range);
#else
  EXPECT_DEATH_IF_SUPPORTED(map.at(3), "absl::btree_map::at");
#endif
}

TEST(Btree, BtreeMultisetEmplace) {
  const int value_to_insert = 123456;
  absl::btree_multiset<int> s;
  auto iter = s.emplace(value_to_insert);
  ASSERT_NE(iter, s.end());
  EXPECT_EQ(*iter, value_to_insert);
  iter = s.emplace(value_to_insert);
  ASSERT_NE(iter, s.end());
  EXPECT_EQ(*iter, value_to_insert);
  auto result = s.equal_range(value_to_insert);
  EXPECT_EQ(std::distance(result.first, result.second), 2);
}

TEST(Btree, BtreeMultisetEmplaceHint) {
  const int value_to_insert = 123456;
  absl::btree_multiset<int> s;
  auto iter = s.emplace(value_to_insert);
  ASSERT_NE(iter, s.end());
  EXPECT_EQ(*iter, value_to_insert);
  iter = s.emplace_hint(iter, value_to_insert);
  // The new element should be before the previously inserted one.
  EXPECT_EQ(iter, s.lower_bound(value_to_insert));
  ASSERT_NE(iter, s.end());
  EXPECT_EQ(*iter, value_to_insert);
}

TEST(Btree, BtreeMultimapEmplace) {
  const int key_to_insert = 123456;
  const char value0[] = "a";
  absl::btree_multimap<int, std::string> m;
  auto iter = m.emplace(key_to_insert, value0);
  ASSERT_NE(iter, m.end());
  EXPECT_EQ(iter->first, key_to_insert);
  EXPECT_EQ(iter->second, value0);
  const char value1[] = "b";
  iter = m.emplace(key_to_insert, value1);
  ASSERT_NE(iter, m.end());
  EXPECT_EQ(iter->first, key_to_insert);
  EXPECT_EQ(iter->second, value1);
  auto result = m.equal_range(key_to_insert);
  EXPECT_EQ(std::distance(result.first, result.second), 2);
}

TEST(Btree, BtreeMultimapEmplaceHint) {
  const int key_to_insert = 123456;
  const char value0[] = "a";
  absl::btree_multimap<int, std::string> m;
  auto iter = m.emplace(key_to_insert, value0);
  ASSERT_NE(iter, m.end());
  EXPECT_EQ(iter->first, key_to_insert);
  EXPECT_EQ(iter->second, value0);
  const char value1[] = "b";
  iter = m.emplace_hint(iter, key_to_insert, value1);
  // The new element should be before the previously inserted one.
  EXPECT_EQ(iter, m.lower_bound(key_to_insert));
  ASSERT_NE(iter, m.end());
  EXPECT_EQ(iter->first, key_to_insert);
  EXPECT_EQ(iter->second, value1);
}

TEST(Btree, ConstIteratorAccessors) {
  absl::btree_set<int> set;
  for (int i = 0; i < 100; ++i) {
    set.insert(i);
  }

  auto it = set.cbegin();
  auto r_it = set.crbegin();
  for (int i = 0; i < 100; ++i, ++it, ++r_it) {
    ASSERT_EQ(*it, i);
    ASSERT_EQ(*r_it, 99 - i);
  }
  EXPECT_EQ(it, set.cend());
  EXPECT_EQ(r_it, set.crend());
}

TEST(Btree, StrSplitCompatible) {
  const absl::btree_set<std::string> split_set = absl::StrSplit("a,b,c", ',');
  const absl::btree_set<std::string> expected_set = {"a", "b", "c"};

  EXPECT_EQ(split_set, expected_set);
}

TEST(Btree, KeyComp) {
  absl::btree_set<int> s;
  EXPECT_TRUE(s.key_comp()(1, 2));
  EXPECT_FALSE(s.key_comp()(2, 2));
  EXPECT_FALSE(s.key_comp()(2, 1));

  absl::btree_map<int, int> m1;
  EXPECT_TRUE(m1.key_comp()(1, 2));
  EXPECT_FALSE(m1.key_comp()(2, 2));
  EXPECT_FALSE(m1.key_comp()(2, 1));

  // Even though we internally adapt the comparator of `m2` to be three-way and
  // heterogeneous, the comparator we expose through key_comp() is the original
  // unadapted comparator.
  absl::btree_map<std::string, int> m2;
  EXPECT_TRUE(m2.key_comp()("a", "b"));
  EXPECT_FALSE(m2.key_comp()("b", "b"));
  EXPECT_FALSE(m2.key_comp()("b", "a"));
}

TEST(Btree, ValueComp) {
  absl::btree_set<int> s;
  EXPECT_TRUE(s.value_comp()(1, 2));
  EXPECT_FALSE(s.value_comp()(2, 2));
  EXPECT_FALSE(s.value_comp()(2, 1));

  absl::btree_map<int, int> m1;
  EXPECT_TRUE(m1.value_comp()(std::make_pair(1, 0), std::make_pair(2, 0)));
  EXPECT_FALSE(m1.value_comp()(std::make_pair(2, 0), std::make_pair(2, 0)));
  EXPECT_FALSE(m1.value_comp()(std::make_pair(2, 0), std::make_pair(1, 0)));

  // Even though we internally adapt the comparator of `m2` to be three-way and
  // heterogeneous, the comparator we expose through value_comp() is based on
  // the original unadapted comparator.
  absl::btree_map<std::string, int> m2;
  EXPECT_TRUE(m2.value_comp()(std::make_pair("a", 0), std::make_pair("b", 0)));
  EXPECT_FALSE(m2.value_comp()(std::make_pair("b", 0), std::make_pair("b", 0)));
  EXPECT_FALSE(m2.value_comp()(std::make_pair("b", 0), std::make_pair("a", 0)));
}

// Test that we have the protected members from the std::map::value_compare API.
// See https://en.cppreference.com/w/cpp/container/map/value_compare.
TEST(Btree, MapValueCompProtected) {
  struct key_compare {
    bool operator()(int l, int r) const { return l < r; }
    int id;
  };
  using value_compare = absl::btree_map<int, int, key_compare>::value_compare;
  struct value_comp_child : public value_compare {
    explicit value_comp_child(key_compare kc) : value_compare(kc) {}
    int GetId() const { return comp.id; }
  };
  value_comp_child c(key_compare{10});
  EXPECT_EQ(c.GetId(), 10);
}

TEST(Btree, DefaultConstruction) {
  absl::btree_set<int> s;
  absl::btree_map<int, int> m;
  absl::btree_multiset<int> ms;
  absl::btree_multimap<int, int> mm;

  EXPECT_TRUE(s.empty());
  EXPECT_TRUE(m.empty());
  EXPECT_TRUE(ms.empty());
  EXPECT_TRUE(mm.empty());
}

TEST(Btree, SwissTableHashable) {
  static constexpr int kValues = 10000;
  std::vector<int> values(kValues);
  std::iota(values.begin(), values.end(), 0);
  std::vector<std::pair<int, int>> map_values;
  for (int v : values) map_values.emplace_back(v, -v);

  using set = absl::btree_set<int>;
  EXPECT_TRUE(absl::VerifyTypeImplementsAbslHashCorrectly({
      set{},
      set{1},
      set{2},
      set{1, 2},
      set{2, 1},
      set(values.begin(), values.end()),
      set(values.rbegin(), values.rend()),
  }));

  using mset = absl::btree_multiset<int>;
  EXPECT_TRUE(absl::VerifyTypeImplementsAbslHashCorrectly({
      mset{},
      mset{1},
      mset{1, 1},
      mset{2},
      mset{2, 2},
      mset{1, 2},
      mset{1, 1, 2},
      mset{1, 2, 2},
      mset{1, 1, 2, 2},
      mset(values.begin(), values.end()),
      mset(values.rbegin(), values.rend()),
  }));

  using map = absl::btree_map<int, int>;
  EXPECT_TRUE(absl::VerifyTypeImplementsAbslHashCorrectly({
      map{},
      map{{1, 0}},
      map{{1, 1}},
      map{{2, 0}},
      map{{2, 2}},
      map{{1, 0}, {2, 1}},
      map(map_values.begin(), map_values.end()),
      map(map_values.rbegin(), map_values.rend()),
  }));

  using mmap = absl::btree_multimap<int, int>;
  EXPECT_TRUE(absl::VerifyTypeImplementsAbslHashCorrectly({
      mmap{},
      mmap{{1, 0}},
      mmap{{1, 1}},
      mmap{{1, 0}, {1, 1}},
      mmap{{1, 1}, {1, 0}},
      mmap{{2, 0}},
      mmap{{2, 2}},
      mmap{{1, 0}, {2, 1}},
      mmap(map_values.begin(), map_values.end()),
      mmap(map_values.rbegin(), map_values.rend()),
  }));
}

TEST(Btree, ComparableSet) {
  absl::btree_set<int> s1 = {1, 2};
  absl::btree_set<int> s2 = {2, 3};
  EXPECT_LT(s1, s2);
  EXPECT_LE(s1, s2);
  EXPECT_LE(s1, s1);
  EXPECT_GT(s2, s1);
  EXPECT_GE(s2, s1);
  EXPECT_GE(s1, s1);
}

TEST(Btree, ComparableSetsDifferentLength) {
  absl::btree_set<int> s1 = {1, 2};
  absl::btree_set<int> s2 = {1, 2, 3};
  EXPECT_LT(s1, s2);
  EXPECT_LE(s1, s2);
  EXPECT_GT(s2, s1);
  EXPECT_GE(s2, s1);
}

TEST(Btree, ComparableMultiset) {
  absl::btree_multiset<int> s1 = {1, 2};
  absl::btree_multiset<int> s2 = {2, 3};
  EXPECT_LT(s1, s2);
  EXPECT_LE(s1, s2);
  EXPECT_LE(s1, s1);
  EXPECT_GT(s2, s1);
  EXPECT_GE(s2, s1);
  EXPECT_GE(s1, s1);
}

TEST(Btree, ComparableMap) {
  absl::btree_map<int, int> s1 = {{1, 2}};
  absl::btree_map<int, int> s2 = {{2, 3}};
  EXPECT_LT(s1, s2);
  EXPECT_LE(s1, s2);
  EXPECT_LE(s1, s1);
  EXPECT_GT(s2, s1);
  EXPECT_GE(s2, s1);
  EXPECT_GE(s1, s1);
}

TEST(Btree, ComparableMultimap) {
  absl::btree_multimap<int, int> s1 = {{1, 2}};
  absl::btree_multimap<int, int> s2 = {{2, 3}};
  EXPECT_LT(s1, s2);
  EXPECT_LE(s1, s2);
  EXPECT_LE(s1, s1);
  EXPECT_GT(s2, s1);
  EXPECT_GE(s2, s1);
  EXPECT_GE(s1, s1);
}

TEST(Btree, ComparableSetWithCustomComparator) {
  // As specified by
  // http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2012/n3337.pdf section
  // [container.requirements.general].12, ordering associative containers always
  // uses default '<' operator
  // - even if otherwise the container uses custom functor.
  absl::btree_set<int, std::greater<int>> s1 = {1, 2};
  absl::btree_set<int, std::greater<int>> s2 = {2, 3};
  EXPECT_LT(s1, s2);
  EXPECT_LE(s1, s2);
  EXPECT_LE(s1, s1);
  EXPECT_GT(s2, s1);
  EXPECT_GE(s2, s1);
  EXPECT_GE(s1, s1);
}

TEST(Btree, EraseReturnsIterator) {
  absl::btree_set<int> set = {1, 2, 3, 4, 5};
  auto result_it = set.erase(set.begin(), set.find(3));
  EXPECT_EQ(result_it, set.find(3));
  result_it = set.erase(set.find(5));
  EXPECT_EQ(result_it, set.end());
}

TEST(Btree, ExtractAndInsertNodeHandleSet) {
  absl::btree_set<int> src1 = {1, 2, 3, 4, 5};
  auto nh = src1.extract(src1.find(3));
  EXPECT_THAT(src1, ElementsAre(1, 2, 4, 5));
  absl::btree_set<int> other;
  absl::btree_set<int>::insert_return_type res = other.insert(std::move(nh));
  EXPECT_THAT(other, ElementsAre(3));
  EXPECT_EQ(res.position, other.find(3));
  EXPECT_TRUE(res.inserted);
  EXPECT_TRUE(res.node.empty());

  absl::btree_set<int> src2 = {3, 4};
  nh = src2.extract(src2.find(3));
  EXPECT_THAT(src2, ElementsAre(4));
  res = other.insert(std::move(nh));
  EXPECT_THAT(other, ElementsAre(3));
  EXPECT_EQ(res.position, other.find(3));
  EXPECT_FALSE(res.inserted);
  ASSERT_FALSE(res.node.empty());
  EXPECT_EQ(res.node.value(), 3);
}

template <typename Set>
void TestExtractWithTrackingForSet() {
  InstanceTracker tracker;
  {
    Set s;
    // Add enough elements to make sure we test internal nodes too.
    const size_t kSize = 1000;
    while (s.size() < kSize) {
      s.insert(MovableOnlyInstance(s.size()));
    }
    for (int i = 0; i < kSize; ++i) {
      // Extract with key
      auto nh = s.extract(MovableOnlyInstance(i));
      EXPECT_EQ(s.size(), kSize - 1);
      EXPECT_EQ(nh.value().value(), i);
      // Insert with node
      s.insert(std::move(nh));
      EXPECT_EQ(s.size(), kSize);

      // Extract with iterator
      auto it = s.find(MovableOnlyInstance(i));
      nh = s.extract(it);
      EXPECT_EQ(s.size(), kSize - 1);
      EXPECT_EQ(nh.value().value(), i);
      // Insert with node and hint
      s.insert(s.begin(), std::move(nh));
      EXPECT_EQ(s.size(), kSize);
    }
  }
  EXPECT_EQ(0, tracker.instances());
}

template <typename Map>
void TestExtractWithTrackingForMap() {
  InstanceTracker tracker;
  {
    Map m;
    // Add enough elements to make sure we test internal nodes too.
    const size_t kSize = 1000;
    while (m.size() < kSize) {
      m.insert(
          {CopyableMovableInstance(m.size()), MovableOnlyInstance(m.size())});
    }
    for (int i = 0; i < kSize; ++i) {
      // Extract with key
      auto nh = m.extract(CopyableMovableInstance(i));
      EXPECT_EQ(m.size(), kSize - 1);
      EXPECT_EQ(nh.key().value(), i);
      EXPECT_EQ(nh.mapped().value(), i);
      // Insert with node
      m.insert(std::move(nh));
      EXPECT_EQ(m.size(), kSize);

      // Extract with iterator
      auto it = m.find(CopyableMovableInstance(i));
      nh = m.extract(it);
      EXPECT_EQ(m.size(), kSize - 1);
      EXPECT_EQ(nh.key().value(), i);
      EXPECT_EQ(nh.mapped().value(), i);
      // Insert with node and hint
      m.insert(m.begin(), std::move(nh));
      EXPECT_EQ(m.size(), kSize);
    }
  }
  EXPECT_EQ(0, tracker.instances());
}

TEST(Btree, ExtractTracking) {
  TestExtractWithTrackingForSet<absl::btree_set<MovableOnlyInstance>>();
  TestExtractWithTrackingForSet<absl::btree_multiset<MovableOnlyInstance>>();
  TestExtractWithTrackingForMap<
      absl::btree_map<CopyableMovableInstance, MovableOnlyInstance>>();
  TestExtractWithTrackingForMap<
      absl::btree_multimap<CopyableMovableInstance, MovableOnlyInstance>>();
}

TEST(Btree, ExtractAndInsertNodeHandleMultiSet) {
  absl::btree_multiset<int> src1 = {1, 2, 3, 3, 4, 5};
  auto nh = src1.extract(src1.find(3));
  EXPECT_THAT(src1, ElementsAre(1, 2, 3, 4, 5));
  absl::btree_multiset<int> other;
  auto res = other.insert(std::move(nh));
  EXPECT_THAT(other, ElementsAre(3));
  EXPECT_EQ(res, other.find(3));

  absl::btree_multiset<int> src2 = {3, 4};
  nh = src2.extract(src2.find(3));
  EXPECT_THAT(src2, ElementsAre(4));
  res = other.insert(std::move(nh));
  EXPECT_THAT(other, ElementsAre(3, 3));
  EXPECT_EQ(res, ++other.find(3));
}

TEST(Btree, ExtractAndInsertNodeHandleMap) {
  absl::btree_map<int, int> src1 = {{1, 2}, {3, 4}, {5, 6}};
  auto nh = src1.extract(src1.find(3));
  EXPECT_THAT(src1, ElementsAre(Pair(1, 2), Pair(5, 6)));
  absl::btree_map<int, int> other;
  absl::btree_map<int, int>::insert_return_type res =
      other.insert(std::move(nh));
  EXPECT_THAT(other, ElementsAre(Pair(3, 4)));
  EXPECT_EQ(res.position, other.find(3));
  EXPECT_TRUE(res.inserted);
  EXPECT_TRUE(res.node.empty());

  absl::btree_map<int, int> src2 = {{3, 6}};
  nh = src2.extract(src2.find(3));
  EXPECT_TRUE(src2.empty());
  res = other.insert(std::move(nh));
  EXPECT_THAT(other, ElementsAre(Pair(3, 4)));
  EXPECT_EQ(res.position, other.find(3));
  EXPECT_FALSE(res.inserted);
  ASSERT_FALSE(res.node.empty());
  EXPECT_EQ(res.node.key(), 3);
--> --------------------

--> maximum size reached

--> --------------------