// 11. hét – Hash tábla láncolással (string kulcs -> int érték)
// Futtatás: go run ./h11/hashtable
package main

import "fmt"

type entry struct {
	key   string
	value int
	next  *entry
}

type HashTable struct {
	buckets []*entry
	size    int
}

func NewHashTable(m int) *HashTable { return &HashTable{buckets: make([]*entry, m)} }

// hash: polinomiális hash, h = (h·31 + c) mod m (kódpontonként)
func (t *HashTable) hash(key string) int {
	h := 0
	for _, c := range key {
		h = (h*31 + int(c)) % len(t.buckets)
	}
	return h
}

func (t *HashTable) Put(key string, value int) {
	i := t.hash(key)
	for e := t.buckets[i]; e != nil; e = e.next {
		if e.key == key {
			e.value = value
			return
		}
	}
	t.buckets[i] = &entry{key, value, t.buckets[i]}
	t.size++
	if float64(t.size) > 0.75*float64(len(t.buckets)) {
		t.resize()
	}
}

func (t *HashTable) Get(key string) (int, bool) {
	for e := t.buckets[t.hash(key)]; e != nil; e = e.next {
		if e.key == key {
			return e.value, true
		}
	}
	return 0, false
}

func (t *HashTable) Remove(key string) bool {
	i := t.hash(key)
	var prev *entry
	for e := t.buckets[i]; e != nil; prev, e = e, e.next {
		if e.key == key {
			if prev == nil {
				t.buckets[i] = e.next
			} else {
				prev.next = e.next
			}
			t.size--
			return true
		}
	}
	return false
}

func (t *HashTable) resize() {
	old := t.buckets
	t.buckets = make([]*entry, 2*len(old))
	t.size = 0
	for _, head := range old {
		for e := head; e != nil; e = e.next {
			t.Put(e.key, e.value)
		}
	}
}

func (t *HashTable) Print() {
	for i, head := range t.buckets {
		s := ""
		for e := head; e != nil; e = e.next {
			s += fmt.Sprintf("%s=%d -> ", e.key, e.value)
		}
		if s == "" {
			s = "∅"
		} else {
			s += "nil"
		}
		fmt.Printf("  [%2d] %s\n", i, s)
	}
}

func main() {
	t := NewHashTable(11)
	names := []string{"Li", "Wang", "Chen", "Anna", "Péter", "Zhou", "Liu", "Yang"}
	for i, n := range names {
		t.Put(n, 20+i)
	}
	fmt.Printf("%d elem, m = %d, α = %.2f\n", t.size, len(t.buckets), float64(t.size)/float64(len(t.buckets)))
	t.Print()
	v, ok := t.Get("Chen")
	_, ok2 := t.Get("Zhang")
	fmt.Println(`Get("Chen") =`, v, ok, `, Get("Zhang") megvan?`, ok2)
	t.Put("Zhang", 28)
	fmt.Printf("\nPut(\"Zhang\") után újrahashelés: m = %d, α = %.2f\n", len(t.buckets), float64(t.size)/float64(len(t.buckets)))
	t.Print()
	t.Remove("Li")
	_, ok3 := t.Get("Li")
	fmt.Println(`Remove("Li") után megvan?`, ok3, ", elemszám =", t.size)
}