competitive::data_structure::binary_search_tree::split

Struct Split3

pub struct Split3<'a, Spec>where
    Spec: BstSpec,{
    left: Option<BstRoot<Spec>>,
    mid: Option<BstRoot<Spec>>,
    right: Option<BstRoot<Spec>>,
    root: &'a mut Option<BstRoot<Spec>>,
}

Fields§

§left: Option<BstRoot<Spec>>§mid: Option<BstRoot<Spec>>§right: Option<BstRoot<Spec>>§root: &'a mut Option<BstRoot<Spec>>

Implementations§

Source §

impl<'a, Spec> Split3<'a, Spec>
where Spec: BstSpec,

Source

pub fn new<Seek1, Seek2>( node: &'a mut Option<BstRoot<Spec>>, start: Bound<Seek1>, end: Bound<Seek2>, ) -> Self
where Seek1: BstSeeker<Spec = Spec>, Seek2: BstSeeker<Spec = Spec>,

Examples found in repository ?

crates/competitive/src/data_structure/binary_search_tree/split.rs (line 159)

142    pub fn seek_by_key<K, Q, R>(node: &'a mut Option<BstRoot<Spec>>, range: R) -> Self
143    where
144        Spec: BstSpec<Data: BstDataAccess<data::marker::Key, Value = K>>,
145        K: Borrow<Q>,
146        Q: Ord + ?Sized,
147        R: RangeBounds<Q>,
148    {
149        let start = match range.start_bound() {
150            Bound::Included(key) => Bound::Included(SeekByKey::new(key)),
151            Bound::Excluded(key) => Bound::Excluded(SeekByKey::new(key)),
152            Bound::Unbounded => Bound::Unbounded,
153        };
154        let end = match range.end_bound() {
155            Bound::Included(key) => Bound::Included(SeekByKey::new(key)),
156            Bound::Excluded(key) => Bound::Excluded(SeekByKey::new(key)),
157            Bound::Unbounded => Bound::Unbounded,
158        };
159        Self::new(node, start, end)
160    }
161
162    pub fn seek_by_size<R>(node: &'a mut Option<BstRoot<Spec>>, range: R) -> Self
163    where
164        Spec: BstSpec<Data: BstDataAccess<data::marker::Size, Value = usize>>,
165        R: RangeBounds<usize>,
166    {
167        let start = match range.start_bound() {
168            Bound::Included(&index) => Bound::Included(SeekBySize::new(index)),
169            Bound::Excluded(&index) => Bound::Excluded(SeekBySize::new(index)),
170            Bound::Unbounded => Bound::Unbounded,
171        };
172        let end = match range.end_bound() {
173            Bound::Included(&index) => Bound::Included(SeekBySize::new(index)),
174            Bound::Excluded(&index) => Bound::Excluded(SeekBySize::new(index)),
175            Bound::Unbounded => Bound::Unbounded,
176        };
177        Self::new(node, start, end)
178    }

Source

pub fn left(&self) -> Option<BstImmutRef<'_, Spec>>

Source

pub fn mid(&self) -> Option<BstImmutRef<'_, Spec>>

Examples found in repository ?

crates/competitive/src/data_structure/treap.rs (line 474)

473    pub fn fold(&self) -> L::Agg {
474        if let Some(node) = self.split3.mid() {
475            node.reborrow().into_data().value.agg.clone()
476        } else {
477            L::agg_unit()
478        }
479    }

Source

pub fn right(&self) -> Option<BstImmutRef<'_, Spec>>

Source

pub fn left_datamut(&mut self) -> Option<BstDataMutRef<'_, Spec>>

Source

pub fn mid_datamut(&mut self) -> Option<BstDataMutRef<'_, Spec>>

Examples found in repository ?

crates/competitive/src/data_structure/treap.rs (line 482)

481    pub fn update_key(&mut self, act: M::Act) {
482        if let Some(node) = self.split3.mid_datamut() {
483            MonoidActElement::<M>::update_act(node, &act);
484            self.key_updated = true;
485        }
486    }
487
488    pub fn update_value(&mut self, act: L::Act) {
489        if let Some(node) = self.split3.mid_datamut() {
490            LazyMapElement::<L>::update_act(node, &act);
491        }
492    }

Source

pub fn right_datamut(&mut self) -> Option<BstDataMutRef<'_, Spec>>

Source

pub fn manually_merge<F>(&mut self, f: F)
where F: FnMut(Option<BstRoot<Spec>>, Option<BstRoot<Spec>>) -> Option<BstRoot<Spec>>,

Examples found in repository ?

crates/competitive/src/data_structure/treap.rs (line 502)

500    fn drop(&mut self) {
501        if self.key_updated {
502            self.split3.manually_merge(TreapSpec::merge_ordered);
503        }
504    }

Source

pub fn seek_by_key<K, Q, R>( node: &'a mut Option<BstRoot<Spec>>, range: R, ) -> Self
where Spec: BstSpec<Data: BstDataAccess<Key, Value = K>>, K: Borrow<Q>, Q: Ord + ?Sized, R: RangeBounds<Q>,

Examples found in repository ?

crates/competitive/src/data_structure/treap.rs (line 409)

403    pub fn range_by_key<Q, R>(&mut self, range: R) -> TreapSplit3<'_, M, L>
404    where
405        M: MonoidAct<Key: Borrow<Q>>,
406        Q: Ord + ?Sized,
407        R: RangeBounds<Q>,
408    {
409        let split3 = Split3::seek_by_key(&mut self.root, range);
410        TreapSplit3 {
411            split3,
412            key_updated: false,
413        }
414    }