conformance_test.go

package height_interval_test

import (
	"bytes"
	"encoding/json"
	"net/http"
	"os"
	"strings"
	"testing"

	hi "github.com/alexes.dev/height_interval"
)

// Queue is the behavior every implementation must satisfy — the in-process Go
// original, or a remote Python/TypeScript server reached over HTTP. The same
// conformance scenarios run against each backend, so all ports stay equivalent.
type Queue interface {
	Push(it hi.Interval) bool
	PopGaps(bound hi.Interval, maxSize, maxCount int64) hi.IntervalQueue
	Cut(it hi.Interval) bool
	Size() int64
	RemainingSize(available hi.Interval) int64
	AllHeights() []int64
	Snapshot() hi.IntervalQueue
	ContainsHeight(h int64) bool
	FullyCovered(bound hi.Interval) bool
	PeekGaps(bound hi.Interval, maxSize, maxCount int64) hi.IntervalQueue
	Merge(other hi.IntervalQueue)
	Len() int
	Frontier() hi.Interval
	GapCount(bound hi.Interval) int
}

type factory func(initial hi.IntervalQueue) Queue

// ── native (in-process Go) ────────────────────────────────────────────────────

type nativeQueue struct{ q *hi.IntervalQueue }

func newNative(initial hi.IntervalQueue) Queue {
	c := initial.Copy()
	return &nativeQueue{q: &c}
}

func (n *nativeQueue) Push(it hi.Interval) bool { return n.q.Push(it) }
func (n *nativeQueue) PopGaps(b hi.Interval, size, count int64) hi.IntervalQueue {
	return n.q.PopGaps(b, size, count)
}
func (n *nativeQueue) Cut(it hi.Interval) bool           { return n.q.Cut(it) }
func (n *nativeQueue) Size() int64                       { return n.q.Size() }
func (n *nativeQueue) RemainingSize(a hi.Interval) int64 { return n.q.RemainingSize(a) }
func (n *nativeQueue) AllHeights() []int64               { return n.q.AllHeights() }
func (n *nativeQueue) Snapshot() hi.IntervalQueue        { return n.q.Copy() }
func (n *nativeQueue) ContainsHeight(h int64) bool       { return n.q.ContainsHeight(h) }
func (n *nativeQueue) FullyCovered(b hi.Interval) bool   { return n.q.FullyCovered(b) }
func (n *nativeQueue) PeekGaps(b hi.Interval, size, count int64) hi.IntervalQueue {
	return n.q.PeekGaps(b, size, count)
}
func (n *nativeQueue) Merge(other hi.IntervalQueue) { n.q.Merge(other) }
func (n *nativeQueue) Len() int                     { return n.q.Len() }
func (n *nativeQueue) Frontier() hi.Interval        { return n.q.Frontier() }
func (n *nativeQueue) GapCount(b hi.Interval) int   { return n.q.GapCount(b) }

// ── remote (HTTP to another implementation) ───────────────────────────────────

// httpQueue mirrors the queue state on the client and ships it with every call.
// The remote server is a pure function: it receives the queue plus the operation
// and returns the result and the new queue. No server-side sessions.
type httpQueue struct {
	t     *testing.T
	base  string
	state hi.IntervalQueue
}

func newHTTPFactory(t *testing.T, base string) factory {
	return func(initial hi.IntervalQueue) Queue {
		return &httpQueue{t: t, base: base, state: initial.Copy()}
	}
}

func (h *httpQueue) call(path string, req, resp any) {
	body, err := json.Marshal(req)
	if err != nil {
		h.t.Fatalf("marshal %s: %v", path, err)
	}
	r, err := http.Post(h.base+path, "application/json", bytes.NewReader(body))
	if err != nil {
		h.t.Fatalf("POST %s: %v", path, err)
	}
	defer r.Body.Close()
	if r.StatusCode != http.StatusOK {
		h.t.Fatalf("POST %s: status %s", path, r.Status)
	}
	if err := json.NewDecoder(r.Body).Decode(resp); err != nil {
		h.t.Fatalf("decode %s: %v", path, err)
	}
}

func (h *httpQueue) Push(it hi.Interval) bool {
	var resp struct {
		Added bool             `json:"added"`
		Queue hi.IntervalQueue `json:"queue"`
	}
	h.call("/push", map[string]any{"queue": h.state, "interval": it}, &resp)
	h.state = resp.Queue
	return resp.Added
}

func (h *httpQueue) PopGaps(b hi.Interval, size, count int64) hi.IntervalQueue {
	var resp struct {
		Gaps  hi.IntervalQueue `json:"gaps"`
		Queue hi.IntervalQueue `json:"queue"`
	}
	h.call("/popgaps", map[string]any{"queue": h.state, "bound": b, "maxSize": size, "maxCount": count}, &resp)
	h.state = resp.Queue
	return resp.Gaps
}

func (h *httpQueue) Cut(it hi.Interval) bool {
	var resp struct {
		Cut   bool             `json:"cut"`
		Queue hi.IntervalQueue `json:"queue"`
	}
	h.call("/cut", map[string]any{"queue": h.state, "interval": it}, &resp)
	h.state = resp.Queue
	return resp.Cut
}

func (h *httpQueue) Size() int64 {
	var resp struct {
		Size int64 `json:"size"`
	}
	h.call("/size", map[string]any{"queue": h.state}, &resp)
	return resp.Size
}

func (h *httpQueue) RemainingSize(a hi.Interval) int64 {
	var resp struct {
		Remaining int64 `json:"remaining"`
	}
	h.call("/remaining", map[string]any{"queue": h.state, "available": a}, &resp)
	return resp.Remaining
}

func (h *httpQueue) AllHeights() []int64 {
	var resp struct {
		Heights []int64 `json:"heights"`
	}
	h.call("/allheights", map[string]any{"queue": h.state}, &resp)
	return resp.Heights
}

func (h *httpQueue) Snapshot() hi.IntervalQueue { return h.state.Copy() }

func (h *httpQueue) ContainsHeight(height int64) bool {
	var resp struct{ Contains bool `json:"contains"` }
	h.call("/containsheight", map[string]any{"queue": h.state, "height": height}, &resp)
	return resp.Contains
}

func (h *httpQueue) FullyCovered(bound hi.Interval) bool {
	var resp struct{ Covered bool `json:"covered"` }
	h.call("/fullycovered", map[string]any{"queue": h.state, "bound": bound}, &resp)
	return resp.Covered
}

func (h *httpQueue) PeekGaps(b hi.Interval, size, count int64) hi.IntervalQueue {
	var resp struct{ Gaps hi.IntervalQueue `json:"gaps"` }
	h.call("/peekgaps", map[string]any{"queue": h.state, "bound": b, "maxSize": size, "maxCount": count}, &resp)
	return resp.Gaps
}

func (h *httpQueue) Merge(other hi.IntervalQueue) {
	var resp struct{ Queue hi.IntervalQueue `json:"queue"` }
	h.call("/merge", map[string]any{"queue": h.state, "other": other}, &resp)
	h.state = resp.Queue
}

func (h *httpQueue) Len() int {
	var resp struct{ Len int `json:"len"` }
	h.call("/len", map[string]any{"queue": h.state}, &resp)
	return resp.Len
}

func (h *httpQueue) Frontier() hi.Interval {
	var resp struct{ Frontier hi.Interval `json:"frontier"` }
	h.call("/frontier", map[string]any{"queue": h.state}, &resp)
	return resp.Frontier
}

func (h *httpQueue) GapCount(bound hi.Interval) int {
	var resp struct{ Count int `json:"count"` }
	h.call("/gapcount", map[string]any{"queue": h.state, "bound": bound}, &resp)
	return resp.Count
}

// ── entry points ──────────────────────────────────────────────────────────────

// TestConformance runs every scenario against the native Go implementation, and
// — when HI_REMOTE_URL points at a running server — against that remote one too.
func TestConformance(t *testing.T) {
	t.Run("native", func(t *testing.T) { runConformance(t, newNative) })

	// HI_REMOTE_URL=url  →  subtest "remote"
	// HI_REMOTE_URL_FOO=url  →  subtest "foo"
	for _, env := range os.Environ() {
		if !strings.HasPrefix(env, "HI_REMOTE_URL") {
			continue
		}
		kv := strings.SplitN(env, "=", 2)
		if len(kv) != 2 || kv[1] == "" {
			continue
		}
		suffix := strings.TrimPrefix(kv[0], "HI_REMOTE_URL")
		name := "remote"
		if suffix != "" {
			name = strings.ToLower(strings.TrimPrefix(suffix, "_"))
		}
		base := kv[1]
		t.Run(name, func(t *testing.T) { runConformance(t, newHTTPFactory(t, base)) })
	}
}

func runConformance(t *testing.T, newQueue factory) {
	t.Run("Push", func(t *testing.T) { conformPush(t, newQueue) })
	t.Run("PopGaps", func(t *testing.T) { conformPopGaps(t, newQueue) })
	t.Run("PopGapsMaxCount", func(t *testing.T) { conformPopGapsMaxCount(t, newQueue) })
	t.Run("PopGapsMaxSizeCapsTotal", func(t *testing.T) { conformPopGapsMaxSizeCapsTotal(t, newQueue) })
	t.Run("Cut", func(t *testing.T) { conformCut(t, newQueue) })
	t.Run("RemainingSize", func(t *testing.T) { conformRemainingSize(t, newQueue) })
	t.Run("Real", func(t *testing.T) { conformReal(t, newQueue) })
	t.Run("Real2", func(t *testing.T) { conformReal2(t, newQueue) })
	t.Run("ContainsHeight", func(t *testing.T) { conformContainsHeight(t, newQueue) })
	t.Run("FullyCovered", func(t *testing.T) { conformFullyCovered(t, newQueue) })
	t.Run("PeekGaps", func(t *testing.T) { conformPeekGaps(t, newQueue) })
	t.Run("Merge", func(t *testing.T) { conformMerge(t, newQueue) })
	t.Run("Len", func(t *testing.T) { conformLen(t, newQueue) })
	t.Run("Frontier", func(t *testing.T) { conformFrontier(t, newQueue) })
	t.Run("GapCount", func(t *testing.T) { conformGapCount(t, newQueue) })
}

// ── scenarios ─────────────────────────────────────────────────────────────────

func conformPush(t *testing.T, newQueue factory) {
	cases := []struct {
		name    string
		init    hi.IntervalQueue
		val     hi.Interval
		wantRet bool
		wantFin hi.IntervalQueue
	}{
		{"empty", iq(), iv(1, 2), true, iq(1, 2)},
		{"invalid empty", iq(1, 2), iv(5, 5), false, iq(1, 2)},
		{"invalid negative", iq(1, 2), iv(5, 3), false, iq(1, 2)},
		{"overlap", iq(1, 2), iv(1, 3), false, iq(1, 2)},
		{"insert before", iq(2, 3), iv(0, 1), true, iq(0, 1, 2, 3)},
		{"insert after", iq(0, 1), iv(2, 3), true, iq(0, 1, 2, 3)},
		{"insert middle", iq(0, 1, 4, 5), iv(2, 3), true, iq(0, 1, 2, 3, 4, 5)},
		{"insert middle+collapse", iq(0, 1, 3, 4), iv(1, 3), true, iq(0, 4)},
		{"merge before", iq(2, 3), iv(1, 2), true, iq(1, 3)},
		{"merge after", iq(1, 2), iv(2, 3), true, iq(1, 3)},
	}
	for _, c := range cases {
		q := newQueue(c.init)
		if got := q.Push(c.val); got != c.wantRet {
			t.Errorf("[%s] Push returned %v, want %v", c.name, got, c.wantRet)
		}
		if fin := q.Snapshot(); !eqIQ(fin, c.wantFin) {
			t.Errorf("[%s] queue = %v, want %v", c.name, fin, c.wantFin)
		}
	}
}

func conformPopGaps(t *testing.T, newQueue factory) {
	fin := func(pairs ...int64) *hi.IntervalQueue { q := iq(pairs...); return &q }

	cases := []struct {
		name     string
		init     hi.IntervalQueue
		bound    hi.Interval
		maxSize  int64
		maxCount int64
		wantGaps hi.IntervalQueue
		wantFin  *hi.IntervalQueue
	}{
		{"ignore maxSize=0", nil, iv(1, 2), 0, 0, nil, nil},
		{"ignore invalid bound", nil, iv(1, 0), 0, 0, nil, nil},
		{"partial head", nil, iv(1, 3), 1, 0, iq(2, 3), fin(2, 3)},
		{"full head", nil, iv(1, 2), 2, 0, iq(1, 2), fin(1, 2)},
		{"partial tail", iq(3, 5), iv(1, 5), 1, 0, iq(2, 3), fin(2, 5)},
		{"available_break", iq(3, 4), iv(1, 2), 1, 0, iq(1, 2), fin(1, 2, 3, 4)},
		{"interval_break", iq(1, 3), iv(1, 6), 1, 0, iq(5, 6), fin(1, 3, 5, 6)},
		{"interval_empty", iq(1, 3), iv(1, 5), 2, 0, iq(3, 5), fin(1, 5)},
		{"full tail", iq(3, 5), iv(1, 3), 2, 0, iq(1, 3), fin(1, 5)},
		{"partial middle", iq(3, 4, 7, 8), iv(3, 8), 1, 0, iq(6, 7), fin(3, 4, 6, 8)},
		{"full middle+collapse", iq(3, 5, 7, 8), iv(3, 8), 2, 0, iq(5, 7), fin(3, 8)},
		{"two full gaps", iq(10, 11), iv(1, 20), 50, 0, iq(11, 20, 1, 10), fin(1, 20)},
		{"full+partial gap", iq(10, 11), iv(1, 21), 11, 0, iq(11, 21, 9, 10), fin(9, 21)},
		{"ignore unavailable", iq(10, 11, 20, 21), iv(15, 16), 10, 0, iq(15, 16), fin(10, 11, 15, 16, 20, 21)},
		{"hmm1", iq(50, 52, 55, 56), iv(1, 52), 1, 0, iq(49, 50), fin(49, 52, 55, 56)},
		{"hmm2", iq(50, 51, 55, 56), iv(1, 52), 1, 0, iq(51, 52), fin(50, 52, 55, 56)},
		{"hmm3_size2", iq(50, 51, 55, 56), iv(1, 52), 2, 0, iq(51, 52, 49, 50), fin(49, 52, 55, 56)},
		{"hmm4_size3", iq(50, 51, 55, 56), iv(1, 52), 3, 0, iq(51, 52, 48, 50), fin(48, 52, 55, 56)},
	}

	for _, c := range cases {
		q := newQueue(c.init)
		gaps := q.PopGaps(c.bound, c.maxSize, c.maxCount)
		if !eqIQ(gaps, c.wantGaps) {
			t.Errorf("[%s] gaps = %v, want %v", c.name, gaps, c.wantGaps)
		}
		if c.wantFin != nil {
			if fin := q.Snapshot(); !eqIQ(fin, *c.wantFin) {
				t.Errorf("[%s] fin = %v, want %v", c.name, fin, *c.wantFin)
			}
		}
	}
}

func conformPopGapsMaxCount(t *testing.T, newQueue factory) {
	q := newQueue(iq(50, 51, 55, 56))
	gaps := q.PopGaps(iv(1, 52), 3, 1)
	if !eqIQ(gaps, iq(51, 52)) {
		t.Fatalf("gaps = %v", gaps)
	}
	if fin := q.Snapshot(); !eqIQ(fin, iq(50, 52, 55, 56)) {
		t.Fatalf("queue = %v", fin)
	}
}

// maxSize is a hard cap on the total values returned, even when maxCount asks for
// more gaps than the budget allows: only the newest maxSize values come back.
func conformPopGapsMaxSizeCapsTotal(t *testing.T, newQueue factory) {
	q := newQueue(iq(200, 301))
	gaps := q.PopGaps(iv(1, 401), 50, 3)
	if !eqIQ(gaps, iq(351, 401)) {
		t.Fatalf("gaps = %v", gaps)
	}
	// only [351,401) is claimed; the still-unbudgeted gap [301,351) stays open.
	if fin := q.Snapshot(); !eqIQ(fin, iq(200, 301, 351, 401)) {
		t.Fatalf("queue = %v", fin)
	}
}

func conformCut(t *testing.T, newQueue factory) {
	cases := []struct {
		name    string
		init    hi.IntervalQueue
		it      hi.Interval
		wantRet bool
		wantFin hi.IntervalQueue
	}{
		{"empty", iq(), iv(1, 2), false, iq()},
		{"no overlap", iq(1, 2), iv(3, 4), false, iq(1, 2)},
		{"cut before", iq(1, 2), iv(0, 1), false, iq(1, 2)},
		{"cut before 2", iq(1, 2), iv(0, 2), true, iq()},
		{"cut after", iq(1, 2), iv(2, 3), false, iq(1, 2)},
		{"cut after 2", iq(1, 2), iv(1, 3), true, iq()},
		{"cut middle", iq(1, 4), iv(2, 3), true, iq(1, 2, 3, 4)},
		{"cut overlapped", iq(1, 4, 6, 8, 10, 12, 15, 21), iv(2, 18), true, iq(1, 2, 18, 21)},
	}
	for _, c := range cases {
		q := newQueue(c.init)
		if got := q.Cut(c.it); got != c.wantRet {
			t.Errorf("[%s] Cut returned %v, want %v", c.name, got, c.wantRet)
		}
		if fin := q.Snapshot(); !eqIQ(fin, c.wantFin) {
			t.Errorf("[%s] queue = %v, want %v", c.name, fin, c.wantFin)
		}
	}
}

func conformRemainingSize(t *testing.T, newQueue factory) {
	cases := []struct {
		q    hi.IntervalQueue
		av   hi.Interval
		want int64
	}{
		{iq(1, 10), iv(1, 10), 0},
		{iq(1, 10), iv(1, 11), 1},
		{iq(1, 10), iv(5, 11), 1},
		{iq(1, 10, 20, 30), iv(5, 25), 10},
		{iq(5, 10, 20, 25), iv(1, 30), 19},
	}
	for _, c := range cases {
		q := newQueue(c.q)
		if got := q.RemainingSize(c.av); got != c.want {
			t.Errorf("RemainingSize(%v, %v) = %d, want %d", c.q, c.av, got, c.want)
		}
	}
}

func conformReal(t *testing.T, newQueue factory) {
	available := iv(20286856, 21301987)
	init := hi.IntervalQueue{
		iv(21220382, 21220446), iv(21220510, 21220766), iv(21220894, 21221278),
		iv(21221406, 21221790), iv(21221918, 21222302), iv(21222430, 21222814),
		iv(21222942, 21223582), iv(21223814, 21224198), iv(21224326, 21224710),
		iv(21224838, 21225222), iv(21225350, 21225734), iv(21225862, 21226246),
		iv(21226374, 21226758), iv(21226886, 21227270), iv(21227398, 21227782),
		iv(21227910, 21228294), iv(21228550, 21229164), iv(21229292, 21229676),
		iv(21229804, 21230188), iv(21230316, 21230700), iv(21230828, 21231212),
		iv(21231340, 21231724), iv(21231852, 21232236), iv(21232364, 21232748),
		iv(21232876, 21233260), iv(21233388, 21233516), iv(21233644, 21234131),
		iv(21234259, 21234643), iv(21234771, 21235155), iv(21235283, 21235667),
		iv(21235795, 21236179), iv(21236307, 21236691), iv(21236819, 21237203),
		iv(21237331, 21237715), iv(21237843, 21238035), iv(21238163, 21238859),
		iv(21238890, 21240898), iv(21240907, 21242090), iv(21242187, 21244039),
		iv(21244064, 21301987),
	}

	q := newQueue(init)
	gaps := q.PopGaps(available, 128, 0)
	gaps.SortByLatest()

	expected := hi.IntervalQueue{
		iv(21240907-6, 21240907),
		iv(21244039, 21244064),
		iv(21242090, 21242187),
	}
	expected.SortByLatest()

	if !eqIQ(gaps, expected) {
		t.Fatalf("gaps = %v, want %v", gaps, expected)
	}
}

func conformReal2(t *testing.T, newQueue factory) {
	available := iv(20286856, 21302987)
	init := hi.IntervalQueue{
		iv(21297835, 21297931),
		iv(21297963, 21298283),
		iv(21298347, 21302987),
	}

	q := newQueue(init)

	gaps0 := q.PopGaps(available, 128, 0)
	gaps0.SortByLatest()
	expected := iq(21297803, 21297835, 21297931, 21297963, 21298283, 21298347)
	expected.SortByLatest()
	if !eqIQ(gaps0, expected) {
		t.Fatalf("gaps0 = %v, want %v", gaps0, expected)
	}

	gaps1 := q.PopGaps(available, 128, 0)
	if len(gaps1) == 0 || gaps1[0] != iv(21297675, 21297803) {
		t.Fatalf("gaps1 = %v", gaps1)
	}

	gaps2 := q.PopGaps(available, 128, 0)
	if len(gaps2) == 0 || gaps2[0] != iv(21297547, 21297675) {
		t.Fatalf("gaps2 = %v", gaps2)
	}
}

func conformContainsHeight(t *testing.T, newQueue factory) {
	q := newQueue(iq(1, 5, 10, 20))
	cases := []struct {
		h    int64
		want bool
	}{
		{0, false}, {1, true}, {4, true}, {5, false},
		{9, false}, {10, true}, {19, true}, {20, false},
	}
	for _, c := range cases {
		if got := q.ContainsHeight(c.h); got != c.want {
			t.Errorf("ContainsHeight(%d) = %v, want %v", c.h, got, c.want)
		}
	}
}

func conformFullyCovered(t *testing.T, newQueue factory) {
	q := newQueue(iq(1, 10))
	if !q.FullyCovered(iv(1, 10)) {
		t.Error("exact bound should be covered")
	}
	if !q.FullyCovered(iv(3, 8)) {
		t.Error("inner range should be covered")
	}
	if q.FullyCovered(iv(1, 11)) {
		t.Error("wider bound should not be covered")
	}
	if q.FullyCovered(iv(0, 10)) {
		t.Error("left-wider bound should not be covered")
	}
}

func conformPeekGaps(t *testing.T, newQueue factory) {
	q := newQueue(iq(3, 5, 7, 9))
	snap := q.Snapshot()

	gaps := q.PeekGaps(iv(1, 11), 100, 0)
	if !eqIQ(gaps, iq(9, 11, 5, 7, 1, 3)) {
		t.Errorf("gaps = %v, want [9,11) [5,7) [1,3)", gaps)
	}
	if fin := q.Snapshot(); !eqIQ(fin, snap) {
		t.Error("PeekGaps must not modify the queue")
	}
}

func conformMerge(t *testing.T, newQueue factory) {
	q := newQueue(iq(1, 3, 7, 9))
	q.Merge(iq(3, 5, 11, 13))
	if fin := q.Snapshot(); !eqIQ(fin, iq(1, 5, 7, 9, 11, 13)) {
		t.Errorf("after merge = %v, want [1,5) [7,9) [11,13)", fin)
	}
}

func conformLen(t *testing.T, newQueue factory) {
	if got := newQueue(iq()).Len(); got != 0 {
		t.Errorf("empty Len = %d, want 0", got)
	}
	if got := newQueue(iq(1, 2, 3, 4, 5, 6)).Len(); got != 3 {
		t.Errorf("Len = %d, want 3", got)
	}
}

func conformFrontier(t *testing.T, newQueue factory) {
	if got := newQueue(iq()).Frontier(); got.Valid() {
		t.Errorf("empty frontier should be invalid, got %v", got)
	}
	if got := newQueue(iq(1, 5, 10, 20)).Frontier(); got != iv(1, 20) {
		t.Errorf("frontier = %v, want [1,20)", got)
	}
}

func conformGapCount(t *testing.T, newQueue factory) {
	q := newQueue(iq(3, 5, 7, 9))
	if got := q.GapCount(iv(1, 11)); got != 3 {
		t.Errorf("GapCount([1,11)) = %d, want 3", got)
	}
	if got := q.GapCount(iv(3, 9)); got != 1 {
		t.Errorf("GapCount([3,9)) = %d, want 1", got)
	}
	if got := q.GapCount(iv(3, 5)); got != 0 {
		t.Errorf("GapCount([3,5)) = %d, want 0", got)
	}
}