Struct SeekBySize 

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

Fields

index: usize

_marker: PhantomData<fn() -> (K, V)>

Implementations

impl<K, V> SeekBySize<K, V>

fn new(index: usize) -> Self

Examples found in repository

crates/competitive/src/data_structure/splay_tree/sized_map.rs (line 177)

    fn splay_at(&mut self, index: usize) -> Option<Ordering> {
        self.root.splay_by(SeekBySize::new(index))
    }
    pub fn get_key_value_at(&mut self, index: usize) -> Option<(&K, &V)> {
        if index >= self.length {
            return None;
        }
        self.splay_at(index);
        self.root.root().map(|node| {
            let ((k, v), _) = node.data();
            (k, v)
        })
    }
    pub fn insert(&mut self, key: K, value: V) -> Option<V>
    where
        K: Ord,
    {
        let ord = self.splay_by_key(&key);
        self.length += (ord != Some(Ordering::Equal)) as usize;
        match ord {
            Some(Ordering::Equal) => {
                return Some(replace(
                    &mut (self.root.root_data_mut().unwrap().data_mut().0).1,
                    value,
                ));
            }
            Some(Ordering::Less) => unsafe {
                self.root.insert_left(NodeRef::from_data(
                    ((key, value), 1),
                    self.alloc.deref_mut(),
                ));
            },
            _ => unsafe {
                self.root.insert_right(NodeRef::from_data(
                    ((key, value), 1),
                    self.alloc.deref_mut(),
                ));
            },
        }
        None
    }
    pub fn remove<Q>(&mut self, key: &Q) -> Option<V>
    where
        K: Borrow<Q>,
        Q: Ord + ?Sized,
    {
        if !matches!(self.splay_by_key(key)?, Ordering::Equal) {
            return None;
        }
        self.length -= 1;
        let node = self.root.take_root().unwrap().into_dying();
        unsafe { Some((node.into_data(self.alloc.deref_mut()).0).1) }
    }
    pub fn remove_at(&mut self, index: usize) -> Option<(K, V)> {
        if index >= self.length {
            return None;
        }
        self.splay_at(index);
        self.length -= 1;
        let node = self.root.take_root().unwrap().into_dying();
        unsafe { Some(node.into_data(self.alloc.deref_mut()).0) }
    }
    pub fn len(&self) -> usize {
        self.length
    }
    pub fn is_empty(&self) -> bool {
        self.len() == 0
    }
    pub fn iter(&mut self) -> Iter<'_, K, V> {
        Iter {
            iter: NodeRange::new(&mut self.root),
        }
    }
    pub fn range<Q, R>(&mut self, range: R) -> Iter<'_, K, V>
    where
        K: Borrow<Q>,
        Q: Ord + ?Sized,
        R: RangeBounds<Q>,
    {
        let start = match range.start_bound() {
            Bound::Included(key) => Bound::Included(SeekByKey::new(key)),
            Bound::Excluded(key) => Bound::Excluded(SeekByKey::new(key)),
            Bound::Unbounded => Bound::Unbounded,
        };
        let end = match range.end_bound() {
            Bound::Included(key) => Bound::Included(SeekByKey::new(key)),
            Bound::Excluded(key) => Bound::Excluded(SeekByKey::new(key)),
            Bound::Unbounded => Bound::Unbounded,
        };
        Iter {
            iter: self.root.range(start, end),
        }
    }
    pub fn range_at<R>(&mut self, range: R) -> Iter<'_, K, V>
    where
        R: RangeBounds<usize>,
    {
        let start = match range.start_bound() {
            Bound::Included(&index) => Bound::Included(SeekBySize::new(index)),
            Bound::Excluded(&index) => Bound::Excluded(SeekBySize::new(index)),
            Bound::Unbounded => Bound::Unbounded,
        };
        let end = match range.end_bound() {
            Bound::Included(&index) => Bound::Included(SeekBySize::new(index)),
            Bound::Excluded(&index) => Bound::Excluded(SeekBySize::new(index)),
            Bound::Unbounded => Bound::Unbounded,
        };
        Iter {
            iter: self.root.range(start, end),
        }
    }

Trait Implementations

impl<K, V> SplaySeeker for SeekBySize<K, V>

type S = SizedSplay<(K, V)>

fn splay_seek(&mut self, node: NodeRef<Immut<'_>, Self::S>) -> Ordering