RangeSet data structure

1

I’m interested in how the RangeSet data structure works. Is my understanding correct that overlapping ranges are never stored within the same list of chunks? Instead when a new range is inserted that would overlap an existing ranges it gets pushed to the “nextLayer” until no ranges overlap in that next layer?

If that’s how it works is this something unique that you came up with for CodeMirror, or is it a more general approach that other text editors use? I hadn’t seen it before. Anyway seems to nicely solve the problems of querying overlapping ranges efficiently as long as you don’t expect too many overlaps.

Thanks!

2

Yes, that’s correct (though ‘layer’ would be more appropriate than ‘chunk’ here). I’m doing something similar in ProseMirror, but I don’t know of similar data structures. Basically, this is optimized to allow both fast in-order iteration and lookup (ranges are ordered within layers), and cheap position mapping (chunks can be reused if they don’t move or move in a uniform way).

1 Like