text:
/****************************************************************************
 * Copyright (c) 2017-2021 by the ArborX authors                            *
 * All rights reserved.                                                     *
 *                                                                          *
 * This file is part of the ArborX library. ArborX is                       *
 * distributed under a BSD 3-clause license. For the licensing terms see    *
 * the LICENSE file in the top-level directory.                             *
 *                                                                          *
 * SPDX-License-Identifier: BSD-3-Clause                                    *
 ****************************************************************************/

#include "ArborXTest_StdVectorToKokkosView.hpp"
#include "ArborX_EnableDeviceTypes.hpp" // ARBORX_DEVICE_TYPES
#include "ArborX_EnableViewComparison.hpp"
#include <ArborX_DetailsTreeNodeLabeling.hpp>

#include "BoostTest_CUDA_clang_workarounds.hpp"
#include <boost/test/unit_test.hpp>

template <class MemorySpace>
struct MockBVH
{
  Kokkos::View<Kokkos::pair<int, int> *, MemorySpace> children_;
  KOKKOS_FUNCTION auto size() const { return children_.extent(0) + 1; }
};

#define HAPPY_TREE_FRIENDS_GET_CHILDREN_SPECIALIZATION(MEMORY_SPACE)           \
  template <>                                                                  \
  KOKKOS_FUNCTION auto                                                         \
  ArborX::Details::HappyTreeFriends::getLeftChild<MockBVH<MEMORY_SPACE>>(      \
      MockBVH<MEMORY_SPACE> const &x, int i)                                   \
  {                                                                            \
    return x.children_(i).first;                                               \
  }                                                                            \
  template <>                                                                  \
  KOKKOS_FUNCTION auto                                                         \
  ArborX::Details::HappyTreeFriends::getRightChild<MockBVH<MEMORY_SPACE>>(     \
      MockBVH<MEMORY_SPACE> const &x, int i)                                   \
  {                                                                            \
    return x.children_(i).second;                                              \
  }

HAPPY_TREE_FRIENDS_GET_CHILDREN_SPECIALIZATION(
    Kokkos::DefaultExecutionSpace::memory_space)
#if defined(KOKKOS_ENABLE_CUDA) || defined(KOKKOS_ENABLE_HIP) ||               \
    defined(KOKKOS_ENABLE_SYCL) || defined(KOKKOS_ENABLE_OPENMPTARGET)
static_assert(!std::is_same<Kokkos::DefaultExecutionSpace::memory_space,
                            Kokkos::HostSpace>::value,
              "");
HAPPY_TREE_FRIENDS_GET_CHILDREN_SPECIALIZATION(Kokkos::HostSpace)
#endif

namespace Test
{
using ArborXTest::toView;

template <class ExecutionSpace>
auto findParents(ExecutionSpace const &exec_space,
                 std::vector<Kokkos::pair<int, int>> const &children_host)
{
  auto children = toView<ExecutionSpace>(children_host, "Test::children");

  auto const n = children.extent(0) + 1;
  Kokkos::View<int *, ExecutionSpace> parents(
      Kokkos::view_alloc(Kokkos::WithoutInitializing, "Test::parents"),
      2 * n - 1);
  Kokkos::deep_copy(parents, -1);

  using MemorySpace = typename ExecutionSpace::memory_space;
  ArborX::Details::findParents(exec_space, MockBVH<MemorySpace>{children},
                               parents);
  return Kokkos::create_mirror_view_and_copy(Kokkos::HostSpace{}, parents);
}

#define ARBORX_TEST_FIND_PARENTS(exec_space, children, ref)                    \
  BOOST_TEST(Test::findParents(exec_space, children) == ref,                   \
             boost::test_tools::per_element())

template <class ExecutionSpace>
auto reduceLabels(ExecutionSpace const &exec_space,
                  std::vector<int> const &parents_host,
                  std::vector<int> const &labels_host)
{
  auto labels = toView<ExecutionSpace>(labels_host, "Test::labels");
  auto parents = toView<ExecutionSpace>(parents_host, "Test::parents");

  ArborX::Details::reduceLabels(exec_space, parents, labels);

  return Kokkos::create_mirror_view_and_copy(Kokkos::HostSpace{}, labels);
}

#define ARBORX_TEST_REDUCE_LABELS(exec_space, parents, labels, ref)            \
  BOOST_TEST(Test::reduceLabels(exec_space, parents, labels) == ref,           \
             boost::test_tools::per_element())

} // namespace Test

BOOST_AUTO_TEST_SUITE(TreeNodeLabeling)

BOOST_AUTO_TEST_CASE_TEMPLATE(find_parents, DeviceType, ARBORX_DEVICE_TYPES)
{

  using ExecutionSpace = typename DeviceType::execution_space;
  ExecutionSpace exec_space;
  /*
     [0]--*--
         / \
        0   1
  */
  ARBORX_TEST_FIND_PARENTS(exec_space,
                           (std::vector<Kokkos::pair<int, int>>{{1, 2}}),
                           (std::vector<int>{-1, 0, 0}));
  /*
     [0]----*----
           / \
      --*[1]  |
       / \    |
      0   1   2
  */
  ARBORX_TEST_FIND_PARENTS(
      exec_space, (std::vector<Kokkos::pair<int, int>>{{1, 4}, {2, 3}}),
      (std::vector<int>{-1, 0, 1, 1, 0}));
  /*
     [0]------------*--------------
                   / \
      ------*----[3] [4]*----------
           / \         / \
      --*[1] [2]*--   |  [5]----*--
       / \     / \    |        / \
      |   |   |   |   |   --*[6]  |
      |   |   |   |   |    / \    |
      0   1   2   3   4   5   6   7
  */
  auto const parents =
      std::vector<int>{-1, 3, 3, 0, 0, 4, 5, 1, 1, 2, 2, 4, 6, 6, 5};
  //                    0  1  2  3  4  5  6  7  8  9 10 11 12 13 14
  //                   [0][1][2][3][4][5][6] 0  1  2  3  4  5  6  7

  auto const children = std::vector<Kokkos::pair<int, int>>{
      {3, 4}, {7, 8}, {9, 10}, {1, 2}, {11, 5}, {6, 14}, {12, 13}};
  //  [0]     [1]     [2]      [3]      [4]     [5]       [6]
  //  [3][4]   0  1    2   3   [1][2]    4 [5]  [6]  7     5   6
  ARBORX_TEST_FIND_PARENTS(exec_space, children, parents);
}

BOOST_AUTO_TEST_CASE_TEMPLATE(reduce_labels, DeviceType, ARBORX_DEVICE_TYPES)
{
  /*
      [0]------------*--------------
                    / \
       ------*----[3] [4]*----------
            / \         / \
       --*[1] [2]*--   |  [5]----*--
        / \     / \    |        / \
       |   |   |   |   |   --*[6]  |
       |   |   |   |   |    / \    |
       0   1   2   3   4   5   6   7
  */
  auto const parents =
      std::vector<int>{-1, 3, 3, 0, 0, 4, 5, 1, 1, 2, 2, 4, 6, 6, 5};
  //                    0  1  2  3  4  5  6  7  8  9 10 11 12 13 14
  //                   [0][1][2][3][4][5][6] 0  1  2  3  4  5  6  7

  using ExecutionSpace = typename DeviceType::execution_space;
  ExecutionSpace exec_space;

  ARBORX_TEST_REDUCE_LABELS(
      exec_space, parents,
      (std::vector<int>{0, 1, 2, 3, 4, 5, 6, 0, 0, 0, 0, 0, 0, 0, 0}),
      (std::vector<int>{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}));

  ARBORX_TEST_REDUCE_LABELS(
      exec_space, parents,
      (std::vector<int>{0, 1, 2, 3, 4, 5, 6, 7, 7, 7, 7, 7, 7, 7, 7}),
      (std::vector<int>{7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7}));

  ARBORX_TEST_REDUCE_LABELS(
      exec_space, parents,
      (std::vector<int>{0, 1, 2, 3, 4, 5, 6, 0, 1, 2, 3, 4, 5, 6, 7}),
      (std::vector<int>{-1, -1, -1, -1, -1, -1, -1, 0, 1, 2, 3, 4, 5, 6, 7}));

  ARBORX_TEST_REDUCE_LABELS(
      exec_space, parents,
      (std::vector<int>{0, 1, 2, 3, 4, 5, 6, 0, 0, 0, 3, 4, 4, 4, 7}),
      (std::vector<int>{-1, 0, -1, -1, -1, -1, 4, 0, 0, 0, 3, 4, 4, 4, 7}));
}

BOOST_AUTO_TEST_SUITE_END()

max_stars_repo_name: aprokop/ArborX

max_issues_repo_name: aprokop/ArborX

max_forks_repo_name: aprokop/ArborX


text:
/*=============================================================================
    Copyright (c) 2001-2014 Joel de Guzman
    Copyright (c) 2001-2011 Hartmut Kaiser
    http://spirit.sourceforge.net/

    Distributed under the Boost Software License, Version 1.0. (See accompanying
    file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
=============================================================================*/
#if !defined(BOOST_SPIRIT_X3_CONTAINER_FEBRUARY_06_2007_1001AM)
#define BOOST_SPIRIT_X3_CONTAINER_FEBRUARY_06_2007_1001AM

#if defined(_MSC_VER)
#pragma once
#endif

#include <boost/fusion/support/category_of.hpp>
#include <boost/spirit/home/x3/support/unused.hpp>
#include <boost/detail/iterator.hpp>
#include <boost/fusion/include/deque.hpp>
#include <boost/mpl/has_xxx.hpp>
#include <boost/mpl/bool.hpp>
#include <boost/mpl/identity.hpp>
#include <vector>
#include <string>

namespace boost { namespace spirit { namespace x3 { namespace traits
{
    ///////////////////////////////////////////////////////////////////////////
    //  This file contains some container utils for stl containers.
    ///////////////////////////////////////////////////////////////////////////

    namespace detail
    {
        BOOST_MPL_HAS_XXX_TRAIT_DEF(value_type)
        BOOST_MPL_HAS_XXX_TRAIT_DEF(iterator)
        BOOST_MPL_HAS_XXX_TRAIT_DEF(size_type)
        BOOST_MPL_HAS_XXX_TRAIT_DEF(reference)
    }

    template <typename T, typename Enable = void>
    struct is_container
      : mpl::bool_<
            detail::has_value_type<T>::value &&
            detail::has_iterator<T>::value &&
            detail::has_size_type<T>::value &&
            detail::has_reference<T>::value>
    {};

    ///////////////////////////////////////////////////////////////////////////
    namespace detail
    {
        template <typename T>
        struct remove_value_const : mpl::identity<T> {};

        template <typename T>
        struct remove_value_const<T const> : remove_value_const<T> {};

        template <typename F, typename S>
        struct remove_value_const<std::pair<F, S>>
        {
            typedef typename remove_value_const<F>::type first_type;
            typedef typename remove_value_const<S>::type second_type;
            typedef std::pair<first_type, second_type> type;
        };
    }

    ///////////////////////////////////////////////////////////////////////
    template <typename Container, typename Enable = void>
    struct container_value
      : detail::remove_value_const<typename Container::value_type>
    {};

    template <typename Container>
    struct container_value<Container const> : container_value<Container> {};

    // There is no single container value for fusion maps, but because output
    // of this metafunc is used to check wheter parser's attribute can be
    // saved to container, we simply return whole fusion::map as is
    // so that check can be done in traits::is_substitute specialisation
    template <typename T>
    struct container_value<T
			   , typename enable_if<typename mpl::eval_if <
						    fusion::traits::is_sequence<T>
						    , fusion::traits::is_associative<T>
						    , mpl::false_ >::type >::type>
    : mpl::identity<T> {};

    template <>
    struct container_value<unused_type> : mpl::identity<unused_type> {};

    ///////////////////////////////////////////////////////////////////////////
    template <typename Container, typename Enable = void>
    struct container_iterator
        : mpl::identity<typename Container::iterator> {};

    template <typename Container>
    struct container_iterator<Container const>
         : mpl::identity<typename Container::const_iterator> {};

    template <>
    struct container_iterator<unused_type>
        : mpl::identity<unused_type const*> {};

    template <>
    struct container_iterator<unused_type const>
        : mpl::identity<unused_type const*> {};

    ///////////////////////////////////////////////////////////////////////////
    template <typename Container, typename T>
    bool push_back(Container& c, T&& val);

    template <typename Container, typename Enable = void>
    struct push_back_container
    {
        template <typename T>
        static bool call(Container& c, T&& val)
        {
            c.insert(c.end(), std::move(val));
            return true;
        }
    };

    template <typename Container, typename T>
    inline bool push_back(Container& c, T&& val)
    {
        return push_back_container<Container>::call(c, std::move(val));
    }

    template <typename Container>
    inline bool push_back(Container&, unused_type)
    {
        return true;
    }

    template <typename T>
    inline bool push_back(unused_type, T const&)
    {
        return true;
    }

    inline bool push_back(unused_type, unused_type)
    {
        return true;
    }

    ///////////////////////////////////////////////////////////////////////////
    template <typename Container, typename Iterator>
    bool append(Container& c, Iterator first, Iterator last);

    template <typename Container, typename Enable = void>
    struct append_container
    {
        // Not all containers have "reserve"
        template <typename Container_>
        static void reserve(Container_& c, std::size_t size) {}

        template <typename T>
        static void reserve(std::vector<T>& c, std::size_t size)
        {
            c.reserve(size);
        }

        template <typename Iterator>
        static bool call(Container& c, Iterator first, Iterator last)
        {
            reserve(c, c.size() + std::distance(first, last));
            c.insert(c.end(), first, last);
            return true;
        }
    };

    template <typename Container, typename Iterator>
    inline bool append(Container& c, Iterator first, Iterator last)
    {
        return append_container<Container>::call(c, first, last);
    }

    template <typename Iterator>
    inline bool append(unused_type, Iterator first, Iterator last)
    {
        return true;
    }

    ///////////////////////////////////////////////////////////////////////////
    template <typename Container, typename Enable = void>
    struct is_empty_container
    {
        static bool call(Container const& c)
        {
            return c.empty();
        }
    };

    template <typename Container>
    inline bool is_empty(Container const& c)
    {
        return is_empty_container<Container>::call(c);
    }

    inline bool is_empty(unused_type)
    {
        return true;
    }

    ///////////////////////////////////////////////////////////////////////////
    template <typename Container, typename Enable = void>
    struct begin_container
    {
        static typename container_iterator<Container>::type call(Container& c)
        {
            return c.begin();
        }
    };

    template <typename Container>
    inline typename container_iterator<Container>::type
    begin(Container& c)
    {
        return begin_container<Container>::call(c);
    }

    inline unused_type const*
    begin(unused_type)
    {
        return &unused;
    }

    ///////////////////////////////////////////////////////////////////////////
    template <typename Container, typename Enable = void>
    struct end_container
    {
        static typename container_iterator<Container>::type call(Container& c)
        {
            return c.end();
        }
    };

    template <typename Container>
    inline typename container_iterator<Container>::type
    end(Container& c)
    {
        return end_container<Container>::call(c);
    }

    inline unused_type const*
    end(unused_type)
    {
        return &unused;
    }

    ///////////////////////////////////////////////////////////////////////////
    template <typename Iterator, typename Enable = void>
    struct deref_iterator
    {
        typedef typename boost::detail::iterator_traits<Iterator>::reference type;
        static type call(Iterator& it)
        {
            return *it;
        }
    };

    template <typename Iterator>
    typename deref_iterator<Iterator>::type
    deref(Iterator& it)
    {
        return deref_iterator<Iterator>::call(it);
    }

    inline unused_type
    deref(unused_type const*)
    {
        return unused;
    }

    ///////////////////////////////////////////////////////////////////////////
    template <typename Iterator, typename Enable = void>
    struct next_iterator
    {
        static void call(Iterator& it)
        {
            ++it;
        }
    };

    template <typename Iterator>
    void next(Iterator& it)
    {
        next_iterator<Iterator>::call(it);
    }

    inline void next(unused_type const*)
    {
        // do nothing
    }

    ///////////////////////////////////////////////////////////////////////////
    template <typename Iterator, typename Enable = void>
    struct compare_iterators
    {
        static bool call(Iterator const& it1, Iterator const& it2)
        {
            return it1 == it2;
        }
    };

    template <typename Iterator>
    bool compare(Iterator& it1, Iterator& it2)
    {
        return compare_iterators<Iterator>::call(it1, it2);
    }

    inline bool compare(unused_type const*, unused_type const*)
    {
        return false;
    }

    ///////////////////////////////////////////////////////////////////////////
    template <typename T>
    struct build_container : mpl::identity<std::vector<T>> {};

    template <typename T>
    struct build_container<boost::fusion::deque<T> > : build_container<T> {};

    template <>
    struct build_container<unused_type> : mpl::identity<unused_type> {};

    template <>
    struct build_container<char> : mpl::identity<std::string> {};

}}}}

#endif

ext: hpp


text: #include <boost/test/minimal.hpp>

max_stars_repo_name: miathedev/BoostForArduino

max_issues_repo_name: miathedev/BoostForArduino

max_forks_repo_name: miathedev/BoostForArduino


text:
/*
 * Copyright 2010 Vicente J. Botet Escriba
 * Copyright 2015 Andrey Semashev
 * Copyright 2016 Jorge Lodos
 * Copyright 2017 James E. King, III
 *
 * Distributed under the Boost Software License, Version 1.0.
 * See http://www.boost.org/LICENSE_1_0.txt
 */

#ifndef BOOST_WINAPI_FILE_MANAGEMENT_HPP_INCLUDED_
#define BOOST_WINAPI_FILE_MANAGEMENT_HPP_INCLUDED_

#include <boost/winapi/basic_types.hpp>
#include <boost/winapi/limits.hpp>
#include <boost/winapi/time.hpp>
#include <boost/winapi/overlapped.hpp>

#ifdef BOOST_HAS_PRAGMA_ONCE
#pragma once
#endif

/*
 * UWP:
 * API                         SDK 8     SDK 10            _WIN32_WINNT
 * AreFileApisANSI             DESKTOP - DESKTOP | SYSTEM
 * CreateFile                  DESKTOP - DESKTOP | SYSTEM
 * DeleteFile                  APP     - APP     | SYSTEM
 * FindClose                   APP     - APP     | SYSTEM
 * FindFirstFile               DESKTOP > APP     | SYSTEM
 * FindNextFile                DESKTOP > APP     | SYSTEM
 * GetFileAttributes           DESKTOP > APP     | SYSTEM
 * GetFileInformationByHandle  DESKTOP - DESKTOP | SYSTEM
 * GetFileSizeEx               DESKTOP > APP     | SYSTEM
 * LockFile                    DESKTOP - DESKTOP | SYSTEM
 * MoveFileEx                  APP     - APP     | SYSTEM
 * ReadFile                    APP     - APP     | SYSTEM
 * SetEndOfFile                APP     - APP     | SYSTEM
 * SetFilePointer              DESKTOP > APP     | SYSTEM
 * SetFileValidData            DESKTOP - DESKTOP | SYSTEM  >= 0x0501
 * UnlockFile                  DESKTOP - DESKTOP | SYSTEM
 * WriteFile                   APP     - APP     | SYSTEM
 */

#if !defined( BOOST_USE_WINDOWS_H )
extern "C" {

#if BOOST_WINAPI_PARTITION_DESKTOP || BOOST_WINAPI_PARTITION_SYSTEM
#if !defined( BOOST_NO_ANSI_APIS )
BOOST_SYMBOL_IMPORT boost::winapi::BOOL_ WINAPI
AreFileApisANSI(BOOST_WINAPI_DETAIL_VOID);

BOOST_SYMBOL_IMPORT boost::winapi::HANDLE_ WINAPI
CreateFileA(
    boost::winapi::LPCSTR_ lpFileName,
    boost::winapi::DWORD_ dwDesiredAccess,
    boost::winapi::DWORD_ dwShareMode,
    ::_SECURITY_ATTRIBUTES* lpSecurityAttributes,
    boost::winapi::DWORD_ dwCreationDisposition,
    boost::winapi::DWORD_ dwFlagsAndAttributes,
    boost::winapi::HANDLE_ hTemplateFile);

struct _WIN32_FIND_DATAA;
BOOST_SYMBOL_IMPORT boost::winapi::HANDLE_ WINAPI
FindFirstFileA(boost::winapi::LPCSTR_ lpFileName, ::_WIN32_FIND_DATAA* lpFindFileData);

BOOST_SYMBOL_IMPORT boost::winapi::BOOL_ WINAPI
FindNextFileA(boost::winapi::HANDLE_ hFindFile, ::_WIN32_FIND_DATAA* lpFindFileData);
#endif

BOOST_SYMBOL_IMPORT boost::winapi::HANDLE_ WINAPI
CreateFileW(
    boost::winapi::LPCWSTR_ lpFileName,
    boost::winapi::DWORD_ dwDesiredAccess,
    boost::winapi::DWORD_ dwShareMode,
    ::_SECURITY_ATTRIBUTES* lpSecurityAttributes,
    boost::winapi::DWORD_ dwCreationDisposition,
    boost::winapi::DWORD_ dwFlagsAndAttributes,
    boost::winapi::HANDLE_ hTemplateFile);

struct _WIN32_FIND_DATAW;
BOOST_SYMBOL_IMPORT boost::winapi::HANDLE_ WINAPI
FindFirstFileW(boost::winapi::LPCWSTR_ lpFileName, ::_WIN32_FIND_DATAW* lpFindFileData);

BOOST_SYMBOL_IMPORT boost::winapi::BOOL_ WINAPI
FindNextFileW(boost::winapi::HANDLE_ hFindFile, ::_WIN32_FIND_DATAW* lpFindFileData);

struct _BY_HANDLE_FILE_INFORMATION;
BOOST_SYMBOL_IMPORT boost::winapi::BOOL_ WINAPI
GetFileInformationByHandle(
    boost::winapi::HANDLE_ hFile,
    ::_BY_HANDLE_FILE_INFORMATION* lpFileInformation);

BOOST_SYMBOL_IMPORT boost::winapi::BOOL_ WINAPI
LockFile(
    boost::winapi::HANDLE_ hFile,
    boost::winapi::DWORD_ dwFileOffsetLow,
    boost::winapi::DWORD_ dwFileOffsetHigh,
    boost::winapi::DWORD_ nNumberOfBytesToLockLow,
    boost::winapi::DWORD_ nNumberOfBytesToLockHigh);

BOOST_SYMBOL_IMPORT boost::winapi::BOOL_ WINAPI
LockFileEx(
    boost::winapi::HANDLE_ hFile,
    boost::winapi::DWORD_ dwFlags,
    boost::winapi::DWORD_ dwReserved,
    boost::winapi::DWORD_ nNumberOfBytesToLockLow,
    boost::winapi::DWORD_ nNumberOfBytesToLockHigh,
    ::_OVERLAPPED* lpOverlapped);

#if BOOST_USE_WINAPI_VERSION >= BOOST_WINAPI_VERSION_WINXP
BOOST_SYMBOL_IMPORT boost::winapi::BOOL_ WINAPI
SetFileValidData(
    boost::winapi::HANDLE_ hFile,
    boost::winapi::LONGLONG_ ValidDataLength);
#endif

BOOST_SYMBOL_IMPORT boost::winapi::BOOL_ WINAPI
UnlockFile(
    boost::winapi::HANDLE_ hFile,
    boost::winapi::DWORD_ dwFileOffsetLow,
    boost::winapi::DWORD_ dwFileOffsetHigh,
    boost::winapi::DWORD_ nNumberOfBytesToUnlockLow,
    boost::winapi::DWORD_ nNumberOfBytesToUnlockHigh);

BOOST_SYMBOL_IMPORT boost::winapi::BOOL_ WINAPI
UnlockFileEx(
    boost::winapi::HANDLE_ hFile,
    boost::winapi::DWORD_ dwReserved,
    boost::winapi::DWORD_ nNumberOfBytesToUnlockLow,
    boost::winapi::DWORD_ nNumberOfBytesToUnlockHigh,
    ::_OVERLAPPED* lpOverlapped);
#endif

#if BOOST_WINAPI_PARTITION_APP || BOOST_WINAPI_PARTITION_SYSTEM
#if !defined( BOOST_NO_ANSI_APIS )
BOOST_SYMBOL_IMPORT boost::winapi::BOOL_ WINAPI
DeleteFileA(boost::winapi::LPCSTR_ lpFileName);

BOOST_SYMBOL_IMPORT boost::winapi::BOOL_ WINAPI
MoveFileExA(
    boost::winapi::LPCSTR_ lpExistingFileName,
    boost::winapi::LPCSTR_ lpNewFileName,
    boost::winapi::DWORD_ dwFlags);
#endif

BOOST_SYMBOL_IMPORT boost::winapi::BOOL_ WINAPI
DeleteFileW(boost::winapi::LPCWSTR_ lpFileName);

BOOST_SYMBOL_IMPORT boost::winapi::BOOL_ WINAPI
FindClose(boost::winapi::HANDLE_ hFindFile);

BOOST_SYMBOL_IMPORT boost::winapi::BOOL_ WINAPI
MoveFileExW(
    boost::winapi::LPCWSTR_ lpExistingFileName,
    boost::winapi::LPCWSTR_ lpNewFileName,
    boost::winapi::DWORD_ dwFlags);

BOOST_SYMBOL_IMPORT boost::winapi::BOOL_ WINAPI
ReadFile(
    boost::winapi::HANDLE_ hFile,
    boost::winapi::LPVOID_ lpBuffer,
    boost::winapi::DWORD_ nNumberOfBytesToRead,
    boost::winapi::LPDWORD_ lpNumberOfBytesRead,
    ::_OVERLAPPED* lpOverlapped);

BOOST_SYMBOL_IMPORT boost::winapi::BOOL_ WINAPI
SetEndOfFile(boost::winapi::HANDLE_ hFile);

BOOST_SYMBOL_IMPORT boost::winapi::BOOL_ WINAPI
WriteFile(
    boost::winapi::HANDLE_ hFile,
    boost::winapi::LPCVOID_ lpBuffer,
    boost::winapi::DWORD_ nNumberOfBytesToWrite,
    boost::winapi::LPDWORD_ lpNumberOfBytesWritten,
    ::_OVERLAPPED* lpOverlapped);
#endif // BOOST_WINAPI_PARTITION_APP || BOOST_WINAPI_PARTITION_SYSTEM

#if BOOST_WINAPI_PARTITION_APP_SYSTEM
#if !defined( BOOST_NO_ANSI_APIS )
BOOST_SYMBOL_IMPORT boost::winapi::DWORD_ WINAPI
GetFileAttributesA(boost::winapi::LPCSTR_ lpFileName);
#endif

BOOST_SYMBOL_IMPORT boost::winapi::DWORD_ WINAPI
GetFileAttributesW(boost::winapi::LPCWSTR_ lpFileName);

BOOST_SYMBOL_IMPORT boost::winapi::BOOL_ WINAPI
GetFileSizeEx(boost::winapi::HANDLE_ hFile, ::_LARGE_INTEGER* lpFileSize);

BOOST_SYMBOL_IMPORT boost::winapi::DWORD_ WINAPI
SetFilePointer(
    boost::winapi::HANDLE_ hFile,
    boost::winapi::LONG_ lpDistanceToMove,
    boost::winapi::PLONG_ lpDistanceToMoveHigh,
    boost::winapi::DWORD_ dwMoveMethod);
#endif // BOOST_WINAPI_PARTITION_APP_SYSTEM

} // extern "C"
#endif // !defined(BOOST_USE_WINDOWS_H)

namespace boost {
namespace winapi {

#if defined( BOOST_USE_WINDOWS_H )

const DWORD_ INVALID_FILE_SIZE_ = INVALID_FILE_SIZE;
const DWORD_ INVALID_SET_FILE_POINTER_ = INVALID_SET_FILE_POINTER;
const DWORD_ INVALID_FILE_ATTRIBUTES_ = INVALID_FILE_ATTRIBUTES;

const DWORD_ FILE_ATTRIBUTE_READONLY_ = FILE_ATTRIBUTE_READONLY;
const DWORD_ FILE_ATTRIBUTE_HIDDEN_ = FILE_ATTRIBUTE_HIDDEN;
const DWORD_ FILE_ATTRIBUTE_SYSTEM_ = FILE_ATTRIBUTE_SYSTEM;
const DWORD_ FILE_ATTRIBUTE_DIRECTORY_ = FILE_ATTRIBUTE_DIRECTORY;
const DWORD_ FILE_ATTRIBUTE_ARCHIVE_ = FILE_ATTRIBUTE_ARCHIVE;
const DWORD_ FILE_ATTRIBUTE_DEVICE_ = FILE_ATTRIBUTE_DEVICE;
const DWORD_ FILE_ATTRIBUTE_NORMAL_ = FILE_ATTRIBUTE_NORMAL;
const DWORD_ FILE_ATTRIBUTE_TEMPORARY_ = FILE_ATTRIBUTE_TEMPORARY;
const DWORD_ FILE_ATTRIBUTE_SPARSE_FILE_ = FILE_ATTRIBUTE_SPARSE_FILE;
const DWORD_ FILE_ATTRIBUTE_REPARSE_POINT_ = FILE_ATTRIBUTE_REPARSE_POINT;
const DWORD_ FILE_ATTRIBUTE_COMPRESSED_ = FILE_ATTRIBUTE_COMPRESSED;
const DWORD_ FILE_ATTRIBUTE_OFFLINE_ = FILE_ATTRIBUTE_OFFLINE;
const DWORD_ FILE_ATTRIBUTE_NOT_CONTENT_INDEXED_ = FILE_ATTRIBUTE_NOT_CONTENT_INDEXED;
const DWORD_ FILE_ATTRIBUTE_ENCRYPTED_ = FILE_ATTRIBUTE_ENCRYPTED;

const DWORD_ CREATE_NEW_ = CREATE_NEW;
const DWORD_ CREATE_ALWAYS_ = CREATE_ALWAYS;
const DWORD_ OPEN_EXISTING_ = OPEN_EXISTING;
const DWORD_ OPEN_ALWAYS_ = OPEN_ALWAYS;
const DWORD_ TRUNCATE_EXISTING_ = TRUNCATE_EXISTING;

const DWORD_ FILE_SHARE_READ_ = FILE_SHARE_READ;
const DWORD_ FILE_SHARE_WRITE_ = FILE_SHARE_WRITE;
const DWORD_ FILE_SHARE_DELETE_ = FILE_SHARE_DELETE;

const DWORD_ FILE_BEGIN_ = FILE_BEGIN;
const DWORD_ FILE_CURRENT_ = FILE_CURRENT;
const DWORD_ FILE_END_ = FILE_END;

#else // defined( BOOST_USE_WINDOWS_H )

const DWORD_ INVALID_FILE_SIZE_ = ((DWORD_)0xFFFFFFFF);
const DWORD_ INVALID_SET_FILE_POINTER_ = ((DWORD_)-1);
const DWORD_ INVALID_FILE_ATTRIBUTES_ = ((DWORD_)-1);

const DWORD_ FILE_ATTRIBUTE_READONLY_ = 0x00000001;
const DWORD_ FILE_ATTRIBUTE_HIDDEN_ = 0x00000002;
const DWORD_ FILE_ATTRIBUTE_SYSTEM_ = 0x00000004;
const DWORD_ FILE_ATTRIBUTE_DIRECTORY_ = 0x00000010;
const DWORD_ FILE_ATTRIBUTE_ARCHIVE_ = 0x00000020;
const DWORD_ FILE_ATTRIBUTE_DEVICE_ = 0x00000040;
const DWORD_ FILE_ATTRIBUTE_NORMAL_ = 0x00000080;
const DWORD_ FILE_ATTRIBUTE_TEMPORARY_ = 0x00000100;
const DWORD_ FILE_ATTRIBUTE_SPARSE_FILE_ = 0x00000200;
const DWORD_ FILE_ATTRIBUTE_REPARSE_POINT_ = 0x00000400;
const DWORD_ FILE_ATTRIBUTE_COMPRESSED_ = 0x00000800;
const DWORD_ FILE_ATTRIBUTE_OFFLINE_ = 0x00001000;
const DWORD_ FILE_ATTRIBUTE_NOT_CONTENT_INDEXED_ = 0x00002000;
const DWORD_ FILE_ATTRIBUTE_ENCRYPTED_ = 0x00004000;

const DWORD_ CREATE_NEW_ = 1;
const DWORD_ CREATE_ALWAYS_ = 2;
const DWORD_ OPEN_EXISTING_ = 3;
const DWORD_ OPEN_ALWAYS_ = 4;
const DWORD_ TRUNCATE_EXISTING_ = 5;

const DWORD_ FILE_SHARE_READ_ = 0x00000001;
const DWORD_ FILE_SHARE_WRITE_ = 0x00000002;
const DWORD_ FILE_SHARE_DELETE_ = 0x00000004;

const DWORD_ FILE_BEGIN_ = 0;
const DWORD_ FILE_CURRENT_ = 1;
const DWORD_ FILE_END_ = 2;

#endif // defined( BOOST_USE_WINDOWS_H )

// Some of these constants are not defined by Windows SDK in MinGW or older MSVC
const DWORD_ FILE_FLAG_WRITE_THROUGH_ = 0x80000000;
const DWORD_ FILE_FLAG_OVERLAPPED_ = 0x40000000;
const DWORD_ FILE_FLAG_NO_BUFFERING_ = 0x20000000;
const DWORD_ FILE_FLAG_RANDOM_ACCESS_ = 0x10000000;
const DWORD_ FILE_FLAG_SEQUENTIAL_SCAN_ = 0x08000000;
const DWORD_ FILE_FLAG_DELETE_ON_CLOSE_ = 0x04000000;
const DWORD_ FILE_FLAG_BACKUP_SEMANTICS_ = 0x02000000;
const DWORD_ FILE_FLAG_POSIX_SEMANTICS_ = 0x01000000;
const DWORD_ FILE_FLAG_SESSION_AWARE_ = 0x00800000;
const DWORD_ FILE_FLAG_OPEN_REPARSE_POINT_ = 0x00200000;
const DWORD_ FILE_FLAG_OPEN_NO_RECALL_ = 0x00100000;
const DWORD_ FILE_FLAG_FIRST_PIPE_INSTANCE_ = 0x00080000;

#if BOOST_USE_WINAPI_VERSION >= BOOST_WINAPI_VERSION_WIN8
const DWORD_ FILE_FLAG_OPEN_REQUIRING_OPLOCK_ = 0x00040000;
#endif

// This constant is not defined in Windows SDK up until 6.0A
const DWORD_ FILE_ATTRIBUTE_VIRTUAL_ = 0x00010000;

// These constants are not defined in Windows SDK up until 8.0 and MinGW/MinGW-w64 (as of 2016-02-14).
// They are documented to be supported only since Windows 8/Windows Server 2012
// but defined unconditionally.
const DWORD_ FILE_ATTRIBUTE_INTEGRITY_STREAM_ = 0x00008000;
const DWORD_ FILE_ATTRIBUTE_NO_SCRUB_DATA_ = 0x00020000;
// Undocumented
const DWORD_ FILE_ATTRIBUTE_EA_ = 0x00040000;

#if BOOST_WINAPI_PARTITION_DESKTOP || BOOST_WINAPI_PARTITION_SYSTEM
#if !defined( BOOST_NO_ANSI_APIS )
using ::AreFileApisANSI;

BOOST_FORCEINLINE HANDLE_ CreateFileA(
    LPCSTR_ lpFileName,
    DWORD_ dwDesiredAccess,
    DWORD_ dwShareMode,
    SECURITY_ATTRIBUTES_* lpSecurityAttributes,
    DWORD_ dwCreationDisposition,
    DWORD_ dwFlagsAndAttributes,
    HANDLE_ hTemplateFile)
{
    return ::CreateFileA(
        lpFileName,
        dwDesiredAccess,
        dwShareMode,
        reinterpret_cast< ::_SECURITY_ATTRIBUTES* >(lpSecurityAttributes),
        dwCreationDisposition,
        dwFlagsAndAttributes,
        hTemplateFile);
}

BOOST_FORCEINLINE HANDLE_ create_file(
    LPCSTR_ lpFileName,
    DWORD_ dwDesiredAccess,
    DWORD_ dwShareMode,
    SECURITY_ATTRIBUTES_* lpSecurityAttributes,
    DWORD_ dwCreationDisposition,
    DWORD_ dwFlagsAndAttributes,
    HANDLE_ hTemplateFile)
{
    return ::CreateFileA(
        lpFileName,
        dwDesiredAccess,
        dwShareMode,
        reinterpret_cast< ::_SECURITY_ATTRIBUTES* >(lpSecurityAttributes),
        dwCreationDisposition,
        dwFlagsAndAttributes,
        hTemplateFile);
}

typedef struct BOOST_MAY_ALIAS _WIN32_FIND_DATAA {
    DWORD_ dwFileAttributes;
    FILETIME_ ftCreationTime;
    FILETIME_ ftLastAccessTime;
    FILETIME_ ftLastWriteTime;
    DWORD_ nFileSizeHigh;
    DWORD_ nFileSizeLow;
    DWORD_ dwReserved0;
    DWORD_ dwReserved1;
    CHAR_   cFileName[MAX_PATH_];
    CHAR_   cAlternateFileName[14];
#ifdef _MAC
    DWORD_ dwFileType;
    DWORD_ dwCreatorType;
    WORD_  wFinderFlags;
#endif
} WIN32_FIND_DATAA_, *PWIN32_FIND_DATAA_, *LPWIN32_FIND_DATAA_;

BOOST_FORCEINLINE HANDLE_ FindFirstFileA(LPCSTR_ lpFileName, WIN32_FIND_DATAA_* lpFindFileData)
{
    return ::FindFirstFileA(lpFileName, reinterpret_cast< ::_WIN32_FIND_DATAA* >(lpFindFileData));
}

BOOST_FORCEINLINE HANDLE_ find_first_file(LPCSTR_ lpFileName, WIN32_FIND_DATAA_* lpFindFileData)
{
    return ::FindFirstFileA(lpFileName, reinterpret_cast< ::_WIN32_FIND_DATAA* >(lpFindFileData));
}

BOOST_FORCEINLINE BOOL_ FindNextFileA(HANDLE_ hFindFile, WIN32_FIND_DATAA_* lpFindFileData)
{
    return ::FindNextFileA(hFindFile, reinterpret_cast< ::_WIN32_FIND_DATAA* >(lpFindFileData));
}

BOOST_FORCEINLINE BOOL_ find_next_file(HANDLE_ hFindFile, WIN32_FIND_DATAA_* lpFindFileData)
{
    return ::FindNextFileA(hFindFile, reinterpret_cast< ::_WIN32_FIND_DATAA* >(lpFindFileData));
}

#endif // !defined( BOOST_NO_ANSI_APIS )

BOOST_FORCEINLINE HANDLE_ CreateFileW(
    LPCWSTR_ lpFileName,
    DWORD_ dwDesiredAccess,
    DWORD_ dwShareMode,
    SECURITY_ATTRIBUTES_* lpSecurityAttributes,
    DWORD_ dwCreationDisposition,
    DWORD_ dwFlagsAndAttributes,
    HANDLE_ hTemplateFile)
{
    return ::CreateFileW(
        lpFileName,
        dwDesiredAccess,
        dwShareMode,
        reinterpret_cast< ::_SECURITY_ATTRIBUTES* >(lpSecurityAttributes),
        dwCreationDisposition,
        dwFlagsAndAttributes,
        hTemplateFile);
}

BOOST_FORCEINLINE HANDLE_ create_file(
    LPCWSTR_ lpFileName,
    DWORD_ dwDesiredAccess,
    DWORD_ dwShareMode,
    SECURITY_ATTRIBUTES_* lpSecurityAttributes,
    DWORD_ dwCreationDisposition,
    DWORD_ dwFlagsAndAttributes,
    HANDLE_ hTemplateFile)
{
    return ::CreateFileW(
        lpFileName,
        dwDesiredAccess,
        dwShareMode,
        reinterpret_cast< ::_SECURITY_ATTRIBUTES* >(lpSecurityAttributes),
        dwCreationDisposition,
        dwFlagsAndAttributes,
        hTemplateFile);
}

typedef struct BOOST_MAY_ALIAS _WIN32_FIND_DATAW {
    DWORD_ dwFileAttributes;
    FILETIME_ ftCreationTime;
    FILETIME_ ftLastAccessTime;
    FILETIME_ ftLastWriteTime;
    DWORD_ nFileSizeHigh;
    DWORD_ nFileSizeLow;
    DWORD_ dwReserved0;
    DWORD_ dwReserved1;
    WCHAR_  cFileName[MAX_PATH_];
    WCHAR_  cAlternateFileName[14];
#ifdef _MAC
    DWORD_ dwFileType;
    DWORD_ dwCreatorType;
    WORD_  wFinderFlags;
#endif
} WIN32_FIND_DATAW_, *PWIN32_FIND_DATAW_, *LPWIN32_FIND_DATAW_;

typedef struct BOOST_MAY_ALIAS _BY_HANDLE_FILE_INFORMATION {
    DWORD_ dwFileAttributes;
    FILETIME_ ftCreationTime;
    FILETIME_ ftLastAccessTime;
    FILETIME_ ftLastWriteTime;
    DWORD_ dwVolumeSerialNumber;
    DWORD_ nFileSizeHigh;
    DWORD_ nFileSizeLow;
    DWORD_ nNumberOfLinks;
    DWORD_ nFileIndexHigh;
    DWORD_ nFileIndexLow;
} BY_HANDLE_FILE_INFORMATION_, *PBY_HANDLE_FILE_INFORMATION_, *LPBY_HANDLE_FILE_INFORMATION_;

BOOST_FORCEINLINE HANDLE_ FindFirstFileW(LPCWSTR_ lpFileName, WIN32_FIND_DATAW_* lpFindFileData)
{
    return ::FindFirstFileW(lpFileName, reinterpret_cast< ::_WIN32_FIND_DATAW* >(lpFindFileData));
}

BOOST_FORCEINLINE HANDLE_ find_first_file(LPCWSTR_ lpFileName, WIN32_FIND_DATAW_* lpFindFileData)
{
    return ::FindFirstFileW(lpFileName, reinterpret_cast< ::_WIN32_FIND_DATAW* >(lpFindFileData));
}

BOOST_FORCEINLINE BOOL_ FindNextFileW(HANDLE_ hFindFile, WIN32_FIND_DATAW_* lpFindFileData)
{
    return ::FindNextFileW(hFindFile, reinterpret_cast< ::_WIN32_FIND_DATAW* >(lpFindFileData));
}

BOOST_FORCEINLINE BOOL_ find_next_file(HANDLE_ hFindFile, WIN32_FIND_DATAW_* lpFindFileData)
{
    return ::FindNextFileW(hFindFile, reinterpret_cast< ::_WIN32_FIND_DATAW* >(lpFindFileData));
}

BOOST_FORCEINLINE BOOL_ GetFileInformationByHandle(HANDLE_ h, BY_HANDLE_FILE_INFORMATION_* info)
{
    return ::GetFileInformationByHandle(h, reinterpret_cast< ::_BY_HANDLE_FILE_INFORMATION* >(info));
}

using ::LockFile;

BOOST_FORCEINLINE BOOL_ LockFileEx(
    HANDLE_ hFile,
    DWORD_ dwFlags,
    DWORD_ dwReserved,
    DWORD_ nNumberOfBytesToLockLow,
    DWORD_ nNumberOfBytesToLockHigh,
    OVERLAPPED_* lpOverlapped)
{
    return ::LockFileEx(hFile, dwFlags, dwReserved, nNumberOfBytesToLockLow, nNumberOfBytesToLockHigh, reinterpret_cast< ::_OVERLAPPED* >(lpOverlapped));
}

#if BOOST_USE_WINAPI_VERSION >= BOOST_WINAPI_VERSION_WINXP
using ::SetFileValidData;
#endif

using ::UnlockFile;

BOOST_FORCEINLINE BOOL_ UnlockFileEx(
    HANDLE_ hFile,
    DWORD_ dwReserved,
    DWORD_ nNumberOfBytesToUnlockLow,
    DWORD_ nNumberOfBytesToUnlockHigh,
    OVERLAPPED_* lpOverlapped)
{
    return ::UnlockFileEx(hFile, dwReserved, nNumberOfBytesToUnlockLow, nNumberOfBytesToUnlockHigh, reinterpret_cast< ::_OVERLAPPED* >(lpOverlapped));
}
#endif // BOOST_WINAPI_PARTITION_DESKTOP || BOOST_WINAPI_PARTITION_SYSTEM

#if BOOST_WINAPI_PARTITION_APP || BOOST_WINAPI_PARTITION_SYSTEM
#if !defined( BOOST_NO_ANSI_APIS )
using ::DeleteFileA;

BOOST_FORCEINLINE BOOL_ delete_file(LPCSTR_ lpFileName)
{
    return ::DeleteFileA(lpFileName);
}

using ::MoveFileExA;

BOOST_FORCEINLINE BOOL_ move_file(LPCSTR_ lpExistingFileName, LPCSTR_ lpNewFileName, DWORD_ dwFlags)
{
    return ::MoveFileExA(lpExistingFileName, lpNewFileName, dwFlags);
}

#endif
using ::DeleteFileW;

BOOST_FORCEINLINE BOOL_ delete_file(LPCWSTR_ lpFileName)
{
    return ::DeleteFileW(lpFileName);
}

using ::FindClose;
using ::MoveFileExW;

BOOST_FORCEINLINE BOOL_ move_file(LPCWSTR_ lpExistingFileName, LPCWSTR_ lpNewFileName, DWORD_ dwFlags)
{
    return ::MoveFileExW(lpExistingFileName, lpNewFileName, dwFlags);
}

BOOST_FORCEINLINE BOOL_ ReadFile(
    HANDLE_ hFile,
    LPVOID_ lpBuffer,
    DWORD_ nNumberOfBytesToWrite,
    LPDWORD_ lpNumberOfBytesWritten,
    OVERLAPPED_* lpOverlapped)
{
    return ::ReadFile(hFile, lpBuffer, nNumberOfBytesToWrite, lpNumberOfBytesWritten, reinterpret_cast< ::_OVERLAPPED* >(lpOverlapped));
}

using ::SetEndOfFile;

BOOST_FORCEINLINE BOOL_ WriteFile(
    HANDLE_ hFile,
    LPCVOID_ lpBuffer,
    DWORD_ nNumberOfBytesToWrite,
    LPDWORD_ lpNumberOfBytesWritten,
    OVERLAPPED_* lpOverlapped)
{
    return ::WriteFile(hFile, lpBuffer, nNumberOfBytesToWrite, lpNumberOfBytesWritten, reinterpret_cast< ::_OVERLAPPED* >(lpOverlapped));
}
#endif // BOOST_WINAPI_PARTITION_APP || BOOST_WINAPI_PARTITION_SYSTEM

#if BOOST_WINAPI_PARTITION_APP_SYSTEM
#if !defined( BOOST_NO_ANSI_APIS )
using ::GetFileAttributesA;

BOOST_FORCEINLINE DWORD_ get_file_attributes(LPCSTR_ lpFileName)
{
    return ::GetFileAttributesA(lpFileName);
}
#endif
using ::GetFileAttributesW;

BOOST_FORCEINLINE DWORD_ get_file_attributes(LPCWSTR_ lpFileName)
{
    return ::GetFileAttributesW(lpFileName);
}

BOOST_FORCEINLINE BOOL_ GetFileSizeEx(HANDLE_ hFile, LARGE_INTEGER_* lpFileSize)
{
    return ::GetFileSizeEx(hFile, reinterpret_cast< ::_LARGE_INTEGER* >(lpFileSize));
}

using ::SetFilePointer;
#endif // BOOST_WINAPI_PARTITION_APP_SYSTEM

}
}

#endif // BOOST_WINAPI_FILE_MANAGEMENT_HPP_INCLUDED_

max_stars_repo_name: dilawar/eyesthatblink

max_issues_repo_name: dilawar/eyesthatblink

max_forks_repo_name: dilawar/eyesthatblink


text:
// This file is part of Eigen, a lightweight C++ template library
// for linear algebra.
//
// Copyright (C) 2014 Benoit Steiner <benoit.steiner.goog@gmail.com>
//
// This Source Code Form is subject to the terms of the Mozilla
// Public License v. 2.0. If a copy of the MPL was not distributed
// with this file, You can obtain one at http://mozilla.org/MPL/2.0/.

#include "main.h"

#include <Eigen/CXX11/Tensor>

using Eigen::Tensor;

static void test_simple_swap()
{
  Tensor<float, 3, ColMajor> tensor(2,3,7);
  tensor.setRandom();

  Tensor<float, 3, RowMajor> tensor2 = tensor.swap_layout();
  VERIFY_IS_EQUAL(tensor.dimension(0), tensor2.dimension(2));
  VERIFY_IS_EQUAL(tensor.dimension(1), tensor2.dimension(1));
  VERIFY_IS_EQUAL(tensor.dimension(2), tensor2.dimension(0));

  for (int i = 0; i < 2; ++i) {
    for (int j = 0; j < 3; ++j) {
      for (int k = 0; k < 7; ++k) {
        VERIFY_IS_EQUAL(tensor(i,j,k), tensor2(k,j,i));
      }
    }
  }
}

static void test_swap_as_lvalue()
{
  Tensor<float, 3, ColMajor> tensor(2,3,7);
  tensor.setRandom();

  Tensor<float, 3, RowMajor> tensor2(7,3,2);
  tensor2.swap_layout() = tensor;
  VERIFY_IS_EQUAL(tensor.dimension(0), tensor2.dimension(2));
  VERIFY_IS_EQUAL(tensor.dimension(1), tensor2.dimension(1));
  VERIFY_IS_EQUAL(tensor.dimension(2), tensor2.dimension(0));

  for (int i = 0; i < 2; ++i) {
    for (int j = 0; j < 3; ++j) {
      for (int k = 0; k < 7; ++k) {
        VERIFY_IS_EQUAL(tensor(i,j,k), tensor2(k,j,i));
      }
    }
  }
}

void test_cxx11_tensor_layout_swap()
{
  CALL_SUBTEST(test_simple_swap());
  CALL_SUBTEST(test_swap_as_lvalue());
}

ext: cpp


text:
/*
 * Copyright (c) 2014, Stanislav Vorobiov
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are met:
 *
 * 1. Redistributions of source code must retain the above copyright notice, this
 *    list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright notice,
 *    this list of conditions and the following disclaimer in the documentation
 *    and/or other materials provided with the distribution.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
 * DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR
 * ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */

#include "LevelCompletedComponent.h"
#include "Renderer.h"
#include "Scene.h"
#include "Settings.h"
#include "AssetManager.h"
#include "InputManager.h"
#include "Utils.h"
#include "SequentialTweening.h"
#include <boost/make_shared.hpp>

namespace af
{
    LevelCompletedComponent::LevelCompletedComponent(const std::string& thisMission,
        const std::string& nextMission,
        const std::string& scriptPath,
        const std::string& assetPath,
        int zOrder)
    : UIComponent(zOrder),
      logo_(assetManager.getImage("common1/level_completed.png")),
      itemTime_(0.0f),
      numEntries_(0),
      blackoutDone_(false),
      displayButtons_(false),
      currentItem_(-1),
      tweenTime_(0.0f),
      selectionTimeout_(0.0f),
      finger_(-1),
      fingerItem_(-1),
      scriptPath_(scriptPath),
      assetPath_(assetPath),
      strm_(audio.createStream("theme.ogg")),
      sndHit_(audio.createSound("text_hit.ogg"))
    {
        button_[0] = assetManager.getImage("common1/main_menu.png");
        button_[1] = assetManager.getImage("common1/next_level.png");

        SequentialTweeningPtr tweening = boost::make_shared<SequentialTweening>(true);

        tweening->addTweening(boost::make_shared<SingleTweening>(0.5f, EaseInOutQuad, 0.0f, 1.0f));
        tweening->addTweening(boost::make_shared<SingleTweening>(0.5f, EaseInOutQuad, 1.0f, 0.0f));

        tweening_ = tweening;

        strm_->setLoop(true);

        addEntry("Mission:", thisMission);
        addEntry("Enemies killed:", "--");
        addEntry("Accuracy:", "--%");
        addEntry("Time spent:", "--");
        addEntry("Next mission:", nextMission);
    }

    LevelCompletedComponent::~LevelCompletedComponent()
    {
    }

    void LevelCompletedComponent::accept(ComponentVisitor& visitor)
    {
        visitor.visitUIComponent(shared_from_this());
    }

    void LevelCompletedComponent::update(float dt)
    {
        if (!blackoutDone_) {
            if (stainedGlass_->color() == settings.levelCompleted.blackoutColor) {
                blackoutDone_ = true;
                strm_->play();
            }
            return;
        }

        itemTime_ += dt;

        if (numEntries_ < entries_.size()) {
            if (itemTime_ >= settings.levelCompleted.itemTimeout) {
                itemTime_ = 0.0f;
                ++numEntries_;
                sndHit_->play();
            }
        } else if (numEntries_ == entries_.size()) {
            if (itemTime_ >= settings.levelCompleted.buttonsTimeout) {
                displayButtons_ = true;
                ++numEntries_;
                sndHit_->play();
            }
        }

        if (!displayButtons_) {
            return;
        }

        tweenTime_ += dt;

        if (scene()->inputMenuUI()->havePointer()) {
            b2Vec2 point;
            bool pressed = scene()->inputMenuUI()->pressed(&point);
            bool triggered = scene()->inputMenuUI()->triggered();

            if (finger_ == 0) {
                if (pressed) {
                    if (pointInRectFromCenter(point,
                                              buttonPos_[fingerItem_],
                                              buttonWidth_[fingerItem_],
                                              buttonHeight_[fingerItem_])) {
                        if (currentItem_ < 0) {
                            tweenTime_ = 0.0f;
                        }
                        currentItem_ = fingerItem_;
                    } else {
                        currentItem_ = -1;
                    }
                } else {
                    int ci = currentItem_;
                    currentItem_ = -1;
                    finger_ = -1;
                    fingerItem_ = -1;
                    onPress(ci);
                }
            } else if (triggered) {
                if (pointInRectFromCenter(point,
                                          buttonPos_[0],
                                          buttonWidth_[0],
                                          buttonHeight_[0])) {
                    finger_ = 0;
                    fingerItem_ = currentItem_ = 0;
                    tweenTime_ = 0.0f;
                } else if (pointInRectFromCenter(point,
                                                 buttonPos_[1],
                                                 buttonWidth_[1],
                                                 buttonHeight_[1])) {
                    finger_ = 0;
                    fingerItem_ = currentItem_ = 1;
                    tweenTime_ = 0.0f;
                }
            }
        } else {
            if (currentItem_ == -1) {
                currentItem_ = 1;
            }

            selectionTimeout_ -= dt;
            if (scene()->inputMenuUI()->leftPressed()) {
                if (selectionTimeout_ <= 0.0f) {
                    if (currentItem_-- == 0) {
                        currentItem_ = 1;
                    }
                    selectionTimeout_ = 0.5f;
                    tweenTime_ = 0.0f;
                }
            } else if (scene()->inputMenuUI()->rightPressed()) {
                if (selectionTimeout_ <= 0.0f) {
                    if (++currentItem_ == 2) {
                        currentItem_ = 0;
                    }
                    selectionTimeout_ = 0.5f;
                    tweenTime_ = 0.0f;
                }
            } else if (scene()->inputMenuUI()->okPressed()) {
                onPress(currentItem_);
            } else {
                selectionTimeout_ = 0.0f;
            }
        }
    }

    void LevelCompletedComponent::render()
    {
        if (!blackoutDone_) {
            return;
        }

        renderQuad(logo_,
            b2Vec2(scene()->gameWidth() / 2.0f, scene()->gameHeight() - 2.0f),
            4.0f * logo_.aspect(), 4.0f);

        for (size_t i = 0; i < (std::min)(numEntries_, entries_.size()); ++i) {
            entries_[i].value->render();
            entries_[i].key->render();
        }

        if (displayButtons_) {
            for (int i = 0; i < 2; ++i) {
                float extra = 0.0f;

                if (i == currentItem_) {
                    extra += tweening_->getValue(tweenTime_);
                }

                renderQuad(button_[i], buttonPos_[i],
                           buttonWidth_[i] + (extra * button_[i].aspect()),
                           buttonHeight_[i] + extra);
            }
        }
    }

    void LevelCompletedComponent::onRegister()
    {
        audio.stopAll(settings.levelCompleted.blackoutTime);

        stainedGlass_ = boost::make_shared<StainedGlassComponent>(zOrder() - 1);
        stainedGlass_->setColor(settings.levelCompleted.blackoutColor,
            EaseLinear, settings.levelCompleted.blackoutTime);
        parent()->addComponent(stainedGlass_);

        b2Transform xf(b2Vec2(1.0f, scene()->gameHeight() - 4.0f - settings.levelCompleted.charSize * 1.5f),
            b2Rot(0.0f));

        for (size_t i = 0; i < entries_.size(); ++i) {
            entries_[i].key->setWidth(scene()->gameWidth());
            entries_[i].key->setTransform(xf);
            entries_[i].value->setWidth(scene()->gameWidth());
            entries_[i].value->setTransform(xf);
            xf.p.y -= settings.levelCompleted.charSize * 1.5f;
        }

        buttonHeight_[0] = 3.5f;
        buttonWidth_[0] = buttonHeight_[0] * button_[0].aspect();
        buttonPos_[0] = b2Vec2(buttonWidth_[0] / 2.0f, buttonHeight_[0] / 2.0f);
        buttonPos_[0] += b2Vec2(2.0f, 1.0f);

        buttonHeight_[1] = 3.5f;
        buttonWidth_[1] = buttonHeight_[1] * button_[1].aspect();
        buttonPos_[1] = b2Vec2(buttonWidth_[1] / 2.0f, buttonHeight_[1] / 2.0f);
        buttonPos_[1] += b2Vec2(scene()->gameWidth() - buttonWidth_[1] - 2.0f, 1.0f);
    }

    void LevelCompletedComponent::onUnregister()
    {
    }

    void LevelCompletedComponent::addEntry(const std::string& key, const std::string& value)
    {
        Entry entry;

        entry.key = boost::make_shared<TextArea>();
        entry.key->setCharSize(settings.levelCompleted.charSize);
        entry.key->setColor(settings.levelCompleted.keyColor);
        entry.key->setText(key);

        entry.value = boost::make_shared<TextArea>();
        entry.value->setCharSize(settings.levelCompleted.charSize);
        entry.value->setColor(settings.levelCompleted.valueColor);
        entry.value->setText(key + " " + value);

        entries_.push_back(entry);
    }

    void LevelCompletedComponent::renderQuad(const Image& image, const b2Vec2& pos,
        float width, float height)
    {
        renderer.setProgramDef(image.texture());

        RenderTriangleFan rop = renderer.renderTriangleFan();

        b2Vec2 tmp = pos - b2Vec2(width / 2, height / 2); rop.addVertex(tmp.x, tmp.y);
        tmp = pos + b2Vec2(width / 2, -height / 2); rop.addVertex(tmp.x, tmp.y);
        tmp = pos + b2Vec2(width / 2, height / 2); rop.addVertex(tmp.x, tmp.y);
        tmp = pos + b2Vec2(-width / 2, height / 2); rop.addVertex(tmp.x, tmp.y);

        rop.addTexCoords(image.texCoords(), 6);

        rop.addColors();
    }

    void LevelCompletedComponent::onPress(int i)
    {
        if (i == 0) {
            scene()->setNextLevel("main_menu.lua", "");
        } else if (i == 1) {
            scene()->setNextLevel(scriptPath_, assetPath_);
        }
    }
}

max_stars_repo_name: Sheph/TriggerTime

max_issues_repo_name: Sheph/TriggerTime

max_forks_repo_name: Sheph/TriggerTime


text:
#include "join_sort_merge.hpp"

#include <algorithm>
#include <memory>
#include <optional>
#include <string>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

#include <boost/functional/hash_fwd.hpp>

#include "hyrise.hpp"
#include "join_helper/join_output_writing.hpp"
#include "join_sort_merge/radix_cluster_sort.hpp"
#include "operators/multi_predicate_join/multi_predicate_join_evaluator.hpp"
#include "resolve_type.hpp"
#include "scheduler/abstract_task.hpp"
#include "scheduler/job_task.hpp"
#include "storage/reference_segment.hpp"

namespace opossum {

// TODO(anyone) >> todos and nice-to-haves for the sort-merge join:
//    - outer not-equal join (outer !=)
//    - Bloom filters

bool JoinSortMerge::supports(const JoinConfiguration config) {
  return (config.predicate_condition != PredicateCondition::NotEquals || config.join_mode == JoinMode::Inner) &&
         config.left_data_type == config.right_data_type && config.join_mode != JoinMode::Semi &&
         config.join_mode != JoinMode::AntiNullAsTrue && config.join_mode != JoinMode::AntiNullAsFalse;
}

// The sort merge join performs a join on two input tables on specific join columns. For usage notes, see the
// join_sort_merge.hpp. This is how the join works:
// -> The input tables are materialized and clustered into a specified number of clusters.
//    /utils/radix_cluster_sort.hpp for more info on the clustering phase.
// -> The join is performed per cluster. For the joining phase, runs of entries with the same value are identified
//    and handled at once. If a join-match is identified, the corresponding row_ids are noted for the output.
// -> Using the join result, the output table is built using pos lists referencing the original tables.
JoinSortMerge::JoinSortMerge(const std::shared_ptr<const AbstractOperator>& left,
                             const std::shared_ptr<const AbstractOperator>& right, const JoinMode mode,
                             const OperatorJoinPredicate& primary_predicate,
                             const std::vector<OperatorJoinPredicate>& secondary_predicates)
    : AbstractJoinOperator(OperatorType::JoinSortMerge, left, right, mode, primary_predicate, secondary_predicates,
                           std::make_unique<OperatorPerformanceData<OperatorSteps>>()) {}

std::shared_ptr<AbstractOperator> JoinSortMerge::_on_deep_copy(
    const std::shared_ptr<AbstractOperator>& copied_left_input,
    const std::shared_ptr<AbstractOperator>& copied_right_input,
    std::unordered_map<const AbstractOperator*, std::shared_ptr<AbstractOperator>>& copied_ops) const {
  return std::make_shared<JoinSortMerge>(copied_left_input, copied_right_input, _mode, _primary_predicate,
                                         _secondary_predicates);
}

void JoinSortMerge::_on_set_parameters(const std::unordered_map<ParameterID, AllTypeVariant>& parameters) {}

std::shared_ptr<const Table> JoinSortMerge::_on_execute() {
  Assert(supports({_mode, _primary_predicate.predicate_condition,
                   left_input_table()->column_data_type(_primary_predicate.column_ids.first),
                   right_input_table()->column_data_type(_primary_predicate.column_ids.second),
                   !_secondary_predicates.empty(), left_input_table()->type(), right_input_table()->type()}),
         "JoinSortMerge doesn't support these parameters");

  std::shared_ptr<const Table> left_input_table_ptr = _left_input->get_output();
  std::shared_ptr<const Table> right_input_table_ptr = _right_input->get_output();

  // Check column types
  const auto& left_column_type = left_input_table()->column_data_type(_primary_predicate.column_ids.first);
  DebugAssert(left_column_type == right_input_table()->column_data_type(_primary_predicate.column_ids.second),
              "Left and right column types do not match. The sort merge join requires matching column types");

  // Create implementation to compute the join result
  resolve_data_type(left_column_type, [&](const auto type) {
    using ColumnDataType = typename decltype(type)::type;
    _impl = std::make_unique<JoinSortMergeImpl<ColumnDataType>>(
        *this, left_input_table_ptr, right_input_table_ptr, _primary_predicate.column_ids.first,
        _primary_predicate.column_ids.second, _primary_predicate.predicate_condition, _mode, _secondary_predicates,
        dynamic_cast<OperatorPerformanceData<JoinSortMerge::OperatorSteps>&>(*performance_data));
  });

  return _impl->_on_execute();
}

void JoinSortMerge::_on_cleanup() { _impl.reset(); }

const std::string& JoinSortMerge::name() const {
  static const auto name = std::string{"JoinSortMerge"};
  return name;
}

template <typename T>
class JoinSortMerge::JoinSortMergeImpl : public AbstractReadOnlyOperatorImpl {
 public:
  JoinSortMergeImpl<T>(JoinSortMerge& sort_merge_join, const std::shared_ptr<const Table>& left_input_table,
                       const std::shared_ptr<const Table>& right_input_table, ColumnID left_column_id,
                       ColumnID right_column_id, const PredicateCondition op, JoinMode mode,
                       const std::vector<OperatorJoinPredicate>& secondary_join_predicates,
                       OperatorPerformanceData<JoinSortMerge::OperatorSteps>& performance_data)
      : _sort_merge_join{sort_merge_join},
        _left_input_table{left_input_table},
        _right_input_table{right_input_table},
        _performance{performance_data},
        _primary_left_column_id{left_column_id},
        _primary_right_column_id{right_column_id},
        _primary_predicate_condition{op},
        _mode{mode},
        _secondary_join_predicates{secondary_join_predicates} {
    _cluster_count = _determine_number_of_clusters();
    _output_pos_lists_left.resize(_cluster_count);
    _output_pos_lists_right.resize(_cluster_count);
  }

 protected:
  JoinSortMerge& _sort_merge_join;
  const std::shared_ptr<const Table> _left_input_table, _right_input_table;

  OperatorPerformanceData<JoinSortMerge::OperatorSteps>& _performance;

  // Contains the materialized sorted input tables
  MaterializedSegmentList<T> _sorted_left_table;
  MaterializedSegmentList<T> _sorted_right_table;

  // Contains the null value row ids if a join column is an outer join column
  RowIDPosList _null_rows_left;
  RowIDPosList _null_rows_right;

  const ColumnID _primary_left_column_id;
  const ColumnID _primary_right_column_id;

  const PredicateCondition _primary_predicate_condition;
  const JoinMode _mode;

  const std::vector<OperatorJoinPredicate>& _secondary_join_predicates;

  // The cluster count must be a power of two, i.e. 1, 2, 4, 8, 16, ...
  size_t _cluster_count;

  // Contains the output row ids for each cluster
  std::vector<RowIDPosList> _output_pos_lists_left;
  std::vector<RowIDPosList> _output_pos_lists_right;

  struct RowHasher {
    size_t operator()(const RowID& row) const {
      auto seed = size_t{0};
      boost::hash_combine(seed, row.chunk_id);
      boost::hash_combine(seed, row.chunk_offset);
      return seed;
    }
  };

  using RowHashSet = std::unordered_set<RowID, RowHasher>;

  // These are used for outer joins with multiple predicates where the primary predicate is not equals.
  RowHashSet _left_row_ids_emitted{};
  RowHashSet _right_row_ids_emitted{};

  std::vector<RowHashSet> _left_row_ids_emitted_per_chunk;
  std::vector<RowHashSet> _right_row_ids_emitted_per_chunk;

  // The TablePosition is a utility struct that is used to define a specific position in a sorted input table.
  struct TableRange;
  struct TablePosition {
    TablePosition() = default;
    TablePosition(size_t init_cluster, size_t init_index) : cluster{init_cluster}, index{init_index} {}

    size_t cluster;
    size_t index;

    TableRange to(TablePosition position) { return TableRange(*this, position); }
  };

  TablePosition _end_of_left_table;
  TablePosition _end_of_right_table;

  // The TableRange is a utility struct that is used to define ranges of rows in a sorted input table spanning from
  // a start position to an end position.
  struct TableRange {
    TableRange(TablePosition start_position, TablePosition end_position) : start(start_position), end(end_position) {}
    TableRange(size_t cluster, size_t start_index, size_t end_index)
        : start{TablePosition(cluster, start_index)}, end{TablePosition(cluster, end_index)} {}

    TablePosition start;
    TablePosition end;

    // Executes the given action for every row id of the table in this range.
    template <typename F>
    void for_every_row_id(const MaterializedSegmentList<T>& table, const F& action) {
// False positive with gcc and tsan (https://gcc.gnu.org/bugzilla/show_bug.cgi?id=92194)
#pragma GCC diagnostic push
#pragma GCC diagnostic ignored "-Wmaybe-uninitialized"
      for (auto cluster = start.cluster; cluster <= end.cluster; ++cluster) {
        const auto start_index = (cluster == start.cluster) ? start.index : 0;
        const auto end_index = (cluster == end.cluster) ? end.index : table[cluster].size();
        for (auto index = start_index; index < end_index; ++index) {
          action(table[cluster][index].row_id);
        }
      }
#pragma GCC diagnostic pop
    }
  };

  // Determines the number of clusters to be used for the join. The number of clusters must be a power of two.
  size_t _determine_number_of_clusters() {
    // We try to have a partition size of roughly 256 KB to avoid out-of-L2 cache sorts. This value has been determined
    // by an array of benchmarks. Ideally, it would incorporate hardware knowledge such as the L2 cache size.
    const auto max_sort_items_count = 256'000 / sizeof(T);
    const size_t cluster_count_left = _sort_merge_join.left_input_table()->row_count() / max_sort_items_count;
    const size_t cluster_count_right = _sort_merge_join.right_input_table()->row_count() / max_sort_items_count;

    // Return the next larger power of two for the larger of the two cluster counts.
    return static_cast<size_t>(
        std::pow(2, std::floor(std::log2(std::max({size_t{1}, cluster_count_left, cluster_count_right})))));
  }

  // Gets the table position corresponding to the end of the table, i.e. the last entry of the last cluster.
  static TablePosition _end_of_table(const MaterializedSegmentList<T>& table) {
    DebugAssert(!table.empty(), "table has no chunks");
    auto last_cluster = table.size() - 1;
    return TablePosition(last_cluster, table[last_cluster].size());
  }

  // Represents the result of a value comparison.
  enum class CompareResult { Less, Greater, Equal };

  // Performs the join for two runs of a specified cluster.
  // A run is a series of rows in a cluster with the same value.
  void _join_runs(TableRange left_run, TableRange right_run, CompareResult compare_result,
                  std::optional<MultiPredicateJoinEvaluator>& multi_predicate_join_evaluator, const size_t cluster_id) {
    switch (_primary_predicate_condition) {
      case PredicateCondition::Equals:
        if (compare_result == CompareResult::Equal) {
          _emit_qualified_combinations(cluster_id, left_run, right_run, multi_predicate_join_evaluator);
        } else if (compare_result == CompareResult::Less) {
          if (_mode == JoinMode::Left || _mode == JoinMode::FullOuter) {
            _emit_right_primary_null_combinations(cluster_id, left_run);
          }
        } else if (compare_result == CompareResult::Greater) {
          if (_mode == JoinMode::Right || _mode == JoinMode::FullOuter) {
            _emit_left_primary_null_combinations(cluster_id, right_run);
          }
        }
        break;
      case PredicateCondition::NotEquals:
        if (compare_result == CompareResult::Greater) {
          _emit_qualified_combinations(cluster_id, left_run.start.to(_end_of_left_table), right_run,
                                       multi_predicate_join_evaluator);
        } else if (compare_result == CompareResult::Equal) {
          _emit_qualified_combinations(cluster_id, left_run.end.to(_end_of_left_table), right_run,
                                       multi_predicate_join_evaluator);
          _emit_qualified_combinations(cluster_id, left_run, right_run.end.to(_end_of_right_table),
                                       multi_predicate_join_evaluator);
        } else if (compare_result == CompareResult::Less) {
          _emit_qualified_combinations(cluster_id, left_run, right_run.start.to(_end_of_right_table),
                                       multi_predicate_join_evaluator);
        }
        break;
      case PredicateCondition::GreaterThan:
        if (compare_result == CompareResult::Greater) {
          _emit_qualified_combinations(cluster_id, left_run.start.to(_end_of_left_table), right_run,
                                       multi_predicate_join_evaluator);
        } else if (compare_result == CompareResult::Equal) {
          _emit_qualified_combinations(cluster_id, left_run.end.to(_end_of_left_table), right_run,
                                       multi_predicate_join_evaluator);
        }
        break;
      case PredicateCondition::GreaterThanEquals:
        if (compare_result == CompareResult::Greater || compare_result == CompareResult::Equal) {
          _emit_qualified_combinations(cluster_id, left_run.start.to(_end_of_left_table), right_run,
                                       multi_predicate_join_evaluator);
        }
        break;
      case PredicateCondition::LessThan:
        if (compare_result == CompareResult::Less) {
          _emit_qualified_combinations(cluster_id, left_run, right_run.start.to(_end_of_right_table),
                                       multi_predicate_join_evaluator);
        } else if (compare_result == CompareResult::Equal) {
          _emit_qualified_combinations(cluster_id, left_run, right_run.end.to(_end_of_right_table),
                                       multi_predicate_join_evaluator);
        }
        break;
      case PredicateCondition::LessThanEquals:
        if (compare_result == CompareResult::Less || compare_result == CompareResult::Equal) {
          _emit_qualified_combinations(cluster_id, left_run, right_run.start.to(_end_of_right_table),
                                       multi_predicate_join_evaluator);
        }
        break;
      default:
        throw std::logic_error("Unknown PredicateCondition");
    }
  }

  // Emits a combination of a left row id and a right row id to the join output.
  void _emit_combination(size_t output_cluster, RowID left_row_id, RowID right_row_id) {
    _output_pos_lists_left[output_cluster].push_back(left_row_id);
    _output_pos_lists_right[output_cluster].push_back(right_row_id);
  }

  // Emits all the combinations of row ids from the left table range and the right table range to the join output
  // where also the secondary predicates are satisfied.
  void _emit_qualified_combinations(size_t output_cluster, TableRange left_range, TableRange right_range,
                                    std::optional<MultiPredicateJoinEvaluator>& multi_predicate_join_evaluator) {
    if (multi_predicate_join_evaluator) {
      if (_mode == JoinMode::Inner) {
        _emit_combinations_multi_predicated_inner(output_cluster, left_range, right_range,
                                                  *multi_predicate_join_evaluator);
      } else if (_mode == JoinMode::Left) {
        _emit_combinations_multi_predicated_left_outer(output_cluster, left_range, right_range,
                                                       *multi_predicate_join_evaluator);
      } else if (_mode == JoinMode::Right) {
        _emit_combinations_multi_predicated_right_outer(output_cluster, left_range, right_range,
                                                        *multi_predicate_join_evaluator);
      } else if (_mode == JoinMode::FullOuter) {
        _emit_combinations_multi_predicated_full_outer(output_cluster, left_range, right_range,
                                                       *multi_predicate_join_evaluator);
      }
    } else {
      // no secondary join predicates
      left_range.for_every_row_id(_sorted_left_table, [&](RowID left_row_id) {
        right_range.for_every_row_id(_sorted_right_table, [&](RowID right_row_id) {
          _emit_combination(output_cluster, left_row_id, right_row_id);
        });
      });
    }
  }

  // Only for multi predicated inner joins.
  // Emits all the combinations of row ids from the left table range and the right table range to the join output
  // where the secondary predicates are satisfied.
  void _emit_combinations_multi_predicated_inner(size_t output_cluster, TableRange left_range, TableRange right_range,
                                                 MultiPredicateJoinEvaluator& multi_predicate_join_evaluator) {
    left_range.for_every_row_id(_sorted_left_table, [&](RowID left_row_id) {
      right_range.for_every_row_id(_sorted_right_table, [&](RowID right_row_id) {
        if (multi_predicate_join_evaluator.satisfies_all_predicates(left_row_id, right_row_id)) {
          _emit_combination(output_cluster, left_row_id, right_row_id);
        }
      });
    });
  }

  // Only for multi predicated left outer joins.
  // Emits all the combinations of row ids from the left table range and the right table range to the join output
  // where the secondary predicates are satisfied.
  // For a left row id without a match, the combination [left row id|NULL row id] is emitted.
  void _emit_combinations_multi_predicated_left_outer(size_t output_cluster, TableRange left_range,
                                                      TableRange right_range,
                                                      MultiPredicateJoinEvaluator& multi_predicate_join_evaluator) {
    if (_primary_predicate_condition == PredicateCondition::Equals) {
      left_range.for_every_row_id(_sorted_left_table, [&](RowID left_row_id) {
        bool left_row_id_matched = false;
        right_range.for_every_row_id(_sorted_right_table, [&](RowID right_row_id) {
          if (multi_predicate_join_evaluator.satisfies_all_predicates(left_row_id, right_row_id)) {
            _emit_combination(output_cluster, left_row_id, right_row_id);
            left_row_id_matched = true;
          }
        });
        if (!left_row_id_matched) {
          _emit_combination(output_cluster, left_row_id, NULL_ROW_ID);
        }
      });
    } else {
      // primary predicate is <, <=, >, or >=
      left_range.for_every_row_id(_sorted_left_table, [&](RowID left_row_id) {
        right_range.for_every_row_id(_sorted_right_table, [&](RowID right_row_id) {
          if (multi_predicate_join_evaluator.satisfies_all_predicates(left_row_id, right_row_id)) {
            _emit_combination(output_cluster, left_row_id, right_row_id);
            _left_row_ids_emitted_per_chunk[output_cluster].emplace(left_row_id);
          }
        });
      });
    }
  }

  // Only for multi predicated right outer joins.
  // Emits all the combinations of row ids from the left table range and the right table range to the join output
  // where the secondary predicates are satisfied.
  // For a right row id without a match, the combination [NULL row id|right row id] is emitted.
  void _emit_combinations_multi_predicated_right_outer(size_t output_cluster, TableRange left_range,
                                                       TableRange right_range,
                                                       MultiPredicateJoinEvaluator& multi_predicate_join_evaluator) {
    if (_primary_predicate_condition == PredicateCondition::Equals) {
      right_range.for_every_row_id(_sorted_right_table, [&](RowID right_row_id) {
        bool right_row_id_matched = false;
        left_range.for_every_row_id(_sorted_left_table, [&](RowID left_row_id) {
          if (multi_predicate_join_evaluator.satisfies_all_predicates(left_row_id, right_row_id)) {
            _emit_combination(output_cluster, left_row_id, right_row_id);
            right_row_id_matched = true;
          }
        });
        if (!right_row_id_matched) {
          _emit_combination(output_cluster, NULL_ROW_ID, right_row_id);
        }
      });
    } else {
      // primary predicate is <, <=, >, or >=
      right_range.for_every_row_id(_sorted_right_table, [&](RowID right_row_id) {
        left_range.for_every_row_id(_sorted_left_table, [&](RowID left_row_id) {
          if (multi_predicate_join_evaluator.satisfies_all_predicates(left_row_id, right_row_id)) {
            _emit_combination(output_cluster, left_row_id, right_row_id);
            _right_row_ids_emitted_per_chunk[output_cluster].emplace(right_row_id);
          }
        });
      });
    }
  }

  // Only for multi-predicate full outer joins.
  // Emits all the combinations of row ids from the left table range and the right table range to the join output
  // where the secondary predicates are satisfied.
  // For a left row id without a match, the combination [right row id|NULL row id] is emitted.
  // For a right row id without a match, the combination [NULL row id|right row id] is emitted.
  void _emit_combinations_multi_predicated_full_outer(size_t output_cluster, TableRange left_range,
                                                      TableRange right_range,
                                                      MultiPredicateJoinEvaluator& multi_predicate_join_evaluator) {
    if (_primary_predicate_condition == PredicateCondition::Equals) {
      std::set<RowID> matched_right_row_ids;

      left_range.for_every_row_id(_sorted_left_table, [&](RowID left_row_id) {
        bool left_row_id_matched = false;
        right_range.for_every_row_id(_sorted_right_table, [&](RowID right_row_id) {
          if (multi_predicate_join_evaluator.satisfies_all_predicates(left_row_id, right_row_id)) {
            _emit_combination(output_cluster, left_row_id, right_row_id);
            left_row_id_matched = true;
            matched_right_row_ids.insert(right_row_id);
          }
        });
        if (!left_row_id_matched) {
          _emit_combination(output_cluster, left_row_id, NULL_ROW_ID);
        }
      });
      // add null value combinations for right row ids that have no match.
      right_range.for_every_row_id(_sorted_right_table, [&](RowID right_row_id) {
        // right_row_ids_with_match has no key `right_row_id`
        if (matched_right_row_ids.count(right_row_id) == 0) {
          _emit_combination(output_cluster, NULL_ROW_ID, right_row_id);
        }
      });
    } else {
      left_range.for_every_row_id(_sorted_left_table, [&](RowID left_row_id) {
        right_range.for_every_row_id(_sorted_right_table, [&](RowID right_row_id) {
          if (multi_predicate_join_evaluator.satisfies_all_predicates(left_row_id, right_row_id)) {
            _emit_combination(output_cluster, left_row_id, right_row_id);
            _left_row_ids_emitted_per_chunk[output_cluster].emplace(left_row_id);
            _right_row_ids_emitted_per_chunk[output_cluster].emplace(right_row_id);
          }
        });
      });
    }
  }

  // Emits all combinations of row ids from the left table range and a NULL value on the right side
  // (regarding the primary predicate) to the join output.
  void _emit_right_primary_null_combinations(size_t output_cluster, TableRange left_range) {
    left_range.for_every_row_id(
        _sorted_left_table, [&](RowID left_row_id) { _emit_combination(output_cluster, left_row_id, NULL_ROW_ID); });
  }

  // Emits all combinations of row ids from the right table range and a NULL value on the left side
  // (regarding the primary predicate) to the join output.
  void _emit_left_primary_null_combinations(size_t output_cluster, TableRange right_range) {
    right_range.for_every_row_id(
        _sorted_right_table, [&](RowID right_row_id) { _emit_combination(output_cluster, NULL_ROW_ID, right_row_id); });
  }

  // Determines the length of the run starting at start_index in the values vector. A run is a series of the same
  // value. Even though the input vector is sorted, we first start by linearly scanning for the end of the run. The
  // reason is that we know with a high probability that the item we are looking for is at the beginning of the input
  // vector (the run value is the first in the sequence and the sequence is sorted). If we do not find the run's end
  // within the linearly scanned part, we use a binary search. An unsuccessful linear search should come with
  // neglectable costs as we will iterate over the values anyways.
  size_t _run_length(size_t start_index, const MaterializedSegment<T>& values) {
    if (start_index >= values.size()) {
      return 0;
    }

    const auto begin = values.begin() + start_index;
    const auto run_value = begin->value;

    constexpr auto LINEAR_SEARCH_ITEMS = size_t{128};
    auto end = begin + LINEAR_SEARCH_ITEMS;
    if (start_index + LINEAR_SEARCH_ITEMS >= values.size()) {
      // Set end of linear search to end of input vector if we would overshoot otherwise.
      end = values.end();
    }

    const auto linear_search_result = std::find_if(begin, end, [&](const auto& v) { return v.value > run_value; });
    if (linear_search_result != end) {
      // Match found within the linearly scanned part.
      return std::distance(begin, linear_search_result);
    }

    if (linear_search_result == values.end()) {
      // We did not find a larger value in the linearly scanned part and it spanned until the end of the input vector.
      // That means all values up to the end are part of the run.
      return std::distance(begin, end);
    }

    // Binary search in case the run did not end within the linearly scanned part.
    const auto binary_search_result = std::upper_bound(
        end, values.end(), *end, [](const auto& lhs, const auto& rhs) { return lhs.value < rhs.value; });
    return std::distance(begin, binary_search_result);
  }

  // Compares two values and creates a comparison result.
  CompareResult _compare(const T& left, const T& right) {
    if (left < right) {
      return CompareResult::Less;
    } else if (left == right) {
      return CompareResult::Equal;
    } else {
      return CompareResult::Greater;
    }
  }

  // Performs the join on a single cluster. Runs of entries with the same value are identified and handled together.
  // This constitutes the merge phase of the join. The output combinations of row ids are determined by _join_runs.
  void _join_cluster(const size_t cluster_id,
                     std::optional<MultiPredicateJoinEvaluator>& multi_predicate_join_evaluator) {
    const auto& left_cluster = _sorted_left_table[cluster_id];
    const auto& right_cluster = _sorted_right_table[cluster_id];

    auto left_run_start = size_t{0};
    auto right_run_start = size_t{0};

    auto left_run_end = left_run_start + _run_length(left_run_start, left_cluster);
    auto right_run_end = right_run_start + _run_length(right_run_start, right_cluster);

    const auto left_size = left_cluster.size();
    const auto right_size = right_cluster.size();

    while (left_run_start < left_size && right_run_start < right_size) {
      const auto& left_value = left_cluster[left_run_start].value;
      const auto& right_value = right_cluster[right_run_start].value;

      const auto compare_result = _compare(left_value, right_value);

      TableRange left_run(cluster_id, left_run_start, left_run_end);
      TableRange right_run(cluster_id, right_run_start, right_run_end);
      _join_runs(left_run, right_run, compare_result, multi_predicate_join_evaluator, cluster_id);

      // Advance to the next run on the smaller side or both if equal
      switch (compare_result) {
        case CompareResult::Equal:
          // Advance both runs
          left_run_start = left_run_end;
          right_run_start = right_run_end;
          left_run_end = left_run_start + _run_length(left_run_start, left_cluster);
          right_run_end = right_run_start + _run_length(right_run_start, right_cluster);
          break;
        case CompareResult::Less:
          // Advance the left run
          left_run_start = left_run_end;
          left_run_end = left_run_start + _run_length(left_run_start, left_cluster);
          break;
        case CompareResult::Greater:
          // Advance the right run
          right_run_start = right_run_end;
          right_run_end = right_run_start + _run_length(right_run_start, right_cluster);
          break;
        default:
          throw std::logic_error("Unknown CompareResult");
      }
    }

    // Join the rest of the unfinished side, which is relevant for outer joins and non-equi joins
    const auto right_rest = TableRange(cluster_id, right_run_start, right_size);
    const auto left_rest = TableRange(cluster_id, left_run_start, left_size);
    if (left_run_start < left_size) {
      _join_runs(left_rest, right_rest, CompareResult::Less, multi_predicate_join_evaluator, cluster_id);
    } else if (right_run_start < right_size) {
      _join_runs(left_rest, right_rest, CompareResult::Greater, multi_predicate_join_evaluator, cluster_id);
    }
  }

  // Determines the smallest value in a sorted materialized table.
  const T& _table_min_value(const MaterializedSegmentList<T>& sorted_table) {
    DebugAssert(_primary_predicate_condition != PredicateCondition::Equals,
                "Complete table order is required for _table_min_value() which is only available in the non-equi case");
    DebugAssert(!sorted_table.empty(), "Sorted table has no partitions");

    for (const auto& partition : sorted_table) {
      if (!partition.empty()) {
        return partition[0].value;
      }
    }

    Fail("Every partition is empty");
  }

  // Determines the largest value in a sorted materialized table.
  const T& _table_max_value(const MaterializedSegmentList<T>& sorted_table) {
    DebugAssert(_primary_predicate_condition != PredicateCondition::Equals,
                "The table needs to be sorted for _table_max_value() which is only the case for non-equi joins");
    DebugAssert(!sorted_table.empty(), "Sorted table is empty");

    for (auto partition_iter = sorted_table.rbegin(); partition_iter != sorted_table.rend(); ++partition_iter) {
      if (!partition_iter->empty()) {
        return partition_iter->back().value;
      }
    }

    Fail("Every partition is empty");
  }

  // Looks for the first value in a sorted materialized table that fulfills the specified condition.
  // Returns the TablePosition of this element and whether a satisfying element has been found.
  template <typename Function>
  std::optional<TablePosition> _first_value_that_satisfies(const MaterializedSegmentList<T>& sorted_table,
                                                           const Function& condition) {
    const auto sorted_table_size = sorted_table.size();
    for (auto partition_id = size_t{0}; partition_id < sorted_table_size; ++partition_id) {
      const auto& partition = sorted_table[partition_id];
      if (!partition.empty() && condition(partition.back().value)) {
        const auto partition_size = partition.size();
        for (auto index = size_t{0}; index < partition_size; ++index) {
          if (condition(partition[index].value)) {
            return TablePosition(partition_id, index);
          }
        }
      }
    }

    return {};
  }

  // Looks for the first value in a sorted materialized table that fulfills the specified condition, but searches
  // the table in reverse order. Returns the TablePosition of this element, and a satisfying element has been found.
  template <typename Function>
  std::optional<TablePosition> _first_value_that_satisfies_reverse(const MaterializedSegmentList<T>& sorted_table,
                                                                   const Function& condition) {
    const auto sorted_table_size = sorted_table.size();
    for (auto partition_id = static_cast<int64_t>(sorted_table_size - 1); partition_id >= 0; --partition_id) {
      const auto& partition = sorted_table[partition_id];
      if (!partition.empty() && condition(partition[0].value)) {
        const auto partition_size = partition.size();
        for (auto index = static_cast<int64_t>(partition_size - 1); index >= 0; --index) {
          if (condition(partition[index].value)) {
            return TablePosition(partition_id, index + 1);
          }
        }
      }
    }

    return {};
  }

  // Adds the rows without matches for right outer joins for non-equi operators (<, <=, >, >=).
  // This method adds those rows from the right table to the output that do not find a join partner.
  // The outer join for the equality operator is handled in _join_runs instead.
  void _right_outer_non_equi_join() {
    auto end_of_right_table = _end_of_table(_sorted_right_table);

    if (_sort_merge_join.left_input_table()->row_count() == 0) {
      _emit_left_primary_null_combinations(0, TablePosition(0, 0).to(end_of_right_table));
      return;
    }

    const auto& left_min_value = _table_min_value(_sorted_left_table);
    const auto& left_max_value = _table_max_value(_sorted_left_table);

    auto unmatched_range = std::optional<TableRange>{};

    if (_primary_predicate_condition == PredicateCondition::LessThan) {
      // Look for the first right value that is bigger than the smallest left value.
      auto result =
          _first_value_that_satisfies(_sorted_right_table, [&](const T& value) { return value > left_min_value; });
      if (result) {
        unmatched_range = TablePosition(0, 0).to(*result);
      }
    } else if (_primary_predicate_condition == PredicateCondition::LessThanEquals) {
      // Look for the first right value that is bigger or equal to the smallest left value.
      auto result =
          _first_value_that_satisfies(_sorted_right_table, [&](const T& value) { return value >= left_min_value; });
      if (result) {
        unmatched_range = TablePosition(0, 0).to(*result);
      }
    } else if (_primary_predicate_condition == PredicateCondition::GreaterThan) {
      // Look for the first right value that is smaller than the biggest left value.
      auto result = _first_value_that_satisfies_reverse(_sorted_right_table,
                                                        [&](const T& value) { return value < left_max_value; });
      if (result) {
        unmatched_range = (*result).to(end_of_right_table);
      }
    } else if (_primary_predicate_condition == PredicateCondition::GreaterThanEquals) {
      // Look for the first right value that is smaller or equal to the biggest left value.
      auto result = _first_value_that_satisfies_reverse(_sorted_right_table,
                                                        [&](const T& value) { return value <= left_max_value; });
      if (result) {
        unmatched_range = (*result).to(end_of_right_table);
      }
    }

    if (unmatched_range) {
      _emit_left_primary_null_combinations(0, *unmatched_range);
      unmatched_range->for_every_row_id(_sorted_right_table, [&](RowID right_row_id) {
        // Mark as emitted so that it doesn't get emitted again below
        _right_row_ids_emitted.emplace(right_row_id);
      });
    }

    // Add null-combinations for right row ids where the primary predicate was satisfied but the
    // secondary predicates were not.
    if (!_secondary_join_predicates.empty()) {
      for (const auto& cluster : _sorted_right_table) {
        for (const auto& row : cluster) {
          if (!_right_row_ids_emitted.contains(row.row_id)) {
            _emit_combination(0, NULL_ROW_ID, row.row_id);
          }
        }
      }
    }
  }

  // Adds the rows without matches for left outer joins for non-equi operators (<, <=, >, >=).
  // This method adds those rows from the left table to the output that do not find a join partner.
  // The outer join for the equality operator is handled in _join_runs instead.
  void _left_outer_non_equi_join() {
    auto end_of_left_table = _end_of_table(_sorted_left_table);

    if (_sort_merge_join.right_input_table()->row_count() == 0) {
      _emit_right_primary_null_combinations(0, TablePosition(0, 0).to(end_of_left_table));
      return;
    }

    const auto& right_min_value = _table_min_value(_sorted_right_table);
    const auto& right_max_value = _table_max_value(_sorted_right_table);

    auto unmatched_range = std::optional<TableRange>{};

    if (_primary_predicate_condition == PredicateCondition::LessThan) {
      // Look for the last left value that is smaller than the biggest right value.
      auto result = _first_value_that_satisfies_reverse(_sorted_left_table,
                                                        [&](const T& value) { return value < right_max_value; });
      if (result) {
        unmatched_range = (*result).to(end_of_left_table);
      }
    } else if (_primary_predicate_condition == PredicateCondition::LessThanEquals) {
      // Look for the last left value that is smaller or equal than the biggest right value.
      auto result = _first_value_that_satisfies_reverse(_sorted_left_table,
                                                        [&](const T& value) { return value <= right_max_value; });
      if (result) {
        unmatched_range = (*result).to(end_of_left_table);
      }
    } else if (_primary_predicate_condition == PredicateCondition::GreaterThan) {
      // Look for the first left value that is bigger than the smallest right value.
      auto result =
          _first_value_that_satisfies(_sorted_left_table, [&](const T& value) { return value > right_min_value; });
      if (result) {
        unmatched_range = TablePosition(0, 0).to(*result);
      }
    } else if (_primary_predicate_condition == PredicateCondition::GreaterThanEquals) {
      // Look for the first left value that is bigger or equal to the smallest right value.
      auto result =
          _first_value_that_satisfies(_sorted_left_table, [&](const T& value) { return value >= right_min_value; });
      if (result) {
        unmatched_range = TablePosition(0, 0).to(*result);
      }
    }

    if (unmatched_range) {
      _emit_right_primary_null_combinations(0, *unmatched_range);
      unmatched_range->for_every_row_id(_sorted_left_table, [&](RowID left_row_id) {
        // Mark as emitted so that it doesn't get emitted again below
        _left_row_ids_emitted.emplace(left_row_id);
      });
    }

    // Add null-combinations for left row ids where the primary predicate was satisfied but the
    // secondary predicates were not.
    if (!_secondary_join_predicates.empty()) {
      for (const auto& cluster : _sorted_left_table) {
        for (const auto& row : cluster) {
          if (!_left_row_ids_emitted.contains(row.row_id)) {
            _emit_combination(0, row.row_id, NULL_ROW_ID);
          }
        }
      }
    }
  }

  // Performs the join on all clusters in parallel.
  void _perform_join() {
    auto jobs = std::vector<std::shared_ptr<AbstractTask>>{};
    _left_row_ids_emitted_per_chunk.resize(_cluster_count);
    _right_row_ids_emitted_per_chunk.resize(_cluster_count);

    // Parallel join for each cluster
    for (auto cluster_id = size_t{0}; cluster_id < _cluster_count; ++cluster_id) {
      // Create output position lists
      _output_pos_lists_left[cluster_id] = RowIDPosList{};
      _output_pos_lists_right[cluster_id] = RowIDPosList{};

      // Avoid empty jobs for inner equi joins
      if (_mode == JoinMode::Inner && _primary_predicate_condition == PredicateCondition::Equals) {
        if (_sorted_left_table[cluster_id].empty() || _sorted_right_table[cluster_id].empty()) {
          continue;
        }
      }

      _left_row_ids_emitted_per_chunk[cluster_id] = RowHashSet{};
      _right_row_ids_emitted_per_chunk[cluster_id] = RowHashSet{};

      const auto merge_row_count = _sorted_left_table[cluster_id].size() + _sorted_right_table[cluster_id].size();
      const auto join_cluster_task = [this, cluster_id] {
        // Accessors are not thread-safe, so we create one evaluator per job
        std::optional<MultiPredicateJoinEvaluator> multi_predicate_join_evaluator;
        if (!_secondary_join_predicates.empty()) {
          multi_predicate_join_evaluator.emplace(*_sort_merge_join._left_input->get_output(),
                                                 *_sort_merge_join.right_input()->get_output(), _mode,
                                                 _secondary_join_predicates);
        }

        this->_join_cluster(cluster_id, multi_predicate_join_evaluator);
      };

      if (merge_row_count > JOB_SPAWN_THRESHOLD) {
        jobs.push_back(std::make_shared<JobTask>(join_cluster_task));
      } else {
        join_cluster_task();
      }
    }

    Hyrise::get().scheduler()->schedule_and_wait_for_tasks(jobs);

    // The outer joins for the non-equi cases
    // Note: Equi outer joins can be integrated into the main algorithm, while these can not.
    if ((_mode == JoinMode::Left || _mode == JoinMode::FullOuter) &&
        _primary_predicate_condition != PredicateCondition::Equals) {
      for (auto& set : _left_row_ids_emitted_per_chunk) {
        _left_row_ids_emitted.merge(set);
      }

      _left_outer_non_equi_join();
    }
    if ((_mode == JoinMode::Right || _mode == JoinMode::FullOuter) &&
        _primary_predicate_condition != PredicateCondition::Equals) {
      for (auto& set : _right_row_ids_emitted_per_chunk) {
        _right_row_ids_emitted.merge(set);
      }
      _right_outer_non_equi_join();
    }
  }

 public:
  std::shared_ptr<const Table> _on_execute() override {
    const auto include_null_left = (_mode == JoinMode::Left || _mode == JoinMode::FullOuter);
    const auto include_null_right = (_mode == JoinMode::Right || _mode == JoinMode::FullOuter);
    auto radix_clusterer = RadixClusterSort<T>(
        _sort_merge_join.left_input_table(), _sort_merge_join.right_input_table(),
        _sort_merge_join._primary_predicate.column_ids, _primary_predicate_condition == PredicateCondition::Equals,
        include_null_left, include_null_right, _cluster_count, _performance);
    // Sort and cluster the input tables
    auto sort_output = radix_clusterer.execute();
    _sorted_left_table = std::move(sort_output.clusters_left);
    _sorted_right_table = std::move(sort_output.clusters_right);
    _null_rows_left = std::move(sort_output.null_rows_left);
    _null_rows_right = std::move(sort_output.null_rows_right);
    _end_of_left_table = _end_of_table(_sorted_left_table);
    _end_of_right_table = _end_of_table(_sorted_right_table);

    Timer timer;

    _perform_join();

    if (include_null_left || include_null_right) {
      auto null_output_left = RowIDPosList();
      auto null_output_right = RowIDPosList();

      // Add the outer join rows which had a null value in their join column
      if (include_null_left) {
        null_output_left.reserve(_null_rows_left.size());
        null_output_right.insert(null_output_right.end(), _null_rows_left.size(), NULL_ROW_ID);
        for (const auto& row_id_left : _null_rows_left) {
          null_output_left.push_back(row_id_left);
        }
      }
      if (include_null_right) {
        null_output_left.insert(null_output_left.end(), _null_rows_right.size(), NULL_ROW_ID);
        null_output_right.reserve(_null_rows_right.size());
        for (const auto& row_id_right : _null_rows_right) {
          null_output_right.push_back(row_id_right);
        }
      }

      DebugAssert(null_output_left.size() == null_output_right.size(),
                  "Null positions lists are expected to be of equal length.");
      if (!null_output_left.empty()) {
        _output_pos_lists_left.push_back(std::move(null_output_left));
        _output_pos_lists_right.push_back(std::move(null_output_right));
      }
    }
    _performance.set_step_runtime(OperatorSteps::Merging, timer.lap());

    const auto create_left_side_pos_lists_by_segment = (_left_input_table->type() == TableType::References);
    const auto create_right_side_pos_lists_by_segment = (_right_input_table->type() == TableType::References);

    // A sort merge join's input can be heavily pre-filtered or the join results in very few matches. In contrast to
    // the hash join, we do not (for now) merge small partitions to keep the sorted chunk guarantees, which could be
    // exploited by subsequent operators.
    constexpr auto ALLOW_PARTITION_MERGE = false;
    auto output_chunks =
        write_output_chunks(_output_pos_lists_left, _output_pos_lists_right, _left_input_table, _right_input_table,
                            create_left_side_pos_lists_by_segment, create_right_side_pos_lists_by_segment,
                            OutputColumnOrder::LeftFirstRightSecond, ALLOW_PARTITION_MERGE);

    const ColumnID left_join_column = _sort_merge_join._primary_predicate.column_ids.first;
    const ColumnID right_join_column = static_cast<ColumnID>(_sort_merge_join.left_input_table()->column_count() +
                                                             _sort_merge_join._primary_predicate.column_ids.second);

    for (auto& chunk : output_chunks) {
      if (_sort_merge_join._primary_predicate.predicate_condition == PredicateCondition::Equals &&
          _mode == JoinMode::Inner) {
        chunk->finalize();
        // The join columns are sorted in ascending order (ensured by radix_cluster_sort)
        chunk->set_individually_sorted_by({SortColumnDefinition(left_join_column, SortMode::Ascending),
                                           SortColumnDefinition(right_join_column, SortMode::Ascending)});
      }
    }
    _performance.set_step_runtime(OperatorSteps::OutputWriting, timer.lap());

    auto result_table = _sort_merge_join._build_output_table(std::move(output_chunks));

    if (_mode != JoinMode::Left && _mode != JoinMode::Right && _mode != JoinMode::FullOuter &&
        _sort_merge_join._primary_predicate.predicate_condition == PredicateCondition::Equals) {
      // Table clustering is not defined for columns storing NULL values. Additionally, clustering is not given for
      // non-equal predicates.
      result_table->set_value_clustered_by({left_join_column, right_join_column});
    }
    return result_table;
  }
};

}  // namespace opossum