graphtage.bounds

A module for representing bounded ranges.

Examples

>>> from graphtage import bounds
>>> p = bounds.Infinity(positive=True)
>>> str(p)
'∞'
>>> str(p + p)
'∞'
>>> bounds.Range(0, p)
Range(0, Infinity(positive=True))
>>> bounds.Range(0, 10) < bounds.Range(20, 30)
True

This module provides a variety of data structures and algorithms for both representing bounds as well as operating on bounded ranges (e.g., sorting).

graphtage.bounds.NEGATIVE_INFINITY

Negative infinity.

Type:: Infinity

graphtage.bounds.POSITIVE_INFINITY

Positive infinity.

Type:: Infinity

bounds classes

Bounded

class graphtage.bounds.Bounded(*args, **kwargs)

Bases: Protocol

A protocol for objects that have bounds that can be tightened.

__init__(*args, **kwargs)

bounds() → Range: Returns the bounds of this object.

tighten_bounds() → bool

Attempts to shrink the bounds of this object.

Returns:: True if the bounds were tightened.
Return type:: bool

BoundedComparator

class graphtage.bounds.BoundedComparator(bounded: Bounded)

Bases: object

A comparator for Bounded objects.

This comparator will automatically tighten the bounds of the Bounded object it wraps until they are either definitive or sufficiently distinct to differentiate them from another object to which it is being compared.

__init__(bounded: Bounded)

Initializes this bounded comparator.

Parameters:: bounded – The object to wrap.

__lt__(other)

Compares the wrapped object to other, auto-tightening their bounds if necessary.

The auto-tightening is equivalent to:

while not (
    self.bounded.bounds().dominates(other.bounded.bounds())
    or
    other.bounded.bounds().dominates(self.bounded.bounds())
) and (
    self.bounded.tighten_bounds() or other.bounded.tighten_bounds()
):
    pass

In the event that self.bounded and other have identical bounds after fully tightening, the object with the smaller id() is returned.

bounded: The wrapped bounded object.

ConstantBound

class graphtage.bounds.ConstantBound(value: int | Infinity)

Bases: Bounded

An object with constant bounds.

__init__(value: int | Infinity)

Initializes the constant bounded object.

Parameters:: value – The constant value of the object, which will constitute both its lower and upper bound.

bounds() → Range: Returns a Range where both the lower and upper bounds are equal to this object’s constant value.

tighten_bounds() → bool: Since the bounds are already definitive, this always returns False.

IdentityInterval

class graphtage.bounds.IdentityInterval(begin, end, data=None)

Bases: Interval

An intervaltree.Interval that also hashes on the identity of its data.

intervaltree.Interval hashes on (begin, end) alone, but its equality test compares data as well. intervaltree.IntervalTree stores its intervals in set objects, so intervals that share a span but carry different data all land in one hash bucket, and every insertion and lookup degenerates into a linear scan of equality tests. make_distinct() hits that case directly: the bounded objects it receives start out with near-identical bounds.

Mixing id(data) into the hash spreads those intervals across buckets. make_distinct() needs one interval per bounded object regardless of how those objects compare, so distinguishing them by identity matches what the function already assumes.

Note

Do not look up an IdentityInterval with a plain intervaltree.Interval, or the other way around. The two hash differently, so the lookup misses even when the intervals compare equal. intervaltree.IntervalTree builds no intervals of its own on the add, remove, and overlap-query paths that make_distinct() uses, so the tree here only ever holds and probes instances of this class.

__cmp__(other)

Tells whether other sorts before, after or equal to this Interval.

Sorting is by begins, then by ends, then by data fields.

If data fields are not both sortable types, data fields are compared alphabetically by type name. :param other: Interval :return: -1, 0, 1 :rtype: int

__eq__(other): Whether the begins equal, the ends equal, and the data fields equal. Compare range_matches(). :param other: Interval :return: True or False :rtype: bool

__gt__(other): Greater than operator. Parrots __cmp__() :param other: Interval or point :return: True or False :rtype: bool

__init__()

__lt__(other): Less than operator. Parrots __cmp__() :param other: Interval or point :return: True or False :rtype: bool

__reduce__(): For pickle-ing. :return: pickle data :rtype: tuple

__repr__(): Executable string representation of this Interval. :return: string representation :rtype: str

__str__(): Executable string representation of this Interval. :return: string representation :rtype: str

_get_fields()

Used by str, unicode, repr and __reduce__.

Returns only the fields necessary to reconstruct the Interval. :return: reconstruction info :rtype: tuple

_raise_if_null(other)

Raises:: ValueError – if either self or other is a null Interval

begin: Alias for field number 0

contains_interval(other): Whether other is contained in this Interval. :param other: Interval :return: True or False :rtype: bool

contains_point(p): Whether the Interval contains p. :param p: a point :return: True or False :rtype: bool

copy(): Shallow copy. :return: copy of self :rtype: Interval

count(value, /): Return number of occurrences of value.

data: Alias for field number 2

distance_to(other): Returns the size of the gap between intervals, or 0 if they touch or overlap. :param other: Interval or point :return: distance :rtype: Number

end: Alias for field number 1

ge(other): Greater than or overlaps. Returns True if no part of this Interval extends lower than other. :raises ValueError: if either self or other is a null Interval :param other: Interval or point :return: True or False :rtype: bool

gt(other): Strictly greater than. Returns True if no part of this Interval extends lower than or into other. :raises ValueError: if either self or other is a null Interval :param other: Interval or point :return: True or False :rtype: bool

index(value, start=0, stop=9223372036854775807, /)

Return first index of value.

Raises ValueError if the value is not present.

is_null(): Whether this equals the null interval. :return: True if end <= begin else False :rtype: bool

le(other): Less than or overlaps. Returns True if no part of this Interval extends higher than other. :raises ValueError: if either self or other is a null Interval :param other: Interval or point :return: True or False :rtype: bool

length(): The distance covered by this Interval. :return: length :type: Number

lt(other): Strictly less than. Returns True if no part of this Interval extends higher than or into other. :raises ValueError: if either self or other is a null Interval :param other: Interval or point :return: True or False :rtype: bool

overlap_size(begin, end=None): Return the overlap size between two intervals or a point :param begin: beginning point of the range, or the point, or an Interval :param end: end point of the range. Optional if not testing ranges. :return: Return the overlap size, None if not overlap is found :rtype: depends on the given input (e.g., int will be returned for int interval and timedelta for datetime intervals)

overlaps(begin, end=None): Whether the interval overlaps the given point, range or Interval. :param begin: beginning point of the range, or the point, or an Interval :param end: end point of the range. Optional if not testing ranges. :return: True or False :rtype: bool

range_matches(other): Whether the begins equal and the ends equal. Compare __eq__(). :param other: Interval :return: True or False :rtype: bool

Infinity

class graphtage.bounds.Infinity(positive=True)

Bases: object

A class for representing infinite values. This is primarily used for unbounded ranges.

__init__(positive=True)

property positive: bool: Returns whether or not this represents positive infinity.

Range

class graphtage.bounds.Range(lower_bound: int | Infinity = Infinity(positive=False), upper_bound: int | Infinity = Infinity(positive=True))

Bases: object

An integer range.

__init__(lower_bound: int | Infinity = Infinity(positive=False), upper_bound: int | Infinity = Infinity(positive=True))

Constructs a range.

Parameters:

lower_bound – The lower bound of the range (inclusive).
upper_bound – The upper bound of the range (inclusive).

Raises:

ValueError – If the upper bound is less than the lower bound.

definitive() → bool

Checks whether this range is definitive.

A range is definitive if both of its bounds are finite and equal to each other.

dominates(other) → bool

Checks whether this range dominates another.

One range dominates another if its upper bound is less than or equal to the lower bound of the other.

This is equivalent to:

return self.upper_bound <= other.lower_bound

property finite: bool

Returns whether this range is finite.

A range is finite if neither of its bounds is infinite.

intersect(other) → Range: Intersects this range with another.

lower_bound: int | Infinity: The lower bound of this range.

to_interval() → Interval: Converts this range to an intervaltree.Interval for use with the Interval Tree package.

upper_bound: int | Infinity: The upper bound of this range.

bounds functions

make_distinct

graphtage.bounds.make_distinct(*bounded: Bounded): Ensures that all of the provided bounded arguments are tightened until they are finite and either definitive or non-overlapping with any of the other arguments.

min_bounded

graphtage.bounds.min_bounded(bounds: Iterator[B]) → B

Returns the smallest bounded object.

The objects are auto-tightened in the event that their ranges overlap and a definitive minimum does not exist.

repeat_until_tightened

graphtage.bounds.repeat_until_tightened(func)

A decorator that will repeatedly call the function until its class’s bounds are tightened.

Intended for Bounded.tighten_bounds(). The value returned by the decorated function is ignored.

sort

graphtage.bounds.sort(items: Iterable[B]) → Iterator[B]

Sorts a sequence of bounded items.

Parameters:: items – Zero or more bounded objects.
Returns:: An iterator over the sorted sequence of items.
Return type:: Iterator[B]

This is equivalent to:

heap: FibonacciHeap[B, BoundedComparator] = FibonacciHeap(key=BoundedComparator)
for item in items:
    heap.push(item)
while heap:
    yield heap.pop()