#include "jel.h"

/*
Not Implemented:
void Schedule::triggerTime(Uint32 triggerTime)
void Schedule::triggerTime(TimeEventID id)
void Schedule::clearFutureTimeEvents()
TimeEvent Schedule::removeTimeEvent(TimeEventID id)

Dev Note:  Tree
The main part of this library is the sorted tree implementation for the 
TimeEvents.  It is stored as successive links starting from a single Epoch* 
stored in Schedule.  Each Epoch has two branches, first and second.  The tree 
is sorted by time of an event (epoch->event.time).  The "first" link's time is 
always <= the parent's time, which is less than the "second" link's time.  
This means that if a time t has passed and the parent's time is less than t, 
then the "first" link can be ignored.  This lets you skip over lots of old 
events without any further testing.

The initial Epoch* starts off as NULL.  It must be created when the first
element is added and deleted when the last element is erased.

The way to traverse the tree is the follow the "first" links, pushing
the "second" links to a stack.  Once you hit a dead end, you pop the stack
once and follow that link, traversing the "first" links again, pushing the 
"second" links.

The parent node is stable if it's time value lies between its two children.
A node with two children is guaranteed to be stable.  If a new time is added 
and the parent has only one child, then the parent will be swapped if it is 
not a midvalue of the child and the incoming value.  Values are sorted by 
which side of the parent it falls on (equal on left).


Given the sequence 1000, 2000, 1100, 1500, 1700, 2000, 2900, 2800, 2850, 2000

                      1100
                      /  \
                   1000  1700
                          /  \
                        1500 2800
                             /  \
                          2000  2900
                           /    /
                         2000  2850

Given the sequence: 200, 300, 550, 100, 170, 200, 210, 400, 60, 80, 200, 230, 350, 100

                    300
                   /   \
                 170   400
                  / \   /  \
                80  200 550 350
               /  \  / \
             60 100 200 210
                 /    /   \
              100    200  230

*/

namespace JEL
{

    Schedule Schedule::Instance;

	class Epoch
	{
	    public:
		Epoch* first;
		Epoch* second;
		
		TimeEvent event;
		
	    Epoch(const TimeEvent& event)
            : first(NULL), second(NULL), event(event)
	    {}
	    
	    Epoch(const TimeEvent& event, Uint32 time, unsigned int idNum)
            : first(NULL), second(NULL), event(event, time, idNum)
	    {}
	};



void Event::trigger()
{
	if(signal != NULL)
		signal->trigger();
}










ActionEventID Schedule::addActionEvent(const ActionEvent& event)
{
	ActionEvent a = event;
	a.id = actionEvents.size();
	actionEvents.push_back(a);
	return a.id;
}

TimeEventID Schedule::addTimeEvent(const TimeEvent& event, Uint32 absoluteTime)
{
    if(timeEvents == NULL)
    {
        timeEvents = new Epoch(event, absoluteTime, ++lastTimeID);
        return lastTimeID;
    }
    else
    {
        Epoch** parentPtr = &timeEvents;
        Epoch* parent;
        
        
        do
        {
            parent = *parentPtr;
            if(parent->first == NULL)
            {
                if(parent->second == NULL)
                {
                    // No children, just add it
                    if(absoluteTime <= parent->event.time)
                    {
                        parent->first = new Epoch(event, absoluteTime, ++lastTimeID);
                        return lastTimeID;
                    }
                    else
                    {
                        parent->second = new Epoch(event, absoluteTime, ++lastTimeID);
                        return lastTimeID;
                    }
                }
                
                // Second is not NULL, but first is.
                if(absoluteTime <= parent->event.time)
                {
                    parent->first = new Epoch(event, absoluteTime, ++lastTimeID);
                    return lastTimeID;
                }
                else
                {
                    // The parent isn't the middle value.  Swap it.
                    if(absoluteTime < parent->second->event.time)
                    {
                        // P < new < S
                        //     P             new   .
                        //      \    ->      / \   .
                        //       S          P   S  .
                        // Move new one to parent
                        *parentPtr = new Epoch(event, absoluteTime, ++lastTimeID);
                        // Move parent to first
                        (*parentPtr)->first = parent;
                        // Move second to second
                        (*parentPtr)->second = parent->second;
                        // Clear old second
                        parent->second = NULL;
                        return lastTimeID;
                    }
                    else
                    {
                        // P < S < new
                        //     P              S     .
                        //      \    ->      / \    .
                        //       S          P  new  .
                        // Move second to parent
                        *parentPtr = parent->second;
                        // Move parent to first
                        (*parentPtr)->first = parent;
                        // Move new one to second
                        (*parentPtr)->second = new Epoch(event, absoluteTime, ++lastTimeID);
                        // Clear old second
                        parent->second = NULL;
                        return lastTimeID;
                    }
                }
            }
            else if(parent->second == NULL)
            {
                // First is not NULL, but second is.
                if(absoluteTime > parent->event.time)
                {
                    parent->second = new Epoch(event, absoluteTime, ++lastTimeID);
                    return lastTimeID;
                }
                else
                {
                    // The parent isn't the middle value.  Swap it.
                    if(absoluteTime > parent->first->event.time)
                    {
                        //  F < new < P
                        //     P             new   .
                        //    /      ->      / \   .
                        //   F              F   P  .
                        // Move new one to parent
                        *parentPtr = new Epoch(event, absoluteTime, ++lastTimeID);
                        // Move parent to second
                        (*parentPtr)->second = parent;
                        // Move first to first
                        (*parentPtr)->first = parent->first;
                        // Clear old first
                        parent->first = NULL;
                        return lastTimeID;
                    }
                    else
                    {
                        // new < F < P
                        //     P              F    .
                        //    /      ->      / \   .
                        //   F             new  P  .
                        // Move first to parent
                        *parentPtr = parent->first;
                        // Move parent to second
                        (*parentPtr)->second = parent;
                        // Move new one to first
                        (*parentPtr)->first = new Epoch(event, absoluteTime, ++lastTimeID);
                        // Clear old first
                        parent->first = NULL;
                        return lastTimeID;
                    }
                }
                
            }
            else
            {
                // This node is full.  Pass it along.
                if(absoluteTime <= parent->event.time)
                    parentPtr = &(parent->first);
                else
                    parentPtr = &(parent->second);
            }
        }
        while(1);
    }
    
	return 0;
}

TimeEventID Schedule::addTimeEventFromNow(const TimeEvent& event, Uint32 time)
{
	return addTimeEvent(event, this->time + time);
}

void Schedule::clearActionEvents()
{
    actionEvents.clear();
}

void Schedule::clearTimeEvents()
{
    Epoch* epoch = timeEvents;
    
    list<Epoch*> stack;
    Epoch* left;
    Epoch* right;
    while(epoch != NULL)
    {
        left = epoch->first;
        right = epoch->second;
        
        // Delete the head, then progress down the children.
        delete epoch;
        
        if(left == NULL && right == NULL)
        {
            if(stack.size() == 0)
                epoch = NULL;
            else
            {
                epoch = stack.front();
                stack.erase(stack.begin());
            }
            continue;
        }
        
        if(left == NULL)
        {
            epoch = right;
        }
        else
        {
            epoch = left;
            if(right != NULL)
                stack.push_front(right);
        }
    }
    
    timeEvents = NULL;
    
}

void deleteBranch(Epoch* epoch)
{
    list<Epoch*> toDelete;
    
    list<Epoch*> stack;
    Epoch* left;
    Epoch* right;
    while(epoch != NULL)
    {
        left = epoch->first;
        right = epoch->second;
        
            //printf("Deleting time/id: %d/%d\n", epoch->event.time, epoch->event.id.getID());
        // Delete the head, then progress down the children.
        toDelete.push_back(epoch);
        
        if(left == NULL && right == NULL)
        {
            if(stack.size() == 0)
                epoch = NULL;
            else
            {
                epoch = stack.front();
                stack.erase(stack.begin());
            }
            continue;
        }
        
        if(left == NULL)
        {
            epoch = right;
        }
        else
        {
            epoch = left;
            if(right != NULL)
                stack.push_front(right);
        }
    }
    
    for(list<Epoch*>::iterator e = toDelete.begin(); e != toDelete.end(); e++)
        delete *e;
}

void Schedule::clearPastTimeEvents()
{
    Epoch** epochPtr = &timeEvents;
    Epoch* epoch = *epochPtr;
    
    list<Epoch*> toDelete;
    
    list<Epoch**> stack;
    Epoch* left;
    Epoch* right;
    while(1)
    {
        if(epoch == NULL)
        {
            if(stack.size() == 0)
                break;
            else
            {
                epochPtr = stack.front();
                epoch = *epochPtr;
                stack.erase(stack.begin());
            }
            continue;
        }
        
        left = epoch->first;
        right = epoch->second;
        
        if(epoch->event.time <= time)
        {
            //printf("Deleting branch time/id: %d/%d\n", epoch->event.time, epoch->event.id.getID());
            // Epoch is old.  Delete it and left.
            deleteBranch(left);
            epoch->first = NULL;
            
            // Put the next one where the old one was.
            *epochPtr = epoch->second;
            // Delete the old one.
            toDelete.push_back(epoch);
            //delete epoch;
            //epochPtr = &(epoch->second);
            epoch = *epochPtr;
            continue;
        }
        
        
        if(left == NULL)
        {
            epochPtr = &(epoch->second);
            epoch = *epochPtr;
        }
        else
        {
            epochPtr = &(epoch->first);
            epoch = *epochPtr;
            if(right != NULL)
                stack.push_front(&(epoch->second));
        }
    }
    
    // FIXME: This is cheating.  I really need to fix the double-delete somewhere in this function.
    // It seems that an epoch is added twice.
    toDelete.sort();
    toDelete.unique();
    
    for(list<Epoch*>::iterator e = toDelete.begin(); e != toDelete.end(); e++)
        delete *e;
}

void Schedule::clearFutureTimeEvents()
{
    
}

ActionEvent Schedule::removeActionEvent(ActionEventID id)
{
    if(id == 0)
        return ActionEvent();
    
    for(vector<ActionEvent>::iterator e = actionEvents.begin(); e != actionEvents.end(); e++)
    {
        if((*e).id == id)
        {
            ActionEvent a = *e;
            actionEvents.erase(e);
            return a;
        }
    }
    
	return ActionEvent();
}

TimeEvent Schedule::removeTimeEvent(TimeEventID id)
{
    return TimeEvent();
}

ActionEvent Schedule::getActionEvent(ActionEventID id)
{
    if(id == 0)
        return ActionEvent();
    
    for(vector<ActionEvent>::iterator e = actionEvents.begin(); e != actionEvents.end(); e++)
    {
        if((*e).id == id)
            return (*e);
    }
    
	return ActionEvent();
}

TimeEvent Schedule::getTimeEvent(TimeEventID id)
{
    if(id.getID() == 0)
        return TimeEvent();
    
    Epoch* epoch = timeEvents;
    list<Epoch*> stack;
    Epoch* left;
    Epoch* right;
    while(epoch != NULL)
    {
        if(epoch->event.id.getID() == id.getID())
            return epoch->event;
        
        left = epoch->first;
        right = epoch->second;
            
        if(left == NULL && right == NULL)
        {
            //epoch = stack.pop();
            if(stack.size() == 0)
                epoch = NULL;
            else
            {
                epoch = stack.front();
                stack.erase(stack.begin());
            }
            continue;
        }
        
        if(left == NULL)
        {
            epoch = right;
        }
        else
        {
            epoch = left;
            if(right != NULL)
                stack.push_front(right);
        }
    }
    
    return TimeEvent();
}

vector<ActionEvent> Schedule::getAllActionEvents()
{
	return actionEvents;
}

vector<TimeEvent> Schedule::getAllTimeEvents()
{
	vector<TimeEvent> v;
	
    Epoch* epoch = timeEvents;
    list<Epoch*> stack;
    Epoch* left;
    Epoch* right;
    while(epoch != NULL)
    {
        v.push_back(epoch->event);
        
        left = epoch->first;
        right = epoch->second;
        
        if(left == NULL && right == NULL)
        {
            //epoch = stack.pop();
            if(stack.size() == 0)
                epoch = NULL;
            else
            {
                epoch = stack.front();
                stack.erase(stack.begin());
            }
            continue;
        }
        
        if(left == NULL)
        {
            epoch = right;
        }
        else
        {
            epoch = left;
            if(right != NULL)
                stack.push_front(right);
        }
    }
	return v;
}

void Schedule::addActionEvents(const vector<ActionEvent>& events)
{
    for(vector<ActionEvent>::const_iterator e = events.begin(); e != events.end(); e++)
    {
        addActionEvent(*e);
    }
}

void Schedule::addTimeEvents(const vector<TimeEvent>& events)
{
    for(vector<TimeEvent>::const_iterator e = events.begin(); e != events.end(); e++)
    {
        addTimeEvent(*e, e->time);
    }
}


void Schedule::update(Uint32 dt)
{
    Uint32 oldTime = time;
    time += dt;
    
    Epoch* epoch = timeEvents;
    //Stack<Epoch*> stack;
    list<Epoch*> stack;
    Epoch* left;
    Epoch* right;
    while(epoch != NULL)
    {
        left = epoch->first;
        right = epoch->second;
        
        if(epoch->event.time > oldTime && epoch->event.time <= time)
            epoch->event.trigger();
        
        if(left == NULL && right == NULL)
        {
            //epoch = stack.pop();
            if(stack.size() == 0)
                epoch = NULL;
            else
            {
                epoch = stack.front();
                stack.erase(stack.begin());
            }
            continue;
        }
        
        // If the epoch's time is older than the old time, then we can skip the left side.
        // That is, we've already processed the left side at a previous update.
        if(oldTime >= epoch->event.time)
        {
            if(right == NULL)
            {
                //epoch = stack.pop();
                if(stack.size() == 0)
                    epoch = NULL;
                else
                {
                    epoch = stack.front();
                    stack.erase(stack.begin());
                }
            }
            else
                epoch = right;
            continue;
        }
        
        // If the epoch's time has not come yet, we can skip the right branch (they're all in the future too).
        if(epoch->event.time > time)
        {
            if(left == NULL)
            {
                //epoch = stack.pop();
                if(stack.size() == 0)
                    epoch = NULL;
                else
                {
                    epoch = stack.front();
                    stack.erase(stack.begin());
                }
            }
            else
                epoch = left;
            continue;
        }
        
        if(left == NULL)
        {
            epoch = right;
        }
        else
        {
            epoch = left;
            if(right != NULL)
                stack.push_front(right);
        }
    }
}


void Schedule::setTime(Uint32 time)
{
    this->time = time;
}

Uint32 Schedule::getTime()
{
    return time;
}

// Trigger is here so I can search down iteratively, instead of recursively.  I think this is cheaper and faster.
void Schedule::triggerTime(Uint32 triggerTime)  // Recursively searches for and triggers any events that have a trigger time earlier than the given time.
{}

void Schedule::triggerAction(ActionEventID id)
{
	if(id < int(actionEvents.size()))
		actionEvents[id].trigger();
}

void Schedule::triggerTime(TimeEventID id)
{}


}  // END namespace JEL 
