ellalgo package

Subpackages

ellalgo.oracles namespace

Submodules

ellalgo.conjugate_gradient module

Conjugate Gradient method for solving symmetric positive-definite linear systems.

This module implements the Conjugate Gradient (CG) iterative algorithm for solving Ax = b where A is a symmetric positive-definite matrix. The CG method generates A-orthogonal search directions and is guaranteed to converge in at most n iterations in exact arithmetic.

exception ellalgo.conjugate_gradient.ConvergenceError[source]

Bases: ValueError

Raised when an iterative solver fails to converge within max_iter.

ellalgo.conjugate_gradient.conjugate_gradient(A: ndarray, b: ndarray, x0: ndarray | None = None, tol: float = 1e-05, max_iter: int = 1000) → ndarray[source]

Solve $\mathbf{Ax} = \mathbf{b}$ using the Conjugate Gradient method.

The CG method generates $\mathbf{A}$-orthogonal (conjugate) search directions and converges in at most $n$ iterations in exact arithmetic. The iteration proceeds as follows:

\[\begin{split}\mathbf{r}_0 &= \mathbf{b} - \mathbf{A}\mathbf{x}_0,\qquad \mathbf{p}_0 = \mathbf{r}_0 \\[4pt] \alpha_k &= \frac{\mathbf{r}_k^T \mathbf{r}_k} {\mathbf{p}_k^T \mathbf{A} \mathbf{p}_k} \\[4pt] \mathbf{x}_{k+1} &= \mathbf{x}_k + \alpha_k \mathbf{p}_k \\[4pt] \mathbf{r}_{k+1} &= \mathbf{r}_k - \alpha_k \mathbf{A} \mathbf{p}_k \\[4pt] \beta_k &= \frac{\mathbf{r}_{k+1}^T \mathbf{r}_{k+1}} {\mathbf{r}_k^T \mathbf{r}_k} \\[4pt] \mathbf{p}_{k+1} &= \mathbf{r}_{k+1} + \beta_k \mathbf{p}_k\end{split}\]

The algorithm terminates when $\|\mathbf{r}_k\| < \text{tol}$.

Parameters:

A – Symmetric positive-definite coefficient matrix.
b – Right-hand side vector.
x0 – Initial guess (default: zero vector).
tol – Convergence tolerance on residual norm (default: 1e-5).
max_iter – Maximum iterations (default: 1000).

Returns:

Solution vector $\mathbf{x}$ satisfying $\mathbf{Ax} = \mathbf{b}$.

Raises:

ValueError – If the method does not converge within max_iter iterations.

ellalgo.cutting_plane module

Cutting-plane algorithms for convex optimization.

This module implements the core cutting-plane loop that drives the ellipsoid method. It provides four algorithm entry points:

cutting_plane_feas: Solve convex feasibility problems f(x) ≤ 0.

cutting_plane_optim: Solve convex maximization problems.

cutting_plane_optim_q: Variant for discrete/quantized optimization.

bsearch: Binary search over monotonic objectives using a feasibility oracle.

The algorithms work iteratively: at each step the oracle assesses the current center point, returning either success (feasible/optimal) or a cutting plane that eliminates part of the search space. The process repeats until convergence or iteration limit.

class ellalgo.cutting_plane.BSearchAdaptor(omega: OracleFeas, space: SearchSpace, options: Options | None = None)[source]

Bases: OracleBS

Adapter for using feasibility oracle in binary search.

Enables g-parameterized feasibility checks for: maximize g s.t. Exists x feasible for given g

Maintains state between binary search iterations for efficiency.

assess_bs(gamma: float | int) → bool[source]

Test feasibility for given g value.

Implementation: 1. Clone current search space state 2. Update oracle with new g value 3. Solve feasibility subproblem 4. Update main space if feasible solution found

property x_best: Any: Current best feasible solution candidate.

class ellalgo.cutting_plane.OptimQState[source]

Bases: object

State machine for the discrete cutting-plane method.

Encapsulates the mutable state of cutting_plane_optim_q: the best-so-far solution x_best and the retry phase flag. The on_update transition maps a CutStatus (plus the oracle’s more_alt hint) onto a control-flow outcome.

Note

State pattern: the driver loop asks the machine for its current phase (retry), feeds it each oracle/space result, and stops when on_update returns False. The retry/termination bookkeeping that used to be scattered through the loop now lives in one place.

Parameters:: None.

x_best: Best-so-far discrete solution (None until first improvement).

retry: Whether the next assessment is a retry (reuse cached point).

on_shrunk(x_q: ArrayType) → None[source]

Transition on a newly obtained (shrunk) best solution.

Parameters:: x_q – The new best discrete point.

on_update(status: CutStatus, more_alt: bool) → bool[source]

Transition on the space update result.

Parameters:

status – CutStatus returned by space.update_q.
more_alt – Whether the oracle has more alternative cuts.

Returns:

True to keep iterating; False to stop.

class ellalgo.cutting_plane.SolverResult(values: Tuple[Any, ...], status: SolverStatus)[source]

Bases: tuple

Result of a cutting-plane / binary-search solve.

Unpacks exactly like the historical plain tuples (x, niter = ...) while additionally exposing status, so callers can tell an exhausted search space (Infeasible) apart from an iteration-cap stop (MaxIters) — both previously surfaced only as None.

status: SolverStatus

ellalgo.cutting_plane.bsearch(omega: OracleBS, intrvl: Tuple[Any, Any], options: Options | None = None) → Tuple[Any, int][source]

Binary search with feasibility oracle.

Operates on monotonic objectives by: 1. Maintaining upper/lower bounds 2. Testing mid-point feasibility 3. Halving search interval each iteration

Parameters:

omega – Binary search oracle implementing assess_bs()
intrvl – (lower, upper) bound tuple
options – Control parameters

Returns:

(Best g found, iterations used)

Examples

>>> from ellalgo.cutting_plane import bsearch
>>> from ellalgo.ell_config import Options
>>> class MyOracle:
...     def assess_bs(self, gamma):
...         return gamma > 0.5
>>> omega = MyOracle()
>>> upper, niter = bsearch(omega, (0.0, 1.0), Options())
>>> upper > 0.5
True

ellalgo.cutting_plane.cutting_plane_feas(omega: OracleFeas[ArrayType], space: SearchSpace[ArrayType], options: Options | None = None) → Tuple[ArrayType | None, int][source]

Cutting-plane algorithm for convex feasibility problems.

This algorithm solves the problem of finding a feasible solution for a convex function f(x) such that f(x) <= 0. It uses an iterative cutting-plane approach.

Implementation Details: The algorithm works as follows:

At each iteration, it queries the oracle at the current center point xc.
If the point is feasible (i.e., cut is None), it returns xc as a solution.
If the point is infeasible, the oracle returns a separating hyperplane (a “cut”).
The search space is then updated by eliminating the region that violates the cut.
This process is repeated until the search space becomes too small (i.e., tsq < tolerance).

Mathematical Basis: For a convex function f and a given point xc, if f(xc) > 0, there exists a subgradient g such that f(x) >= g^T(x - xc) + f(xc) for all x. The cut is defined by g^T(x - xc) + beta <= 0, where beta = f(xc). This cut eliminates the infeasible region from the search space.

┌────────────┐ ┌───────────┐┌──────────┐ │CuttingPlane│ │SearchSpace││OracleFeas│ └─────┬──────┘ └─────┬─────┘└────┬─────┘ │ │ │ │ request xc │ │ │────────────────>│ │ │ │ │ │ return xc │ │ │<────────────────│ │ │ │ │ │ assess_feas(xc) │ │────────────────────────────>│ │ │ │ │ return cut │ │<────────────────────────────│ │ │ │ │update by the cut│ │ │────────────────>│ │ ┌─────┴──────┐ ┌─────┴─────┐┌────┴─────┐ │CuttingPlane│ │SearchSpace││OracleFeas│ └────────────┘ └───────────┘└──────────┘

Parameters:

omega (ellalgo.ell_typing.OracleFeas) – The feasibility oracle.
space (ellalgo.ell_typing.SearchSpace) – The search space.
options (ellalgo.ell_config.Options, optional) – The options for the algorithm. Defaults to Options().

Returns:

A tuple containing the feasible solution (if found) and the number of iterations.

Return type:

Tuple[Optional[ArrayType], int]

Examples

>>> import numpy as np
>>> from ellalgo.cutting_plane import cutting_plane_feas
>>> from ellalgo.ell import Ell
>>> from ellalgo.ell_config import Options
>>> class MyOracle:
...     def assess_feas(self, xc):
...         return (np.array([1.0, 1.0]), 0.0) if xc[0] + xc[1] > 0 else None
>>> omega = MyOracle()
>>> space = Ell(10.0, np.array([0.0, 0.0]))
>>> x, niter = cutting_plane_feas(omega, space, Options())
>>> x is not None
True

ellalgo.cutting_plane.cutting_plane_optim(omega: OracleOptim[ArrayType], space: SearchSpace[ArrayType], gamma: float, options: Options | None = None) → Tuple[ArrayType | None, float, int][source]

Cutting-plane method for convex optimization problems.

This algorithm solves the problem of maximizing a variable gamma subject to the constraint f(x) >= gamma, where f is a convex function. It uses a cutting-plane approach with central and bias cut updates.

The algorithm maintains the current best gamma and the corresponding candidate solution x_best. It alternates between two types of cuts:

Optimality cuts: These are used to improve the value of gamma when a better solution is found.
Feasibility cuts: These are used to maintain the feasibility of the solution space as gamma increases.

The update rules for the search space are as follows:

Central cut: This tightens the search around a solution that has shown improvement.
Bias cut: This maintains the feasibility of the current gamma level.

Parameters:

omega (ellalgo.ell_typing.OracleOptim) – The optimization oracle.
space (ellalgo.ell_typing.SearchSpace) – The search space.
gamma (float) – The initial best objective value.
options (ellalgo.ell_config.Options, optional) – The options for the algorithm. Defaults to Options().

Returns:

A tuple containing the best solution, the achieved gamma, and the number of iterations.

Return type:

Tuple[Optional[ArrayType], float, int]

Examples

>>> import numpy as np
>>> from ellalgo.cutting_plane import cutting_plane_optim
>>> from ellalgo.ell import Ell
>>> from ellalgo.ell_config import Options
>>> class MyOracle:
...     def assess_optim(self, xc, gamma):
...         g = 2 * (xc[0] + xc[1]) * np.array([1.0, 1.0])
...         if np.all(g == 0.0):
...             g = np.array([1.0, 1.0])
...         if (xc[0] + xc[1])**2 > gamma:
...             return (g, 0.0), (xc[0] + xc[1])**2
...         else:
...             return (g, 0.0), None
>>> omega = MyOracle()
>>> space = Ell(10.0, np.array([0.0, 0.0]))
>>> x, _, niter = cutting_plane_optim(omega, space, 0.0, Options())
>>> x is not None
True

ellalgo.cutting_plane.cutting_plane_optim_q(omega: OracleOptimQ[ArrayType], space_q: SearchSpace[ArrayType], gamma: float, options: Options | None = None) → Tuple[ArrayType | None, float, int][source]

Cutting-plane method for discrete convex optimization.

Handles quantized solutions through: - Continuous relaxation with rounding - Retry mechanism for discrete feasibility checks - Adaptive cut management for discrete solutions

Process Flow: 1. First attempt with continuous solution 2. If feasible, round to nearest integer solution 3. Verify discrete solution feasibility 4. Generate cuts adjusted for rounding effects

Parameters:

omega – Discrete optimization oracle
space_q – Quantized search space
gamma – Initial best objective value
options – Algorithm parameters

Returns:

(Best discrete solution, achieved g, iterations)

ellalgo.ell module

Ellipsoid search space implementation for the ellipsoid method.

The Ell class represents a convex search space as an n-dimensional ellipsoid defined by a center point and a shape matrix. It provides methods to update the ellipsoid when cutting planes (deep cuts, central cuts, parallel cuts) are applied, progressively narrowing the search region toward an optimal solution.

This module implements the classic direct Q-update strategy. See EllBase for the shared public API.

Key operations:

update_bias_cut: Apply a deep (non-central) cut
update_central_cut: Apply a central cut through the ellipsoid center
update_q: Apply a cut for discrete/quantized optimization

class ellalgo.ell.Ell(val: float | ArrayType, x_center: ArrayType, no_defer_trick: bool = False)[source]

Bases: EllBase[ndarray]

Ellipsoid Search Space (classic direct Q-update strategy).

Concrete strategy of EllBase: updates the shape matrix directly via the rank-1 update $M \leftarrow M - (\sigma/\omega)\,\tilde{g}\tilde{g}^T$.

Examples

>>> import numpy as np
>>> from ellalgo.ell import Ell
>>> ell = Ell(1.0, np.array([0.0, 0.0]))
>>> ell.xc()
array([0., 0.])
>>> ell.tsq()
0.0

ellalgo.ell_base module

Shared ellipsoid search space base (Strategy pattern).

The EllBase class implements the common public API of the ellipsoid search space: construction from either a scalar (kappa) or per-axis values, center accessors, and the three cutting-plane update entry points. The actual ellipsoid update (_update_core) is delegated to concrete subclasses:

Ell: classic direct Q-update (see ellalgo.ell)

EllStable: numerically-stable LDL^T update (see ellalgo.ell_stable)

This mirrors the Strategy pattern: the cutting-plane drivers only depend on the SearchSpace protocol (xc, tsq, update_*), and the update strategy is selected by choosing the concrete subclass.

class ellalgo.ell_base.EllBase(val: float | ArrayType, x_center: ArrayType, no_defer_trick: bool = False)[source]

Bases: SearchSpace[ArrayType]

Ellipsoid Search Space (shared implementation).

The EllBase class represents an ellipsoid, which is a search space for convex optimization problems. It provides methods to update the ellipsoid based on cutting planes, which are used to narrow down the search for an optimal solution.

Concrete subclasses implement _update_core(), which applies the cutting plane to the ellipsoid using a specific matrix update strategy.

classmethod from_alpha(alpha: float, x_center: ArrayType) → EllBase[source]

Create an ellipsoid from a scaling factor.

Parameters:

alpha – The scaling factor (kappa) for the unit shape matrix.
x_center – The initial center point of the ellipsoid.

Returns:

A new ellipsoid initialized from a scalar scaling factor.

classmethod from_radii(val: ArrayType, x_center: ArrayType) → EllBase[source]

Create an ellipsoid from per-axis radii.

Parameters:

val – Per-axis radii (diagonal of the shape matrix).
x_center – The initial center point of the ellipsoid.

Returns:

A new ellipsoid initialized from per-axis values.

helper: EllCalc

no_defer_trick: bool

set_xc(x_center: ArrayType) → None[source]

Setter method for the ellipsoid’s center point.

Parameters:: x_center – The new center point for the ellipsoid

tsq() → float[source]

Getter method for the tsq value.

tsq represents the measure of distance between current center (xc) and optimal point (x*). It’s calculated as kappa * omega, where omega is grad^T * M * grad.

Returns:: The current tsq value

update_bias_cut(cut: Tuple[ArrayType, float | Tuple[float, float | None] | List[float]]) → CutStatus[source]

Update the ellipsoid using a bias cut (deep cut) strategy.

A bias cut is a general cut that can be either deep or shallow. This method delegates to _update_core with the standard cut strategy.

Parameters:: cut – A tuple containing (gradient, beta) for the cut
Returns:: CutStatus indicating success or failure of the update

Examples

>>> import numpy as np
>>> from ellalgo.ell import Ell
>>> from ellalgo.ell_config import CutStatus
>>> ell = Ell(1.0, np.array([0.0, 0.0]))
>>> cut = (np.array([1.0, 1.0]), 0.0)
>>> status = ell.update_bias_cut(cut)
>>> status == CutStatus.Success
True

update_central_cut(cut: Tuple[ArrayType, float | Tuple[float, float | None] | List[float]]) → CutStatus[source]

Update the ellipsoid using a central cut strategy.

A central cut is a special case where beta = 0, meaning the cut passes exactly through the center of the current ellipsoid.

Parameters:: cut – A tuple containing (gradient, beta) for the cut
Returns:: CutStatus indicating success or failure of the update

Examples

>>> import numpy as np
>>> from ellalgo.ell import Ell
>>> from ellalgo.ell_config import CutStatus
>>> ell = Ell(1.0, np.array([0.0, 0.0]))
>>> cut = (np.array([1.0, 1.0]), 0.0)
>>> status = ell.update_central_cut(cut)
>>> status == CutStatus.Success
True

update_q(cut: Tuple[ArrayType, float | Tuple[float, float | None] | List[float]]) → CutStatus[source]

Update the ellipsoid using a non-central cut strategy for Q.

This is used for non-central cuts (either deep or shallow) in Q space.

Parameters:: cut – A tuple containing (gradient, beta) for the cut
Returns:: CutStatus indicating success or failure of the update

Examples

>>> import numpy as np
>>> from ellalgo.ell import Ell
>>> from ellalgo.ell_config import CutStatus
>>> ell = Ell(1.0, np.array([0.0, 0.0]))
>>> cut = (np.array([1.0, 1.0]), 0.01)
>>> status = ell.update_q(cut)
>>> status == CutStatus.Success
True

xc() → ArrayType[source]

Getter method for the ellipsoid’s center point.

Returns:: The current center point (_xc) of the ellipsoid

ellalgo.ell_calc module

Ellipsoid calculation routines for the ellipsoid method.

The EllCalc class provides high-level dispatch logic for determining how to update an ellipsoid based on different types of cutting planes. It selects among single deep cuts, parallel cuts, and central cuts, delegating the low-level mathematical computations to EllCalcCore.

Cut types supported:

Deep cut (bias cut): A hyperplane that does not pass through the center.
Central cut: A hyperplane passing through the ellipsoid center.
Parallel cut: Two parallel hyperplanes cutting the ellipsoid.
Quantized variants: Versions optimized for discrete optimization stability.

class ellalgo.ell_calc.EllCalc(n: int, use_parallel_cut: bool = True)[source]

Bases: object

Ellipsoid Calculator for the Ellipsoid Method.

The EllCalc class is a core component of the ellipsoid method, responsible for calculating the parameters required to update the search ellipsoid at each iteration. It provides methods for various types of cutting planes, including deep cuts, parallel cuts, and central cuts.

A deep cut is a hyperplane that cuts the ellipsoid, excluding a portion of the search space that does not contain the optimal solution.
A parallel cut uses two parallel hyperplanes to cut the ellipsoid, which can be more efficient in certain situations.
A central cut is a special case of a deep cut that passes through the center of the ellipsoid.

The class uses an instance of EllCalcCore to perform the low-level mathematical computations, while it handles the higher-level logic for selecting the appropriate cut type and returning the results.

calc_bias_cut(beta: float, tsq: float) → Tuple[CutStatus, Tuple[float, float, float] | None][source]

Calculate parameters for a single deep cut.

A deep cut is a hyperplane cut that doesn’t necessarily pass through the center of the ellipsoid. This method validates the input and calculates the transformation parameters if valid.

Parameters:

beta (float) – Cut parameter (must be >= 0).
tsq (float) – Square of the tolerance parameter (τ²).

Returns:

Status and optional result tuple.

Examples

>>> from ellalgo.ell_calc import EllCalc
>>> from ellalgo.ell_config import CutStatus
>>> calc = EllCalc(3)
>>> status, result = calc.calc_bias_cut(1.0, 4.0)
>>> status
<CutStatus.Success: 0>
>>> result[0]
1.25
>>> status, result = calc.calc_bias_cut(0.0, 4.0)
>>> status
<CutStatus.Success: 0>
>>> result[0]
0.5
>>> status, result = calc.calc_bias_cut(1.5, 2.0)
>>> status
<CutStatus.NoSoln: 1>

calc_bias_cut_q(beta: float, tsq: float) → Tuple[CutStatus, Tuple[float, float, float] | None][source]

Calculate deep cut (discrete optimization version).

This version includes additional checks for numerical stability in discrete optimization problems, specifically checking if eta ≤ 0.0.

Parameters:

beta (float) – Cut parameter.
tsq (float) – Square of the tolerance parameter (τ²).

Returns:

Status and optional result tuple.

Examples

>>> from ellalgo.ell_calc import EllCalc
>>> from ellalgo.ell_config import CutStatus
>>> calc = EllCalc(3)
>>> status, result = calc.calc_bias_cut_q(0.0, 4.0)
>>> status
<CutStatus.Success: 0>
>>> result[0]
0.5
>>> status, result = calc.calc_bias_cut_q(1.5, 2.0)
>>> status
<CutStatus.NoSoln: 1>
>>> status, result = calc.calc_bias_cut_q(-1.5, 4.0)
>>> status
<CutStatus.NoEffect: 2>

calc_parallel(beta0: float, beta1: float, tsq: float) → Tuple[CutStatus, Tuple[float, float, float] | None][source]

Calculate parameters for a parallel deep cut.

A parallel cut involves two parallel hyperplanes cutting the ellipsoid. This method calculates the transformation parameters for such a cut after validating the inputs.

Parameters:

beta0 (float) – First cut parameter (lower bound).
beta1 (float) – Second cut parameter (upper bound).
tsq (float) – Square of the tolerance parameter (τ²).

Returns:

Status and optional result tuple.

The method first checks if beta1 < beta0 (invalid case), then checks if the cut would be outside the ellipsoid (tsq ≤ b1sq), and falls back to a single cut if so. Otherwise, it calculates the parallel cut parameters.

calc_parallel_q(beta0: float, beta1: float, tsq: float) → Tuple[CutStatus, Tuple[float, float, float] | None][source]

Calculate parallel deep cut (discrete optimization version).

This version includes additional checks for numerical stability in discrete optimization problems, specifically checking if eta ≤ 0.0.

Parameters:

beta0 (float) – First cut parameter.
beta1 (float) – Second cut parameter.
tsq (float) – Square of the tolerance parameter (τ²).

Returns:

Status and optional result tuple.

calc_single_or_parallel(beta: float | Tuple[float, float | None] | List[float], tsq: float) → Tuple[CutStatus, Tuple[float, float, float] | None][source]

Calculates the parameters for either a single deep cut or a parallel cut.

This method acts as a dispatcher, determining whether to perform a single deep cut or a parallel cut based on the beta parameter.

If beta is a single float, a single deep cut is performed.
If beta is a list or tuple with two elements, a parallel cut is performed using beta[0] and beta[1] as the two cut parameters.
The use_parallel_cut flag can be used to disable parallel cuts, in which case a single deep cut will be used as a fallback.

Parameters:

beta – The cut parameter(s). Can be a single float for a deep cut, or a list/tuple of two floats for a parallel cut.
tsq – The square of the tolerance (τ²), used in the cut calculations.

Returns:

A tuple containing the CutStatus and an optional tuple of the update parameters (rho, sigma, delta) if the cut is successful.

calc_single_or_parallel_central_cut(beta: float | Tuple[float, float | None] | List[float], tsq: float) → Tuple[CutStatus, Tuple[float, float, float] | None][source]

Calculate either a single central cut or a parallel central cut.

Similar to calc_single_or_parallel but specifically for central cuts (cuts passing through the center of the ellipsoid).

Parameters:

beta – Either a single numeric value or a list of two values.
tsq – The square of the tolerance parameter (τ²).

Returns:

A tuple containing status and optional result values.

Examples

>>> from ellalgo.ell_calc import EllCalc
>>> from ellalgo.ell_config import CutStatus
>>> from pytest import approx
>>> calc = EllCalc(4)
>>> status, result = calc.calc_single_or_parallel_central_cut([0, 0.11], 0.01)
>>> status
<CutStatus.Success: 0>
>>> result[0] == approx(0.02)
True

calc_single_or_parallel_q(beta: float | Tuple[float, float | None] | List[float], tsq: float) → Tuple[CutStatus, Tuple[float, float, float] | None][source]

Calculate either single or parallel deep cut (discrete version).

This is a variant of calc_single_or_parallel designed for discrete optimization problems, with additional checks for numerical stability.

Parameters:

beta – Either a single numeric value or a list of two values.
tsq (float) – Square of the tolerance parameter (τ²).

Returns:

Status and optional result tuple.

helper: EllCalcCore

use_parallel_cut: bool

ellalgo.ell_calc_core module

Core mathematical computations for ellipsoid updates.

The EllCalcCore class implements the low-level formulas that compute the ellipsoid update parameters (rho, sigma, delta) for various types of cuts. These three parameters define the transformation applied to the ellipsoid’s center and shape matrix after each cutting-plane iteration.

Supported cut calculations:

calc_central_cut: Central cut through the ellipsoid center.
calc_bias_cut / calc_bias_cut_fast: Deep (non-central) cuts.
calc_parallel_central_cut: Parallel central cut.
calc_parallel_bias_cut / calc_parallel_bias_cut_fast: Parallel deep cuts.

Legacy/alternative formulations now live in ellalgo.ell_calc_legacy.

All methods return (rho, sigma, delta) — the center displacement, shape scaling, and size adjustment factor respectively.

class ellalgo.ell_calc_core.EllCalcCore(n_f: float)[source]

Bases: object

The EllCalcCore class provides the low-level mathematical calculations required for the ellipsoid method. It computes the essential parameters (rho, sigma, and delta) that define the transformation of the search ellipsoid at each iteration of the algorithm.

rho (ρ): Represents the displacement of the ellipsoid’s center.
sigma (σ): A scaling factor for the ellipsoid’s shape matrix.
delta (δ): A factor that adjusts the overall size of the ellipsoid.

This class is designed to be used by EllCalc, which handles the higher-level logic of the ellipsoid method. By encapsulating the core calculations, EllCalcCore allows for a clean separation of concerns and facilitates maintenance and optimization of the mathematical formulas.

calc_bias_cut(beta: float, tau: float) → Tuple[float, float, float][source]

Deep cut ellipsoid parameters (standard version).

Deep cut where the hyperplane does not pass through the center. Computes $\eta = \tau + n \beta$ internally and delegates to calc_bias_cut_fast().

\[\begin{split}\eta &= \tau + n \beta \\[4pt] \rho &= \frac{\eta}{n+1} \\[4pt] \sigma &= \frac{2\eta}{(n+1)(\tau + \beta)} \\[4pt] \delta &= \frac{n^2}{n^2-1}\, \frac{\tau^2 - \beta^2}{\tau^2}\end{split}\]

$_.-'''''''-._ ,' | `. / | \ . | . | | | | | . | | | | :\ | /: | `._ | _.' | | '-.......-' | | | | "-τ" "-β" +τ$

Parameters:

beta – Bias distance from center to cut hyperplane
tau – Distance parameter for the cut

Returns:

Tuple $(\rho, \sigma, \delta)$ for the biased cut

Examples

>>> calc = EllCalcCore(3)
>>> calc.calc_bias_cut(1.0, 2.0)
(1.25, 0.8333333333333334, 0.84375)
>>> calc.calc_bias_cut(0.0, 2.0)
(0.5, 0.5, 1.125)

calc_bias_cut_fast(beta: float, tau: float, eta: float) → Tuple[float, float, float][source]

Deep cut ellipsoid parameters (with precomputed $\eta$).

A deep (non-central) cut at distance $\beta$ from the center. The auxiliary variable $\eta = \tau + n \beta$ is passed in to avoid recomputation.

\[\begin{split}\eta &= \tau + n \beta \\[4pt] \rho &= \frac{\eta}{n+1} \\[4pt] \sigma &= \frac{2\rho}{\tau + \beta} = \frac{2\eta}{(n+1)(\tau + \beta)} \\[4pt] \delta &= \frac{n^2}{n^2-1}\, \frac{\tau^2 - \beta^2}{\tau^2}\end{split}\]

$_.-'''''''-._ ,' | `. / | \ . | . | | | | | . | | | | :\ | /: | `._ | _.' | | '-.......-' | | | | "-τ" "-β" +τ$

Parameters:

beta – Bias distance from center to cut hyperplane
tau – Distance parameter for the cut
eta – Precomputed $\tau + n \beta$

Returns:

Tuple $(\rho, \sigma, \delta)$ for the biased cut

Examples

>>> calc = EllCalcCore(3)
>>> calc.calc_bias_cut_fast(1.0, 2.0, 5.0)
(1.25, 0.8333333333333334, 0.84375)
>>> calc.calc_bias_cut_fast(0.0, 2.0, 2.0)
(0.5, 0.5, 1.125)

calc_central_cut(tau: float) → Tuple[float, float, float][source]

Update parameters for a central cut.

A central cut passes through the ellipsoid center. The update parameters $\rho, \sigma, \delta$ are dimension-dependent constants scaled by $\tau$:

\[\begin{split}\rho &= \frac{1}{n+1}\,\tau \\[4pt] \sigma &= \frac{2}{n+1} \\[4pt] \delta &= \frac{n^2}{n^2-1}\end{split}\]

where $n$ is the dimension of the space and $\tau$ is the distance from the center to the ellipsoid boundary along the cut direction.

Parameters:: tau – The distance parameter for the central cut.
Returns:: Tuple (rho, sigma, delta) for the ellipsoid update.

calc_parallel_bias_cut(beta0: float, beta1: float, tsq: float) → Tuple[float, float, float][source]

Parallel deep cut (standard version).

Two parallel biased cuts at $\beta_0$ and $\beta_1$. Computes intermediates $\eta = \tau^2 + n \beta_0 \beta_1$ and delegates to calc_parallel_bias_cut_fast().

\[\begin{split}\eta &= \tau^2 + n\,\beta_0 \beta_1 \\[4pt] \bar\beta &= \frac{\beta_0 + \beta_1}{2} \\[4pt] h &= \tfrac12\bigl(\tau^2 + \beta_0 \beta_1\bigr) + n\,\bar\beta^{\,2} \\[4pt] k &= h + \sqrt{h^2 - (n+1)\,\eta\,\bar\beta^{\,2}} \\[4pt] \sigma &= \frac{\eta}{k} \\[4pt] \rho &= \bar\beta\,\sigma \\[4pt] \frac{1}{\mu} &= \frac{\eta}{k - \eta} \\[4pt] \delta &= 1 + \frac{1}{\mu\tau^2}\, \bigl(\bar\beta^{\,2}\sigma - \beta_0\beta_1\bigr)\end{split}\]

$_.-'''''''-._ ,' | `. / | | \ . | | . | | | | | | |. | | | | | :\ | | /: | `._ | _.' | | |'-.......-' | | | | | "-τ" "-β" "-β" +τ 1 0$

Parameters:

beta0 – First bias parameter
beta1 – Second bias parameter
tsq – Square of $\tau$

Returns:

Tuple $(\rho, \sigma, \delta)$

Examples

>>> calc = EllCalcCore(4)
>>> calc.calc_parallel_bias_cut(0.01, 0.11, 0.01)
(0.027228509068282114, 0.45380848447136857, 1.0443438549074862)
>>> calc.calc_parallel_bias_cut(-0.25, 0.25, 1.0)
(0.0, 0.8, 1.25)
>>> calc.calc_parallel_bias_cut(0.0, 0.09, 0.01)
(0.020941836487980856, 0.46537414417735234, 1.082031295477563)

calc_parallel_bias_cut_fast(beta0: float, beta1: float, tsq: float, b0b1: float, eta: float) → Tuple[float, float, float][source]

Parallel deep cut (optimized formulation).

Uses auxiliary variables $\zeta_0 = \tau^2 - \beta_0^2$ and $\zeta_1 = \tau^2 - \beta_1^2$ to compute:

\[\begin{split}\zeta_0 &= \tau^2 - \beta_0^2 \\[4pt] \zeta_1 &= \tau^2 - \beta_1^2 \\[4pt] \xi &= \sqrt{\zeta_0 \zeta_1 + \left(\frac{n}{2}(\beta_1^2 - \beta_0^2)\right)^{\!2}} \\[6pt] \sigma &= \frac{2\eta}{\tau^2 + \beta_0\beta_1 + \frac{n}{2}(\beta_0+\beta_1)^2 + \xi} \\[4pt] \rho &= \sigma\,\frac{\beta_0 + \beta_1}{2} \\[4pt] \delta &= \frac{n^2}{(n^2-1)\,\tau^2}\, \left(\frac{\zeta_0 + \zeta_1}{2} + \frac{\xi}{n}\right)\end{split}\]

Parameters:

beta0 – First bias parameter
beta1 – Second bias parameter
tsq – Square of $\tau$
b0b1 – Precomputed $\beta_0\beta_1$
eta – Precomputed $\tau^2 + n\beta_0\beta_1$

Returns:

Tuple $(\rho, \sigma, \delta)$

Examples

>>> calc = EllCalcCore(4)
>>> calc.calc_parallel_bias_cut_fast(0.11, 0.01, 0.01, 0.0011, 0.0144)
(0.027228509068282114, 0.45380848447136857, 1.0443438549074862)
>>> calc.calc_parallel_bias_cut_fast(-0.25, 0.25, 1.0, -0.0625, 0.75)
(0.0, 0.8, 1.25)

calc_parallel_central_cut(beta1: float, tsq: float) → Tuple[float, float, float][source]

Parallel central cut parameters.

A cut parallel to a central cut, offset by $\beta_1$. The auxiliary variable $\alpha = \beta_1 / \tau$ and $k = \frac{n}{2}\alpha^2$ define the root $r$:

\[\begin{split}\alpha^2 &= \frac{\beta_1^2}{\tau^2} \\[4pt] k &= \frac{n}{2}\,\alpha^2 \\[4pt] r &= k + \sqrt{k^2 + 1 - \alpha^2} \\[4pt] \rho &= \frac{\beta_1}{r+1} \\[4pt] \sigma &= \frac{2}{r+1} \\[4pt] \delta &= \frac{r}{r - 1/n}\end{split}\]

$_.-'''''''-._ ,' | `. / | | \ . | | . | | | | | . | | | | :\ | | /: | `._ | _.' | | |'-.......-' | | | | | "-τ" "-β" 0 +τ 1$

Parameters:

beta1 – Offset parameter for the parallel cut
tsq – Square of the distance parameter $\tau^2$

Returns:

Tuple $(\rho, \sigma, \delta)$

Examples

>>> calc = EllCalcCore(4)
>>> calc.calc_parallel_central_cut(0.09, 0.01)
(0.020941836487980856, 0.46537414417735234, 1.082031295477563)

ellalgo.ell_calc_legacy module

Legacy and alternative ellipsoid-update formulations.

These slower / alternative parallel-cut formulas are kept for cross-language reference (see compare-py-cpp-rs.md) and regression testing only. The production cut-selection code in ellalgo.ell_calc uses EllCalcCore exclusively.

class ellalgo.ell_calc_legacy.EllCalcCoreLegacy(n_f: float)[source]

Bases: EllCalcCore

Reference-only alternative/legacy formulas (not used in production).

Inherits every production calculation from EllCalcCore and adds the historical *_old/*_fast2 variants.

calc_parallel_bias_cut_fast2(beta0: float, beta1: float, tsq: float, b0b1: float, eta: float) → Tuple[float, float, float][source]

Parallel deep cut (alternative sigma formulation).

Same $\zeta$ and $\xi$ as EllCalcCore.calc_parallel_bias_cut_fast() but uses an alternative $\sigma$ formula.

Parameters:

beta0 – First bias parameter
beta1 – Second bias parameter
tsq – Square of $\tau$
b0b1 – Precomputed $\beta_0\beta_1$
eta – Precomputed $\tau^2 + n\beta_0\beta_1$

Returns:

Tuple $(\rho, \sigma, \delta)$

Examples

>>> calc = EllCalcCoreLegacy(4)
>>> calc.calc_parallel_bias_cut_fast2(0.11, 0.01, 0.01, 0.0011, 0.0144)
(0.02722850906828212, 0.4538084844713687, 1.0443438549074862)
>>> calc.calc_parallel_bias_cut_fast2(0.0, 0.09, 0.01, 0.0, 0.01)
(0.020941836487980856, 0.46537414417735234, 1.082031295477563)

calc_parallel_bias_cut_fast_old(beta0: float, beta1: float, tsq: float, b0b1: float, eta: float) → Tuple[float, float, float][source]

Parallel deep cut (original fast formulation).

Uses $\bar\beta = (\beta_0+\beta_1)/2$ and the same $h, k$ computation as the standard version, but expressed as $\sigma = 1/(\mu+1)$.

Parameters:

beta0 – First bias parameter
beta1 – Second bias parameter
tsq – Square of $\tau$
b0b1 – Precomputed $\beta_0\beta_1$
eta – Precomputed $\tau^2 + n\beta_0\beta_1$

Returns:

Tuple $(\rho, \sigma, \delta)$

Examples

>>> calc = EllCalcCoreLegacy(4)
>>> calc.calc_parallel_bias_cut_fast_old(0.11, 0.01, 0.01, 0.0011, 0.0144)
(0.027228509068282114, 0.45380848447136857, 1.0443438549074862)
>>> calc.calc_parallel_bias_cut_fast_old(-0.25, 0.25, 1.0, -0.0625, 0.75)
(0.0, 0.8, 1.25)

calc_parallel_bias_cut_old(beta0: float, beta1: float, tsq: float) → Tuple[float, float, float][source]

Parallel deep cut (original slower formulation).

This version shares the same $\zeta_0, \zeta_1, \xi$ computation as calc_parallel_bias_cut_fast2() but the formulas are written in an expanded form.

Parameters:

beta0 – First bias parameter
beta1 – Second bias parameter
tsq – Square of $\tau$

Returns:

Tuple $(\rho, \sigma, \delta)$

Examples

>>> calc = EllCalcCoreLegacy(4)
>>> calc.calc_parallel_bias_cut_old(0.11, 0.01, 0.01)
(0.02722850906828212, 0.4538084844713687, 1.0443438549074862)

calc_parallel_central_cut_old(beta1: float, tsq: float) → Tuple[float, float, float][source]

Parallel central cut (original formulation).

Original (slower) formulation of the parallel central cut.

\[\begin{split}\xi &= \sqrt{(\tau^2 - \beta_1^2)\,\tau^2 + \left(\frac{n \beta_1^2}{2}\right)^{\!2}} \\[6pt] \sigma &= \frac{n}{n+1} + \frac{2(\tau^2 - \xi)}{(n+1)\beta_1^2} \\[4pt] \rho &= \frac{\sigma \beta_1}{2} \\[4pt] \delta &= \frac{n^2}{(n^2-1)\tau^2}\, \left(\tau^2 - \frac{\beta_1^2}{2} + \frac{\xi}{n}\right)\end{split}\]

Parameters:

beta1 – Offset parameter for the parallel cut
tsq – Square of $\tau$

Returns:

Tuple $(\rho, \sigma, \delta)$

Examples

>>> calc = EllCalcCoreLegacy(4)
>>> calc.calc_parallel_central_cut_old(0.09, 0.01)
(0.02094183648798086, 0.46537414417735246, 1.082031295477563)

ellalgo.ell_config module

Configuration types for the ellipsoid method.

This module defines the core enumeration and options data classes used throughout the ellipsoid method implementation.

CutStatus: Outcome status of a cutting-plane update
Options: Algorithm control parameters (iterations, tolerance, verbosity)

class ellalgo.ell_config.CutStatus(value)[source]

Bases: Enum

Outcome status of an ellipsoid update operation.

Returned by update methods to indicate whether the cut was applied successfully, or why it failed.

Success: Cut was applied successfully; ellipsoid was updated.

NoSoln: Cut is infeasible (no solution exists in the remaining region).

NoEffect: Cut had no effect on the ellipsoid (e.g., numerical degeneracy).

Unknown: Fallback status for unclassified outcomes.

NoEffect = 2

NoSoln = 1

Success = 0

Unknown = 3

class ellalgo.ell_config.Options(max_iters: int = 2000, tolerance: float = 1e-20, verbose: bool = False)[source]

Bases: object

Control parameters for cutting-plane algorithms.

max_iters

Maximum number of iterations before giving up.

Type:: int

tolerance

Convergence threshold; algorithm stops when tsq < tolerance.

Type:: float

verbose

If True, print progress information during execution.

Type:: bool

max_iters: int = 2000

tolerance: float = 1e-20

verbose: bool = False

class ellalgo.ell_config.SolverStatus(value)[source]

Bases: Enum

Termination status of a cutting-plane / binary-search solve.

Success: A solution (or converged bracket) was produced.

Infeasible: The search space was exhausted; no solution exists.

MaxIters: The iteration cap was reached before terminating.

Infeasible = 1

MaxIters = 2

Success = 0

ellalgo.ell_stable module

Numerically stable ellipsoid implementation using LDL^T factorization.

The EllStable class implements the ellipsoid method using a square-root-free Cholesky (LDL^T) decomposition of the shape matrix. This approach avoids explicit matrix inversion and provides better numerical stability, especially for ill-conditioned problems.

Key differences from Ell:

Stores the LDL^T factors of the shape matrix directly
Uses forward/backward substitution instead of matrix-vector products
Implements rank-one updates for the LDL^T factors

See EllBase for the shared public API.

class ellalgo.ell_stable.EllStable(val: float | ndarray, x_center: ndarray)[source]

Bases: EllBase[ndarray]

Numerically stable ellipsoid search space using LDL^T factorization.

This class stores the ellipsoid’s shape matrix in LDL^T factored form and performs rank-one updates directly on the factors, avoiding the need for explicit matrix inversion. This provides better numerical stability for ill-conditioned problems.

Examples

>>> import numpy as np
>>> from ellalgo.ell_stable import EllStable
>>> ell = EllStable(1.0, np.array([0.0, 0.0]))
>>> ell.xc()
array([0., 0.])
>>> ell.tsq()
0.0

ellalgo.ell_typing module

Type definitions, abstract base classes, and type aliases for the ellipsoid method.

This module provides:

ArrayType: A generic TypeVar bound to numpy.ndarray for type-safe array operations
Cut-related type aliases (SingleCut, ParallelCut, CutChoice, Cut, Num)
Constraint: Abstract scalar constraint scanned by multi-constraint oracles
Abstract oracle interfaces defining the contract between cutting-plane algorithms and problem-specific feasibility/optimization logic
SearchSpace: Abstract interface for ellipsoidal search spaces

Cut is deliberately a plain (gradient, beta) tuple rather than a value object: it mirrors the POD cut representation used by the sibling C++ (ellalgo-cpp) and Rust (ellalgo-rs) ports, keeping the three implementations structurally aligned across the hot cutting-plane loop.

class ellalgo.ell_typing.Constraint[source]

Bases: Generic[ArrayType]

A scalar constraint scanned by multi-constraint oracles.

A constraint reports a positive value when violated and supplies the (sub)gradient of the violating constraint. Oracles such as ProfitOracle scan a list of these in round-robin order and return the first violation as a cut.

abstractmethod gradient(gamma: float) → ArrayType[source]: Return the (sub)gradient of this constraint at the current point.

abstractmethod violation(x: ArrayType, gamma: float) → float | None[source]: Return the violation amount (> 0 when violated, else <= 0).

class ellalgo.ell_typing.OracleBS[source]

Bases: ABC

Binary search oracle for monotonic objectives.

Implement assess_bs to test feasibility at a given parameter value, enabling binary search over the parameter space.

abstractmethod assess_bs(gamma: Any) → bool[source]

Test feasibility at the given parameter value.

Parameters:: gamma – Parameter value to test.
Returns:: True if feasible, False otherwise.

class ellalgo.ell_typing.OracleFeas[source]

Bases: Generic[ArrayType]

Feasibility oracle with optional gamma update.

Implement assess_feas to check feasibility. Override update() if the oracle needs to respond to gamma changes (used by BSearchAdaptor).

abstractmethod assess_feas(x_center: ArrayType) → Tuple[ArrayType, float | Tuple[float, float | None] | List[float]] | None[source]

update(gamma: Any) → None[source]: Default no-op. Override for gamma-sensitive oracles.

class ellalgo.ell_typing.OracleOptim[source]

Bases: Generic[ArrayType]

Optimization oracle for convex optimization problems.

Implement assess_optim to assess optimality at a candidate point and optionally return an improved objective value.

abstractmethod assess_optim(x_center: ArrayType, gamma: Any) → Tuple[Tuple[ArrayType, float | Tuple[float, float | None] | List[float]], float | None][source]

Assess optimality of candidate solution x_center at level gamma.

Parameters:

x_center – Current center point of the search space.
gamma – Current best objective value.

Returns:

A tuple (cut, gamma_new) where cut is a separating hyperplane, and gamma_new is an improved objective value (or None if not improved).

class ellalgo.ell_typing.OracleOptimQ[source]

Bases: Generic[ArrayType]

Optimization oracle for discrete/quantized convex optimization.

Implement assess_optim_q to handle quantized solutions with a retry mechanism for discrete feasibility checks.

abstractmethod assess_optim_q(x_center: ArrayType, gamma: Any, retry: bool) → Tuple[Tuple[ArrayType, float | Tuple[float, float | None] | List[float]], ArrayType, float | None, bool][source]

Assess optimality with quantized/rounded solutions.

Parameters:

x_center – Current continuous center point.
gamma – Current best objective value.
retry – Whether this is a retry with a rounded discrete solution.

Returns:

cut: Separating hyperplane
x_q: Evaluation point (continuous or rounded)
gamma_new: Improved objective or None
more_alt: Whether alternative cuts remain available

Return type:

Tuple of (cut, x_q, gamma_new, more_alt) where

class ellalgo.ell_typing.SearchSpace(val: float | ArrayType, x_center: ArrayType)[source]

Bases: Generic[ArrayType]

Search space for cutting-plane methods.

Unified interface that replaces SearchSpace, SearchSpaceQ, and SearchSpace2. - update_q() defaults to update_bias_cut; override for custom quantized behavior. - set_xc() defaults to no-op; override to allow external center updates.

clone() → SearchSpace[ArrayType][source]

Return an independent copy of this search space (Prototype).

Drivers that need a scratch search space (e.g. BSearchAdaptor) call this instead of hard-coding copy.deepcopy. Subclasses may override with a cheaper copy.

set_xc(x_center: ArrayType) → None[source]: Default no-op. Override to allow external center updates.

abstractmethod tsq() → float[source]

abstractmethod update_bias_cut(cut: Tuple[ArrayType, float | Tuple[float, float | None] | List[float]]) → CutStatus[source]

abstractmethod update_central_cut(cut: Tuple[ArrayType, float | Tuple[float, float | None] | List[float]]) → CutStatus[source]

update_q(cut: Tuple[ArrayType, float | Tuple[float, float | None] | List[float]]) → CutStatus[source]: Quantized update. Default delegates to update_bias_cut.

abstractmethod xc() → ArrayType[source]

ellalgo.lmi_problem module

LMI problem facade: owns data and drives the cutting-plane loop.

The LMIProblem class bundles the LMI coefficient matrices with a lazily created oracle and drives the cutting-plane feasibility method, hiding the 3-step recipe (build oracle -> build search space -> call driver) behind a single call.

class ellalgo.lmi_problem.LMIProblem(mat_f: ~typing.List[~numpy.ndarray], mat_b: ~numpy.ndarray, space_factory: ~typing.Callable[[...], ~ellalgo.ell_typing.SearchSpace] = <class 'ellalgo.ell_stable.EllStable'>)[source]

Bases: object

LMI feasibility problem facade.

Owns the LMI data (mat_f and the constant term mat_b) and the lazily-created LMIOracle, then drives the cutting-plane method through the standard cutting_plane_feas driver.

The LMI feasibility problem is:

find x s.t. B − Σₖ Fₖ xₖ ⪰ 0 (positive semidefinite)

Parameters:

mat_f – List of symmetric coefficient matrices [F₁, F₂, …, Fₙ].
mat_b – Constant matrix B defining the LMI constraint.
space_factory – Callable building the ellipsoidal search space from (val, x_center). Defaults to EllStable.

solve_feas(val: float | ndarray, x_center: ndarray, options: Options | None = None) → Tuple[ndarray | None, int][source]

Solve the LMI feasibility problem.

Builds a search space via the injected factory and runs the cutting-plane feasibility method.

Parameters:

val – Either a scalar (kappa) or per-axis values for the initial ellipsoid.
x_center – Initial center point.
options – Algorithm control parameters.

Returns:

Tuple (solution x, number of iterations). The solution is None if no feasible point was found.

Examples

>>> import numpy as np
>>> F1 = np.array([[1.0, 0.0], [0.0, 1.0]])
>>> F2 = np.array([[0.0, 1.0], [1.0, 0.0]])
>>> B = np.array([[2.0, 0.0], [0.0, 2.0]])
>>> problem = LMIProblem([F1, F2], B)
>>> x, niter = problem.solve_feas(10.0, np.zeros(2))
>>> x is not None
True

ellalgo.round_robin module

Round-robin index helper for cyclic constraint scanning.

Extracts the repeated idx += 1; if idx == N: idx = 0 idiom into a small stateful helper (used by LowpassOracle and ProfitOracle).

class ellalgo.round_robin.RoundRobin(n: int, lo: int = 0, hi: int | None = None, start: int | None = None)[source]

Bases: object

Round-robin index generator over a half-open range [lo, hi).

Successive calls to next() yield lo, lo+1, …, hi-1, lo, … Used to scan constraints cyclically.

Parameters:

n – Upper bound (exclusive); range is [0, n).
lo – Lower bound (inclusive). Defaults to 0.
hi – Upper bound (exclusive). If omitted, equals n.
start – Initial cursor position; the first next() returns start + 1 wrapped into [lo, hi). Defaults to lo - 1, so the first call returns lo.

Examples

>>> rr = RoundRobin(3)
>>> [rr.next() for _ in range(5)]
[0, 1, 2, 0, 1]
>>> rr2 = RoundRobin(4, lo=1)
>>> [rr2.next() for _ in range(4)]
[1, 2, 3, 1]

next() → int[source]: Advance to the next index and return it.

peek_next() → int[source]

Return the index the next next() would yield, without advancing.

Examples

>>> rr = RoundRobin(3)
>>> rr.peek_next()
0
>>> rr.next()
0
>>> rr.peek_next()
1

seek(idx: int) → None[source]

Set the cursor to idx so the next next() yields idx + 1.

Used to resume a scan right after the point at idx.

Examples

>>> rr = RoundRobin(4)
>>> rr.seek(2)
>>> [rr.next() for _ in range(3)]
[3, 0, 1]