util.hpp

#ifndef UTIL_H_
#define UTIL_H_

#include <cstddef>
#include "type_traits.hpp"

// 这个文件包含一些通用工具，包括 move, forward, swap 等函数，以及 pair 等

namespace tstl
{

  // move
  template <class T>
  typename tstl::remove_reference<T>::type &&move(T &&arg) noexcept
  {
    return static_cast<typename tstl::remove_reference<T>::type &&>(arg);
  }

  // forward
  template <class T>
  T &&forward(typename tstl::remove_reference<T>::type &arg) noexcept
  {
    return static_cast<T &&>(arg);
  }

  template <class T>
  T &&forward(typename tstl::remove_reference<T>::type &&arg) noexcept
  {
    static_assert(!std::is_lvalue_reference<T>::value, "bad forward");
    return static_cast<T &&>(arg);
  }

  // swap

  template <class Tp>
  void swap(Tp &lhs, Tp &rhs)
  {
    auto tmp(tstl::move(lhs));
    lhs = tstl::move(rhs);
    rhs = tstl::move(tmp);
  }

  template <class ForwardIter1, class ForwardIter2>
  ForwardIter2 swap_range(ForwardIter1 first1, ForwardIter1 last1, ForwardIter2 first2)
  {
    for (; first1 != last1; ++first1, (void)++first2)
      tstl::swap(*first1, *first2);
    return first2;
  }

  template <class Tp, size_t N>
  void swap(Tp (&a)[N], Tp (&b)[N])
  {
    tstl::swap_range(a, a + N, b);
  }

  // 太多了直接抄
  // GCC标准库中将的pair分成了另一个文件<bits/stl_pair.h>
  // pair总体实现思想并不复杂，但是构造函数用了一大波判断各种
  // 情况的模板参数，然后是三五法则连击！对不熟悉的人简直劝退
  // 度百分之两百......头痛，什么鬼畜语法

  // pair

  // 结构体模板 : pair
  // 两个模板参数分别表示两个数据的类型
  // 用 first 和 second 来分别取出第一个数据和第二个数据
  template <class Ty1, class Ty2>
  struct pair
  {
    typedef Ty1 first_type;
    typedef Ty2 second_type;

    first_type first;   // 保存第一个数据
    second_type second; // 保存第二个数据

    // explicit关键字的作用是防止类构造函数的隐式自动转换.
    // 标准库在下面的构造函数提供了两个版本
    // 不都是 default_construct 加上了 explicit ???
    
    // default constructiable
    template <class Other1 = Ty1, class Other2 = Ty2,
              typename = typename std::enable_if<
                  std::is_default_constructible<Other1>::value &&
                      std::is_default_constructible<Other2>::value,
                  void>::type>
    constexpr pair()
        : first(), second() {}

    // implicit constructiable for this type
    template <class U1 = Ty1, class U2 = Ty2,
              typename std::enable_if<
                  std::is_copy_constructible<U1>::value &&
                      std::is_copy_constructible<U2>::value &&
                      std::is_convertible<const U1 &, Ty1>::value &&
                      std::is_convertible<const U2 &, Ty2>::value,
                  int>::type = 0>
    constexpr pair(const Ty1 &a, const Ty2 &b)
        : first(a), second(b)
    {
    }

    // explicit constructible for this type
    template <class U1 = Ty1, class U2 = Ty2,
              typename std::enable_if<
                  std::is_copy_constructible<U1>::value &&
                      std::is_copy_constructible<U2>::value &&
                      (!std::is_convertible<const U1 &, Ty1>::value ||
                       !std::is_convertible<const U2 &, Ty2>::value),
                  int>::type = 0>
    explicit constexpr pair(const Ty1 &a, const Ty2 &b)
        : first(a), second(b) {}

    pair(const pair &rhs) = default;
    pair(pair &&rhs) = default;

    // implicit constructiable for other type
    template <class Other1, class Other2,
              typename std::enable_if<
                  std::is_constructible<Ty1, Other1>::value &&
                      std::is_constructible<Ty2, Other2>::value &&
                      std::is_convertible<Other1 &&, Ty1>::value &&
                      std::is_convertible<Other2 &&, Ty2>::value,
                  int>::type = 0>
    constexpr pair(Other1 &&a, Other2 &&b)
        : first(tstl::forward<Other1>(a)),
          second(tstl::forward<Other2>(b)) {}

    // explicit constructiable for other type
    template <class Other1, class Other2,
              typename std::enable_if<
                  std::is_constructible<Ty1, Other1>::value &&
                      std::is_constructible<Ty2, Other2>::value &&
                      (!std::is_convertible<Other1, Ty1>::value ||
                       !std::is_convertible<Other2, Ty2>::value),
                  int>::type = 0>
    explicit constexpr pair(Other1 &&a, Other2 &&b)
        : first(tstl::forward<Other1>(a)),
          second(tstl::forward<Other2>(b)) {}

    // implicit constructiable for other pair
    template <class Other1, class Other2,
              typename std::enable_if<
                  std::is_constructible<Ty1, const Other1 &>::value &&
                      std::is_constructible<Ty2, const Other2 &>::value &&
                      std::is_convertible<const Other1 &, Ty1>::value &&
                      std::is_convertible<const Other2 &, Ty2>::value,
                  int>::type = 0>
    constexpr pair(const pair<Other1, Other2> &other)
        : first(other.first),
          second(other.second) {}

    // explicit constructiable for other pair
    template <class Other1, class Other2,
              typename std::enable_if<
                  std::is_constructible<Ty1, const Other1 &>::value &&
                      std::is_constructible<Ty2, const Other2 &>::value &&
                      (!std::is_convertible<const Other1 &, Ty1>::value ||
                       !std::is_convertible<const Other2 &, Ty2>::value),
                  int>::type = 0>
    explicit constexpr pair(const pair<Other1, Other2> &other)
        : first(other.first),
          second(other.second)
    {
    }

    // implicit constructiable for other pair
    template <class Other1, class Other2,
              typename std::enable_if<
                  std::is_constructible<Ty1, Other1>::value &&
                      std::is_constructible<Ty2, Other2>::value &&
                      std::is_convertible<Other1, Ty1>::value &&
                      std::is_convertible<Other2, Ty2>::value,
                  int>::type = 0>
    constexpr pair(pair<Other1, Other2> &&other)
        : first(tstl::forward<Other1>(other.first)),
          second(tstl::forward<Other2>(other.second)) {}

    // explicit constructiable for other pair
    template <class Other1, class Other2,
              typename std::enable_if<
                  std::is_constructible<Ty1, Other1>::value &&
                      std::is_constructible<Ty2, Other2>::value &&
                      (!std::is_convertible<Other1, Ty1>::value ||
                       !std::is_convertible<Other2, Ty2>::value),
                  int>::type = 0>
    explicit constexpr pair(pair<Other1, Other2> &&other)
        : first(tstl::forward<Other1>(other.first)),
          second(tstl::forward<Other2>(other.second)) {}

    // copy assign for this pair
    pair &operator=(const pair &rhs)
    {
      if (this != &rhs)
      {
        first = rhs.first;
        second = rhs.second;
      }
      return *this;
    }

    // move assign for this pair
    pair &operator=(pair &&rhs)
    {
      if (this != &rhs)
      {
        first = tstl::move(rhs.first);
        second = tstl::move(rhs.second);
      }
      return *this;
    }

    // copy assign for other pair
    template <class Other1, class Other2>
    pair &operator=(const pair<Other1, Other2> &other)
    {
      first = other.first;
      second = other.second;
      return *this;
    }

    // move assign for other pair
    template <class Other1, class Other2>
    pair &operator=(pair<Other1, Other2> &&other)
    {
      first = tstl::forward<Other1>(other.first);
      second = tstl::forward<Other2>(other.second);
      return *this;
    }

    // ??? 普通类型会自动回收，复杂类型在结束时会调用自己的析构 ???
    ~pair() = default;

    void swap(pair &other)
    {
      if (this != &other)
      {
        tstl::swap(first, other.first);
        tstl::swap(second, other.second);
      }
    }
  };

  // 重载比较操作符
  template <class Ty1, class Ty2>
  bool operator==(const pair<Ty1, Ty2> &lhs, const pair<Ty1, Ty2> &rhs)
  {
    return lhs.first == rhs.first && lhs.second == rhs.second;
  }

  template <class Ty1, class Ty2>
  bool operator<(const pair<Ty1, Ty2> &lhs, const pair<Ty1, Ty2> &rhs)
  {
    return lhs.first < rhs.first || (lhs.first == rhs.first && lhs.second < rhs.second);
  }

  template <class Ty1, class Ty2>
  bool operator!=(const pair<Ty1, Ty2> &lhs, const pair<Ty1, Ty2> &rhs)
  {
    return !(lhs == rhs);
  }

  template <class Ty1, class Ty2>
  bool operator>(const pair<Ty1, Ty2> &lhs, const pair<Ty1, Ty2> &rhs)
  {
    return rhs < lhs;
  }

  template <class Ty1, class Ty2>
  bool operator<=(const pair<Ty1, Ty2> &lhs, const pair<Ty1, Ty2> &rhs)
  {
    return !(rhs < lhs);
  }

  template <class Ty1, class Ty2>
  bool operator>=(const pair<Ty1, Ty2> &lhs, const pair<Ty1, Ty2> &rhs)
  {
    return !(lhs < rhs);
  }

  // 重载 mystl 的 swap
  template <class Ty1, class Ty2>
  void swap(pair<Ty1, Ty2> &lhs, pair<Ty1, Ty2> &rhs)
  {
    lhs.swap(rhs);
  }

  // 全局函数，让两个数据成为一个 pair
  template <class Ty1, class Ty2>
  pair<Ty1, Ty2> make_pair(Ty1 &&first, Ty2 &&second)
  {
    return pair<Ty1, Ty2>(tstl::forward<Ty1>(first), tstl::forward<Ty2>(second));
  }

}

#endif // UTIL_H