Introduce `keyed::Column` widget

1 files changed, 82 insertions, 0 deletions

diff --git a/core/src/widget/tree.rs b/core/src/widget/tree.rs
index 0af40c33..202cca9a 100644
--- a/core/src/widget/tree.rs
+++ b/core/src/widget/tree.rs
@@ -107,6 +107,88 @@ impl Tree {
     }
 }
 
+/// Reconciliates the `current_children` with the provided list of widgets using
+/// custom logic both for diffing and creating new widget state.
+///
+/// The algorithm will try to minimize the impact of diffing by querying the
+/// `maybe_changed` closure.
+pub fn diff_children_custom_with_search<T>(
+    current_children: &mut Vec<Tree>,
+    new_children: &[T],
+    diff: impl Fn(&mut Tree, &T),
+    maybe_changed: impl Fn(usize) -> bool,
+    new_state: impl Fn(&T) -> Tree,
+) {
+    if new_children.is_empty() {
+        current_children.clear();
+        return;
+    }
+
+    if current_children.is_empty() {
+        current_children.extend(new_children.iter().map(new_state));
+        return;
+    }
+
+    let first_maybe_changed = maybe_changed(0);
+    let last_maybe_changed = maybe_changed(current_children.len() - 1);
+
+    if current_children.len() > new_children.len() {
+        if !first_maybe_changed && last_maybe_changed {
+            current_children.truncate(new_children.len());
+        } else {
+            let difference_index = if first_maybe_changed {
+                0
+            } else {
+                (1..current_children.len())
+                    .find(|&i| maybe_changed(i))
+                    .unwrap_or(0)
+            };
+
+            let _ = current_children.splice(
+                difference_index
+                    ..difference_index
+                        + (current_children.len() - new_children.len()),
+                std::iter::empty(),
+            );
+        }
+    }
+
+    if current_children.len() < new_children.len() {
+        let first_maybe_changed = maybe_changed(0);
+        let last_maybe_changed = maybe_changed(current_children.len() - 1);
+
+        if !first_maybe_changed && last_maybe_changed {
+            current_children.extend(
+                new_children[current_children.len()..].iter().map(new_state),
+            );
+        } else {
+            let difference_index = if first_maybe_changed {
+                0
+            } else {
+                (1..current_children.len())
+                    .find(|&i| maybe_changed(i))
+                    .unwrap_or(0)
+            };
+
+            let _ = current_children.splice(
+                difference_index..difference_index,
+                new_children[difference_index
+                    ..difference_index
+                        + (new_children.len() - current_children.len())]
+                    .iter()
+                    .map(new_state),
+            );
+        }
+    }
+
+    // TODO: Merge loop with extend logic (?)
+    for (child_state, new) in
+        current_children.iter_mut().zip(new_children.iter())
+    {
+        diff(child_state, new);
+    }
+}
+
 /// The identifier of some widget state.
 #[derive(Debug, Clone, Copy, PartialOrd, Ord, PartialEq, Eq, Hash)]
 pub struct Tag(any::TypeId);