rangeable

README

GoRangeable

Reference Go implementation of Rangeable<Element> — a generic, integer-coordinate, closed-interval set container with first-insert ordered active queries.

Installation

go get github.com/ZhgChgLi/GoRangeable@v1.0.0

Standard library only — no external dependencies.

Usage

package main

import (
    "fmt"

    rangeable "github.com/ZhgChgLi/GoRangeable"
)

type Strong struct{}
type Italic struct{}
type Link struct{ URL string }

func main() {
    r := rangeable.New[any]()
    _ = r.Insert(Strong{}, 2, 5)
    _ = r.Insert(Strong{}, 3, 7)        // merges with [2, 5] → [2, 7]
    _ = r.Insert(Strong{}, 9, 11)       // disjoint
    _ = r.Insert(Italic{}, 3, 8)

    fmt.Println(r.GetRange(Strong{}))   // [{2 7} {9 11}]
    fmt.Println(r.GetRange(Italic{}))   // [{3 8}]

    fmt.Println(r.At(4).Objs)           // [{} {}] (Strong, Italic)
    fmt.Println(r.At(8).Objs)           // [{}] (Italic)
}

Sweep iteration via transitions

for _, ev := range r.Transitions(0, intPtr(15)) {
    coord := "+∞"
    if ev.Coordinate != nil {
        coord = fmt.Sprintf("%d", *ev.Coordinate)
    }
    fmt.Println(coord, ev.Kind, ev.Element)
}

API

Member	Returns	Notes
New[E comparable]()	*Rangeable[E]	empty container
r.Insert(e, start, end)	error	returns *InvalidIntervalError on start > end
r.At(i)	Slot[E]	Slot.Objs is the active-set slice
r.GetRange(e)	[]Interval	merged disjoint ranges
r.Transitions(from, to *int)	[]TransitionEvent[E]	to == nil means +∞
r.Size()	int	distinct elements
r.IsEmpty()	bool
r.Each(fn)	iterates (element, intervals)	first-insert order
r.Copy()	*Rangeable[E]	deep copy
r.Version()	int	unchanged on idempotent insert

Element type

Rangeable[E comparable] accepts any comparable Go type:

• Primitive types (int, string, …)
• Struct types whose fields are all comparable
• Interface types (compared by ==)
• Pointer types (compared by reference)

This matches RFC §4.2 (E1–E5) — Go's built-in == is reflexive, symmetric, transitive, and consistent with the runtime hash used by maps.

type Strong struct{}
type Link struct{ URL string }

// Strong{} == Strong{} (zero-field struct equality)
// Link{"a"} == Link{"a"}
// Link{"a"} != Link{"b"}

For element types whose equivalence cannot be expressed via ==, wrap them in a comparable adapter struct.

Semantics

• End is inclusive: Insert(e, a, b) covers [a, b], both ends.
• Same-element merging: equal elements (by ==) merge on overlap or integer adjacency. [2, 4] ∪ [5, 7] = [2, 7].
• Idempotent insert: re-inserting a contained interval does not bump Version.
• Out-of-order rejected: Insert(e, 5, 2) returns *InvalidIntervalError (matches errors.Is(err, ErrInvalidInterval)).
• Active-set ordering: deterministic — first-insert order of the element.
• Coordinate sentinel: a close event for an interval ending at the optional IntMaxSentinel carries Coordinate == nil (nil == +∞ per RFC §4.7).

See RangeableRFC § 4 for normative semantics and § 10 for the 23-case test contract.

Cross-language consistency

This Go implementation joins the Ruby, Swift, Python, JS and Kotlin implementations. All six share a 160-op / 86-probe JSON fixture and produce byte-identical outputs.

See also

• RangeableRFC — normative specification.
• RubyRangeable — Ruby reference (gem install rangeable).
• SwiftRangeable — Swift reference (SPM).
• PythonRangeable — Python reference (pip install rangeable).
• JSRangeable — TypeScript reference (npm i rangeable-js).
• KotlinRangeable — Kotlin/JVM reference (JitPack).

Development

go test ./...           # run the suite
go test -run Cross ./... # cross-language fixture only
go vet ./...

The suite covers the full RFC § 10 contract, the cross-language fixture replay, and a property test against a brute-force oracle.

License

MIT (c) ZhgChgLi

Documentation

Overview

Package rangeable is the Go reference implementation of the Rangeable RFC — a generic, integer-coordinate, closed-interval set container with first-insert ordered active queries.

See https://github.com/ZhgChgLi/RangeableRFC for the normative specification.

Index

• Variables
• type Interval
  • func NewInterval(lo, hi int) (Interval, error)
  • func (iv Interval) Contains(coord int) bool
• type InvalidIntervalError
  • func (e *InvalidIntervalError) Error() string
  • func (e *InvalidIntervalError) Is(target error) bool
• type Option
  • func WithIntMaxSentinel(v int) Option
• type Rangeable
  • func New[E comparable](opts ...Option) *Rangeable[E]
  • func (r *Rangeable[E]) At(i int) Slot[E]
  • func (r *Rangeable[E]) Copy() *Rangeable[E]
  • func (r *Rangeable[E]) Each(fn func(element E, intervals []Interval))
  • func (r *Rangeable[E]) GetRange(element E) []Interval
  • func (r *Rangeable[E]) Insert(element E, start, end int) error
  • func (r *Rangeable[E]) IsEmpty() bool
  • func (r *Rangeable[E]) Size() int
  • func (r *Rangeable[E]) Transitions(from int, to *int) ([]TransitionEvent[E], error)
  • func (r *Rangeable[E]) Version() int
• type Slot
  • func (s Slot[E]) IsEmpty() bool
  • func (s Slot[E]) Size() int
• type TransitionEvent
• type TransitionKind
  • func (k TransitionKind) String() string

Variables

var ErrInvalidInterval = errors.New("rangeable: invalid interval")

ErrInvalidInterval is the sentinel error returned when an interval is malformed (start > end). Use errors.Is to check.

Types

type Interval

type Interval struct {
	Lo int
	Hi int
}

Interval is an immutable closed integer interval [Lo, Hi].

Both ends are inclusive, matching RFC §4.1. Construct directly via a struct literal or via NewInterval for explicit validation.

func NewInterval

func NewInterval(lo, hi int) (Interval, error)

NewInterval validates the bounds and returns an Interval or an InvalidIntervalError on Lo > Hi.

func (Interval) Contains

func (iv Interval) Contains(coord int) bool

Contains reports whether coord is within [Lo, Hi] inclusive.

type InvalidIntervalError

type InvalidIntervalError struct {
	Start int
	End   int
}

InvalidIntervalError is returned by Rangeable.Insert and Rangeable.Transitions when the supplied bounds violate start <= end. It wraps ErrInvalidInterval so errors.Is succeeds.

func (*InvalidIntervalError) Error

func (e *InvalidIntervalError) Error() string

func (*InvalidIntervalError) Is

func (e *InvalidIntervalError) Is(target error) bool

Is allows errors.Is(err, ErrInvalidInterval) to succeed for any InvalidIntervalError instance.

type Option

type Option func(*config)

Option configures a Rangeable instance at construction time.

func WithIntMaxSentinel

func WithIntMaxSentinel(v int) Option

WithIntMaxSentinel opts the container into "treat hi == v as +∞" semantics for cross-language fixture parity with bounded-int languages. Default is unset.

type Rangeable

type Rangeable[E comparable] struct {
	// contains filtered or unexported fields
}

Rangeable is a generic, integer-coordinate, closed-interval set container. It pairs hashable elements with their merged disjoint integer ranges and supports three query families:

• by-element via Rangeable.GetRange
• by-position via Rangeable.At
• by-range via Rangeable.Transitions

The element type must be Go-[comparable] (RFC §4.2 — equality decided by `==`, which is reflexive, symmetric, transitive, and consistent with the runtime hash used by maps).

func New

func New[E comparable](opts ...Option) *Rangeable[E]

New constructs an empty Rangeable with the given options.

func (*Rangeable[E]) At

func (r *Rangeable[E]) At(i int) Slot[E]

At returns the active-element list at coordinate i. RFC §3.3.

O(log |segments| + r) once the index is built. Returns an empty Slot for coordinates outside every segment.

func (*Rangeable[E]) Copy

func (r *Rangeable[E]) Copy() *Rangeable[E]

Copy returns a deep copy. Mutation on the copy MUST NOT affect this instance, and vice versa.

func (*Rangeable[E]) Each

func (r *Rangeable[E]) Each(fn func(element E, intervals []Interval))

Each iterates (element, intervals) pairs in first-insert order ascending. The intervals slice is a fresh copy; mutating it does not affect the container.

func (*Rangeable[E]) GetRange

func (r *Rangeable[E]) GetRange(element E) []Interval

GetRange returns the merged ranges for element as a freshly allocated slice. RFC §3.4. Returns an empty slice when no element equal to element has ever been inserted.

func (*Rangeable[E]) Insert

func (r *Rangeable[E]) Insert(element E, start, end int) error

Insert covers the closed interval [start, end] with element. Returns an InvalidIntervalError (matchable via errors.Is against ErrInvalidInterval) if start > end. RFC §3.2.

Idempotent: re-inserting a sub-range that is already fully contained leaves the container unchanged and does NOT bump Rangeable.Version.

func (*Rangeable[E]) IsEmpty

func (r *Rangeable[E]) IsEmpty() bool

IsEmpty reports whether Rangeable.Size is zero.

func (*Rangeable[E]) Size

func (r *Rangeable[E]) Size() int

Size returns the number of distinct equivalence-class elements ever inserted. RFC §3.5.1.

func (*Rangeable[E]) Transitions

func (r *Rangeable[E]) Transitions(from int, to *int) ([]TransitionEvent[E], error)

Transitions returns open / close events within the inclusive coordinate range [from, to]. RFC §3.5.

to == nil means +∞ (include all events through the upper bound). Returns an InvalidIntervalError if from > *to.

func (*Rangeable[E]) Version

func (r *Rangeable[E]) Version() int

Version returns the monotonic counter that increments on every mutating insert. Idempotent inserts MUST NOT bump it (RFC §3.2, Test #21).

type Slot

type Slot[E any] struct {
	Objs []E
}

Slot wraps the ordered slice of elements active at a coordinate.

Objs is sorted by first-insertion order ascending (RFC §4.5). The same coordinate within an unmutated container always returns equivalent Objs.

func (Slot[E]) IsEmpty

func (s Slot[E]) IsEmpty() bool

IsEmpty reports whether no elements are active at the underlying coordinate.

func (Slot[E]) Size

func (s Slot[E]) Size() int

Size returns the number of active elements.

type TransitionEvent

type TransitionEvent[E any] struct {
	Coordinate *int
	Kind       TransitionKind
	Element    E
}

TransitionEvent is a single boundary event in coordinate-sorted order.

Coordinate is normally a finite [int]; it is nil for close events whose underlying interval ends at the implementation's +∞ sentinel (RFC §4.7 C4). Comparison treats nil as greater than any finite int.

type TransitionKind

type TransitionKind int

TransitionKind is the kind of a boundary event.

const (
	// Open marks the start of an element's active range.
	Open TransitionKind = iota
	// Close marks the position just past the end of an element's active range.
	Close
)

func (TransitionKind) String

func (k TransitionKind) String() string

String returns the canonical lowercase JSON-style tag.