| # 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. |
| Args: |
| 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) |
| return |
| 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 |
| |
| "1+2,5+1,4,4+3" |
| |
| 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 |
| suffix. |
| """ |
| 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) |
| else: |
| segments.append('%d+%d' % (relative_start, range_size - 1)) |
| prev_start = r[-1] |
| return ','.join(segments) |
| |
| @classmethod |
| 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 |
| else: |
| start = last_end + int(s) |
| ranges.append(range(start, start + 1)) |
| last_end = start |
| return RangeSet(ranges=ranges) |