| 1 | use crate::geom::{Change, Rect}; |
| 2 | use crate::strategy::plan_group; |
| 3 | |
| 4 | #[derive(Clone, Copy, Debug, PartialEq, Eq)] |
| 5 | pub enum Style { |
| 6 | /// Every window moves or resizes along one axis per phase. |
| 7 | Orthogonal, |
| 8 | /// Windows may change both axes in one phase when no pair loses its separation. |
| 9 | Direct, |
| 10 | } |
| 11 | |
| 12 | #[derive(Clone, Copy, Debug, PartialEq)] |
| 13 | pub struct Config { |
| 14 | pub style: Style, |
| 15 | /// Gap between tiled windows. Neighbours closer than this are adjacent. |
| 16 | pub gap: f64, |
| 17 | /// Tolerance for separation and adjacency tests. |
| 18 | pub eps: f64, |
| 19 | /// Lanes thinner than this are not used. |
| 20 | pub min_lane: f64, |
| 21 | } |
| 22 | |
| 23 | impl Default for Config { |
| 24 | fn default() -> Self { |
| 25 | Self { |
| 26 | style: Style::Orthogonal, |
| 27 | gap: 10.0, |
| 28 | eps: 0.5, |
| 29 | min_lane: 6.0, |
| 30 | } |
| 31 | } |
| 32 | } |
| 33 | |
| 34 | #[derive(Clone, Copy, Debug, PartialEq, Eq)] |
| 35 | pub enum Strategy { |
| 36 | Unchanged, |
| 37 | Direct, |
| 38 | AxisOrder, |
| 39 | Lanes { lanes: usize }, |
| 40 | Grid { cells: usize }, |
| 41 | Pinch, |
| 42 | } |
| 43 | |
| 44 | /// Windows that plan together. Groups never touch each other while moving. |
| 45 | #[derive(Clone, Debug, PartialEq)] |
| 46 | pub struct Group { |
| 47 | pub members: Vec<usize>, |
| 48 | pub strategy: Strategy, |
| 49 | pub phases: usize, |
| 50 | /// Whether the plan briefly separates two neighbours that touch at both ends. |
| 51 | pub opens_hole: bool, |
| 52 | } |
| 53 | |
| 54 | /// Keyframe layouts indexed like the input. Every phase lasts the same time |
| 55 | /// and every window in a group moves on that group's curve. |
| 56 | #[derive(Clone, Debug, PartialEq)] |
| 57 | pub struct Plan { |
| 58 | pub keyframes: Vec<Vec<Rect>>, |
| 59 | pub groups: Vec<Group>, |
| 60 | } |
| 61 | |
| 62 | impl Plan { |
| 63 | pub fn phases(&self) -> usize { |
| 64 | self.keyframes.len().saturating_sub(1) |
| 65 | } |
| 66 | |
| 67 | /// Window positions at `phase` with eased progress `s`. |
| 68 | pub fn sample(&self, phase: usize, s: f64) -> Vec<Rect> { |
| 69 | match (self.keyframes.get(phase), self.keyframes.get(phase + 1)) { |
| 70 | (Some(a), Some(b)) => a.iter().zip(b).map(|(a, b)| a.lerp(b, s)).collect(), |
| 71 | _ => self.keyframes.last().cloned().unwrap_or_default(), |
| 72 | } |
| 73 | } |
| 74 | } |
| 75 | |
| 76 | pub(crate) struct GroupPlan { |
| 77 | pub keys: Vec<Vec<Rect>>, |
| 78 | pub strategy: Strategy, |
| 79 | pub opens_hole: bool, |
| 80 | } |
| 81 | |
| 82 | impl GroupPlan { |
| 83 | pub fn reversed(mut self) -> Self { |
| 84 | self.keys.reverse(); |
| 85 | self |
| 86 | } |
| 87 | } |
| 88 | |
| 89 | /// Plans the transition from `from` to `to`. Both slices index the same windows. |
| 90 | /// When some windows appear while others vanish in the same place, no single |
| 91 | /// set of phases keeps them apart, so the vanishing ones finish first. |
| 92 | pub fn plan(from: &[Rect], to: &[Rect], cfg: &Config) -> Plan { |
| 93 | let direct = plan_once(from, to, cfg); |
| 94 | if !direct.groups.iter().any(|g| g.strategy == Strategy::Pinch) { |
| 95 | return direct; |
| 96 | } |
| 97 | staged(from, to, cfg).unwrap_or(direct) |
| 98 | } |
| 99 | |
| 100 | /// Plans everything but the windows that appear, then lets those grow. |
| 101 | /// A window that appears from a seed sits inside the space a vanishing one |
| 102 | /// still fills, and the exact overlap check rejects growing into it. |
| 103 | fn staged(from: &[Rect], to: &[Rect], cfg: &Config) -> Option<Plan> { |
| 104 | let appears = |i: usize| is_empty(&from[i], cfg) && !is_empty(&to[i], cfg); |
| 105 | if !(0..from.len()).any(appears) { |
| 106 | return None; |
| 107 | } |
| 108 | let mid: Vec<Rect> = (0..from.len()) |
| 109 | .map(|i| if appears(i) { from[i] } else { to[i] }) |
| 110 | .collect(); |
| 111 | let (first, second) = (plan_once(from, &mid, cfg), plan_once(&mid, to, cfg)); |
| 112 | let groups: Vec<Group> = first.groups.into_iter().chain(second.groups).collect(); |
| 113 | if groups.iter().any(|g| g.strategy == Strategy::Pinch) { |
| 114 | return None; |
| 115 | } |
| 116 | let mut keyframes = first.keyframes; |
| 117 | keyframes.extend(second.keyframes.into_iter().skip(1)); |
| 118 | Some(Plan { keyframes, groups }) |
| 119 | } |
| 120 | |
| 121 | fn is_empty(r: &Rect, cfg: &Config) -> bool { |
| 122 | r.w <= cfg.eps || r.h <= cfg.eps |
| 123 | } |
| 124 | |
| 125 | /// Windows with no area at either end, like hidden ones held at their seed, |
| 126 | /// jump straight to `to`. Planning them would let an invisible point inside |
| 127 | /// a visible window join its group, or block every strategy and pinch. |
| 128 | fn plan_once(from: &[Rect], to: &[Rect], cfg: &Config) -> Plan { |
| 129 | assert_eq!( |
| 130 | from.len(), |
| 131 | to.len(), |
| 132 | "layouts must describe the same windows" |
| 133 | ); |
| 134 | let live: Vec<usize> = (0..from.len()) |
| 135 | .filter(|&i| !(is_empty(&from[i], cfg) && is_empty(&to[i], cfg))) |
| 136 | .collect(); |
| 137 | if live.len() == from.len() { |
| 138 | return plan_live(from, to, cfg); |
| 139 | } |
| 140 | let pick = |rects: &[Rect]| live.iter().map(|&i| rects[i]).collect::<Vec<_>>(); |
| 141 | let inner = plan_live(&pick(from), &pick(to), cfg); |
| 142 | let keyframes = inner |
| 143 | .keyframes |
| 144 | .iter() |
| 145 | .map(|key| { |
| 146 | let mut frame = to.to_vec(); |
| 147 | for (k, &i) in live.iter().enumerate() { |
| 148 | frame[i] = key[k]; |
| 149 | } |
| 150 | frame |
| 151 | }) |
| 152 | .collect(); |
| 153 | let groups = inner |
| 154 | .groups |
| 155 | .into_iter() |
| 156 | .map(|g| Group { |
| 157 | members: g.members.iter().map(|&k| live[k]).collect(), |
| 158 | ..g |
| 159 | }) |
| 160 | .collect(); |
| 161 | Plan { keyframes, groups } |
| 162 | } |
| 163 | |
| 164 | fn plan_live(from: &[Rect], to: &[Rect], cfg: &Config) -> Plan { |
| 165 | let mut groups = Vec::new(); |
| 166 | let mut plans = Vec::new(); |
| 167 | for members in motion_groups(from, to, cfg) { |
| 168 | let f: Vec<Rect> = members.iter().map(|&i| from[i]).collect(); |
| 169 | let t: Vec<Rect> = members.iter().map(|&i| to[i]).collect(); |
| 170 | let gp = plan_canonical(&f, &t, cfg); |
| 171 | groups.push(Group { |
| 172 | members: members.clone(), |
| 173 | strategy: gp.strategy, |
| 174 | phases: gp.keys.len() - 1, |
| 175 | opens_hole: gp.opens_hole, |
| 176 | }); |
| 177 | plans.push((members, gp)); |
| 178 | } |
| 179 | let phases = groups.iter().map(|g| g.phases).max().unwrap_or(0); |
| 180 | let mut keyframes = vec![to.to_vec(); phases + 1]; |
| 181 | for (members, gp) in &plans { |
| 182 | for (k, frame) in keyframes.iter_mut().enumerate() { |
| 183 | let key = &gp.keys[k.min(gp.keys.len() - 1)]; |
| 184 | for (local, &i) in members.iter().enumerate() { |
| 185 | frame[i] = key[local]; |
| 186 | } |
| 187 | } |
| 188 | } |
| 189 | Plan { keyframes, groups } |
| 190 | } |
| 191 | |
| 192 | /// Plans in one fixed direction per pair of layouts, so planning back plays |
| 193 | /// the same plan in reverse. |
| 194 | pub(crate) fn plan_canonical(from: &[Rect], to: &[Rect], cfg: &Config) -> GroupPlan { |
| 195 | if canonical_order(from, to).is_le() { |
| 196 | plan_group(from, to, cfg) |
| 197 | } else { |
| 198 | plan_group(to, from, cfg).reversed() |
| 199 | } |
| 200 | } |
| 201 | |
| 202 | fn canonical_order(a: &[Rect], b: &[Rect]) -> std::cmp::Ordering { |
| 203 | let q = |v: f64| (v * 10.0).round() as i64; |
| 204 | let key = |r: &Rect| [q(r.x), q(r.y), q(r.w), q(r.h)]; |
| 205 | a.iter().map(key).cmp(b.iter().map(key)) |
| 206 | } |
| 207 | |
| 208 | /// Partitions windows so that windows in different groups can never meet. |
| 209 | /// A moving window joins every window its swept area comes within a gap of. |
| 210 | fn motion_groups(from: &[Rect], to: &[Rect], cfg: &Config) -> Vec<Vec<usize>> { |
| 211 | let n = from.len(); |
| 212 | let swept: Vec<Rect> = (0..n) |
| 213 | .map(|i| Rect::bounding([&from[i], &to[i]]).expanded(cfg.gap / 2.0 + cfg.eps)) |
| 214 | .collect(); |
| 215 | let moves: Vec<bool> = (0..n) |
| 216 | .map(|i| Change::between(&from[i], &to[i]).moves()) |
| 217 | .collect(); |
| 218 | let mut parent: Vec<usize> = (0..n).collect(); |
| 219 | fn find(parent: &mut [usize], mut i: usize) -> usize { |
| 220 | while parent[i] != i { |
| 221 | parent[i] = parent[parent[i]]; |
| 222 | i = parent[i]; |
| 223 | } |
| 224 | i |
| 225 | } |
| 226 | for i in 0..n { |
| 227 | for j in i + 1..n { |
| 228 | if (moves[i] || moves[j]) && swept[i].intersects(&swept[j]) { |
| 229 | let (a, b) = (find(&mut parent, i), find(&mut parent, j)); |
| 230 | parent[a] = b; |
| 231 | } |
| 232 | } |
| 233 | } |
| 234 | let mut groups: Vec<Vec<usize>> = Vec::new(); |
| 235 | let mut slot = vec![usize::MAX; n]; |
| 236 | for i in 0..n { |
| 237 | let root = find(&mut parent, i); |
| 238 | if slot[root] == usize::MAX { |
| 239 | slot[root] = groups.len(); |
| 240 | groups.push(Vec::new()); |
| 241 | } |
| 242 | groups[slot[root]].push(i); |
| 243 | } |
| 244 | groups |
| 245 | } |