| 494 | |
| 495 | #[test] |
| 496 | fn three_level_sparse_tree() { |
| 497 | let mut f = SetForest::<u32>::new(); |
| 498 | let mut s = Set::<u32>::new(); |
| 499 | let mut c = SetCursor::new(&mut s, &mut f, &()); |
| 500 | |
| 501 | // Insert enough elements that we get a 3-level tree. |
| 502 | // Each leaf node holds 8 elements when filled up sequentially. |
| 503 | // Inner nodes hold 8 node pointers. |
| 504 | assert!(c.is_empty()); |
| 505 | for i in 0..150 { |
| 506 | assert!(c.insert(i)); |
| 507 | assert_eq!(c.elem(), Some(i)); |
| 508 | } |
| 509 | assert!(!c.is_empty()); |
| 510 | |
| 511 | assert!(c.goto(0)); |
| 512 | assert_eq!(c.tpath(), "node11[0]--node2[0]--node0[0]"); |
| 513 | |
| 514 | assert_eq!(c.prev(), None); |
| 515 | for i in 1..150 { |
| 516 | assert_eq!(c.next(), Some(i)); |
| 517 | } |
| 518 | assert_eq!(c.next(), None); |
| 519 | for i in (0..150).rev() { |
| 520 | assert_eq!(c.prev(), Some(i)); |
| 521 | } |
| 522 | assert_eq!(c.prev(), None); |
| 523 | |
| 524 | assert!(c.goto(125)); |
| 525 | for i in 125..150 { |
| 526 | assert_eq!(c.remove(), Some(i)); |
| 527 | assert!(!c.is_empty()); |
| 528 | c.verify(); |
| 529 | } |
| 530 | |
| 531 | for i in (0..125).rev() { |
| 532 | assert!(!c.is_empty()); |
| 533 | assert_eq!(c.elem(), None); |
| 534 | assert_eq!(c.prev(), Some(i)); |
| 535 | assert_eq!(c.remove(), Some(i)); |
| 536 | c.verify(); |
| 537 | } |
| 538 | assert_eq!(c.elem(), None); |
| 539 | assert!(c.is_empty()); |
| 540 | } |
| 541 | |
| 542 | // Generate a densely populated 4-level tree. |
| 543 | // |