circular_deque_unittest.cc

// Copyright 2017 The Chromium Authors
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#include "base/containers/circular_deque.h"

#include "base/memory/raw_ptr.h"
#include "base/memory/scoped_refptr.h"
#include "base/test/copy_only_int.h"
#include "base/test/gtest_util.h"
#include "base/test/move_only_int.h"
#include "testing/gmock/include/gmock/gmock.h"
#include "testing/gtest/include/gtest/gtest.h"

using base::internal::VectorBuffer;
using testing::ElementsAre;

namespace base {

namespace {

circular_deque<int> MakeSequence(size_t max) {
  circular_deque<int> ret;
  for (size_t i = 0; i < max; i++) {
    ret.push_back(i);
  }
  return ret;
}

// Cycles through the queue, popping items from the back and pushing items
// at the front to validate behavior across different configurations of the
// queue in relation to the underlying buffer. The tester closure is run for
// each cycle.
template <class QueueT, class Tester>
void CycleTest(circular_deque<QueueT>& queue, const Tester& tester) {
  size_t steps = queue.size() * 2;
  for (size_t i = 0; i < steps; i++) {
    tester(queue, i);
    queue.pop_back();
    queue.push_front(QueueT());
  }
}

class DestructorCounter {
 public:
  DestructorCounter(int* counter) : counter_(counter) {}
  ~DestructorCounter() { ++(*counter_); }

 private:
  raw_ptr<int> counter_;
};

// This class implements the interface that scoped_refptr expects, but actually
// just counts the number of reference count changes that are attempted.
class RefCountChangeCounter {
 public:
  void AddRef() { ++ref_count_changes_; }

  void Release() { ++ref_count_changes_; }

  int ref_count_changes() const { return ref_count_changes_; }

 private:
  int ref_count_changes_ = 0;
};

}  // namespace

TEST(CircularDeque, FillConstructor) {
  constexpr size_t num_elts = 9;

  std::vector<int> foo(15);
  EXPECT_EQ(15u, foo.size());

  // Fill with default constructor.
  {
    circular_deque<int> buf(num_elts);

    EXPECT_EQ(num_elts, buf.size());
    EXPECT_EQ(num_elts, static_cast<size_t>(buf.end() - buf.begin()));

    for (size_t i = 0; i < num_elts; i++) {
      EXPECT_EQ(0, buf[i]);
    }
  }

  // Fill with explicit value.
  {
    int value = 199;
    circular_deque<int> buf(num_elts, value);

    EXPECT_EQ(num_elts, buf.size());
    EXPECT_EQ(num_elts, static_cast<size_t>(buf.end() - buf.begin()));

    for (size_t i = 0; i < num_elts; i++) {
      EXPECT_EQ(value, buf[i]);
    }
  }
}

TEST(CircularDeque, IteratorConstructor) {
  int values[] = {1, 2, 3, 4, 5, 6};
  // SAFETY: Testing the unsafe ctor. begin/end form a valid iterator pair.
  auto first = UNSAFE_BUFFERS(
      circular_deque<CopyOnlyInt>(std::begin(values), std::end(values)));

  circular_deque<CopyOnlyInt> second(first);
  EXPECT_EQ(6u, second.size());
  for (int i = 0; i < 6; i++) {
    EXPECT_EQ(i + 1, second[i].data());
  }
}

TEST(CircularDeque, MoveConstructor) {
  int values[] = {1, 2, 3, 4, 5, 6};
  circular_deque<MoveOnlyInt> first(base::from_range, values);

  circular_deque<MoveOnlyInt> second(std::move(first));
  EXPECT_TRUE(first.empty());
  EXPECT_EQ(6u, second.size());
  for (int i = 0; i < 6; i++) {
    EXPECT_EQ(i + 1, second[i].data());
  }
}

TEST(CircularDeque, InitializerListConstructor) {
  circular_deque<int> empty({});
  ASSERT_TRUE(empty.empty());

  circular_deque<int> first({1, 2, 3, 4, 5, 6});
  EXPECT_EQ(6u, first.size());
  for (int i = 0; i < 6; i++) {
    EXPECT_EQ(i + 1, first[i]);
  }
}

TEST(CircularDeque, RangeConstructor) {
  circular_deque<CopyOnlyInt> deq(base::from_range,
                                  std::vector({1, 2, 3, 4, 5, 6}));
  EXPECT_EQ(6u, deq.size());
  for (int i = 0; i < 6; i++) {
    EXPECT_EQ(i + 1, deq[i].data());
  }
}

TEST(CircularDeque, Destructor) {
  int destruct_count = 0;

  // Contiguous buffer.
  {
    circular_deque<DestructorCounter> q;
    q.resize(5, DestructorCounter(&destruct_count));

    EXPECT_EQ(1, destruct_count);  // The temporary in the call to resize().
    destruct_count = 0;
  }
  EXPECT_EQ(5, destruct_count);  // One call for each.

  // Force a wraparound buffer.
  {
    circular_deque<DestructorCounter> q;
    q.reserve(7);
    q.resize(5, DestructorCounter(&destruct_count));

    // Cycle throught some elements in our buffer to force a wraparound.
    destruct_count = 0;
    for (int i = 0; i < 4; i++) {
      q.emplace_back(&destruct_count);
      q.pop_front();
    }
    EXPECT_EQ(4, destruct_count);  // One for each cycle.
    destruct_count = 0;
  }
  EXPECT_EQ(5, destruct_count);  // One call for each.
}

TEST(CircularDeque, EqualsCopy) {
  circular_deque<int> first = {1, 2, 3, 4, 5, 6};
  circular_deque<int> copy;
  EXPECT_TRUE(copy.empty());
  copy = first;
  EXPECT_EQ(6u, copy.size());
  for (int i = 0; i < 6; i++) {
    EXPECT_EQ(i + 1, first[i]);
    EXPECT_EQ(i + 1, copy[i]);
    EXPECT_NE(&first[i], &copy[i]);
  }
}

TEST(CircularDeque, EqualsMove) {
  circular_deque<int> first = {1, 2, 3, 4, 5, 6};
  circular_deque<int> move;
  EXPECT_TRUE(move.empty());
  move = std::move(first);
  EXPECT_TRUE(first.empty());
  EXPECT_EQ(6u, move.size());
  for (int i = 0; i < 6; i++) {
    EXPECT_EQ(i + 1, move[i]);
  }
}

// Tests that self-assignment is a no-op.
TEST(CircularDeque, EqualsSelf) {
  circular_deque<int> q = {1, 2, 3, 4, 5, 6};
  q = *&q;  // The *& defeats Clang's -Wself-assign warning.
  EXPECT_EQ(6u, q.size());
  for (int i = 0; i < 6; i++) {
    EXPECT_EQ(i + 1, q[i]);
  }
}

TEST(CircularDeque, EqualsInitializerList) {
  circular_deque<int> q;
  EXPECT_TRUE(q.empty());
  q = {1, 2, 3, 4, 5, 6};
  EXPECT_EQ(6u, q.size());
  for (int i = 0; i < 6; i++) {
    EXPECT_EQ(i + 1, q[i]);
  }
}

TEST(CircularDeque, AssignCountValue) {
  circular_deque<int> empty;
  empty.assign(0, 52);
  EXPECT_EQ(0u, empty.size());

  circular_deque<int> full;
  size_t count = 13;
  int value = 12345;
  full.assign(count, value);
  EXPECT_EQ(count, full.size());

  for (size_t i = 0; i < count; i++) {
    EXPECT_EQ(value, full[i]);
  }
}

TEST(CircularDeque, AssignIterator) {
  auto range = std::to_array<int>({11, 12, 13, 14, 15, 16, 17, 18});

  circular_deque<int> empty;
  // SAFETY: begin and begin provide an valid iterator pair over `range`.
  UNSAFE_BUFFERS(empty.assign(std::begin(range), std::begin(range)));
  EXPECT_TRUE(empty.empty());

  circular_deque<int> full;
  // SAFETY: begin and end provide an valid iterator pair over `range`.
  UNSAFE_BUFFERS(full.assign(std::begin(range), std::end(range)));
  EXPECT_EQ(8u, full.size());
  for (size_t i = 0; i < 8u; i++) {
    EXPECT_EQ(range[i], full[i]);
  }
}

TEST(CircularDeque, AssignInitializerList) {
  circular_deque<int> empty;
  empty.assign({});
  EXPECT_TRUE(empty.empty());

  circular_deque<int> full;
  full.assign({11, 12, 13, 14, 15, 16, 17, 18});
  EXPECT_EQ(8u, full.size());
  for (int i = 0; i < 8; i++) {
    EXPECT_EQ(11 + i, full[i]);
  }
}

TEST(CircularDeque, AssignRange) {
  circular_deque<int> empty;
  empty.assign_range(std::vector<int>{});
  EXPECT_TRUE(empty.empty());

  circular_deque<int> full;
  full.assign_range(std::vector<int>{11, 12, 13, 14, 15, 16, 17, 18});
  EXPECT_EQ(8u, full.size());
  for (int i = 0; i < 8; i++) {
    EXPECT_EQ(11 + i, full[i]);
  }
}

// Tests [] and .at().
TEST(CircularDeque, At) {
  circular_deque<int> q = MakeSequence(10);
  CycleTest(q, [](const circular_deque<int>& q, size_t cycle) {
    size_t expected_size = 10;
    EXPECT_EQ(expected_size, q.size());

    // A sequence of 0's.
    size_t index = 0;
    size_t num_zeros = std::min(expected_size, cycle);
    for (size_t i = 0; i < num_zeros; i++, index++) {
      EXPECT_EQ(0, q[index]);
      EXPECT_EQ(0, q.at(index));
    }

    // Followed by a sequence of increasing ints.
    size_t num_ints = expected_size - num_zeros;
    for (int i = 0; i < static_cast<int>(num_ints); i++, index++) {
      EXPECT_EQ(i, q[index]);
      EXPECT_EQ(i, q.at(index));
    }
  });
}

// This also tests the copy constructor with lots of different types of
// input configurations.
TEST(CircularDeque, FrontBackPushPop) {
  circular_deque<int> q = MakeSequence(10);

  int expected_front = 0;
  int expected_back = 9;

  // Go in one direction.
  for (int i = 0; i < 100; i++) {
    const circular_deque<int> const_q(q);

    EXPECT_EQ(expected_front, q.front());
    EXPECT_EQ(expected_back, q.back());
    EXPECT_EQ(expected_front, const_q.front());
    EXPECT_EQ(expected_back, const_q.back());

    expected_front++;
    expected_back++;

    q.pop_front();
    q.push_back(expected_back);
  }

  // Go back in reverse.
  for (int i = 0; i < 100; i++) {
    const circular_deque<int> const_q(q);

    EXPECT_EQ(expected_front, q.front());
    EXPECT_EQ(expected_back, q.back());
    EXPECT_EQ(expected_front, const_q.front());
    EXPECT_EQ(expected_back, const_q.back());

    expected_front--;
    expected_back--;

    q.pop_back();
    q.push_front(expected_front);
  }
}

TEST(CircularDeque, ReallocateWithSplitBuffer) {
  // Tests reallocating a deque with an internal buffer that looks like this:
  //   4   5   x   x   0   1   2   3
  //       end-^       ^-begin
  circular_deque<int> q;
  q.reserve(7);  // Internal buffer is always 1 larger than requested.
  q.push_back(-1);
  q.push_back(-1);
  q.push_back(-1);
  q.push_back(-1);
  q.push_back(0);
  q.pop_front();
  q.pop_front();
  q.pop_front();
  q.pop_front();
  q.push_back(1);
  q.push_back(2);
  q.push_back(3);
  q.push_back(4);
  q.push_back(5);

  q.shrink_to_fit();
  EXPECT_EQ(6u, q.size());

  EXPECT_EQ(0, q[0]);
  EXPECT_EQ(1, q[1]);
  EXPECT_EQ(2, q[2]);
  EXPECT_EQ(3, q[3]);
  EXPECT_EQ(4, q[4]);
  EXPECT_EQ(5, q[5]);
}

TEST(CircularDeque, Swap) {
  circular_deque<int> a = MakeSequence(10);
  circular_deque<int> b = MakeSequence(100);

  a.swap(b);
  EXPECT_EQ(100u, a.size());
  for (int i = 0; i < 100; i++) {
    EXPECT_EQ(i, a[i]);
  }

  EXPECT_EQ(10u, b.size());
  for (int i = 0; i < 10; i++) {
    EXPECT_EQ(i, b[i]);
  }
}

TEST(CircularDeque, Iteration) {
  circular_deque<int> q = MakeSequence(10);

  int expected_front = 0;
  int expected_back = 9;

  // This loop causes various combinations of begin and end to be tested.
  for (int i = 0; i < 30; i++) {
    // Range-based for loop going forward.
    int current_expected = expected_front;
    for (int cur : q) {
      EXPECT_EQ(current_expected, cur);
      current_expected++;
    }

    // Manually test reverse iterators.
    current_expected = expected_back;
    for (auto cur = q.crbegin(); cur < q.crend(); cur++) {
      EXPECT_EQ(current_expected, *cur);
      current_expected--;
    }

    expected_front++;
    expected_back++;

    q.pop_front();
    q.push_back(expected_back);
  }

  // Go back in reverse.
  for (int i = 0; i < 100; i++) {
    const circular_deque<int> const_q(q);

    EXPECT_EQ(expected_front, q.front());
    EXPECT_EQ(expected_back, q.back());
    EXPECT_EQ(expected_front, const_q.front());
    EXPECT_EQ(expected_back, const_q.back());

    expected_front--;
    expected_back--;

    q.pop_back();
    q.push_front(expected_front);
  }
}

TEST(CircularDeque, IteratorComparisons) {
  circular_deque<int> q = MakeSequence(10);

  // This loop causes various combinations of begin and end to be tested.
  for (int i = 0; i < 30; i++) {
    EXPECT_LT(q.begin(), q.end());
    EXPECT_LE(q.begin(), q.end());
    EXPECT_LE(q.begin(), q.begin());

    EXPECT_GT(q.end(), q.begin());
    EXPECT_GE(q.end(), q.begin());
    EXPECT_GE(q.end(), q.end());

    EXPECT_EQ(q.begin(), q.begin());
    EXPECT_NE(q.begin(), q.end());

    q.push_front(10);
    q.pop_back();
  }
}

TEST(CircularDeque, IteratorIncDec) {
  circular_deque<int> q;

  // No-op offset computations with no capacity.
  EXPECT_EQ(q.end(), q.end() + 0);
  EXPECT_EQ(q.end(), q.end() - 0);

  q = MakeSequence(10);

  // Mutable preincrement, predecrement.
  {
    circular_deque<int>::iterator it = q.begin();
    circular_deque<int>::iterator op_result = ++it;
    EXPECT_EQ(1, *op_result);
    EXPECT_EQ(1, *it);

    op_result = --it;
    EXPECT_EQ(0, *op_result);
    EXPECT_EQ(0, *it);
  }

  // Const preincrement, predecrement.
  {
    circular_deque<int>::const_iterator it = q.begin();
    circular_deque<int>::const_iterator op_result = ++it;
    EXPECT_EQ(1, *op_result);
    EXPECT_EQ(1, *it);

    op_result = --it;
    EXPECT_EQ(0, *op_result);
    EXPECT_EQ(0, *it);
  }

  // Mutable postincrement, postdecrement.
  {
    circular_deque<int>::iterator it = q.begin();
    circular_deque<int>::iterator op_result = it++;
    EXPECT_EQ(0, *op_result);
    EXPECT_EQ(1, *it);

    op_result = it--;
    EXPECT_EQ(1, *op_result);
    EXPECT_EQ(0, *it);
  }

  // Const postincrement, postdecrement.
  {
    circular_deque<int>::const_iterator it = q.begin();
    circular_deque<int>::const_iterator op_result = it++;
    EXPECT_EQ(0, *op_result);
    EXPECT_EQ(1, *it);

    op_result = it--;
    EXPECT_EQ(1, *op_result);
    EXPECT_EQ(0, *it);
  }
}

TEST(CircularDeque, IteratorIntegerOps) {
  circular_deque<int> q = MakeSequence(10);

  int expected_front = 0;
  int expected_back = 9;

  for (int i = 0; i < 30; i++) {
    EXPECT_EQ(0, q.begin() - q.begin());
    EXPECT_EQ(0, q.end() - q.end());
    EXPECT_EQ(q.size(), static_cast<size_t>(q.end() - q.begin()));

    // +=
    circular_deque<int>::iterator eight = q.begin();
    eight += 8;
    EXPECT_EQ(8, eight - q.begin());
    EXPECT_EQ(expected_front + 8, *eight);

    // -=
    eight -= 8;
    EXPECT_EQ(q.begin(), eight);

    // +
    eight = eight + 8;
    EXPECT_EQ(8, eight - q.begin());

    // -
    eight = eight - 8;
    EXPECT_EQ(q.begin(), eight);

    expected_front++;
    expected_back++;

    q.pop_front();
    q.push_back(expected_back);
  }
}

TEST(CircularDeque, IteratorArrayAccess) {
  circular_deque<int> q = MakeSequence(10);

  circular_deque<int>::iterator begin = q.begin();
  EXPECT_EQ(0, begin[0]);
  EXPECT_EQ(9, begin[9]);

  circular_deque<int>::iterator end = q.end();
  EXPECT_EQ(0, end[-10]);
  EXPECT_EQ(9, end[-1]);

  begin[0] = 100;
  EXPECT_EQ(100, end[-10]);
}

TEST(CircularDeque, ReverseIterator) {
  circular_deque<int> q;
  q.push_back(4);
  q.push_back(3);
  q.push_back(2);
  q.push_back(1);

  circular_deque<int>::reverse_iterator iter = q.rbegin();
  EXPECT_EQ(1, *iter);
  iter++;
  EXPECT_EQ(2, *iter);
  ++iter;
  EXPECT_EQ(3, *iter);
  iter++;
  EXPECT_EQ(4, *iter);
  ++iter;
  EXPECT_EQ(q.rend(), iter);
}

TEST(CircularDeque, CapacityReserveShrink) {
  circular_deque<int> q;

  // A default constructed queue should have no capacity since it should waste
  // no space.
  EXPECT_TRUE(q.empty());
  EXPECT_EQ(0u, q.size());
  EXPECT_EQ(0u, q.capacity());

  size_t new_capacity = 100;
  q.reserve(new_capacity);
  EXPECT_EQ(new_capacity, q.capacity());

  // Adding that many items should not cause a resize.
  for (size_t i = 0; i < new_capacity; i++) {
    q.push_back(i);
  }
  EXPECT_EQ(new_capacity, q.size());
  EXPECT_EQ(new_capacity, q.capacity());

  // Shrink to fit to a smaller size.
  size_t capacity_2 = new_capacity / 2;
  q.resize(capacity_2);
  q.shrink_to_fit();
  EXPECT_EQ(capacity_2, q.size());
  EXPECT_EQ(capacity_2, q.capacity());
}

TEST(CircularDeque, CapacityAutoShrink) {
  size_t big_size = 1000u;
  circular_deque<int> q;
  q.resize(big_size);

  size_t big_capacity = q.capacity();

  // Delete 3/4 of the items.
  for (size_t i = 0; i < big_size / 4 * 3; i++) {
    q.pop_back();
  }

  // The capacity should have shrunk by deleting that many items.
  size_t medium_capacity = q.capacity();
  EXPECT_GT(big_capacity, medium_capacity);

  // Using resize to shrink should keep some extra capacity.
  q.resize(1);
  EXPECT_LT(1u, q.capacity());

  q.resize(0);
  EXPECT_LT(0u, q.capacity());

  // Using clear() should delete everything.
  q.clear();
  EXPECT_EQ(0u, q.capacity());
}

TEST(CircularDeque, ClearAndEmpty) {
  circular_deque<int> q;
  EXPECT_TRUE(q.empty());

  q.resize(10);
  EXPECT_EQ(10u, q.size());
  EXPECT_FALSE(q.empty());

  q.clear();
  EXPECT_EQ(0u, q.size());
  EXPECT_TRUE(q.empty());

  // clear() also should reset the capacity.
  EXPECT_EQ(0u, q.capacity());
}

TEST(CircularDeque, Resize) {
  circular_deque<int> q;

  // Resize with default constructor.
  size_t first_size = 10;
  q.resize(first_size);
  EXPECT_EQ(first_size, q.size());
  for (size_t i = 0; i < first_size; i++) {
    EXPECT_EQ(0, q[i]);
  }

  // Resize with different value.
  size_t second_expand = 10;
  q.resize(first_size + second_expand, 3);
  EXPECT_EQ(first_size + second_expand, q.size());
  for (size_t i = 0; i < first_size; i++) {
    EXPECT_EQ(0, q[i]);
  }
  for (size_t i = 0; i < second_expand; i++) {
    EXPECT_EQ(3, q[i + first_size]);
  }

  // Erase from the end and add to the beginning so resize is forced to cross
  // a circular buffer wrap boundary.
  q.shrink_to_fit();
  for (int i = 0; i < 5; i++) {
    q.pop_back();
    q.push_front(6);
  }
  q.resize(10);

  EXPECT_EQ(6, q[0]);
  EXPECT_EQ(6, q[1]);
  EXPECT_EQ(6, q[2]);
  EXPECT_EQ(6, q[3]);
  EXPECT_EQ(6, q[4]);
  EXPECT_EQ(0, q[5]);
  EXPECT_EQ(0, q[6]);
  EXPECT_EQ(0, q[7]);
  EXPECT_EQ(0, q[8]);
  EXPECT_EQ(0, q[9]);
}

// Tests destructor behavior of resize.
TEST(CircularDeque, ResizeDelete) {
  int counter = 0;
  circular_deque<DestructorCounter> q;
  q.resize(10, DestructorCounter(&counter));
  // The one temporary when calling resize() should be deleted, that's it.
  EXPECT_EQ(1, counter);

  // The loops below assume the capacity will be set by resize().
  EXPECT_EQ(10u, q.capacity());

  // Delete some via resize(). This is done so that the wasted items are
  // still greater than the size() so that auto-shrinking is not triggered
  // (which will mess up our destructor counting).
  counter = 0;
  q.resize(8, DestructorCounter(&counter));
  // 2 deleted ones + the one temporary in the resize() call.
  EXPECT_EQ(3, counter);

  // Cycle through some items so two items will cross the boundary in the
  // 11-item buffer (one more than the capacity).
  //   Before: x x x x x x x x . . .
  //   After:  x . . . x x x x x x x
  counter = 0;
  for (int i = 0; i < 4; i++) {
    q.emplace_back(&counter);
    q.pop_front();
  }
  EXPECT_EQ(4, counter);  // Loop should have deleted 7 items.

  // Delete two items with resize, these should be on either side of the
  // buffer wrap point.
  counter = 0;
  q.resize(6, DestructorCounter(&counter));
  // 2 deleted ones + the one temporary in the resize() call.
  EXPECT_EQ(3, counter);
}

TEST(CircularDeque, InsertEraseSingle) {
  circular_deque<int> q;
  q.push_back(1);
  q.push_back(2);

  // Insert at the beginning.
  auto result = q.insert(q.begin(), 0);
  EXPECT_EQ(q.begin(), result);
  EXPECT_EQ(3u, q.size());
  EXPECT_EQ(0, q[0]);
  EXPECT_EQ(1, q[1]);
  EXPECT_EQ(2, q[2]);

  // Erase at the beginning.
  result = q.erase(q.begin());
  EXPECT_EQ(q.begin(), result);
  EXPECT_EQ(2u, q.size());
  EXPECT_EQ(1, q[0]);
  EXPECT_EQ(2, q[1]);

  // Insert at the end.
  result = q.insert(q.end(), 3);
  EXPECT_EQ(q.end() - 1, result);
  EXPECT_EQ(1, q[0]);
  EXPECT_EQ(2, q[1]);
  EXPECT_EQ(3, q[2]);

  // Erase at the end.
  result = q.erase(q.end() - 1);
  EXPECT_EQ(q.end(), result);
  EXPECT_EQ(1, q[0]);
  EXPECT_EQ(2, q[1]);

  // Insert in the middle.
  result = q.insert(q.begin() + 1, 10);
  EXPECT_EQ(q.begin() + 1, result);
  EXPECT_EQ(1, q[0]);
  EXPECT_EQ(10, q[1]);
  EXPECT_EQ(2, q[2]);

  // Erase in the middle.
  result = q.erase(q.begin() + 1);
  EXPECT_EQ(q.begin() + 1, result);
  EXPECT_EQ(1, q[0]);
  EXPECT_EQ(2, q[1]);
}

TEST(CircularDeque, InsertFill) {
  circular_deque<int> q;

  // Fill when empty.
  q.insert(q.begin(), 2, 1);

  // 0's at the beginning.
  q.insert(q.begin(), 2, 0);

  // 50's in the middle (now at offset 3).
  q.insert(q.begin() + 3, 2, 50);

  // 200's at the end.
  q.insert(q.end(), 2, 200);

  ASSERT_EQ(8u, q.size());
  EXPECT_EQ(0, q[0]);
  EXPECT_EQ(0, q[1]);
  EXPECT_EQ(1, q[2]);
  EXPECT_EQ(50, q[3]);
  EXPECT_EQ(50, q[4]);
  EXPECT_EQ(1, q[5]);
  EXPECT_EQ(200, q[6]);
  EXPECT_EQ(200, q[7]);
}

TEST(CircularDeque, InsertFromPointers) {
  circular_deque<int> q;

  int data[] = {1, 2, 3};
  q.insert(q.begin(), std::begin(data), std::end(data));
  EXPECT_THAT(q, ElementsAre(1, 2, 3));
}

TEST(CircularDeque, InsertEraseRange) {
  circular_deque<int> q;

  // Erase nothing from an empty deque should work.
  q.erase(q.begin(), q.end());

  // Loop index used below to shift the used items in the buffer.
  for (int i = 0; i < 1; i++) {
    circular_deque<int> source;

    // Fill empty range.
    q.insert(q.begin(), source.begin(), source.end());
    ASSERT_EQ(0u, q.size());

    // Have some stuff to insert.
    source.push_back(1);
    source.push_back(2);
    EXPECT_EQ(1, source[0]);
    EXPECT_EQ(2, source[1]);

    q.insert(q.begin(), source.begin(), source.end());
    ASSERT_EQ(2u, q.size());
    EXPECT_EQ(1, q[0]);
    EXPECT_EQ(2, q[1]);

    // Shift the used items in the buffer by i which will place the two used
    // elements in different places in the buffer each time through this loop.
    for (int shift_i = 0; shift_i < i; shift_i++) {
      q.push_back(0);
      q.pop_front();
    }

    // Set the two items to notable values so we can check for them later.
    ASSERT_EQ(2u, q.size());
    q[0] = 100;
    q[1] = 101;

    // Insert at the beginning, middle (now at offset 3), and end.
    q.insert(q.begin(), source.begin(), source.end());
    q.insert(q.begin() + 3, source.begin(), source.end());
    q.insert(q.end(), source.begin(), source.end());

    ASSERT_EQ(8u, q.size());
    EXPECT_EQ(1, q[0]);
    EXPECT_EQ(2, q[1]);
    EXPECT_EQ(100, q[2]);  // First inserted one.
    EXPECT_EQ(1, q[3]);
    EXPECT_EQ(2, q[4]);
    EXPECT_EQ(101, q[5]);  // First inserted second one.
    EXPECT_EQ(1, q[6]);
    EXPECT_EQ(2, q[7]);

    // Now erase the inserted ranges. Try each subsection also with no items
    // being erased, which should be a no-op.
    auto result = q.erase(q.begin(), q.begin());  // No-op.
    EXPECT_EQ(q.begin(), result);
    result = q.erase(q.begin(), q.begin() + 2);
    EXPECT_EQ(q.begin(), result);

    result = q.erase(q.begin() + 1, q.begin() + 1);  // No-op.
    EXPECT_EQ(q.begin() + 1, result);
    result = q.erase(q.begin() + 1, q.begin() + 3);
    EXPECT_EQ(q.begin() + 1, result);

    result = q.erase(q.end() - 2, q.end() - 2);  // No-op.
    EXPECT_EQ(q.end() - 2, result);
    result = q.erase(q.end() - 2, q.end());
    EXPECT_EQ(q.end(), result);

    ASSERT_EQ(2u, q.size());
    EXPECT_EQ(100, q[0]);
    EXPECT_EQ(101, q[1]);

    // Erase everything.
    result = q.erase(q.begin(), q.end());
    EXPECT_EQ(q.end(), result);
    EXPECT_TRUE(q.empty());
  }
}

TEST(CircularDeque, EmplaceMoveOnly) {
  int values[] = {1, 3};
  circular_deque<MoveOnlyInt> q(base::from_range, values);

  q.emplace(q.begin(), MoveOnlyInt(0));
  q.emplace(q.begin() + 2, MoveOnlyInt(2));
  q.emplace(q.end(), MoveOnlyInt(4));

  ASSERT_EQ(5u, q.size());
  EXPECT_EQ(0, q[0].data());
  EXPECT_EQ(1, q[1].data());
  EXPECT_EQ(2, q[2].data());
  EXPECT_EQ(3, q[3].data());
  EXPECT_EQ(4, q[4].data());
}

TEST(CircularDeque, EmplaceFrontBackReturnsReference) {
  circular_deque<int> q;
  q.reserve(2);

  int& front = q.emplace_front(1);
  int& back = q.emplace_back(2);
  ASSERT_EQ(2u, q.size());
  EXPECT_EQ(1, q[0]);
  EXPECT_EQ(2, q[1]);

  EXPECT_EQ(&front, &q.front());
  EXPECT_EQ(&back, &q.back());

  front = 3;
  back = 4;

  ASSERT_EQ(2u, q.size());
  EXPECT_EQ(3, q[0]);
  EXPECT_EQ(4, q[1]);

  EXPECT_EQ(&front, &q.front());
  EXPECT_EQ(&back, &q.back());
}

// This test tries to dereference an iterator after mutating the container.
TEST(CircularDeque, UseIteratorAfterMutate) {
  circular_deque<int> q;
  q.push_back(0);

  auto old_begin = q.begin();
  EXPECT_EQ(0, *old_begin);

  q.push_back(1);

  // This statement is not executed when DCHECKs are disabled.
  EXPECT_DCHECK_DEATH(*old_begin);
}

// This test verifies that a scoped_refptr specifically is moved rather than
// copied when a circular_deque is resized. It would be extremely inefficient if
// it was copied in this case.
TEST(CircularDeque, DoesntChurnRefCount) {
  static constexpr size_t kCount = 10;
  RefCountChangeCounter counters[kCount];
  circular_deque<scoped_refptr<RefCountChangeCounter>> deque;
  bool checked_capacity = false;
  for (auto& counter : counters) {
    deque.push_back(scoped_refptr<RefCountChangeCounter>(&counter));
    if (!checked_capacity) {
      // Verify that the deque will have to reallocate.
      EXPECT_LT(deque.capacity(), kCount);
      checked_capacity = true;
    }
  }
  // Verify that reallocation has happened.
  EXPECT_GE(deque.capacity(), kCount);
  for (const auto& counter : counters) {
    EXPECT_EQ(1, counter.ref_count_changes());
  }
}

TEST(CircularDeque, EraseBoundaryConditions) {
  {
    circular_deque<int> d;

    d.reserve(3u);
    d.push_back(0);
    d.push_back(1);
    d.pop_front();  // Drop 0, making 1 empty spot at the front.
    d.push_back(2);
    d.push_back(3);
    EXPECT_THAT(d, ElementsAre(1, 2, 3));
    // Now the buffer has [_, 1, 2, 3] and the erase will make us copy elements
    // from the end of the buffer. It's erasing from the middle of the values so
    // that we can't just shift the begin up. We will try to copy 1 items from
    // the back of the buffer, but if we do it wrong as the end of the copy
    // range is at the start of the buffer, we'll end up trying to copy from
    // outside the buffer.
    d.erase(std::ranges::find(d, 2));
    EXPECT_THAT(d, ElementsAre(1, 3));
  }

  {
    circular_deque<int> d;

    d.reserve(4u);
    d.push_back(0);
    d.push_back(0);
    d.pop_front();  // Drop 0, making 1 empty spot at the front.
    d.push_back(1);
    d.pop_front();  // Drop 0, making 2 empty spots at the front.
    d.push_back(2);
    d.push_back(3);
    d.push_back(4);  // Eats the first empty spot at the front.
    EXPECT_THAT(d, ElementsAre(1, 2, 3, 4));
    // Now the buffer has [4, _, 1, 2, 3] and the erase will make us copy
    // elements from the end of the buffer and from the start of the buffer.
    // It's erasing from the middle of the values so that we can't just shift
    // the begin up. We will try to copy 1 items from the back of the buffer,
    // and 1 fro mthe start, but if we do it wrong we'll end up trying to copy
    // from outside the buffer.
    d.erase(std::ranges::find(d, 2), std::ranges::find(d, 4));
    EXPECT_THAT(d, ElementsAre(1, 4));
  }

  {
    circular_deque<int> d;

    d.reserve(4u);
    d.push_back(0);
    d.push_back(0);
    d.pop_front();  // Drop 0, making 1 empty spot at the front.
    d.push_back(0);
    d.pop_front();  // Drop 0, making 2 empty spots at the front.
    d.push_back(1);
    d.pop_front();  // Drop 0, making 3 empty spots at the front.
    d.push_back(2);
    d.push_back(3);  // Eats the first empty spot at the front.
    d.push_back(4);  // Eats the second empty spot at the front.
    EXPECT_THAT(d, ElementsAre(1, 2, 3, 4));
    // Now the buffer has [3, 4, _, 1, 2] and the erase will wrap around the
    // end. It's erasing from the middle of the values so that we can't just
    // shift the begin up. We're going to move more than one element from the
    // front of the buffer to the back. If we do it wrong, we'll write out the
    // back of the buffer.
    d.erase(std::ranges::find(d, 2), std::ranges::find(d, 4));
    EXPECT_THAT(d, ElementsAre(1, 4));
  }
}

TEST(CircularDeque, InsertBoundaryConditions) {
  {
    circular_deque<int> d;

    d.reserve(3u);
    d.push_back(0);
    d.push_back(1);
    d.pop_front();  // Drop 0, making 1 empty spot at the front.
    d.push_back(2);
    EXPECT_THAT(d, ElementsAre(1, 2));
    // Now the buffer has [_, 1, 2], when we insert between 1 and 2, it will
    // have to copy 2 to the front of the buffer. If we do it wrong, it will
    // copy it out of bounds.
    d.insert(std::ranges::find(d, 2), 3);
    EXPECT_THAT(d, ElementsAre(1, 3, 2));
  }

  {
    circular_deque<int> d;

    d.reserve(4u);
    d.push_back(0);
    d.push_back(0);
    d.push_back(0);
    d.push_back(1);
    d.pop_front();  // Drop 0, making 1 empty spot at the front.
    d.pop_front();  // Drop 0, making 2 empty spots at the front.
    d.pop_front();  // Drop 0, making 3 empty spots at the front.
    d.push_back(2);
    d.push_back(3);  // Eat the first empty spot at the front.
    EXPECT_THAT(d, ElementsAre(1, 2, 3));
    // Now the buffer has [3, _, _, 1, 2], when we insert between 1 and 2, it
    // will have to copy 2 to the front of the buffer and copy from 3 at the
    // front of the buffer. If we do it wrong, it will copy to/from outside the
    // bounds of the buffer.
    d.insert(std::ranges::find(d, 2), 4);
    EXPECT_THAT(d, ElementsAre(1, 4, 2, 3));
  }
}

}  // namespace base