| 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 | /// Windows with no area at either end, like hidden ones held at their seed, |
| 91 | /// jump straight to `to`. Planning them would let an invisible point inside |
| 92 | /// a visible window join its group, or block every strategy and pinch. |
| 93 | pub fn plan(from: &[Rect], to: &[Rect], cfg: &Config) -> Plan { |
| 94 | assert_eq!( |
| 95 | from.len(), |
| 96 | to.len(), |
| 97 | "layouts must describe the same windows" |
| 98 | ); |
| 99 | let empty = |r: &Rect| r.w <= cfg.eps || r.h <= cfg.eps; |
| 100 | let live: Vec<usize> = (0..from.len()) |
| 101 | .filter(|&i| !(empty(&from[i]) && empty(&to[i]))) |
| 102 | .collect(); |
| 103 | if live.len() == from.len() { |
| 104 | return plan_live(from, to, cfg); |
| 105 | } |
| 106 | let pick = |rects: &[Rect]| live.iter().map(|&i| rects[i]).collect::<Vec<_>>(); |
| 107 | let inner = plan_live(&pick(from), &pick(to), cfg); |
| 108 | let keyframes = inner |
| 109 | .keyframes |
| 110 | .iter() |
| 111 | .map(|key| { |
| 112 | let mut frame = to.to_vec(); |
| 113 | for (k, &i) in live.iter().enumerate() { |
| 114 | frame[i] = key[k]; |
| 115 | } |
| 116 | frame |
| 117 | }) |
| 118 | .collect(); |
| 119 | let groups = inner |
| 120 | .groups |
| 121 | .into_iter() |
| 122 | .map(|g| Group { |
| 123 | members: g.members.iter().map(|&k| live[k]).collect(), |
| 124 | ..g |
| 125 | }) |
| 126 | .collect(); |
| 127 | Plan { keyframes, groups } |
| 128 | } |
| 129 | |
| 130 | fn plan_live(from: &[Rect], to: &[Rect], cfg: &Config) -> Plan { |
| 131 | let mut groups = Vec::new(); |
| 132 | let mut plans = Vec::new(); |
| 133 | for members in motion_groups(from, to, cfg) { |
| 134 | let f: Vec<Rect> = members.iter().map(|&i| from[i]).collect(); |
| 135 | let t: Vec<Rect> = members.iter().map(|&i| to[i]).collect(); |
| 136 | let gp = plan_canonical(&f, &t, cfg); |
| 137 | groups.push(Group { |
| 138 | members: members.clone(), |
| 139 | strategy: gp.strategy, |
| 140 | phases: gp.keys.len() - 1, |
| 141 | opens_hole: gp.opens_hole, |
| 142 | }); |
| 143 | plans.push((members, gp)); |
| 144 | } |
| 145 | let phases = groups.iter().map(|g| g.phases).max().unwrap_or(0); |
| 146 | let mut keyframes = vec![to.to_vec(); phases + 1]; |
| 147 | for (members, gp) in &plans { |
| 148 | for (k, frame) in keyframes.iter_mut().enumerate() { |
| 149 | let key = &gp.keys[k.min(gp.keys.len() - 1)]; |
| 150 | for (local, &i) in members.iter().enumerate() { |
| 151 | frame[i] = key[local]; |
| 152 | } |
| 153 | } |
| 154 | } |
| 155 | Plan { keyframes, groups } |
| 156 | } |
| 157 | |
| 158 | /// Plans in one fixed direction per pair of layouts, so planning back plays |
| 159 | /// the same plan in reverse. |
| 160 | pub(crate) fn plan_canonical(from: &[Rect], to: &[Rect], cfg: &Config) -> GroupPlan { |
| 161 | if canonical_order(from, to).is_le() { |
| 162 | plan_group(from, to, cfg) |
| 163 | } else { |
| 164 | plan_group(to, from, cfg).reversed() |
| 165 | } |
| 166 | } |
| 167 | |
| 168 | fn canonical_order(a: &[Rect], b: &[Rect]) -> std::cmp::Ordering { |
| 169 | let q = |v: f64| (v * 10.0).round() as i64; |
| 170 | let key = |r: &Rect| [q(r.x), q(r.y), q(r.w), q(r.h)]; |
| 171 | a.iter().map(key).cmp(b.iter().map(key)) |
| 172 | } |
| 173 | |
| 174 | /// Partitions windows so that windows in different groups can never meet. |
| 175 | /// A moving window joins every window its swept area comes within a gap of. |
| 176 | fn motion_groups(from: &[Rect], to: &[Rect], cfg: &Config) -> Vec<Vec<usize>> { |
| 177 | let n = from.len(); |
| 178 | let swept: Vec<Rect> = (0..n) |
| 179 | .map(|i| Rect::bounding([&from[i], &to[i]]).expanded(cfg.gap / 2.0 + cfg.eps)) |
| 180 | .collect(); |
| 181 | let moves: Vec<bool> = (0..n) |
| 182 | .map(|i| Change::between(&from[i], &to[i]).moves()) |
| 183 | .collect(); |
| 184 | let mut parent: Vec<usize> = (0..n).collect(); |
| 185 | fn find(parent: &mut [usize], mut i: usize) -> usize { |
| 186 | while parent[i] != i { |
| 187 | parent[i] = parent[parent[i]]; |
| 188 | i = parent[i]; |
| 189 | } |
| 190 | i |
| 191 | } |
| 192 | for i in 0..n { |
| 193 | for j in i + 1..n { |
| 194 | if (moves[i] || moves[j]) && swept[i].intersects(&swept[j]) { |
| 195 | let (a, b) = (find(&mut parent, i), find(&mut parent, j)); |
| 196 | parent[a] = b; |
| 197 | } |
| 198 | } |
| 199 | } |
| 200 | let mut groups: Vec<Vec<usize>> = Vec::new(); |
| 201 | let mut slot = vec![usize::MAX; n]; |
| 202 | for i in 0..n { |
| 203 | let root = find(&mut parent, i); |
| 204 | if slot[root] == usize::MAX { |
| 205 | slot[root] = groups.len(); |
| 206 | groups.push(Vec::new()); |
| 207 | } |
| 208 | groups[slot[root]].push(i); |
| 209 | } |
| 210 | groups |
| 211 | } |