From 63669bc28be11adbf55c8d49bb747bb22124be86 Mon Sep 17 00:00:00 2001
From: Linnea Gräf <nea@nea.moe>
Date: Wed, 7 May 2025 23:09:10 +0200
Subject: feat: Add more complex entity equipment scraper

---
 src/main/kotlin/util/math/GChainReconciliation.kt | 102 ++++++++++++++++++++++
 1 file changed, 102 insertions(+)
 create mode 100644 src/main/kotlin/util/math/GChainReconciliation.kt

(limited to 'src/main/kotlin/util')

diff --git a/src/main/kotlin/util/math/GChainReconciliation.kt b/src/main/kotlin/util/math/GChainReconciliation.kt
new file mode 100644
index 0000000..37998d5
--- /dev/null
+++ b/src/main/kotlin/util/math/GChainReconciliation.kt
@@ -0,0 +1,102 @@
+package moe.nea.firmament.util.math
+
+import kotlin.math.min
+
+/**
+ * Algorithm for (sort of) cheap reconciliation of two cycles with missing frames.
+ */
+object GChainReconciliation {
+	// Step one: Find the most common element and shift the arrays until it is at the start in both (this could be just rotating until minimal levenshtein distance or smth. that would be way better for cycles with duplicates, but i do not want to implement levenshtein as well)
+	// Step two: Find the first different element.
+	// Step three: Find the next index of both of the elements.
+	// Step four: Insert the element that is further away.
+
+	fun <T> Iterable<T>.frequencies(): Map<T, Int> {
+		val acc = mutableMapOf<T, Int>()
+		for (t in this) {
+			acc.compute(t, { _, old -> (old ?: 0) + 1 })
+		}
+		return acc
+	}
+
+	fun <T> findMostCommonlySharedElement(
+		leftChain: List<T>,
+		rightChain: List<T>,
+	): T {
+		val lf = leftChain.frequencies()
+		val rf = rightChain.frequencies()
+		val mostCommonlySharedElement = lf.maxByOrNull { min(it.value, rf[it.key] ?: 0) }?.key
+		if (mostCommonlySharedElement == null || mostCommonlySharedElement !in rf)
+			error("Could not find a shared element")
+		return mostCommonlySharedElement
+	}
+
+	fun <T> List<T>.getMod(index: Int): T {
+		return this[index.mod(size)]
+	}
+
+	fun <T> List<T>.rotated(offset: Int): List<T> {
+		val newList = mutableListOf<T>()
+		for (index in indices) {
+			newList.add(getMod(index - offset))
+		}
+		return newList
+	}
+
+	fun <T> shiftToFront(list: List<T>, element: T): List<T> {
+		val shiftDistance = list.indexOf(element)
+		require(shiftDistance >= 0)
+		return list.rotated(-shiftDistance)
+	}
+
+	fun <T> List<T>.indexOfOrMaxInt(element: T): Int = indexOf(element).takeUnless { it < 0 } ?: Int.MAX_VALUE
+
+	fun <T> reconcileCycles(
+		leftChain: List<T>,
+		rightChain: List<T>,
+	): List<T> {
+		val mostCommonElement = findMostCommonlySharedElement(leftChain, rightChain)
+		val left = shiftToFront(leftChain, mostCommonElement).toMutableList()
+		val right = shiftToFront(rightChain, mostCommonElement).toMutableList()
+
+		var index = 0
+		while (index < left.size && index < right.size) {
+			val leftEl = left[index]
+			val rightEl = right[index]
+			if (leftEl == rightEl) {
+				index++
+				continue
+			}
+			val nextLeftInRight = right.subList(index, right.size)
+				.indexOfOrMaxInt(leftEl)
+
+			val nextRightInLeft = left.subList(index, left.size)
+				.indexOfOrMaxInt(rightEl)
+			if (nextLeftInRight < nextRightInLeft) {
+				left.add(index, rightEl)
+			} else if (nextRightInLeft < nextLeftInRight) {
+				right.add(index, leftEl)
+			} else {
+				index++
+			}
+		}
+		return if (left.size < right.size) right else left
+	}
+
+	fun <T> isValidCycle(longList: List<T>, cycle: List<T>): Boolean {
+		for ((i, value) in longList.withIndex()) {
+			if (cycle.getMod(i) != value)
+				return false
+		}
+		return true
+	}
+
+	fun <T> List<T>.shortenCycle(): List<T> {
+		for (i in (1..<size)) {
+			if (isValidCycle(this, subList(0, i)))
+				return subList(0, i)
+		}
+		return this
+	}
+
+}
-- 
cgit