module cachetools.containers.lists;

private import std.experimental.allocator;
private import std.experimental.allocator.mallocator : Mallocator;
private import std.experimental.logger;
private import std.format;

///
/// N-way multilist
struct MultiDList(T, int N, Allocator = Mallocator)
{
    alias allocator = Allocator.instance;
    struct Node {
        T payload;
        private:
        Link[N] links;
        Node* next(size_t i) @safe @nogc
        {
            return links[i].next;
        }
        Node* prev(size_t i) @safe @nogc
        {
            return links[i].prev;
        }
        alias payload this;
    }
    private 
    {
        struct Link
        {
            Node* prev;
            Node* next;
        }
        Node*[N]    _heads;
        Node*[N]    _tails;
        size_t      _length;
        
    }
    size_t length() const pure nothrow @safe @nogc {
        return _length;
    }

    Node* insert_last(T v) @safe nothrow
    out
    {
        assert(_length>0);
    }
    do
    {
        auto n = make!(Node)(allocator, v);
        static foreach(index;0..N) {
            if ( _heads[index] is null ) {
                _heads[index] = n;
            }
            n.links[index].prev = _tails[index];
            if ( _tails[index] !is null )
            {
                _tails[index].links[index].next = n;
            }
            _tails[index] = n;
        }
        _length++;
        return n;
    }

    void move_to_tail(Node* n, size_t i) @safe @nogc
    in
    {
        assert(i < N);
        assert(_length>0);
    }
    out
    {
        assert(_heads[i] !is null && _tails[i] !is null);
    }
    do
    {
        if ( n == _tails[i] ) {
            return;
        }
        // unlink
        if ( n.links[i].prev is null )
        {
            _heads[i] = n.links[i].next;
        }
        else
        {
            n.links[i].prev.links[i].next = n.links[i].next;
        }
        if ( n.links[i].next is null )
        {
            _tails[i] = n.links[i].prev;
        }
        else
        {
            n.links[i].next.links[i].prev = n.links[i].prev;
        }
        // insert back
        if ( _heads[i] is null ) {
            _heads[i] = n;
        }
        n.links[i].prev = _tails[i];
        if ( _tails[i] !is null )
        {
            _tails[i].links[i].next = n;
        }
        n.links[i].next = null;
        _tails[i] = n;
    }

    void remove(Node* n) nothrow @safe @nogc
    {
        if ( n is null || _length == 0 )
        {
            return;
        }
        static foreach(i;0..N) {
            if ( n.links[i].prev !is null ) {
                n.links[i].prev.links[i].next = n.links[i].next;
            }
            if ( n.links[i].next !is null ) {
                n.links[i].next.links[i].prev = n.links[i].prev;
            }
            if ( n == _tails[i] ) {
                _tails[i] = n.links[i].prev;
            }
            if ( n == _heads[i] ) {
                _heads[i] = n.links[i].next;
            }
        }
        (() @trusted {dispose(allocator, n);})();
        _length--;
    }
    Node* tail(size_t i) pure nothrow @safe @nogc
    {
        return _tails[i];
    }
    Node* head(size_t i) pure nothrow @safe @nogc
    {
        return _heads[i];
    }
    void clear() nothrow @safe @nogc
    {
        while(_length>0)
        {
            auto n = _heads[0];
            remove(n);
        }
    }
}

@safe unittest {
    import std.algorithm;
    import std.stdio;
    import std.range;
    struct Person
    {
        string name;
        int    age;
    }
    MultiDList!(Person*, 2) mdlist;
    Person[3] persons = [{"Alice", 11}, {"Bob", 9}, {"Carl", 10}];
    foreach(i; 0..persons.length)
    {
        mdlist.insert_last(&persons[i]);
    }
    enum NameIndex = 0;
    enum AgeIndex  = 1;
    assert(mdlist.head(NameIndex).payload.name == "Alice");
    assert(mdlist.head(AgeIndex).payload.age == 11);
    assert(mdlist.tail(NameIndex).payload.name == "Carl");
    assert(mdlist.tail(AgeIndex).payload.age == 10);
    auto alice = mdlist.head(NameIndex);
    auto bob = alice.next(NameIndex);
    auto carl = bob.next(NameIndex);
    mdlist.move_to_tail(alice, AgeIndex);
    assert(mdlist.tail(AgeIndex).payload.age == 11);
    mdlist.remove(alice);
    assert(mdlist.head(NameIndex).payload.name == "Bob");
    assert(mdlist.tail(NameIndex).payload.name == "Carl");
    assert(mdlist.head(AgeIndex).payload.age == 9);
    assert(mdlist.tail(AgeIndex).payload.age == 10);
}

struct DList(T, Allocator = Mallocator) {
    this(this) @disable;
    struct Node(T) {
        T payload;
        private Node!T* prev;
        private Node!T* next;
        alias payload this;
    }
    private {
        alias allocator = Allocator.instance;
        Node!T* _head;
        Node!T* _tail;
        ulong   _length;
    }

    invariant {
        assert
        (
            ( _length > 0 && _head !is null && _tail !is null) ||
            ( _length == 0 && _tail is null && _tail is null) ||
            ( _length == 1 && _tail == _head && _head !is null ),
            "length: %s, head: %s, tail: %s".format(_length, _head, _tail)
        );
    }

    ulong length() const pure nothrow @safe @nogc {
        return _length;
    }

    Node!T* insert_last(T v) @safe nothrow
    out
    {
        assert(_length>0);
        assert(_head !is null && _tail !is null);
    }
    do
    {
        auto n = make!(Node!T)(allocator);
        n.payload = v;
        if ( _head is null ) {
            _head = n;
        }
        n.prev = _tail;
        if ( _tail !is null )
        {
            _tail.next = n;
        }
        _tail = n;
        _length++;
        return n;
    }

    alias insertFront = insert_first;
    Node!T* insert_first(T v) @safe nothrow
    out
    {
        assert(_length>0);
        assert(_head !is null && _tail !is null);
    }
    do 
    {
        auto n = make!(Node!T)(allocator);
        n.payload = v;
        if ( _tail is null ) {
            _tail = n;
        }
        n.next = _head;
        if ( _head !is null )
        {
            _head.prev = n;
        }
        _head = n;
        _length++;
        return n;
    }

    bool remove(Node!T* n) @safe @nogc
    in {assert(_length>0);}
    do {
        if ( n.prev ) {
            n.prev.next = n.next;
        }
        if ( n.next ) {
            n.next.prev = n.prev;
        }
        if ( n == _tail ) {
            _tail = n.prev;
        }
        if ( n == _head ) {
            _head = n.next;
        }
        (() @trusted {dispose(allocator, n);})();
        _length--;
        return true;
    }

    void move_to_tail(Node!T* n) @safe @nogc
    in
    {
        assert(_length > 0);
        assert(_head !is null && _tail !is null);
    }
    out {
        assert(_tail == n && n.next is null);
    }
    do
    {
        if ( n == _tail ) {
            return;
        }
        // unlink
        if ( n.prev is null )
        {
            _head = n.next;
        }
        else
        {
            n.prev.next = n.next;
        }
        if ( n.next is null )
        {
            _tail = n.prev;
        }
        else
        {
            n.next.prev = n.prev;
        }
        // insert back
        if ( _head is null ) {
            _head = n;
        }
        n.prev = _tail;
        if ( _tail !is null )
        {
            _tail.next = n;
        }
        n.next = null;
        _tail = n;

        ////debug(cachetools) tracef("n: %s".format(*n));
        //assert(n.next !is null);
        ////debug tracef("m-t-t: %s, tail: %s", *n, *_tail);
        //assert(n.next, "non-tail entry have no 'next' pointer?");
        //if ( _head == n ) {
        //    assert(n.prev is null);
        //    _head = n.next;
        //} else {
        //    n.prev.next = n.next;
        //}
        //// move this node to end
        //n.next.prev = n.prev;
        //n.next = null;
        //tail.next = n;
        //_tail = n;
    }

    Node!T* head() @safe @nogc nothrow {
        return _head;
    }
    Node!T* tail() @safe @nogc nothrow {
        return _tail;
    }
}

struct SList(T, Allocator = Mallocator) {
    this(this) @safe
    {
        // copy items
        _Node!T* __newFirst, __newLast;
        auto f = _first;
        while(f)
        {
            auto v = f.v;
            auto n = make!(_Node!T)(allocator, v);
            if ( __newLast !is null ) {
                __newLast._next = n;
            } else {
                __newFirst = n;
            }
            __newLast = n;
            f = f._next;
        }
        _first = __newFirst;
        _last = __newLast;
    }

    package {
        struct _Node(T) {
            T v;
            _Node!T *_next;
        }
        alias allocator = Allocator.instance;

        ulong _length;
        _Node!T *_first;
        _Node!T *_last;
    }

    invariant {
        assert
        ( 
            ( _length > 0 && _first !is null && _last !is null) ||
            ( _length == 0 && _first is null && _last is null)
        );
    }
    ~this()
    {
        clear();
    }
    ulong length() const pure @nogc @safe nothrow {
        return _length;
    }

    bool empty() @nogc @safe const {
        return _length == 0;
    }

    T front() pure @nogc @safe {
        return _first.v;
    }

    T back() pure @nogc @safe {
        return _last.v;
    }

    T popFront() @nogc @safe nothrow
    in { assert(_first !is null); }
    do {
        T v = _first.v;
        auto next = _first._next;
        (() @trusted {dispose(allocator, _first);})();
        _first = next;
        if ( _first is null ) {
            _last = null;
        }
        _length--;
        return v;
    }
    void clear() @nogc @safe {
        _Node!T* n = _first;
        while( n !is null ) {
            auto next = n._next;
            (() @trusted {dispose(allocator, n);})();
            n = next;
        }
    }
    private struct Range(T) {
        private {
            _Node!T *current;
        }
        auto front() pure nothrow @safe @nogc @property {
            return &current.v;
        }
        void popFront() @safe @nogc nothrow {
            current = current._next;
        }
        bool empty() pure const nothrow @safe @nogc @property {
            return current is null;
        }
    }
    alias opSlice = range;
    auto range() {
        return Range!T(_first);
    }

    void insertFront(T v) @safe nothrow
    out{ assert(_first !is null && _last !is null);}
    do {
        auto n = make!(_Node!T)(allocator, v);
        if ( _first !is null ) {
            n._next = _first;
        }
        _first = n;
        if ( _last is null ) {
            _last = n;
        }
        _length++;
    }

    void insertBack(T v) @safe nothrow
    out{ assert(_first !is null && _last !is null);}
    do {
        auto n = make!(_Node!T)(allocator, v);
        if ( _last !is null ) {
            _last._next = n;
        } else {
            _first = n;
        }
        _last = n;
        _length++;
    }
    bool remove_by_predicate(scope bool delegate(T) @safe @nogc nothrow f) @nogc @trusted nothrow {
        bool removed;
        _Node!T *current = _first;
        _Node!T *prev = null;
        while (current !is null) {
            auto next = current._next;
            if ( !f(current.v) ) {
                prev = current;
                current = next;
                continue;
            }
            // do remove
            _length--;
            removed = true;
            dispose(allocator, current);
            if ( prev is null ) {
                _first = next;                    
            } else {
                prev._next = next;
            }
            if ( next is null ) {
                _last = prev;
            }
        }
        return removed;
    }
}

@safe @nogc unittest {
    SList!int l;
    assert(l.length() == 0);
    l.insertBack(1);
    assert(l.front() == 1);
    assert(l.length() == 1);
    l.insertBack(2);
    assert(l.front() == 1);
    assert(l.back() == 2);
    assert(l.length() == 2);
    //log(l.range());
    l.popFront();
    assert(l.front() == 2);
    assert(l.back() == 2);
    assert(l.length() == 1);
    l.insertBack(3);
    l.insertBack(4);
    //foreach(v; l[]){
    //    log("v=%d\n", *v);
    //}
    //log("---\n");
    bool removed;
    removed = l.remove_by_predicate((n){return n==2;});
    foreach(v; l[]){
        //log("v=%d\n", *v);
    }
    assert(removed);
    assert(l.length()==2);
    //log("---\n");
    removed = l.remove_by_predicate((n){return n==4;});
    foreach(v; l[]){
        //log("v=%d\n", *v);
    }
    assert(removed);
    assert(l.length()==1);
    //log("---\n");
    removed = l.remove_by_predicate((n){return n==3;});
    foreach(v; l[]){
        //log("v=%d\n", *v);
    }
    assert(removed);
    assert(l.length()==0);
    //log("---\n");
    removed = l.remove_by_predicate((n){return n==3;});
    foreach(v; l[]){
        //log("v=%d\n", *v);
    }
    assert(!removed);
    assert(l.length()==0);
    auto l1 = SList!int();
    foreach(i;0..100) {
        l1.insertBack(i);
    }
    while(l.length) {
        l1.popFront();
    }
    foreach(i;0..100) {
        l1.insertFront(i);
    }
    while(l.length) {
        l1.popFront();
    }
}

@safe unittest {
    DList!int dlist;
    auto n1 = dlist.insert_last(1);
    assert(dlist.length == 1);
    dlist.remove(n1);
    assert(dlist.length == 0);

    n1 = dlist.insert_first(1);
    assert(dlist.length == 1);
    dlist.remove(n1);
    assert(dlist.length == 0);

    n1 = dlist.insert_first(1);
    auto n2 = dlist.insert_last(2);
    assert(dlist.length == 2);
    dlist.move_to_tail(n1);
    assert(dlist.head.payload == 2);
    assert(dlist.tail.payload == 1);
}