1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
|
extern crate itertools;
use itertools::Itertools;
use std::cmp::Eq;
use std::cmp::Ordering;
use std::collections::binary_heap::BinaryHeap;
static MESSAGE: &'static str = r#"
Hello! What's going on? This is a program.
The brown fox jumped over the lazy dog.
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
\o/
"#;
#[derive(Debug, Eq, PartialEq)]
enum Tree<T> {
Leaf(i32, T),
Branch(i32, Box<Tree<T>>, Box<Tree<T>>),
}
#[derive(Debug, Eq, PartialEq)]
enum Direction { Left, Right }
fn cost<T>(t: &Tree<T>) -> i32 {
match *t {
Tree::Leaf(cost, _) => cost,
Tree::Branch(cost, _, _) => cost,
}
}
impl<T: Eq> Ord for Tree<T> {
fn cmp(&self, other: &Self) -> Ordering {
cost(other).cmp(&cost(self))
}
}
impl<T: Eq> PartialOrd for Tree<T> {
fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
Some(self.cmp(other))
}
}
fn make_path<T: Eq>(tree: &Tree<T>, elem: &T) -> Vec<Direction> {
fn find<T: Eq>(n: &Tree<T>, elem: &T) -> Option<Vec<Direction>> {
match *n {
Tree::Leaf(_, ref e) =>
if e == elem { Some(vec!()) } else { None },
Tree::Branch(_, ref left, ref right) =>
find(left.as_ref(), elem)
.map(|mut path| { path.push(Direction::Left); path })
.or(find(right.as_ref(), elem)
.map(|mut path| { path.push(Direction::Right); path})),
}
};
let mut result = find(tree, elem).unwrap();
result.reverse();
result
}
fn find_char<T: Eq+Copy>(tree: &Tree<T>, path: &[Direction]) -> Option<T> {
match (tree, path.split_first()) {
(&Tree::Branch(_, ref left, _), Some((&Direction::Left, ds))) =>
find_char(left.as_ref(), ds),
(&Tree::Branch(_, _, ref right), Some((&Direction::Right, ds))) =>
find_char(right.as_ref(), ds),
(&Tree::Leaf(_, ref c), None) => Some(*c),
_ => None
}
}
fn main() {
if MESSAGE.is_empty() {
panic!("Empty string");
}
let mut counts = MESSAGE
.chars()
.sorted().into_iter()
.group_by(|x| *x)
.map(|(elem, xs)| (elem, xs.len() as i32))
.map(|(elem, cost)| Box::new(Tree::Leaf(cost, elem)))
.collect::<BinaryHeap<_>>();
let mut left;
loop {
left = counts.pop().unwrap();
let right = match counts.pop() {
Some(right) => right,
None => break
};
counts.push(Box::new(
Tree::Branch(cost(left.as_ref()) + cost(right.as_ref()),
left, right)));
}
let restored_message = MESSAGE
.chars()
.map(|c| make_path(left.as_ref(), &c))
.flat_map(|p| find_char(left.as_ref(), &p))
.collect::<String>();
println!("{}", MESSAGE);
println!("{}", restored_message);
}
|
