3
\$\begingroup\$

I was surprised to find that there doesn't seem to be a good "continuous range from start to end" data structure in python. I feel such a structure might be useful. So I made one.

Moreover, from my time answering questions on StackOverflow, a use case that I've seen come up repeatedly is to have a program have differing behavior based on which range of values a given variable falls into. You can normally use dicts to elegantly select different behavior based on the precise value of a range, but if you want to accommodate a whole range of values you basically have to use if statements. So one goal I have for this code is to include it in a RangeDict class that would act kind of like a dict except for each key would be a Range or set of Ranges associated with a particular value.

I tried to make the class's interface as similar to an existing data structure (set - a range is, mathematically, similar to a continuous bounded set) as possible. I also wanted the class to be flexible and able to be defined in any reasonale way, hence the large number of branches in the constructor. I also made it so that the class's __str__() method returns a value that can be used directly to construct a new Range.

Most of the error-handling is implicit, to allow as broad a use of the class as possible (so long as start and end can be compared with each other, this class does not care what types they actually are - most non-numeric types will raise errors when compared with each other, which naturally filters out problematic inputs).

The constructor is one of the main things here I hope to get feedback on, as well as "is the documentation acceptable?" and "is this a sensible way to create a data structure like this?".


Note that I also have another class I'm not showing yet, called RangeSet. It's just a set-like data structure that contains a set of disjoint ranges all at once. I figured that it should be compatible with a single continuous Range, so I added functionality for that. For now, I'm only interested in reviewing my Range class with respect to other Range objects - RangeSet can have its own review later.

class Range:
    """
    A class representing a range from a start value to an end value.
    The start and end need not be numeric, but they must be comparable.
    A Range is immutable, but not strictly so - nevertheless, it should
    not be modified directly.

    A new Range can be constructed in several ways:

        1. From an existing `Range` object

            >>> a = Range()   # range from -infinity to +infinity
            >>> b = Range(a)  # copy of a

        2. From an iterable representing a range. The first two elements of
          the iterable will be taken as start and end respectively.
          `start` and `end` may be anything so long as the condition
          `start <= end` is True and does not error.

            >>> c = Range([3, 5])
            >>> d = Range([3, 5], include_start=False, include_end=True)

        3. From a string, in the format "[start, end)".
          Both '()' (exclusive) and '[]' (inclusive) are valid brackets,
          and `start` and `end` must be able to be parsed as floats.
          Also, the condition `start <= end` must be True. Brackets
          must be present (a ValueError will be raised if they aren't).
          If constructing a Range from a string, then include_start and
          include_end will be ignored.

            >>> e = Range("(-3, 5.5)")  # Infers include_start and include_end to both be false
            >>> f = Range("[-3, 5.5)")  # Infers include_start to be true, include_end to be false

        4. From two positional arguments representing `start` and `end`.
          `start` and `end` may be anything so long as the condition
          `start <= end` is True and does not error. Both `start` and
          `end` must be given together as positional arguments; if only
          one is given, then the program will try to consider it as an
          iterable.

            >>> g = Range(3, 5)
            >>> h = Range(3, 5, include_start=False, include_end=True)

        5. From the keyword arguments `start` and/or `end`. `start` and `end`
          may be anything so long as the condition `start <= end` is True and
          does not error. If not provided, `start` is set to -infinity by
          default, and `end` is set to +infinity by default. If any of the
          other methods are used to provide start
          and end values for the range, then these keyword arguments will be
          ignored.

            >>> i = Range(start=3, end=5)  # range from 3 to 5
            >>> j = Range(start=3)  # range from 3 to infinity
            >>> k = Range(end=5)  # range from -infinity to 5
            >>> l = Range(start=3, end=5, include_start=False, include_end=True)

        Non-numeric values may be used as arguments, such as dates:

            >>> import datetime
            >>> m = Range(datetime.date(2016,9,5), datetime.date(2017,3,1))
            >>> print(datetime.date(2016,12,31) in m)  # True
            >>> print(datetime.date(2017,3,15) in m)  # False

        and strings (using lexicographic comparisons):

            >>> n = Range("leaner", "neither")
            >>> print("kazoo" in n)  # False
            >>> print("mouse" in n)  # True
            >>> print("leader" in n)  # False

        or any other comparable type.
    """
    def __init__(self, *args, **kwargs):
        """
        Constructs a new Range from start to end, or from an existing range.
        Is inclusive by default (meaning that both bounds are included) but
        can be made exclusive by setting include_start and include_end to False.
        """
        # process kwargs
        start = kwargs.get('start', float('-inf'))
        end = kwargs.get('end', float('inf'))
        include_start = kwargs.get('include_start', True)
        include_end = kwargs.get('include_end', True)
        self.include_start = include_start
        self.include_end = include_end
        # Check how many positional args we got, and initialize accordingly
        if len(args) == 0:
            # with 0 positional args, initialize from kwargs directly
            rng = None
        elif len(args) == 1:
            # with 1 positional arg, initialize from existing range-like object
            if not args[0] and not isinstance(args[0], Range):
                raise ValueError("Cannot take a falsey non-Range value as only positional argument")
            rng = args[0]
        else:  # len(args) >= 2:
            # with 2 positional args, initialize from given start and end values
            start = args[0]
            end = args[1]
            rng = None
        # initialize differently if given a Range vs if given a Start/End.
        if rng:
            # case 1: construct from Range
            if isinstance(rng, Range):
                self.start = rng.start
                self.end = rng.end
            # case 3: construct from String
            elif isinstance(rng, str):
                pattern = r"(\[|\()\s*([^\s,]+)[,\s]*([^\s,]+)\s*(\]|\))"
                match = re.match(pattern, rng)
                try:
                    # check for validity of open-bracket
                    if match.group(1) == "[": 
                        self.include_start = True
                    elif match.group(1) == "(": 
                        self.include_start = False
                    else: 
                        raise AttributeError()
                    # check for validity of close-bracket
                    if match.group(4) == "]": 
                        self.include_end = True
                    elif match.group(4) == ")": 
                        self.include_end = False
                    else: 
                        raise AttributeError()
                    # check start and end values
                    self.start = float(match.group(2))
                    self.end = float(match.group(3))
                except (AttributeError, IndexError):
                    raise ValueError("Range was given in wrong format. Must be like '(start, end)' "
                                     "where () means exclusive, [] means inclusive")
                except ValueError:
                    raise ValueError("start and end must be numbers")
            # case 2: construct from iterable representing start/end
            else:
                try:
                    self.start = rng[0]
                    self.end = rng[1]
                except TypeError:
                    raise ValueError("Given range must be a Range, string, or iterable")
                except IndexError:
                    raise ValueError("Range iterable must contain at least two values")
        else:
            # case 4 or 5: construct from positional args or kwargs
            self.start = start
            self.end = end
        if start > end:
            raise ValueError("start must be less than or equal to end")
        # no further initialization should be necessary

    def isdisjoint(self, rng):
        """
        returns False if this range overlaps with the given range, and True otherwise.
        """
        # if RangeSet, return that instead
        if isinstance(rng, RangeSet):
            return rng.isdisjoint(self)
        # convert other range to a format we can work with
        try:
            if not isinstance(rng, Range):
                rng = Range(rng)
        except ValueError:
            raise TypeError(str(rng) + " is not a range")
        # detect overlap
        rng_a, rng_b = (self, rng) if self < rng else (rng, self)
        return not(rng_a == rng_b or rng_a.end in rng_b or rng_b.start in rng_a)

    def union(self, rng):
        """
        If this range and the given range overlap, then returns a range that encompasses
        both of them. Returns None if the ranges don't overlap.
        """
        # if RangeSet, return union of that instead
        if isinstance(rng, RangeSet):
            return rng.union(self)
        # convert other range to a format we can really work with
        try:
            if not isinstance(rng, Range):
                rng = Range(rng)
        except ValueError:
            raise TypeError("Cannot merge a Range with a non-Range")
        # do the ranges overlap?
        rng_a, rng_b = (self, rng) if self < rng else (rng, self)
        if rng_a.isdisjoint(rng_b):
            return None
        # merge 'em
        new_start = min((rng_a.start, rng_a.include_start), (rng_b.start, rng_b.include_start))
        new_end = max((rng_a.end, rng_a.include_end), (rng_b.end, rng_b.include_end))
        return Range(start=new_start[0], end=new_end[0], include_start=new_start[1], include_end=new_end[1])

    def intersection(self, rng):
        """
        Returns a range representing the intersection between this range and the given range,
        or None if the ranges don't overlap at all.
        """
        # if a RangeSet, then return the intersection of that with this instead.
        if isinstance(rng, RangeSet):
            return rng.intersection(self)
        # convert other range to a format we can work with
        try:
            if not isinstance(rng, Range):
                rng = Range(rng)
        except ValueError:
            raise TypeError("Cannot overlap a Range with a non-Range")
        # do the ranges overlap?
        rng_a, rng_b = (self, rng) if self < rng else (rng, self)
        if rng_a.isdisjoint(rng_a):
            return None
        # compute parameters for new intersecting range
        new_start = max((rng_a.start, rng_a.include_start), (rng_b.start, rng_b.include_start))
        new_end = max((rng_a.end, rng_a.include_end), (rng_b.end, rng_b.include_end))
        # create and return new range
        return Range(start=new_start[0], end=new_end[0], include_start=new_start[1], include_end=new_end[1])

    def difference(self, rng):
        """
        Returns a range containing all elements of this range that are not within the
        other range, or None if this range is entirely consumed by the other range.
        If the other range is entirely consumed by this range, then returns a 2-tuple
        of (lower_range, higher_range).
        """
        # if a RangeSet, then return the intersection of one of those with this instead.
        if isinstance(rng, RangeSet):
            return RangeSet((self,)).difference(rng)
        # convert other range to a workable format
        try:
            if not isinstance(rng, Range):
                rng = Range(rng)
        except ValueError:
            raise TypeError("Cannot diff a Range with a non-Range")
        # completely disjoint
        if self.isdisjoint(rng):
            return self
        # fully contained
        elif self in rng or self == rng:
            return None
        # fully contained (in the other direction)
        elif rng in self:
            return (
                Range(start=self.start, end=rng.end, include_start=self.include_start, include_end=not rng.include_end),
                Range(start=rng.start, end=self.end, include_start=not rng.include_start, include_end=self.include_end)
            )
        # lower portion of this range
        elif self < rng:
            return Range(start=self.start, end=rng.start, 
                         include_start=self.include_start, include_end=not rng.include_end)
        # higher portion of this range
        elif self > rng:
            return Range(start=rng.end, end=self.end, include_start=not rng.include_start, include_end=self.include_end)

    def symmetric_difference(self, rng):
        """
        Returns a 1- or 2-tuple of ranges comprising the parts of self and rng that
        do not overlap. Resulting tuples will be sorted from lowest to highest range.
        Returns None if the ranges overlap exactly (thus are equal).
        """
        # if a RangeSet, then return the symmetric difference of one of those with this instead.
        if isinstance(rng, RangeSet):
            return rng.symmetric_difference(self)
        # convert to range so we can work with it
        try:
            if not isinstance(rng, Range):
                rng = Range(rng)
        except ValueError:
            raise TypeError("Cannot diff a Range with a non-Range")
        # if ranges are equal
        if self == rng:
            return None
        # otherwise, get differences
        diff_a = self.difference(rng)
        diff_b = rng.difference(self)
        # create dummy symmetric difference object
        if isinstance(diff_a, tuple):
            # diffA has 2 elements, therefore diffB has 0 elements, e.g. (1,4) (2,3) -> (1,2] [3,4)
            return diff_a
        elif isinstance(diff_b, tuple):
            # diffB has 2 elements, therefore diffA has 0 elements, e.g. (2,3) (1,4) -> (1,2] [3,4)
            return diff_b
        elif diff_a is not None and diff_b is not None:
            # diffA has 1 element, diffB has 1 element, e.g. (1,3) (2,4) -> (1,2] [3,4)
            return tuple(sorted((diff_a, diff_b)))
        elif diff_a is not None:
            # diffA has 1 element, diffB has 0 elements, e.g. (1,4) (1,2) -> [2,4)
            return diff_a,
        else:
            # diffA has 0 elements, diffB has 1 element, e.g. (3,4) (1,4) -> (1,3]
            return diff_b,

    def isempty(self):
        """
        Returns True if this range is empty (it contains no values), and False otherwise.
        In essence, will only return True if start == end and both ends are exclusive.
        """
        return self.start == self.end and not self.include_start and not self.include_end

    def copy(self):
        """ Returns a copy of this object, similar to calling Range(self) """
        return Range(self)

    def _above_start(self, item):
        if self.include_start:
            return item >= self.start
        else:
            return item > self.start

    def _below_end(self, item):
        if self.include_end:
            return item <= self.end
        else:
            return item < self.end

    def __eq__(self, obj):
        """
        Compares the start and end of this range to the other range, along with inclusivity at
        either end. Returns True if everything is the same, False otherwise.
        """
        try:
            return (self.start, self.end, self.include_start, self.include_end) == \
                    (obj.start, obj.end, obj.include_start, obj.include_end)
        except AttributeError:
            return False

    def __lt__(self, obj):
        """
        Used for ordering, not for subranging/subsetting. Compares attributes in
        the following order, returning True/False accordingly:
        1. start
        2. include_start (inclusive < exclusive)
        3. end
        4. include_end (exclusive < inclusive)
        """
        try:
            if not isinstance(obj, Range):
                obj = Range(obj)
            return (self.start, not self.include_start, self.end, self.include_end) < \
                   (obj.start, not obj.include_start, obj.end, obj.include_end)
        except (AttributeError, ValueError, TypeError):
            raise TypeError(f"'<' not supported between instances of 'Range' and '{obj.__class__.__name__}'")

    def __gt__(self, obj):
        """
        Used for ordering, not for subranging/subsetting. Compares attributes in
        the following order, returning True/False accordingly:
        1. start
        2. include_start (inclusive < exclusive)
        3. end
        4. include_end (exclusive < inclusive)
        """
        try:
            if not isinstance(obj, Range):
                obj = Range(obj)
            return (self.start, not self.include_start, self.end, self.include_end) > \
                   (obj.start, not obj.include_start, obj.end, obj.include_end)
        except (AttributeError, ValueError, TypeError):
            raise TypeError(f"'<' not supported between instances of 'Range' and '{obj.__class__.__name__}'")

    def __ge__(self, obj):
        """
        Used for ordering, not for subranging/subsetting. See docstrings for
        __eq__() and __gt__().
        """
        return self > obj or self == obj

    def __le__(self, obj):
        """
        Used for ordering, not for subranging/subsetting. See docstrings for
        __eq__() and __lt__().
        """
        return self < obj or self == obj

    def __ne__(self, obj):
        """
        See docstring for __eq__(). Returns the opposite of that.
        """
        return not self == obj

    def __or__(self, other):
        """
        Equivalent to self.union(other)
        """
        return self.union(other)

    def __and__(self, other):
        return self.intersection(other)

    def __sub__(self, other):
        """
        Equivalent to self.difference(other)
        """
        return self.difference(other)

    def __xor__(self, other):
        """
        Equivalent to self.symmetric_difference(other)
        """
        return self.symmetric_difference(other)

    def __contains__(self, item):
        """
        Returns True if the given item is inside the bounds of this range, False if it isn't.
        If the given item isn't comparable to this object's start and end objects, then
        tries to convert the item to a Range, and returns True if it is completely
        contained within this range, False if it isn't.
        """
        if isinstance(item, RangeSet):
            return all(rng in self for rng in item.ranges())
        else:
            try:
                return self._above_start(item) and self._below_end(item)
            except TypeError:
                rng_item = Range(item)
                return rng_item.start in self and rng_item.end in self

    def __len__(self):
        """ Returns the size of this range (end - start), irrespective of whether either end is inclusive """
        return self.end - self.start

    def __hash__(self):
        return hash((self.start, self.end, self.include_start, self.include_end))

    def __str__(self):
        return f"{'[' if self.include_start else '('}{self.start}, {self.end}{']' if self.include_end else ')'}"

    def __repr__(self):
        return f"range{str(self)}"
```
\$\endgroup\$
1
\$\begingroup\$

Design Decision

You have designed the defaults to be both including the start and end.

 include_start = kwargs.get('include_start', True)
 include_end = kwargs.get('include_end', True)

However, for continuous ranges a better default is to exclude the end. Why? Because we cannot expect the values to be discretes (hence, 'continous' range). In continous functions, an included end would need to defined as the excluded end minus some sort of epsilon. This is very tedious and cumbersome practice.

Example in pseudo code: 01/01/2000 - 01/01/2001 is much cleaner than 01/01/2000 - 12/31/2000 23:59:59.999999.

Change your default for the end item to be excluded.

  include_start = kwargs.get('include_start', True)
  include_end = kwargs.get('include_end', False)
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.