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
//! Types and functionality related to the calculation of a **Graph**'s rendering depth order.
use super::{Graph, Node};
use daggy::Walker;
use fnv;
use std;
use widget;
/// Contains Node indices in order of depth, starting with the deepest.
#[derive(Debug)]
pub struct DepthOrder {
/// The primary **Vec** storing the **DepthOrder**'s ordered indices.
pub indices: Vec<widget::Id>,
/// Used for storing indices of "floating" widgets during depth sorting so that they may be
/// visited after widgets of the root tree.
floating: Vec<widget::Id>,
}
impl DepthOrder {
/// Construct a new empty **DepthOrder**.
pub fn new() -> DepthOrder {
DepthOrder {
indices: Vec::new(),
floating: Vec::new(),
}
}
/// Construct a new empty **DepthOrder**.
///
/// There can be at most two indices per widget (the widget and the widget's scrollbar). Thus
/// we'll reserve double the number of nodes given.
pub fn with_node_capacity(n_nodes: usize) -> DepthOrder {
let n_indices = n_nodes * 2;
DepthOrder {
indices: Vec::with_capacity(n_indices),
floating: Vec::with_capacity(n_nodes),
}
}
/// Update the **DepthOrder** (starting with the deepest) for all nodes in the given **Graph**.
///
/// FIXME:
/// This likely needs to be re-written, and will probably fail for graphs with many floating
/// widgets instantiated upon other floating widgets.
///
/// The proper algorithm should be a full toposort where the neighbours of each node are
/// visited in the order specified within `visit_by_depth`.
///
/// The `visit_by_depth` algorithm should not be recursive and instead use either looping,
/// walking or iteration.
pub fn update(
&mut self,
graph: &Graph,
root: widget::Id,
updated_widgets: &fnv::FnvHashSet<widget::Id>,
) {
let DepthOrder {
ref mut indices,
ref mut floating,
} = *self;
// Clear the buffers and ensure they've enough memory allocated.
let num_nodes = graph.node_count();
indices.clear();
indices.reserve(num_nodes);
floating.clear();
floating.reserve(num_nodes);
// Visit each node in order of depth and add their indices to depth_order.
// If the widget is floating, then store it in the floating deque instead.
visit_by_depth(graph, root, updated_widgets, indices, floating);
// Sort the floating widgets so that the ones clicked last come last.
floating.sort_by(|&a, &b| match (&graph[a], &graph[b]) {
(&Node::Widget(ref a), &Node::Widget(ref b)) => {
let a_floating = a.maybe_floating.expect("Not floating");
let b_floating = b.maybe_floating.expect("Not floating");
a_floating
.time_last_clicked
.cmp(&b_floating.time_last_clicked)
}
_ => std::cmp::Ordering::Equal,
});
// Visit all of the floating widgets last.
while !floating.is_empty() {
let idx = floating.remove(0);
visit_by_depth(graph, idx, updated_widgets, indices, floating);
}
}
}
/// Recursive function for visiting all nodes within the dag.
fn visit_by_depth(
graph: &Graph,
idx: widget::Id,
updated_widgets: &fnv::FnvHashSet<widget::Id>,
depth_order: &mut Vec<widget::Id>,
floating_deque: &mut Vec<widget::Id>,
) {
// First, if the current node is a widget and it was set in the current `set_widgets` stage,
// store its index.
match graph.widget(idx).is_some() && updated_widgets.contains(&idx) {
true => depth_order.push(idx),
// If the current node is not an updated widget, we're done with this branch.
false => return,
}
// Sort the children of the current node by their `.depth` members.
// FIXME: We should remove these allocations by storing a `child_sorter` buffer in each Widget
// node (perhaps in the `Container`).
let mut child_sorter: Vec<widget::Id> =
graph.depth_children(idx).iter(&graph).nodes().collect();
child_sorter.sort_by(|&a, &b| {
use std::cmp::Ordering;
if let (&Node::Widget(ref a), &Node::Widget(ref b)) = (&graph[a], &graph[b]) {
match b.depth.partial_cmp(&a.depth).expect("Depth was NaN!") {
Ordering::Equal => a.instantiation_order_idx.cmp(&b.instantiation_order_idx),
ordering => ordering,
}
} else {
Ordering::Equal
}
});
// Then, visit each of the child widgets. If we come across any floating widgets, we'll store
// those in the floating deque so that we can visit them following the current tree.
for child_idx in child_sorter.into_iter() {
// Determine whether or not the node is a floating widget.
let maybe_is_floating = graph.widget(child_idx).map(|w| w.maybe_floating.is_some());
// Store floating widgets int he floating_deque for visiting after the current tree.
match maybe_is_floating {
Some(true) => floating_deque.push(child_idx),
_ => visit_by_depth(
graph,
child_idx,
updated_widgets,
depth_order,
floating_deque,
),
}
}
}