decision 0.1.3

//! c45
//! c4.5 分类相关工具
use std::f32;
use std::fmt;

///结果
#[derive(Debug)]
pub struct Result {
	cells:Vec<String>
}

impl Result{
	fn new()->Result{
		Result{cells:Vec::new(),}
	}
}

/// 列类型
#[derive(Clone,Copy,Debug)]
pub enum ColType {
	Conti,//连续型 
	Discr,//离散型
}

///统计
#[derive(Debug)]
pub struct Stati {
	k:String,//key
	n:usize,//count
	child:Vec<Stati>,
	info:f32,//entropy
}

impl Stati{
	fn new(k:String)->Stati{
		Stati{
			k,
			n:0,
			child:Vec::new(),
			info:-1.0,
		}
	}
	fn get_info(&mut self)->f32{
		if self.info == -1.0 && self.child.len() > 0{
			let mut info:f32 = 0.0;
			if self.child[0].get_info() == -1.0 {
				for c in self.child.iter(){
					let r = c.n as f32/self.n as f32;
					info += r * (-1.0 *  r.log2());
				}
			}else{
				for c in self.child.iter_mut(){
					let r = c.n as f32/self.n as f32;
					info += r * c.get_info();
				}
			}
			self.info = info;
		}
		self.info
	}
}

///列
#[derive(Debug)]
pub struct Col {
	cells:Vec<String>,
	stati:Stati,
	name:String,
	t:ColType,
	gain_ratio:f32,
	gain:f32,
	info:f32,
}

impl Col{
	fn new(name:String,t:ColType)->Col{
		Col{
			cells:Vec::new(),
			stati:Stati::new(name.clone()),
			name,
			t,
			gain_ratio:-1.0,
			gain:-1.0,
			info:-1.0,
		}
	}
}

#[derive(Debug)]
pub struct D {
	cols:Vec<Col>,
	r:Result,
	info:f32,
}

impl D {
	fn get_d_info(&mut self) -> f32{
		if self.info == -1.0 {
			let mut sta = Stati::new("d".to_string());
			for ai in self.r.cells.iter() {
				sta.n+=1;
				fill_stati(&mut sta,ai,&"".to_string());
			}	
			self.info = sta.get_info();	
		}
		self.info
	}
	
	//计算列本身的熵
	fn get_cols_info(&mut self){
		for c in self.cols.iter_mut(){
			let mut sta = Stati::new(c.name.clone());
			let mut n = 0;
			for ai in c.stati.child.iter() {
				let mut sta_child = Stati::new(ai.k.clone());
				sta_child.n = ai.n;
				sta.child.push(sta_child);
				n += ai.n;
			}
			sta.n = n;
			c.info = sta.get_info();
		}
	}
	
	fn get_conti_gain_and_stati(&mut self) {
		let d_info = self.get_d_info();
		for c in self.cols.iter_mut(){
			if let ColType::Conti = c.t{
				let mut copy = Vec::new();
				//复制此列的数据到一个新Vec，并同时转换为f32
				for vi in c.cells.iter() {
					let f:f32 = vi.parse().unwrap();
					copy.push(f);
				}
				copy = sort(&mut copy);
				let mut mid = Vec::new();
				//计算 中间值，并存入Vec
				for i in 0..(copy.len()-1) {
					let c1 = copy[i];
					let c2 = copy[i+1];
					if c1 == c2 {
						continue;
					}
					let m = (c1 + c2) / 2.0;
					mid.push(m);
				}
				let mut max_gain = 0.0_f32;
				let mut max_stati = Stati::new(c.name.clone());
				//对每一个中间值，计算增益，
				for m in mid.iter() {
					let mut sta = Stati::new(m.to_string());
					for i in 0..c.cells.len() {
						let f:f32 = c.cells[i].parse().unwrap();
						sta.n += 1;
						let mut k = format!("<{}",m);
						if f > *m {
							k = format!(">{}",m);
						}
						fill_stati(&mut sta,&k,&self.r.cells[i]);
					}
					let g = d_info - sta.get_info();
					if g > max_gain{
						max_gain = g;
						max_stati = sta;
					}
				}		
				c.gain = max_gain;
				c.stati = max_stati;
			}
		}
	}
	
	fn get_discr_gain_and_stati(&mut self){
		let d_info = self.get_d_info();
		for c in self.cols.iter_mut(){
			if let ColType::Discr = c.t {
				let mut sta = Stati::new(c.name.clone());
				for i in 0..c.cells.len() {
					let k = &c.cells[i];
					sta.n += 1;
					fill_stati(&mut sta,k,&self.r.cells[i]);
				}
				c.gain = d_info - sta.get_info();
				c.stati = sta;
			}
		}		
	}
	
	fn get_gain_ratio(&mut self){
		self.get_conti_gain_and_stati();
		self.get_discr_gain_and_stati();
		self.get_cols_info();
		
		for c in self.cols.iter_mut() {
			if c.gain == 0.0{
				c.gain_ratio = 0.0;
				continue;
			}
			c.gain_ratio = c.gain / c.info;
		}
	}
	
	pub fn push(&mut self,v:Vec<String>){
		for s in v.iter(){
			if s == ""{
				return;
			}
		}
		for i in 0..(v.len()-1) {
			self.cols[i].cells.push(v[i].clone());
		}
		self.r.cells.push(v[v.len()-1].clone());
	}
	
	pub fn gen_col(&mut self,name:Vec<String>,t:Vec<ColType>){
		for i in 0..name.len() {
			let c = Col::new(name[i].clone(),t[i]);
			self.cols.push(c);
		}
	}
	
	pub fn new()->D{
		D{
			cols:Vec::new(),
			r:Result::new(),
			info:-1.0,
		}
	}
}

#[derive(Debug)]
pub enum NodeType {
	Name,
	Value,
}

#[derive(Debug)]
pub struct Node {
	name:String,
	child:Vec<Node>,
	t:NodeType,
}

impl Node{
	fn new(name:String,t:NodeType)->Node{
		Node{
			name,
			child:Vec::new(),
			t,
		}
	}
}

pub fn test_by_tree(node:&Node,name:&Vec<String>,t:&Vec<ColType>,v:&Vec<String>)->String{
	let mut cur_node = node;
	loop{
		if cur_node.child.len() == 0{
			break;
		}
		match cur_node.t{
			NodeType::Name=>{
				for i in 0..name.len(){
					
					if name[i] == cur_node.name{
						match t[i]{
							ColType::Conti=>{
								let vi:f32 = v[i].parse().unwrap();
								let mut ncv = cur_node.child[0].name.clone();
								ncv.remove(0);
								let vn:f32 = ncv.parse().unwrap();
								for c_n in cur_node.child.iter(){
									if c_n.name.starts_with("<"){
										if vi < vn{
											cur_node = c_n;
											break;
										}
									}else{
										if vi > vn{
											cur_node = c_n;
											break;
										}
									}
								}
							},
							ColType::Discr=>{
								let mut has = false;
								for c_n in cur_node.child.iter(){
									if c_n.name == v[i]{
										cur_node = c_n;
										has = true;
										break;
									}
								}
								if !has{
									return String::from("没有先例");
								}
							},
						}
						break;
					}
				}				
			},
			NodeType::Value=>{
				cur_node = cur_node.child.first().unwrap();
			},
		}		
	}
	cur_node.name.clone()
}

pub fn get_tree(mut d:D)->Option<Node>{
	//如果结果集中都是相同的，把这个结果做为一个node返回
	let result = d.r.cells[0].clone();
	let mut has_diff = false;
	for i in 1..d.r.cells.len(){
		if result != d.r.cells[i]{
			has_diff = true;
			break;
		}
	}
	if !has_diff{
		let nd = Node::new(d.r.cells[0].clone(),NodeType::Value);
		return Some(nd);
	}
	
	if d.cols.len()<1{
		let mut sta = Stati::new("sdjfs".to_string());
		for s in d.r.cells.iter(){
			fill_stati(&mut sta,s,&String::from(""));
		}
		let mut max = 0;
		for c in sta.child.iter(){
			if c.n > max{
				max = c.n;
			}
		}
		for c in sta.child.iter(){
			if c.n == max{
				let nd = Node::new(c.k.clone(),NodeType::Value);
				return Some(nd);
			}
		}			
	}
	
	d.get_gain_ratio();

	//取最大增益率
	let mut gr = 0.0;
	for i in d.cols.iter(){
		if i.gain_ratio > gr{
			gr = i.gain_ratio;
		}
	}
	//建node
	let mut node = None ;
	let mut m_i = 0;
	for i in 0..d.cols.len(){
		if d.cols[i].gain_ratio == gr{
			m_i = i;
			let mut nd = Node::new(d.cols[i].name.clone(),NodeType::Name);
			for st in d.cols[i].stati.child.iter(){
				let n = Node::new(st.k.clone(),NodeType::Value);
				nd.child.push(n);
			}
			node = Some(nd);
			break;
		}
	}
	
	//分D 
	if let Some(mut nd) = node{
		let mut v_d = Vec::new();//存储分开的d
		//node有几个孩子，d就分成几份
		for _j in 0..nd.child.len(){
			let di = D::new();
			v_d.push(di);
		}
		if nd.child.len() > 0{
			loop{
				//把d分完了，退出循环
				if d.cols[m_i].cells.len() == 0 {
					break;
				}
				let curr_col_val = d.cols[m_i].cells.remove(0);//分界列的第一个值
				//轮循node的每一个孩子，查找分界列的第一个值相符合的孩子，把这行数据分到与这个孩子索引相同的v_d里
				for ni in 0..nd.child.len(){
					let mut right = false;
					match d.cols[m_i].t{
						ColType::Conti=>{
							let mut cp = nd.child[ni].name.clone();
							cp.remove(0);
							let f1:f32 = cp.parse().unwrap();
							let f2:f32 = curr_col_val.parse().unwrap();
							if nd.child[ni].name.starts_with(">"){
								if f2 > f1{
									right = true;
								}
							}else{
								if f2 < f1{
									right = true;
								}
							}
						},
						ColType::Discr=>{
							if nd.child[ni].name == curr_col_val{
								right = true;
							}
						},
					}
					//把这行数据分到与这个孩子索引相同的v_d里
					if right{
						for i in 0..d.cols.len(){
							if i == m_i{
								continue;
							}
							let val = d.cols[i].cells.remove(0);
							let mut has = false;
							for ac in v_d[ni].cols.iter_mut(){
								if ac.name == d.cols[i].name {
									ac.cells.push(val.clone());
									has = true;
									break;
								}
							}
							if !has{
								let mut col = Col::new(d.cols[i].name.clone(),d.cols[i].t);
								col.cells.push(val);
								v_d[ni].cols.push(col);
							}
						}
						let r = d.r.cells.remove(0);
						v_d[ni].r.cells.push(r);
						break;
					}
				}
			}
		}
		//对每一个孩子，回调get_tree,并把得到的node追加到末尾
		for i in nd.child.iter_mut(){
			let di = v_d.remove(0);
			if let Some(n) = get_tree(di){
				i.child.push(n);
			}
		}
		return Some(nd);
	}
	None	
}

impl fmt::Display for Node{
	fn fmt(&self,f:&mut fmt::Formatter)->fmt::Result{
		write_node(self,f,0)
	}
}

fn write_node(n:&Node,f:&mut fmt::Formatter,layer:usize)->fmt::Result{
	for _i in 0..layer{
		write!(f,"\t|")?;
	}
	write!(f,"-{}\r\n",n.name)?;
	if n.child.len()>0{
		for nd in n.child.iter(){
			write_node(nd,f,layer+1)?
		}
	}
	write!(f,"")	
}

fn fill_stati(sta:&mut Stati,k1:&String,k2:&String) {
	let mut has = false;
	for mut ci in sta.child.iter_mut() {
		if ci.k == *k1 {
			ci.n += 1;
			has = true;
			if k2 != "" {
				fill_stati(&mut ci,k2,&"".to_string());
			}
			break;
		}
	}
	if !has {
		let mut s = Stati::new(k1.clone());
		s.n += 1;
		if k2 != "" {
			let mut sc = Stati::new(k2.clone());
			sc.n += 1;
			s.child.push(sc);
		}
		sta.child.push(s);
	}	
}

fn sort(v:&mut Vec<f32>) -> Vec<f32> {
	let mut r = Vec::new();
	loop {
		if v.len() == 0{
			break;
		}
		let mut min = v[0];
		for i in 1..v.len(){
			min = min.min(v[i]);
		}
		for i in 0..v.len(){
			if min == v[i]{
				r.push(v.remove(i));
				break;
			}
		}
	}
	r
}