// 第 11 周 – 用线性探测的开放定址法
// 运行：go run ./w11/linearprobing
package main

import (
	"fmt"
	"math"
	"math/rand"
)

const empty = math.MinInt

type LinearProbing struct {
	table  []int
	probes int
}

func New(m int) *LinearProbing {
	t := make([]int, m)
	for i := range t {
		t[i] = empty
	}
	return &LinearProbing{table: t}
}

func (lp *LinearProbing) hash(k int) int {
	m := len(lp.table)
	return ((k % m) + m) % m
}

func (lp *LinearProbing) Insert(k int) {
	i := lp.hash(k)
	for step := range lp.table {
		lp.probes++
		j := (i + step) % len(lp.table)
		if lp.table[j] == empty || lp.table[j] == k {
			lp.table[j] = k
			return
		}
	}
	panic("the table is full")
}

func (lp *LinearProbing) Contains(k int) bool {
	i := lp.hash(k)
	for step := range lp.table {
		lp.probes++
		j := (i + step) % len(lp.table)
		if lp.table[j] == empty {
			return false
		}
		if lp.table[j] == k {
			return true
		}
	}
	return false
}

func main() {
	t := New(10)
	for _, k := range []int{13, 7, 23, 33} {
		t.Insert(k)
	}
	for i, v := range t.table {
		if v == empty {
			fmt.Printf("%d:-  ", i)
		} else {
			fmt.Printf("%d:%d  ", i, v)
		}
	}
	fmt.Println()
	t.probes = 0
	fmt.Println("Contains(33) =", t.Contains(33), "(", t.probes, "probes )")
	t.probes = 0
	fmt.Println("Contains(43) =", t.Contains(43), "(", t.probes, "probes )")

	fmt.Println("\nLoad factor (α) and average number of probes for a successful search:")
	rnd := rand.New(rand.NewSource(1))
	for _, alpha := range []float64{0.25, 0.5, 0.75, 0.9, 0.99} {
		m := 100_000
		n := int(alpha * float64(m))
		lp := New(m)
		keys := make([]int, n)
		for i := range keys {
			keys[i] = rnd.Intn(math.MaxInt32)
			lp.Insert(keys[i])
		}
		lp.probes = 0
		for _, k := range keys {
			lp.Contains(k)
		}
		fmt.Printf("  α = %.2f: %.2f\n", alpha, float64(lp.probes)/float64(n))
	}
}