Source code for piwheels.ranges

# The piwheels project
#   Copyright (c) 2017 Ben Nuttall <https://github.com/bennuttall>
#   Copyright (c) 2017 Dave Jones <dave@waveform.org.uk>
#
# Redistribution and use in source and binary forms, with or without
# modification, are permitted provided that the following conditions are met:
#
#     * Redistributions of source code must retain the above copyright
#       notice, this list of conditions and the following disclaimer.
#     * Redistributions in binary form must reproduce the above copyright
#       notice, this list of conditions and the following disclaimer in the
#       documentation and/or other materials provided with the distribution.
#     * Neither the name of the copyright holder nor the
#       names of its contributors may be used to endorse or promote products
#       derived from this software without specific prior written permission.
#
# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
# AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
# IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
# ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
# LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
# CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
# SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
# INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
# CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
# ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
# POSSIBILITY OF SUCH DAMAGE.

"""
A set of utility routines for efficiently tracking byte ranges within a stream.
These are used to track which chunks of a file have been received during file
transfers from build slaves.

See :class:`~.file_juggler.FileJuggler` for the usage of these functions.


.. autofunction:: consolidate

.. autofunction:: exclude

.. autofunction:: intersect

.. autofunction:: split
"""


[docs]def consolidate(ranges): """ Given a list of *ranges* in ascending order, this generator function returns the list with any overlapping ranges consolidated into individual ranges. For example:: >>> list(consolidate([range(0, 5), range(4, 10)])) [range(0, 10)] >>> list(consolidate([range(0, 5), range(5, 10)])) [range(0, 10)] >>> list(consolidate([range(0, 5), range(6, 10)])) [range(0, 5), range(6, 10)] """ start = stop = None for r in ranges: if start is None: start = r.start elif r.start > stop: yield range(start, stop) start = r.start stop = r.stop yield range(start, stop)
[docs]def split(ranges, i): """ Given a list of non-overlapping *ranges* in ascending order, this generator function returns the list with the range containing *i* split into two ranges, one ending at *i* and the other starting at *i*. If *i* is not contained in any of the ranges, then *ranges* is returned unchanged. For example:: >>> list(split([range(10)], 5)) [range(0, 5), range(5, 10)] >>> list(split([range(10)], 0)) [range(0, 10)] >>> list(split([range(10)], 20)) [range(0, 10)] """ for r in ranges: if i in r and i > r.start: yield range(r.start, i) yield range(i, r.stop) else: yield r
[docs]def exclude(ranges, ex): """ Given a list of non-overlapping *ranges* in ascending order, and a range *ex* to exclude, this generator function returns *ranges* with all values covered by *ex* removed from any contained ranges. For example:: >>> list(exclude([range(10)], range(2))) [range(2, 10)] >>> list(exclude([range(10)], range(2, 4))) [range(0, 2), range(4, 10)] """ for r in split(split(ranges, ex.start), ex.stop): if r.stop <= ex.start or r.start >= ex.stop: yield r
[docs]def intersect(range1, range2): """ Given two ranges *range1* and *range2* (which must both have a step of 1), returns the range formed by the intersection of the two ranges, or ``None`` if the ranges do not overlap. For example:: >>> intersect(range(10), range(5)) range(0, 5) >>> intersect(range(10), range(10, 2)) >>> intersect(range(10), range(2, 5)) range(2, 5) """ assert range1.step == 1 assert range2.step == 1 r = range(max(range1.start, range2.start), min(range1.stop, range2.stop)) if r: return r