Repository Public
1//2// SP Chat iOS3// File: SPChat-iOS/Features/Constellation/ForceLayout.swift4// Description: A small deterministic force-directed layout (repulsion, springs, centring) for the Conversation5// Constellation. A pure value type: it runs off the main thread and is tested without any view.6//7// Author: Simon-Pierre Boucher8// Contact: contact@spboucher.ai9//1011import CoreGraphics12import Foundation1314struct ForceLayout: Sendable, Equatable {15 struct Edge: Sendable, Equatable {16 var a: Int17 var b: Int18 /// Rest length of the spring, in layout points.19 var length: Double20 /// 0…1: how hard the spring pulls.21 var strength: Double22 }2324 private(set) var x: [Double]25 private(set) var y: [Double]26 private var vx: [Double]27 private var vy: [Double]28 let edges: [Edge]29 /// Nodes held in place (being dragged).30 var pinned: Set<Int> = []31 /// Simulation temperature: forces are scaled by it and it cools at every step; the layout is settled below `minAlpha`.32 private(set) var alpha: Double33 static let minAlpha = 0.01234 private let repulsion: Double35 private let decay = 0.97236 /// Pull toward the centre on each axis: a tall canvas pulls harder sideways, so the graph grows along the screen.37 private let gravityX: Double38 private let gravityY: Double3940 var count: Int { x.count }41 var isSettled: Bool { alpha < Self.minAlpha || count < 2 }42 var positions: [CGPoint] { zip(x, y).map { CGPoint(x: $0, y: $1) } }4344 /// `seed` makes the initial placement reproducible: the same graph always settles in the same shape.45 init(count: Int, edges: [Edge], seed: UInt64 = 0x5EED_C0DE, spacing: Double = 90, aspect: Double = 1) {46 (gravityX, gravityY) = Self.gravity(aspect: aspect)47 var rng = SplitMix64(state: seed)48 var xs = [Double](repeating: 0, count: count), ys = xs49 // a sunflower spiral with a little jitter: no two nodes start at the same place, nothing starts aligned50 for i in 0..<count {51 let r = spacing * 0.55 * (Double(i) + 0.5).squareRoot(), a = Double(i) * 2.39996322972865352 xs[i] = r * cos(a) + (rng.unit() - 0.5) * 653 ys[i] = r * sin(a) + (rng.unit() - 0.5) * 654 }55 x = xs; y = ys56 vx = [Double](repeating: 0, count: count); vy = vx57 self.edges = edges.filter { $0.a != $0.b && $0.a >= 0 && $0.b >= 0 && $0.a < count && $0.b < count }58 alpha = 159 repulsion = spacing * spacing * 0.960 }6162 /// Starts from given positions (a node was dragged, the data was refreshed) with a lower temperature.63 init(positions: [CGPoint], edges: [Edge], alpha: Double = 0.35, spacing: Double = 90, aspect: Double = 1) {64 (gravityX, gravityY) = Self.gravity(aspect: aspect)65 x = positions.map { Double($0.x).isFinite ? Double($0.x) : 0 }; y = positions.map { Double($0.y).isFinite ? Double($0.y) : 0 }66 vx = [Double](repeating: 0, count: positions.count); vy = vx67 let n = positions.count68 self.edges = edges.filter { $0.a != $0.b && $0.a >= 0 && $0.b >= 0 && $0.a < n && $0.b < n }69 self.alpha = alpha70 repulsion = spacing * spacing * 0.971 }7273 /// `aspect` = height / width of the canvas, clamped: 1 = square (same pull on both axes).74 private static func gravity(aspect: Double) -> (Double, Double) {75 let a = min(max(aspect.isFinite ? aspect : 1, 0.5), 2)76 return (0.012 * a.squareRoot() * (a > 1 ? a : 1), 0.012 / a.squareRoot() / (a < 1 ? a : 1))77 }7879 mutating func move(_ index: Int, to p: CGPoint) {80 guard index >= 0, index < count, p.x.isFinite, p.y.isFinite else { return }81 x[index] = Double(p.x); y[index] = Double(p.y); vx[index] = 0; vy[index] = 082 }83 mutating func reheat(_ value: Double = 0.3) { alpha = max(alpha, value) }8485 /// One iteration. O(n²) repulsion: fine for the ≤ 200 conversations the constellation shows.86 mutating func step() {87 let n = count88 guard n > 1, alpha >= Self.minAlpha else { alpha = min(alpha, Self.minAlpha * 0.5); return }89 var fx = [Double](repeating: 0, count: n), fy = fx90 for i in 0..<n {91 for j in (i + 1)..<max(i + 1, n) {92 var dx = x[i] - x[j], dy = y[i] - y[j]93 var d2 = dx * dx + dy * dy94 if d2 < 0.01 { dx = Double((i &* 31 &+ j) % 7) - 3 + 0.5; dy = Double((j &* 17 &+ i) % 5) - 2 + 0.5; d2 = dx * dx + dy * dy } // coincident nodes: a fixed nudge, never a division by zero95 let d = d2.squareRoot()96 let f = min(repulsion / d2, 40)97 let ux = dx / d, uy = dy / d98 fx[i] += ux * f; fy[i] += uy * f; fx[j] -= ux * f; fy[j] -= uy * f99 }100 // gentle pull toward the centre keeps unlinked nodes on screen101 fx[i] -= x[i] * gravityX; fy[i] -= y[i] * gravityY102 }103 for e in edges {104 let dx = x[e.b] - x[e.a], dy = y[e.b] - y[e.a]105 let d = max((dx * dx + dy * dy).squareRoot(), 0.01)106 let f = (d - e.length) * 0.06 * max(0.05, min(e.strength, 1))107 let ux = dx / d, uy = dy / d108 fx[e.a] += ux * f; fy[e.a] += uy * f; fx[e.b] -= ux * f; fy[e.b] -= uy * f109 }110 for i in 0..<n where !pinned.contains(i) {111 vx[i] = (vx[i] + fx[i] * alpha) * 0.82; vy[i] = (vy[i] + fy[i] * alpha) * 0.82112 let speed = (vx[i] * vx[i] + vy[i] * vy[i]).squareRoot()113 if speed > 28 { vx[i] *= 28 / speed; vy[i] *= 28 / speed }114 x[i] += vx[i]; y[i] += vy[i]115 }116 alpha *= decay117 }118119 /// Runs until settled (Reduce Motion: the layout is complete before the first display).120 mutating func settle(maxIterations: Int = 600) {121 var i = 0122 while !isSettled && i < maxIterations { step(); i += 1 }123 }124125 /// Bounding box of the layout (used to fit the graph in the canvas).126 var bounds: CGRect {127 guard let minX = x.min(), let maxX = x.max(), let minY = y.min(), let maxY = y.max() else { return .zero }128 return CGRect(x: minX, y: minY, width: maxX - minX, height: maxY - minY)129 }130}131132/// Small deterministic generator (the system generator is seeded differently at every launch).133struct SplitMix64: Sendable {134 var state: UInt64135 mutating func next() -> UInt64 {136 state &+= 0x9E37_79B9_7F4A_7C15137 var z = state138 z = (z ^ (z >> 30)) &* 0xBF58_476D_1CE4_E5B9139 z = (z ^ (z >> 27)) &* 0x94D0_49BB_1331_11EB140 return z ^ (z >> 31)141 }142 mutating func unit() -> Double { Double(next() >> 11) / Double(1 << 53) }143}144145extension ForceLayout {146 /// Springs of a constellation: a branch keeps parent and child close, a project groups loosely, a topic link pulls147 /// in proportion to its similarity.148 static func edges(for graph: Constellation) -> [Edge] {149 let index = Dictionary(graph.nodes.enumerated().map { ($0.element.id, $0.offset) }, uniquingKeysWith: { a, _ in a })150 return graph.links.compactMap { l in151 guard let a = index[l.source], let b = index[l.target] else { return nil }152 switch l.kind {153 case "branch": return Edge(a: a, b: b, length: 60, strength: 1)154 case "project": return Edge(a: a, b: b, length: 85, strength: 0.6)155 default: return Edge(a: a, b: b, length: 150 - 70 * min(max(l.weight, 0), 1), strength: 0.25 + 0.5 * min(max(l.weight, 0), 1))156 }157 }158 }159}160