Struct ConcaveEnvelope 

struct ConcaveEnvelope<'a, T> {
    arbitrary: &'a [T],
    concave: &'a [T],
    leaf_count: usize,
    query_root: usize,
    node_curves: Vec<Option<usize>>,
    result: Vec<T>,
}

Fields

arbitrary: &'a [T]

concave: &'a [T]

leaf_count: usize

query_root: usize

node_curves: Vec<Option<usize>>

result: Vec<T>

Implementations

impl<'a, T> ConcaveEnvelope<'a, T>

where T: Signed,

fn new(arbitrary: &'a [T], concave: &'a [T]) -> Self

Examples found in repository

crates/competitive/src/math/min_plus_convolution/concave.rs (line 205)

pub(super) fn concave_envelope<T>(arbitrary: &[T], concave: &[T]) -> Vec<T>
where
    T: Signed,
{
    if concave.len() == 1 {
        return arbitrary
            .iter()
            .map(|&value| {
                if value.is_maximum() {
                    T::maximum()
                } else {
                    value + concave[0]
                }
            })
            .collect();
    }
    if arbitrary.len() == 1 {
        return if arbitrary[0].is_maximum() {
            vec![T::maximum(); concave.len()]
        } else {
            concave.iter().map(|&value| arbitrary[0] + value).collect()
        };
    }

    ConcaveEnvelope::new(arbitrary, concave).convolve()
}

fn value(&self, curve: usize, output: usize) -> T

Examples found in repository

crates/competitive/src/math/min_plus_convolution/concave.rs (line 55)

    fn query(&mut self, output: usize) {
        let mut best = self.result[output];
        let mut node = (output + self.leaf_count) >> 1;
        while node >= self.query_root {
            if let Some(curve) = self.node_curves[node] {
                best = best.min(self.value(curve, output));
            }
            node >>= 1;
        }
        self.result[output] = best;
    }

    #[inline]
    fn insert_from_left(&mut self, left: usize) {
        let mut right = left + self.concave.len();
        let block = 1_usize << (left ^ right).ilog2();
        right &= !(block - 1);
        let mut depth = bit_width(right - left - 1);
        let mut node = (self.leaf_count + left) >> depth;
        let mut pending = (!self.arbitrary[left].is_maximum()).then_some(left);
        while depth != 0 {
            let Some(curve) = pending else {
                break;
            };
            depth -= 1;
            let middle = ((node << 1 | 1) << depth) - self.leaf_count - 1;
            if middle < left {
                node = node << 1 | 1;
            } else if self.node_curves[node]
                .is_some_and(|old| self.value(old, middle) < self.value(curve, middle))
            {
                node <<= 1;
            } else {
                std::mem::swap(&mut self.node_curves[node], &mut pending);
                node = node << 1 | 1;
            }
        }
        if let Some(curve) = pending {
            let output = node - self.leaf_count;
            self.result[output] = self.result[output].min(self.value(curve, output));
        }
    }

    #[inline]
    fn insert_from_right(&mut self, right: usize) {
        let curve = right - self.concave.len();
        let block = 1_usize << (curve ^ right).ilog2();
        let left = right & !(block - 1);
        if left == right {
            return;
        }
        let mut depth = bit_width(right - left - 1);
        let mut node = (self.leaf_count + left) >> depth;
        let mut pending = (!self.arbitrary[curve].is_maximum()).then_some(curve);
        while depth != 0 {
            let Some(curve) = pending else {
                break;
            };
            depth -= 1;
            let middle = ((node << 1 | 1) << depth) - self.leaf_count;
            if middle >= right {
                node <<= 1;
            } else if self.node_curves[node]
                .is_some_and(|old| self.value(old, middle) < self.value(curve, middle))
            {
                node = node << 1 | 1;
            } else {
                std::mem::swap(&mut self.node_curves[node], &mut pending);
                node <<= 1;
            }
        }
        if let Some(curve) = pending {
            let output = node - self.leaf_count;
            self.result[output] = self.result[output].min(self.value(curve, output));
        }
    }

fn query(&mut self, output: usize)

Examples found in repository

crates/competitive/src/math/min_plus_convolution/concave.rs (line 132)

    fn convolve(mut self) -> Vec<T> {
        // Curve i is valid on [i, i + concave.len()). The two passes insert
        // opposite sides of each validity interval into the segment envelope.
        for left in 0..self.arbitrary.len() {
            self.insert_from_left(left);
            self.query(left);
        }
        for output in self.arbitrary.len()..self.result.len() {
            self.query(output);
        }

        self.node_curves.fill(None);
        let mut right = self.result.len();
        while right >= self.concave.len() {
            self.insert_from_right(right);
            right -= 1;
            self.query(right);
        }
        for output in 0..self.concave.len() {
            self.query(output);
        }
        self.result
    }

fn insert_from_left(&mut self, left: usize)

Examples found in repository

crates/competitive/src/math/min_plus_convolution/concave.rs (line 131)

    fn convolve(mut self) -> Vec<T> {
        // Curve i is valid on [i, i + concave.len()). The two passes insert
        // opposite sides of each validity interval into the segment envelope.
        for left in 0..self.arbitrary.len() {
            self.insert_from_left(left);
            self.query(left);
        }
        for output in self.arbitrary.len()..self.result.len() {
            self.query(output);
        }

        self.node_curves.fill(None);
        let mut right = self.result.len();
        while right >= self.concave.len() {
            self.insert_from_right(right);
            right -= 1;
            self.query(right);
        }
        for output in 0..self.concave.len() {
            self.query(output);
        }
        self.result
    }

fn insert_from_right(&mut self, right: usize)

Examples found in repository

crates/competitive/src/math/min_plus_convolution/concave.rs (line 141)

    fn convolve(mut self) -> Vec<T> {
        // Curve i is valid on [i, i + concave.len()). The two passes insert
        // opposite sides of each validity interval into the segment envelope.
        for left in 0..self.arbitrary.len() {
            self.insert_from_left(left);
            self.query(left);
        }
        for output in self.arbitrary.len()..self.result.len() {
            self.query(output);
        }

        self.node_curves.fill(None);
        let mut right = self.result.len();
        while right >= self.concave.len() {
            self.insert_from_right(right);
            right -= 1;
            self.query(right);
        }
        for output in 0..self.concave.len() {
            self.query(output);
        }
        self.result
    }

fn convolve(self) -> Vec<T>

Examples found in repository

crates/competitive/src/math/min_plus_convolution/concave.rs (line 205)

pub(super) fn concave_envelope<T>(arbitrary: &[T], concave: &[T]) -> Vec<T>
where
    T: Signed,
{
    if concave.len() == 1 {
        return arbitrary
            .iter()
            .map(|&value| {
                if value.is_maximum() {
                    T::maximum()
                } else {
                    value + concave[0]
                }
            })
            .collect();
    }
    if arbitrary.len() == 1 {
        return if arbitrary[0].is_maximum() {
            vec![T::maximum(); concave.len()]
        } else {
            concave.iter().map(|&value| arbitrary[0] + value).collect()
        };
    }

    ConcaveEnvelope::new(arbitrary, concave).convolve()
}