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).
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() graphtage.bounds.Range ¶
Returns the bounds of this object.
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
andother
have identical bounds after fully tightening, the object with the smallerid()
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.
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: bool¶
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: Union[int, graphtage.bounds.Infinity]¶
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: Union[int, graphtage.bounds.Infinity]¶
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¶
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[graphtage.bounds.B]) Iterator[graphtage.bounds.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()