Improve Event Processing Efficiency

[MrGVSV]

The Problem

Currently, when processing events we iterate through every node in the tree using down_iter:

kayak_ui/kayak_core/src/context.rs

Line 277 in a068b4a

for index in self.widget_manager.node_tree.down_iter() {

And even with #43, we still iterate through every node:

kayak_ui/kayak_core/src/event_dispatcher.rs

Lines 147 to 149 in 63d62f2

	let mut stack: Vec<TreeNode> = vec![(root, 0)];
	while stack.len() > 0 {
	let (current, depth) = stack.pop().unwrap();

This could be much more efficient if we could smartly recurse down the tree, skipping nodes we don't need to process. Additionally, the only events that actually need to process individual nodes (as of now) are Cursor events. Keyboard and Focus events either happen on a single, known node (the focused node) or are invoked from a Cursor event.

The Issue with Smart Recursion

The main issue with performing a smart recursion down the tree for a Cursor event is that we don't always know if a parent's layout contains a descendant's. For example, a child node may overflow the parent's actual bounding box. For self-directed nodes, the parent could even have no width or height since self-directed nodes don't contribute to a parent's layout.

This is an issue because we can't just recursively select the child node that contains the cursor: we don't know if its descendants will contain it or if its actually within another part of the tree entirely.

A Possible Solution

One possible solution would be to manage a spatial hash of some type, such as a quad-tree, for the nodes. This would cache the layout of every node, allowing fast read-access when determining which nodes contain a specified point. However, it comes at the cost of additional memory overhead. It might also be an issue with animations where a layout could change very quickly in a short period of time, requiring lots of updates to the tree.

Other solutions/suggestions are welcome!