2 files changed, 129 insertions, 0 deletions
diff --git a/pkg/libs/rangemap/rangemap.go b/pkg/libs/rangemap/rangemap.go
new file mode 100644
index 0000000..df891a6
--- /dev/null
+++ b/pkg/libs/rangemap/rangemap.go
@@ -0,0 +1,58 @@
+package rangemap
+
+type RangeMap[D any] struct {
+	ranges []rangeEntry
+	data   []D
+}
+
+func New[D any]() RangeMap[D] {
+	return RangeMap[D]{
+		ranges: []rangeEntry{},
+	}
+}
+
+func (rm *RangeMap[D]) AppendToLast(to int, data D) bool {
+	if to < 0 {
+		return false
+	}
+
+	from := 0
+	if len(rm.ranges) != 0 {
+		last := rm.ranges[len(rm.ranges)-1]
+		if last.to >= to {
+			return false
+		}
+		from = last.to + 1
+	}
+
+	rm.ranges = append(rm.ranges, rangeEntry{
+		from: from,
+		to:   to,
+	})
+
+	rm.data = append(rm.data, data)
+	return true
+}
+
+func (rm *RangeMap[D]) Get(i int) (*D, bool) {
+	left := 0
+	right := len(rm.ranges) - 1
+	for left <= right {
+		mid := (left + right) / 2
+		entry := rm.ranges[mid]
+		if i < entry.from {
+			right = mid - 1
+		} else if i > entry.to {
+			left = mid + 1
+		} else {
+			return &rm.data[mid], true
+		}
+	}
+
+	return nil, false
+}
+
+type rangeEntry struct {
+	from int
+	to   int
+}
diff --git a/pkg/libs/rangemap/rangemap_test.go b/pkg/libs/rangemap/rangemap_test.go
new file mode 100644
index 0000000..b120efa
--- /dev/null
+++ b/pkg/libs/rangemap/rangemap_test.go
@@ -0,0 +1,71 @@
+package rangemap_test
+
+import (
+	"jinx/pkg/libs/rangemap"
+	"testing"
+
+	"github.com/stretchr/testify/assert"
+)
+
+func TestAppend(t *testing.T) {
+	rm := rangemap.New[string]()
+
+	assert.True(t, rm.AppendToLast(0, "a"))
+	assert.True(t, rm.AppendToLast(1, "b"))
+	assert.True(t, rm.AppendToLast(4, "c"))
+}
+
+func TestAppendAndGet(t *testing.T) {
+	rm := rangemap.New[string]()
+
+	assert.True(t, rm.AppendToLast(0, "a"))
+	assert.True(t, rm.AppendToLast(1, "b"))
+	assert.True(t, rm.AppendToLast(4, "c"))
+
+	a, ok := rm.Get(0)
+	assert.True(t, ok)
+	assert.Equal(t, "a", *a)
+
+	b, ok := rm.Get(1)
+	assert.True(t, ok)
+	assert.Equal(t, "b", *b)
+
+	cfrom, ok := rm.Get(2)
+	assert.True(t, ok)
+	assert.Equal(t, "c", *cfrom)
+
+	cmid, ok := rm.Get(3)
+	assert.True(t, ok)
+	assert.Equal(t, "c", *cmid)
+
+	cto, ok := rm.Get(4)
+	assert.True(t, ok)
+	assert.Equal(t, "c", *cto)
+}
+
+func TestWrongAppend(t *testing.T) {
+	rm := rangemap.New[string]()
+
+	assert.True(t, rm.AppendToLast(0, "a"))
+	assert.False(t, rm.AppendToLast(0, "b"))
+}
+
+func TestUnknownRange(t *testing.T) {
+	rm := rangemap.New[string]()
+
+	assert.True(t, rm.AppendToLast(6, "a"))
+
+	a, ok := rm.Get(6)
+	assert.True(t, ok)
+	assert.Equal(t, "a", *a)
+
+	b, ok := rm.Get(7)
+	assert.False(t, ok)
+	assert.Nil(t, b)
+}
+
+func TestNegativeAppend(t *testing.T) {
+	rm := rangemap.New[string]()
+
+	assert.False(t, rm.AppendToLast(-1, "a"))
+}