// -*- C++ -*-
//===-- parallel_backend_utils.h ------------------------------------------===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//

#ifndef __PSTL_parallel_backend_utils_H
#define __PSTL_parallel_backend_utils_H

#include <iterator>
#include <utility>
#include <cassert>
#include "utils.h"

namespace __pstl
{
namespace par_backend
{

//! Destroy sequence [xs,xe)
struct serial_destroy
{
    template <typename _RandomAccessIterator>
    void
    operator()(_RandomAccessIterator __zs, _RandomAccessIterator __ze)
    {
        typedef typename std::iterator_traits<_RandomAccessIterator>::value_type _ValueType;
        while (__zs != __ze)
        {
            --__ze;
            (*__ze).~_ValueType();
        }
    }
};

//! Merge sequences [__xs,__xe) and [__ys,__ye) to output sequence [__zs,(__xe-__xs)+(__ye-__ys)), using std::move
template <class _MoveValues, class _MoveSequences>
struct serial_move_merge
{
    const std::size_t _M_nmerge;
    _MoveValues _M_move_values;
    _MoveSequences _M_move_sequences;

    explicit serial_move_merge(std::size_t __nmerge, _MoveValues __move_values, _MoveSequences __move_sequences)
        : _M_nmerge(__nmerge), _M_move_values(__move_values), _M_move_sequences(__move_sequences)
    {
    }
    template <class _RandomAccessIterator1, class _RandomAccessIterator2, class _RandomAccessIterator3, class _Compare>
    void
    operator()(_RandomAccessIterator1 __xs, _RandomAccessIterator1 __xe, _RandomAccessIterator2 __ys,
               _RandomAccessIterator2 __ye, _RandomAccessIterator3 __zs, _Compare __comp)
    {
        auto __n = _M_nmerge;
        assert(__n > 0);
        if (__xs != __xe)
        {
            if (__ys != __ye)
            {
                for (;;)
                {
                    if (__comp(*__ys, *__xs))
                    {
                        _M_move_values(__ys, __zs);
                        ++__zs, --__n;
                        if (++__ys == __ye)
                        {
                            break;
                        }
                        else if (__n == 0)
                        {
                            __zs = _M_move_sequences(__ys, __ye, __zs);
                            break;
                        }
                        else
                        {
                        }
                    }
                    else
                    {
                        _M_move_values(__xs, __zs);
                        ++__zs, --__n;
                        if (++__xs == __xe)
                        {
                            _M_move_sequences(__ys, __ye, __zs);
                            return;
                        }
                        else if (__n == 0)
                        {
                            __zs = _M_move_sequences(__xs, __xe, __zs);
                            _M_move_sequences(__ys, __ye, __zs);
                            return;
                        }
                        else
                        {
                        }
                    }
                }
            }
            __ys = __xs;
            __ye = __xe;
        }
        _M_move_sequences(__ys, __ye, __zs);
    }
};

template <typename _RandomAccessIterator1, typename _OutputIterator>
void
init_buf(_RandomAccessIterator1 __xs, _RandomAccessIterator1 __xe, _OutputIterator __zs, bool __bMove)
{
    const _OutputIterator __ze = __zs + (__xe - __xs);
    typedef typename std::iterator_traits<_OutputIterator>::value_type _ValueType;
    if (__bMove)
    {
        // Initialize the temporary buffer and move keys to it.
        for (; __zs != __ze; ++__xs, ++__zs)
            new (&*__zs) _ValueType(std::move(*__xs));
    }
    else
    {
        // Initialize the temporary buffer
        for (; __zs != __ze; ++__zs)
            new (&*__zs) _ValueType;
    }
}

template <typename _Buf>
class stack
{
    typedef typename std::iterator_traits<decltype(_Buf(0).get())>::value_type _ValueType;
    typedef typename std::iterator_traits<_ValueType*>::difference_type _DifferenceType;

    _Buf _M_buf;
    _ValueType* _M_ptr;
    _DifferenceType _M_maxsize;

    stack(const stack&) = delete;
    void
    operator=(const stack&) = delete;

  public:
    stack(_DifferenceType __max_size) : _M_buf(__max_size), _M_maxsize(__max_size) { _M_ptr = _M_buf.get(); }

    ~stack()
    {
        assert(size() <= _M_maxsize);
        while (!empty())
            pop();
    }

    const _Buf&
    buffer() const
    {
        return _M_buf;
    }
    size_t
    size() const
    {
        assert(_M_ptr - _M_buf.get() <= _M_maxsize);
        assert(_M_ptr - _M_buf.get() >= 0);
        return _M_ptr - _M_buf.get();
    }
    bool
    empty() const
    {
        assert(_M_ptr >= _M_buf.get());
        return _M_ptr == _M_buf.get();
    }
    void
    push(const _ValueType& __v)
    {
        assert(size() < _M_maxsize);
        new (_M_ptr) _ValueType(__v);
        ++_M_ptr;
    }
    const _ValueType&
    top() const
    {
        return *(_M_ptr - 1);
    }
    void
    pop()
    {
        assert(_M_ptr > _M_buf.get());
        --_M_ptr;
        (*_M_ptr).~_ValueType();
    }
};

} // namespace par_backend
} // namespace __pstl

#endif /* __PSTL_parallel_backend_utils_H */