1//===----------------------------------------------------------------------===//
  2//
  3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
  4// See https://llvm.org/LICENSE.txt for license information.
  5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
  6//
  7//===----------------------------------------------------------------------===//
  8
  9#ifndef _LIBCPP___ALGORITHM_SET_UNION_H
 10#define _LIBCPP___ALGORITHM_SET_UNION_H
 11
 12#include <__algorithm/comp.h>
 13#include <__algorithm/comp_ref_type.h>
 14#include <__algorithm/copy.h>
 15#include <__config>
 16#include <__iterator/iterator_traits.h>
 17#include <__utility/move.h>
 18#include <__utility/pair.h>
 19
 20#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 21#  pragma GCC system_header
 22#endif
 23
 24_LIBCPP_PUSH_MACROS
 25#include <__undef_macros>
 26
 27_LIBCPP_BEGIN_NAMESPACE_STD
 28
 29template <class _InIter1, class _InIter2, class _OutIter>
 30struct __set_union_result {
 31  _InIter1 __in1_;
 32  _InIter2 __in2_;
 33  _OutIter __out_;
 34
 35  // need a constructor as C++03 aggregate init is hard
 36  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
 37  __set_union_result(_InIter1&& __in_iter1, _InIter2&& __in_iter2, _OutIter&& __out_iter)
 38      : __in1_(std::move(__in_iter1)), __in2_(std::move(__in_iter2)), __out_(std::move(__out_iter)) {}
 39};
 40
 41template <class _Compare, class _InIter1, class _Sent1, class _InIter2, class _Sent2, class _OutIter>
 42_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 __set_union_result<_InIter1, _InIter2, _OutIter> __set_union(
 43    _InIter1 __first1, _Sent1 __last1, _InIter2 __first2, _Sent2 __last2, _OutIter __result, _Compare&& __comp) {
 44  for (; __first1 != __last1; ++__result) {
 45    if (__first2 == __last2) {
 46      auto __ret1 = std::__copy(std::move(__first1), std::move(__last1), std::move(__result));
 47      return __set_union_result<_InIter1, _InIter2, _OutIter>(
 48          std::move(__ret1.first), std::move(__first2), std::move((__ret1.second)));
 49    }
 50    if (__comp(*__first2, *__first1)) {
 51      *__result = *__first2;
 52      ++__first2;
 53    } else {
 54      if (!__comp(*__first1, *__first2)) {
 55        ++__first2;
 56      }
 57      *__result = *__first1;
 58      ++__first1;
 59    }
 60  }
 61  auto __ret2 = std::__copy(std::move(__first2), std::move(__last2), std::move(__result));
 62  return __set_union_result<_InIter1, _InIter2, _OutIter>(
 63      std::move(__first1), std::move(__ret2.first), std::move((__ret2.second)));
 64}
 65
 66template <class _InputIterator1, class _InputIterator2, class _OutputIterator, class _Compare>
 67_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 _OutputIterator set_union(
 68    _InputIterator1 __first1,
 69    _InputIterator1 __last1,
 70    _InputIterator2 __first2,
 71    _InputIterator2 __last2,
 72    _OutputIterator __result,
 73    _Compare __comp) {
 74  return std::__set_union<__comp_ref_type<_Compare> >(
 75             std::move(__first1),
 76             std::move(__last1),
 77             std::move(__first2),
 78             std::move(__last2),
 79             std::move(__result),
 80             __comp)
 81      .__out_;
 82}
 83
 84template <class _InputIterator1, class _InputIterator2, class _OutputIterator>
 85_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 _OutputIterator set_union(
 86    _InputIterator1 __first1,
 87    _InputIterator1 __last1,
 88    _InputIterator2 __first2,
 89    _InputIterator2 __last2,
 90    _OutputIterator __result) {
 91  return std::set_union(
 92      std::move(__first1),
 93      std::move(__last1),
 94      std::move(__first2),
 95      std::move(__last2),
 96      std::move(__result),
 97      __less<>());
 98}
 99
100_LIBCPP_END_NAMESPACE_STD
101
102_LIBCPP_POP_MACROS
103
104#endif // _LIBCPP___ALGORITHM_SET_UNION_H