/*
 * Copyright (C) 2014 The Android Open Source Project
 *
 * 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.
 */

package com.android.internal.midi;

import java.util.Iterator;
import java.util.SortedMap;
import java.util.TreeMap;

Store arbitrary timestamped events using a Long timestamp.
Only one Thread can write into the buffer.
And only one Thread can read from the buffer.
/**
 * Store arbitrary timestamped events using a Long timestamp.
 * Only one Thread can write into the buffer.
 * And only one Thread can read from the buffer.
 */
public class EventScheduler {
    private static final long NANOS_PER_MILLI = 1000000;

    private final Object mLock = new Object();
    volatile private SortedMap<Long, FastEventQueue> mEventBuffer;
    private FastEventQueue mEventPool = null;
    private int mMaxPoolSize = 200;
    private boolean mClosed;

    public EventScheduler() {
        mEventBuffer = new TreeMap<Long, FastEventQueue>();
    }

    // If we keep at least one node in the list then it can be atomic
    // and non-blocking.
    private class FastEventQueue {
        // One thread takes from the beginning of the list.
        volatile SchedulableEvent mFirst;
        // A second thread returns events to the end of the list.
        volatile SchedulableEvent mLast;
        volatile long mEventsAdded;
        volatile long mEventsRemoved;

        FastEventQueue(SchedulableEvent event) {
            mFirst = event;
            mLast = mFirst;
            mEventsAdded = 1;
            mEventsRemoved = 0;
        }

        int size() {
            return (int)(mEventsAdded - mEventsRemoved);
        }

        
Do not call this unless there is more than one event
in the list.
Returns:
first event in the list/**
         * Do not call this unless there is more than one event
         * in the list.
         * @return first event in the list
         */
        public SchedulableEvent remove() {
            // Take first event.
            mEventsRemoved++;
            SchedulableEvent event = mFirst;
            mFirst = event.mNext;
            event.mNext = null;
            return event;
        }

        
Params:
event – /**
         * @param event
         */
        public void add(SchedulableEvent event) {
            event.mNext = null;
            mLast.mNext = event;
            mLast = event;
            mEventsAdded++;
        }
    }

    
Base class for events that can be stored in the EventScheduler.
/**
     * Base class for events that can be stored in the EventScheduler.
     */
    public static class SchedulableEvent {
        private long mTimestamp;
        volatile private SchedulableEvent mNext = null;

        
Params:
timestamp – /**
         * @param timestamp
         */
        public SchedulableEvent(long timestamp) {
            mTimestamp = timestamp;
        }

        
Returns:
timestamp/**
         * @return timestamp
         */
        public long getTimestamp() {
            return mTimestamp;
        }

        
The timestamp should not be modified when the event is in the
scheduling buffer.
/**
         * The timestamp should not be modified when the event is in the
         * scheduling buffer.
         */
        public void setTimestamp(long timestamp) {
            mTimestamp = timestamp;
        }
    }

    
Get an event from the pool.
Always leave at least one event in the pool.
Returns:
event or null/**
     * Get an event from the pool.
     * Always leave at least one event in the pool.
     * @return event or null
     */
    public SchedulableEvent removeEventfromPool() {
        SchedulableEvent event = null;
        if (mEventPool != null && (mEventPool.size() > 1)) {
            event = mEventPool.remove();
        }
        return event;
    }

    
Return events to a pool so they can be reused.
Params:
event – /**
     * Return events to a pool so they can be reused.
     *
     * @param event
     */
    public void addEventToPool(SchedulableEvent event) {
        if (mEventPool == null) {
            mEventPool = new FastEventQueue(event);
        // If we already have enough items in the pool then just
        // drop the event. This prevents unbounded memory leaks.
        } else if (mEventPool.size() < mMaxPoolSize) {
            mEventPool.add(event);
        }
    }

    
Add an event to the scheduler. Events with the same time will be
processed in order.
Params:
event – /**
     * Add an event to the scheduler. Events with the same time will be
     * processed in order.
     *
     * @param event
     */
    public void add(SchedulableEvent event) {
        synchronized (mLock) {
            FastEventQueue list = mEventBuffer.get(event.getTimestamp());
            if (list == null) {
                long lowestTime = mEventBuffer.isEmpty() ? Long.MAX_VALUE
                        : mEventBuffer.firstKey();
                list = new FastEventQueue(event);
                mEventBuffer.put(event.getTimestamp(), list);
                // If the event we added is earlier than the previous earliest
                // event then notify any threads waiting for the next event.
                if (event.getTimestamp() < lowestTime) {
                    mLock.notify();
                }
            } else {
                list.add(event);
            }
        }
    }

    private SchedulableEvent removeNextEventLocked(long lowestTime) {
        SchedulableEvent event;
        FastEventQueue list = mEventBuffer.get(lowestTime);
        // Remove list from tree if this is the last node.
        if ((list.size() == 1)) {
            mEventBuffer.remove(lowestTime);
        }
        event = list.remove();
        return event;
    }

    
Check to see if any scheduled events are ready to be processed.
Params:
timestamp – 
Returns:
next event or null if none ready/**
     * Check to see if any scheduled events are ready to be processed.
     *
     * @param timestamp
     * @return next event or null if none ready
     */
    public SchedulableEvent getNextEvent(long time) {
        SchedulableEvent event = null;
        synchronized (mLock) {
            if (!mEventBuffer.isEmpty()) {
                long lowestTime = mEventBuffer.firstKey();
                // Is it time for this list to be processed?
                if (lowestTime <= time) {
                    event = removeNextEventLocked(lowestTime);
                }
            }
        }
        // Log.i(TAG, "getNextEvent: event = " + event);
        return event;
    }

    
Return the next available event or wait until there is an event ready to
be processed. This method assumes that the timestamps are in nanoseconds
and that the current time is System.nanoTime().
Throws:
InterruptedException – 
Returns:
event/**
     * Return the next available event or wait until there is an event ready to
     * be processed. This method assumes that the timestamps are in nanoseconds
     * and that the current time is System.nanoTime().
     *
     * @return event
     * @throws InterruptedException
     */
    public SchedulableEvent waitNextEvent() throws InterruptedException {
        SchedulableEvent event = null;
        synchronized (mLock) {
            while (!mClosed) {
                long millisToWait = Integer.MAX_VALUE;
                if (!mEventBuffer.isEmpty()) {
                    long now = System.nanoTime();
                    long lowestTime = mEventBuffer.firstKey();
                    // Is it time for the earliest list to be processed?
                    if (lowestTime <= now) {
                        event = removeNextEventLocked(lowestTime);
                        break;
                    } else {
                        // Figure out how long to sleep until next event.
                        long nanosToWait = lowestTime - now;
                        // Add 1 millisecond so we don't wake up before it is
                        // ready.
                        millisToWait = 1 + (nanosToWait / NANOS_PER_MILLI);
                        // Clip 64-bit value to 32-bit max.
                        if (millisToWait > Integer.MAX_VALUE) {
                            millisToWait = Integer.MAX_VALUE;
                        }
                    }
                }
                mLock.wait((int) millisToWait);
            }
        }
        return event;
    }

    protected void flush() {
        // Replace our event buffer with a fresh empty one
        mEventBuffer = new TreeMap<Long, FastEventQueue>();
    }

    public void close() {
        synchronized (mLock) {
            mClosed = true;
            mLock.notify();
        }
    }
}