/*
 * Copyright (C) 2016 The Android Open Source Project
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

#include <algorithm>
#include <forward_list>
#include <vector>

#include "gtest/gtest.h"
#include "intrusive_forward_list.h"

namespace art {

struct IFLTestValue : public IntrusiveForwardListNode<IFLTestValue> {
  // Deliberately not explicit.
  IFLTestValue(int v) : value(v) { }  // NOLINT(runtime/explicit)

  int value;
};
using IFLTestValueList = IntrusiveForwardList<IFLTestValue>;
using ConstIFLTestValueList = IntrusiveForwardList<const IFLTestValue>;

bool operator==(const IFLTestValue& lhs, const IFLTestValue& rhs) {
  return lhs.value == rhs.value;
}

bool operator<(const IFLTestValue& lhs, const IFLTestValue& rhs) {
  return lhs.value < rhs.value;
}

struct IFLTestValue2 {
  // Deliberately not explicit.
  IFLTestValue2(int v) : hook(), value(v) { }  // NOLINT(runtime/explicit)

  IntrusiveForwardListHook hook;
  int value;
};
using IFLTestValue2List =
    IntrusiveForwardList<IFLTestValue2, IntrusiveForwardListMemberHookTraits<IFLTestValue2>>;

bool operator==(const IFLTestValue2& lhs, const IFLTestValue2& rhs) {
  return lhs.value == rhs.value;
}

bool operator<(const IFLTestValue2& lhs, const IFLTestValue2& rhs) {
  return lhs.value < rhs.value;
}

#define ASSERT_LISTS_EQUAL(expected, value)                                         \
  do {                                                                              \
    ASSERT_EQ((expected).empty(), (value).empty());                                 \
    ASSERT_EQ(std::distance((expected).begin(), (expected).end()),                  \
              std::distance((value).begin(), (value).end()));                       \
    ASSERT_TRUE(std::equal((expected).begin(), (expected).end(), (value).begin())); \
  } while (false)

class IntrusiveForwardListTest : public testing::Test {
 public:
  template <typename ListType>
  void IteratorToConstIterator();

  template <typename ListType>
  void IteratorOperators();

  template <typename ListType>
  void ConstructRange();

  template <typename ListType>
  void Assign();

  template <typename ListType>
  void PushPop();

  template <typename ListType>
  void InsertAfter1();

  template <typename ListType>
  void InsertAfter2();

  template <typename ListType>
  void EraseAfter1();

  template <typename ListType>
  void EraseAfter2();

  template <typename ListType>
  void SwapClear();

  template <typename ListType>
  void SpliceAfter();

  template <typename ListType>
  void Remove();

  template <typename ListType>
  void Unique();

  template <typename ListType>
  void Merge();

  template <typename ListType>
  void Sort1();

  template <typename ListType>
  void Sort2();

  template <typename ListType>
  void Reverse();

  template <typename ListType>
  void ModifyValue();
};

template <typename ListType>
void IntrusiveForwardListTest::IteratorToConstIterator() {
  ListType ifl;
  typename ListType::iterator begin = ifl.begin();
  typename ListType::const_iterator cbegin = ifl.cbegin();
  typename ListType::const_iterator converted_begin = begin;
  ASSERT_TRUE(converted_begin == cbegin);
}

TEST_F(IntrusiveForwardListTest, IteratorToConstIterator) {
  IteratorToConstIterator<IFLTestValueList>();
  IteratorToConstIterator<ConstIFLTestValueList>();
  IteratorToConstIterator<IFLTestValue2List>();
}

template <typename ListType>
void IntrusiveForwardListTest::IteratorOperators() {
  using ValueType = typename ListType::value_type;
  ListType ifl;
  ASSERT_TRUE(ifl.begin() == ifl.cbegin());
  ASSERT_FALSE(ifl.begin() != ifl.cbegin());
  ASSERT_TRUE(ifl.end() == ifl.cend());
  ASSERT_FALSE(ifl.end() != ifl.cend());

  ASSERT_TRUE(ifl.begin() == ifl.end());  // Empty.
  ASSERT_FALSE(ifl.begin() != ifl.end());  // Empty.

  ValueType value(1);
  ifl.insert_after(ifl.cbefore_begin(), value);

  ASSERT_FALSE(ifl.begin() == ifl.end());  // Not empty.
  ASSERT_TRUE(ifl.begin() != ifl.end());  // Not empty.
}

TEST_F(IntrusiveForwardListTest, IteratorOperators) {
  IteratorOperators<IFLTestValueList>();
  IteratorOperators<ConstIFLTestValueList>();
  IteratorOperators<IFLTestValue2List>();
}

template <typename ListType>
void IntrusiveForwardListTest::ConstructRange() {
  using ValueType = typename ListType::value_type;
  std::forward_list<int> ref({ 1, 2, 7 });
  std::vector<ValueType> storage(ref.begin(), ref.end());
  ListType ifl(storage.begin(), storage.end());
  ASSERT_LISTS_EQUAL(ref, ifl);
}

TEST_F(IntrusiveForwardListTest, ConstructRange) {
  ConstructRange<IFLTestValueList>();
  ConstructRange<ConstIFLTestValueList>();
  ConstructRange<IFLTestValue2List>();
}

template <typename ListType>
void IntrusiveForwardListTest::Assign() {
  using ValueType = typename ListType::value_type;
  std::forward_list<int> ref1({ 2, 8, 5 });
  std::vector<ValueType> storage1(ref1.begin(), ref1.end());
  ListType ifl;
  ifl.assign(storage1.begin(), storage1.end());
  ASSERT_LISTS_EQUAL(ref1, ifl);
  std::forward_list<int> ref2({ 7, 1, 3 });
  std::vector<ValueType> storage2(ref2.begin(), ref2.end());
  ifl.assign(storage2.begin(), storage2.end());
  ASSERT_LISTS_EQUAL(ref2, ifl);
}

TEST_F(IntrusiveForwardListTest, Assign) {
  Assign<IFLTestValueList>();
  Assign<ConstIFLTestValueList>();
  Assign<IFLTestValue2List>();
}

template <typename ListType>
void IntrusiveForwardListTest::PushPop() {
  using ValueType = typename ListType::value_type;
  ValueType value3(3);
  ValueType value7(7);
  std::forward_list<int> ref;
  ListType ifl;
  ASSERT_LISTS_EQUAL(ref, ifl);
  ref.push_front(3);
  ifl.push_front(value3);
  ASSERT_LISTS_EQUAL(ref, ifl);
  ASSERT_EQ(3, ifl.front());
  ref.push_front(7);
  ifl.push_front(value7);
  ASSERT_LISTS_EQUAL(ref, ifl);
  ASSERT_EQ(7, ifl.front());
  ref.pop_front();
  ifl.pop_front();
  ASSERT_LISTS_EQUAL(ref, ifl);
  ASSERT_EQ(3, ifl.front());
  ref.pop_front();
  ifl.pop_front();
  ASSERT_LISTS_EQUAL(ref, ifl);
}

TEST_F(IntrusiveForwardListTest, PushPop) {
  PushPop<IFLTestValueList>();
  PushPop<ConstIFLTestValueList>();
  PushPop<IFLTestValue2List>();
}

template <typename ListType>
void IntrusiveForwardListTest::InsertAfter1() {
  using ValueType = typename ListType::value_type;
  ValueType value4(4);
  ValueType value8(8);
  ValueType value5(5);
  ValueType value3(3);
  std::forward_list<int> ref;
  ListType ifl;

  auto ref_it = ref.insert_after(ref.before_begin(), 4);
  auto ifl_it = ifl.insert_after(ifl.before_begin(), value4);
  ASSERT_LISTS_EQUAL(ref, ifl);
  ASSERT_EQ(*ref_it, *ifl_it);
  CHECK(ref_it == ref.begin());
  ASSERT_TRUE(ifl_it == ifl.begin());

  ref_it = ref.insert_after(ref.begin(), 8);
  ifl_it = ifl.insert_after(ifl.begin(), value8);
  ASSERT_LISTS_EQUAL(ref, ifl);
  ASSERT_EQ(*ref_it, *ifl_it);
  CHECK(ref_it != ref.end());
  ASSERT_TRUE(ifl_it != ifl.end());
  CHECK(++ref_it == ref.end());
  ASSERT_TRUE(++ifl_it == ifl.end());

  ref_it = ref.insert_after(ref.begin(), 5);
  ifl_it = ifl.insert_after(ifl.begin(), value5);
  ASSERT_LISTS_EQUAL(ref, ifl);
  ASSERT_EQ(*ref_it, *ifl_it);

  ref_it = ref.insert_after(ref_it, 3);
  ifl_it = ifl.insert_after(ifl_it, value3);
  ASSERT_LISTS_EQUAL(ref, ifl);
  ASSERT_EQ(*ref_it, *ifl_it);
}

TEST_F(IntrusiveForwardListTest, InsertAfter1) {
  InsertAfter1<IFLTestValueList>();
  InsertAfter1<ConstIFLTestValueList>();
  InsertAfter1<IFLTestValue2List>();
}

template <typename ListType>
void IntrusiveForwardListTest::InsertAfter2() {
  using ValueType = typename ListType::value_type;
  std::forward_list<int> ref;
  ListType ifl;

  auto ref_it = ref.insert_after(ref.before_begin(), { 2, 8, 5 });
  std::vector<ValueType> storage1({ { 2 }, { 8 }, { 5 } });
  auto ifl_it = ifl.insert_after(ifl.before_begin(), storage1.begin(), storage1.end());
  ASSERT_LISTS_EQUAL(ref, ifl);
  ASSERT_EQ(*ref_it, *ifl_it);

  std::vector<ValueType> storage2({ { 7 }, { 2 } });
  ref_it = ref.insert_after(ref.begin(), { 7, 2 });
  ifl_it = ifl.insert_after(ifl.begin(), storage2.begin(), storage2.end());
  ASSERT_LISTS_EQUAL(ref, ifl);
  ASSERT_EQ(*ref_it, *ifl_it);

  std::vector<ValueType> storage3({ { 1 }, { 3 }, { 4 }, { 9 } });
  ref_it = ref.begin();
  ifl_it = ifl.begin();
  std::advance(ref_it, std::distance(ref.begin(), ref.end()) - 1);
  std::advance(ifl_it, std::distance(ifl.begin(), ifl.end()) - 1);
  ref_it = ref.insert_after(ref_it, { 1, 3, 4, 9 });
  ifl_it = ifl.insert_after(ifl_it, storage3.begin(), storage3.end());
  ASSERT_LISTS_EQUAL(ref, ifl);
}

TEST_F(IntrusiveForwardListTest, InsertAfter2) {
  InsertAfter2<IFLTestValueList>();
  InsertAfter2<ConstIFLTestValueList>();
  InsertAfter2<IFLTestValue2List>();
}

template <typename ListType>
void IntrusiveForwardListTest::EraseAfter1() {
  using ValueType = typename ListType::value_type;
  std::forward_list<int> ref({ 1, 2, 7, 4, 5 });
  std::vector<ValueType> storage(ref.begin(), ref.end());
  ListType ifl(storage.begin(), storage.end());
  ASSERT_LISTS_EQUAL(ref, ifl);
  CHECK_EQ(std::distance(ref.begin(), ref.end()), 5);

  auto ref_it = ref.begin();
  auto ifl_it = ifl.begin();
  std::advance(ref_it, 2);
  std::advance(ifl_it, 2);
  ref_it = ref.erase_after(ref_it);
  ifl_it = ifl.erase_after(ifl_it);
  ASSERT_LISTS_EQUAL(ref, ifl);
  CHECK_EQ(std::distance(ref.begin(), ref.end()), 4);
  CHECK(ref_it != ref.end());
  ASSERT_TRUE(ifl_it != ifl.end());
  CHECK(++ref_it == ref.end());
  ASSERT_TRUE(++ifl_it == ifl.end());

  ref_it = ref.begin();
  ifl_it = ifl.begin();
  std::advance(ref_it, 2);
  std::advance(ifl_it, 2);
  ref_it = ref.erase_after(ref_it);
  ifl_it = ifl.erase_after(ifl_it);
  ASSERT_LISTS_EQUAL(ref, ifl);
  CHECK_EQ(std::distance(ref.begin(), ref.end()), 3);
  CHECK(ref_it == ref.end());
  ASSERT_TRUE(ifl_it == ifl.end());

  ref_it = ref.erase_after(ref.begin());
  ifl_it = ifl.erase_after(ifl.begin());
  ASSERT_LISTS_EQUAL(ref, ifl);
  CHECK_EQ(std::distance(ref.begin(), ref.end()), 2);
  CHECK(ref_it != ref.end());
  ASSERT_TRUE(ifl_it != ifl.end());
  CHECK(++ref_it == ref.end());
  ASSERT_TRUE(++ifl_it == ifl.end());

  ref_it = ref.erase_after(ref.before_begin());
  ifl_it = ifl.erase_after(ifl.before_begin());
  ASSERT_LISTS_EQUAL(ref, ifl);
  CHECK_EQ(std::distance(ref.begin(), ref.end()), 1);
  CHECK(ref_it == ref.begin());
  ASSERT_TRUE(ifl_it == ifl.begin());

  ref_it = ref.erase_after(ref.before_begin());
  ifl_it = ifl.erase_after(ifl.before_begin());
  ASSERT_LISTS_EQUAL(ref, ifl);
  CHECK_EQ(std::distance(ref.begin(), ref.end()), 0);
  CHECK(ref_it == ref.begin());
  ASSERT_TRUE(ifl_it == ifl.begin());
}

TEST_F(IntrusiveForwardListTest, EraseAfter1) {
  EraseAfter1<IFLTestValueList>();
  EraseAfter1<ConstIFLTestValueList>();
  EraseAfter1<IFLTestValue2List>();
}

template <typename ListType>
void IntrusiveForwardListTest::EraseAfter2() {
  using ValueType = typename ListType::value_type;
  std::forward_list<int> ref({ 1, 2, 7, 4, 5, 3, 2, 8, 9 });
  std::vector<ValueType> storage(ref.begin(), ref.end());
  ListType ifl(storage.begin(), storage.end());
  ASSERT_LISTS_EQUAL(ref, ifl);
  CHECK_EQ(std::distance(ref.begin(), ref.end()), 9);

  auto ref_it = ref.begin();
  auto ifl_it = ifl.begin();
  std::advance(ref_it, 3);
  std::advance(ifl_it, 3);
  ref_it = ref.erase_after(ref.begin(), ref_it);
  ifl_it = ifl.erase_after(ifl.begin(), ifl_it);
  ASSERT_LISTS_EQUAL(ref, ifl);
  ASSERT_EQ(std::distance(ref.begin(), ref_it), std::distance(ifl.begin(), ifl_it));
  CHECK_EQ(std::distance(ref.begin(), ref.end()), 7);

  ref_it = ref.erase_after(ref_it, ref.end());
  ifl_it = ifl.erase_after(ifl_it, ifl.end());
  ASSERT_LISTS_EQUAL(ref, ifl);
  CHECK(ref_it == ref.end());
  ASSERT_TRUE(ifl_it == ifl.end());
  CHECK_EQ(std::distance(ref.begin(), ref.end()), 2);

  ref_it = ref.erase_after(ref.before_begin(), ref.end());
  ifl_it = ifl.erase_after(ifl.before_begin(), ifl.end());
  ASSERT_LISTS_EQUAL(ref, ifl);
  CHECK(ref_it == ref.end());
  ASSERT_TRUE(ifl_it == ifl.end());
  CHECK_EQ(std::distance(ref.begin(), ref.end()), 0);
}

TEST_F(IntrusiveForwardListTest, EraseAfter2) {
  EraseAfter2<IFLTestValueList>();
  EraseAfter2<ConstIFLTestValueList>();
  EraseAfter2<IFLTestValue2List>();
}

template <typename ListType>
void IntrusiveForwardListTest::SwapClear() {
  using ValueType = typename ListType::value_type;
  std::forward_list<int> ref1({ 1, 2, 7 });
  std::vector<ValueType> storage1(ref1.begin(), ref1.end());
  ListType ifl1(storage1.begin(), storage1.end());
  std::forward_list<int> ref2({ 3, 8, 6 });
  std::vector<ValueType> storage2(ref2.begin(), ref2.end());
  ListType ifl2(storage2.begin(), storage2.end());
  ASSERT_LISTS_EQUAL(ref1, ifl1);
  ASSERT_LISTS_EQUAL(ref2, ifl2);
  ref1.swap(ref2);
  ifl1.swap(ifl2);
  ASSERT_LISTS_EQUAL(ref1, ifl1);
  ASSERT_LISTS_EQUAL(ref2, ifl2);
  ref1.clear();
  ifl1.clear();
  ASSERT_LISTS_EQUAL(ref1, ifl1);
  ASSERT_LISTS_EQUAL(ref2, ifl2);
  swap(ref1, ref2);
  swap(ifl1, ifl2);
  ASSERT_LISTS_EQUAL(ref1, ifl1);
  ASSERT_LISTS_EQUAL(ref2, ifl2);
  ref1.clear();
  ifl1.clear();
  ASSERT_LISTS_EQUAL(ref1, ifl1);
  ASSERT_LISTS_EQUAL(ref2, ifl2);
}

TEST_F(IntrusiveForwardListTest, SwapClear) {
  SwapClear<IFLTestValueList>();
  SwapClear<ConstIFLTestValueList>();
  SwapClear<IFLTestValue2List>();
}

template <typename ListType>
void IntrusiveForwardListTest::SpliceAfter() {
  using ValueType = typename ListType::value_type;
  std::forward_list<int> ref1({ 3, 1, 2, 7, 4, 5, 4, 8, 7 });
  std::forward_list<int> ref2;
  std::vector<ValueType> storage(ref1.begin(), ref1.end());
  ListType ifl1(storage.begin(), storage.end());
  ListType ifl2;
  ASSERT_LISTS_EQUAL(ref1, ifl1);
  ASSERT_LISTS_EQUAL(ref2, ifl2);

  // Move everything to ref2/ifl2.
  ref2.splice_after(ref2.before_begin(), ref1);
  ifl2.splice_after(ifl2.before_begin(), ifl1);
  ASSERT_LISTS_EQUAL(ref1, ifl1);
  ASSERT_LISTS_EQUAL(ref2, ifl2);

  // Move first element (3) to ref1/ifl1.
  ref1.splice_after(ref1.before_begin(), ref2, ref2.before_begin());
  ifl1.splice_after(ifl1.before_begin(), ifl2, ifl2.before_begin());
  ASSERT_LISTS_EQUAL(ref1, ifl1);
  ASSERT_LISTS_EQUAL(ref2, ifl2);

  // Move second element (2) to ref1/ifl1 after the first element (3).
  ref1.splice_after(ref1.begin(), ref2, ref2.begin());
  ifl1.splice_after(ifl1.begin(), ifl2, ifl2.begin());
  ASSERT_LISTS_EQUAL(ref1, ifl1);
  ASSERT_LISTS_EQUAL(ref2, ifl2);

  // Move everything from ref2/ifl2 between the 2 elements now in ref1/ifl1.
  ref1.splice_after(ref1.begin(), ref2);
  ifl1.splice_after(ifl1.begin(), ifl2);
  ASSERT_LISTS_EQUAL(ref1, ifl1);
  ASSERT_LISTS_EQUAL(ref2, ifl2);

  std::forward_list<int> check({ 3, 1, 7, 4, 5, 4, 8, 7, 2 });
  ASSERT_LISTS_EQUAL(check, ifl1);
  ASSERT_TRUE(ifl2.empty());

  // Empty splice_after().
  ref2.splice_after(
      ref2.before_begin(), ref1, ref1.before_begin(), ref1.begin());
  ifl2.splice_after(ifl2.before_begin(), ifl1, ifl1.before_begin(), ifl1.begin());
  ASSERT_LISTS_EQUAL(ref1, ifl1);
  ASSERT_LISTS_EQUAL(ref2, ifl2);

  // Move { 1, 7 } to ref2/ifl2.
  auto ref_it = ref1.begin();
  auto ifl_it = ifl1.begin();
  std::advance(ref_it, 3);
  std::advance(ifl_it, 3);
  ref2.splice_after(ref2.before_begin(), ref1, ref1.begin(), ref_it);
  ifl2.splice_after(ifl2.before_begin(), ifl1, ifl1.begin(), ifl_it);
  ASSERT_LISTS_EQUAL(ref1, ifl1);
  ASSERT_LISTS_EQUAL(ref2, ifl2);

  // Move { 8, 7, 2 } to the beginning of ref1/ifl1.
  ref_it = ref1.begin();
  ifl_it = ifl1.begin();
  std::advance(ref_it, 3);
  std::advance(ifl_it, 3);
  ref1.splice_after(ref1.before_begin(), ref1, ref_it, ref1.end());
  ifl1.splice_after(ifl1.before_begin(), ifl1, ifl_it, ifl1.end());
  ASSERT_LISTS_EQUAL(ref1, ifl1);

  check.assign({ 8, 7, 2, 3, 4, 5, 4 });
  ASSERT_LISTS_EQUAL(check, ifl1);
  check.assign({ 1, 7 });
  ASSERT_LISTS_EQUAL(check, ifl2);

  // Move all but the first element to ref2/ifl2.
  ref_it = ref2.begin();
  ifl_it = ifl2.begin();
  std::advance(ref_it, 1);
  std::advance(ifl_it, 1);
  ref2.splice_after(ref_it, ref1, ref1.begin(), ref1.end());
  ifl2.splice_after(ifl_it, ifl1, ifl1.begin(), ifl1.end());
  ASSERT_LISTS_EQUAL(ref1, ifl1);
  ASSERT_LISTS_EQUAL(ref2, ifl2);

  check.assign({8});
  ASSERT_LISTS_EQUAL(check, ifl1);

  // Move the first element of ref1/ifl1 to the beginning of ref1/ifl1 (do nothing).
  ref1.splice_after(ref1.before_begin(), ref1, ref1.before_begin());
  ifl1.splice_after(ifl1.before_begin(), ifl1, ifl1.before_begin());
  ASSERT_LISTS_EQUAL(ref1, ifl1);
  ASSERT_LISTS_EQUAL(check, ifl1);

  // Move the first element of ref2/ifl2 after itself (do nothing).
  ref1.splice_after(ref1.begin(), ref1, ref1.before_begin());
  ifl1.splice_after(ifl1.begin(), ifl1, ifl1.before_begin());
  ASSERT_LISTS_EQUAL(ref1, ifl1);
  ASSERT_LISTS_EQUAL(check, ifl1);

  check.assign({ 1, 7, 7, 2, 3, 4, 5, 4 });
  ASSERT_LISTS_EQUAL(check, ifl2);

  // Move the first element of ref2/ifl2 to the beginning of ref2/ifl2 (do nothing).
  ref2.splice_after(ref2.before_begin(), ref2, ref2.before_begin());
  ifl2.splice_after(ifl2.before_begin(), ifl2, ifl2.before_begin());
  ASSERT_LISTS_EQUAL(ref2, ifl2);
  ASSERT_LISTS_EQUAL(check, ifl2);

  // Move the first element of ref2/ifl2 after itself (do nothing).
  ref2.splice_after(ref2.begin(), ref2, ref2.before_begin());
  ifl2.splice_after(ifl2.begin(), ifl2, ifl2.before_begin());
  ASSERT_LISTS_EQUAL(ref2, ifl2);
  ASSERT_LISTS_EQUAL(check, ifl2);
}

TEST_F(IntrusiveForwardListTest, SpliceAfter) {
  SpliceAfter<IFLTestValueList>();
  SpliceAfter<ConstIFLTestValueList>();
  SpliceAfter<IFLTestValue2List>();
}

template <typename ListType>
void IntrusiveForwardListTest::Remove() {
  using ValueType = typename ListType::value_type;
  std::forward_list<int> ref({ 3, 1, 2, 7, 4, 5, 4, 8, 7 });
  std::vector<ValueType> storage(ref.begin(), ref.end());
  ListType ifl(storage.begin(), storage.end());
  ASSERT_LISTS_EQUAL(ref, ifl);
  ref.remove(1);
  ifl.remove(1);
  ASSERT_LISTS_EQUAL(ref, ifl);
  ref.remove(4);
  ifl.remove(4);
  ASSERT_LISTS_EQUAL(ref, ifl);
  auto odd = [](ValueType value) { return (value.value & 1) != 0; };
  ref.remove_if(odd);
  ifl.remove_if(odd);
  ASSERT_LISTS_EQUAL(ref, ifl);
  auto all = [](ValueType value ATTRIBUTE_UNUSED) { return true; };
  ref.remove_if(all);
  ifl.remove_if(all);
  ASSERT_LISTS_EQUAL(ref, ifl);
}

TEST_F(IntrusiveForwardListTest, Remove) {
  Remove<IFLTestValueList>();
  Remove<ConstIFLTestValueList>();
  Remove<IFLTestValue2List>();
}

template <typename ListType>
void IntrusiveForwardListTest::Unique() {
  using ValueType = typename ListType::value_type;
  std::forward_list<int> ref({ 3, 1, 1, 2, 3, 3, 7, 7, 4, 4, 5, 7 });
  std::vector<ValueType> storage(ref.begin(), ref.end());
  ListType ifl(storage.begin(), storage.end());
  ASSERT_LISTS_EQUAL(ref, ifl);
  ref.unique();
  ifl.unique();
  ASSERT_LISTS_EQUAL(ref, ifl);
  std::forward_list<int> check({ 3, 1, 2, 3, 7, 4, 5, 7 });
  ASSERT_LISTS_EQUAL(check, ifl);

  auto bin_pred = [](const ValueType& lhs, const ValueType& rhs) {
    return (lhs.value & ~1) == (rhs.value & ~1);
  };
  ref.unique(bin_pred);
  ifl.unique(bin_pred);
  ASSERT_LISTS_EQUAL(ref, ifl);
  check.assign({ 3, 1, 2, 7, 4, 7 });
  ASSERT_LISTS_EQUAL(check, ifl);
}

TEST_F(IntrusiveForwardListTest, Unique) {
  Unique<IFLTestValueList>();
  Unique<ConstIFLTestValueList>();
  Unique<IFLTestValue2List>();
}

template <typename ListType>
void IntrusiveForwardListTest::Merge() {
  using ValueType = typename ListType::value_type;
  std::forward_list<int> ref1({ 1, 4, 8, 8, 12 });
  std::vector<ValueType> storage1(ref1.begin(), ref1.end());
  ListType ifl1(storage1.begin(), storage1.end());
  std::forward_list<int> ref2({ 3, 5, 6, 7, 9 });
  std::vector<ValueType> storage2(ref2.begin(), ref2.end());
  ListType ifl2(storage2.begin(), storage2.end());
  ASSERT_LISTS_EQUAL(ref1, ifl1);
  ASSERT_LISTS_EQUAL(ref2, ifl2);
  CHECK(std::is_sorted(ref1.begin(), ref1.end()));
  CHECK(std::is_sorted(ref2.begin(), ref2.end()));
  ref1.merge(ref2);
  ifl1.merge(ifl2);
  ASSERT_LISTS_EQUAL(ref1, ifl1);
  ASSERT_LISTS_EQUAL(ref2, ifl2);
  CHECK(ref2.empty());
  std::forward_list<int> check({ 1, 3, 4, 5, 6, 7, 8, 8, 9, 12 });
  ASSERT_LISTS_EQUAL(check, ifl1);
}

TEST_F(IntrusiveForwardListTest, Merge) {
  Merge<IFLTestValueList>();
  Merge<ConstIFLTestValueList>();
  Merge<IFLTestValue2List>();
}

template <typename ListType>
void IntrusiveForwardListTest::Sort1() {
  using ValueType = typename ListType::value_type;
  std::forward_list<int> ref({ 2, 9, 8, 3, 7, 4, 1, 5, 3, 0 });
  std::vector<ValueType> storage(ref.begin(), ref.end());
  ListType ifl(storage.begin(), storage.end());
  ASSERT_LISTS_EQUAL(ref, ifl);
  CHECK(!std::is_sorted(ref.begin(), ref.end()));
  ref.sort();
  ifl.sort();
  ASSERT_LISTS_EQUAL(ref, ifl);
  std::forward_list<int> check({ 0, 1, 2, 3, 3, 4, 5, 7, 8, 9 });
  ASSERT_LISTS_EQUAL(check, ifl);
}

TEST_F(IntrusiveForwardListTest, Sort1) {
  Sort1<IFLTestValueList>();
  Sort1<ConstIFLTestValueList>();
  Sort1<IFLTestValue2List>();
}

template <typename ListType>
void IntrusiveForwardListTest::Sort2() {
  using ValueType = typename ListType::value_type;
  std::forward_list<int> ref({ 2, 9, 8, 3, 7, 4, 1, 5, 3, 0 });
  std::vector<ValueType> storage(ref.begin(), ref.end());
  ListType ifl(storage.begin(), storage.end());
  ASSERT_LISTS_EQUAL(ref, ifl);
  auto cmp = [](const ValueType& lhs, const ValueType& rhs) {
    return (lhs.value & ~1) < (rhs.value & ~1);
  };
  CHECK(!std::is_sorted(ref.begin(), ref.end(), cmp));
  ref.sort(cmp);
  ifl.sort(cmp);
  ASSERT_LISTS_EQUAL(ref, ifl);
  std::forward_list<int> check({ 1, 0, 2, 3, 3, 4, 5, 7, 9, 8 });
  ASSERT_LISTS_EQUAL(check, ifl);
}

TEST_F(IntrusiveForwardListTest, Sort2) {
  Sort2<IFLTestValueList>();
  Sort2<ConstIFLTestValueList>();
  Sort2<IFLTestValue2List>();
}

template <typename ListType>
void IntrusiveForwardListTest::Reverse() {
  using ValueType = typename ListType::value_type;
  std::forward_list<int> ref({ 8, 3, 5, 4, 1, 3 });
  std::vector<ValueType> storage(ref.begin(), ref.end());
  ListType ifl(storage.begin(), storage.end());
  ASSERT_LISTS_EQUAL(ref, ifl);
  CHECK(!std::is_sorted(ref.begin(), ref.end()));
  ref.reverse();
  ifl.reverse();
  ASSERT_LISTS_EQUAL(ref, ifl);
  std::forward_list<int> check({ 3, 1, 4, 5, 3, 8 });
  ASSERT_LISTS_EQUAL(check, ifl);
}

TEST_F(IntrusiveForwardListTest, Reverse) {
  Reverse<IFLTestValueList>();
  Reverse<ConstIFLTestValueList>();
  Reverse<IFLTestValue2List>();
}

template <typename ListType>
void IntrusiveForwardListTest::ModifyValue() {
  using ValueType = typename ListType::value_type;
  std::forward_list<int> ref({ 3, 7, 42 });
  std::vector<ValueType> storage(ref.begin(), ref.end());
  ListType ifl(storage.begin(), storage.end());
  ASSERT_LISTS_EQUAL(ref, ifl);

  auto add1 = [](const ValueType& value) { return value.value + 1; };
  std::transform(ref.begin(), ref.end(), ref.begin(), add1);
  std::transform(ifl.begin(), ifl.end(), ifl.begin(), add1);
  ASSERT_LISTS_EQUAL(ref, ifl);
}

TEST_F(IntrusiveForwardListTest, ModifyValue) {
  ModifyValue<IFLTestValueList>();
  // Does not compile with ConstIFLTestValueList because LHS of the assignment is const.
  // ModifyValue<ConstIFLTestValueList>();
  static_assert(std::is_const<ConstIFLTestValueList::iterator::value_type>::value, "Const check.");
  ModifyValue<IFLTestValue2List>();
}

struct Tag1;
struct Tag2;
struct TwoListsValue : public IntrusiveForwardListNode<TwoListsValue, Tag1>,
                       public IntrusiveForwardListNode<TwoListsValue, Tag2> {
  // Deliberately not explicit.
  TwoListsValue(int v) : value(v) { }  // NOLINT(runtime/explicit)

  int value;
};
using FirstList =
    IntrusiveForwardList<TwoListsValue, IntrusiveForwardListBaseHookTraits<TwoListsValue, Tag1>>;
using SecondList =
    IntrusiveForwardList<TwoListsValue, IntrusiveForwardListBaseHookTraits<TwoListsValue, Tag2>>;

bool operator==(const TwoListsValue& lhs, const TwoListsValue& rhs) {
  return lhs.value == rhs.value;
}

TEST_F(IntrusiveForwardListTest, TwoLists) {
  // Test that a value can be in two lists at the same time and the hooks do not interfere.
  std::vector<TwoListsValue> storage({ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 });  // storage[i] = i

  std::vector<int> order1({ 3, 1, 7, 2, 8, 9, 4, 0, 6, 5 });
  FirstList list1;
  auto pos1 = list1.before_begin();
  for (size_t idx : order1) {
    pos1 = list1.insert_after(pos1, storage[idx]);
  }

  std::vector<int> order2({ 8, 5, 1, 6, 7, 2, 9, 3, 0, 4 });
  SecondList list2;
  auto pos2 = list2.before_begin();
  for (size_t idx : order2) {
    pos2 = list2.insert_after(pos2, storage[idx]);
  }

  // Using `storage[i] = i`, we can easily compare that nodes of each list are in the right order.
  ASSERT_LISTS_EQUAL(order1, list1);
  ASSERT_LISTS_EQUAL(order2, list2);
}

}  // namespace art