/**
 * Copyright 2016 Yahoo 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.
 */

#ifndef LIB_BLOCKINGQUEUE_H_
#define LIB_BLOCKINGQUEUE_H_

#include <boost/thread/mutex.hpp>
#include <boost/thread/condition.hpp>
#include <boost/circular_buffer.hpp>

/**
 * Following structs are defined for holding a predicate in wait() call on condition variables.
 * This is done in order to avoid spurious wake up problem.
 * Details: https://www.justsoftwaresolutions.co.uk/threading/condition-variable-spurious-wakes.html
 */
template<typename Container>
struct QueueNotEmpty {
    const Container& queue_;
    QueueNotEmpty(const Container& queue)
            : queue_(queue) {

    }
    bool operator()() const {
        return !queue_.isEmptyNoMutex();
    }
};

template<typename Container>
struct QueueNotFull {
    const Container& queue_;
    QueueNotFull(const Container& queue)
            : queue_(queue) {

    }
    bool operator()() const {
        return !queue_.isFullNoMutex();
    }
};

template<typename T>
class BlockingQueue {
 public:
    typedef typename boost::circular_buffer<T> Container;
    typedef typename Container::iterator iterator;
    typedef typename Container::const_iterator const_iterator;

    class ReservedSpot {
     public:
        ReservedSpot()
                : queue_(),
                  released_(true) {
        }

        ReservedSpot(BlockingQueue<T>& queue)
                : queue_(&queue),
                  released_(false) {
        }

        ~ReservedSpot() {
            release();
        }

        void release() {
            if (!released_) {
                queue_->releaseReservedSpot();
                released_ = true;
            }
        }

     private:
        BlockingQueue<T>* queue_;
        bool released_;

        friend class BlockingQueue<T> ;
    };

    BlockingQueue(size_t maxSize)
            : maxSize_(maxSize),
              mutex_(),
              queue_(maxSize),
              reservedSpots_(0) {
    }

    bool tryReserve(size_t noOfSpots) {
        assert(noOfSpots <= maxSize_);
        Lock lock(mutex_);
        if(noOfSpots <= maxSize_ - (reservedSpots_ + queue_.size())) {
            reservedSpots_ += noOfSpots;
            return true;
        }
        return false;
    }

    void reserve(size_t noOfSpots) {
        assert(noOfSpots <= maxSize_);
        Lock lock(mutex_);
        while(noOfSpots--) {
            queueFullCondition.wait(lock, QueueNotFull<BlockingQueue<T> >(*this));
            reservedSpots_++;
        }
    }

    void release(size_t noOfSpots) {
        Lock lock(mutex_);
        assert(noOfSpots <= reservedSpots_);
        bool wasFull = isFullNoMutex();
        reservedSpots_ -= noOfSpots;
        lock.unlock();

        if (wasFull) {
            // Notify that one spot is now available
            queueFullCondition.notify_all();
        }
    }

    ReservedSpot reserve() {
        Lock lock(mutex_);
        // If the queue is full, wait for space to be available
        queueFullCondition.wait(lock, QueueNotFull<BlockingQueue<T> >(*this));
        reservedSpots_++;
        return ReservedSpot(*this);
    }

    void push(const T& value, bool wasReserved = false) {
        Lock lock(mutex_);
        if (wasReserved) {
            reservedSpots_--;
        }
        // If the queue is full, wait for space to be available
        queueFullCondition.wait(lock, QueueNotFull<BlockingQueue<T> >(*this));
        bool wasEmpty = queue_.empty();
        queue_.push_back(value);
        lock.unlock();
        if (wasEmpty) {
            // Notify that an element is pushed
            queueEmptyCondition.notify_one();
        }
    }

    void push(const T& value, ReservedSpot& spot) {
        Lock lock(mutex_);

        // Since the value already had a spot reserved in the queue, we need to
        // discount it
        assert(reservedSpots_ > 0);
        reservedSpots_--;
        spot.released_ = true;

        bool wasEmpty = queue_.empty();
        queue_.push_back(value);
        lock.unlock();

        if (wasEmpty) {
            // Notify that an element is pushed
            queueEmptyCondition.notify_one();
        }
    }

    bool tryPush(const T& value) {
        Lock lock(mutex_);

        // Need to consider queue_.size() + reserved spot
        if (isFullNoMutex()) {
            return false;
        }

        bool wasEmpty = queue_.empty();
        queue_.push_back(value);
        lock.unlock();

        if (wasEmpty) {
            // Notify that an element is pushed
            queueEmptyCondition.notify_one();
        }

        return true;
    }

    void pop() {
        Lock lock(mutex_);
        // If the queue is empty, wait until an element is available to be popped
        queueEmptyCondition.wait(lock, QueueNotEmpty<BlockingQueue<T> >(*this));

        bool wasFull = isFullNoMutex();
        queue_.pop_front();
        lock.unlock();

        if (wasFull) {
            // Notify that an element is popped
            queueFullCondition.notify_one();
        }
    }

    void pop(T& value) {
        Lock lock(mutex_);
        // If the queue is empty, wait until an element is available to be popped
        queueEmptyCondition.wait(lock, QueueNotEmpty<BlockingQueue<T> >(*this));
        value = queue_.front();

        bool wasFull = isFullNoMutex();
        queue_.pop_front();
        lock.unlock();

        if (wasFull) {
            // Notify that an element is popped
            queueFullCondition.notify_one();
        }
    }

    bool pop(T& value, const boost::posix_time::time_duration& timeout) {
        Lock lock(mutex_);
        if (!queueEmptyCondition.timed_wait(lock, timeout,
                                            QueueNotEmpty<BlockingQueue<T> >(*this))) {
            return false;
        }

        bool wasFull = isFullNoMutex();
        value = queue_.front();
        queue_.pop_front();
        lock.unlock();

        if (wasFull) {
            // Notify that an element is popped
            queueFullCondition.notify_all();
        }

        return true;
    }

    // Check the 1st element of the queue
    bool peek(T& value) {
        Lock lock(mutex_);
        if (queue_.empty()) {
            return false;
        }

        value = queue_.front();
        return true;
    }

    // Remove all elements from the queue
    void clear() {
        Lock lock(mutex_);
        queue_.clear();
        queueFullCondition.notify_all();
    }

    size_t size() const {
        Lock lock(mutex_);
        return queue_.size();
    }

    size_t maxSize() const {
        return maxSize_;
    }

    bool empty() const {
        Lock lock(mutex_);
        return isEmptyNoMutex();
    }

    bool full() const {
        Lock lock(mutex_);
        return isFullNoMutex();
    }

    const_iterator begin() const {
        return queue_.begin();
    }

    const_iterator end() const {
        return queue_.end();
    }

    iterator begin() {
        return queue_.begin();
    }

    iterator end() {
        return queue_.end();
    }

 private:
    void releaseReservedSpot() {
        Lock lock(mutex_);
        bool wasFull = isFullNoMutex();
        --reservedSpots_;
        lock.unlock();

        if (wasFull) {
            // Notify that one spot is now available
            queueFullCondition.notify_one();
        }
    }

    bool isEmptyNoMutex() const {
        return queue_.empty();
    }

    bool isFullNoMutex() const {
        return (queue_.size() + reservedSpots_) == maxSize_;
    }

    const size_t maxSize_;
    mutable boost::mutex mutex_;
    boost::condition_variable queueFullCondition;
    boost::condition_variable queueEmptyCondition;
    Container queue_;
    int reservedSpots_;

    typedef boost::unique_lock<boost::mutex> Lock;
    friend class QueueReservedSpot;
    friend struct QueueNotEmpty<BlockingQueue<T> > ;
    friend struct QueueNotFull<BlockingQueue<T> > ;
};

#endif /* LIB_BLOCKINGQUEUE_H_ */