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
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
use std::cell::RefCell;
use std::collections::{HashMap, VecDeque};
use std::rc::Rc;
use crate::menuitem::{self, MenuItem};
use crate::{flatiter, recfiltiter, reciter};
pub struct Builder<C>
where
C: Clone + Default
{
items: HashMap<String, menuitem::Builder<C>>
}
impl<C> Builder<C>
where
C: Clone + Default
{
pub fn new() -> Self {
Builder {
items: HashMap::new()
}
}
/// Add a menu item to this menu.
pub fn add(&mut self, mib: menuitem::Builder<C>) -> &mut Self {
self.items.insert(mib.miid.to_string(), mib);
self
}
pub fn build(self) -> Menu<C> {
let mut rootitems: Vec<String> = Vec::new();
let mut parents: HashMap<String, Vec<String>> = HashMap::new();
let mut menuitems: HashMap<String, Rc<RefCell<MenuItem<C>>>> =
HashMap::new();
// Iterate over all nodes to generate:
// - a map of all parent identifiers to a list of their submenu identifiers
// - a list of all menu item identifiers with no parents
for (id, mib) in self.items {
//println!("Processing miid '{}'", id);
// If this menu item builder node has a parent, then add it to the
// parent-to-children container.
// Otherwise add it to the list of root menu items.
if let Some(ref parent_id) = mib.parent {
// Make sure parent exists in dictionary of all parents and their
// subitems
if !parents.contains_key(parent_id) {
parents.insert(parent_id.to_string(), Vec::new());
}
// Get list of child node identifiers for this parent.
// This is guaranteed to exist at this point.
if let Some(idv) = parents.get_mut(parent_id) {
// Add this (child menu item identifier) to the parent's list of
// children.
idv.push(id.to_string());
}
} else {
// This item didn't specify a parent, which means that it is a root
// menu item.
rootitems.push(id.to_string());
}
// Build MenuItem object from this builder
menuitems.insert(id.to_string(), Rc::new(RefCell::new(mib.build())));
}
// At this point:
// - rootitems is a vector of all menu item identifiers that do not have
// any parents (i.e. are root items)
// - parents is a hashmap of all parent identifiers mapped to a vector of
// all child menu item identifiers.
// - menuitems is a hashmap of all menu item identifiers mapped to their
// MenuItem.
// Create a stack of parent nodes. These will be ordered so that child
// nodes will be processed before their parents (which is important
// when constructing the real tree later).
let mut q = VecDeque::new();
let mut stack = Vec::new();
// push all root nodes that are parents onto the queue
for id in &rootitems {
if parents.contains_key(id) {
q.push_back(id.clone());
}
}
// As long as the queue is not empty:
// - keep pulling nodes off it
// - push the node on to the stack
// - if the node contain children, then push then on to the queue
while let Some(id) = q.pop_back() {
// Push node on to the stack, because it has children
stack.push(id.clone());
// If node is a parent, then push its children that have children on to
// the queue
if let Some(child_ids) = parents.get(&id) {
for child_id in child_ids {
if parents.contains_key(child_id) {
q.push_back(child_id.clone());
}
}
}
}
// At this point "stack" is an stack of all parents.
// Take the nodes off the stack one by one and clone the child nodes onto
// their parents' child list.
while let Some(parent_id) = stack.pop() {
let parent = match menuitems.get(&parent_id) {
Some(parent) => parent,
None => continue
};
let child_ids = match parents.get(&parent_id) {
Some(v) => v,
None => continue
};
//println!("Adding children {:?} to parent {:?}", child_ids, parent);
for child_id in child_ids {
let child = match menuitems.get(child_id) {
Some(child) => child,
None => continue
};
//println!("Adding child {} to parent {}", child_id, parent_id);
let mut parent = parent.borrow_mut();
// Clone child node into child list.
// The order is important here, which is why the stack is ordered the
// way it is.
parent.children.push(child.borrow().clone());
//println!("{:?}", parent);
}
//println!("Parent2: {:?}\n", parent);
// Sort child items
let mut parent = parent.borrow_mut();
parent.children.sort_by(|a, b| a.order_cmp(b));
}
//println!("\nParents: {:?}\n", parents);
//println!("menuitems: {:?}\n", menuitems);
let mut rootmis = Vec::new();
// Put root nodes into root list
for root_id in rootitems {
if let Some(mi) = menuitems.get(&root_id) {
rootmis.push(mi.borrow().clone());
}
}
// sort root items
rootmis.sort_by(|a, b| a.order_cmp(b));
//println!("\nFinal: {:?}\n", rootmis);
Menu { rootlst: rootmis }
}
}
pub struct Menu<C>
where
C: Clone + Default
{
pub(crate) rootlst: Vec<MenuItem<C>>
}
impl<C> Menu<C>
where
C: Clone + Default
{
pub fn get_rootitems(&self) -> &Vec<MenuItem<C>> {
&self.rootlst
}
pub fn iter_root(&self) -> flatiter::MenuIter<C> {
flatiter::MenuIter::new(&self.rootlst)
}
pub fn iter_hier(&self) -> reciter::MenuIter<C> {
reciter::MenuIter::new(self)
}
pub fn filtiter_hier<F>(&self, p: F) -> recfiltiter::MenuIter<C, F>
where
F: Fn(&MenuItem<C>) -> bool
{
recfiltiter::MenuIter::new(self, p)
}
}
// vim: set ft=rust et sw=2 ts=2 sts=2 cinoptions=2 tw=79 :