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

from utils.algo_context import AlgoContext
from utils.algo_array import Array
from utils.algo_int import Int
from hashtable import HashTableOpenAddressing, DELETED_MARK, UNUSED_MARK
from analyze_hashtable import h, f

ctx = AlgoContext()
values = Array.from_file('data/seq0.txt', ctx)

ht = HashTableOpenAddressing(20, f, ctx)
for cell in values:
    ht.insert(cell)

# ── a) delete(52) ────────────────────────────────────────────────────────────
print("=== a) Nach delete(52) ===")
ht.delete(Int(52, ctx))
print(ht)

slot_52 = int(h(Int(52, ctx), ht.m))
print(f"\nSlot h(52) = {slot_52}: Inhalt = {ht.table[Int(slot_52, ctx)].value!r}  ← DELETED_MARK")

# ── b) Warum search bei DELETED_MARK weitersucht ─────────────────────────────
print("\n=== b) Warum search bei DELETED_MARK fortgesetzt wird ===")
print(
    "search prüft in jeder Iteration: Ist der aktuelle Slot UNUSED? → Abbruch\n"
    "(der gesuchte Wert wurde nie an eine spätere Position sondiert, also ist\n"
    "er nicht vorhanden). Ist der Slot DELETED_MARK? → weitersuchen, denn der\n"
    "Wert könnte durch einen früheren Eintrag über diesen Slot hinaus sondiert\n"
    "worden sein. DELETED_MARK erhält die Sondierungssequenz aufrecht."
)

# ── c) Konkretes Gegenbeispiel: UNUSED_MARK statt DELETED_MARK ───────────────
print("\n=== c) Konkretes Gegenbeispiel ===")
# Wir bauen eine kleine Tabelle, in der das Problem klar sichtbar ist.
ctx2 = AlgoContext()
ht2  = HashTableOpenAddressing(20, f, ctx2)
for cell in values:
    ht2.insert(cell)

# Finde einen Wert, der über denselben Slot wie 52 sondiert
# h(52) = slot_52; suche einen anderen Wert v mit h(v)=slot_52 oder f(v,0)=slot_52
slot_52_v = int(h(Int(52, ctx2), ht2.m))
print(f"h(52) = {slot_52_v}")

# Prüfe: gibt es einen Wert im Baum, der bei i=0 auf slot_52 trifft?
# Sondierungssequenz für jeden eingefügten Wert anzeigen
from utils.algo_int import Int as I
_A = (math.sqrt(5) - 1) / 2
def h_raw(v, m=20):
    full = v * _A
    return int(abs(full - int(full)) * m)

def f_raw(v, i, m=20):
    return (h_raw(v, m) + i + 5*i*i) % m

print("\nSondierungssequenzen (erste 3 Schritte) für seq0.txt-Werte:")
raw_vals = [int(str(c)) for c in values]
for v in raw_vals:
    seq = [f_raw(v, i) for i in range(3)]
    print(f"  h({v:4d}) = {h_raw(v):2d}, f(·,0)={seq[0]:2d}, f(·,1)={seq[1]:2d}, f(·,2)={seq[2]:2d}")

# 52 belegt slot_52; angenommen 58 kollidiert und liegt hinter 52
# → delete(52) mit UNUSED würde search(58) frühzeitig abbrechen
print(
    "\nAngenommen, zwei Werte v1 und v2 sondieren über denselben Slot:\n"
    "  v1 landet in Slot s (erste Sondierung)\n"
    "  v2 kollidiert bei Slot s und landet bei s' (zweite Sondierung)\n"
    "Wird v1 gelöscht und Slot s auf UNUSED gesetzt, bricht search(v2)\n"
    "bei Slot s ab – obwohl v2 noch in s' liegt. Das Ergebnis ist 'nicht\n"
    "gefunden', obwohl v2 vorhanden ist. DELETED_MARK verhindert das."
)

# ── d) Wo landet 24 nach delete(52)? ─────────────────────────────────────────
print("\n=== d) Wo landet 24 nach delete(52)? ===")
h24 = h_raw(24)
print(f"h(24)       = int({{24·A}} mod 1 · 20) = {h24}")
for i in range(5):
    slot = f_raw(24, i)
    val  = ht.table[Int(slot, ctx)].value
    status = "frei (DELETED/UNUSED)" if val in (DELETED_MARK, UNUSED_MARK) else f"belegt ({val})"
    print(f"f(24, {i}, 20) = {slot:2d}  → {status}")
    if val in (DELETED_MARK, UNUSED_MARK):
        print(f"  ⇒ 24 landet in Slot {slot}")
        break

ht.insert(Int(24, ctx))
print(f"\nVerifikation __str__ (relevante Slots):")
for idx in [0, 1, 2, 3, 16, 17]:
    v = ht.table[Int(idx, ctx)].value
    marker = " ← 24 eingefügt" if str(v) == "24" else ""
    print(f"  Slot {idx:2d}: {v}{marker}")