// Copyright (c) 2013, the Dart project authors.  Please see the AUTHORS file
// for details. All rights reserved. Use of this source code is governed by a
// BSD-style license that can be found in the LICENSE file.

part of dart.io;

// Timer heap implemented as a array-based binary heap[0].
// This allows for O(1) `first`, O(log(n)) `remove`/`removeFirst` and O(log(n))
// `add`.
//
// To ensure the timers are ordered by insertion time, the _Timer class has a
// `_id` field set when added to the heap.
//
// [0] http://en.wikipedia.org/wiki/Binary_heap
class _TimerHeap {
  List<_Timer> _list;
  int _used = 0;

  _TimerHeap([int initSize = 7])
      : _list = new List<_Timer>(initSize);

  bool get isEmpty => _used == 0;
  bool get isNotEmpty => _used > 0;

  _Timer get first => _list[0];

  bool isFirst(_Timer timer) => timer._indexOrNext == 0;

  void add(_Timer timer) {
    if (_used == _list.length) {
      _resize();
    }
    timer._indexOrNext = _used++;
    _list[timer._indexOrNext] = timer;
    _bubbleUp(timer);
  }

  _Timer removeFirst() {
    var f = first;
    remove(f);
    return f;
  }

  void remove(_Timer timer) {
    _used--;
    timer._id = -1;
    if (isEmpty) {
      _list[0] = null;
      timer._indexOrNext = null;
      return;
    }
    var last = _list[_used];
    if (!identical(last, timer)) {
      last._indexOrNext = timer._indexOrNext;
      _list[last._indexOrNext] = last;
      if (last._compareTo(timer) < 0) {
        _bubbleUp(last);
      } else {
        _bubbleDown(last);
      }
    }
    _list[_used] = null;
    timer._indexOrNext = null;
  }

  void _resize() {
    var newList = new List(_list.length * 2 + 1);
    newList.setRange(0, _used, _list);
    _list = newList;
  }

  void _bubbleUp(_Timer timer) {
    while (!isFirst(timer)) {
      Timer parent = _parent(timer);
      if (timer._compareTo(parent) < 0) {
        _swap(timer, parent);
      } else {
        break;
      }
    }
  }

  void _bubbleDown(_Timer timer) {
    while (true) {
      int leftIndex = _leftChildIndex(timer._indexOrNext);
      int rightIndex = _rightChildIndex(timer._indexOrNext);
      _Timer newest = timer;
      if (leftIndex < _used && _list[leftIndex]._compareTo(newest) < 0) {
        newest = _list[leftIndex];
      }
      if (rightIndex < _used && _list[rightIndex]._compareTo(newest) < 0) {
        newest = _list[rightIndex];
      }
      if (identical(newest, timer)) {
        // We are where we should be, break.
        break;
      }
      _swap(newest, timer);
    }
  }

  void _swap(_Timer first, _Timer second) {
    int tmp = first._indexOrNext;
    first._indexOrNext = second._indexOrNext;
    second._indexOrNext = tmp;
    _list[first._indexOrNext] = first;
    _list[second._indexOrNext] = second;
  }

  Timer _parent(_Timer timer) => _list[_parentIndex(timer._indexOrNext)];
  Timer _leftChild(_Timer timer) => _list[_leftChildIndex(timer._indexOrNext)];
  Timer _rightChild(_Timer timer) =>
      _list[_rightChildIndex(timer._indexOrNext)];

  static int _parentIndex(int index) => (index - 1) ~/ 2;
  static int _leftChildIndex(int index) => 2 * index + 1;
  static int _rightChildIndex(int index) => 2 * index + 2;
}

class _Timer implements Timer {
  // Disables the timer.
  static const int _NO_TIMER = -1;

  // Timers are ordered by wakeup time.
  static _TimerHeap _heap = new _TimerHeap();
  static _Timer _firstZeroTimer;
  static _Timer _lastZeroTimer;
  static int _idCount = 0;

  static RawReceivePort _receivePort;
  static bool _handlingCallbacks = false;

  Function _callback;
  int _milliSeconds;
  int _wakeupTime = 0;
  var _indexOrNext;
  int _id = -1;

  static Timer _createTimer(void callback(Timer timer),
                            int milliSeconds,
                            bool repeating) {
    _Timer timer = new _Timer._internal();
    timer._callback = callback;
    if (milliSeconds > 0) {
      // Add one because DateTime.now() is assumed to round down
      // to nearest millisecond, not up, so that time + duration is before
      // duration milliseconds from now. Using micosecond timers like
      // Stopwatch allows detecting that the timer fires early.
      timer._wakeupTime =
          new DateTime.now().millisecondsSinceEpoch + 1 + milliSeconds;
    }
    timer._milliSeconds = repeating ? milliSeconds : -1;
    if (timer._addTimerToHeap()) {
      // The new timer is the first in queue. Update event handler.
      _notifyEventHandler();
    }
    return timer;
  }

  factory _Timer(int milliSeconds, void callback(Timer timer)) {
    return _createTimer(callback, milliSeconds, false);
  }

  factory _Timer.periodic(int milliSeconds, void callback(Timer timer)) {
    return _createTimer(callback, milliSeconds, true);
  }

  _Timer._internal() {}

  bool get _isInHeap => _id >= 0;

  void _clear() {
    _callback = null;
  }

  int _compareTo(_Timer other) {
    int c = _wakeupTime - other._wakeupTime;
    if (c != 0) return c;
    return _id - other._id;
  }

  bool get _repeating => _milliSeconds >= 0;

  bool get isActive => _callback != null;

  // Cancels a set timer. The timer is removed from the timer list and if
  // the given timer is the earliest timer the native timer is reset.
  void cancel() {
    _clear();
    if (!_isInHeap) return;
    assert(_wakeupTime != 0);
    bool update = _firstZeroTimer == null && _heap.isFirst(this);
    _heap.remove(this);
    if (update) {
      _notifyEventHandler();
    }
  }

  void _advanceWakeupTime() {
    assert(_milliSeconds >= 0);
    _wakeupTime += _milliSeconds;
  }

  // Adds a timer to the timer list. Timers with the same wakeup time are
  // enqueued in order and notified in FIFO order.
  bool _addTimerToHeap() {
    if (_wakeupTime == 0) {
      if (_firstZeroTimer == null) {
        _lastZeroTimer = _firstZeroTimer = this;
        return true;
      } else {
        _lastZeroTimer = _lastZeroTimer._indexOrNext = this;
        return false;
      }
    } else {
      _id = _idCount++;
      _heap.add(this);
      return _firstZeroTimer == null && _heap.isFirst(this);
    }
  }


  static void _notifyEventHandler() {
    if (_handlingCallbacks) {
      // While we are already handling callbacks we will not notify the event
      // handler. _handleTimeout will call _notifyEventHandler once all pending
      // timers are processed.
      return;
    }

    if (_firstZeroTimer == null && _heap.isEmpty) {
      // No pending timers: Close the receive port and let the event handler
      // know.
      if (_receivePort != null) {
        _EventHandler._sendData(null, _receivePort, _NO_TIMER);
        _shutdownTimerHandler();
      }
    } else {
      if (_receivePort == null) {
        // Create a receive port and register a message handler for the timer
        // events.
        _createTimerHandler();
      }
      _EventHandler._sendData(null,
                              _receivePort,
                              _firstZeroTimer != null ?
                                  0 : _heap.first._wakeupTime);
    }
  }

  static void _handleTimeout(_) {
    int currentTime = new DateTime.now().millisecondsSinceEpoch;
    // Collect all pending timers.
    var timer = _firstZeroTimer;
    var nextTimer = _lastZeroTimer;
    _firstZeroTimer = _lastZeroTimer = null;
    while (_heap.isNotEmpty && _heap.first._wakeupTime <= currentTime) {
      var next = _heap.removeFirst();
      if (timer == null) {
        nextTimer = timer = next;
      } else {
        nextTimer = nextTimer._indexOrNext = next;
      }
    }

    // Trigger all of the pending timers. New timers added as part of the
    // callbacks will be enqueued now and notified in the next spin at the
    // earliest.
    _handlingCallbacks = true;
    try {
      while (timer != null) {
        var next = timer._indexOrNext;
        timer._indexOrNext = null;
        // One of the timers in the pending_timers list can cancel
        // one of the later timers which will set the callback to
        // null.
        if (timer._callback != null) {
          var callback = timer._callback;
          if (!timer._repeating) {
            // Mark timer as inactive.
            timer._callback = null;
          }
          callback(timer);
          // Re-insert repeating timer if not canceled.
          if (timer._repeating && timer._callback != null) {
            timer._advanceWakeupTime();
            timer._addTimerToHeap();
          }
        }
        timer = next;
      }
    } finally {
      _handlingCallbacks = false;
      _notifyEventHandler();
    }
  }

  // Creates a receive port and registers the timer handler on that
  // receive port.
  static void _createTimerHandler() {
    if(_receivePort == null) {
      _receivePort = new RawReceivePort(_handleTimeout);
    }
  }

  static void _shutdownTimerHandler() {
    _receivePort.close();
    _receivePort = null;
  }
}

// Provide a closure which will allocate a Timer object to be able to hook
// up the Timer interface in dart:isolate with the implementation here.
_getTimerFactoryClosure() {
  return (int milliSeconds, void callback(Timer timer), bool repeating) {
    if (repeating) {
      return new _Timer.periodic(milliSeconds, callback);
    }
    return new _Timer(milliSeconds, callback);
  };
}