height_interval.go

// Package height_interval provides sorted, non-overlapping right-open block-height
// intervals [Earliest, Latest) and an IntervalQueue for gap-aware tracking.
package height_interval

import (
	"fmt"
	"sort"
)

// Interval represents a right-opened interval [Earliest, Latest).
// A value v is inside iff Earliest <= v < Latest.
// The right-open convention means default Interval{0,0}.Valid() == false,
// which simplifies unmarshal-error detection.
type Interval struct {
	Earliest int64 `json:"earliest"`
	Latest   int64 `json:"latest"`
}

func (it Interval) String() string {
	size := it.Size()
	return fmt.Sprintf("[%d, %d) S:%d", it.Earliest, it.Latest, size)
}

// Size returns how many values are in the interval.
func (it Interval) Size() int64 {
	return it.Latest - it.Earliest
}

// Valid returns true if the interval is valid — size greater than 0.
func (it Interval) Valid() bool {
	return it.Size() > 0
}

// Chunks splits the interval into chunks of the given size.
func (it *Interval) Chunks(size int64) []Interval {
	var chunks []Interval

	for i := it.Earliest; i < it.Latest; i += size {
		latest := i + size
		if latest > it.Latest {
			latest = it.Latest
		}
		chunks = append(chunks, Interval{Earliest: i, Latest: latest})
	}

	return chunks
}

// Clamp clamps the interval to the given bound.
func (it *Interval) Clamp(bound Interval) {
	if it.Earliest < bound.Earliest {
		it.Earliest = bound.Earliest
	}
	if it.Latest > bound.Latest {
		it.Latest = bound.Latest
	}
}

// LeftLimit changes the size of the interval to at most the given size,
// keeping Latest fixed. Returns the actual size used.
func (it *Interval) LeftLimit(size int64) int64 {
	curr := it.Size()

	if curr > size {
		it.Earliest = it.Latest - size
		return size
	}

	return curr
}

// Contains reports whether it fully contains other.
func (it Interval) Contains(other Interval) bool {
	return it.Earliest <= other.Earliest && it.Latest >= other.Latest
}

// Overlaped returns true if the intervals overlap.
func (it *Interval) Overlaped(other Interval) bool {
	return it.Earliest < other.Latest && other.Earliest < it.Latest
}

// IntervalQueue is a sorted, non-overlapping slice of Interval.
// It must always be sorted and non-overlapping.
// Push merges touching intervals automatically.
type IntervalQueue []Interval

// SortByLatest sorts the slice by .Latest ascending.
func (iq *IntervalQueue) SortByLatest() {
	sort.Slice(*iq, func(i, j int) bool {
		return (*iq)[i].Latest < (*iq)[j].Latest
	})
}

// Push inserts the interval into the queue. Returns true if added.
// Returns false if the interval overlaps with an existing one.
// Collapses or merges touching intervals: [1,2) + [2,3) → [1,3).
func (iq *IntervalQueue) Push(it Interval) bool {
	if !it.Valid() {
		return false
	}

	idx := sort.Search(len(*iq), func(i int) bool {
		return (*iq)[i].Earliest > it.Earliest
	})

	if idx < len(*iq) && (*iq)[idx].Overlaped(it) {
		return false
	}

	if idx > 0 && (*iq)[idx-1].Overlaped(it) {
		return false
	}

	touchEarliest := idx > 0 && (*iq)[idx-1].Latest == it.Earliest
	touchLatest := idx < len(*iq) && (*iq)[idx].Earliest == it.Latest

	if touchEarliest && touchLatest {
		// collapse the previous and the current to one
		(*iq)[idx-1].Latest = (*iq)[idx].Latest
		*iq = append((*iq)[:idx], (*iq)[idx+1:]...)
		return true
	}

	if touchEarliest {
		// merge with the previous
		(*iq)[idx-1].Latest = it.Latest
		return true
	}

	if touchLatest {
		// merge with the current
		(*iq)[idx].Earliest = it.Earliest
		return true
	}

	*iq = append(*iq, Interval{})
	copy((*iq)[idx+1:], (*iq)[idx:])
	(*iq)[idx] = it

	return true
}

// Size returns the total size of all intervals in the queue.
func (iq *IntervalQueue) Size() int64 {
	var size int64
	for _, it := range *iq {
		size += it.Size()
	}
	return size
}

// PopGaps returns unprocessed ranges within bound, newest-first, and claims each
// one in the same call (via Push) so the same range is never returned twice.
// It returns at most maxSize values in total across all gaps, and — when
// maxCount > 0 — at most maxCount gaps. Returns nil when bound is invalid,
// maxSize <= 0, or bound is already fully covered.
func (iq *IntervalQueue) PopGaps(bound Interval, maxSize, maxCount int64) IntervalQueue {
	if maxSize <= 0 || !bound.Valid() {
		return nil
	}

	gaps := iq.findGaps(bound, maxSize, maxCount)
	for _, gap := range gaps {
		iq.Push(gap)
	}

	return gaps
}

// findGaps walks the complement of the queue within bound, newest-first, without
// mutating the queue. It stops once maxSize values have been collected in total,
// or — when maxCount > 0 — once maxCount gaps have been collected.
func (iq IntervalQueue) findGaps(bound Interval, maxSize, maxCount int64) IntervalQueue {
	var (
		gaps  IntervalQueue
		total int64
	)

	// ceil is the upper edge of the next gap, walked down from the chain tip.
	ceil := bound.Latest

	// collect clamps a gap candidate to bound, claims as much of it as the budget
	// allows (newest values first), and reports whether the budget is now spent.
	collect := func(gap Interval) (spent bool) {
		gap.Clamp(bound)
		if !gap.Valid() {
			return false
		}
		total += gap.LeftLimit(maxSize - total)
		gaps = append(gaps, gap)
		return total >= maxSize || (maxCount > 0 && int64(len(gaps)) >= maxCount)
	}

	for i := len(iq) - 1; i >= 0; i-- {
		it := iq[i]
		if collect(Interval{Earliest: it.Latest, Latest: ceil}) {
			return gaps
		}
		if it.Earliest < ceil {
			ceil = it.Earliest
		}
	}

	collect(Interval{Earliest: bound.Earliest, Latest: ceil})
	return gaps
}

// Cut removes it from the queue, splitting intervals as needed.
// Returns true if anything was actually removed.
func (iq *IntervalQueue) Cut(it Interval) bool {
	cutted := false
	newQueue := IntervalQueue{}

	for _, current := range *iq {
		if current.Overlaped(it) {
			cutted = true
			switch {
			case current.Earliest < it.Earliest && current.Latest > it.Latest:
				// cutting interval is completely within current — split into two
				newQueue = append(newQueue, Interval{Earliest: current.Earliest, Latest: it.Earliest})
				newQueue = append(newQueue, Interval{Earliest: it.Latest, Latest: current.Latest})
			case current.Earliest < it.Earliest:
				// cut chops off the end part
				newQueue = append(newQueue, Interval{Earliest: current.Earliest, Latest: it.Earliest})
			case current.Latest > it.Latest:
				// cut chops off the start part
				newQueue = append(newQueue, Interval{Earliest: it.Latest, Latest: current.Latest})
				// else: entire current interval covered — drop it
			}
		} else {
			newQueue = append(newQueue, current)
		}
	}

	*iq = newQueue
	return cutted
}

// AllHeights expands every interval into a flat slice of individual heights.
// Memory: 8 bytes × total values.
func (iq IntervalQueue) AllHeights() []int64 {
	heights := []int64{}
	for _, it := range iq {
		for i := it.Earliest; i < it.Latest; i++ {
			heights = append(heights, i)
		}
	}
	return heights
}

func (iq IntervalQueue) String() string {
	q := iq
	q.SortByLatest()

	str := "[ "
	for idx, it := range q {
		if idx > 0 {
			str += fmt.Sprintf("{GAP:%d} ", it.Earliest-q[idx-1].Latest)
		}
		str += it.String() + " "
	}

	return fmt.Sprintf("%s TOTAL %d]", str, iq.Size())
}

// RemainingSize returns how many values in availableInterval are not covered
// by any interval in the queue.
func (iq IntervalQueue) RemainingSize(availableInterval Interval) int64 {
	remaining := availableInterval.Size()
	for _, it := range iq {
		it.Clamp(availableInterval)
		remaining -= it.Size()
	}
	return remaining
}

// Copy returns a deep copy of the queue.
func (iq IntervalQueue) Copy() IntervalQueue {
	newQueue := make(IntervalQueue, len(iq))
	copy(newQueue, iq)
	return newQueue
}

// ContainsHeight reports whether h is covered by any interval in the queue.
func (iq IntervalQueue) ContainsHeight(h int64) bool {
	idx := sort.Search(len(iq), func(i int) bool { return iq[i].Latest > h })
	return idx < len(iq) && iq[idx].Earliest <= h
}

// FullyCovered reports whether every value in bound is covered by the queue.
func (iq IntervalQueue) FullyCovered(bound Interval) bool {
	return iq.RemainingSize(bound) == 0
}

// PeekGaps returns unprocessed ranges within bound, newest-first, without
// modifying the queue. Identical to PopGaps except nothing is claimed.
func (iq IntervalQueue) PeekGaps(bound Interval, maxSize, maxCount int64) IntervalQueue {
	if maxSize <= 0 || !bound.Valid() {
		return nil
	}
	return iq.findGaps(bound, maxSize, maxCount)
}

// Merge pushes every interval from other into the queue.
// Overlapping intervals in other are silently skipped.
func (iq *IntervalQueue) Merge(other IntervalQueue) {
	for _, it := range other {
		iq.Push(it)
	}
}

// Len returns the number of distinct intervals stored (not the total value count).
func (iq IntervalQueue) Len() int {
	return len(iq)
}

// Frontier returns [earliest.Earliest, latest.Latest) spanning the full queue.
// Returns a zero (invalid) Interval when the queue is empty.
func (iq IntervalQueue) Frontier() Interval {
	if len(iq) == 0 {
		return Interval{}
	}
	return Interval{Earliest: iq[0].Earliest, Latest: iq[len(iq)-1].Latest}
}

// GapCount returns how many unprocessed gaps exist within bound without
// modifying the queue.
func (iq IntervalQueue) GapCount(bound Interval) int {
	if !bound.Valid() {
		return 0
	}
	return len(iq.findGaps(bound, bound.Size(), 0))
}