huffman_tree 0.1.0

//! #哈夫曼树相关功能
//!
//!

struct HuffmanNode {
	ch:char,
	weight: usize,
	parent: usize,
	lchild: usize,
	rchild: usize,
}

impl HuffmanNode {
	fn new(ch:char,weight:usize,parent:usize,lchild:usize,rchild:usize) ->HuffmanNode{
		HuffmanNode{
			ch,
			weight,
			parent,
			lchild,
			rchild,
		}
	}
}

pub struct HuffmanTree {
	data:Vec<HuffmanNode>,
	leaf_num:usize,
}

impl HuffmanTree{
	
	fn set_parent(&mut self,index:usize,parent:usize){
		self.data[index].parent = parent;
	}

	fn push(&mut self,node:HuffmanNode){
		self.data.push(node);
	}
	
	fn len(&self) -> usize{
		self.data.len()
	}
	
	fn get_parent(&self,index:usize)->usize{
		self.data[index].parent
	}
	
	fn get_ch(&self,index:usize)->char{
		self.data[index].ch
	}	
	
	fn get_weight(&self,index:usize)->usize{
		self.data[index].weight
	}
	
	fn get_ch_index(&self,ch:char)->usize{
		let mut i = 0;
		for item in self.data.iter(){
			if item.ch == ch{
				return i;
			}
			i += 1;
		}
		0
	}
	
	fn get_lchild(&self,index:usize)->usize{
		self.data[index].lchild
	}
	
	fn get_rchild(&self,index:usize)->usize{
		self.data[index].rchild
	}	
	
	/// 建立哈夫曼树，
	/// c是字符的列表，w是相应的权重
	pub fn create(c:&Vec<char>,w:&Vec<usize>) -> HuffmanTree{
		let mut n = c.len();
		if w.len() < n{
			n = w.len();
		}
		let mut tree = HuffmanTree{
			data:Vec::new(),
			leaf_num:n,
		};		
		if n <=1 {
			return tree;
		}
		
		//留着这个索引0，给parent,lchild,rchild用，以表示没有
		tree.push(HuffmanNode::new('🐅',0,0,0,0));
		for i in 0..n{
			let node = HuffmanNode::new(c[i],w[i],0,0,0);
			tree.push(node);
		}
		
		loop{
			let mut s1=0;
			let mut weight = usize::MAX;
			for i in 1..(tree.len()){
				if tree.get_parent(i) == 0 && tree.get_weight(i) < weight {
					weight = tree.get_weight(i);
					s1 = i;
				}
			}
			weight = usize::MAX;
			let mut s2 = 0;
			for i in 1..(tree.len()){
				if tree.get_parent(i) == 0 && i != s1 && tree.get_weight(i) < weight {
					weight = tree.get_weight(i);
					s2 = i;
				}
			}	
			if s2 == 0{
					break;
			}
			
			let the_i = tree.len();
			tree.set_parent(s1,the_i);
			tree.set_parent(s2,the_i);
			let node = HuffmanNode::new('🐅',tree.get_weight(s1) + tree.get_weight(s2),0,s2,s1);
			tree.push(node);
		}
		
		tree
	}
}

/// # 根据给定的哈夫曼树，从每个叶子节点出发追溯到树根，逆向找出二叉树中叶子节点的编码
pub fn encoding(tree:&HuffmanTree,buff:&String)->String{
	let mut code = String::from("");
	if tree.leaf_num <=1 {
		return code;
	}
	let mut chars = buff.chars();
	while let Some(cha) = chars.next(){
		
		let mut c = tree.get_ch_index(cha);
		let mut f = tree.get_parent(c);
		let mut cd = String::from("");
		loop{
			if tree.get_lchild(f) == c{
				cd.insert(0,'0');
			}else{
				cd.insert(0,'1');
			}
			c = f;
			f = tree.get_parent(f);
			if f == 0{
				break;
			}
		}
		code.push_str(&cd);
	}
	code
}

/// 利用具有n个节点的最优二叉树进行译码，叶子的下标为1-n，
///buff是二进制位串编码序列
pub fn decoding(tree:&HuffmanTree,buff:&String)->String{
	let mut st = String::from("");
	let mut p = 2 * tree.leaf_num - 1;
	for i in 0..(buff.len()){
		let c = &buff[i..(i+1)];
		if c == "0" {
			p = tree.get_lchild(p);
		}else{
			p = tree.get_rchild(p);
		}
		if tree.get_lchild(p) == 0 && tree.get_rchild(p) == 0{
			st.push(tree.get_ch(p));
			p = 2 * tree.leaf_num - 1;
		}
	}
	st
}

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