package ru.dbotthepony.kstarbound.util

import com.github.benmanes.caffeine.cache.Interner
import it.unimi.dsi.fastutil.HashCommon
import it.unimi.dsi.fastutil.objects.ObjectArrayList
import ru.dbotthepony.kstarbound.Starbound
import ru.dbotthepony.kstarbound.stream
import java.lang.ref.ReferenceQueue
import java.lang.ref.WeakReference
import java.util.concurrent.TimeUnit
import java.util.concurrent.locks.ReentrantLock
import kotlin.concurrent.withLock
import kotlin.math.log
import kotlin.math.roundToInt

// hand-rolled interner, which has similar performance to ConcurrentHashMap
// (given there is no strong congestion, otherwise it performs somewhere above Caffeine interner),
// while yielding significantly better memory utilization than both
class HashTableInterner<T : Any>(private val segmentBits: Int = log(Runtime.getRuntime().availableProcessors().toDouble(), 2.0).roundToInt().coerceAtLeast(4)) : Interner<T> {
	companion object {
		private val interners = ArrayList<WeakReference<HashTableInterner<*>>>()

		private var wait = 1_000_000L
		private const val minWait = 1_000_000L
		private const val maxWait = 1_000_000_000L

		private fun cleanupCycle() {
			var any = 0

			synchronized(interners) {
				val i = interners.iterator()

				for (v in i) {
					val get = v.get()

					if (get == null) {
						i.remove()
					} else {
						for (segment in get.segments) {
							any += segment.cleanup()
						}
					}
				}
			}

			if (any != 0) {
				wait = (wait - 1_000_000L * any).coerceAtLeast(minWait)
			} else {
				wait = (wait + 1_000_000L).coerceAtMost(maxWait)
			}

			Starbound.schedule(::cleanupCycle, wait, TimeUnit.NANOSECONDS)
		}

		init {
			cleanupCycle()
		}
	}

	class Ref<T : Any>(referent: T, queue: ReferenceQueue<T>) : WeakReference<T>(referent, queue), Iterable<Ref<T>> {
		val hash = referent.hashCode()
		var nextEntry: Ref<T>? = null

		override fun hashCode(): Int {
			return hash
		}

		override fun equals(other: Any?): Boolean {
			return other === this
		}

		fun insert(value: Ref<T>) {
			var current = this

			while (current.nextEntry != null) {
				current = current.nextEntry!!
			}

			current.nextEntry = value
		}

		fun remove(value: Ref<T>): Boolean {
			var current = this

			while (true) {
				if (current.nextEntry === value) {
					current.nextEntry = current.nextEntry!!.nextEntry
					return true
				} else if (current.nextEntry == null) {
					return false
				} else {
					current = current.nextEntry!!
				}
			}
		}

		override fun iterator(): Iterator<Ref<T>> {
			return object : Iterator<Ref<T>> {
				private var next: Ref<T>? = this@Ref

				override fun hasNext(): Boolean {
					return next != null
				}

				override fun next(): Ref<T> {
					val next = next ?: throw NoSuchElementException()
					this.next = next.nextEntry
					return next
				}
			}
		}
	}

	private val actualSegmentBits: Int

	init {
		var result = 0

		for (i in 0 until segmentBits) {
			result = result or (1.shl(i))
		}

		actualSegmentBits = result
	}

	private val locks: Array<ReentrantLock> = Array(1.shl(segmentBits)) { ReentrantLock() }
	private val segments: Array<Segment> = Array(1.shl(segmentBits)) { Segment(32, locks[it]) }

	init {
		synchronized(interners) {
			interners.add(WeakReference(this))
		}
	}

	// chained linking hash table backed by plain array
	// while this increase memory usage (linked list), this greatly
	// simplify logic, and make scanning a bit faster given if there are narrow collisions avoidances
	// (assuming past our neighbour there is no such key)
	private inner class Segment(val size: Int, private val lock: ReentrantLock) {
		private val queue = ReferenceQueue<T>()

		val mask = size - 1
		val mem = arrayOfNulls<Ref<T>>(size)
		var stored = 0
		var collisions = 0

		private fun hash(e: Any): Int {
			return HashCommon.mix(e.hashCode()).rotateRight(segmentBits) and mask
		}

		fun remove(ref: Ref<T>): Boolean {
			val hash = hash(ref)
			val mem = mem
			val search = mem[hash]

			if (search == null) {
				return false
			} else if (search === ref) {
				mem[hash] = search.nextEntry
				if (mem[hash] != null) check(--collisions >= 0) { "Collision count turned negative" }
				check(--stored >= 0) { "Stored count turned negative" }
				return true
			} else {
				return search.remove(ref).also {
					if (it) {
						check(--stored >= 0) { "Stored count turned negative" }
						check(--collisions >= 0) { "Collision count turned negative" }
					}
				}
			}
		}

		fun insert(sample: T) {
			stored++
			val ref = Ref(sample, queue)
			val mem = this.mem
			val hash = hash(ref)
			val existing = mem[hash]

			if (existing == null)
				mem[hash] = ref
			else {
				existing.insert(ref)
				collisions++
			}
		}

		fun cleanup(): Int {
			var p: Ref<T>? = queue.poll() as Ref<T>? ?: return 0
			var any = 0

			lock.withLock {
				while (p != null) {
					check(remove(p!!)) { "Unable to remove null entry $p at hash ${hash(p!!)}" }
					p = queue.poll() as Ref<T>?
					any++
				}
			}

			return any
		}

		fun grow(): Segment {
			val old = mem.stream()
				.filter { it != null }
				.flatMap { ObjectArrayList(it!!.iterator()).stream() }
				//.filter { !it.refersTo(null) }
				.map { val v = it.get(); it.clear(); v }
				.filter { it != null }
				.collect(ObjectArrayList.toList())

			val new = Segment(size * 2, lock)
			for (elem in old) new.insert(elem as T)
			return new
		}

		fun search(sample: T, hash: Int): T? {
			val mem = mem
			var search = mem[hash and mask]

			while (search != null) {
				val get = search.get()

				if (get == sample)
					return get
				else
					search = search.nextEntry
			}

			return null
		}
	}

	override fun intern(sample: T): T {
		var hash = HashCommon.mix(sample.hashCode())
		val segmentIndex = hash and actualSegmentBits
		var segment = segments[segmentIndex]

		hash = hash.rotateRight(segmentBits)
		val find = segment.search(sample, hash)
		if (find != null) return find

		locks[segmentIndex].withLock {
			segment = segments[segmentIndex]

			val find = segment.search(sample, hash)
			if (find != null) return find

			if (segment.stored >= segment.mem.size * 0.75f) {
				segment = segment.grow()
				segments[segmentIndex] = segment
			}

			segment.insert(sample)
			return sample
		}
	}
}
