//---------------------------------------------------------------------------//
// Copyright (c) 2013 Kyle Lutz <kyle.r.lutz@gmail.com>
//
// 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
//
// See http://boostorg.github.com/compute for more information.
//---------------------------------------------------------------------------//

#ifndef BOOST_COMPUTE_CONTAINER_VECTOR_HPP
#define BOOST_COMPUTE_CONTAINER_VECTOR_HPP

#include <vector>
#include <cstddef>
#include <iterator>
#include <exception>

#include <boost/throw_exception.hpp>

#include <boost/compute/config.hpp>

#ifndef BOOST_COMPUTE_NO_HDR_INITIALIZER_LIST
#include <initializer_list>
#endif

#include <boost/compute/buffer.hpp>
#include <boost/compute/device.hpp>
#include <boost/compute/system.hpp>
#include <boost/compute/context.hpp>
#include <boost/compute/command_queue.hpp>
#include <boost/compute/algorithm/copy.hpp>
#include <boost/compute/algorithm/copy_n.hpp>
#include <boost/compute/algorithm/fill_n.hpp>
#include <boost/compute/allocator/buffer_allocator.hpp>
#include <boost/compute/iterator/buffer_iterator.hpp>
#include <boost/compute/type_traits/detail/capture_traits.hpp>
#include <boost/compute/detail/buffer_value.hpp>
#include <boost/compute/detail/iterator_range_size.hpp>

namespace boost {
namespace compute {

/// \class vector
/// \brief A resizable array of values.
///
/// The vector<T> class stores a dynamic array of values. Internally, the data
/// is stored in an OpenCL buffer object.
///
/// The vector class is the prefered container for storing and accessing data
/// on a compute device. In most cases it should be used instead of directly
/// dealing with buffer objects. If the undelying buffer is needed, it can be
/// accessed with the get_buffer() method.
///
/// The internal storage is allocated in a specific OpenCL context which is
/// passed as an argument to the constructor when the vector is created.
///
/// For example, to create a vector on the device containing space for ten
/// \c int values:
/// \code
/// boost::compute::vector<int> vec(10, context);
/// \endcode
///
/// Allocation and data transfer can also be performed in a single step:
/// \code
/// // values on the host
/// int data[] = { 1, 2, 3, 4 };
///
/// // create a vector of size four and copy the values from data
/// boost::compute::vector<int> vec(data, data + 4, queue);
/// \endcode
///
/// The Boost.Compute \c vector class provides a STL-like API and is modeled
/// after the \c std::vector class from the C++ standard library. It can be
/// used with any of the STL-like algorithms provided by Boost.Compute
/// including \c copy(), \c transform(), and \c sort() (among many others).
///
/// For example:
/// \code
/// // a vector on a compute device
/// boost::compute::vector<float> vec = ...
///
/// // copy data to the vector from a host std:vector
/// boost::compute::copy(host_vec.begin(), host_vec.end(), vec.begin(), queue);
///
/// // copy data from the vector to a host std::vector
/// boost::compute::copy(vec.begin(), vec.end(), host_vec.begin(), queue);
///
/// // sort the values in the vector
/// boost::compute::sort(vec.begin(), vec.end(), queue);
///
/// // calculate the sum of the values in the vector (also see reduce())
/// float sum = boost::compute::accumulate(vec.begin(), vec.end(), 0, queue);
///
/// // reverse the values in the vector
/// boost::compute::reverse(vec.begin(), vec.end(), queue);
///
/// // fill the vector with ones
/// boost::compute::fill(vec.begin(), vec.end(), 1, queue);
/// \endcode
///
/// \see \ref array "array<T, N>", buffer
template<class T, class Alloc = buffer_allocator<T> >
class vector
{
public:
    typedef T value_type;
    typedef Alloc allocator_type;
    typedef typename allocator_type::size_type size_type;
    typedef typename allocator_type::difference_type difference_type;
    typedef detail::buffer_value<T> reference;
    typedef const detail::buffer_value<T> const_reference;
    typedef typename allocator_type::pointer pointer;
    typedef typename allocator_type::const_pointer const_pointer;
    typedef buffer_iterator<T> iterator;
    typedef buffer_iterator<T> const_iterator;
    typedef std::reverse_iterator<iterator> reverse_iterator;
    typedef std::reverse_iterator<const_iterator> const_reverse_iterator;

    /// Creates an empty vector in \p context.
    explicit vector(const context &context = system::default_context())
        : m_size(0),
          m_allocator(context)
    {
        m_data = m_allocator.allocate(_minimum_capacity());
    }

    /// Creates a vector with space for \p count elements in \p context.
    ///
    /// Note that unlike \c std::vector's constructor, this will not initialize
    /// the values in the container. Either call the vector constructor which
    /// takes a value to initialize with or use the fill() algorithm to set
    /// the initial values.
    ///
    /// For example:
    /// \code
    /// // create a vector on the device with space for ten ints
    /// boost::compute::vector<int> vec(10, context);
    /// \endcode
    explicit vector(size_type count,
                    const context &context = system::default_context())
        : m_size(count),
          m_allocator(context)
    {
        m_data = m_allocator.allocate((std::max)(count, _minimum_capacity()));
    }

    /// Creates a vector with space for \p count elements and sets each equal
    /// to \p value.
    ///
    /// For example:
    /// \code
    /// // creates a vector with four values set to nine (e.g. [9, 9, 9, 9]).
    /// boost::compute::vector<int> vec(4, 9, queue);
    /// \endcode
    vector(size_type count,
           const T &value,
           command_queue &queue = system::default_queue())
        : m_size(count),
          m_allocator(queue.get_context())
    {
        m_data = m_allocator.allocate((std::max)(count, _minimum_capacity()));

        ::boost::compute::fill_n(begin(), count, value, queue);
    }

    /// Creates a vector with space for the values in the range [\p first,
    /// \p last) and copies them into the vector with \p queue.
    ///
    /// For example:
    /// \code
    /// // values on the host
    /// int data[] = { 1, 2, 3, 4 };
    ///
    /// // create a vector of size four and copy the values from data
    /// boost::compute::vector<int> vec(data, data + 4, queue);
    /// \endcode
    template<class InputIterator>
    vector(InputIterator first,
           InputIterator last,
           command_queue &queue = system::default_queue())
        : m_size(detail::iterator_range_size(first, last)),
          m_allocator(queue.get_context())
    {
        m_data = m_allocator.allocate((std::max)(m_size, _minimum_capacity()));

        ::boost::compute::copy(first, last, begin(), queue);
    }

    /// Creates a new vector and copies the values from \p other.
    vector(const vector &other,
           command_queue &queue = system::default_queue())
        : m_size(other.m_size),
          m_allocator(other.m_allocator)
    {
        m_data = m_allocator.allocate((std::max)(m_size, _minimum_capacity()));

        if(!other.empty()){
            if(other.get_buffer().get_context() != queue.get_context()){
                command_queue other_queue = other.default_queue();
                ::boost::compute::copy(other.begin(), other.end(), begin(), other_queue);
                other_queue.finish();
            }
            else {
                ::boost::compute::copy(other.begin(), other.end(), begin(), queue);
                queue.finish();
            }
        }
    }

    /// Creates a new vector and copies the values from \p other.
    template<class OtherAlloc>
    vector(const vector<T, OtherAlloc> &other,
           command_queue &queue = system::default_queue())
        : m_size(other.size()),
          m_allocator(queue.get_context())
    {
        m_data = m_allocator.allocate((std::max)(m_size, _minimum_capacity()));

        if(!other.empty()){
            ::boost::compute::copy(other.begin(), other.end(), begin(), queue);
            queue.finish();
        }
    }

    /// Creates a new vector and copies the values from \p vector.
    template<class OtherAlloc>
    vector(const std::vector<T, OtherAlloc> &vector,
           command_queue &queue = system::default_queue())
        : m_size(vector.size()),
          m_allocator(queue.get_context())
    {
        m_data = m_allocator.allocate((std::max)(m_size, _minimum_capacity()));

        ::boost::compute::copy(vector.begin(), vector.end(), begin(), queue);
    }

    #ifndef BOOST_COMPUTE_NO_HDR_INITIALIZER_LIST
    vector(std::initializer_list<T> list,
           command_queue &queue = system::default_queue())
        : m_size(list.size()),
          m_allocator(queue.get_context())
    {
        m_data = m_allocator.allocate((std::max)(m_size, _minimum_capacity()));

        ::boost::compute::copy(list.begin(), list.end(), begin(), queue);
    }
    #endif // BOOST_COMPUTE_NO_HDR_INITIALIZER_LIST

    vector& operator=(const vector &other)
    {
        if(this != &other){
            command_queue queue = default_queue();
            resize(other.size(), queue);
            ::boost::compute::copy(other.begin(), other.end(), begin(), queue);
            queue.finish();
        }

        return *this;
    }

    template<class OtherAlloc>
    vector& operator=(const vector<T, OtherAlloc> &other)
    {
        command_queue queue = default_queue();
        resize(other.size(), queue);
        ::boost::compute::copy(other.begin(), other.end(), begin(), queue);
        queue.finish();

        return *this;
    }

    template<class OtherAlloc>
    vector& operator=(const std::vector<T, OtherAlloc> &vector)
    {
        command_queue queue = default_queue();
        resize(vector.size(), queue);
        ::boost::compute::copy(vector.begin(), vector.end(), begin(), queue);
        queue.finish();
        return *this;
    }

    #ifndef BOOST_COMPUTE_NO_RVALUE_REFERENCES
    /// Move-constructs a new vector from \p other.
    vector(vector&& other)
        : m_data(std::move(other.m_data)),
          m_size(other.m_size),
          m_allocator(std::move(other.m_allocator))
    {
        other.m_size = 0;
    }

    /// Move-assigns the data from \p other to \c *this.
    vector& operator=(vector&& other)
    {
        if(capacity() > 0){
            m_allocator.deallocate(m_data, capacity());
        }

        m_data = std::move(other.m_data);
        m_size = other.m_size;
        m_allocator = std::move(other.m_allocator);

        other.m_size = 0;

        return *this;
    }
    #endif // BOOST_COMPUTE_NO_RVALUE_REFERENCES

    /// Destroys the vector object.
    ~vector()
    {
        if(capacity() > 0){
            m_allocator.deallocate(m_data, capacity());
        }
    }

    iterator begin()
    {
        return ::boost::compute::make_buffer_iterator<T>(m_data.get_buffer(), 0);
    }

    const_iterator begin() const
    {
        return ::boost::compute::make_buffer_iterator<T>(m_data.get_buffer(), 0);
    }

    const_iterator cbegin() const
    {
        return begin();
    }

    iterator end()
    {
        return ::boost::compute::make_buffer_iterator<T>(m_data.get_buffer(), m_size);
    }

    const_iterator end() const
    {
        return ::boost::compute::make_buffer_iterator<T>(m_data.get_buffer(), m_size);
    }

    const_iterator cend() const
    {
        return end();
    }

    reverse_iterator rbegin()
    {
        return reverse_iterator(end() - 1);
    }

    const_reverse_iterator rbegin() const
    {
        return reverse_iterator(end() - 1);
    }

    const_reverse_iterator crbegin() const
    {
        return rbegin();
    }

    reverse_iterator rend()
    {
        return reverse_iterator(begin() - 1);
    }

    const_reverse_iterator rend() const
    {
        return reverse_iterator(begin() - 1);
    }

    const_reverse_iterator crend() const
    {
        return rend();
    }

    /// Returns the number of elements in the vector.
    size_type size() const
    {
        return m_size;
    }

    size_type max_size() const
    {
        return m_allocator.max_size();
    }

    /// Resizes the vector to \p size.
    void resize(size_type size, command_queue &queue)
    {
        if(size <= capacity()){
            m_size = size;
        }
        else {
            // allocate new buffer
            pointer new_data =
                m_allocator.allocate(
                    static_cast<size_type>(
                        static_cast<float>(size) * _growth_factor()
                    )
                );

            if(capacity() > 0)
            {
                // copy old values to the new buffer
                ::boost::compute::copy(m_data, m_data + m_size, new_data, queue);

                // free old memory
                m_allocator.deallocate(m_data, capacity());
            }

            // set new data and size
            m_data = new_data;
            m_size = size;
        }
    }

    /// \overload
    void resize(size_type size)
    {
        command_queue queue = default_queue();
        resize(size, queue);
        queue.finish();
    }

    /// Returns \c true if the vector is empty.
    bool empty() const
    {
        return m_size == 0;
    }

    /// Returns the capacity of the vector.
    size_type capacity() const
    {
        if(m_data == pointer()) // null pointer check
        {
            return 0;
        }
        return m_data.get_buffer().size() / sizeof(T);
    }

    void reserve(size_type size, command_queue &queue)
    {
        if(size > max_size()){
            throw std::length_error("vector::reserve");
        }
        if(capacity() < size){
            // allocate new buffer
            pointer new_data =
                m_allocator.allocate(
                    static_cast<size_type>(
                        static_cast<float>(size) * _growth_factor()
                    )
                );

            if(capacity() > 0)
            {
                // copy old values to the new buffer
                ::boost::compute::copy(m_data, m_data + m_size, new_data, queue);

                // free old memory
                m_allocator.deallocate(m_data, capacity());
            }

            // set new data
            m_data = new_data;
        }
    }

    void reserve(size_type size)
    {
        command_queue queue = default_queue();
        reserve(size, queue);
        queue.finish();
    }

    void shrink_to_fit(command_queue &queue)
    {
        pointer old_data = m_data;
        m_data = pointer(); // null pointer
        if(m_size > 0)
        {
            // allocate new buffer
            m_data = m_allocator.allocate(m_size);

            // copy old values to the new buffer
            ::boost::compute::copy(old_data, old_data + m_size, m_data, queue);
        }

        if(capacity() > 0)
        {
            // free old memory
            m_allocator.deallocate(old_data, capacity());
        }
    }

    void shrink_to_fit()
    {
        command_queue queue = default_queue();
        shrink_to_fit(queue);
        queue.finish();
    }

    reference operator[](size_type index)
    {
        return *(begin() + static_cast<difference_type>(index));
    }

    const_reference operator[](size_type index) const
    {
        return *(begin() + static_cast<difference_type>(index));
    }

    reference at(size_type index)
    {
        if(index >= size()){
            BOOST_THROW_EXCEPTION(std::out_of_range("index out of range"));
        }

        return operator[](index);
    }

    const_reference at(size_type index) const
    {
        if(index >= size()){
            BOOST_THROW_EXCEPTION(std::out_of_range("index out of range"));
        }

        return operator[](index);
    }

    reference front()
    {
        return *begin();
    }

    const_reference front() const
    {
        return *begin();
    }

    reference back()
    {
        return *(end() - static_cast<difference_type>(1));
    }

    const_reference back() const
    {
        return *(end() - static_cast<difference_type>(1));
    }

    template<class InputIterator>
    void assign(InputIterator first,
                InputIterator last,
                command_queue &queue)
    {
        // resize vector for new contents
        resize(detail::iterator_range_size(first, last), queue);

        // copy values into the vector
        ::boost::compute::copy(first, last, begin(), queue);
    }

    template<class InputIterator>
    void assign(InputIterator first, InputIterator last)
    {
        command_queue queue = default_queue();
        assign(first, last, queue);
        queue.finish();
    }

    void assign(size_type n, const T &value, command_queue &queue)
    {
        // resize vector for new contents
        resize(n, queue);

        // fill vector with value
        ::boost::compute::fill_n(begin(), n, value, queue);
    }

    void assign(size_type n, const T &value)
    {
        command_queue queue = default_queue();
        assign(n, value, queue);
        queue.finish();
    }

    /// Inserts \p value at the end of the vector (resizing if neccessary).
    ///
    /// Note that calling \c push_back() to insert data values one at a time
    /// is inefficient as there is a non-trivial overhead in performing a data
    /// transfer to the device. It is usually better to store a set of values
    /// on the host (for example, in a \c std::vector) and then transfer them
    /// in bulk using the \c insert() method or the copy() algorithm.
    void push_back(const T &value, command_queue &queue)
    {
        insert(end(), value, queue);
    }

    /// \overload
    void push_back(const T &value)
    {
        command_queue queue = default_queue();
        push_back(value, queue);
        queue.finish();
    }

    void pop_back(command_queue &queue)
    {
        resize(size() - 1, queue);
    }

    void pop_back()
    {
        command_queue queue = default_queue();
        pop_back(queue);
        queue.finish();
    }

    iterator insert(iterator position, const T &value, command_queue &queue)
    {
        if(position == end()){
            resize(m_size + 1, queue);
            position = begin() + position.get_index();
            ::boost::compute::copy_n(&value, 1, position, queue);
        }
        else {
            ::boost::compute::vector<T, Alloc> tmp(position, end(), queue);
            resize(m_size + 1, queue);
            position = begin() + position.get_index();
            ::boost::compute::copy_n(&value, 1, position, queue);
            ::boost::compute::copy(tmp.begin(), tmp.end(), position + 1, queue);
        }

        return position + 1;
    }

    iterator insert(iterator position, const T &value)
    {
        command_queue queue = default_queue();
        iterator iter = insert(position, value, queue);
        queue.finish();
        return iter;
    }

    void insert(iterator position,
                size_type count,
                const T &value,
                command_queue &queue)
    {
        ::boost::compute::vector<T, Alloc> tmp(position, end(), queue);
        resize(size() + count, queue);

        position = begin() + position.get_index();

        ::boost::compute::fill_n(position, count, value, queue);
        ::boost::compute::copy(
            tmp.begin(),
            tmp.end(),
            position + static_cast<difference_type>(count),
            queue
        );
    }

    void insert(iterator position, size_type count, const T &value)
    {
        command_queue queue = default_queue();
        insert(position, count, value, queue);
        queue.finish();
    }

    /// Inserts the values in the range [\p first, \p last) into the vector at
    /// \p position using \p queue.
    template<class InputIterator>
    void insert(iterator position,
                InputIterator first,
                InputIterator last,
                command_queue &queue)
    {
        ::boost::compute::vector<T, Alloc> tmp(position, end(), queue);

        size_type count = detail::iterator_range_size(first, last);
        resize(size() + count, queue);

        position = begin() + position.get_index();

        ::boost::compute::copy(first, last, position, queue);
        ::boost::compute::copy(
            tmp.begin(),
            tmp.end(),
            position + static_cast<difference_type>(count),
            queue
        );
    }

    /// \overload
    template<class InputIterator>
    void insert(iterator position, InputIterator first, InputIterator last)
    {
        command_queue queue = default_queue();
        insert(position, first, last, queue);
        queue.finish();
    }

    iterator erase(iterator position, command_queue &queue)
    {
        return erase(position, position + 1, queue);
    }

    iterator erase(iterator position)
    {
        command_queue queue = default_queue();
        iterator iter = erase(position, queue);
        queue.finish();
        return iter;
    }

    iterator erase(iterator first, iterator last, command_queue &queue)
    {
        if(last != end()){
            ::boost::compute::vector<T, Alloc> tmp(last, end(), queue);
            ::boost::compute::copy(tmp.begin(), tmp.end(), first, queue);
        }

        difference_type count = std::distance(first, last);
        resize(size() - static_cast<size_type>(count), queue);

        return begin() + first.get_index() + count;
    }

    iterator erase(iterator first, iterator last)
    {
        command_queue queue = default_queue();
        iterator iter = erase(first, last, queue);
        queue.finish();
        return iter;
    }

    /// Swaps the contents of \c *this with \p other.
    void swap(vector &other)
    {
        std::swap(m_data, other.m_data);
        std::swap(m_size, other.m_size);
        std::swap(m_allocator, other.m_allocator);
    }

    /// Removes all elements from the vector.
    void clear()
    {
        m_size = 0;
    }

    allocator_type get_allocator() const
    {
        return m_allocator;
    }

    /// Returns the underlying buffer.
    const buffer& get_buffer() const
    {
        return m_data.get_buffer();
    }

    /// \internal_
    ///
    /// Returns a command queue usable to issue commands for the vector's
    /// memory buffer. This is used when a member function is called without
    /// specifying an existing command queue to use.
    command_queue default_queue() const
    {
        const context &context = m_allocator.get_context();
        command_queue queue(context, context.get_device());
        return queue;
    }

private:
    /// \internal_
    BOOST_CONSTEXPR size_type _minimum_capacity() const { return 4; }

    /// \internal_
    BOOST_CONSTEXPR float _growth_factor() const { return 1.5; }

private:
    pointer m_data;
    size_type m_size;
    allocator_type m_allocator;
};

namespace detail {

// set_kernel_arg specialization for vector<T>
template<class T, class Alloc>
struct set_kernel_arg<vector<T, Alloc> >
{
    void operator()(kernel &kernel_, size_t index, const vector<T, Alloc> &vector)
    {
        kernel_.set_arg(index, vector.get_buffer());
    }
};

// for capturing vector<T> with BOOST_COMPUTE_CLOSURE()
template<class T, class Alloc>
struct capture_traits<vector<T, Alloc> >
{
    static std::string type_name()
    {
        return std::string("__global ") + ::boost::compute::type_name<T>() + "*";
    }
};

// meta_kernel streaming operator for vector<T>
template<class T, class Alloc>
meta_kernel& operator<<(meta_kernel &k, const vector<T, Alloc> &vector)
{
  return k << k.get_buffer_identifier<T>(vector.get_buffer());
}

} // end detail namespace
} // end compute namespace
} // end boost namespace

#endif // BOOST_COMPUTE_CONTAINER_VECTOR_HPP