Skip to content

Instantly share code, notes, and snippets.

@chriseidhof
Last active April 25, 2023 15:00
Show Gist options
  • Save chriseidhof/b5f91ca23f7b98307c066218d4b119ff to your computer and use it in GitHub Desktop.
Save chriseidhof/b5f91ca23f7b98307c066218d4b119ff to your computer and use it in GitHub Desktop.
Trees
//
// Diagrams.swift
// DiagramsSample
//
// Created by Chris Eidhof on 16.12.19.
// Copyright © 2019 objc.io. All rights reserved.
//
import SwiftUI
/// A simple Tree datastructure that holds nodes with `A` as the value.
struct Tree<A> {
var value: A
var children: [Tree<A>] = []
init(_ value: A, children: [Tree<A>] = []) {
self.value = value
self.children = children
}
}
extension Tree {
func map<B>(_ transform: (A) -> B) -> Tree<B> {
return Tree<B>(transform(value), children: children.map({ $0.map(transform) }))
}
}
class Unique<A>: Identifiable {
let value: A
init(_ value: A) { self.value = value }
}
struct CollectDict<Key: Hashable, Value>: PreferenceKey {
static var defaultValue: [Key:Value] { [:] }
static func reduce(value: inout [Key:Value], nextValue: () -> [Key:Value]) {
value.merge(nextValue(), uniquingKeysWith: { $1 })
}
}
/// This is needed to use `CGPoint` as animatable data
extension CGPoint: VectorArithmetic {
public static func -= (lhs: inout CGPoint, rhs: CGPoint) {
lhs = lhs - rhs
}
public static func - (lhs: CGPoint, rhs: CGPoint) -> CGPoint {
return CGPoint(x: lhs.x - rhs.x, y: lhs.y - rhs.y)
}
public static func += (lhs: inout CGPoint, rhs: CGPoint) {
lhs = lhs + rhs
}
public mutating func scale(by rhs: Double) {
x *= CGFloat(rhs)
y *= CGFloat(rhs)
}
public static func + (lhs: CGPoint, rhs: CGPoint) -> CGPoint {
return CGPoint(x: lhs.x + rhs.x, y: lhs.y + rhs.y)
}
public var magnitudeSquared: Double { return Double(x*x + y*y) }
}
/// Draws an edge from `from` to `to`
struct Line: Shape {
var from: CGPoint
var to: CGPoint
var animatableData: AnimatablePair<CGPoint, CGPoint> {
get { AnimatablePair(from, to) }
set {
from = newValue.first
to = newValue.second
}
}
func path(in rect: CGRect) -> Path {
Path { p in
p.move(to: self.from)
p.addLine(to: self.to)
}
}
}
/// A simple Diagram. It's not very performant yet, but works great for smallish trees.
struct Diagram<A: Identifiable, V: View>: View {
let tree: Tree<A>
let node: (A) -> V
typealias Key = CollectDict<A.ID, Anchor<CGPoint>>
var body: some View {
VStack(alignment: .center) {
node(tree.value)
.anchorPreference(key: Key.self, value: .center, transform: {
[self.tree.value.id: $0]
})
HStack(alignment: .bottom, spacing: 10) {
ForEach(tree.children, id: \.value.id, content: { child in
Diagram(tree: child, node: self.node)
})
}
}.backgroundPreferenceValue(Key.self, { (centers: [A.ID: Anchor<CGPoint>]) in
GeometryReader { proxy in
ForEach(self.tree.children, id: \.value.id, content: {
child in
Line(
from: proxy[centers[self.tree.value.id]!],
to: proxy[centers[child.value.id]!])
.stroke()
})
}
})
}
}
//
// ContentView.swift
// DiagramsSample
//
// Created by Chris Eidhof on 16.12.19.
// Copyright © 2019 objc.io. All rights reserved.
//
import SwiftUI
let binaryTree = Tree<Int>(50, children: [
Tree(17, children: [
Tree(12),
Tree(23)
]),
Tree(72, children: [
Tree(54),
Tree(72)
])
])
let uniqueTree = binaryTree.map(Unique.init)
struct RoundedCircleStyle: ViewModifier {
func body(content: Content) -> some View {
content
.frame(width: 50, height: 50)
.background(Circle().stroke())
.background(Circle().fill(Color.white))
.padding(10)
}
}
extension Tree where A == Unique<Int> {
mutating func insert(_ number: Int) {
if number < value.value {
if children.count > 0 {
children[0].insert(number)
} else {
children.append(Tree(Unique(number)))
}
} else {
if children.count == 2 {
children[1].insert(number)
} else if children.count == 1 && children[0].value.value > number {
children[0].insert(number)
} else {
children.append(Tree(Unique(number)))
}
}
}
}
struct BinaryTreeView: View {
@State var tree = uniqueTree
var body: some View {
VStack {
Button(action: {
withAnimation(.default) {
self.tree.insert(Int.random(in: 0...100))
}
}, label: { Text("Insert random number") })
Diagram(tree: tree, node: { value in
Text("\(value.value)")
.modifier(RoundedCircleStyle())
})
}
}
}
struct ContentView: View {
var body: some View {
BinaryTreeView()
}
}
struct ContentView_Previews: PreviewProvider {
static var previews: some View {
ContentView()
}
}
@dndydon
Copy link

dndydon commented Jan 1, 2020

Chris, do you know why I get error "Redundant conformance of 'CGPoint' to protocol 'VectorArithmetic'" on...

/// This is needed to use `CGPoint` as animatable data
extension CGPoint: VectorArithmetic {

?

@dndydon
Copy link

dndydon commented Jan 1, 2020

I found and fixed the problem: When I added your Gist as a file "Diagram.swift" in my project, I should not have included it in the test target. The test target was the source of the redundant conformance. A better error message is needed when this happens.

@happyjem
Copy link

happyjem commented Feb 2, 2020

I suggest the code below in RoundedCircleStyle Struct

struct RoundedCircleStyle: ViewModifier {
    func body(content: Content) -> some View {
        content
            .frame(width: 50, height: 50)
            .background(Circle().stroke())
            .background(Circle().fill(Color.white))
            .foregroundColor(Color.black) // #. add foreground code
            .padding(10)
    }
}

@naeem3d
Copy link

naeem3d commented Jan 15, 2022

Hi Chris ... Please I need help to add Child on specific node in that tree so how can I do that if i have textfield contain name of that specific node, and other textfield contain that child value and not limit children in binary ... I try to do that but I couldn't ... so please don't ignore this request I know You can do it.... Thanks for help

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment