A compact and time efficient value store for sparse regions of ordered values

[phausler]

It would be quite useful to have a type that can efficiently store values with corrilative range regions. This type ideally would conform to RangeReplaceableCollection (or near miss). It should store values such that the indicies are sparse and there is a way to test if it contains and index. (Example posted with a name just for illustration).

struct RegionList<Element, Index> {
	struct Region: RandomAccessCollection {
		// a contiguous region of elements from startIndex to endIndex 
		// Element = SpareArray.Element
		// Index = RegionList.Index
	}

	struct RegionView: RandomAccessCollection {
		typealias Element = Region
		typealias Index = Int
	}

	var regions: RegionView { get }
}

extension RegionList: RangeReplaceableCollection { }

Example usage:

var items = RegionList<String, Int>()

items[0] = "hello"
// Array(items) = ["hello"]
// Array(items.indicies) = [0]
// items.regions.map { Array($0) } = [["hello"]]

items[1] = "world"
// Array(items) = ["hello", "world"]
// Array(items.indicies) = [0, 1]
// items.regions.map { Array($0) } = [["hello", "world"]]

items[5] = "foo"
// Array(items) = ["hello", "world", "foo"]
// Array(items.indicies) = [0, 1, 5]
// items.regions.map { Array($0) } = [["hello", "world"], ["foo"]]

items[6] = "bar"
// Array(items) = ["hello", "world", "foo", "bar"]
// Array(items.indicies) = [0, 1, 5, 6]
// items.regions.map { Array($0) } = [["hello", "world"], ["foo", "bar"]]

items[7] = "Baz"
// Array(items) = ["hello", "world", "foo", "bar", "Baz"]
// Array(items.indicies) = [0, 1, 5, 6, 7]
// items.regions.map { Array($0) } = [["hello", "world"], ["foo", "bar", "Baz"]]

items[7] = "baz"
// Array(items) = ["hello", "world", "foo", "bar", "baz"]
// Array(items.indicies) = [0, 1, 5, 6, 7]
// items.regions.map { Array($0) } = [["hello", "world"], ["foo", "bar", "baz"]]


items[2...4] = ["test1", "test2", "test3"]
// Array(items) = ["hello", "world", "test1", "test2", "test3, "foo", "bar", "baz"]
// Array(items.indicies) = [0, 1, 2, 3, 4, 5, 6, 7]
// items.regions.map { Array($0) } = [["hello", "world", "test1", "test2", "test3, "foo", "bar", "baz"]]

items.remove(at: 3)
// Array(items) = ["hello", "world", "test1", "test2", "foo", "bar", "baz"]
// Array(items.indicies) = [0, 1, 2, 4, 5, 6, 7]
// items.regions.map { Array($0) } = [["hello", "world", "test1", "test2"], ["foo", "bar", "baz"]]

As the count of items increases the storage should increase as a constant scale factor accordingly O(space N) = k*N + c.
As the count of items increases the access time per index should remain constant O(access N) = c.
As the delta between the start index and end index increases the storage should only crease as a the count of items increases. e.g. the memory usage from a region list with a start index of 0 and end index of 100 with 2 elements in it should be the same as one with a start index of 0 and an end index of 100000 with 2 elements in it.
Testing if an index is not contained within the indicies should be at most amortized constant time.