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: typing.Protocol

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

__init__(*args, **kwargs)

Initialize self. See help(type(self)) for accurate signature.

bounds()graphtage.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: graphtage.bounds.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: graphtage.bounds.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: Union[int, graphtage.bounds.Infinity])

Bases: graphtage.bounds.Bounded

An object with constant bounds.

__init__(value: Union[int, graphtage.bounds.Infinity])

Initializes the constant bounded object.

Parameters

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

bounds()graphtage.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.

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)

Initialize self. See help(type(self)) for accurate signature.

property positive

Returns whether or not this represents positive infinity.

Range

class graphtage.bounds.Range(lower_bound: Union[int, graphtage.bounds.Infinity] = Infinity(positive=False), upper_bound: Union[int, graphtage.bounds.Infinity] = Infinity(positive=True))

Bases: object

An integer range.

__init__(lower_bound: Union[int, graphtage.bounds.Infinity] = Infinity(positive=False), upper_bound: Union[int, graphtage.bounds.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

Returns whether this range is finite.

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

intersect(other)graphtage.bounds.Range

Intersects this range with another.

lower_bound: RangeValue

The lower bound of this range.

to_interval() → intervaltree.interval.Interval

Converts this range to an intervaltree.Interval for use with the Interval Tree package.

upper_bound: RangeValue

The upper bound of this range.

bounds functions

make_distinct

graphtage.bounds.make_distinct(*bounded: graphtage.bounds.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()