use Into
use Alloc (Allocator(allocate))
use Iter (map-maybe, for-each, cons)
use Math (mod)
use Misc (fmap-maybe)
use Hashable (Hashable, hash)
use Str (Str(*))
use Error
	panic, unreachable, or-fail, todo
use Slice (Slice)


Bucket k v
	Empty  # first entry, so we can zero initialize
	Tombstone
	Taken (k, v)

Hash al k v
	allocator al
	buckets Slice (Bucket k v)
	entries U32


fn mk (al Allocator) -> Hash Allocator k v
	return {
		buckets: Slice.empty(),
		allocator: al,
		entries: 0 }


fn bucket-to-maybe (b Bucket k v) -> Maybe (k, v)
	case b
		Taken(t)
			return Just(t)
		_
			return None

fn entries (self Ptr (Hash al k v)) -> Iter.MapMaybe (Slice.SliceIter (Bucket k v)) (Bucket k v) (k, v):
	self&.buckets map-maybe(bucket-to-maybe)

fn insert-no-check (self Ptr (Hash Allocator k v), k k, v v) <= Eq k, Hashable k
	h = k hash()
	i = h mod (self&.buckets.count)
	first-free = None
	while True
		case self&.buckets Slice.get(i)
			Taken ((found-k, _))
				if found-k == k
					first-free <= Just(i)
					break
				
			Tombstone
				if first-free == None
					first-free <= Just(i)
			Empty
				if first-free == None
					first-free <= Just(i)
				break

		i <= (i + 1) mod (self&.buckets.count)

	insert-i = first-free or-fail('(insert-no-check): no free slot?')
	self&.buckets Slice.set(insert-i, Taken((k, v)))
	self <&.entries= self&.entries + 1

fn resize-if-needed (self Ptr (Hash Allocator k v)) <= Eq k, Hashable k
	load-factor = 100 * (self&.entries into-uint() + 1) / (self&.buckets.count + 1)

	min-size = 16
	min-load-factor = 5
	max-load-factor = 60
	if (load-factor < max-load-factor and (load-factor >= min-load-factor or self&.entries into-uint() > min-size))
		return

	new-size =
		if self&.buckets.count == 0: 8
		elif load-factor < min-load-factor: Math.max(self&.buckets.count / 2, min-size) # decrease
		else self&.buckets.count * 2 # increase

	old-bucket-arr = self&.buckets

	# new array and replace the old one.
	nu-hash =& Hash {
		buckets: self&.allocator allocate(new-size) as Slice (Bucket k v),
		allocator: self&.allocator,
		entries: 0
		}
	Slice.zero-initialize(nu-hash&.buckets)

	self entries()
		for-each(fn ((ek, ev)): nu-hash insert-no-check(ek as k, ev as v))

	self&.allocator Alloc.free(old-bucket-arr)
	self <&= nu-hash&


fn get-bucket-ptr (self Ptr (Hash al k v), k k) -> Maybe (Ptr (Bucket k v)) <= Eq k, Hashable k
	if self&.buckets.count == 0
		return None

	h = k hash()
	i = h mod (self&.buckets.count)
	while True
		bucket-ptr = self&.buckets Slice.get-ptr(i)
		case bucket-ptr
			Ptr(Taken ((found-k, v)))  # NOTE: this requires deconstructions to operate on ORIGINAL VALUES.
				if found-k == k
					return Just(bucket-ptr)
				
			Ptr(Tombstone)
				pass

			Ptr(Empty)
				return None

		i <= (i + 1) mod (self&.buckets.count)


##### API

fn insert (self Ptr (Hash Allocator k v), k k, v v) <= Eq k, Hashable k
	self resize-if-needed()
	self insert-no-check(k, v)

fn lookup-ptr (self Ptr (Hash al k v), k k) -> Maybe (Ptr v) <= Eq k, Hashable k
	case self get-bucket-ptr(k)
		Just(Ptr(Taken((_, v))))
			return Just(&v)

		None
			return None

		_
			unreachable()


fn lookup (self Ptr (Hash al k v), k k) -> Maybe v <= Eq k, Hashable k
	return self lookup-ptr(k) fmap-maybe(fn x: x&)

fn get (self Ptr (Hash al k v), k k) -> v <= Eq k, Hashable k
	return self lookup(k) or-fail('(Hash.get) lookup failed.')


fn remove (self Ptr (Hash al k v), k k) -> () <= Eq k, Hashable k
	case self get-bucket-ptr(k)
		Just(bucket-ptr)
			bucket-ptr <&= Tombstone
			self <&.entries= self&.entries - 1
			# don't resize ON PURSPOSE. removing should not fail!
		None
			panic('(Hash.remove) Element not in Hash.')


inst Str Hash
	print-str (self _): (&self) entries() Str.print-as-list()
	# currently Str.list-chars is not working in this context...
	# chars (self _)
	# 	chars = (&self) entries() Str.list-chars()
	# 	return chars
	chars (self _): (todo() as ()) chars()

inst Indexable Hash
	elem-get (self, k): get(&self, k)