competitive::data_structure::splay_tree::sized_map

Struct SeekByKey

struct SeekByKey<'a, K, V, Q>where
    Q: ?Sized,{
    key: &'a Q,
    _marker: PhantomData<fn() -> (K, V)>,
}

Fields§

§key: &'a Q§_marker: PhantomData<fn() -> (K, V)>

Implementations§

Source §

impl<'a, K, V, Q> SeekByKey<'a, K, V, Q>
where Q: ?Sized,

Source

fn new(key: &'a Q) -> Self

Examples found in repository ?

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

156    fn splay_by_key<Q>(&mut self, key: &Q) -> Option<Ordering>
157    where
158        K: Borrow<Q>,
159        Q: Ord + ?Sized,
160    {
161        self.root.splay_by(SeekByKey::new(key))
162    }
163    pub fn get_key_value<Q>(&mut self, key: &Q) -> Option<(&K, &V)>
164    where
165        K: Borrow<Q>,
166        Q: Ord + ?Sized,
167    {
168        if !matches!(self.splay_by_key(key)?, Ordering::Equal) {
169            return None;
170        }
171        self.root.root().map(|node| {
172            let ((k, v), _) = node.data();
173            (k, v)
174        })
175    }
176    fn splay_at(&mut self, index: usize) -> Option<Ordering> {
177        self.root.splay_by(SeekBySize::new(index))
178    }
179    pub fn get_key_value_at(&mut self, index: usize) -> Option<(&K, &V)> {
180        if index >= self.length {
181            return None;
182        }
183        self.splay_at(index);
184        self.root.root().map(|node| {
185            let ((k, v), _) = node.data();
186            (k, v)
187        })
188    }
189    pub fn insert(&mut self, key: K, value: V) -> Option<V>
190    where
191        K: Ord,
192    {
193        let ord = self.splay_by_key(&key);
194        self.length += (ord != Some(Ordering::Equal)) as usize;
195        match ord {
196            Some(Ordering::Equal) => {
197                return Some(replace(
198                    &mut (self.root.root_data_mut().unwrap().data_mut().0).1,
199                    value,
200                ));
201            }
202            Some(Ordering::Less) => unsafe {
203                self.root.insert_left(NodeRef::from_data(
204                    ((key, value), 1),
205                    self.alloc.deref_mut(),
206                ));
207            },
208            _ => unsafe {
209                self.root.insert_right(NodeRef::from_data(
210                    ((key, value), 1),
211                    self.alloc.deref_mut(),
212                ));
213            },
214        }
215        None
216    }
217    pub fn remove<Q>(&mut self, key: &Q) -> Option<V>
218    where
219        K: Borrow<Q>,
220        Q: Ord + ?Sized,
221    {
222        if !matches!(self.splay_by_key(key)?, Ordering::Equal) {
223            return None;
224        }
225        self.length -= 1;
226        let node = self.root.take_root().unwrap().into_dying();
227        unsafe { Some((node.into_data(self.alloc.deref_mut()).0).1) }
228    }
229    pub fn remove_at(&mut self, index: usize) -> Option<(K, V)> {
230        if index >= self.length {
231            return None;
232        }
233        self.splay_at(index);
234        self.length -= 1;
235        let node = self.root.take_root().unwrap().into_dying();
236        unsafe { Some(node.into_data(self.alloc.deref_mut()).0) }
237    }
238    pub fn len(&self) -> usize {
239        self.length
240    }
241    pub fn is_empty(&self) -> bool {
242        self.len() == 0
243    }
244    pub fn iter(&mut self) -> Iter<'_, K, V> {
245        Iter {
246            iter: NodeRange::new(&mut self.root),
247        }
248    }
249    pub fn range<Q, R>(&mut self, range: R) -> Iter<'_, K, V>
250    where
251        K: Borrow<Q>,
252        Q: Ord + ?Sized,
253        R: RangeBounds<Q>,
254    {
255        let start = match range.start_bound() {
256            Bound::Included(key) => Bound::Included(SeekByKey::new(key)),
257            Bound::Excluded(key) => Bound::Excluded(SeekByKey::new(key)),
258            Bound::Unbounded => Bound::Unbounded,
259        };
260        let end = match range.end_bound() {
261            Bound::Included(key) => Bound::Included(SeekByKey::new(key)),
262            Bound::Excluded(key) => Bound::Excluded(SeekByKey::new(key)),
263            Bound::Unbounded => Bound::Unbounded,
264        };
265        Iter {
266            iter: self.root.range(start, end),
267        }
268    }