/*
This is experimental code still:
- the code is raw still
- it lacks commentes
- it does the bare minimum (append one item and extract the array),
  extend is absent still
- unit tests are messy still
*/


import std.stdio: put = writef, putr = writefln;
import std.gc: gcmalloc = malloc, gcrealloc = realloc, hasNoPointers;
import std.conv: toInt;


//---------------------------------------------------------------
// Correct starting point
class ArrayBuilderBasic(T) {
    private T[] data;

    void opCatAssign(T x) {
        this.data ~= x;
    }

    T[] toarray() {
        return this.data;
    }
}


//---------------------------------------------------------------
// useless naive version
class ArrayBuilderNaive(T) {
    private T* data;
    private int len;

    this() {
        this.len = 0;
        this.data = cast(T*)malloc(this.len * T.sizeof);
    }

    void opCatAssign(T x) {
        this.len++;
        this.data = cast(T*)realloc(this.data, this.len * T.sizeof);
        this.data[this.len - 1] = x;
    }

    T[] toarray() {
        return this.data[0 .. this.len];
    }
}


//=============================================================
// Minimal potentially usabe version

import std.traits: FieldTypeTuple;

class ArgumentException: Exception {
    this(string msg) {
        super(msg);
    }
}

template IsType(T, Types...) {
    // Original idea by Burton Radons, modified
    static if (Types.length == 0)
        const bool IsType = false;
    else
        const bool IsType = is(T == Types[0]) || IsType!(T, Types[1 .. $]);
}


// HasReferences and IsReferenceType may be merged in a single template
template HasReferences(Types...) {
    static if (Types.length == 0)
        const bool HasReferences = false;
    else
        const bool HasReferences = IsReferenceType!(Types[0]) |
                                   HasReferences!(Types[1 .. $]);
}

template IsReferenceType(T) {
    static if (IsType!(T, bool, byte, ubyte, short, ushort, int, uint, long,
                          ulong, float, double, real, ifloat, idouble, ireal,
                          cfloat, cdouble, creal, char, dchar, wchar) ) {
        const bool IsReferenceType = false;
    } else static if ( is(T == struct) ) {
        const bool IsReferenceType = HasReferences!(FieldTypeTuple!(T));
    } else
        const bool IsReferenceType = true;
}


template IsArray(T) {
    const bool IsArray = is(typeof(T.length)) && is(typeof(T.sort)) &&
                         is(typeof(T.reverse)) && is(typeof(T.dup));
}

template IsDynamicArray(T) {
    // Adapted from the module tango.core.Traits, (C) 2005-2006 Sean Kelly, BSD style licence
    const bool IsDynamicArray = is( typeof(T.init[0])[] == T );
}

template IsStaticArray(T) {
    const bool IsStaticArray = IsArray!(T) && (!IsDynamicArray!(T));
}

///
static struct ArrayBuilder(T) {
    private T* data;
    private int len, _capacity;

    void opCatAssign(T x) {
        if (this.len >= this._capacity) {
            int old_capacity = this._capacity;

            if (this._capacity == 0)
                this._capacity = 4; // starting point not too much small
            else if (this._capacity < (1 << 26)) // 67_108_864
                this._capacity *= 2; // for amortized O(1) and less RAM fragmentation
            else
                this._capacity *= 1.3; // slower growing rate to save RAM

            if (old_capacity != 0)
                this.data = cast(T*)gcrealloc(this.data, this._capacity * T.sizeof);
            else
                this.data = cast(T*)gcmalloc(this._capacity * T.sizeof);

            // to not leave random dangling pointers to
            // the GC if T contains references or pointers
            static if (IsReferenceType!(T)) {
                static if (IsStaticArray!(T)) {
                    // This can't be used, DMD BUG:
                    // this.data[old_capacity .. this._capacity][] = T.init;
                    T Tinit;
                    this.data[old_capacity .. this._capacity][] = Tinit;
                } else
                    this.data[old_capacity .. this._capacity] = T.init;
            } else {
                // is this necessary at every realloc or doing it once is enough?
                hasNoPointers(this.data);
            }
        }

        static if (IsStaticArray!(T))
            this.data[this.len][] = x;
        else
            this.data[this.len] = x;

        this.len++;
    }

    // void opCatAssign(T[] arr) { }  // TODO
    // generic iterable, the following code must be moved inside
    // opCatAssign, and managed with static ifs, this will make things
    // quite hairy
    // void opCatAssign(TyIter)(TyIter iter) { ... } // TODO

    ///
    void clear(bool reclaim=true) {
        // the 'reclaim' argument may be overkill, maybe only one of the
        // two possibilities can be kept

        if (reclaim) {
            gcrealloc(this.data, 0);
            this.data = null;
            this._capacity = 0;
        } else {
            static if (IsReferenceType!(T)) {
                static if (IsStaticArray!(T)) {
                    // This can't be used, DMD BUG:
                    // this.data[old_capacity .. this._capacity][] = T.init;
                    T Tinit;
                    this.data[0 .. this._capacity][] = Tinit;
                } else
                    this.data[0 .. this._capacity] = T.init;
            }
        }

        this.len = 0;
    }

    ///
    int length() {
        return this.len;
    }

    //void length(int newlen) { } // TODO

    ///
    int capacity() {
        return this._capacity;
    }

    //void capacity(int newlen) { } // TODO

    ///
    T[] toarray() {
        return this.data[0 .. this.len];
    }
} // end ArrayBuilder!()



unittest { // tests of ArrayBuilder!()
    //alias ArrayBuilderBasic AB;
    //alias ArrayBuilderNaive AB;
    alias ArrayBuilder AB;

    // First test ------------------------------------
    AB!(int) ab1;
    assert(ab1.toarray == new int[0]);
    ab1 ~= 1;
    ab1 ~= 3;
    ab1 ~= 5;
    assert(ab1.toarray == [1, 3, 5]);
    ab1.clear;
    assert(ab1.toarray == new int[0]);

    auto array1 = new int[1000];
    foreach (i, ref el; array1) {
        ab1 ~= i;
        el = i;
    }
    assert(array1 == ab1.toarray);



    // Second test ------------------------------------
    class Foo {
        int i;
        this(int i) { this.i = i; }
        int opEquals(Foo o) { /* putr("* ", this.i, " ", o.i); */ return this.i == o.i; }
    }

    AB!(Foo) ab2;
    assert(ab2.toarray == new Foo[0]);
    ab2 ~= new Foo(1);
    ab2 ~= new Foo(3);
    ab2 ~= new Foo(5);
    Foo[] r1 = [new Foo(1), new Foo(3), new Foo(5)];
    //putr(typeid(typeof(ab2.toarray)));
    //putr(typeid(typeof(ab2.toarray()))); // their type is different!
    //assert(ab2.toarray == r1); // doesn't work! I don't know why
    foreach (i, el; ab2.toarray())
        assert(el == r1[i]);

    ab2.clear;
    assert(ab2.toarray == new Foo[0]);
    auto array2 = new Foo[1000];
    foreach (i, ref el; array2) {
        ab2 ~= new Foo(i);
        el = new Foo(i);
    }

    //assert(array2 == ab2.toarray);  // doesn't work! I don't know why
    foreach (i, el; ab2.toarray())
        assert(el == array2[i]);


    // Third test ------------------------------------
    AB!(int[2]) ab3;
    assert(ab3.toarray == new int[2][0]);
    ab3 ~= [1, 2];
    ab3 ~= [3, 4];
    ab3 ~= [5, 6];
    auto r2 = ab3.toarray;
    assert(r2[0] == [1, 2]);
    assert(r2[1] == [3, 4]);
    assert(r2[2] == [5, 6]);

    ab3.clear;
    assert(ab3.toarray == new int[2][0]);
    auto array3 = new int[2][](1000);

    foreach (i, ref el; array3) {
        ab3 ~= [i, i];
        el[] = [i, i];
    }
    foreach (i, el; ab3.toarray())
        assert(el == array3[i]);
} // end tests of AB!()



unittest { printf(__FILE__ " unittest performed.\n"); }


// benchmarks ====================================================

import std.string: join, toString;
import std.math: abs;


version (Win32) {
    import std.c.windows.windows: QueryPerformanceCounter, QueryPerformanceFrequency;

    /*********************************
    Return the seconds (a double) from the start of the program.
    */
    double clock() {
        long t;
        QueryPerformanceCounter(&t);

        return cast(double)t / queryPerformanceFrequency;
    }

    long queryPerformanceFrequency;

    static this() {
        QueryPerformanceFrequency(&queryPerformanceFrequency);
    }
}

version (linux) { // this may give too few decimals?
    import std.c.linux.linux: time;

    /// ditto
    double clock() {
        return cast(double)time(null);
    }
}


string thousands(TyIntegral)(TyIntegral n, string separator="_") {
    string ns = toString(abs(n)).reverse;
    string[] parts;
    for (int i = 0; i < ns.length; i += 3)
        parts ~= ns[i .. (i+3) < length ? i+3 : length];
    return (n < 0 ? "-" : "") ~ parts.join(separator).reverse;
}


void benchmark1(alias AB)(int ntest, int N=2_000_000) {
    putr("\nbenchmark 1, N=", thousands(N), ":");

    if (!ntest) {
        auto t0 = clock();
        int[] a1;
        for (int i; i < N; i++)
            a1 ~= i;
        auto last1 = a1[$ - 1];
        auto t2 = clock() - t0;
        putr("  Array append: %.3f", t2, " s   ", last1);
    } else {
        auto t0 = clock();
        AB!(int) a2;
        for (int i; i < N; i++)
            a2 ~= i;
        auto last2 = a2.toarray[$ - 1];
        auto t2 = clock() - t0;
        putr("  AB: %.3f", t2, " s   ", last2);
    }
}


void benchmark2(alias AB)(int ntest, int N=2_000_000) {
    putr("\nbenchmark 2, N=", thousands(N), ":");

    if (!ntest) {
        auto t0 = clock();
        int[] a1a;
        int[] a1b;
        for (int i; i < N; i++) {
            a1a ~= i;
            a1b ~= i;
        }
        auto last1a = a1a[$ - 1];
        auto last1b = a1b[$ - 1];
        auto t2 = clock() - t0;
        putr("  Array append: %.3f", t2, " s   ", last1a, " ", last1b);
    } else {
        auto t0 = clock();
        AB!(int) a2a;
        AB!(int) a2b;
        for (int i; i < N; i++) {
            a2a ~= i;
            a2b ~= i;
        }
        auto last2a = a2a.toarray[$ - 1];
        auto last2b = a2b.toarray[$ - 1];
        auto t2 = clock() - t0;
        putr("  AB: %.3f", t2, " s   ", last2a, " ", last2b);
    }
}


void benchmark3(alias AB)(int ntest, int N=2_000_000) {
    putr("\nbenchmark 3, N=", thousands(N), ":");

    class Foo {
        int i;
        this(int i) { this.i = i; }
    }

    if (!ntest) {
        auto t0 = clock();
        Foo[] a1;
        for (int i; i < N; i++)
            a1 ~= new Foo(i);
        auto last1 = a1[$ - 1];
        auto t2 = clock() - t0;
        putr("  Array append: %.3f", t2, " s   ", last1.i);
    } else {
        auto t0 = clock();
        AB!(Foo) a2;
        for (int i; i < N; i++)
            a2 ~= new Foo(i);
        auto last2 = a2.toarray[$ - 1];
        auto t2 = clock() - t0;
        putr("  AB: %.3f", t2, " s   ", last2.i);
    }
}


void benchmark4(alias AB)(int ntest, int N=2_000_000) {
    putr("\nbenchmark 4, N=", thousands(N), ":");

    class Foo {
        int i;
        this(int i) { this.i = i; }
    }

    if (!ntest) {
        auto t0 = clock();
        Foo[] a1a;
        Foo[] a1b;
        for (int i; i < N; i++) {
            a1a ~= new Foo(i);
            a1b ~= new Foo(i);
        }
        auto last1a = a1a[$ - 1];
        auto last1b = a1b[$ - 1];
        auto t2 = clock() - t0;
        putr("  Array append: %.3f", t2, " s   ", last1a.i, " ", last1b.i);
    } else {
        auto t0 = clock();
        AB!(Foo) a2a;
        AB!(Foo) a2b;
        for (int i; i < N; i++) {
            a2a ~= new Foo(i);
            a2b ~= new Foo(i);
        }
        auto last2a = a2a.toarray[$ - 1];
        auto last2b = a2b.toarray[$ - 1];
        auto t2 = clock() - t0;
        putr("  AB: %.3f", t2, " s   ", last2a.i, " ", last2b.i);
    }
}




void main(string[] args) {
    int bench = args.length >= 2 ? toInt(args[1]) : 1;
    int ntest = args.length >= 3 ? toInt(args[2]) : 0;
    int N = args.length >= 4 ? toInt(args[3]) : 10_000;

    //alias ArrayBuilderBasic AB;
    //alias ArrayBuilderNaive AB;
    alias ArrayBuilder AB;

    switch (bench) {
        case 1: benchmark1!(AB)(ntest, N); break;
        case 2: benchmark2!(AB)(ntest, N); break;
        case 3: benchmark3!(AB)(ntest, N); break;
        case 4: benchmark4!(AB)(ntest, N); break;
        default: throw new Error("wrong bench number");
    }
}

/*
Timings, on a Core Duo @ 2 GHz, 2 GB RAM:

benchmark 1, N=2_000_000:
  Array append: 0.160 s
  ArrayBuilder: 0.026 s
benchmark 1, N=20_000_000:
  Array append: 1.837 s
  ArrayBuilder: 0.325 s
benchmark 1, N=50_000_000:
  Array append: 4.489 s
  ArrayBuilder: 0.731 s
benchmark 1, N=200_000_000:
  Array append: 32.293 s
  ArrayBuilder: Out of memory

benchmark 2, N=200_000:
  Array append: 0.099 s
  ArrayBuilder: 0.004 s
benchmark 2, N=2_000_000:
  Array append: 6.896 s
  ArrayBuilder: 0.050 s

benchmark 3, N=200_000:
  Array append: 0.090 s
  ArrayBuilder: 0.076 s
benchmark 3, N=2_000_000:
  Array append: 1.014 s
  ArrayBuilder: 0.923 s (why is this so slow?)
benchmark 3, N=6_000_000:
  Array append: 5.295 s
  ArrayBuilder: 4.431 s

benchmark 4, N=500_000:
  Array append: 1.109 s
  ArrayBuilder: 0.414 s
benchmark 4, N=1_000_000:
  Array append: 3.103 s
  ArrayBuilder: 0.962 s

*/

// -O -release -inline