sortedArrayManipulation.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

// Source includes
#include "Macros.hpp"
#include "arrayManipulation.hpp"
#include "sortedArrayManipulationHelpers.hpp"

// System includes
#include <cstdlib>      // for std::malloc and std::free.
#include <algorithm>    // for std::sort

namespace LvArray
{

namespace sortedArrayManipulation
{

enum Description
{
  SORTED_UNIQUE,
  UNSORTED_NO_DUPLICATES,
  SORTED_WITH_DUPLICATES,
  UNSORTED_WITH_DUPLICATES
};

LVARRAY_HOST_DEVICE constexpr inline
bool isSorted( Description const desc )
{ return desc == SORTED_UNIQUE || desc == SORTED_WITH_DUPLICATES; }

LVARRAY_HOST_DEVICE constexpr inline
bool isUnique( Description const desc )
{ return desc == SORTED_UNIQUE || desc == UNSORTED_NO_DUPLICATES; }

template< typename T >
class CallBacks
{
public:

  LVARRAY_HOST_DEVICE inline
  T * incrementSize( T * const curPtr,
                     std::ptrdiff_t const nToAdd )
  {
    LVARRAY_UNUSED_VARIABLE( nToAdd );
    return curPtr;
  }

  LVARRAY_HOST_DEVICE inline
  void insert( std::ptrdiff_t const pos )
  { LVARRAY_UNUSED_VARIABLE( pos ); }

  LVARRAY_HOST_DEVICE inline
  void set( std::ptrdiff_t const pos,
            std::ptrdiff_t const valuePos )
  {
    LVARRAY_UNUSED_VARIABLE( pos );
    LVARRAY_UNUSED_VARIABLE( valuePos );
  }

  LVARRAY_HOST_DEVICE inline
  void insert( std::ptrdiff_t const nLeftToInsert,
               std::ptrdiff_t const valuePos,
               std::ptrdiff_t const pos,
               std::ptrdiff_t const prevPos )
  {
    LVARRAY_UNUSED_VARIABLE( nLeftToInsert );
    LVARRAY_UNUSED_VARIABLE( valuePos );
    LVARRAY_UNUSED_VARIABLE( pos );
    LVARRAY_UNUSED_VARIABLE( prevPos );
  }

  LVARRAY_HOST_DEVICE inline
  void remove( std::ptrdiff_t const pos )
  { LVARRAY_UNUSED_VARIABLE( pos ); }

  LVARRAY_HOST_DEVICE inline
  void remove( std::ptrdiff_t const nRemoved,
               std::ptrdiff_t const curPos,
               std::ptrdiff_t const nextPos )
  {
    LVARRAY_UNUSED_VARIABLE( nRemoved );
    LVARRAY_UNUSED_VARIABLE( curPos );
    LVARRAY_UNUSED_VARIABLE( nextPos );
  }
};

template< typename T >
struct less
{
  DISABLE_HD_WARNING
  constexpr LVARRAY_HOST_DEVICE inline
  bool operator() ( T const & lhs, T const & rhs ) const
  { return lhs < rhs; }
};

template< typename T >
struct greater
{
  DISABLE_HD_WARNING
  constexpr LVARRAY_HOST_DEVICE inline
  bool operator() ( T const & lhs, T const & rhs ) const
  { return lhs > rhs; }
};

DISABLE_HD_WARNING
template< typename RandomAccessIterator,
          typename Compare=less< typename std::iterator_traits< RandomAccessIterator >::value_type > >
LVARRAY_HOST_DEVICE inline void makeSorted( RandomAccessIterator const first,
                                            RandomAccessIterator const last,
                                            Compare && comp=Compare() )
{
#ifdef __CUDA_ARCH__
  if( last - first > internal::INTROSORT_THRESHOLD )
  {
    internal::introsortLoop( first, last, comp );
  }

  internal::insertionSort( first, last - first, comp );
#else
  std::sort( first, last, std::forward< Compare >( comp ) );
#endif
}

DISABLE_HD_WARNING
template< typename RandomAccessIteratorA,
          typename RandomAccessIteratorB,
          typename Compare=less< typename std::iterator_traits< RandomAccessIteratorA >::value_type > >
LVARRAY_HOST_DEVICE inline void dualSort( RandomAccessIteratorA valueFirst, RandomAccessIteratorA valueLast,
                                          RandomAccessIteratorB dataFirst, Compare && comp=Compare() )
{
  std::ptrdiff_t const size = valueLast - valueFirst;
  internal::DualIterator< RandomAccessIteratorA, RandomAccessIteratorB > dualIter( valueFirst, dataFirst );

  auto dualCompare = dualIter.createComparator( std::forward< Compare >( comp ) );

  if( size > internal::INTROSORT_THRESHOLD )
  {
    internal::introsortLoop( dualIter, dualIter + size, dualCompare );
  }

  internal::insertionSort( dualIter, size, dualCompare );
}

DISABLE_HD_WARNING
template< typename ITER, typename Compare=less< typename std::iterator_traits< ITER >::value_type > >
LVARRAY_HOST_DEVICE inline
bool isSorted( ITER first, ITER const last, Compare && comp=Compare() )
{
  if( first == last )
  {
    return true;
  }

  ITER next = first;
  ++next;
  while( next != last )
  {
    if( comp( *next, *first ) )
    {
      return false;
    }

    first = next;
    ++next;
  }

  return true;
}

DISABLE_HD_WARNING
template< typename ITER, typename Compare=less< typename std::iterator_traits< ITER >::value_type > >
LVARRAY_HOST_DEVICE inline
std::ptrdiff_t removeDuplicates( ITER first, ITER const last, Compare && comp=Compare() )
{
  LVARRAY_ASSERT( isSorted( first, last, comp ) );

  if( first == last )
  {
    return 0;
  }

  std::ptrdiff_t numUnique = 1;

  ITER next = first;
  for(; next != last; ++next )
  {
    if( comp( *first, *next ) )
    {
      ++numUnique;
      ++first;
      if( first != next )
      {
        *first = std::move( *next );
      }
    }
  }

  return numUnique;
}

DISABLE_HD_WARNING
template< typename ITER, typename Compare=less< typename std::iterator_traits< ITER >::value_type > >
LVARRAY_HOST_DEVICE inline
std::ptrdiff_t makeSortedUnique( ITER const first, ITER const last, Compare && comp=Compare() )
{
  makeSorted( first, last, comp );
  return removeDuplicates( first, last, comp );
}

DISABLE_HD_WARNING
template< typename ITER, typename Compare=less< typename std::iterator_traits< ITER >::value_type > >
LVARRAY_HOST_DEVICE inline
bool isSortedUnique( ITER first, ITER const last, Compare && comp=Compare() )
{
  if( first == last )
  {
    return true;
  }

  ITER next = first;
  ++next;
  while( next != last )
  {
    if( comp( *next, *first ) || !comp( *first, *next ) )
    {
      return false;
    }

    first = next;
    ++next;
  }

  return true;
}

DISABLE_HD_WARNING
template< typename T, typename Compare=less< T > >
LVARRAY_HOST_DEVICE inline
std::ptrdiff_t find( T const * const LVARRAY_RESTRICT ptr,
                     std::ptrdiff_t const size,
                     T const & value,
                     Compare && comp=Compare() )
{
  LVARRAY_ASSERT( ptr != nullptr || size == 0 );
  LVARRAY_ASSERT( arrayManipulation::isPositive( size ) );
  LVARRAY_ASSERT( isSorted( ptr, ptr + size, comp ) );

  std::ptrdiff_t lower = 0;
  std::ptrdiff_t upper = size;
  while( lower != upper )
  {
    std::ptrdiff_t const guess = (lower + upper) / 2;
    if( comp( ptr[guess], value ) )
    {
      lower = guess + 1;
    }
    else
    {
      upper = guess;
    }
  }

  return lower;
}

DISABLE_HD_WARNING
template< typename T, typename Compare=less< T > >
LVARRAY_HOST_DEVICE inline
bool contains( T const * const LVARRAY_RESTRICT ptr,
               std::ptrdiff_t const size,
               T const & value,
               Compare && comp=Compare() )
{
  std::ptrdiff_t const pos = find( ptr, size, value, std::forward< Compare >( comp ) );
  return (pos != size) && (ptr[pos] == value);
}

DISABLE_HD_WARNING
template< typename T, typename CALLBACKS >
LVARRAY_HOST_DEVICE inline
bool remove( T * const LVARRAY_RESTRICT ptr,
             std::ptrdiff_t const size,
             T const & value,
             CALLBACKS && callBacks )
{
  LVARRAY_ASSERT( ptr != nullptr || size == 0 );
  LVARRAY_ASSERT( arrayManipulation::isPositive( size ) );

  // Find the position of value.
  std::ptrdiff_t const index = find( ptr, size, value );

  // If it's not in the array we can return.
  if( index == size || ptr[index] != value )
  {
    return false;
  }

  // Remove the value and call the callback.
  arrayManipulation::erase( ptr, size, index );
  callBacks.remove( index );
  return true;
}

DISABLE_HD_WARNING
template< typename T, typename ITER, typename CALLBACKS=CallBacks< T > >
LVARRAY_HOST_DEVICE inline
std::ptrdiff_t remove( T * const LVARRAY_RESTRICT ptr,
                       std::ptrdiff_t const size,
                       ITER const first,
                       ITER const last,
                       CALLBACKS && callBacks=CALLBACKS() )
{
  LVARRAY_ASSERT( ptr != nullptr || size == 0 );
  LVARRAY_ASSERT( arrayManipulation::isPositive( size ) );
  LVARRAY_ASSERT( isSortedUnique( ptr, ptr + size ) );

  LVARRAY_ASSERT( isSortedUnique( first, last ) );

  // Find the position of the first value to remove and the position it's at in the array.
  ITER valueToRemove = first;
  std::ptrdiff_t removalPosition = 0;
  for(; valueToRemove != last; ++valueToRemove )
  {
    removalPosition += find( ptr + removalPosition, size - removalPosition, *valueToRemove );

    // If the current value is larger than the largest value in the array we can return.
    if( removalPosition == size )
    {
      return 0;
    }

    if( ptr[ removalPosition ] == *valueToRemove )
    {
      break;
    }
  }

  // If we didn't find a value to remove we can return.
  if( valueToRemove == last )
  {
    return 0;
  }

  // Loop over the values
  std::ptrdiff_t nRemoved = 0;
  for(; valueToRemove != last; )
  {
    // Find the next value to remove
    ITER nextValueToRemove = valueToRemove;
    ++nextValueToRemove;
    std::ptrdiff_t nextRemovalPosition = removalPosition;
    for(; nextValueToRemove != last; ++nextValueToRemove )
    {
      // Find the position
      nextRemovalPosition += find( ptr + nextRemovalPosition, size - nextRemovalPosition, *nextValueToRemove );

      // If it's not in the array then neither are any of the rest of the values.
      if( nextRemovalPosition == size )
      {
        nextValueToRemove = last;
        break;
      }

      // If it's in the array then we can exit this loop.
      if( ptr[ nextRemovalPosition ] == *nextValueToRemove )
      {
        break;
      }
    }

    if( nextValueToRemove == last )
    {
      nextRemovalPosition = size;
    }

    // Shift the values down and call the callback.
    nRemoved += 1;
    arrayManipulation::shiftDown( ptr, nextRemovalPosition, removalPosition + 1, nRemoved );
    callBacks.remove( nRemoved, removalPosition, nextRemovalPosition );

    valueToRemove = nextValueToRemove;
    removalPosition = nextRemovalPosition;

    // If we've reached the end of the array we can exit the loop.
    if( removalPosition == size )
    {
      break;
    }
  }

  // Destroy the values moved out of at the end of the array.
  for( std::ptrdiff_t i = size - nRemoved; i < size; ++i )
  {
    ptr[ i ].~T();
  }

  return nRemoved;
}

DISABLE_HD_WARNING
template< typename T, typename CALLBACKS=CallBacks< T > >
LVARRAY_HOST_DEVICE inline
bool insert( T * const LVARRAY_RESTRICT ptr,
             std::ptrdiff_t const size,
             T const & value,
             CALLBACKS && callBacks=CALLBACKS() )
{
  LVARRAY_ASSERT( ptr != nullptr || size == 0 );
  LVARRAY_ASSERT( arrayManipulation::isPositive( size ) );
  LVARRAY_ASSERT( isSortedUnique( ptr, ptr + size ) );

  std::ptrdiff_t insertPos = std::ptrdiff_t( -1 );
  if( size == 0 || value < ptr[0] ) // Take care of the case of an empty array or inserting at the beginning.
  {
    insertPos = 0;
  }
  else if( ptr[size - 1] < value ) // The case of inserting at the end.
  {
    insertPos = size;
  }
  else // otherwise do a binary search
  {
    // We've already checked the first and last values.
    insertPos = find( ptr, size, value );
  }

  // If it's in the array we call the incrementSize callback and return false.
  if( insertPos != size && ptr[insertPos] == value )
  {
    callBacks.incrementSize( ptr, 0 );
    return false;
  }

  // Otherwise call the incrementSize callback, get the new pointer, insert and call the insert callback.
  T * const newPtr = callBacks.incrementSize( ptr, 1 );
  arrayManipulation::emplace( newPtr, size, insertPos, value );
  callBacks.insert( insertPos );
  return true;
}

DISABLE_HD_WARNING
template< typename T, typename ITER, typename CALLBACKS=CallBacks< T > >
LVARRAY_HOST_DEVICE inline
std::ptrdiff_t insert( T * const LVARRAY_RESTRICT ptr,
                       std::ptrdiff_t const size,
                       ITER const first,
                       ITER const last,
                       CALLBACKS && callBacks=CALLBACKS() )
{
  LVARRAY_ASSERT( ptr != nullptr || size == 0 );
  LVARRAY_ASSERT( arrayManipulation::isPositive( size ) );
  LVARRAY_ASSERT( isSortedUnique( ptr, ptr + size ) );

  LVARRAY_ASSERT( isSortedUnique( first, last ) );

  // Special case for inserting into an empty array.
  if( size == 0 )
  {
    std::ptrdiff_t numInserted = arrayManipulation::iterDistance( first, last );
    T * const newPtr = callBacks.incrementSize( ptr, numInserted );

    numInserted = 0;
    for( ITER iter = first; iter != last; ++iter )
    {
      new ( newPtr + numInserted ) T( *iter );
      callBacks.set( numInserted, numInserted );
      ++numInserted;
    }

    return numInserted;
  }

  // Count up the number of values that will actually be inserted.
  std::ptrdiff_t nVals = 0;
  std::ptrdiff_t nToInsert = 0;
  std::ptrdiff_t upperBound = size;
  ITER iter = last;
  while( iter != first )
  {
    --iter;
    ++nVals;
    upperBound = find( ptr, upperBound, *iter );
    if( upperBound == size || ptr[upperBound] != *iter )
    {
      ++nToInsert;
    }
  }

  // Call callBack with the number to insert and get a new pointer back.
  T * const newPtr = callBacks.incrementSize( ptr, nToInsert );

  // If there are no values to insert we can return.
  if( nToInsert == 0 )
  {
    return 0;
  }

  // Insert the rest of the values.
  std::ptrdiff_t currentIndex = nVals - 1;
  std::ptrdiff_t nLeftToInsert = nToInsert;
  upperBound = size;
  iter = last;
  while( iter != first )
  {
    --iter;
    std::ptrdiff_t const pos = find( newPtr, upperBound, *iter );

    // If *iter is already in the array skip it.
    if( pos != upperBound && newPtr[pos] == *iter )
    {
      --currentIndex;
      continue;
    }

    // Else shift the values up and insert.
    arrayManipulation::shiftUp( newPtr, upperBound, pos, nLeftToInsert );
    new ( newPtr + pos + nLeftToInsert - 1 ) T( *iter );
    callBacks.insert( nLeftToInsert, currentIndex, pos, upperBound );

    --currentIndex;
    --nLeftToInsert;
    upperBound = pos;
  }

  return nToInsert;
}

} // namespace sortedArrayManipulation
} // namespace LvArray