pub trait SplaySpec: Sized {
type T;
// Provided methods
fn has_bottom_up() -> bool { ... }
fn top_down(_node: NodeRef<DataMut<'_>, Self>) { ... }
fn bottom_up(_node: NodeRef<DataMut<'_>, Self>) { ... }
}Required Associated Types§
Provided Methods§
Sourcefn has_bottom_up() -> bool
fn has_bottom_up() -> bool
Examples found in repository?
crates/competitive/src/data_structure/splay_tree/node.rs (line 413)
296 pub fn splay_by<Seeker>(self, mut seeker: Seeker) -> (Ordering, Self)
297 where
298 Seeker: SplaySeeker<S = S>,
299 {
300 let mut x = self;
301 // let dummy = Node { data: None, left: left_subtree, right: right_subtree };
302 let mut left_subtree: Option<NonNull<Node<S::T>>> = None;
303 let mut right_subtree: Option<NonNull<Node<S::T>>> = None;
304 let mut left_entry = &mut left_subtree;
305 let mut right_entry = &mut right_subtree;
306 let mut stack = vec![];
307
308 macro_rules! add {
309 (@left Some($ptr:ident)) => { add!(@inner Some($ptr.node), left_entry $ptr right); };
310 (@right Some($ptr:ident)) => { add!(@inner Some($ptr.node), right_entry $ptr left); };
311 (@inner $node:expr, $entry:ident $ptr:ident $dir:ident) => {
312 *$entry = $node;
313 if S::has_bottom_up() {
314 stack.push($ptr.node);
315 }
316 $entry = unsafe { &mut (*$entry.as_mut().unwrap().as_ptr()).$dir };
317 };
318 }
319
320 let root_ord = loop {
321 S::top_down(x.borrow_datamut());
322 match seeker.splay_seek(x.reborrow()) {
323 Ordering::Less => {
324 if let Some(mut y) = x.borrow_mut().take_left() {
325 S::top_down(y.borrow_datamut());
326 match seeker.splay_seek(y.reborrow()) {
327 Ordering::Less => {
328 if let Some(mut z) = y.borrow_mut().take_left() {
329 S::top_down(z.borrow_datamut());
330 x.borrow_mut().set_left(y.borrow_mut().take_right());
331 S::bottom_up(x.borrow_datamut());
332 y.borrow_mut().set_right(Some(x));
333 add!(@right Some(y));
334 x = z;
335 } else {
336 add!(@right Some(x));
337 x = y;
338 break Ordering::Less;
339 }
340 }
341 Ordering::Equal => {
342 add!(@right Some(x));
343 x = y;
344 break Ordering::Equal;
345 }
346 Ordering::Greater => {
347 if let Some(mut z) = y.borrow_mut().take_right() {
348 S::top_down(z.borrow_datamut());
349 add!(@right Some(x));
350 add!(@left Some(y));
351 x = z;
352 } else {
353 add!(@right Some(x));
354 x = y;
355 break Ordering::Greater;
356 }
357 }
358 }
359 } else {
360 break Ordering::Less;
361 }
362 }
363 Ordering::Equal => break Ordering::Equal,
364 Ordering::Greater => {
365 if let Some(mut y) = x.borrow_mut().take_right() {
366 S::top_down(y.borrow_datamut());
367 match seeker.splay_seek(y.reborrow()) {
368 Ordering::Less => {
369 if let Some(mut z) = y.borrow_mut().take_left() {
370 S::top_down(z.borrow_datamut());
371 add!(@left Some(x));
372 add!(@right Some(y));
373 x = z;
374 } else {
375 add!(@left Some(x));
376 x = y;
377 break Ordering::Less;
378 }
379 }
380 Ordering::Equal => {
381 add!(@left Some(x));
382 x = y;
383 break Ordering::Equal;
384 }
385 Ordering::Greater => {
386 if let Some(mut z) = y.borrow_mut().take_right() {
387 S::top_down(z.borrow_datamut());
388 x.borrow_mut().set_right(y.borrow_mut().take_left());
389 S::bottom_up(x.borrow_datamut());
390 y.borrow_mut().set_left(Some(x));
391 add!(@left Some(y));
392 x = z;
393 } else {
394 add!(@left Some(x));
395 x = y;
396 break Ordering::Greater;
397 }
398 }
399 }
400 } else {
401 break Ordering::Greater;
402 }
403 }
404 }
405 };
406 *left_entry = x.borrow_mut().take_left().map(|node| node.node);
407 *right_entry = x.borrow_mut().take_right().map(|node| node.node);
408 unsafe {
409 x.borrow_mut()
410 .set_left(left_subtree.map(|node| NodeRef::new_unchecked(node)));
411 x.borrow_mut()
412 .set_right(right_subtree.map(|node| NodeRef::new_unchecked(node)));
413 if S::has_bottom_up() {
414 while let Some(node) = stack.pop() {
415 S::bottom_up(NodeRef::new_unchecked(node));
416 }
417 }
418 }
419 S::bottom_up(x.borrow_datamut());
420 (root_ord, x)
421 }Sourcefn top_down(_node: NodeRef<DataMut<'_>, Self>)
fn top_down(_node: NodeRef<DataMut<'_>, Self>)
Examples found in repository?
crates/competitive/src/data_structure/splay_tree/node.rs (line 321)
296 pub fn splay_by<Seeker>(self, mut seeker: Seeker) -> (Ordering, Self)
297 where
298 Seeker: SplaySeeker<S = S>,
299 {
300 let mut x = self;
301 // let dummy = Node { data: None, left: left_subtree, right: right_subtree };
302 let mut left_subtree: Option<NonNull<Node<S::T>>> = None;
303 let mut right_subtree: Option<NonNull<Node<S::T>>> = None;
304 let mut left_entry = &mut left_subtree;
305 let mut right_entry = &mut right_subtree;
306 let mut stack = vec![];
307
308 macro_rules! add {
309 (@left Some($ptr:ident)) => { add!(@inner Some($ptr.node), left_entry $ptr right); };
310 (@right Some($ptr:ident)) => { add!(@inner Some($ptr.node), right_entry $ptr left); };
311 (@inner $node:expr, $entry:ident $ptr:ident $dir:ident) => {
312 *$entry = $node;
313 if S::has_bottom_up() {
314 stack.push($ptr.node);
315 }
316 $entry = unsafe { &mut (*$entry.as_mut().unwrap().as_ptr()).$dir };
317 };
318 }
319
320 let root_ord = loop {
321 S::top_down(x.borrow_datamut());
322 match seeker.splay_seek(x.reborrow()) {
323 Ordering::Less => {
324 if let Some(mut y) = x.borrow_mut().take_left() {
325 S::top_down(y.borrow_datamut());
326 match seeker.splay_seek(y.reborrow()) {
327 Ordering::Less => {
328 if let Some(mut z) = y.borrow_mut().take_left() {
329 S::top_down(z.borrow_datamut());
330 x.borrow_mut().set_left(y.borrow_mut().take_right());
331 S::bottom_up(x.borrow_datamut());
332 y.borrow_mut().set_right(Some(x));
333 add!(@right Some(y));
334 x = z;
335 } else {
336 add!(@right Some(x));
337 x = y;
338 break Ordering::Less;
339 }
340 }
341 Ordering::Equal => {
342 add!(@right Some(x));
343 x = y;
344 break Ordering::Equal;
345 }
346 Ordering::Greater => {
347 if let Some(mut z) = y.borrow_mut().take_right() {
348 S::top_down(z.borrow_datamut());
349 add!(@right Some(x));
350 add!(@left Some(y));
351 x = z;
352 } else {
353 add!(@right Some(x));
354 x = y;
355 break Ordering::Greater;
356 }
357 }
358 }
359 } else {
360 break Ordering::Less;
361 }
362 }
363 Ordering::Equal => break Ordering::Equal,
364 Ordering::Greater => {
365 if let Some(mut y) = x.borrow_mut().take_right() {
366 S::top_down(y.borrow_datamut());
367 match seeker.splay_seek(y.reborrow()) {
368 Ordering::Less => {
369 if let Some(mut z) = y.borrow_mut().take_left() {
370 S::top_down(z.borrow_datamut());
371 add!(@left Some(x));
372 add!(@right Some(y));
373 x = z;
374 } else {
375 add!(@left Some(x));
376 x = y;
377 break Ordering::Less;
378 }
379 }
380 Ordering::Equal => {
381 add!(@left Some(x));
382 x = y;
383 break Ordering::Equal;
384 }
385 Ordering::Greater => {
386 if let Some(mut z) = y.borrow_mut().take_right() {
387 S::top_down(z.borrow_datamut());
388 x.borrow_mut().set_right(y.borrow_mut().take_left());
389 S::bottom_up(x.borrow_datamut());
390 y.borrow_mut().set_left(Some(x));
391 add!(@left Some(y));
392 x = z;
393 } else {
394 add!(@left Some(x));
395 x = y;
396 break Ordering::Greater;
397 }
398 }
399 }
400 } else {
401 break Ordering::Greater;
402 }
403 }
404 }
405 };
406 *left_entry = x.borrow_mut().take_left().map(|node| node.node);
407 *right_entry = x.borrow_mut().take_right().map(|node| node.node);
408 unsafe {
409 x.borrow_mut()
410 .set_left(left_subtree.map(|node| NodeRef::new_unchecked(node)));
411 x.borrow_mut()
412 .set_right(right_subtree.map(|node| NodeRef::new_unchecked(node)));
413 if S::has_bottom_up() {
414 while let Some(node) = stack.pop() {
415 S::bottom_up(NodeRef::new_unchecked(node));
416 }
417 }
418 }
419 S::bottom_up(x.borrow_datamut());
420 (root_ord, x)
421 }
422 pub fn insert_left(mut self, mut node: Self) -> Self {
423 if let Some(left) = self.borrow_mut().take_left() {
424 node.borrow_mut().set_left(Some(left));
425 S::bottom_up(self.borrow_datamut());
426 };
427 node.borrow_mut().set_right(Some(self));
428 S::bottom_up(node.borrow_datamut());
429 node
430 }
431 pub fn insert_right(mut self, mut node: Self) -> Self {
432 if let Some(right) = self.borrow_mut().take_right() {
433 node.borrow_mut().set_right(Some(right));
434 S::bottom_up(self.borrow_datamut());
435 }
436 node.borrow_mut().set_left(Some(self));
437 S::bottom_up(node.borrow_datamut());
438 node
439 }
440 pub fn insert_first(self, mut node: Self) -> Self {
441 node.borrow_mut().set_right(Some(self));
442 S::bottom_up(node.borrow_datamut());
443 node
444 }
445 pub fn insert_last(self, mut node: Self) -> Self {
446 node.borrow_mut().set_left(Some(self));
447 S::bottom_up(node.borrow_datamut());
448 node
449 }
450 pub fn merge(mut self, mut other: Self) -> Self {
451 if other.reborrow().left().is_none() {
452 S::top_down(other.borrow_datamut());
453 other.borrow_mut().set_left(Some(self));
454 S::bottom_up(other.borrow_datamut());
455 other
456 } else {
457 self = self.splay_by(SeekRight::new()).1;
458 self.borrow_mut().set_right(Some(other));
459 S::bottom_up(self.borrow_datamut());
460 self
461 }
462 }Sourcefn bottom_up(_node: NodeRef<DataMut<'_>, Self>)
fn bottom_up(_node: NodeRef<DataMut<'_>, Self>)
Examples found in repository?
More examples
crates/competitive/src/data_structure/splay_tree/node.rs (line 331)
296 pub fn splay_by<Seeker>(self, mut seeker: Seeker) -> (Ordering, Self)
297 where
298 Seeker: SplaySeeker<S = S>,
299 {
300 let mut x = self;
301 // let dummy = Node { data: None, left: left_subtree, right: right_subtree };
302 let mut left_subtree: Option<NonNull<Node<S::T>>> = None;
303 let mut right_subtree: Option<NonNull<Node<S::T>>> = None;
304 let mut left_entry = &mut left_subtree;
305 let mut right_entry = &mut right_subtree;
306 let mut stack = vec![];
307
308 macro_rules! add {
309 (@left Some($ptr:ident)) => { add!(@inner Some($ptr.node), left_entry $ptr right); };
310 (@right Some($ptr:ident)) => { add!(@inner Some($ptr.node), right_entry $ptr left); };
311 (@inner $node:expr, $entry:ident $ptr:ident $dir:ident) => {
312 *$entry = $node;
313 if S::has_bottom_up() {
314 stack.push($ptr.node);
315 }
316 $entry = unsafe { &mut (*$entry.as_mut().unwrap().as_ptr()).$dir };
317 };
318 }
319
320 let root_ord = loop {
321 S::top_down(x.borrow_datamut());
322 match seeker.splay_seek(x.reborrow()) {
323 Ordering::Less => {
324 if let Some(mut y) = x.borrow_mut().take_left() {
325 S::top_down(y.borrow_datamut());
326 match seeker.splay_seek(y.reborrow()) {
327 Ordering::Less => {
328 if let Some(mut z) = y.borrow_mut().take_left() {
329 S::top_down(z.borrow_datamut());
330 x.borrow_mut().set_left(y.borrow_mut().take_right());
331 S::bottom_up(x.borrow_datamut());
332 y.borrow_mut().set_right(Some(x));
333 add!(@right Some(y));
334 x = z;
335 } else {
336 add!(@right Some(x));
337 x = y;
338 break Ordering::Less;
339 }
340 }
341 Ordering::Equal => {
342 add!(@right Some(x));
343 x = y;
344 break Ordering::Equal;
345 }
346 Ordering::Greater => {
347 if let Some(mut z) = y.borrow_mut().take_right() {
348 S::top_down(z.borrow_datamut());
349 add!(@right Some(x));
350 add!(@left Some(y));
351 x = z;
352 } else {
353 add!(@right Some(x));
354 x = y;
355 break Ordering::Greater;
356 }
357 }
358 }
359 } else {
360 break Ordering::Less;
361 }
362 }
363 Ordering::Equal => break Ordering::Equal,
364 Ordering::Greater => {
365 if let Some(mut y) = x.borrow_mut().take_right() {
366 S::top_down(y.borrow_datamut());
367 match seeker.splay_seek(y.reborrow()) {
368 Ordering::Less => {
369 if let Some(mut z) = y.borrow_mut().take_left() {
370 S::top_down(z.borrow_datamut());
371 add!(@left Some(x));
372 add!(@right Some(y));
373 x = z;
374 } else {
375 add!(@left Some(x));
376 x = y;
377 break Ordering::Less;
378 }
379 }
380 Ordering::Equal => {
381 add!(@left Some(x));
382 x = y;
383 break Ordering::Equal;
384 }
385 Ordering::Greater => {
386 if let Some(mut z) = y.borrow_mut().take_right() {
387 S::top_down(z.borrow_datamut());
388 x.borrow_mut().set_right(y.borrow_mut().take_left());
389 S::bottom_up(x.borrow_datamut());
390 y.borrow_mut().set_left(Some(x));
391 add!(@left Some(y));
392 x = z;
393 } else {
394 add!(@left Some(x));
395 x = y;
396 break Ordering::Greater;
397 }
398 }
399 }
400 } else {
401 break Ordering::Greater;
402 }
403 }
404 }
405 };
406 *left_entry = x.borrow_mut().take_left().map(|node| node.node);
407 *right_entry = x.borrow_mut().take_right().map(|node| node.node);
408 unsafe {
409 x.borrow_mut()
410 .set_left(left_subtree.map(|node| NodeRef::new_unchecked(node)));
411 x.borrow_mut()
412 .set_right(right_subtree.map(|node| NodeRef::new_unchecked(node)));
413 if S::has_bottom_up() {
414 while let Some(node) = stack.pop() {
415 S::bottom_up(NodeRef::new_unchecked(node));
416 }
417 }
418 }
419 S::bottom_up(x.borrow_datamut());
420 (root_ord, x)
421 }
422 pub fn insert_left(mut self, mut node: Self) -> Self {
423 if let Some(left) = self.borrow_mut().take_left() {
424 node.borrow_mut().set_left(Some(left));
425 S::bottom_up(self.borrow_datamut());
426 };
427 node.borrow_mut().set_right(Some(self));
428 S::bottom_up(node.borrow_datamut());
429 node
430 }
431 pub fn insert_right(mut self, mut node: Self) -> Self {
432 if let Some(right) = self.borrow_mut().take_right() {
433 node.borrow_mut().set_right(Some(right));
434 S::bottom_up(self.borrow_datamut());
435 }
436 node.borrow_mut().set_left(Some(self));
437 S::bottom_up(node.borrow_datamut());
438 node
439 }
440 pub fn insert_first(self, mut node: Self) -> Self {
441 node.borrow_mut().set_right(Some(self));
442 S::bottom_up(node.borrow_datamut());
443 node
444 }
445 pub fn insert_last(self, mut node: Self) -> Self {
446 node.borrow_mut().set_left(Some(self));
447 S::bottom_up(node.borrow_datamut());
448 node
449 }
450 pub fn merge(mut self, mut other: Self) -> Self {
451 if other.reborrow().left().is_none() {
452 S::top_down(other.borrow_datamut());
453 other.borrow_mut().set_left(Some(self));
454 S::bottom_up(other.borrow_datamut());
455 other
456 } else {
457 self = self.splay_by(SeekRight::new()).1;
458 self.borrow_mut().set_right(Some(other));
459 S::bottom_up(self.borrow_datamut());
460 self
461 }
462 }
463}
464
465impl<S> Root<S>
466where
467 S: SplaySpec,
468{
469 pub fn new(root: Option<NodeRef<marker::Owned, S>>) -> Self {
470 Self { root }
471 }
472 pub unsafe fn from_single_nodes(nodes: Vec<NodeRef<marker::Owned, S>>) -> Self {
473 unsafe { Self::from_single_nodes_inner(&nodes) }
474 }
475 unsafe fn from_single_nodes_inner(nodes: &[NodeRef<marker::Owned, S>]) -> Self {
476 if nodes.is_empty() {
477 Self::new(None)
478 } else {
479 let m = nodes.len() / 2;
480 let left = unsafe { Self::from_single_nodes_inner(&nodes[..m]) };
481 let right = unsafe { Self::from_single_nodes_inner(&nodes[m + 1..]) };
482 let mut node = NodeRef::new(nodes[m].node);
483 node.borrow_mut().set_left(left.root);
484 node.borrow_mut().set_right(right.root);
485 S::bottom_up(node.borrow_datamut());
486 Self::new(Some(node))
487 }
488 }
489 pub fn is_empty(&self) -> bool {
490 self.root.is_none()
491 }
492 pub fn root(&self) -> Option<NodeRef<marker::Immut<'_>, S>> {
493 Some(self.root.as_ref()?.reborrow())
494 }
495 pub fn root_data_mut(&mut self) -> Option<NodeRef<marker::DataMut<'_>, S>> {
496 Some(self.root.as_mut()?.borrow_datamut())
497 }
498 pub fn splay_by<Seeker>(&mut self, seeker: Seeker) -> Option<Ordering>
499 where
500 Seeker: SplaySeeker<S = S>,
501 {
502 let (ord, root) = self.root.take()?.splay_by(seeker);
503 self.root = Some(root);
504 Some(ord)
505 }
506 pub fn insert_left(&mut self, mut node: NodeRef<marker::Owned, S>) {
507 self.root = Some(match self.root.take() {
508 Some(root) => root.insert_left(node),
509 None => {
510 S::bottom_up(node.borrow_datamut());
511 node
512 }
513 });
514 }
515 pub fn insert_right(&mut self, mut node: NodeRef<marker::Owned, S>) {
516 self.root = Some(match self.root.take() {
517 Some(root) => root.insert_right(node),
518 None => {
519 S::bottom_up(node.borrow_datamut());
520 node
521 }
522 });
523 }
524 pub fn insert_first(&mut self, mut node: NodeRef<marker::Owned, S>) {
525 self.root = Some(match self.root.take() {
526 Some(root) => root.insert_first(node),
527 None => {
528 S::bottom_up(node.borrow_datamut());
529 node
530 }
531 });
532 }
533 pub fn insert_last(&mut self, mut node: NodeRef<marker::Owned, S>) {
534 self.root = Some(match self.root.take() {
535 Some(root) => root.insert_last(node),
536 None => {
537 S::bottom_up(node.borrow_datamut());
538 node
539 }
540 });
541 }
542 pub fn take_root(&mut self) -> Option<NodeRef<marker::Owned, S>> {
543 let mut root = self.root.take()?;
544 let right = root.borrow_mut().take_right();
545 self.root = root.borrow_mut().take_left();
546 self.append(&mut Self::new(right));
547 Some(root)
548 }
549 pub fn take_first(&mut self) -> Option<NodeRef<marker::Owned, S>> {
550 let mut root = self.root.take()?.splay_by(SeekLeft::new()).1;
551 let right = root.borrow_mut().take_right();
552 self.root = right;
553 Some(root)
554 }
555 pub fn take_last(&mut self) -> Option<NodeRef<marker::Owned, S>> {
556 let mut root = self.root.take()?.splay_by(SeekRight::new()).1;
557 let left = root.borrow_mut().take_left();
558 self.root = left;
559 Some(root)
560 }
561 pub fn split_left(&mut self) -> Option<NodeRef<marker::Owned, S>> {
562 let root = self.root.as_mut()?;
563 let left = root.borrow_mut().take_left();
564 S::bottom_up(root.borrow_datamut());
565 left
566 }
567 pub fn split_right(&mut self) -> Option<NodeRef<marker::Owned, S>> {
568 let root = self.root.as_mut()?;
569 let right = root.borrow_mut().take_right();
570 S::bottom_up(root.borrow_datamut());
571 right
572 }Dyn Compatibility§
This trait is not dyn compatible.
In older versions of Rust, dyn compatibility was called "object safety", so this trait is not object safe.