sortedArrayManipulationHelpers.hpp

Go to the documentation of this file.

/*
 * Copyright (c) 2020, Lawrence Livermore National Security, LLC and LvArray contributors.
 * All rights reserved.
 * See the LICENSE file for details.
 * SPDX-License-Identifier: (BSD-3-Clause)
 */

#pragma once

#include "LvArrayConfig.hpp"
#include "Macros.hpp"

#include <utility>

namespace LvArray
{
namespace sortedArrayManipulation
{
namespace internal
{

constexpr int INTROSORT_THRESHOLD = 64;

template< class A, class B >
struct DualIteratorAccessor
{
  struct Temporary
  {
    inline Temporary() = delete;

    inline Temporary( Temporary const & ) = delete;

    DISABLE_HD_WARNING
    LVARRAY_HOST_DEVICE inline Temporary( Temporary && src ):
      m_a( std::move( src.m_a )),
      m_b( std::move( src.m_b ))
    {}

    DISABLE_HD_WARNING
    LVARRAY_HOST_DEVICE inline Temporary( DualIteratorAccessor && src ):
      m_a( std::move( src.m_a )),
      m_b( std::move( src.m_b ))
    {}

    DISABLE_HD_WARNING
    inline ~Temporary() = default;

    inline Temporary & operator=( Temporary const & ) = delete;

    inline Temporary & operator=( Temporary && ) = delete;

    A m_a;

    B m_b;
  };

  DualIteratorAccessor() = delete;

  DISABLE_HD_WARNING
  LVARRAY_HOST_DEVICE inline DualIteratorAccessor( A & a, B & b ):
    m_a( a ),
    m_b( b )
  {}

  DualIteratorAccessor( DualIteratorAccessor const & ) = delete;

  DISABLE_HD_WARNING
  inline DualIteratorAccessor( DualIteratorAccessor && ) = default;

  DualIteratorAccessor & operator=( DualIteratorAccessor const & ) = delete;

  DISABLE_HD_WARNING
  LVARRAY_HOST_DEVICE inline DualIteratorAccessor & operator=( DualIteratorAccessor && src )
  {
    m_a = std::move( src.m_a );
    m_b = std::move( src.m_b );
    return *this;
  }

  DISABLE_HD_WARNING
  LVARRAY_HOST_DEVICE DualIteratorAccessor & operator=( Temporary && src )
  {
    m_a = std::move( src.m_a );
    m_b = std::move( src.m_b );
    return *this;
  }

  A & m_a;

  B & m_b;
};

template< typename A, typename B, typename Compare >
struct DualIteratorComparator
{
  DISABLE_HD_WARNING
  LVARRAY_HOST_DEVICE inline DualIteratorComparator( Compare comp ):
    m_compare( comp )
  {}

  DISABLE_HD_WARNING
  LVARRAY_HOST_DEVICE inline bool operator()( DualIteratorAccessor< A, B > const & lhs,
                                              DualIteratorAccessor< A, B > const & rhs ) const
  { return m_compare( lhs.m_a, rhs.m_a ); }

  DISABLE_HD_WARNING
  LVARRAY_HOST_DEVICE inline bool operator()( typename DualIteratorAccessor< A, B >::Temporary const & lhs,
                                              DualIteratorAccessor< A, B > const & rhs ) const
  { return m_compare( lhs.m_a, rhs.m_a ); }

private:
  Compare m_compare;
};

template< class RandomAccessIteratorA, class RandomAccessIteratorB >
class DualIterator
{
public:
  using A = typename std::remove_reference< decltype( *std::declval< RandomAccessIteratorA >() ) >::type;

  using B = typename std::remove_reference< decltype( *std::declval< RandomAccessIteratorB >() ) >::type;

  DISABLE_HD_WARNING
  inline DualIterator() = default;

  DISABLE_HD_WARNING
  LVARRAY_HOST_DEVICE inline DualIterator( RandomAccessIteratorA const itA, RandomAccessIteratorB const itB ):
    m_itA( itA ),
    m_itB( itB )
  {}

  DISABLE_HD_WARNING
  inline DualIterator( DualIterator const & src ) = default;

  DISABLE_HD_WARNING
  inline DualIterator( DualIterator && src ) = default;

  DISABLE_HD_WARNING
  inline DualIterator & operator=( DualIterator const & src ) = default;

  DISABLE_HD_WARNING
  inline DualIterator & operator=( DualIterator && src ) = default;

  DISABLE_HD_WARNING
  LVARRAY_HOST_DEVICE inline DualIterator operator+( std::ptrdiff_t const offset ) const
  { return DualIterator( m_itA + offset, m_itB + offset ); }

  DISABLE_HD_WARNING
  LVARRAY_HOST_DEVICE inline DualIterator & operator+=( std::ptrdiff_t const offset )
  {
    m_itA += offset;
    m_itB += offset;
    return *this;
  }

  DISABLE_HD_WARNING
  LVARRAY_HOST_DEVICE inline DualIterator & operator++()
  {
    m_itA++;
    m_itB++;
    return *this;
  }

  DISABLE_HD_WARNING
  LVARRAY_HOST_DEVICE inline std::ptrdiff_t operator-( DualIterator const & rhs ) const
  {
    std::ptrdiff_t const distance = m_itA - rhs.m_itA;
    LVARRAY_ASSERT_EQ( distance, m_itB - rhs.m_itB );
    return distance;
  }

  DISABLE_HD_WARNING
  LVARRAY_HOST_DEVICE inline DualIterator operator-( std::ptrdiff_t const offset ) const
  { return *this + (-offset); }

  DISABLE_HD_WARNING
  LVARRAY_HOST_DEVICE inline DualIterator & operator-=( std::ptrdiff_t const offset )
  { return *this += (-offset); }

  DISABLE_HD_WARNING
  LVARRAY_HOST_DEVICE inline DualIterator & operator--()
  {
    m_itA--;
    m_itB--;
    return *this;
  }

  DISABLE_HD_WARNING
  LVARRAY_HOST_DEVICE inline bool operator!=( DualIterator const & rhs ) const
  { return m_itA != rhs.m_itA; }

  DISABLE_HD_WARNING
  LVARRAY_HOST_DEVICE inline bool operator<( DualIterator const & rhs ) const
  { return m_itA < rhs.m_itA; }

  DISABLE_HD_WARNING
  LVARRAY_HOST_DEVICE inline DualIteratorAccessor< A, B > operator*() const
  { return DualIteratorAccessor< A, B >( *m_itA, *m_itB ); }

  DISABLE_HD_WARNING
  template< class Compare >
  LVARRAY_HOST_DEVICE inline DualIteratorComparator< A, B, Compare > createComparator( Compare && comp ) const
  { return DualIteratorComparator< A, B, Compare >( std::forward< Compare >( comp ) ); }

private:
  RandomAccessIteratorA m_itA;

  RandomAccessIteratorB m_itB;

};

DISABLE_HD_WARNING
template< class T >
LVARRAY_HOST_DEVICE inline T && createTemporary( T & a )
{
  return std::move( a );
}

DISABLE_HD_WARNING
template< class A, class B >
inline LVARRAY_HOST_DEVICE typename DualIteratorAccessor< A, B >::Temporary createTemporary( DualIteratorAccessor< A, B > && it )
{ return typename DualIteratorAccessor< A, B >::Temporary( std::move( it )); }

DISABLE_HD_WARNING
template< class Iterator >
LVARRAY_HOST_DEVICE inline void exchange( Iterator a, Iterator b )
{
  auto temp = createTemporary( *a );
  *a = std::move( *b );
  *b = std::move( temp );
}

DISABLE_HD_WARNING
template< class BidirIt1, class BidirIt2 >
LVARRAY_HOST_DEVICE inline void moveBackward( BidirIt1 first, BidirIt1 last, BidirIt2 d_last )
{
  while( first != last )
  {
    *(--d_last) = std::move( *(--last));
  }
}

DISABLE_HD_WARNING
template< typename Iterator, typename Compare >
LVARRAY_HOST_DEVICE inline void computeMedian( Iterator result, Iterator a, Iterator b, Iterator c, Compare && comp )
{
  if( comp( *a, *b ))
  {
    if( comp( *b, *c ))
    {
      exchange( result, b );
    }
    else if( comp( *a, *c ))
    {
      exchange( result, c );
    }
    else
    {
      exchange( result, a );
    }
  }
  else if( comp( *a, *c ))
  {
    exchange( result, a );
  }
  else if( comp( *b, *c ))
  {
    exchange( result, c );
  }
  else
  {
    exchange( result, b );
  }
}

DISABLE_HD_WARNING
template< typename RandomAccessIterator, typename Compare >
LVARRAY_HOST_DEVICE inline RandomAccessIterator unguardedPartition( RandomAccessIterator first, RandomAccessIterator last,
                                                                    RandomAccessIterator pivot, Compare && comp )
{
  while( true )
  {
    while( comp( *first, *pivot ))
    {
      ++first;
    }

    --last;
    while( comp( *pivot, *last ))
    {
      --last;
    }

    if( !(first < last))
    {
      return first;
    }

    exchange( first, last );
    ++first;
  }
}

DISABLE_HD_WARNING
template< typename RandomAccessIterator, typename Compare >
LVARRAY_HOST_DEVICE inline RandomAccessIterator unguardedPartitionPivot( RandomAccessIterator first, RandomAccessIterator last, Compare && comp )
{
  RandomAccessIterator mid = first + (last - first) / 2;
  computeMedian( first, first + 1, mid, last - 1, comp );
  return unguardedPartition( first + 1, last, first, comp );
}

DISABLE_HD_WARNING
template< typename RandomAccessIterator, typename Compare >
LVARRAY_HOST_DEVICE inline void unguardedLinearInsert( RandomAccessIterator last, Compare comp )
{
  auto val = createTemporary( *last );
  RandomAccessIterator next = last - 1;
  while( comp( val, *next ))
  {
    *last = std::move( *next );
    last = next;
    --next;
  }
  *last = std::move( val );
}

DISABLE_HD_WARNING
template< class RandomAccessIterator, class Compare >
LVARRAY_HOST_DEVICE inline void insertionSort( RandomAccessIterator first, std::ptrdiff_t const n, Compare comp )
{
  for( std::ptrdiff_t i = 1; i < n; ++i )
  {
    if( comp( *(first + i), *first ))
    {
      auto val = createTemporary( *(first + i));
      moveBackward( first, first + i, first + i + 1 );
      *first = std::move( val );
    }
    else
    {
      unguardedLinearInsert( first + i, comp );
    }
  }
}

DISABLE_HD_WARNING
template< typename RandomAccessIterator, typename Compare >
LVARRAY_HOST_DEVICE inline void introsortLoop( RandomAccessIterator first, RandomAccessIterator last, Compare && comp )
{
  constexpr int MAX_RANGES = 31;
  RandomAccessIterator ranges[MAX_RANGES + 1];

  int nRanges = 1;
  ranges[0] = first;
  ranges[1] = last;
  while( nRanges != 0 )
  {
    RandomAccessIterator const m_first = ranges[nRanges - 1];

    if( ranges[nRanges] - m_first > INTROSORT_THRESHOLD )
    {
      LVARRAY_ASSERT( nRanges < MAX_RANGES );
      ranges[nRanges + 1] = ranges[nRanges];
      ranges[nRanges] = unguardedPartitionPivot( m_first, ranges[nRanges], comp );
      ++nRanges;
    }
    else
    {
      --nRanges;
    }
  }
}

} // namespace internal
} // namespace sortedArrayManipulation
} // namespace LvArray