blob: f8e944e2e6a0c934fa34fabc83766b15a6e950b4 [file] [log] [blame]
# Copyright 2019 The Fuchsia Authors. All rights reserved.
# Use of this source code is governed by a BSD-style license that can be
# found in the LICENSE file.
from functools import reduce
from typing import List, Iterable
class RangeSet:
"""Collection of discrete integer ranges.
This implementation is append-only. It uses Python's built-in `range`, so
all the ranges are [closed, open).
ranges: List[range]
def __init__(self, ranges: Iterable[range] = None):
"""Constructs an empty RangeSet.
ranges: For internal use only.
self.ranges = list(ranges) if ranges else []
def __len__(self):
return reduce(lambda x, y: x + y, map(len, self.ranges))
def __eq__(self, other):
return self.ranges == other.ranges
def append(self, code_point: int) -> None:
"""Appends an integer to the end of the set."""
if self.ranges:
last_range = self.ranges[-1]
if code_point <= last_range[-1]:
raise IndexError('Can\'t append to the middle of the range set')
if last_range[-1] + 1 == code_point:
self.ranges[-1] = range(last_range[0], code_point + 1)
self.ranges.append(range(code_point, code_point + 1))
def to_offset_string(self) -> str:
"""Generate a compact string representation of the RangeSet.
If the set of ranges is
[range(1,4), range(8,10), range(13, 14), range(18, 21)]
the output will be
In each entry, the first number is the offset from the end of the
previous range. If the current range has length > 1, then there's a
'+x' that shows how much to add to get the upper bound of the range.
Note that the range [13, 14) has length 1, so it doesn't get a plus
prev_start = 0
segments = []
for r in self.ranges:
relative_start = r[0] - prev_start
range_size = len(r)
if range_size == 1:
segments.append('%d' % relative_start)
segments.append('%d+%d' % (relative_start, range_size - 1))
prev_start = r[-1]
return ','.join(segments)
def from_offset_string(cls, offsets: str) -> 'RangeSet':
"""Construct a RangeSet from an offset string.
See `to_offset_string` for a description of the format.
ranges = []
split_offsets = offsets.split(',')
last_end = 0
for s in split_offsets:
if '+' in s:
endpoints = s.split('+')
start = last_end + int(endpoints[0])
end = start + int(endpoints[1])
ranges.append(range(start, end + 1))
last_end = end
start = last_end + int(s)
ranges.append(range(start, start + 1))
last_end = start
return RangeSet(ranges=ranges)