package ru.dbotthepony.kstarbound.world

import it.unimi.dsi.fastutil.ints.IntAVLTreeSet
import it.unimi.dsi.fastutil.longs.Long2ObjectFunction
import it.unimi.dsi.fastutil.longs.Long2ObjectOpenHashMap
import it.unimi.dsi.fastutil.longs.LongArrayList
import it.unimi.dsi.fastutil.objects.Object2IntAVLTreeMap
import it.unimi.dsi.fastutil.objects.ObjectAVLTreeSet
import ru.dbotthepony.kommons.util.AABB
import ru.dbotthepony.kommons.util.KOptional
import ru.dbotthepony.kommons.vector.Vector2d
import ru.dbotthepony.kommons.vector.Vector2i
import ru.dbotthepony.kstarbound.world.entities.AbstractEntity
import ru.dbotthepony.kstarbound.world.entities.tile.TileEntity
import java.util.concurrent.atomic.AtomicInteger
import java.util.function.Predicate

// After some thinking, I decided to go with separate spatial index over
// using chunk/chunkmap as spatial indexing of entities (just like original engine does).

// Advantages of this system include allowing to put entities outside any chunks
// into index and getting rid of "orphaned entities" collection,
// and allowing one entity to have multiple bounding boxes,
// while also setting up ground for better spatial index strategies, if they
// have to be done in the future.
class EntityIndex(val geometry: WorldGeometry) {
	private val lock = Any()
	private val map = Long2ObjectOpenHashMap<Sector>()
	private val factory = Long2ObjectFunction { Sector(it) }
	private val counter = AtomicInteger()

	private fun index(x: Int, y: Int): Long {
		require(x in 0 .. Int.MAX_VALUE) { "x out of range: $x" }
		require(y in 0 .. Int.MAX_VALUE) { "y out of range: $y" }
		return (x.toLong() shl 32) or y.toLong()
	}

	private fun values(index: Long): Pair<Int, Int> {
		return index.ushr(32).toInt() to index.toInt()
	}

	private inner class Sector(val index: Long) : Comparable<Sector> {
		val entries = ObjectAVLTreeSet<Entry>()

		override fun compareTo(other: Sector): Int {
			return index.compareTo(other.index)
		}

		fun add(entry: Entry) {
			entries.add(entry)
		}

		fun remove(entry: Entry) {
			check(entries.remove(entry)) { "Expected to remove spatial entry from spatial sector" }

			if (entries.isEmpty()) {
				check(map.remove(index) == this) { "Tried to remove self from spatial index, but removed something else!" }
			}
		}
	}

	inner class Entry(val value: AbstractEntity) : Comparable<Entry> {
		private val sectors = Object2IntAVLTreeMap<Sector>()
		val id = counter.getAndIncrement()
		private val fixtures = ArrayList<Fixture>(1)

		// default fixture since in most cases it should be enough
		val fixture = Fixture()

		fun intersects(rect: AABB, withEdges: Boolean): Boolean {
			return fixtures.any { it.intersects(rect, withEdges) }
		}

		override fun compareTo(other: Entry): Int {
			return id.compareTo(other.id)
		}

		private fun ref(sector: Sector) {
			val new = sectors.getInt(sector) + 1

			if (new == 1) {
				sector.add(this)
			}

			check(new >= 1)
			sectors.put(sector, new)
		}

		private fun deref(sector: Sector) {
			val result = sectors.getInt(sector) - 1

			if (result <= 0) {
				check(result == 0)
				sectors.removeInt(sector)
				sector.remove(this)
			} else {
				sectors.put(sector, result)
			}
		}

		inner class Fixture {
			init {
				synchronized(lock) {
					fixtures.add(this)
				}
			}

			private var isRemoved = false
			private val sectors = ObjectAVLTreeSet<Sector>()
			private var boxes: List<AABB> = listOf()

			fun intersects(aabb: AABB, withEdges: Boolean): Boolean {
				return boxes.any { if (withEdges) aabb.intersect(it) else aabb.intersectWeak(it) }
			}

			fun move(aabb: AABB) {
				if (isRemoved) return
				val newSectors = LongArrayList()
				val split = geometry.split(aabb).first
				boxes = split

				for (actualRegion in split) {
					val xMin = geometry.x.chunkFromCell(actualRegion.mins.x)
					val xMax = geometry.x.chunkFromCell(actualRegion.maxs.x)

					val yMin = geometry.y.chunkFromCell(actualRegion.mins.y)
					val yMax = geometry.y.chunkFromCell(actualRegion.maxs.y)

					for (x in xMin .. xMax) {
						for (y in yMin .. yMax) {
							newSectors.add(index(x, y))
						}
					}
				}

				if (newSectors.isEmpty) {
					// how?
					clear()
				} else {
					val newSectors0 = newSectors.toLongArray()
					newSectors0.sort()

					synchronized(lock) {
						if (isRemoved) return

						val addSectors = ArrayList<Sector>(0)

						val existingItr = sectors.iterator()
						val newItr = newSectors0.iterator()
						var existing = if (existingItr.hasNext()) existingItr.next() else null
						var sector = newItr.nextLong()

						while (true) {
							if (existing != null && existing.index == sector) {
								// everything is correct
								existing = if (existingItr.hasNext()) existingItr.next() else null

								if (!newItr.hasNext()) {
									break
								} else {
									var nextSector = newItr.nextLong()

									while (nextSector == sector && newItr.hasNext())
										nextSector = newItr.nextLong()

									if (nextSector != sector)
										sector = nextSector
									else
										break
								}

								continue
							}

							if (existing == null || existing.index > sector) {
								// we started to reference new sector
								val get = map.computeIfAbsent(sector, factory)
								addSectors.add(get)
								ref(get)
								// println("Entered sector ${values(sector)}")

								if (!newItr.hasNext()) {
									break
								} else {
									var nextSector = newItr.nextLong()

									while (nextSector == sector && newItr.hasNext())
										nextSector = newItr.nextLong()

									if (nextSector != sector)
										sector = nextSector
									else
										break
								}

								continue
							}

							// `existing` references sector which is no longer valid for this fixture
							deref(existing)
							existingItr.remove()
							// println("Left sector ${values(existing.index)}")
							existing = if (existingItr.hasNext()) existingItr.next() else null
						}

						while (existing != null || existingItr.hasNext()) {
							if (existing == null)
								existing = existingItr.next()

							if (existing!!.index > newSectors0.last()) {
								// println("Left sector ${values(existing.index)}")
								existingItr.remove()
							}

							existing = null
						}

						addSectors.forEach { sectors.add(it) }
					}
				}
			}

			internal fun clear0() {
				sectors.forEach { deref(it) }
				sectors.clear()
			}

			fun clear() {
				synchronized(lock) {
					clear0()
				}
			}

			fun remove() {
				synchronized(lock) {
					isRemoved = true
					sectors.forEach { deref(it) }
					sectors.clear()
					fixtures.remove(this)
				}
			}
		}

		fun remove() {
			synchronized(lock) {
				fixtures.forEach { it.clear0() }
				sectors.keys.forEach { it.remove(this) }
				sectors.clear()
			}
		}
	}

	fun query(rect: AABB, filter: Predicate<in AbstractEntity> = Predicate { true }, withEdges: Boolean = true): List<AbstractEntity> {
		val entriesDirect = ArrayList<AbstractEntity>()

		iterate(rect, withEdges = withEdges, visitor = {
			if (filter.test(it)) entriesDirect.add(it)
		})

		return entriesDirect
	}

	fun any(rect: AABB, filter: Predicate<in AbstractEntity> = Predicate { true }, withEdges: Boolean = true): Boolean {
		return walk(rect, withEdges = withEdges, visitor = {
			if (filter.test(it)) KOptional(true) else KOptional()
		}).orElse(false)
	}

	fun all(rect: AABB, filter: Predicate<in AbstractEntity> = Predicate { true }, withEdges: Boolean = true): Boolean {
		return walk(rect, withEdges = withEdges, visitor = {
			if (!filter.test(it)) KOptional(false) else KOptional()
		}).orElse(true)
	}

	fun first(rect: AABB, filter: Predicate<in AbstractEntity> = Predicate { true }, withEdges: Boolean = true): AbstractEntity? {
		return walk(rect, withEdges = withEdges, visitor = {
			if (filter.test(it)) KOptional(it) else KOptional()
		}).orNull()
	}

	fun tileEntityAt(pos: Vector2i): TileEntity? {
		return first(AABB(pos.toDoubleVector(), pos.toDoubleVector() + Vector2d.POSITIVE_XY), Predicate { it is TileEntity && pos in it.occupySpaces }) as TileEntity?
	}

	fun iterate(rect: AABB, visitor: (AbstractEntity) -> Unit, withEdges: Boolean = true) {
		walk<Unit>(rect, { visitor(it); KOptional()  }, withEdges)
	}

	fun <V> walk(rect: AABB, visitor: (AbstractEntity) -> KOptional<V>, withEdges: Boolean = true): KOptional<V> {
		val seen = IntAVLTreeSet()

		for (actualRegion in geometry.split(rect).first) {
			val xMin = geometry.x.chunkFromCell(actualRegion.mins.x)
			val xMax = geometry.x.chunkFromCell(actualRegion.maxs.x)

			val yMin = geometry.y.chunkFromCell(actualRegion.mins.y)
			val yMax = geometry.y.chunkFromCell(actualRegion.maxs.y)

			for (x in xMin .. xMax) {
				for (y in yMin .. yMax) {
					val sector = map[index(x, y)] ?: continue

					for (entry in sector.entries) {
						if (entry.intersects(actualRegion, withEdges) && seen.add(entry.id)) {
							val visit = visitor(entry.value)

							if (visit.isPresent)
								return visit
						}
					}
				}
			}
		}

		return KOptional()
	}
}
