/************************************************************
*
* Licensed to the Apache Software Foundation (ASF) under one
* or more contributor license agreements.  See the NOTICE file
* distributed with this work for additional information
* regarding copyright ownership.  The ASF licenses this file
* to you 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 SINGA_UTILS_SAFE_QUEUE_H_
#define SINGA_UTILS_SAFE_QUEUE_H_

#include <algorithm>
#include <queue>
#include <list>
#include <mutex>
#include <condition_variable>
#include <thread>

/**
 * Thread-safe queue.
 */
template <typename T, class Container = std::queue<T>>
class SafeQueue {
 public:
  SafeQueue() = default;
  ~SafeQueue() {
    std::lock_guard<std::mutex> lock(mutex_);
  }

  /**
   * Push an element into the queue. Blocking operation.
   * @return true if success;
   */
  bool Push(const T& e) {
    std::lock_guard<std::mutex> lock(mutex_);
    queue_.push(e);
    condition_.notify_one();
    return true;
  }

  /**
   * Pop an element from the queue.
   * It will be blocked until one element is poped.
   */
  void Pop(T& e) {
    std::unique_lock<std::mutex> lock(mutex_);
    condition_.wait(lock, [this]() { return !queue_.empty(); });
    e = queue_.front();
    queue_.pop();
  }
  /**
   * Pop an item from the queue until one element is poped or timout.
   * @param[in] timeout, return false after waiting this number of microseconds
   */
  bool Pop(T& item, std::uint64_t timeout) {
    std::unique_lock<std::mutex> lock(mutex_);

    if (queue_.empty()) {
      if (timeout == 0)
        return false;

      if (condition_.wait_for(lock, std::chrono::microseconds(timeout))
          == std::cv_status::timeout)
        return false;
    }

    item = queue_.front();
    queue_.pop();
    return true;
  }

  /**
   *  Try to pop an element from the queue.
   * \return false the queue is empty now.
   */
  bool TryPop(T& e) {
    std::unique_lock<std::mutex> lock(mutex_);

    if (queue_.empty())
      return false;

    e = queue_.front();
    queue_.pop();
    return true;
  }


  /**
   * @return Number of elements in the queue.
   */
  unsigned int Size() const {
    std::lock_guard<std::mutex> lock(mutex_);
    return queue_.size();
  }

 private:
  Container queue_;
  mutable std::mutex mutex_;
  std::condition_variable condition_;
};

/**
 * Thread safe priority queue.
 */
template<typename T>
class PriorityQueue {
 public:
  PriorityQueue() = default;
  /**
   * Push an element into the queue with a given priority.
   * The queue should not be a priority queue.
   * @return true if success; otherwise false, e.g., due to capacity constraint.
   */
  bool Push(const T& e, int priority) {
    Element ele;
    ele.data = e;
    ele.priority = priority;
    queue_.push(ele);
    return true;
  }

  /**
   * Pop an element from the queue with the highest priority.
   * It blocks until one element is poped.
   */
  void Pop(T& e) {
    Element ele;
    queue_.pop(ele);
    e = ele.data;
  }
  /**
   * Pop the item with the highest priority from the queue until one element is
   * poped or timeout.
   * @param[in] timeout, return false if no element is poped after this number
   * of microseconds.
   */
  bool Pop(T& e, std::uint64_t timeout) {
    Element ele;
    if (queue_.pop(ele, timeout)) {
      e = ele.data;
      return true;
    } else {
      return false;
    }
  }

  /**
   * Try to pop an element from the queue.
   * @return false if the queue is empty now.
   */
  bool TryPop(T& e) {
    Element ele;
    if (queue_.TryPop(ele)) {
      e = ele.data;
      return true;
    } else {
      return false;
    }
  }

  /**
   * @return Number of elements in the queue.
   */
  unsigned int Size() const {
    return queue_.Size();
  }

 private:
  struct Element {
    T data;
    int priority;
    inline bool operator<(const Element &other) const {
      return priority < other.priority;
    }
  };

  SafeQueue<Element, std::priority_queue<Element>> queue_;
};

#endif  // SINGA_UTILS_SAFE_QUEUE_H_