/*************************************************************************
 *
 * Copyright 2016 Realm Inc.
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 * http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 *
 **************************************************************************/


#pragma once
#ifndef REALM_UTIL_PRIORITY_QUEUE_HPP
#define REALM_UTIL_PRIORITY_QUEUE_HPP

#include <vector>
#include <functional>
#include <algorithm>

namespace realm {
namespace util {


/// PriorityQueue corresponds exactly to `std::priority_queue`, but has the extra feature
/// of allowing iteration and erasure of elements in the queue.
///
/// PriorityQueue only allows const access to its elements, because non-const access
/// would open up the risk of changing the ordering of the elements.
///
/// Note: As opposed to `std::priority_queue`, this does not store elements in a heap
/// internally. Instead, elements are stored in sorted order. Users of this class are
/// allowed to operate on this assumption.
template <class T, class Container = std::vector<T>, class Compare = std::less<typename Container::value_type>>
class PriorityQueue : private Compare {
public:
    using container_type = Container;
    using value_type = typename Container::value_type;
    using size_type = typename Container::size_type;
    using reference = typename Container::reference;
    using const_reference = typename Container::const_reference;
    using const_reverse_iterator = typename Container::const_reverse_iterator;
    using const_iterator = typename Container::const_iterator;

    //@{
    /// Construct a PriorityQueue, optionally providing a comparator object.
    PriorityQueue(const Compare& comparator, const Container& cont);

    explicit PriorityQueue(const Compare& comparator = Compare{}, Container&& cont = Container{});

    template <class InputIt>
    PriorityQueue(InputIt first, InputIt last, const Compare& comparator, const Container& cont);

    template <class InputIt>
    PriorityQueue(InputIt first, InputIt last, const Compare& comparator = Compare{}, Container&& cont = Container{});
    //@}
    // Skipping Allocator-specific template constructors.

    PriorityQueue(const PriorityQueue&) = default;
    PriorityQueue(PriorityQueue&&) = default;
    PriorityQueue& operator=(const PriorityQueue&) = default;
    PriorityQueue& operator=(PriorityQueue&&) = default;

    bool empty() const;
    size_type size() const;

    //@{
    /// Push an element to the priority queue.
    ///
    /// If insertion to the underlying `Container` invalidates
    /// iterators and references, any iterators and references into this
    /// priority queue are also invalidated. By default, this is the case.
    void push(const T& value);
    void push(T&& value);
    //@}

    /// Pop the largest element from the priority queue.
    ///
    /// If `pop_back` on the underlying `Container` invalidates
    /// iterators and references, any iterators and reference into this
    /// priority queue are also invalidated. By default, this is *NOT* the case.
    ///
    /// Calling `pop()` on an empty priority queue is undefined.
    void pop();

    /// Return a reference to the largest element of the priority queue.
    ///
    /// Calling `top()` on an empty priority queue is undefined.
    const_reference top() const;

    /// Pop the top of the queue and return it by moving it out of the queue.
    ///
    /// Note: This method does not exist in `std::priority_queue`.
    ///
    /// Calling `pop_top()` on an empty priorty queue is undefined.
    value_type pop_top();

    // FIXME: emplace() deliberately omitted for simplicity.

    /// Swap the contents of this priority queue with the contents of \a other.
    void swap(PriorityQueue& other);

    // Not in std::priority_queue:

    /// Return an iterator to the beginning of the queue (smallest element first).
    const_iterator begin() const;

    /// Return an iterator to the end of the queue (largest element last);
    const_iterator end() const;

    /// Return a reverse iterator into the priority queue (largest element first).
    const_reverse_iterator rbegin() const;

    /// Return a reverse iterator representing the end of the priority queue (smallest element last).
    const_reverse_iterator rend() const;

    /// Erase element pointed to by \a it.
    ///
    /// Note: This function differs from `std::priority_queue` by returning the erased
    /// element using move semantics.
    ///
    /// Calling `erase()` with a beyond-end iterator (such as what is returned by `end()`)
    /// is undefined.
    value_type erase(const_iterator it);

    /// Remove all elements from the priority queue.
    void clear();

    /// Calls `reserve()` on the underlying `Container`.
    void reserve(size_type);

private:
    Container m_queue;

    const Compare& compare() const;
    Compare& compare();
};


/// Implementation

template <class T, class Container, class Compare>
PriorityQueue<T, Container, Compare>::PriorityQueue(const Compare& comparator, const Container& cont)
    : Compare(comparator)
    , m_queue(cont)
{
}

template <class T, class Container, class Compare>
PriorityQueue<T, Container, Compare>::PriorityQueue(const Compare& comparator, Container&& cont)
    : Compare(comparator)
    , m_queue(std::move(cont))
{
}

template <class T, class Container, class Compare>
template <class InputIt>
PriorityQueue<T, Container, Compare>::PriorityQueue(InputIt first, InputIt last, const Compare& comparator,
                                                    const Container& cont)
    : Compare(comparator)
    , m_queue(cont)
{
    for (auto it = first; it != last; ++it) {
        push(*it);
    }
}

template <class T, class Container, class Compare>
template <class InputIt>
PriorityQueue<T, Container, Compare>::PriorityQueue(InputIt first, InputIt last, const Compare& comparator,
                                                    Container&& cont)
    : Compare(comparator)
    , m_queue(std::move(cont))
{
    for (auto it = first; it != last; ++it) {
        push(*it);
    }
}

template <class T, class Container, class Compare>
typename PriorityQueue<T, Container, Compare>::size_type PriorityQueue<T, Container, Compare>::size() const
{
    return m_queue.size();
}

template <class T, class Container, class Compare>
bool PriorityQueue<T, Container, Compare>::empty() const
{
    return m_queue.empty();
}

template <class T, class Container, class Compare>
void PriorityQueue<T, Container, Compare>::push(const T& element)
{
    auto it = std::lower_bound(m_queue.begin(), m_queue.end(), element, compare());
    m_queue.insert(it, element);
}

template <class T, class Container, class Compare>
void PriorityQueue<T, Container, Compare>::push(T&& element)
{
    auto it = std::lower_bound(m_queue.begin(), m_queue.end(), element, compare());
    m_queue.insert(it, std::move(element));
}

template <class T, class Container, class Compare>
void PriorityQueue<T, Container, Compare>::pop()
{
    m_queue.pop_back();
}

template <class T, class Container, class Compare>
typename PriorityQueue<T, Container, Compare>::const_reference PriorityQueue<T, Container, Compare>::top() const
{
    return m_queue.back();
}

template <class T, class Container, class Compare>
typename PriorityQueue<T, Container, Compare>::value_type PriorityQueue<T, Container, Compare>::pop_top()
{
    value_type value = std::move(m_queue.back());
    m_queue.pop_back();
    return value;
}

template <class T, class Container, class Compare>
Compare& PriorityQueue<T, Container, Compare>::compare()
{
    return *this;
}

template <class T, class Container, class Compare>
const Compare& PriorityQueue<T, Container, Compare>::compare() const
{
    return *this;
}

template <class T, class Container, class Compare>
typename PriorityQueue<T, Container, Compare>::const_iterator PriorityQueue<T, Container, Compare>::begin() const
{
    return m_queue.begin();
}

template <class T, class Container, class Compare>
typename PriorityQueue<T, Container, Compare>::const_iterator PriorityQueue<T, Container, Compare>::end() const
{
    return m_queue.end();
}

template <class T, class Container, class Compare>
typename PriorityQueue<T, Container, Compare>::const_reverse_iterator
PriorityQueue<T, Container, Compare>::rbegin() const
{
    return m_queue.rbegin();
}

template <class T, class Container, class Compare>
typename PriorityQueue<T, Container, Compare>::const_reverse_iterator
PriorityQueue<T, Container, Compare>::rend() const
{
    return m_queue.rend();
}

template <class T, class Container, class Compare>
typename PriorityQueue<T, Container, Compare>::value_type
PriorityQueue<T, Container, Compare>::erase(const_iterator it)
{
    // Convert to non-const iterator:
    auto non_const_iterator = m_queue.begin() + (it - m_queue.begin());
    value_type value = std::move(*non_const_iterator);
    m_queue.erase(non_const_iterator);
    return value;
}

template <class T, class Container, class Compare>
void PriorityQueue<T, Container, Compare>::clear()
{
    m_queue.clear();
}

template <class T, class Container, class Compare>
void PriorityQueue<T, Container, Compare>::reserve(size_type sz)
{
    m_queue.reserve(sz);
}

template <class T, class Container, class Compare>
void PriorityQueue<T, Container, Compare>::swap(PriorityQueue& other)
{
    using std::swap;
    swap(m_queue, other.m_queue);
    swap(compare(), other.compare());
}
}
}

#endif // REALM_UTIL_PRIORITY_QUEUE_HPP