module nxt.container.variant_arrays;

@safe:

/** Typed index (reference) into an element in `VariantArrays`.
 *
 * TODO: merge with soa.d?
 */
private struct VariantRef(Size, DefinedTypes...)
{
    @safe:

    import std.meta : staticIndexOf;

    alias Kind = ubyte;              // kind code

    import nxt.bit_traits : bitsNeeded;

    /// Used to indicate undefined value.
    private struct Undefined {}

    import std.meta : AliasSeq;

    alias Types = AliasSeq!(Undefined, DefinedTypes);

    /// Number of bits needed to represent kind.
    private enum kindBits = bitsNeeded!(Types.length);

    /** Get number kind of kind type `SomeKind`.
        TODO: make private?
     */
    enum nrOfKind(SomeKind) = staticIndexOf!(SomeKind, Types); // TODO: cast to ubyte if Types.length is <= 256

    /// Is `true` iff an index to a `SomeKind`-kind can be stored.
    enum canReferenceType(SomeKind) = nrOfKind!SomeKind >= 0;

    /// Comparsion works like for integers.
    int opCmp(in typeof(this) rhs) const @trusted
    {
        version(LDC) pragma(inline, true);
        if (this._rawWord < rhs._rawWord)
            return -1;
        if (this._rawWord > rhs._rawWord)
            return +1;
        return 0;
    }

    pragma(inline, true):

    /// Construct from mutable `that`.
    this(in typeof(this) that)
    {
        this._rawWord = that._rawWord;
    }
    /// Construct from constant `that`.
    this(typeof(this) that)
    {
        this._rawWord = that._rawWord;
    }

    /// Construct.
    this(Kind kind, Size index) // TODO: can ctor inferred by bitfields?
    {
        this._word.kindNr = kind;
        this._word.index = index;
    }

    /// Construct from raw word representation `rawWord`.
    private this(Size rawWord)
    {
        this._rawWord = rawWord;
    }

    /// Get kindNr.
    Kind kindNr() const => _word.kindNr;

    /// Get index.
    Size index() const => _word.index;

    /// Cast to `size_t`.
    size_t opCast(T : size_t)() const => _rawWord;

    import core.internal.traits : Unqual;

    /// Allow cast to unqualified.
    U opCast(U : Unqual!(typeof(this)))() const => U(rawWord);

    /// The index itself is the hash.
    hash_t toHash() const @property => _rawWord;
    static assert(hash_t.sizeof == _rawWord.sizeof);

    /// Cast to `bool`, meaning 'true' if defined, `false` otherwise.
    bool opCast(U : bool)() const => isDefined();

    /// Returns: `true` iff is defined.
    bool isDefined() const => _rawWord != 0;

    /// Returns: `true` iff `this` targets a value of type `SomeKind`.
    public bool isA(SomeKind)() const => nrOfKind!(SomeKind) == _word.kindNr;

    void toString(Sink)(ref scope Sink sink) const @trusted
    {
        import std.format : formattedWrite;
        if (isDefined)
            sink.formattedWrite!`%s(%s@%s)`(Unqual!(typeof(this)).stringof, _word.index, _word.kindNr);
        else
            sink.formattedWrite!`%s(null)`(Unqual!(typeof(this)).stringof);
    }

	private struct Word
	{
		import nxt.dip_traits : hasPreviewBitfields;
		version(LittleEndian)
		{
			static if (hasPreviewBitfields)
			{
				// TODO: remove mixins when -preview=bitfields is in stable dmd
				mixin("Kind kindNr:kindBits;");
				mixin("Size index:8*Size.sizeof - kindBits;");
			}
			else
			{
				import std.bitmanip : bitfields;
				mixin(bitfields!(Kind, "kindNr", kindBits,
								 Size, "index", 8*Size.sizeof - kindBits));
			}
		}
		else
		{
			static assert(0, "TODO: BigEndian support");
		}
	}

    private union
    {
		Word _word;
        Size _rawWord;			// for comparsion
    }

    // static assert(this.sizeof == Size.sizeof,
    //               `This should haven't any memory overhead compared to size_t`);
}

@safe pure nothrow unittest
{
    alias R = VariantRef!(size_t, int, float);
    R r;
    static assert(r.canReferenceType!(int));
    static assert(r.canReferenceType!(float));
    static assert(!r.canReferenceType!(short));

    import std.array : Appender;
    Appender!(const(R)[]) app;
    assert(app.data.length == 0);

    const R x;
    R mx = x;
    assert(x == mx);

    // TODO: app ~= x;

    // const y = [R.init, R.init];
    // TODO: app ~= y;
}

unittest
{
    import std.conv : to;
    alias R = VariantRef!(size_t, int, float);
    R r;
    assert(r.to!string == R.stringof~`(null)`);
}

// private mixin template VariantArrayOf(Type)
// {
//     import nxt.container.dynamic_array : DynamicArray;
//     DynamicArray!Type store;
// }

/** Stores set of variants.

    Enables lightweight storage of polymorphic objects.

    Each element is indexed by a corresponding `VariantRef`.
 */
struct VariantArrays(Types...)
{
    @safe:

	alias Size = size_t;
    alias Ref = VariantRef!(Size, Types);

    import nxt.container.dynamic_array : DynamicArray;

    /// Returns: array type (as a string) of `Type`.
    private static immutable(string) arrayTypeStringOfIndex(uint typeIndex)()
    {
        pragma(inline, true);
        return `DynamicArray!(Types[` ~ typeIndex.stringof ~ `])`;
    }

    /** Returns: array instance (as a strinng) storing `SomeKind`.
     * TODO: make this a template mixin
     */
    private static immutable(string) arrayInstanceString(SomeKind)()
    if (Ref.canReferenceType!SomeKind)
    {
        pragma(inline, true);
        return `_store` ~ Ref.nrOfKind!(SomeKind).stringof; // previously `SomeKind.mangleof`
    }

    /// Make reference to type `SomeKind` at offset `index`.
    static Ref makeRef(SomeKind)(Ref.Size index)
    if (Ref.canReferenceType!SomeKind)
    {
        pragma(inline, true);
        return Ref(Ref.nrOfKind!SomeKind, index);
    }

    /** Insert `value` at back.
     */
    Ref insertBack(SomeKind)(SomeKind value) // TODO: add array type overload
    if (Ref.canReferenceType!SomeKind)
    {
        mixin(`alias arrayInstance = ` ~ arrayInstanceString!SomeKind ~ `;`);
        const currentIndex = arrayInstance.length;
        arrayInstance.insertBackMove(value);
        return Ref(Ref.nrOfKind!SomeKind, currentIndex);
    }
    alias put = insertBack;     // polymorphic `OutputRange` support

    /** Move (emplace) `value` into back.
     */
    Ref insertBackMove(SomeKind)(ref SomeKind value) // TODO: add array type overload
    if (Ref.canReferenceType!SomeKind)
    {
        version(DigitalMars) pragma(inline, false); // DMD cannot inline
        mixin(`alias arrayInstance = ` ~ arrayInstanceString!SomeKind ~ `;`);
        const currentIndex = arrayInstance.length;
        arrayInstance.insertBackMove(value);
        return Ref(Ref.nrOfKind!SomeKind, currentIndex);
    }

    /// ditto
    void opOpAssign(string op, SomeKind)(SomeKind value) // TODO: add array type overload
    if (op == "~" &&
        Ref.canReferenceType!SomeKind)
    {
        pragma(inline, true);
        insertBackMove(value);  // move enables uncopyable types
    }

    /// Get reference to element of type `SomeKind` at `index`.
    scope ref inout(SomeKind) at(SomeKind)(in size_t index) inout return
    if (Ref.canReferenceType!SomeKind)
    {
        pragma(inline, true);
        mixin(`return ` ~ arrayInstanceString!SomeKind ~ `[index];`);
    }

    /// Get reference to element of type `SomeKind` at `ref_`.
    scope ref inout(SomeKind) at(SomeKind)(in Ref ref_) inout return
    if (Ref.canReferenceType!SomeKind)
    {
        pragma(inline, true);
        assert(Ref.nrOfKind!SomeKind == ref_.kindNr,
               "Ref is not of expected template type " ~ SomeKind.stringof);
        mixin(`return ` ~ arrayInstanceString!SomeKind ~ `[ref_.index];`);
    }

    /// Peek at element of type `SomeKind` at `ref_`.
    inout(SomeKind)* peek(SomeKind)(in Ref ref_) inout return @system
    if (Ref.canReferenceType!SomeKind)
    {
        pragma(inline, true);
        if (Ref.nrOfKind!SomeKind == ref_._word.kindNr)
            return &at!SomeKind(ref_._word.index);
        else
            return null;
    }

    /// Constant access to all elements of type `SomeKind`.
    scope inout(SomeKind)[] allOf(SomeKind)() inout return
    if (Ref.canReferenceType!SomeKind)
    {
        pragma(inline, true);
        mixin(`return ` ~ arrayInstanceString!SomeKind ~ `[];`);
    }

    /// Reserve space for `newCapacity` elements of type `SomeKind`.
    size_t reserve(SomeKind)(in size_t newCapacity)
    if (Ref.canReferenceType!SomeKind)
    {
        pragma(inline, true);
        mixin(`alias arrayInstance = ` ~ arrayInstanceString!SomeKind ~ `;`);
        return arrayInstance.reserve(newCapacity);
    }

    /** Returns: length of store. */
    @property size_t length() const
    {
        pragma(inline, true);
        typeof(return) lengthSum = 0;
        foreach (Type; Types)
            mixin(`lengthSum += ` ~ arrayInstanceString!Type ~ `.length;`);
        return lengthSum;
    }

    /** Check if empty. */
    bool empty() const @property
    {
        pragma(inline, true);
        return length == 0;
    }

private:
    static if (false/*__VERSION__ >= 2076*/)
    {
        // static foreach (const typeIndex, Type; Types)
        // {
        //     // TODO: is it better to use?: mixin VariantArrayOf!(Type);
        //     mixin(arrayTypeStringOfIndex!typeIndex ~ ` ` ~ arrayInstanceString!Type ~ `;`);
        // }
    }
    else
    {
        mixin({
                string s = "";
                foreach (const typeIndex, Type; Types)
                    s ~= arrayTypeStringOfIndex!typeIndex ~ ` ` ~ arrayInstanceString!Type ~ `;`;
                return s;
            }());
    }
}

/** Minimalistic fixed-length (static) array of (`capacity`) number of elements
 * of type `E` where length only fits in an `ubyte` for compact packing.
 */
version(unittest)
private struct MinimalStaticArray(E, ubyte capacity)
{
@safe:
    this(in E[] es)
    {
        assert(es.length <= capacity,
               "Length of input parameter `es` is larger than capacity "
               ~ capacity.stringof);
        _es[0 .. es.length] = es;
        _length = cast(typeof(_length))es.length;
    }

private:
    E[capacity] _es;
    typeof(capacity) _length;
}

@safe pure nothrow @nogc unittest
{
    const ch7 = MinimalStaticArray!(char, 7)(`1234567`);
    assert(ch7._es[] == `1234567`);
}

///
@safe pure nothrow @nogc unittest
{
    alias Chars(uint capacity) = MinimalStaticArray!(char, capacity);
    alias Chars7 = Chars!7;
    alias Chars15 = Chars!15;
    alias VA = VariantArrays!(ulong,
                              Chars7,
                              Chars15);

    VA data;
    assert(data.length == 0);
    assert(data.empty);

    const i0 = data.put(ulong(13));
    assert(cast(size_t)i0 == 1);

    assert(i0.isA!ulong);
    assert(data.at!ulong(0) == ulong(13));
    assert(data.length == 1);
    assert(!data.empty);
    assert(data.allOf!ulong == [ulong(13)].s);

    const i1 = data.put(Chars7(`1234567`));
    assert(cast(size_t)i1 == 2);

    // same order as in `Types`
    assert(i0 < i1);

    assert(i1.isA!(Chars7));
    assert(data.at!(Chars7)(0) == Chars7(`1234567`));
    assert(data.allOf!(Chars7) == [Chars7(`1234567`)].s);
    assert(data.length == 2);

    const i2 = data.put(Chars15(`123`));
    assert(cast(size_t)i2 == 3);

    // same order as in `Types`
    assert(i0 < i2);
    assert(i1 < i2);

    assert(i2.isA!(Chars15));
    assert(data.at!(Chars15)(0) == Chars15(`123`));
    // TODO: assert(data.allOf!(Chars15) == [Chars15(`123`)].s);
    assert(data.length == 3);

    const i3 = data.put(Chars15(`1234`));
    assert(cast(size_t)i3 == 7);

    // same order as in `Types`
    assert(i0 < i3);
    assert(i1 < i3);
    assert(i2 < i3);            // same type, i2 added before i3

    assert(i3.isA!(Chars15));
    assert(data.at!(Chars15)(1) == Chars15(`1234`));
    assert(data.allOf!(Chars15) == [Chars15(`123`), Chars15(`1234`)].s);
    assert(data.length == 4);
}

// version = extraTests;

version(extraTests)
{
static private:
    alias S = VariantArrays!(Rel1, Rel2, Int);

    // relations
    struct Rel1 { S.Ref[1] args; }
    struct Rel2 { S.Ref[2] args; }

    struct Int { int value; }
}

///
version(extraTests)
@safe pure nothrow @nogc unittest
{
    S s;

    const S.Ref top = s.put(Rel1(s.put(Rel1(s.put(Rel2([s.put(Int(42)),
                                                        s.put(Int(43))]))))));
    assert(top);
    assert(s.allOf!Rel1.length == 2);
    assert(s.allOf!Rel2.length == 1);
    assert(s.allOf!Int.length == 2);
    assert(s.length == 5);
}

/// put and peek
version(extraTests)
@system pure nothrow @nogc unittest
{
    S s;
    const n = 10;
    foreach (const i; 0 .. n)
    {
        S.Ref lone = s.put(Int(i));
        Int* lonePtr = s.peek!Int(lone);
        assert(lonePtr);
        assert(*lonePtr == Int(i));
    }
    assert(s.length == 10);
}

version(unittest)
{
    import nxt.array_help : s;
}

// version = benchmark;

version(benchmark)
unittest
{
    import std.stdio : writeln;
    import std.datetime : MonoTime;
    import std.meta : AliasSeq;
    alias E = uint;
    immutable n = 5_000_000;
    foreach (A; AliasSeq!(VariantArrays!(E)))
    {
        A a;
        immutable before = MonoTime.currTime();
        foreach (uint i; 0 .. n)
            a ~= i;
        immutable after = MonoTime.currTime();
        writeln("Added ", n, " integer nodes into ", A.stringof, " in ", after - before);
    }

}