List

module ws.list;

import io = ws.io;
import std.conv;

struct List(T) {

    T opIndex(size_t idx){
        assert(idx < length);
        Iterator it = first;
        while(idx--) it = it.next;
        return it.obj;
    }

    void opOpAssign(string op)(T e){
        static if(op=="~")
            push(e);
        else static if(op=="-")
            remove(e);
        else static assert(0, "Operator " ~ op ~ " not implemented");
    }

    void push(T e){
        if(!first){
            first = new Iterator;
            first.obj = e;
            last = first;
        }else{
            last.next = new Iterator;
            last.next.prev = last;
            last.next.obj = e;
            last = last.next;
        }
        ++size;
    }

    void pushFront(T e){
        if(!first){
            first = new Iterator;
            first.obj = e;
            last = first;
        }else{
            first.prev = new Iterator;
            first.prev.next = first;
            first.prev.obj = e;
            first = first.prev;
        }
        ++size;
    }

    ref T popBack(){
        assert(size, "list is empty");
        auto tmp = last;
        if(last.prev){
            last.prev.next = null;
            last = last.prev;
        }else{
            first = null;
            last = null;
        }
        --size;
        return tmp.obj;
    }

    ref T popFront(){
        assert(size, "list is empty");
        auto tmp = first;
        if(first.next){
            first.next.prev = null;
            first = first.next;
        }else{
            first = null;
            last = null;
        }
        --size;
        return tmp.obj;
    }

    void remove(T e){
        auto it = first;
        while(it){
            if(it.obj == e) break;
            it = it.next;
        }
        if(!it)
            throw new Exception("element not in list");
        if(it.prev) it.prev.next = it.next;
        else first = it.next;
        if(it.next) it.next.prev = it.prev;
        else last = it.prev;
        --size;
    }

    int opApply(int delegate(ref T) dg){
        int result = 0;
        auto it = first;
        while(it){
            auto obj = it.obj;
            it = it.next;
            result = dg(obj);
            if(result) break;
        }
        return result;
    }

    int opApplyReverse(int delegate(ref T) dg){
        int result = 0;
        auto it = last;
        while(it){
            auto obj = it.obj;
            it = it.prev;
            result = dg(obj);
            if(result) break;
        }
        return result;
    }

    @property string toString(){
        string tmp = "List!" ~ typeid(T).toString ~ " = [\n";
        auto it = first;
        while(it){
            tmp ~= "\t" ~ to!string(it.obj) ~ ",\n";
            it = it.next;
        }
        tmp ~= "]";
        return tmp;
    }

    @property bool empty() const {
        return !first;
    }

    @property size_t length(){
        return size;
    }

    @property T front(){
        return first.obj;
    }

    @property T back(){
        return last.obj;
    }

    @property Iterator begin(){
        return first;
    }

    @property Iterator end(){
        return last;
    }

    @property List save(){
        List n;
        for(auto it = first; it != last; it = it.next)
            n.push(it.obj);
        return n;
    }

    private:

        Iterator first;
        Iterator last;
        size_t size;

        class Iterator {
            Iterator next;
            Iterator prev;
            T obj;
        }

    unittest {
        List!int test;
        test.push(5);
        test.push(10);

        assert(test[0]*test[1] == 5*10);

        test.remove(5);

        assert(test[0] == 10);

        test.push(11);
        test.push(12);

        foreach(i; test)
            if(i == 11){
                test.remove(i);
                test.push(100);
            }

        assert(test[0] == 10);
        assert(test[1] == 12);
        assert(test[2] == 100);
        assert(test.length == 3);

        foreach(i; test)
            test.popFront();
    }

}