slope
The slope module.
Generated from spec/std/slope.cp by cpl doc --format json.
Concave
pub struct Concave(start: Int, base: Int)O(log n) expected per slope operation, for n slopes.
A concave function on the integers lo..=hi: its value at lo and its
slopes in falling order. Law: every operation keeps it concave.
Concave.point
fn point(d: Int) -> ConcaveThe function defined on the single point d, with f(d) = 0.
- cost: O(1)
- traps: never
Examples:
Concave.point(3).at(3) == 0
Concave.flat
fn flat(r: Range<Int>) -> ConcaveThe function that is 0 on every point of r; its domain is r, so lo is the first point of
r and hi the last.
- cost: O(|r| log |r|) expected
- empty: traps
- traps: when
ris empty
Examples:
let f = Concave.flat(2..5); f.lo == 2 and f.hi == 4var f = Concave.flat(0..=1); f.max() == 0
Concave.reserve
fn reserve(mut self, n: Int)Make room for n slopes in total, so later operations do not regrow the storage. Changes
no value.
- cost: O(n)
- traps: when
n < 0
Examples:
var f = Concave.flat(0..=3); f.reserve(100); f.at(2) == 0
Concave.lo
fn lo(self) -> IntThe first point of the domain.
- cost: O(1)
- traps: never
Examples:
var f = Concave.flat(0..=3); f.shift(-2); f.lo == -2
Concave.hi
fn hi(self) -> IntThe last point of the domain.
- cost: O(1)
- traps: never
Examples:
var f = Concave.flat(0..=3); f.max_convolve(Concave.flat(0..=2)); f.hi == 5
Concave.max_convolve
fn max_convolve(mut self, g: Concave)Replace f with c => max over a + b == c of f(a) + g(b). The domain becomes
lo + g.lo ..= hi + g.hi and the two slope multisets merge, so the result stays concave.
Pass the smaller function as g: the cost is in its size.
- cost: O(|g| log n) expected, for
|g|slopes ing - ties: only the value is kept; which point attains it does not matter
- traps: never
Examples:
var f = Concave.point(0); f.add_const(3); f.max_convolve(Concave.flat(0..=2)); f.hi == 2 and f.at(1) == 3var f = Concave.flat(0..=2); f.add_abs(1); var g = Concave.flat(0..=1); g.add_linear(-5); f.max_convolve(g); f.at(3) == -6
Concave.add_quadratic
fn add_quadratic(mut self, q: Int -> Int)f(c) += q(c) for a quadratic q with leading coefficient at most 0, so f stays concave.
q is called at most four times: three points fix it and a fourth checks that it is
quadratic.
- cost: O(1)
- traps: when
qis not a quadratic polynomial on the points read, or its leading coefficient is positive
Examples:
var f = Concave.flat(0..=3); f.add_quadratic(x => -x * x + 1); f.at(2) == -3
Concave.at
fn at(mut self, c: Int) -> IntThe value f(c).
- cost: O(log n) expected (O(c - lo + log n) in the current implementation)
- traps: when
cis outsidelo..=hi
Examples:
var f = Concave.flat(0..=4); f.add_abs(1); f.at(4) == -3
Concave.max
fn max(mut self) -> IntThe largest value of f over its domain.
- cost: O(log n) expected (O(n) in the current implementation)
- ties: only the value is kept; which point attains it does not matter
- traps: never
Examples:
var f = Concave.flat(0..=4); f.add_abs(1); f.add_const(5); f.max() == 5
Concave.add_left
fn add_left(mut self, a: Int)Add min(0, x - a): a hinge with slope 1 left of a and flat from a on.
- cost: O(log n) expected
- traps: never
Examples:
var f = Concave.flat(0..=4); f.add_left(2); f.at(0) == -2 and f.at(3) == 0
Concave.add_right
fn add_right(mut self, a: Int)Add min(0, a - x): flat up to a and slope -1 right of it.
- cost: O(log n) expected
- traps: never
Examples:
var f = Concave.flat(0..=4); f.add_right(2); f.at(4) == -2 and f.at(1) == 0
Concave.add_abs
fn add_abs(mut self, a: Int)Add -|x - a|; add_left(a) and add_right(a) together.
- cost: O(log n) expected
- traps: never
Examples:
var f = Concave.flat(0..=4); f.add_abs(1); f.at(0) == -1 and f.at(4) == -3
Concave.add_const
fn add_const(mut self, c: Int)Add the constant c everywhere.
- cost: O(1)
- traps: never
Examples:
var f = Concave.point(2); f.add_const(-4); f.at(2) == -4
Concave.add_linear
fn add_linear(mut self, k: Int)Add k * x, applied lazily to every slope.
- cost: O(1)
- traps: never
Examples:
var f = Concave.flat(0..=4); f.add_linear(2); f.at(3) == 6 and f.at(0) == 0
Concave.prefix_max
fn prefix_max(mut self)Replace f(x) with the largest f(y) over y <= x in the domain; the domain is unchanged
and every falling slope becomes 0.
- cost: O(log n) expected (O(n log n) in the current implementation)
- ties: only the value is kept; which point attains it does not matter
- traps: never
Examples:
var f = Concave.flat(0..=4); f.add_abs(2); f.prefix_max(); f.at(0) == -2 and f.at(4) == 0
Concave.suffix_max
fn suffix_max(mut self)Replace f(x) with the largest f(y) over y >= x in the domain; the domain is unchanged
and every rising slope becomes 0.
- cost: O(log n) expected (O(n log n) in the current implementation)
- ties: only the value is kept; which point attains it does not matter
- traps: never
Examples:
var f = Concave.flat(0..=4); f.add_abs(2); f.suffix_max(); f.at(0) == 0 and f.at(4) == -2
Concave.shift
fn shift(mut self, d: Int)Move the function right by d: the new f(x) is the old f(x - d), and lo and hi both
grow by d.
- cost: O(1)
- traps: never
Examples:
var f = Concave.point(0); f.add_const(7); f.shift(5); f.lo == 5 and f.at(5) == 7
Concave.slide_max
fn slide_max(mut self, a: Int, b: Int)Replace f(x) with the largest old f(y) over x - b <= y <= x - a; the domain becomes
lo + a ..= hi + b. The same as max_convolve(Concave.flat(a..=b)).
- cost: O(b - a + log n) expected
- ties: only the value is kept; which point attains it does not matter
- traps: when
a > b
Examples:
var f = Concave.point(0); f.add_const(1); f.slide_max(-1, 2); f.lo == -1 and f.hi == 2 and f.at(2) == 1
Concave.argmax
fn argmax(mut self) -> Range<Int>The points where f reaches its maximum, as a half-open range; by concavity they are
contiguous.
- cost: O(log n) expected (O(n) in the current implementation)
- order: ascending points
- ties: every maximizing point is included
- traps: never
Examples:
var f = Concave.flat(0..=4); f.add_abs(2); f.argmax() == 2..3Concave.flat(0..=4).argmax() == 0..5
Concave.count_at_least
fn count_at_least(self, v: Int) -> IntConvex
pub struct Convex(neg: Concave)O(log n) expected per slope operation, for n slopes.
A convex function on the integers lo..=hi, the negation of a Concave:
the same operations with min for max.
Convex.point
fn point(d: Int) -> ConvexThe function defined on the single point d, with f(d) = 0.
- cost: O(1)
- traps: never
Examples:
Convex.point(3).at(3) == 0
Convex.flat
fn flat(r: Range<Int>) -> ConvexThe function that is 0 on every point of r; its domain is r.
- cost: O(|r| log |r|) expected
- empty: traps
- traps: when
ris empty
Examples:
let f = Convex.flat(2..5); f.lo == 2 and f.hi == 4
Convex.lo
fn lo(self) -> IntThe first point of the domain.
- cost: O(1)
- traps: never
Examples:
var f = Convex.flat(0..=3); f.shift(-2); f.lo == -2
Convex.hi
fn hi(self) -> IntThe last point of the domain.
- cost: O(1)
- traps: never
Examples:
var f = Convex.flat(0..=3); f.min_convolve(Convex.flat(0..=2)); f.hi == 5
Convex.min_convolve
fn min_convolve(mut self, g: Convex)Replace f with c => min over a + b == c of f(a) + g(b). The domain becomes
lo + g.lo ..= hi + g.hi and the slope multisets merge. Pass the smaller function as g.
- cost: O(|g| log n) expected, for
|g|slopes ing - ties: only the value is kept; which point attains it does not matter
- traps: never
Examples:
var f = Convex.point(0); f.add_const(3); f.min_convolve(Convex.flat(0..=2)); f.hi == 2 and f.at(1) == 3
Convex.add_quadratic
fn add_quadratic(mut self, q: Int -> Int)f(c) += q(c) for a quadratic q with leading coefficient at least 0, so f stays convex;
q is called at most four times, as in Concave.add_quadratic.
- cost: O(1)
- traps: when
qis not a quadratic polynomial on the points read, or its leading coefficient is negative
Examples:
var f = Convex.flat(0..=3); f.add_quadratic(x => x * x); f.at(3) == 9
Convex.at
fn at(mut self, c: Int) -> IntThe value f(c).
- cost: O(log n) expected (O(c - lo + log n) in the current implementation)
- traps: when
cis outsidelo..=hi
Examples:
var f = Convex.flat(0..=4); f.add_abs(1); f.at(4) == 3
Convex.min
fn min(mut self) -> IntThe smallest value of f over its domain.
- cost: O(log n) expected (O(n) in the current implementation)
- ties: only the value is kept; which point attains it does not matter
- traps: never
Examples:
var f = Convex.flat(0..=4); f.add_abs(1); f.add_const(5); f.min() == 5
Convex.add_left
fn add_left(mut self, a: Int)Add max(0, a - x): slope -1 left of a and flat from a on.
- cost: O(log n) expected
- traps: never
Examples:
var f = Convex.flat(0..=4); f.add_left(2); f.at(0) == 2 and f.at(3) == 0
Convex.add_right
fn add_right(mut self, a: Int)Add max(0, x - a): flat up to a and slope 1 right of it.
- cost: O(log n) expected
- traps: never
Examples:
var f = Convex.flat(0..=4); f.add_right(2); f.at(4) == 2 and f.at(1) == 0
Convex.add_abs
fn add_abs(mut self, a: Int)Add |x - a|; add_left(a) and add_right(a) together.
- cost: O(log n) expected
- traps: never
Examples:
var f = Convex.flat(0..=4); f.add_abs(1); f.at(0) == 1 and f.at(4) == 3
Convex.add_const
fn add_const(mut self, c: Int)Add the constant c everywhere.
- cost: O(1)
- traps: never
Examples:
var f = Convex.point(2); f.add_const(-4); f.at(2) == -4
Convex.add_linear
fn add_linear(mut self, k: Int)Add k * x, applied lazily to every slope.
- cost: O(1)
- traps: never
Examples:
var f = Convex.flat(0..=4); f.add_linear(-2); f.at(3) == -6
Convex.prefix_min
fn prefix_min(mut self)Replace f(x) with the smallest f(y) over y <= x in the domain; the domain is unchanged.
- cost: O(log n) expected (O(n log n) in the current implementation)
- ties: only the value is kept; which point attains it does not matter
- traps: never
Examples:
var f = Convex.flat(0..=4); f.add_abs(2); f.prefix_min(); f.at(0) == 2 and f.at(4) == 0
Convex.suffix_min
fn suffix_min(mut self)Replace f(x) with the smallest f(y) over y >= x in the domain; the domain is unchanged.
- cost: O(log n) expected (O(n log n) in the current implementation)
- ties: only the value is kept; which point attains it does not matter
- traps: never
Examples:
var f = Convex.flat(0..=4); f.add_abs(2); f.suffix_min(); f.at(0) == 0 and f.at(4) == 2
Convex.shift
fn shift(mut self, d: Int)Move the function right by d: the new f(x) is the old f(x - d), and lo and hi both
grow by d.
- cost: O(1)
- traps: never
Examples:
var f = Convex.point(0); f.add_const(7); f.shift(5); f.lo == 5 and f.at(5) == 7
Convex.slide_min
fn slide_min(mut self, a: Int, b: Int)Replace f(x) with the smallest old f(y) over x - b <= y <= x - a; the domain becomes
lo + a ..= hi + b. The same as min_convolve(Convex.flat(a..=b)).
- cost: O(b - a + log n) expected
- ties: only the value is kept; which point attains it does not matter
- traps: when
a > b
Examples:
var f = Convex.point(0); f.add_const(1); f.slide_min(-1, 2); f.lo == -1 and f.hi == 2 and f.at(-1) == 1
Convex.argmin
fn argmin(mut self) -> Range<Int>The points where f reaches its minimum, as a half-open range; by convexity they are
contiguous.
- cost: O(log n) expected (O(n) in the current implementation)
- order: ascending points
- ties: every minimizing point is included
- traps: never
Examples:
var f = Convex.flat(0..=4); f.add_abs(2); f.argmin() == 2..3