//
// timer_queue.hpp
// ~~~~~~~~~~~~~~~
//
// Copyright (c) 2003-2010 Christopher M. Kohlhoff (chris at kohlhoff dot 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)
//

#ifndef BOOST_ASIO_DETAIL_TIMER_QUEUE_HPP
#define BOOST_ASIO_DETAIL_TIMER_QUEUE_HPP

#if defined(_MSC_VER) && (_MSC_VER >= 1200)
# pragma once
#endif // defined(_MSC_VER) && (_MSC_VER >= 1200)

#include <boost/asio/detail/push_options.hpp>

#include <boost/asio/detail/push_options.hpp>
#include <cstddef>
#include <memory>
#include <vector>
#include <boost/config.hpp>
#include <boost/limits.hpp>
#include <boost/asio/detail/pop_options.hpp>

#include <boost/asio/error.hpp>
#include <boost/asio/detail/hash_map.hpp>
#include <boost/asio/detail/op_queue.hpp>
#include <boost/asio/detail/timer_op.hpp>
#include <boost/asio/detail/timer_queue_base.hpp>

namespace boost {
namespace asio {
namespace detail {

template <typename Time_Traits>
class timer_queue
  : public timer_queue_base
{
public:
  // The time type.
  typedef typename Time_Traits::time_type time_type;

  // The duration type.
  typedef typename Time_Traits::duration_type duration_type;

  // Constructor.
  timer_queue()
    : timers_(),
      heap_()
  {
  }

  // Add a new timer to the queue. Returns true if this is the timer that is
  // earliest in the queue, in which case the reactor's event demultiplexing
  // function call may need to be interrupted and restarted.
  bool enqueue_timer(const time_type& time, timer_op* op, void* token)
  {
    // Ensure that there is space for the timer in the heap. We reserve here so
    // that the push_back below will not throw due to a reallocation failure.
    heap_.reserve(heap_.size() + 1);

    // Insert the new timer into the hash.
    typedef typename hash_map<void*, timer>::iterator iterator;
    typedef typename hash_map<void*, timer>::value_type value_type;
    std::pair<iterator, bool> result =
      timers_.insert(value_type(token, timer()));
    result.first->second.op_queue_.push(op);
    if (result.second)
    {
      // Put the new timer at the correct position in the heap.
      result.first->second.time_ = time;
      result.first->second.heap_index_ = heap_.size();
      result.first->second.token_ = token;
      heap_.push_back(&result.first->second);
      up_heap(heap_.size() - 1);
    }

    return (heap_[0] == &result.first->second);
  }

  // Whether there are no timers in the queue.
  virtual bool empty() const
  {
    return heap_.empty();
  }

  // Get the time for the timer that is earliest in the queue.
  virtual long wait_duration_msec(long max_duration) const
  {
    if (heap_.empty())
      return max_duration;

    boost::posix_time::time_duration duration = Time_Traits::to_posix_duration(
        Time_Traits::subtract(heap_[0]->time_, Time_Traits::now()));

    if (duration > boost::posix_time::milliseconds(max_duration))
      duration = boost::posix_time::milliseconds(max_duration);
    else if (duration < boost::posix_time::milliseconds(0))
      duration = boost::posix_time::milliseconds(0);

    return duration.total_milliseconds();
  }

  // Get the time for the timer that is earliest in the queue.
  virtual long wait_duration_usec(long max_duration) const
  {
    if (heap_.empty())
      return max_duration;

    boost::posix_time::time_duration duration = Time_Traits::to_posix_duration(
        Time_Traits::subtract(heap_[0]->time_, Time_Traits::now()));

    if (duration > boost::posix_time::microseconds(max_duration))
      duration = boost::posix_time::microseconds(max_duration);
    else if (duration < boost::posix_time::microseconds(0))
      duration = boost::posix_time::microseconds(0);

    return duration.total_microseconds();
  }

  // Dequeue all timers not later than the current time.
  virtual void get_ready_timers(op_queue<operation>& ops)
  {
    const time_type now = Time_Traits::now();
    while (!heap_.empty() && !Time_Traits::less_than(now, heap_[0]->time_))
    {
      timer* t = heap_[0];
      ops.push(t->op_queue_);
      remove_timer(t);
    }
  }

  // Dequeue all timers.
  virtual void get_all_timers(op_queue<operation>& ops)
  {
    typename hash_map<void*, timer>::iterator i = timers_.begin();
    typename hash_map<void*, timer>::iterator end = timers_.end();
    while (i != end)
    {
      ops.push(i->second.op_queue_);
      typename hash_map<void*, timer>::iterator old_i = i++;
      timers_.erase(old_i);
    }

    heap_.clear();
    timers_.clear();
  }

  // Cancel and dequeue the timers with the given token.
  std::size_t cancel_timer(void* timer_token, op_queue<operation>& ops)
  {
    std::size_t num_cancelled = 0;
    typedef typename hash_map<void*, timer>::iterator iterator;
    iterator it = timers_.find(timer_token);
    if (it != timers_.end())
    {
      while (timer_op* op = it->second.op_queue_.front())
      {
        op->ec_ = boost::asio::error::operation_aborted;
        it->second.op_queue_.pop();
        ops.push(op);
        ++num_cancelled;
      }
      remove_timer(&it->second);
    }
    return num_cancelled;
  }

private:
  // Structure representing a single outstanding timer.
  struct timer
  {
    timer() {}
    timer(const timer&) {}
    void operator=(const timer&) {}

    // The time when the timer should fire.
    time_type time_;

    // The operations waiting on the timer.
    op_queue<timer_op> op_queue_;

    // The index of the timer in the heap.
    size_t heap_index_;

    // The token associated with the timer.
    void* token_;
  };

  // Move the item at the given index up the heap to its correct position.
  void up_heap(size_t index)
  {
    size_t parent = (index - 1) / 2;
    while (index > 0
        && Time_Traits::less_than(heap_[index]->time_, heap_[parent]->time_))
    {
      swap_heap(index, parent);
      index = parent;
      parent = (index - 1) / 2;
    }
  }

  // Move the item at the given index down the heap to its correct position.
  void down_heap(size_t index)
  {
    size_t child = index * 2 + 1;
    while (child < heap_.size())
    {
      size_t min_child = (child + 1 == heap_.size()
          || Time_Traits::less_than(
            heap_[child]->time_, heap_[child + 1]->time_))
        ? child : child + 1;
      if (Time_Traits::less_than(heap_[index]->time_, heap_[min_child]->time_))
        break;
      swap_heap(index, min_child);
      index = min_child;
      child = index * 2 + 1;
    }
  }

  // Swap two entries in the heap.
  void swap_heap(size_t index1, size_t index2)
  {
    timer* tmp = heap_[index1];
    heap_[index1] = heap_[index2];
    heap_[index2] = tmp;
    heap_[index1]->heap_index_ = index1;
    heap_[index2]->heap_index_ = index2;
  }

  // Remove a timer from the heap and list of timers.
  void remove_timer(timer* t)
  {
    // Remove the timer from the heap.
    size_t index = t->heap_index_;
    if (!heap_.empty() && index < heap_.size())
    {
      if (index == heap_.size() - 1)
      {
        heap_.pop_back();
      }
      else
      {
        swap_heap(index, heap_.size() - 1);
        heap_.pop_back();
        size_t parent = (index - 1) / 2;
        if (index > 0 && Time_Traits::less_than(
              heap_[index]->time_, heap_[parent]->time_))
          up_heap(index);
        else
          down_heap(index);
      }
    }

    // Remove the timer from the hash.
    typedef typename hash_map<void*, timer>::iterator iterator;
    iterator it = timers_.find(t->token_);
    if (it != timers_.end())
      timers_.erase(it);
  }

  // A hash of timer token to linked lists of timers.
  hash_map<void*, timer> timers_;

  // The heap of timers, with the earliest timer at the front.
  std::vector<timer*> heap_;
};

} // namespace detail
} // namespace asio
} // namespace boost

#include <boost/asio/detail/pop_options.hpp>

#endif // BOOST_ASIO_DETAIL_TIMER_QUEUE_HPP