//! 二叉排序树

use std::fmt;

pub struct Tnode{
	data:isize,
	lchild:Option<Box<Tnode>>,
	rchild:Option<Box<Tnode>>,
}

impl fmt::Display for Tnode{
	fn fmt(&self,f:&mut fmt::Formatter<'_>)->fmt::Result{
		write!(f,"[{}",self.data)?;
		match &self.lchild{
			Some(c)=>c.fmt(f)?,
			None=>(),
		}
		match &self.rchild{
			Some(c)=>c.fmt(f)?,
			None=>(),
		}		
		write!(f,"]")
	}
}

impl Tnode{
	pub fn new(data:isize,lchild:Option<Tnode>,rchild:Option<Tnode>)->Tnode{
		let l = match lchild{
			Some(t)=>Some(Box::new(t)),
			None=>None,
		};
		let r = match rchild{
			Some(t)=>Some(Box::new(t)),
			None=>None,
		};
		Tnode{
			data,
			lchild:l,
			rchild:r,
		}
	}
	
	pub fn search(&self,key:isize)->Option<&Tnode>{
		let mut p = self;
		while p.data !=key{
			if key < p.data{
				match &p.lchild{
					Some(pl)=>p = &pl,
					None=>return None,
				}
			}else {
				match &p.rchild{
					Some(pr)=>p = &pr,
					None=>return None,				
				}
			}
		}
		Some(p)
	}
	
	pub fn insert(&mut self,key:isize)->OptionResult{
		let n = Tnode::new(key,None,None);
		let mut p = self;
		while p.data !=key{
			if key < p.data{
				match p.lchild.as_mut(){
					Some(pl)=>{
						return pl.insert(key);
					},
					None=>{
						p.lchild = Some(Box::new(n));
						return OptionResult::Success;
					},
				}
			}else {
				match p.rchild.as_mut(){
					Some(pr)=>{
						return pr.insert(key);
					},
					None=>{
						p.rchild = Some(Box::new(n));
						return OptionResult::Success;
					},		
				}
			}
		}
		OptionResult::IsThere
	}
	
	/// 第一种删除节点的方法
	pub fn del(mut self,key:isize)->Option<Box<Self>>{
		if key < self.data{
			self.lchild=match self.lchild{
				Some(c)=>{
					c.del(key)
				},
				None=>{
					None
				}
			};
		}else if key > self.data{
			self.rchild=match self.rchild{
				Some(c)=>{
					c.del(key)
				},
				None=>{
					None
				}
			};			
		}else{
			let lchild = self.lchild;
			let rchild = self.rchild;
			
			match lchild{
				Some(lc)=>{
					match rchild{
						Some(rc)=>{
							//2个孩子
							self = *lc;
							if let None = &self.rchild{
								self.rchild=Some(rc);
							}else{
								let mut r_d = &mut self;
								while let Some(c) = r_d.rchild.as_mut(){
									if let None = c.rchild{
										c.rchild = Some(rc);
										break;
									}
									r_d = c;
								}
							}
							return Some(Box::new(self));
						},
						None=>{
							//有左没右
							return Some(lc);
						},
					}
				},
				None=>{
					match rchild{
						Some(rc)=>{
							//没左有右
							return Some(rc);
						},
						None=>{
							//0个孩子
							return None;
						},
					}					
				},
			}
		}
		Some(Box::new(self))
	}

	/// 第二种删除节点的方法
	pub fn del2(mut self,key:isize)->Option<Box<Self>>{
		if key < self.data{
			self.lchild=match self.lchild{
				Some(c)=>{
					c.del2(key)
				},
				None=>{
					None
				}
			};
		}else if key > self.data{
			self.rchild=match self.rchild{
				Some(c)=>{
					c.del2(key)
				},
				None=>{
					None
				}
			};			
		}else{
			let lchild = self.lchild;
			let rchild = self.rchild;
			match lchild{
				Some(lc)=>{
					match rchild{
						Some(rc)=>{
							//2个孩子
							let (n,d) = del_r_d(*lc);
							self.lchild = n;
							self.rchild = Some(rc);
							self.data = d;
							return Some(Box::new(self));
						},
						None=>{
							//有左没右
							return Some(lc);
						},
					}
				},
				None=>{
					match rchild{
						Some(rc)=>{
							//没左有右
							return Some(rc);
						},
						None=>{
							//0个孩子
							return None;
						},
					}					
				},
			}
		}
		Some(Box::new(self))
	}
	
}

/// 删除右下
fn del_r_d(mut node:Tnode)->(Option<Box<Tnode>>,isize){
	let n_res;
	let data;
	match node.rchild{
		Some(c)=>{
			let (n,d) = del_r_d(*c);
			node.rchild = n;
			n_res=Some(Box::new(node));
			data = d;
		},
		None=>{
			data = node.data;
			n_res = match node.lchild{
				Some(l)=>Some(l),
				None=>None,
			};
		},
	}
	(n_res,data)
}

pub enum OptionResult{
	Success,
	Fail,
	IsThere,
}

#[cfg(test)]
mod tests {
    #[test]
    fn it_works() {
        assert_eq!(2 + 2, 4);
    }
}