Struct Line 

struct Line<T> {
    a: Slope<T>,
    b: T,
    q: Query<T>,
}

Fields

a: Slope<T>

b: T

q: Query<T>

Implementations

impl<T> Line<T>

fn new(a: T, b: T, q: T) -> Self

Examples found in repository

crates/competitive/src/data_structure/line_set.rs (line 166)

    pub fn insert(&mut self, a: T, b: T) {
        fn f<T>(la: T, lb: T, ra: T, rb: T) -> T
        where
            T: Copy + Ord + Sub<Output = T> + Div<Output = T>,
        {
            debug_assert!(la > ra);
            (rb - lb) / (la - ra)
        }
        let left = self.map.range(..Slope(a)).next_back().cloned();
        let mut right = self.map.range(Slope(a)..).next().cloned();
        match (&left, &right) {
            (_, Some(r)) if a == r.a.0 => {
                if r.b <= b {
                    return;
                }
                self.map.remove(r);
                right = self.map.range(Slope(a)..).next().cloned();
            }
            (Some(l), Some(r)) if f(l.a.0, l.b, a, b) >= f(a, b, r.a.0, r.b) => return,
            _ => {}
        }
        loop {
            let rq = if let Some(r) = right {
                let rq = f(a, b, r.a.0, r.b);
                if rq >= r.q.0 {
                    self.map.remove(&r);
                    right = self.map.range(Slope(a)..).next().cloned();
                    continue;
                }
                rq
            } else {
                Bounded::maximum()
            };
            self.map.insert(Line::new(a, b, rq));
            break;
        }
        if let Some(mut l) = left {
            self.map.remove(&l);
            let mut lq = f(l.a.0, l.b, a, b);
            loop {
                if let Some(ll) = self.map.range(..Slope(a)).next_back().cloned() {
                    self.map.remove(&ll);
                    let llq = f(ll.a.0, ll.b, l.a.0, l.b);
                    if llq >= lq {
                        l = ll;
                        lq = f(l.a.0, l.b, a, b);
                        continue;
                    } else {
                        self.map.insert(Line::new(ll.a.0, ll.b, llq));
                    }
                };
                break;
            }
            self.map.insert(Line::new(l.a.0, l.b, lq));
        }
    }

Trait Implementations

impl<T> Borrow<Query<T>> for Line<T>

fn borrow(&self) -> &Query<T>

Immutably borrows from an owned value.

impl<T> Borrow<Slope<T>> for Line<T>

fn borrow(&self) -> &Slope<T>

Immutably borrows from an owned value.

impl<T: Clone> Clone for Line<T>

fn clone(&self) -> Line<T>

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl<T: Debug> Debug for Line<T>

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

Formats the value using the given formatter.

impl<T: Default> Default for Line<T>

fn default() -> Line<T>

Returns the “default value” for a type.

impl<T> Ord for Line<T>

where T: Ord,

fn cmp(&self, other: &Self) -> Ordering

This method returns an Ordering between self and other.

fn max(self, other: Self) -> Self

where Self: Sized,

Compares and returns the maximum of two values.

fn min(self, other: Self) -> Self

where Self: Sized,

Compares and returns the minimum of two values.

fn clamp(self, min: Self, max: Self) -> Self

where Self: Sized,

Restrict a value to a certain interval.

impl<T> PartialEq for Line<T>

where T: PartialEq,

fn eq(&self, other: &Self) -> bool

Tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl<T> PartialOrd for Line<T>

where T: PartialOrd,

fn partial_cmp(&self, other: &Self) -> Option<Ordering>

This method returns an ordering between self and other values if one exists.

fn lt(&self, other: &Rhs) -> bool

Tests less than (for self and other) and is used by the < operator.

fn le(&self, other: &Rhs) -> bool

Tests less than or equal to (for self and other) and is used by the <= operator.

fn gt(&self, other: &Rhs) -> bool

Tests greater than (for self and other) and is used by the > operator.

fn ge(&self, other: &Rhs) -> bool

Tests greater than or equal to (for self and other) and is used by the >= operator.

impl<T> Eq for Line<T>

where T: Eq,