aloha.d

/+ dub.json:
{ "dependencies": {"mir-random": "~>0.2.8"} }
+/
import std.container : RedBlackTree;
import std.algorithm : max;


interface Event(Time)
{
    Time time() const @property;
    Event dupImpl() const @property;

    final This dup(this This)() const @property
    {
        return cast(This) dupImpl();
    }
}


interface DurationEvent(Time) : Event!Time
{
    alias beginTime = time;
    Time endTime() const @property;
}


auto duration(Time)(const DurationEvent!Time event)
{
    return event.endTime - event.beginTime;
}


interface World(Time)
{
    Time nowTime();

    void appendEvent(immutable Event!Time event) in{ assert(this.nowTime < event.time); };

    bool hasEvent();
    size_t processEvents(Time limit, bool withEQ = true);
    size_t processNextEvents();
}


class SimpleWorld(Time) : World!Time
{
    this(Time initTime)
    {
        _nowTime = initTime;
        _eventList = new typeof(_eventList)();
    }


    void callbackOnEvent(void delegate(immutable(Event!Time)[]) onEvent) @property
    {
        _onEvent = onEvent;
    }


    void appendEvent(immutable Event!Time event)
    {
        _eventList.insert(event);
    }


    Time nowTime() { return _nowTime; }


    bool hasEvent() { return _eventList.length != 0; }


    size_t processEvents(Time limit, bool withEQ = true)
    {
        size_t cnt;
        while(_eventList.length != 0 && (withEQ ? (_eventList.front.time <= limit) : (_eventList.front.time < limit)))
        {
            immutable(Event!Time)[] list;
            _nowTime = _eventList.front.time;
            while(_eventList.length != 0 && _nowTime == _eventList.front.time){
                list ~= _eventList.front;
                _eventList.removeFront();
            }

            cnt += list.length;
            if(_onEvent) _onEvent(list);
        }

        return cnt;
    }


    size_t processNextEvents()
    {
        if(_eventList.length != 0)
            return processEvents(_eventList.front.time, true);
        else
            return 0;
    }


  private:
    RedBlackTree!(immutable(Event!Time), "a.time < b.time", true) _eventList;
    Time _nowTime;
    void delegate(immutable(Event!Time)[]) _onEvent;
}


class PrimitiveEvent(Time) : Event!Time
{
    this(Time time) { _time = time; }


    Time time() const @property { return _time; }


    Event dupImpl() const @property
    {
        return new typeof(this)(_time);
    }


  private:
    Time _time;
}


interface Thing(Time)
{
    void onEvent(const Event!Time[]);
}


class CollisionDetector(Time)
{
    this() {}


    void callbackOnEvent(void delegate(immutable(DurationEvent!Time)[]) onEvent)
    {
        _onEventDg = onEvent;
    }


    void callbackOnFailure(void delegate(immutable(DurationEvent!Time)[]) onFailure)
    {
        _onFailureDg = onFailure;
    }


    void onEvent(immutable(DurationEvent!Time)[] event)
    {
        this.flush(event[0].beginTime);

        foreach(e; event)
            _mixedPacket.mix(e);
    }


    void flush(Time flushTime = Time.max)
    {
        _mixedPacket.flush(flushTime, _onEventDg, _onFailureDg);
    }


  private:
    MixedPacket _mixedPacket;
    void delegate(immutable(DurationEvent!Time)[]) _onEventDg;
    void delegate(immutable(DurationEvent!Time)[]) _onFailureDg;


    static struct MixedPacket
    {
        immutable(DurationEvent!Time)[] events;
        Time beginTime;
        Time endTime;


        void flush(Time flushTime,
            void delegate(immutable(DurationEvent!Time)[]) onSuccess,
            void delegate(immutable(DurationEvent!Time)[]) onFailure)
        {
            // パケットが一つも到来してない
            if(events.length == 0) return;

            if(endTime <= flushTime){
                // パケットが1つ == 衝突していない
                if(events.length == 1){
                    if(onSuccess !is null) onSuccess(events);
                }
                else{
                    if(onFailure !is null) onFailure(events);
                }

                events.length = 0;
            }
        }


        void mix(immutable DurationEvent!Time event)
        {
            if(events.length == 0){
                events ~= event;
                beginTime = event.beginTime;
                endTime = event.endTime;
            }else{
                events ~= event;
                endTime = max(endTime, event.endTime);
            }
        }
    }
}


void main()
{
    import std.stdio;
    import std.algorithm;
    import std.range;
    import mir.random;
    import mir.random.variable;

    enum float packetLength = 1;
    enum float totalPackets = 1E6;

    foreach(g; iota(1, 31).map!"a*0.1")
    {
        immutable float totalTime = totalPackets * packetLength / g;

        auto rnd = Random(unpredictableSeed);
        auto erv = ExponentialVariable!double(packetLength / g);

        static
        class TestEvent : DurationEvent!float
        {
            this(float beginTime, float endTime) pure
            {
                _beginTime = beginTime;
                _endTime = endTime;
            }


            float time() const @property { return _beginTime; }
            float endTime() const @property { return _endTime; }
            Event!float dupImpl() const @property { return new TestEvent(_beginTime, _endTime); }

          private:
            float _beginTime, _endTime;
        }

        auto detector = new CollisionDetector!float();

        auto world = new SimpleWorld!float(-1);
        world.callbackOnEvent = delegate(immutable(Event!float)[] events)
        {
            detector.onEvent(cast(immutable(DurationEvent!float)[])events);
        };

        size_t cnt;
        detector.callbackOnEvent = delegate(immutable(DurationEvent!float)[] events)
        {
            cnt += events.length;
        };


        float nowTime = 0;
        while(nowTime < totalTime){
            auto v = nowTime + erv(rnd);
            nowTime = v;
            //writeln(v);
            world.appendEvent(new immutable TestEvent(v, v+1));
            world.processNextEvents();
        }

        writefln("%s : %s", g, cnt / (totalTime / packetLength));
    }
}


//void main()
//{
//    import std.stdio;
//    import std.algorithm;

//    alias Time = float;

//    auto detector = new CollisionDetector!Time();

//    detector.callbackOnEvent = delegate(immutable(DurationEvent!Time)[] events){
//        writeln("Success: ", events.map!"[a.beginTime, a.endTime]");
//    };

//    detector.callbackOnFailure = delegate(immutable(DurationEvent!Time)[] events){
//        writeln("Failure: ", events.map!"[a.beginTime, a.endTime]");
//    };


//    static
//    class TestEvent : DurationEvent!Time
//    {
//        this(Time beginTime, Time endTime) pure
//        {
//            _beginTime = beginTime;
//            _endTime = endTime;
//        }


//        Time time() const @property { return _beginTime; }
//        Time endTime() const @property { return _endTime; }
//        Event!Time dupImpl() const @property { return new TestEvent(_beginTime, _endTime); }

//      private:
//        Time _beginTime, _endTime;
//    }

//    receiver.onEvent([new immutable(TestEvent)(0, 1)]);
//    receiver.onEvent([new immutable(TestEvent)(2, 3)]);
//    receiver.onEvent([new immutable(TestEvent)(3, 4)]);
//    receiver.onEvent([new immutable(TestEvent)(3.1, 4.2)]);
//    receiver.onEvent([new immutable(TestEvent)(3.2, 4.8)]);
//    receiver.onEvent([new immutable(TestEvent)(4.8, 5.0)]);
//    receiver.onEvent([new immutable(TestEvent)(5, 5)]);
//    receiver.flush();
//}

//void main()
//{
//    import core.time;
//    import std.stdio;

//    auto world = new SimpleWorld!(Duration)(0.seconds, (Event!Duration[] e){
//        writefln("%s : %s", e[0].time, e);
//    });

//    assert(world.hasEvent == false);
//    world.appendEvent(new PrimitiveEvent!Duration(1.seconds));
//    world.appendEvent(new PrimitiveEvent!Duration(1.seconds));
//    writeln(world.nowTime);
//    world.processNextEvents().writeln();
//    writeln(world.nowTime);
//}

//import std.stdio;
//import mir.random;
//import mir.random.variable;

//void main()
//{
//    auto rnd = Random(unpredictableSeed);
//    auto erv = ExponentialVariable!double(3.0);

//    uint[100] hist;
//    foreach(i; 0 .. 1000){
//        auto v = prv(rnd);
//        if(v < 100) hist[v] += 1;
//    }

//    foreach(i, e; hist[0 .. 10])
//        writefln("%2d : %3d", i, e);
//}