/* andrew reese's Exponential Array datatype */

use bits, mem.Arena, mem.arena_alloc

const XAR_INIT_SZ = 8
const XAR_MAX_DOUBLE = 20

struct Xar(T) {
	n u32,
	chunk [XAR_MAX_DOUBLE]^T
}

#[inline]
func xar_chnk_slot(xar ^Xar(T), idx u32) (u32, u32) {
	let chnk = 31 - bits.clz((idx / XAR_INIT_SZ) + 1)
	let slot = idx - ((XAR_INIT_SZ << chnk) - XAR_INIT_SZ)
	return (chnk, slot)
}

func xar_get(xar ^Xar(T), idx u32) ^T {
	let chnk, slot = xar_chnk_slot(xar, idx)
	return xar->chunk[chnk] + (slot * sizeof(T))
}

func xar_put(xar ^Xar(T), idx u32, a ^Arena) {
	let chnk, slot = xar_chnk_slot(xar, idx)
	if (!xar->chunk[chnk]) {
		xar->chunk[chnk] := arena_alloc(a, sizeof(T) * (XAR_INIT_SZ << chnk)), alignof(T))
	}
	return xar->chunk[chnk] + (slot * sizeof(T))
}

proc xar_push(xar ^Xar(T), v T, a ^Arena) {
	xar_put(xar, xar.n, a)^ = v
	xar.n := xar.n + 1
}