package connpool

import "sort"

// VanDerCorput returns the i-th value of the binary Van der Corput
// low-discrepancy sequence in [0,1): write i in binary, reverse the bits,
// read back as a fraction. Successive points always land in the largest
// remaining gap — no clumping. Used to place GATEWAYS on the ring so
// their subsets evenly cover the origins even as the fleet changes.
func VanDerCorput(i uint32) float64 {
	var rev uint32
	for b := 0; b < 32; b++ {
		rev = (rev << 1) | (i & 1)
		i >>= 1
	}
	return float64(rev) / float64(1<<32)
}

// fnv1a32 is a stable, well-distributed hash used to position ORIGINS on
// the ring by identity (so removing one origin does not move the others).
func fnv1a32(s string) uint32 {
	var h uint32 = 2166136261
	for i := 0; i < len(s); i++ {
		h ^= uint32(s[i])
		h *= 16777619
	}
	return h
}

func originPos(origin string) float64 { return float64(fnv1a32(origin)) / float64(1<<32) }

type ringPoint struct {
	pos    float64
	origin string
}

// Ring places origins on [0,1) by stable hash. A gateway takes the
// `size` origins clockwise from its own ring position. Because origin
// positions are stable, removing/adding one origin only perturbs the
// gateways whose window touched it — not the whole fleet (contrast with
// hash-mod subsetting, which reshuffles everything when the count
// changes).
type Ring struct {
	points []ringPoint
}

func BuildRing(origins []string) *Ring {
	pts := make([]ringPoint, len(origins))
	for i, o := range origins {
		pts[i] = ringPoint{pos: originPos(o), origin: o}
	}
	sort.Slice(pts, func(a, b int) bool {
		if pts[a].pos == pts[b].pos {
			return pts[a].origin < pts[b].origin // stable tiebreak
		}
		return pts[a].pos < pts[b].pos
	})
	return &Ring{points: pts}
}

// SubsetAt returns the `size` origins clockwise from pos.
func (r *Ring) SubsetAt(pos float64, size int) []string {
	n := len(r.points)
	if size >= n {
		out := make([]string, n)
		for i, p := range r.points {
			out[i] = p.origin
		}
		return out
	}
	start := sort.Search(n, func(i int) bool { return r.points[i].pos >= pos })
	out := make([]string, 0, size)
	for i := 0; i < size; i++ {
		out = append(out, r.points[(start+i)%n].origin)
	}
	return out
}

// GatewayPos places gateway `idx` on the ring using the Van der Corput
// sequence, so the fleet is spread evenly without coordination.
func GatewayPos(idx int) float64 { return VanDerCorput(uint32(idx)) }

// SubsetForGateway returns gateway idx's subset of `size` origins.
func (r *Ring) SubsetForGateway(idx, size int) []string {
	return r.SubsetAt(GatewayPos(idx), size)
}

// Coverage counts, for each origin, how many gateways' subsets include
// it. Even coverage => even load on origins.
func Coverage(origins []string, gateways, subsetSize int) map[string]int {
	ring := BuildRing(origins)
	cov := map[string]int{}
	for _, o := range origins {
		cov[o] = 0
	}
	for g := 0; g < gateways; g++ {
		for _, o := range ring.SubsetForGateway(g, subsetSize) {
			cov[o]++
		}
	}
	return cov
}

// HashModSubset is the naive alternative: subset = `size` origins chosen
// by (hash(gateway)+j) mod len. It is unstable: when len changes (a
// member joins/leaves), the modulus changes and nearly every assignment
// moves. Provided for the stability comparison in tests.
func HashModSubset(origins []string, gatewayIdx, size int) []string {
	n := len(origins)
	if n == 0 {
		return nil
	}
	if size > n {
		size = n
	}
	start := int(VanDerCorput(uint32(gatewayIdx)) * float64(n)) // any per-gw seed
	out := make([]string, 0, size)
	for j := 0; j < size; j++ {
		out = append(out, origins[(start+j)%n])
	}
	return out
}