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
113
114
115
116
117
|
fn main() -> Result<(), Box<dyn std::error::Error>> {
let mut file = std::fs::OpenOptions::new().read(true).open("forest.rep")?;
use std::io::Read;
let mut source: Vec<u8> = Vec::new();
file.read_to_end(&mut source)?;
use forest::bytes::BytesForest;
#[allow(unused_imports)]
use forest::iter::query::{preprocess_forest, QForest};
use graph::Graph;
let bytes_forest = BytesForest::try_from(source)?;
dbg!(
bytes_forest.nodes_len(),
bytes_forest.children_of(0)?.collect::<Vec<_>>()
);
#[cfg(feature = "test-print-viz")]
bytes_forest.print_viz("test forest.gv")?;
let preprocessed = preprocess_forest(bytes_forest, 0)?;
dbg!(&preprocessed);
use std::io::{BufRead, Write};
println!("Input a query:");
std::io::stdout().flush()?;
#[derive(Debug, Default, Copy, Clone)]
enum QueryType {
SubtreeRange(usize),
#[default]
Switches,
DFSNext(usize),
OrderToDFS(usize),
DFSToOrder(usize),
}
for line in std::io::stdin().lock().lines() {
let line = line?;
if line == "q" {
break;
}
let qtype = if line.starts_with('s') {
1u8
} else if line.starts_with('b') {
2u8
} else if line.starts_with('o') {
3u8
} else if line.starts_with('d') {
4u8
} else {
0u8
};
let type_str: &str;
let q = if line.starts_with('s') || line.starts_with('o') || line.starts_with('d') {
if let Ok(n) = line[1..].parse::<usize>() {
n
} else {
0usize
}
} else if let Ok(n) = line.parse::<usize>() {
n
} else {
continue;
};
let query: QueryType = match qtype {
0 => QueryType::DFSNext(q),
1 => QueryType::SubtreeRange(q),
2 => QueryType::default(),
3 => QueryType::OrderToDFS(q),
_ => QueryType::DFSToOrder(q),
};
let ans = match query {
QueryType::SubtreeRange(n) => {
type_str = "subtree range";
format!("{:?}", preprocessed.subtree_ranges.get(n))
}
QueryType::Switches => {
type_str = "branch switches";
format!("{:?}", preprocessed.branch_switches)
}
QueryType::DFSNext(n) => {
type_str = "dfs";
format!("{:?}", preprocessed.dfs_next.get(n).copied())
}
QueryType::OrderToDFS(n) => {
type_str = "order to dfs";
format!("{:?}", preprocessed.translate_to_dfs(n))
}
QueryType::DFSToOrder(n) => {
type_str = "dfs to order";
format!("{:?}", preprocessed.translate_from_dfs(n))
}
};
println!("answer for {type_str} = {ans}");
println!("Input a query:");
std::io::stdout().flush()?;
}
Ok(())
}
|
