module arsd.structures;
import std.stdio;

/*
	Allocators:

	Simple allocators:
		memory regions that can optionally grow

	static arrays are simple allocators
	slices are simple allocators

	Complex allocators take simple allocators

*/

/*
class Foo {
	void bar() {}
}
*/

alias char[] Foo;

void main() {
	char[100] test;
	test[0 .. 5] = "hello";
	auto a = Unique!(Foo)(test[0..5]);
	//a.bar();

	lol(a.loan);
	//int b = *a;
	writeln("about to enter u");
	u(a.release);
	writeln("u is gone");
}

void lol(Loaned!Foo foo) {
	write("payload is: ");
	void writer(char c) { write(c); }
	foo.visitEach(&writer);
	writeln();
	writeln(foo[2]);
}
void u(Unique!Foo foo) {
	writeln("in u");
	writeln("leaving u");
}

struct Unique(T) {
	@disable this();
	@disable this(this) {}

	private T payload;

	T opDot() { return payload; }

	this(T t) {
		this.payload = t;
	}

	~this() {
		if(this.payload !is null) {
			delete this.payload;
			writefln("payload deleted");
		}
	}

	typeof(*payload) opUnary(string op : "*")() {
		return *payload;
	}

	Unique!T release() {
		auto oldpayload = this.payload;
		this.payload = null;
		return Unique!T(oldpayload);
	}

	Loaned!T loan() {
		return this.payload.loan;
	}
}

/*
	Loans are not copyable and not default constructable, and not assignable.

	What this means is:

	Loaned!T l;
	{
		Unique!T u;
		l = u.loan;
	}
	// l now refers to a dead pointer

	Is impossible.
*/

mixin template SliceFunctions(T) {
	auto opIndex(size_t idx) {
		return payload[idx];
	}

	T copyInto(T where, size_t idxStart = 0) {
		where[] = payload[idxStart .. idxStart + where.length];
		return where;
	}

	version(without_gc) {} else
	T dupGc() pure const {
		return payload.dup;
	}

	int opApply(scope int delegate(typeof(payload[0])) dg) {
		foreach(c; payload)
			if(auto result = dg(c))
				return result;
		return 0;
	}

	Loaned!(typeof(payload.ptr)) ptr() {
		return Loaned!(typeof(payload.ptr))(payload.ptr);
	}

	Loaned!(T) opSlice(size_t s1, size_t s2) {
		return Loaned!(T)(payload[s1 .. s2]);
	}
}

mixin template PointerFunctions(T) {
	typeof(*payload) opUnary(string op : "*")() @safe {
		return *payload;
	}
}

struct Loaned(T) {
	@disable this();
	@disable this(this) {}
	private T payload;

	this(T t) @safe {
		this.payload = t;
	}

	// static if(isPointer!T)

	// static if(isPointer!T || isArray!T) or isSliceable!T ???
	/*
		We can:
			1) set a slice
			2) copy a slice (given a buffer or an allocator)
			3) visit a slice (non-copyable range?)

			But we cannot *get* a slice, since that could escape the reference. Perhaps this could be allowed in @system code though.

	*/

	Loaned!T loan() @safe {
		return Loaned!T(this.payload);
	}
}

Loaned!T loan(T)(T t) {
	return Loaned!T(t);
}


import core.stdc.stdlib;
alias realloc manual_realloc;
alias free manual_free;

void manual_free(Object o) {
	auto dtor = cast(void function(Object o)) Object.classinfo.destructor;
	if(dtor)
		dtor(o);
	free(cast(void*) o);
}

// Don't forget that if you save a slice and this goes out of scope, your
// slice is no good!
struct InPlaceArray(ElementType, size_t capacity) {
	ElementType[capacity] buffer;
	size_t length;
	inout(ElementType)[] slice() inout { return buffer[0 .. this.length]; }
	alias slice this;

	typeof(this) opOpAssign(string op : "~")(in T[] rhs) {
		buffer[this.length .. this.length + rhs.length] = rhs[];
		this.length += rhs.length;
		return this;
	}
}

struct LinkedList(T, alias allocator) {

	private struct LinkedListNode {
		T payload;
		LinkedListNode* next;
	}

	LinkedListNode* front;

	void prepend(T what) {
		LinkedListNode* node;
		static if(is(typeof(allocator) == typeof(null)))
			node = new LinkedListNode;
		else
			node = allocator.allocate();

		node.payload = what;
		node.next = front;

		front = node;
	}

	void removeFront() {
		auto old = front;
		front = front.next;

		static if(!is(typeof(allocator) == typeof(null)))
			allocator.free(old);
	}

	auto range() {

	}
}

void llTest() {
	//Pool!(LinkedList!int.LinkedListNode, 16) pool;
	LinkedList!(int, null) list;

	list.prepend(10);
	list.prepend(15);

	import std.stdio;
	auto front = list.front;
	while(front) {
		writeln(front.payload);
		front = front.next;
	}
}
version(none)
void main() { llTest(); }

/*
	Two types of containers:

	1) need to grow themselves
		e.g. arrays

		These need a backing with the append operation (which may or may not allocate)
		and perhaps discard and reserve functions

		Should they own the memory? I think no.. but yes.

	2) need to create sub-containers
		e.g. linked lists

		These need an allocator
*/

struct Stack(alias Backing) {
	private InPlaceArray!(ElementType, capacity) buffer;

	void push(ElementType t) {
		buffer ~= t;
	}

	ElementType pop() {
		assert(buffer.length);
		return buffer.buffer[--buffer.length];
	}
}

struct InPlaceQueue(ElementType, size_t capacity) {
	ElementType[capacity] buffer;
	size_t length;

}

struct InPlaceLinkedList(ElementType, size_t capacity) {
	struct ListItem {
		ElementType content;
		ListItem* next;
	}

	Pool!(ListItem, capacity) pool;

	ListItem* front;

	ListItem* prepend(ElementType element) {
		auto item = pool.allocate();
		item.content = element;
		item.next = front;
		front = item;
		return item;
	}

	void removeNext(ListItem* ptr) {
		assert(ptr !is null);
		assert(ptr.next !is null);
		auto oldptr = ptr.next;
		ptr.next = ptr.next.next;
		pool.free(oldptr);
	}

	void popHead() {
		assert(front !is null);
		front = front.next;
		pool.free(front);
	}

	// since we have to find the previous item to keep the chain going, this is going
	// to be a little slower than the above two
	void findAndRemove(ListItem* ptr) {
		assert(ptr !is null);
		auto f = this.front;
		ListItem* prev = null;
		while(f) {
			if(f is ptr) {
				if(prev is null) {
					// it is the first one, so we can't remove next
					popHead();
				} else
					removeNext(prev);
				break;
			}
			prev = f;
			f = f.next;
		}
	}
}

size_t[max] arrayTo(size_t max)() {
	size_t[max] a;
	foreach(i; 0 .. max)
		a[i] = i;
	return a;
}


// thanks, Walter!
struct CircularBuffer(U: T[dim], T, size_t dim)
{
    void put(T e)
    {
        assert(length != dim);
        size_t i = first + length;
        if (i >= dim)
            i -= dim;
        buf[i] = e;
        length += 1;
    }

    @property T front()
    {
        assert(length);
        return buf[first];
    }

    void popFront()
    {
        assert(length);
        first += 1;
        if (first == dim)
            first = 0;
        --length;
    }

    @property bool full()
    {
        return length == dim;
    }

    @property bool empty()
    {
        return length == 0;
    }

    T opIndex(size_t i)
    {
        assert(i < length);
        i += first;
        if (i >= dim)
            i -= dim;
        return buf[i];
    }

    size_t length;

  private:
    size_t first;
    T[dim] buf = void;
}

unittest
{
    CircularBuffer!(ubyte[3]) buf;
    assert(buf.empty);
    assert(buf.length == 0);
    assert(!buf.full);

    buf.put(7);
    assert(!buf.empty);
    assert(buf.length == 1);
    assert(!buf.full);
    assert(buf[0] == 7);

    buf.put(8);
    buf.put(9);
    assert(!buf.empty);
    assert(buf.length == 3);
    assert(buf.full);

    assert(buf.front == 7);
    buf.popFront();
    buf.put(10);
    assert(!buf.empty);
    assert(buf.length == 3);
    assert(buf.full);
    assert(buf[0] == 8);
    assert(buf[1] == 9);
    assert(buf[2] == 10);
}

struct Pool(ElementType, size_t capacity) {
	ElementType[capacity] buffer;
	bool[capacity] bufferSlotInUse;

	CircularBuffer!(size_t[capacity]) freeList;
	bool initialized;

	// it is your responsibility to initialize the object!
	ElementType* allocate() {
		if(!initialized) {
			foreach(i; 0 .. capacity)
				freeList.put(i);
			initialized = true;
		}

		auto firstAvailableSlot = freeList.front;
		freeList.popFront;

		bufferSlotInUse[firstAvailableSlot] = true;
		auto slot = &(buffer[firstAvailableSlot]);

		return slot;
	}

	// it is your responsibility to run the destructor!
	void free(ref ElementType* item) {
		assert(item >= buffer.ptr);
		assert(item < (buffer.ptr + capacity * ElementType.sizeof));

		size_t idx = (item - buffer.ptr) / ElementType.sizeof;
		assert(idx < capacity);
		bufferSlotInUse[idx] = false;

		freeList.put(idx);

		item = null;
	}
}


final class HeapArrayBacking(T) {
	T* backing;
	size_t capacity;
	size_t length;
	int refcount;

	T[] slice() {
		return backing[0 .. length];
	}

	void setCapacity(size_t capacity) {
		backing = cast(T*) manual_realloc(backing, capacity * T.sizeof);
		this.capacity = capacity;
		if(length > capacity)
			length = capacity;
	}

	void append(T rhs) {
		if(length == capacity) {
			throw new Exception("out of space");
			// FIXME: realloc?
		}
		backing[this.length] = rhs;
		this.length ++;
	}

	void append(in T[] rhs) {
		if(length == capacity) {
			throw new Exception("out of space");
			// FIXME: realloc?
		}
		backing[this.length .. this.length + rhs.length] = rhs[];
		this.length += rhs.length;
	}

	T at(size_t idx, string file = __FILE__, size_t line = __LINE__) {
		if(idx >= length)
			throw new Exception("range error", file, line);
		return backing[idx];
	}

	this() {

	}

	~this() {
		assert(this.refcount == 0);
		if(backing !is null) {
			manual_free(backing);
		}
	}
}

struct HeapArray(T) {
	HeapArrayBacking!T backing;
	@disable this();

	this(size_t capacity) {
		//backing = new HeapArrayBacking!T;
		void* buffer = malloc(__traits(classInstanceSize, HeapArrayBacking!T));
		buffer[0 .. __traits(classInstanceSize, HeapArrayBacking!T)] = HeapArrayBacking!T.classinfo.init[];

		backing = cast(HeapArrayBacking!T) buffer;

		backing.setCapacity(capacity);
		backing.refcount++;
	}

	this(HeapArray!T reference) {
		backing = reference.backing;
		backing.refcount++;
	}

	this(this) {
		backing.refcount++;
	}

	~this() {
		backing.refcount--;
		if(backing.refcount == 0)
			manual_free(backing);
	}

	@disable void opAssign(typeof(this) rhs) {}

	typeof(this) copy() {
		auto cp = HeapArray!T(this.backing.capacity);
		cp ~= this.slice();
		return cp;
	}

	typeof(this) opOpAssign(string op : "~")(in T[] rhs) {
		backing.append(rhs);
		return this;
	}

	typeof(this) opOpAssign(string op : "~")(in T rhs) {
		backing.append(rhs);
		return this;
	}

	T opIndex(size_t idx, string file = __FILE__, size_t line = __LINE__) {
		return backing.at(idx, file, line);
	}

	T[] slice() { return backing.slice; }
	alias slice this;
}

void poolTest() {
	Pool!(int, 6) pool;
	foreach(i; 0 .. 10000) {
		auto a = pool.allocate();
		*a = 10;
		pool.free(a);
	}
}

void gcTest() {
	foreach(i; 0 .. 10000) {
		auto a = new int;
		*a = 10;
	}
}


version(none)
void main() {
	import std.datetime;
	import std.stdio;

	auto r = benchmark!(poolTest, gcTest)(10_000);
	writeln(r);
	writeln(cast(real) r[1].length / r[0].length);

/*
	InPlaceLinkedList!(int, 3) list;

	list.prepend(10);
	auto t = list.prepend(30);
	list.prepend(40);
	list.findAndRemove(t);
	list.prepend(50);

	import std.stdio;
	auto front = list.front;
	while(front) {
		writeln(front.content);
		front = front.next;
	}
*/
}
/**
	Memory management tips

	1) use StackArrays whenever you can
	2) HeapArrays are the second choice, they are refcounted automatically
	3) OwnedArrays are like heap arrays, but non-copyable
*/


// non-refcounted, non-copyable
struct OwnedArray(T) {
	  @disable this();
	  @disable this(this);
	  this(size_t capacity) {

	  }

	  ~this() {

	  }
}

// FIXME: finis this and decide if it is even a good idea
struct RefCountedSlice(T) {
	@disable this();
	HeapArrayBacking backing;
	this(HeapArray!T ha, size_t start, size_t end) {
		this.backing = ha.backing;
		this.start = start;
		this.end = end;
		backing.refcount++;
	}

	this(this) {
		backing.refcount++;
	}

	~this() {
		backing.refcount--;
		if(backing.refcount == 0)
			manual_free(backing);
	}

	typeof(this) copy() {
		auto cp = HeapArray!T(this.backing.capacity);
		cp ~= this.slice();
		return cp;
	}

	size_t start;
	size_t end;
	T opIndex(size_t idx, string file = __FILE__, size_t line = __LINE__) {
		return backing.at(idx + start, file, line);
	}

	T[] slice() { return backing.slice[start .. end]; }
	alias slice this;

}

// introduces double indirection but it is easy
mixin template SimpleRefCounting(T, string freeCode) {
	final class RefCount {
		T payload;
		int refcount;
		this(T t) { payload = t; }
		~this() {
			assert(refcount == 0);
			mixin(freeCode);
		}
	}

	private RefCount payload;
	@property T getPayload() { return payload.payload; }
	alias getPayload this;
	@disable this();
	this(T t) {
		payload = new RefCount(t);
	}

	this(typeof(this) reference) {
		payload = reference.payload;
		payload.refcount++;
	}

	this(this) {
		payload.refcount++;
	}

	~this() {
		payload.refcount--;
		if(payload.refcount == 0)
			manual_free(payload);
	}
}

struct HeapClosure(T) if(is(T == delegate)) {
	mixin SimpleRefCounting!(T, q{
		char[16] buffer;
		write("\nfreeing closure ", intToString(cast(size_t) payload.ptr, buffer),"\n");
		manual_free(payload.ptr);
	});
}

HeapClosure!T makeHeapClosure(T)(T t) { // if(__traits(isNested, T)) {
	return HeapClosure!T(t);
}