import sys, os
_root = os.path.abspath(os.path.join(os.path.dirname(__file__), '..', '..'))
_l07  = os.path.join(_root, 'vorlesung', 'L07_hashtable')
_p06  = os.path.dirname(__file__)
if _l07  not in sys.path: sys.path.insert(0, _l07)
if _root not in sys.path: sys.path.insert(0, _root)
if _p06  not in sys.path: sys.path.insert(0, _p06)

from utils.algo_context import AlgoContext
from utils.algo_array import Array
from hashtable import HashTableOpenAddressing
from analyze_hashtable import h, f
from aufgabe1_chaining import HashTableChaining

ctx = AlgoContext()
values = Array.from_file('data/seq1.txt', ctx)
n = len(values)

# ── a) Größe 90 ───────────────────────────────────────────────────────────────
ht90 = HashTableOpenAddressing(90, f, ctx)
inserted90 = sum(1 for cell in values if ht90.insert(cell))
rejected90 = n - inserted90
print("=== a) HashTableOpenAddressing m=90, seq1.txt (100 Werte) ===")
print(f"Eingefügt: {inserted90}, Abgewiesen: {rejected90}, "
      f"Freie Slots: {90 - inserted90}")
print(
    "Ursache: Die quadratische Sondierungsfunktion f(x,i) = (h(x)+i+5i²) mod m\n"
    "erzeugt für m=90 (keine Primzahl) zyklische Sondierungssequenzen, die nicht\n"
    "alle 90 Slots abdecken. Sobald alle erreichbaren Slots belegt sind, schlägt\n"
    "insert fehl – auch wenn noch andere Slots frei sind."
)

# ── b) Größe 89 ───────────────────────────────────────────────────────────────
ctx2 = AlgoContext()
values2 = Array.from_file('data/seq1.txt', ctx2)
ht89 = HashTableOpenAddressing(89, f, ctx2)
inserted89 = sum(1 for cell in values2 if ht89.insert(cell))
rejected89 = n - inserted89
print(f"\n=== b) HashTableOpenAddressing m=89 (Primzahl), seq1.txt ===")
print(f"Eingefügt: {inserted89}, Abgewiesen: {rejected89}")
print(
    "Bei Primzahlgröße garantiert die quadratische Sondierung, dass mindestens\n"
    "m/2 verschiedene Slots erreicht werden (bei geeigneten Konstanten c1, c2\n"
    "sogar alle m). Für m=89 ist die Sondierungssequenz deutlich länger, bevor\n"
    "sie sich wiederholt – dadurch können mehr Werte platziert werden."
)

# ── c) HashTableChaining m=20, seq1.txt ───────────────────────────────────────
ctx3 = AlgoContext()
values3 = Array.from_file('data/seq1.txt', ctx3)
htc = HashTableChaining(20, h, ctx3)
for cell in values3:
    htc.insert(cell)
print(f"\n=== c) HashTableChaining m=20, seq1.txt ===")
unique = len(set(int(str(c)) for c in values3))
print(f"Eingefügt: {htc._n} (seq1.txt hat {n} Werte, davon {unique} eindeutig; "
      f"Duplikate werden nicht doppelt gespeichert)")
print(f"Belegungsfaktor α = {htc._n}/{int(htc.m)} = {htc.alpha():.2f}")
print("Verkettung hat keine Kapazitätsgrenze – die Ketten wachsen unbegrenzt.")

# ── d) Theoretische Sondierungsanzahl ─────────────────────────────────────────
print("\n=== d) Mittlere Sondierungsanzahl 1/(1-α) ===")
for alpha in [0.5, 0.9]:
    probes = 1 / (1 - alpha)
    print(f"  α = {alpha}: 1/(1−{alpha}) = {probes:.1f} Sondierungen")
print(
    "Bis α ≈ 0,7 bleibt die offene Adressierung praktikabel (≈ 3,3 Sondierungen).\n"
    "Für α > 0,8 steigen die Kosten rapide; α = 0,9 bedeutet bereits 10 Sondierungen\n"
    "im Schnitt. Als Faustregel gilt: Tabelle vergrößern (Rehashing), wenn α > 0,75."
)