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
106
107
108
109
110
111
112
|
use std::collections::HashMap;
/// According to the protobuf specifications, 2^29-1 is the largest field number allowed.
/// 1 is the smallest field number allowed.
const MAX_FIELD_NUMBER: i32 = 536_870_911;
const PROTOBUF_TYPES: &[&'static str] = &[
"double", "float", "int32", "int64", "uint32", "uint64", "sint64", "fixed32", "fixed64",
"sfixed32", "sfixed64", "bool", "string", "bytes",
];
/// According to protobuf specifications,
/// fields 19000 thru 19999 are used by the compiler
/// and are therefore illegal.
fn field_number_is_illegal(n: i32) -> bool {
19000 <= n && n <= 19999 || n <= 0
}
fn init_memo() -> HashMap<i32, i32> {
let mut memo = HashMap::new();
memo.insert(0, 0);
memo.insert(1, 1);
memo
}
fn fib(n: i32, memo: &mut HashMap<i32, i32>) -> Option<i32> {
if let Some(number) = memo.get(&n) {
return Some(*number);
}
let f_n = memo.get(&(n - 1))? + memo.get(&(n - 2))?;
memo.insert(n, f_n);
Some(f_n)
}
fn format_submessage(n: i32, memo: &mut HashMap<i32, i32>, name: &str) -> String {
let number = fib(n, memo);
match number {
None => String::new(),
Some(number) => {
if field_number_is_illegal(number) {
String::new()
} else {
format!(" Fibonacci{} {} = {};\n", n, name, number)
}
}
}
}
fn message_frame(n: i32, memo: &mut HashMap<i32, i32>) -> String {
let n_0 = fib(n, memo)
.map(|number| {
if field_number_is_illegal(number) {
format!(
" // There should be a fibonacci number here, but {} is illegal",
number
)
} else {
// Pick a semi-random type for the fib field
let type_name = PROTOBUF_TYPES[number as usize % PROTOBUF_TYPES.len()];
format!(" {} number = {};", type_name, number)
}
})
.unwrap_or_default();
let (n_minus_2, n_minus_1) = if n == 3 {
(String::new(), format_submessage(n - 1, memo, "prev"))
} else if n != 2 {
(
format_submessage(n - 2, memo, "prevprev"),
format_submessage(n - 1, memo, "prev"),
)
} else {
(String::new(), String::new())
};
format!(
"message Fibonacci{} {{\n\
{}{}{}
}}",
n, n_minus_2, n_minus_1, n_0
)
}
fn main() {
let mut memo = init_memo();
let mut i = 1;
println!("syntax = \"proto3\";\n");
loop {
if fib(i, &mut memo) >= Some(MAX_FIELD_NUMBER) {
break;
}
println!("{}\n", message_frame(i, &mut memo));
i += 1;
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test_small_fibs() {
let mut memo = init_memo();
assert_eq!(fib(0, &mut memo), Some(0));
assert_eq!(fib(1, &mut memo), Some(1));
assert_eq!(fib(2, &mut memo), Some(1));
assert_eq!(fib(3, &mut memo), Some(2));
assert_eq!(fib(4, &mut memo), Some(3));
assert_eq!(fib(5, &mut memo), Some(5));
}
}
|
