Skip to main content

List of intersecting ranges

Project description

Basics

Range is a continuous interval between two points (boundaries). E.g. a numeric interval, a time interval, alphabetic interval, etc. Examples of range are:

  • (1; 3) – means that any number between 1 and 3 belongs to this interval, excluding 1 and 3.
  • [1; 3] – means that any number between 1 and 3 belongs to this interval, including 1 and 3.
  • (1; 3] – means that any number between 1 and 3 belongs to this interval, excluding 1 and including 3.

On the numeric or time scale multiple ranges can intersect or coexist. An arbitrary point on this scale can be included or excluded from the intersection of all ranges.

The rangelist package, as follows from it's name, represents lists of ranges, but not just a plain list, but a proper, valid intersection of ranges on the numeric or time scale, and what's more important - tells if a point or a range belongs to the given list of ranges.

A range is usually represented by (x; y) or [x; y] record, meaning literally 'Interval from x to y'.

Boundary points may or may not belong to the interval itself; to signify that, round or square brackets are used.

A range can be a single point, e.g. [1; 1] - this means that only 1 is in it's range.

A continuous interval can have an excluded point. E.g. [1; 5] + (3;3) => [1; 3), (3; 5]

Usage

There are 3 basic types: Point, RangeItem and RangeList.

Point basically represents a point, which can be an arbitrary value; there are 2 special points to represent infinity and negative infinity:

>>> from rangelist.point import Point, INF, NEG_INF
>>> Point(1)
1
>>> Point(1) == Point(3)
False
>>> Point(1) == Point(1)
True
>>> Point(3) > Point(1)
True
>>> INF
inf
>>> NEG_INF
-inf
>>> INF > Point(999)
True

RangeItem represents a single range:

>>> from rangelist.rangeitem import RangeItem
>>> RangeItem(1, 3, left_excluded=False, right_excluded=True)
[1, 3)
>>> 1 in RangeItem(1, 3, left_excluded=False, right_excluded=True)
True
>>> 2 in RangeItem(1, 3, left_excluded=False, right_excluded=True)
True
>>> 3 in RangeItem(1, 3, left_excluded=False, right_excluded=True)
False

Range items support basic math operations such as inclusion, equality and intersection checks. It's also possible to test a point for inclusion into given range:

>>> RangeItem(1, 3) in RangeItem(0, 4)
True
>>> RangeItem(1, 3) == RangeItem(1, 3)
True
>>> RangeItem(1, 3) > RangeItem(-1, 0)
True
>>> RangeItem(1, 3).intersects_with(RangeItem(-1, 0))
False
>>> RangeItem(1, 3).intersects_with(RangeItem(-1, 2))
True
>>> 2 in RangeItem(1, 3)
True

RangeList represents intersection of multiple RangeItemobjects, honouring their boundaries:

  1. Add 2 ranges with included boundaries, and then add a range that overlaps both ranges, hence it will create a single, continuous range:

    >>> r = RangeList()
    >>> r.insert(RangeItem(0, 2))
    >>> r
    ['[0, 2]']
    >>> r.insert(RangeItem(10, 20))
    >>> r
    ['[0, 2]', '[10, 20]']
    >>> r.insert(RangeItem(1, 11))
    >>> r
    ['[0, 20]']
    
  2. Add 2 ranges, one range has excluded boundary. Then add a range that overlaps both. In this case excluded boundary point must stay excluded (ranges will break):

    >>> r = RangeList()
    >>> r.insert(RangeItem(0, 4))
    >>> r
    ['[0, 4]']
    >>> r.insert(RangeItem(5, 10, left_excluded=True))
    >>> r
    ['[0, 4]', '(5, 10]']
    >>> r.insert(RangeItem(2, 8))  # note that this range overlaps existing, but point 5 is excluded
    >>> r
    ['[0, 5)', '(5, 10]']
    
  3. Just a bit more complex example, when we overlap 2 ranges with excluded boundaries:

    >>> r = RangeList()
    >>> r.insert(RangeItem(1, 4, left_excluded=True, right_excluded=True))
    >>> r
    ['(1, 4)']
    >>> r.insert(RangeItem(3, 6, left_excluded=True, right_excluded=True))
    >>> r
    ['(1, 3)', '(3, 4)', '(4, 6)']
    >>> 2 in r
    True
    >>> 3 in r
    False
    >>> 4 in r
    False
    >>> 5 in r
    >>> RangeItem(4.5, 5.5) in r
    True
    >>> RangeItem(4, 6) in r
    False
    >>> RangeItem(4, 6, left_excluded=True, right_excluded=True) in r
    True
    

Real world application

Consider 2 examples:

  1. Range intersection on the numeric scale. Suppose we want to program system of equations:

    • x < -5
    • x ≠2
    • x > - 1

    and then be able to test if an arbitrary point satisfies these equations.

    Let's create a range intersection with rangelist

    >>> from rangelist.rangelist import RangeList
    >>> from rangelist.rangeitem import RangeItem
    >>> from rangelist.point import INF, NEG_INF
    >>> 
    >>> range_items = [
    ...     RangeItem(NEG_INF, -5, right_excluded=True),
    ...     RangeItem(2, 2, left_excluded=True, right_excluded=True),
    ...     RangeItem(-1, INF, left_excluded=True),
    ... ]
    >>> 
    >>> range_list = RangeList(range_items)
    >>> range_list
    ['[-inf, -5)', '(-1, 2)', '(2, inf]']
    >>> -10 in range_list
    True
    >>> -5 in range_list  # should be False, since -5 is not included
    False
    >>> -3 in range_list  # should be False, it's outside of any interval
    False
    >>> 0 in range_list  # should be True
    True
    >>> 10 in range_list  # should be True
    True
    
  2. Timescale. Suppose we're building a system that sends notifications to customers, and each customer has their own rules when to send or not send them notifications. Suppose a customer wants notifications to be sent from 8am sharp to 10am, and from 1pm to 8pm excluding lunch time 2:30pm - 3pm. Let's build a range list for this example, and then we can test an arbitrary time to see if it fits customer's expectations:

    >>> r = RangeList()
    >>> r.insert(RangeItem(dt.time(8, 0), dt.time(10, 0), right_excluded=True))
    >>> r.insert(RangeItem(dt.time(13, 0), dt.time(14, 30), right_excluded=True))
    >>> r.insert(RangeItem(dt.time(15, 0), dt.time(20, 0), right_excluded=True))
    >>> r
    ['[08:00:00, 10:00:00)', '[13:00:00, 14:30:00)', '[15:00:00, 20:00:00)']
    >>> dt.time(8, 0) in r
    True
    >>> dt.time(10, 0) in r
    False
    >>> dt.time(14, 0) in r
    True
    >>> dt.time(14, 30) in r
    False
    >>> dt.time(20, 30) in r
    False
    

Installation

Best way to install is using pip: pip install rangelist

Project details


Download files

Download the file for your platform. If you're not sure which to choose, learn more about installing packages.

Files for rangelist, version 0.0.4
Filename, size File type Python version Upload date Hashes
Filename, size rangelist-0.0.4-py2-none-any.whl (8.2 kB) File type Wheel Python version py2 Upload date Hashes View hashes
Filename, size rangelist-0.0.4.tar.gz (7.4 kB) File type Source Python version None Upload date Hashes View hashes

Supported by

Elastic Elastic Search Pingdom Pingdom Monitoring Google Google BigQuery Sentry Sentry Error logging AWS AWS Cloud computing DataDog DataDog Monitoring Fastly Fastly CDN DigiCert DigiCert EV certificate StatusPage StatusPage Status page