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
}