/*

TODO:
- try to add extend with generic iterArrayBuilderles
- other array methods may be added: opIndex, opIndexAssign, sort, reverse, opCat, opCat_r
- Add more comments, and improve them
- Add ddoc comments
- Improve unit tests

*/


import std.stdio: put = writef, putr = writefln;
import std.gc: gcmalloc = malloc, gcrealloc = realloc, hasNoPointers, gccapacity = capacity;
import std.conv: toInt;
import std.outofmemory: OutOfMemoryException;
import std.string: replace;

import std.traits: FieldTypeTuple;
import std.intrinsic: bsr;


struct xrange {
    int stop;
    int opApply(int delegate(ref int) dg) {
        int result;
        for (int i; i < stop; i++) {
            result = dg(i);
            if (result) break;
        }
        return result;
    }
}

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 .. $]);
}

template ArrayType1(T: T[]) {
    alias T ArrayType1;
}

template IsReferenceType(Types...) { // this isn't the most updated version of this template!
    static if (Types.length == 0) {
        const bool IsReferenceType = false;
    } else static if (Types.length == 1) {
        // dsimcha suggests to replace the following line with
        // static if (IsType!(MutArrayBuilderle!(Types[0]), bool, byte, ...
        // to make this template work with const/immutArrayBuilderle types on D 2.x.
        static if (IsType!(Types[0], 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(Types[0] == class) ) {
            const bool IsReferenceType = true;
        } else static if ( is(Types[0] == struct) ) {
            const bool IsReferenceType = IsReferenceType!(FieldTypeTuple!(Types[0]));
        } else static if (IsStaticArray!(Types[0])) {
            const bool IsReferenceType = IsReferenceType!(ArrayType1!(Types[0]));
        } else
            const bool IsReferenceType = true;
    } else
        const bool IsReferenceType = IsReferenceType!(Types[0]) |
                                     IsReferenceType!(Types[1 .. $]);
} // end IsReferenceType!()


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));
}


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


int isPow2(long x) {
    return (x < 1) ? false : !(x & (x-1));
}

uint nextPow2(uint n) {
    if (n == 0)
        return 1;
    int first_bit_set = bsr(n);    // get first bit set, starting with most significant.
    if ((1 << first_bit_set) == n) // If already equal to a power of two
        return n;
    return 2 << first_bit_set;
}


///
struct ArrayBuilder(T) {
    static assert(!IsAA!(T),
                  "ArrayBuilder: T can't be an AA because of a v1.034 DMD BUG.");

    const int STARTING_SIZE = 4;
    const int BIG_MEM = (1 << 27) / T.sizeof; // about 134_217_728 bytes
    const int FAST_GROW = 2;
    const float SLOW_GROW = 1.3;
    //const int HUGE_MEM = (1 << 29) / T.sizeof; // to avoid some OutOfMemory?
    //const float VERYSLOW_GROW = 1.08;          // to avoid some OutOfMemory?

    T* data;
    int _length, _capacity;


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


    ///
    void opCatAssign(T item) {
        if (this._length >= this._capacity) {
            if (this._capacity == 0)
                // starting point not too much small
                this._grow_capacity(STARTING_SIZE);
            else if (this._capacity < BIG_MEM)
                // for amortized O(1) and less RAM fragmentation
                this._grow_capacity(cast(int)(this._capacity * FAST_GROW));
            else
                // slower growing rate to save RAM
                this._grow_capacity(cast(int)(this._capacity * SLOW_GROW));
        }

        static if (IsStaticArray!(T))
            this.data[this._length][] = item;
        else
            this.data[this._length] = item;

        this._length++;
    } // end ArrayBuilder!().opCatAssign([])


    /// ditto
    void opCatAssign(T[] array) {
        int newlen = this._length + array.length;

        if (newlen > this._capacity) {
            if (newlen < STARTING_SIZE)
                // starting point not too much small
                this._grow_capacity(STARTING_SIZE);
            else if (newlen > BIG_MEM)
                // slower growing rate to save RAM
                this._grow_capacity(cast(int)((newlen + 1) * SLOW_GROW));
            else
                // for amortized O(1) and less RAM fragmentation
                this._grow_capacity(cast(int)(nextPow2(newlen + 1) * FAST_GROW));
        }

        static if (IsStaticArray!(T))
            this.data[this._length .. newlen][] = array[];
        else
            this.data[this._length .. newlen] = array[];

        this._length = newlen;
    } // end ArrayBuilder!().opCatAssign([])


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


    ///
    void capacity(int newcapacity) {
        if (newcapacity < 0) // do not let errors pass silently
            throw new ArgumentException("ArrayBuilder.capacity: new capacity must be >= 0");
        if (newcapacity <= this._capacity)
            return; // never reduce capacity

        // if it's a power of 2 keep it alone
        // if it's small but not power of 2, make it become the next
        // power of 2 to reduce , so if later the array
        // grows it avoids memory fragmentation
        // if it's very large, then accept it as it is
        if (isPow2(newcapacity) || newcapacity >= BIG_MEM)
            this._grow_capacity(newcapacity);
        else
            this._grow_capacity(nextPow2(newcapacity));
    } // end ArrayBuilder!().capacity()


    ///
    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); // GC free
            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._length = 0;
    } // end ArrayBuilder!().clear()


    // private
    void _grow_capacity(int new_capacity) {
        // if this.data is null performs a gcmalloc
        this.data = cast(T*)gcrealloc(this.data, new_capacity * T.sizeof);
        if (this.data is null)
            // or I can just refuse to do the ~= and raise a better exception
            throw new OutOfMemoryException();

        // to use as much space as possible:
        //new_capacity = gccapacity(this.data) / T.sizeof;
        // I can't use that because gccapacity returns near-random values!
        //putr(new_capacity, " ", gccapacity(this.data) / 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[this._capacity .. new_capacity][] = Tinit;
            } else
                this.data[this._capacity .. new_capacity] = T.init;
        } else {
            hasNoPointers(this.data);
        }

        this._capacity = new_capacity;
    } // end ArrayBuilder!()._grow_capacity()
} // end ArrayBuilder!()



unittest { // Tests of ArrayBuilder!()
    const int MANY = 1_000;

    // Test 1 ------------------------------------
    ArrayBuilder!(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[MANY];
    foreach (i, ref el; array1) {
        ab1 ~= i;
        el = i;
    }
    assert(array1 == ab1.toarray);


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

    ArrayBuilder!(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[MANY];
    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]);


    // Test 3 ------------------------------------
    ArrayBuilder!(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][](MANY);

    foreach (i, ref el; array3) {
        ab3 ~= [i, i];
        el[] = [i, i];
    }
    foreach (i, el; ab3.toarray())
        assert(el == array3[i]);
    assert(ab3.toarray.length == MANY);

    // Test 4 ------------------------------------
    ArrayBuilder!(int) ab4;
    ab4.capacity = 8;
    assert(ab4.toarray == new int[0]);
    ab4 ~= [1, 2, 3, 4];
    ab4 ~= [5, 6, 7, 8];
    assert(ab4.toarray == [1, 2, 3, 4, 5, 6, 7, 8]);

    // Test 5 ------------------------------------
    ArrayBuilder!(int) ab5;
    ab5.capacity = 5;
    assert(ab5.toarray == new int[0]);
    ab5 ~= [1, 2, 3];
    ab5 ~= 4;
    ab5 ~= [5, 6];
    assert(ab5.toarray == [1, 2, 3, 4, 5, 6]);

    // Test 6 ------------------------------------
    ArrayBuilder!(char) ab6;
    ab6.capacity = 50;
    assert(ab6.toarray == new char[0]);
    ab6 ~= "How ";
    ab6 ~= 'a';
    ab6 ~= 'r';
    ab6 ~= 'e';
    ab6 ~= " you?";
    assert(ab6.toarray == "How are you?");

    // Test 7 ------------------------------------
    ArrayBuilder!(int) ab7;
    ab7.capacity = 0;
    assert(ab7.toarray == new int[0]);
    ab7 ~= new int[0];
    assert(ab7.toarray == new int[0]);

    // Test 8 ------------------------------------
    ArrayBuilder!(int) ab8;
    int[] pair = [1, 2];
    foreach (i; xrange(6))
        ab8 ~= pair;
    assert(ab8.toarray == [1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2]);

    // Test 9 ------------------------------------
    ArrayBuilder!(int) ab9;
    foreach (i; xrange(MANY))
        ab9 ~= pair;
    foreach (i, el; ab9.toarray)
        assert(el == (i & 1 ? 2 : 1));
    assert(ab9.toarray.length == pair.length * MANY);

    // Test 10 ------------------------------------
    ArrayBuilder!(int[2]) ab10;
    ab10 ~= [1, 2];
    ab10 ~= [[3, 4], [5, 6]];
    auto r10 = ab10.toarray;
    assert(r10[0] == [1, 2]);
    assert(r10[1] == [3, 4]);
    assert(r10[2] == [5, 6]);
    assert(r10.length == 3);
} // End tests of ArrayBuilder!()



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(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();
        ArrayBuilder!(int) a2;
        for (int i; i < N; i++)
            a2 ~= i;
        auto last2 = a2.toarray[$ - 1];
        auto t2 = clock() - t0;
        putr("  ArrayBuilder: %.3f", t2, " s   ", last2);
    }
}


void benchmark2(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();
        ArrayBuilder!(int) a2a;
        ArrayBuilder!(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("  ArrayBuilder: %.3f", t2, " s   ", last2a, " ", last2b);
    }
}


void benchmark3(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();
        ArrayBuilder!(Foo) a2;
        for (int i; i < N; i++)
            a2 ~= new Foo(i);
        auto last2 = a2.toarray[$ - 1];
        auto t2 = clock() - t0;
        putr("  ArrayBuilder: %.3f", t2, " s   ", last2.i);
    }
}


void benchmark4(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();
        ArrayBuilder!(Foo) a2a;
        ArrayBuilder!(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("  ArrayBuilder: %.3f", t2, " s   ", last2a.i, " ", last2b.i);
    }
}



void benchmark5(int ntest, int N=2_000_000) {
    putr("\nbenchmark 5 (reserve), N=", thousands(N), ":");

    if (!ntest) {
        auto t0 = clock();

        int* aux_ptr = cast(int*)gcmalloc(N * int.sizeof);
        hasNoPointers(aux_ptr);
        int[] a1 = aux_ptr[0 .. 0];

        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();
        ArrayBuilder!(int) a2;
        a2.capacity = N;
        for (int i; i < N; i++)
            a2 ~= i;
        auto last2 = a2.toarray[$ - 1];
        auto t2 = clock() - t0;
        putr("  ArrayBuilder: %.3f", t2, " s   ", last2);
    }
}


void benchmark6(int ntest, int N=2_000_000) {
    putr("\nbenchmark 6 (ubyte), N=", thousands(N), ":");

    if (!ntest) {
        auto t0 = clock();
        ubyte[] 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();
        ArrayBuilder!(ubyte) a2;
        for (int i; i < N; i++)
            a2 ~= i;
        auto last2 = a2.toarray[$ - 1];
        auto t2 = clock() - t0;
        putr("  ArrayBuilder: %.3f", t2, " s   ", last2);
    }
}


void benchmark7(int ntest, int N=2_000_000) {
    putr("\nbenchmark 7 (triples), N=", thousands(N), ":");
    int[3] triple = [1, 2, 3];

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


void benchmark8(int ntest, int N=1_000_000) {
    putr("\nbenchmark 8 (extend 3), N=", thousands(N), ":");
    int[] piece = [1, 2, 3];

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


void benchmark_caller(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].replace("_","")) : 10_000;

    switch (bench) {
        case 1: benchmark1(ntest, N); break;
        case 2: benchmark2(ntest, N); break;
        case 3: benchmark3(ntest, N); break;
        case 4: benchmark4(ntest, N); break;
        case 5: benchmark5(ntest, N); break;
        case 6: benchmark6(ntest, N); break;
        case 7: benchmark7(ntest, N); break;
        case 8: benchmark8(ntest, N); break;
        default: throw new Error("wrong bench number");
    }
}

/*
Timings, on a Core Duo @ 2 GHz, 2 GB RAM:
(approximated, relative to a different BIG_MEM)

benchmark 1, N=2_000_000:
  Array append:  0.159 s
  ArrayBuilder:  0.025 s
benchmark 1, N=20_000_000:
  Array append:  1.843 s
  ArrayBuilder:  0.235 s
  C++ vector  :  0.270 s
benchmark 1, N=50_000_000:
  Array append:  4.557 s
  ArrayBuilder:  0.744 s
benchmark 1, N=100_000_000:
  Array append: 10.900 s
  ArrayBuilder:  1.484 s
  C++ vector  :  1.200 s
benchmark 1, N=200_000_000:
  Array append: 32.293 s
  ArrayBuilder: Out of memory

benchmark 2, N=200_000:
  Array append: 0.098 s
  ArrayBuilder: 0.005 s
benchmark 2, N=2_000_000:
  Array append: 6.881 s
  ArrayBuilder: 0.049 s

benchmark 3, N=200_000:
  Array append: 0.093 s
  ArrayBuilder: 0.075 s
benchmark 3, N=2_000_000:
  Array append: 1.025 s
  ArrayBuilder: 0.993 s (why is this so slow?)
benchmark 3, N=6_000_000:
  Array append: 5.335 s
  ArrayBuilder: 4.687 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

benchmark 5 (reserve), N=50_000_000:
  Array append: 3.842 s
  ArrayBuilder: 0.402 s
  C++:          0.270 s (Reserve + appends)
  C++:          0.500 s (deque append)
benchmark 5 (reserve), N=100_000_000:
  Array append: 7.689 s
  ArrayBuilder: 0.797 s
  C++:          0.540 s (Reserve + appends)
  C++:          1.000 s (deque append)

benchmark 6 (ubyte), N=10_000_000:
  Array append: 0.412 s   127
  ArrayBuilder: 0.095 s   127
benchmark 6 (ubyte), N=100_000_000:
  Array append: 4.509 s   255
  ArrayBuilder: 0.943 s   255

benchmark 7 (triples), N=10_000_000:
  Array append: 1.327 s
  ArrayBuilder: 0.412 s
benchmark 7 (triples), N=30_000_000:
  Array append: 3.156 s
  ArrayBuilder: 1.064 s
benchmark 7 (triples), N=40_000_000:
  Array append: 3.928 s
  ArrayBuilder: Out of memory

benchmark 8 (extend 3), N=10_000_000:
  Array append: 0.745 s
  ArrayBuilder: 0.683 s
benchmark 8 (extend), N=20_000_000:
  Array append: 2.607 s
  ArrayBuilder: 1.252 s
benchmark 8 (extend), N=50_000_000:
  Array append: 5.318 s
  ArrayBuilder: Out of memory
*/



void main(string[] args) {
    benchmark_caller(args);
}