Skip to Content
ReferenceLibrary

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.

Source

Concave.point

fn point(d: Int) -> Concave

The function defined on the single point d, with f(d) = 0.

  • cost: O(1)
  • traps: never

Examples:

  • Concave.point(3).at(3) == 0

Source

Concave.flat

fn flat(r: Range<Int>) -> Concave

The 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 r is empty

Examples:

  • let f = Concave.flat(2..5); f.lo == 2 and f.hi == 4
  • var f = Concave.flat(0..=1); f.max() == 0

Source

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

Source

Concave.lo

fn lo(self) -> Int

The first point of the domain.

  • cost: O(1)
  • traps: never

Examples:

  • var f = Concave.flat(0..=3); f.shift(-2); f.lo == -2

Source

Concave.hi

fn hi(self) -> Int

The 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

Source

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 in g
  • 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) == 3
  • var 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

Source

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 q is 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

Source

Concave.at

fn at(mut self, c: Int) -> Int

The value f(c).

  • cost: O(log n) expected (O(c - lo + log n) in the current implementation)
  • traps: when c is outside lo..=hi

Examples:

  • var f = Concave.flat(0..=4); f.add_abs(1); f.at(4) == -3

Source

Concave.max

fn max(mut self) -> Int

The 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

Source

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

Source

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

Source

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

Source

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

Source

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

Source

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

Source

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

Source

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

Source

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

Source

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..3
  • Concave.flat(0..=4).argmax() == 0..5

Source

Concave.count_at_least

fn count_at_least(self, v: Int) -> Int

Source

Convex

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.

Source

Convex.point

fn point(d: Int) -> Convex

The function defined on the single point d, with f(d) = 0.

  • cost: O(1)
  • traps: never

Examples:

  • Convex.point(3).at(3) == 0

Source

Convex.flat

fn flat(r: Range<Int>) -> Convex

The function that is 0 on every point of r; its domain is r.

  • cost: O(|r| log |r|) expected
  • empty: traps
  • traps: when r is empty

Examples:

  • let f = Convex.flat(2..5); f.lo == 2 and f.hi == 4

Source

Convex.lo

fn lo(self) -> Int

The first point of the domain.

  • cost: O(1)
  • traps: never

Examples:

  • var f = Convex.flat(0..=3); f.shift(-2); f.lo == -2

Source

Convex.hi

fn hi(self) -> Int

The 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

Source

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 in g
  • 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

Source

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 q is 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

Source

Convex.at

fn at(mut self, c: Int) -> Int

The value f(c).

  • cost: O(log n) expected (O(c - lo + log n) in the current implementation)
  • traps: when c is outside lo..=hi

Examples:

  • var f = Convex.flat(0..=4); f.add_abs(1); f.at(4) == 3

Source

Convex.min

fn min(mut self) -> Int

The 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

Source

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

Source

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

Source

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

Source

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

Source

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

Source

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

Source

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

Source

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

Source

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

Source

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

Source

On this page