competitive::data_structure::binary_search_tree::seeker

Struct SeekBySize

pub struct SeekBySize<Spec> {
    index: usize,
    _marker: PhantomData<fn() -> Spec>,
}

Fields§

§index: usize§_marker: PhantomData<fn() -> Spec>

Implementations§

Source §

impl<Spec> SeekBySize<Spec>

Source

pub fn new(index: usize) -> Self

Examples found in repository ?

crates/competitive/src/data_structure/splay_tree.rs (line 201)

200    fn splay_by_size(&mut self, index: usize) -> Option<Ordering> {
201        self.splay(SeekBySize::new(index))
202    }

More examples

Hide additional examples

crates/competitive/src/data_structure/implicit_splay_tree.rs (line 301)

297    pub fn get(&mut self, index: usize) -> Option<&T::Key> {
298        if index >= self.length {
299            return None;
300        }
301        self.splay(SeekBySize::new(index));
302        Some(&self.root.as_ref()?.reborrow().into_data().value.key)
303    }
304
305    pub fn modify<F>(&mut self, index: usize, f: F)
306    where
307        F: FnOnce(&T::Key) -> T::Key,
308    {
309        assert!(index < self.length);
310        self.splay(SeekBySize::new(index));
311        let mut root = self.root.as_mut().unwrap().borrow_datamut();
312        ImplicitSplayTreeSpec::top_down(root.reborrow_datamut());
313        {
314            let data = root.data_mut();
315            data.value.key = f(&data.value.key);
316        }
317        ImplicitSplayTreeSpec::bottom_up(root);
318    }
319
320    pub fn insert(&mut self, index: usize, key: T::Key) {
321        assert!(index <= self.length);
322        let mut node = self.node(key);
323        if self.root.is_none() {
324            self.root = Some(node);
325        } else if index == self.length {
326            self.splay(SeekBySize::new(index));
327            unsafe { node.borrow_mut().left_mut().set(self.root.take().unwrap()) };
328            ImplicitSplayTreeSpec::bottom_up(node.borrow_datamut());
329            self.root = Some(node);
330        } else {
331            self.splay(SeekBySize::new(index));
332            let mut root = self.root.take().unwrap();
333            let left = unsafe { root.borrow_mut().left_mut().take() };
334            if let Some(left) = left {
335                unsafe { node.borrow_mut().left_mut().set(left) };
336            }
337            ImplicitSplayTreeSpec::bottom_up(root.borrow_datamut());
338            unsafe { node.borrow_mut().right_mut().set(root) };
339            ImplicitSplayTreeSpec::bottom_up(node.borrow_datamut());
340            self.root = Some(node);
341        }
342        self.length += 1;
343    }
344
345    pub fn remove(&mut self, index: usize) -> Option<T::Key> {
346        if index >= self.length {
347            return None;
348        }
349        self.splay(SeekBySize::new(index));
350        let mut node = self.root.take().unwrap();
351        ImplicitSplayTreeSpec::top_down(node.borrow_datamut());
352        let left = unsafe { node.borrow_mut().left_mut().take() };
353        let right = unsafe { node.borrow_mut().right_mut().take() };
354        self.root = ImplicitSplayTreeSpec::merge(left, right);
355        self.length -= 1;
356        let data = unsafe { node.into_dying().into_data(self.allocator.deref_mut()) };
357        Some(data.value.key)
358    }
359
360    pub fn partition_point_acc<F>(&mut self, left: usize, mut pred: F) -> usize
361    where
362        F: FnMut(&T::Agg) -> bool,
363    {
364        let mut split3 = Split3::seek_by_size(&mut self.root, left..);
365        let front_size = split3
366            .left()
367            .map(|node| node.into_data().size)
368            .unwrap_or_default();
369        let split = split3.split_mid(SeekByAccCond::new(|acc| !pred(acc)), EqualSide::Right);
370        let index = split
371            .left()
372            .map(|node| node.into_data().size)
373            .unwrap_or_default();
374        front_size + index
375    }
376
377    pub fn rpartition_point_acc<F>(&mut self, right: usize, mut pred: F) -> usize
378    where
379        F: FnMut(&T::Agg) -> bool,
380    {
381        let mut split3 = Split3::seek_by_size(&mut self.root, ..right);
382        let split = split3.split_mid(SeekByRaccCond::new(|acc| !pred(acc)), EqualSide::Left);
383        split
384            .left()
385            .map(|node| node.into_data().size)
386            .unwrap_or_default()
387    }
388
389    pub fn rotate_left(&mut self, mid: usize) {
390        assert!(mid <= self.length);
391        if mid == 0 || mid == self.length {
392            return;
393        }
394        let (left, right) =
395            ImplicitSplayTreeSpec::split(self.root.take(), SeekBySize::new(mid), EqualSide::Right);
396        self.root = ImplicitSplayTreeSpec::merge(right, left);
397    }

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

173    pub fn seek_by_size<R>(node: &'a mut Option<BstRoot<Spec>>, range: R) -> Self
174    where
175        Spec: BstSpec<Data: BstDataAccess<data::marker::Size, Value = usize>>,
176        R: RangeBounds<usize>,
177    {
178        let start = match range.start_bound() {
179            Bound::Included(&index) => Bound::Included(SeekBySize::new(index)),
180            Bound::Excluded(&index) => Bound::Excluded(SeekBySize::new(index)),
181            Bound::Unbounded => Bound::Unbounded,
182        };
183        let end = match range.end_bound() {
184            Bound::Included(&index) => Bound::Included(SeekBySize::new(index)),
185            Bound::Excluded(&index) => Bound::Excluded(SeekBySize::new(index)),
186            Bound::Unbounded => Bound::Unbounded,
187        };
188        Self::new(node, start, end)
189    }

crates/competitive/src/data_structure/implicit_treap.rs (line 414)

405    pub fn insert(&mut self, index: usize, x: T::Key) {
406        assert!(index <= self.length);
407        let node = self.node(x);
408        if index == 0 {
409            self.root = ImplicitTreapSpec::<T>::merge(Some(node), self.root.take());
410        } else if index == self.length {
411            self.root = ImplicitTreapSpec::<T>::merge(self.root.take(), Some(node));
412        } else {
413            let mut node = Some(node);
414            let mut split = Split::new(&mut self.root, SeekBySize::new(index), EqualSide::Right);
415            split.manually_merge(|left, right| {
416                ImplicitTreapSpec::<T>::merge(
417                    ImplicitTreapSpec::<T>::merge(left, node.take()),
418                    right,
419                )
420            });
421        }
422        self.length += 1;
423    }
424
425    pub fn remove(&mut self, index: usize) -> Option<T::Key> {
426        if index >= self.length {
427            return None;
428        }
429        let mid;
430        if index == 0 {
431            let (left, right) = ImplicitTreapSpec::<T>::split(
432                self.root.take(),
433                SeekBySize::new(1),
434                EqualSide::Right,
435            );
436            mid = left;
437            self.root = right;
438        } else if index + 1 == self.length {
439            let (left, right) = ImplicitTreapSpec::<T>::split(
440                self.root.take(),
441                SeekBySize::new(index),
442                EqualSide::Right,
443            );
444            mid = right;
445            self.root = left;
446        } else {
447            let (left, rest) = ImplicitTreapSpec::<T>::split(
448                self.root.take(),
449                SeekBySize::new(index),
450                EqualSide::Right,
451            );
452            let (middle, right) =
453                ImplicitTreapSpec::<T>::split(rest, SeekBySize::new(1), EqualSide::Right);
454            mid = middle;
455            self.root = ImplicitTreapSpec::<T>::merge(left, right);
456        }
457        self.length -= 1;
458        let mut node = mid.unwrap();
459        ImplicitTreapSpec::<T>::top_down(node.borrow_datamut());
460        let data = unsafe { node.into_dying().into_data(self.allocator.deref_mut()) };
461        Some(data.value.key)
462    }
463
464    pub fn partition_point_acc<F>(&mut self, left: usize, mut pred: F) -> usize
465    where
466        F: FnMut(&T::Agg) -> bool,
467    {
468        let mut split3 = Split3::seek_by_size(&mut self.root, left..);
469        let front_size = split3
470            .left()
471            .map(|node| node.into_data().size)
472            .unwrap_or_default();
473        let split = split3.split_mid(SeekByAccCond::new(|acc| !pred(acc)), EqualSide::Right);
474        let index = split
475            .left()
476            .map(|node| node.into_data().size)
477            .unwrap_or_default();
478        front_size + index
479    }
480
481    pub fn rpartition_point_acc<F>(&mut self, right: usize, mut pred: F) -> usize
482    where
483        F: FnMut(&T::Agg) -> bool,
484    {
485        let mut split3 = Split3::seek_by_size(&mut self.root, ..right);
486        let split = split3.split_mid(SeekByRaccCond::new(|acc| !pred(acc)), EqualSide::Left);
487        split
488            .left()
489            .map(|node| node.into_data().size)
490            .unwrap_or_default()
491    }
492
493    pub fn rotate_left(&mut self, mid: usize) {
494        assert!(mid <= self.length);
495        if mid == 0 || mid == self.length {
496            return;
497        }
498        let (left, right) =
499            ImplicitTreapSpec::<T>::split(self.root.take(), SeekBySize::new(mid), EqualSide::Right);
500        self.root = ImplicitTreapSpec::<T>::merge(right, left);
501    }