Struct LiChaoTree 

pub struct LiChaoTree<X, L> {
    range: Range<X>,
    nodes: Vec<LiChaoNode<X, L>>,
}

Fields

range: Range<X>

nodes: Vec<LiChaoNode<X, L>>

Implementations

impl<X, L> LiChaoTree<X, L>

where X: IntBase, L: LiChaoLine<X>,

pub fn new(range: Range<X>) -> Self

fn push_node(&mut self, segment: LiChaoSegment<X, L>) -> u32

Examples found in repository

crates/competitive/src/data_structure/li_chao_tree.rs (line 207)

    fn add_segment_at(
        &mut self,
        mut index: u32,
        mut segment: LiChaoSegment<X, L>,
        mut left: X,
        mut right: X,
    ) {
        loop {
            let last = right - X::one();
            let middle = if left == last {
                left
            } else {
                left.midpoint(last).min(last - X::one())
            };
            let split = middle + X::one();
            if self.nodes[index as usize].segment.covers(left, right) && segment.covers(left, right)
            {
                let candidate_left = segment.line.evaluate(left);
                let candidate_right = segment.line.evaluate(last);
                let child = match place_line(
                    &mut self.nodes[index as usize].segment.line,
                    &mut segment.line,
                    left,
                    middle,
                    last,
                    candidate_left,
                    candidate_right,
                ) {
                    None => return,
                    Some((Branch::Left, _, _)) => {
                        right = split;
                        segment.range.end = right;
                        0
                    }
                    Some((Branch::Right, _, _)) => {
                        left = split;
                        segment.range.start = left;
                        1
                    }
                };
                let next = self.nodes[index as usize].children[child];
                if next == !0 {
                    let next = self.push_node(segment);
                    self.nodes[index as usize].children[child] = next;
                    return;
                }
                index = next;
                continue;
            }
            let segment_right = segment.range.end - X::one();
            if self.nodes[index as usize]
                .segment
                .evaluate(segment.range.start)
                <= segment.line.evaluate(segment.range.start)
                && self.nodes[index as usize].segment.evaluate(segment_right)
                    <= segment.line.evaluate(segment_right)
            {
                return;
            }
            let current = &self.nodes[index as usize].segment;
            let current_left = current.range.start;
            let current_right = current.range.end - X::one();
            if current.line.evaluate(current_left) >= segment.evaluate(current_left)
                && current.line.evaluate(current_right) >= segment.evaluate(current_right)
            {
                self.nodes[index as usize].segment = segment;
                return;
            }
            if segment.covers(left, right) {
                swap(&mut self.nodes[index as usize].segment, &mut segment);
            }
            let child;
            if segment.range.end <= split {
                child = 0;
                right = split;
            } else if middle < segment.range.start {
                child = 1;
                left = split;
            } else {
                let right_segment = LiChaoSegment {
                    range: split..segment.range.end,
                    line: segment.line,
                };
                segment.range.end = split;
                let next = self.nodes[index as usize].children[0];
                if next == !0 {
                    let next = self.push_node(segment);
                    self.nodes[index as usize].children[0] = next;
                } else {
                    self.add_segment_at(next, segment, left, split);
                }
                let next = self.nodes[index as usize].children[1];
                if next == !0 {
                    let next = self.push_node(right_segment);
                    self.nodes[index as usize].children[1] = next;
                } else {
                    self.add_segment_at(next, right_segment, split, right);
                }
                return;
            }
            let next = self.nodes[index as usize].children[child];
            if next == !0 {
                let next = self.push_node(segment);
                self.nodes[index as usize].children[child] = next;
                return;
            }
            index = next;
        }
    }

pub fn add_line(&mut self, line: L)

pub fn add_segment(&mut self, range: Range<X>, line: L)

fn add_segment_at( &mut self, index: u32, segment: LiChaoSegment<X, L>, left: X, right: X, )

Examples found in repository

crates/competitive/src/data_structure/li_chao_tree.rs (lines 142-150)

    pub fn add_line(&mut self, line: L) {
        self.add_segment_at(
            0,
            LiChaoSegment {
                range: self.range.clone(),
                line,
            },
            self.range.start,
            self.range.end,
        );
    }

    pub fn add_segment(&mut self, range: Range<X>, line: L) {
        assert!(self.range.start <= range.start && range.end <= self.range.end);
        if range.start < range.end {
            self.add_segment_at(
                0,
                LiChaoSegment { range, line },
                self.range.start,
                self.range.end,
            );
        }
    }

    fn add_segment_at(
        &mut self,
        mut index: u32,
        mut segment: LiChaoSegment<X, L>,
        mut left: X,
        mut right: X,
    ) {
        loop {
            let last = right - X::one();
            let middle = if left == last {
                left
            } else {
                left.midpoint(last).min(last - X::one())
            };
            let split = middle + X::one();
            if self.nodes[index as usize].segment.covers(left, right) && segment.covers(left, right)
            {
                let candidate_left = segment.line.evaluate(left);
                let candidate_right = segment.line.evaluate(last);
                let child = match place_line(
                    &mut self.nodes[index as usize].segment.line,
                    &mut segment.line,
                    left,
                    middle,
                    last,
                    candidate_left,
                    candidate_right,
                ) {
                    None => return,
                    Some((Branch::Left, _, _)) => {
                        right = split;
                        segment.range.end = right;
                        0
                    }
                    Some((Branch::Right, _, _)) => {
                        left = split;
                        segment.range.start = left;
                        1
                    }
                };
                let next = self.nodes[index as usize].children[child];
                if next == !0 {
                    let next = self.push_node(segment);
                    self.nodes[index as usize].children[child] = next;
                    return;
                }
                index = next;
                continue;
            }
            let segment_right = segment.range.end - X::one();
            if self.nodes[index as usize]
                .segment
                .evaluate(segment.range.start)
                <= segment.line.evaluate(segment.range.start)
                && self.nodes[index as usize].segment.evaluate(segment_right)
                    <= segment.line.evaluate(segment_right)
            {
                return;
            }
            let current = &self.nodes[index as usize].segment;
            let current_left = current.range.start;
            let current_right = current.range.end - X::one();
            if current.line.evaluate(current_left) >= segment.evaluate(current_left)
                && current.line.evaluate(current_right) >= segment.evaluate(current_right)
            {
                self.nodes[index as usize].segment = segment;
                return;
            }
            if segment.covers(left, right) {
                swap(&mut self.nodes[index as usize].segment, &mut segment);
            }
            let child;
            if segment.range.end <= split {
                child = 0;
                right = split;
            } else if middle < segment.range.start {
                child = 1;
                left = split;
            } else {
                let right_segment = LiChaoSegment {
                    range: split..segment.range.end,
                    line: segment.line,
                };
                segment.range.end = split;
                let next = self.nodes[index as usize].children[0];
                if next == !0 {
                    let next = self.push_node(segment);
                    self.nodes[index as usize].children[0] = next;
                } else {
                    self.add_segment_at(next, segment, left, split);
                }
                let next = self.nodes[index as usize].children[1];
                if next == !0 {
                    let next = self.push_node(right_segment);
                    self.nodes[index as usize].children[1] = next;
                } else {
                    self.add_segment_at(next, right_segment, split, right);
                }
                return;
            }
            let next = self.nodes[index as usize].children[child];
            if next == !0 {
                let next = self.push_node(segment);
                self.nodes[index as usize].children[child] = next;
                return;
            }
            index = next;
        }
    }

pub fn query_min(&self, x: X) -> Option<L::Output>

Trait Implementations

impl<X: Clone, L: Clone> Clone for LiChaoTree<X, L>

fn clone(&self) -> Self

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<X: Debug, L: Debug> Debug for LiChaoTree<X, L>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.