#[derive(Debug)]
struct Interval {
lower: i32,
upper: i32,
}
impl Interval {
fn single(lower: i32) -> Interval {
Interval { lower: lower, upper: lower }
}
fn new(lower: i32, upper: i32) -> Interval {
assert!(lower <= upper);
Interval { lower: lower, upper: upper }
}
fn in_range(&self, item: i32) -> bool {
self.lower <= item && item <= self.upper
}
}
type SplitResult = (i32, Option<Box<Node>>);
#[derive(Debug)]
struct Node {
left: Option<Box<Node>>,
value: Interval,
right: Option<Box<Node>>,
}
impl Node {
fn single(v : i32) -> Node {
Node { left: None, value: Interval::single(v), right: None }
}
fn contains(&self, item: i32) -> bool {
if self.value.in_range(item) {
true
} else if item < self.value.lower {
self.left.as_ref().map_or(false, |v| v.contains(item))
} else {
self.right.as_ref().map_or(false, |v| v.contains(item))
}
}
fn split_max(self) -> SplitResult {
if let Some(node) = self.right {
let (u, r_) = node.split_max();
(u, Some(Box::new(Node { right: r_, ..self })))
} else {
(self.value.lower, self.left)
}
}
fn possible_split_max(&self) -> i32 {
if let Some(ref node) = self.right {
node.possible_split_max()
} else {
self.value.upper
}
}
fn join_left(&mut self) {
if self.left.is_none() {
return;
}
let y_ = self.left.as_ref().unwrap().possible_split_max();
if y_ + 1 == self.value.lower {
let (x_, l_) = self.left.take().unwrap().split_max();
self.value.lower = x_;
self.left = l_;
}
}
fn split_min(self) -> SplitResult {
if let Some(node) = self.left {
let (v, l_) = node.split_min();
(v, Some(Box::new(Node { left: l_, ..self })))
} else {
(self.value.upper, self.right)
}
}
fn possible_split_min(&self) -> i32 {
if let Some(ref node) = self.left {
node.possible_split_min()
} else {
self.value.lower
}
}
fn join_right(&mut self) {
if self.right.is_none() {
return;
}
let x_ = self.right.as_ref().unwrap().possible_split_min();
if x_ - 1 == self.value.upper {
let (y_, r_) = self.right.take().unwrap().split_min();
self.value.upper = y_;
self.right = r_;
}
}
fn insert(&mut self, new_item: i32) {
match new_item {
k if k == self.value.lower - 1 => {
self.value.lower = k;
self.join_left();
},
k if k == self.value.upper + 1 => {
self.value.upper = k;
self.join_right();
},
k if k < self.value.lower => {
Node::insert_or_create(&mut self.left, k);
},
k if k > self.value.upper => {
Node::insert_or_create(&mut self.right, k);
},
_ => {
assert!(self.value.in_range(new_item));
}
}
}
fn insert_or_create(node: &mut Option<Box<Node>>, new_item: i32) {
if let Some(ref mut node) = *node {
node.insert(new_item);
} else {
*node = Some(Box::new(Node::single(new_item)));
}
}
fn maybe_delete(opt_node: &mut Option<Box<Self>>, item: i32) {
let mut delete_node = false;
if let Some(ref mut node) = *opt_node {
if item < node.value.lower {
Node::maybe_delete(&mut node.left, item);
} else if item > node.value.upper {
Node::maybe_delete(&mut node.right, item);
} else if item == node.value.lower {
if item == node.value.upper {
match (node.left.take(), node.right.take()) {
(None, None) => {
delete_node = true;
},
(Some(left), None) => {
*node = left;
},
(None, Some(right)) => {
*node = right;
}
(Some(left), Some(right)) => {
let y = left.possible_split_max();
let (x, l_) = left.split_max();
node.value.lower = x;
node.value.upper = y;
node.left = l_;
node.right = Some(right);
}
}
} else {
node.value.lower += 1;
}
} else if item == node.value.upper {
node.value.upper -= 1;
} else {
let right_value = Interval::new(item + 1, node.value.upper);
node.value.upper = item - 1;
let right = node.right.take();
node.right = Some(Box::new(Node { left: None, right: right, value: right_value }));
}
}
if delete_node {
opt_node.take();
}
}
}
#[derive(Debug)]
pub struct Diet {
root: Option<Box<Node>>,
}
impl Diet {
pub fn new() -> Diet {
Diet { root: None }
}
pub fn contains(&self, item: i32) -> bool {
self.root.as_ref().map_or(false, |v| v.contains(item))
}
pub fn insert(&mut self, new_item: i32) -> () {
Node::insert_or_create(&mut self.root, new_item);
}
pub fn delete(&mut self, item: i32) -> () {
Node::maybe_delete(&mut self.root, item);
}
}
#[cfg(test)]
mod test {
use super::{Interval,Node,Diet};
#[test]
fn test_interval() {
Interval::new(3, 4);
}
#[test]
#[should_panic]
fn test_bad_interval() {
Interval::new(4, 4);
Interval::new(4, 3);
}
#[test]
fn test_node() {
let i = Interval::new(4, 5);
let r = Box::new(Node::single(7));
let node = Node { left: None, value: i, right: Some(r) };
assert!(node.contains(4));
assert!(node.contains(5));
assert!(node.contains(7));
assert!(!node.contains(6));
assert!(!node.contains(3));
let i2 = Interval::new(4, 5);
let l = Box::new(Node::single(0));
let node2 = Node { left: Some(l), value: i2, right: None };
assert!(node2.contains(4));
assert!(node2.contains(5));
assert!(!node2.contains(7));
assert!(!node2.contains(6));
assert!(!node2.contains(3));
assert!(node2.contains(0));
}
#[test]
fn test_diet_basic() {
let mut d = Diet::new();
assert!(!d.contains(5));
d.insert(5);
assert!(d.contains(5));
d.insert(3);
assert!(d.contains(3));
d.insert(4);
assert!(d.contains(4));
{
let b = d.root.as_ref().unwrap();
assert!(b.left.is_none());
assert!(b.right.is_none());
assert!(b.value.lower == 3);
assert!(b.value.upper == 5);
}
d.insert(7);
assert!(d.contains(7));
assert!(!d.contains(6));
d.insert(6);
assert!(d.contains(6));
{
let b = &d.root.unwrap();
assert!(b.left.is_none());
assert!(b.right.is_none());
assert!(b.value.lower == 3);
assert!(b.value.upper == 7);
}
}
#[test]
fn test_delete_simple() {
let mut d = Diet::new();
d.delete(5);
d.insert(5);
assert!(d.contains(5));
d.delete(5);
assert!(!d.contains(5));
}
#[test]
fn test_delete_branch() {
let mut d = Diet::new();
d.insert(5);
d.insert(3);
d.insert(7);
d.delete(3);
assert!(!d.contains(3));
assert!(d.contains(5));
assert!(d.contains(7));
d.delete(7);
assert!(d.contains(5));
}
#[test]
fn test_delete_replace_merge() {
let mut d = Diet::new();
d.insert(5);
d.insert(3);
d.delete(5);
assert!(!d.contains(5));
assert!(d.contains(3));
d.insert(7);
d.delete(3);
assert!(!d.contains(3));
assert!(d.contains(7));
}
#[test]
fn test_delete_lower_upper() {
let mut d = Diet::new();
d.insert(5);
d.insert(6);
d.insert(7);
d.delete(5);
assert!(d.contains(6));
assert!(d.contains(7));
d.delete(7);
assert!(d.contains(6));
}
#[test]
fn test_delete_merge() {
unimplemented!();
}
#[test]
fn test_delete_split_left() {
let mut d = Diet::new();
d.insert(8);
d.insert(9);
d.insert(10);
d.insert(2);
d.insert(4);
d.insert(6);
d.insert(14);
d.insert(12);
d.insert(16);
d.delete(8);
d.delete(9);
d.delete(10);
assert!(d.contains(2));
assert!(d.contains(4));
assert!(d.contains(6));
assert!(d.contains(14));
assert!(d.contains(12));
assert!(d.contains(16));
}
}