29:null 2a:["$","title",null,{"children":"Tom in the DOM, a story about tree structures reconciliation | Mathieu Jouhet | Observable"}] 2f:T4b5,One way we can try to do this, is by animating nodes from their previous size to the next one, so when a Node content is updated, it shifts its siblings. The idea is similar to the [FLIP animation approach](https://css-tricks.com/animating-layouts-with-the-flip-technique/): - we store the previous size - get the target size, here we use a [`ResizeObserver`](https://developer.mozilla.org/en-US/docs/Web/API/ResizeObserver) for this - set dynamic animation keyframes using the [WebAnimation API `animate` method](https://developer.mozilla.org/fr/docs/Web/API/Element/animate) In the demo below, we have a quite naive html tree renderer, with the basic layout being done through css flex. When updating the tree, we react **a posteriori** to the change in order to animate. It does the job, but it's not as satisfying and playful as we'd like it to be. If you play with it a bit, you should see that things don't feel exactly quite right. What happens is that as we replace nodes, we are effectively replacing **one tree** (the node itself and its descendants) with **another tree**. When doing so, the whole new tree is rendered, all at once. What we would also want is to animate the subtree in/out.30:T859,We want to find a way to _**transition**_ to the new tree instead. This has multiple advantages: - only new nodes have to be rendered and inserted in the DOM, - existing nodes can be surgically updated if needed, - removed nodes can be animated out - any pre-existing node gets to keep its state This means less work on the overall tree, less work for the browser engine, and, because existing nodes are never replaced, it allows you to preserve the HTML state of the nodes that were already rendered. This means for instance, that if you had `:focus` on one existing node, you would keep it so long as the node isn't removed. When replacing the tree, you loose that focus, because the original node that had it doesn't exist anymore and is replaced by a new one. What you could do is you can maintain your own state to keep track of the precise focused element, and would give back focus to whatever new node you identify as the same one after changing you tree. But then you might have to do the same for a `:hover` state and such. It would soon require you to do quite a lot of book-keeping just to synchronise your state to reflect the browser's DOM state. We might also want to go hardcore on our FLIP animation philosophy, and decide to use a `MutationObserver` in order to animate the changes after the fact. - When a node gets inserted, you're just animating the new element (and the potential subtree) - But for instance, if a node gets removed, you will have to recreate it in the updated DOM, then animate it out, and then remove it. - If a node is modified you also have to take care of its subtree While this could certainly be a valid approach in some cases (this is what [AutoAnimate.js](https://auto-animate.formkit.com/) does), recursively handling nested transitions for descendants in subtrees becomes another challenge. You might want to use your own data structure instead to work out the differences between one tree and the next, and perform a controlled transition of the resulting DOM representation you have of it.31:Tb0a,class TomNode { _version = 0 _lastRendered = 0 constructor( children = [], renderer = TomNodeRenderer ) { this.children = children this.renderer = renderer this.resizeObserver = new ResizeObserver( entries => entries.forEach( entry => this.handleResize(entry) ) ) } get children() { return this._children } set children(newChildren) { this._version++ newChildren.forEach(child => child.parentNode = this) this._children = newChildren } get content() { return this._content } set content(newContent) { this._version++ this._content = newContent } get depth() { let level = 0 let parent = this.parentNode while(parent) { level++ parent = parent.parentNode } return level } render() { // Return cached render if (this.rendered && this._version === this._lastRendered) { return this.rendered } // Re-render if needed this._lastRendered = this._version // Unobserve previous rendered node if (this.rendered) { if (this.resizeObserver) { this.resizeObserver.unobserve(this.rendered) } } // Render the new node and setup observers on the result const rendered = this.renderer.render(this) const content = rendered.querySelector(".tom-node-content .wrapper") const children = rendered.querySelector(".tom-node-children") this.resizeObserver.observe(rendered) if (this.rendered) { this.rendered.replaceWith(rendered) } return this.rendered = rendered } handleResize = (entry) => { const {rendered} = this if (rendered && rendered.isConnected) { TomNodeRenderer.positionConnections(this.rendered) requestAnimationFrame(() => TomNodeRenderer.positionConnections(this.rendered)) } } replaceWith(node) { // update parent children so they get updated depths // if (this.parentNode?.children.length) { // this.parentNode.children = this.parentNode.children.map( // child => child !== this // ? child // : node // ) // } else if (this.parentNode) { // this.parentNode.children = [node] // } if (this.rendered) { console.log("replaceWith") // Reconcile nodes, then update our refs - it should likely be improved so we don't keep // the previous Nodes and instead use the new ones, but for our demonstration purposes // it's enough to show the intended effect TomNodeRenderer.reconcile(this, node) this.content = node.content this.children = node.children node.rendered = this.rendered TomNodeRenderer.positionConnections(this.rendered) } } clone() { return Object.assign(Object.create(Object.getPrototypeOf(this)), this) } }32:T3f8c,class TomNodeRenderer { /** * Entry point to render a TomNode * @returns the rendered DOM Node */ static render(tomNode) { const rendered = html`

` TomNodeRenderer.renderContent(tomNode, rendered) TomNodeRenderer.renderChildren(tomNode, rendered) return rendered } /** * Render given TomNode content */ static renderContent(tomNode, rendered) { if (tomNode && rendered) { const wrapper = rendered.querySelector(":scope > .tom-node-content > .wrapper") wrapper.innerHTML = tomNode.content wrapper.title = `depth: ${tomNode.depth}` } else { console.error( `Provided TomNode ${ tomNode ? "" : `is ${tomNode}` }${ rendered ? "" : " needs to be rendered itself before it can render its content" }` ) } } /** * Render given TomNode children */ static renderChildren(tomNode, rendered) { if (tomNode && rendered) { let childrenContainer = rendered.querySelector(":scope > .tom-node-children") if (childrenContainer) { childrenContainer.innerText = "" } else { childrenContainer = html`

` rendered.append(childrenContainer) } if (tomNode.children.length) { childrenContainer.append(...tomNode.children.map(c => c.render())) } TomNodeRenderer.renderChildConnections(rendered) } else { console.error( `Provided TomNode ${ tomNode ? "" : `is ${tomNode}` }${ rendered ? "" : " needs to be rendered itself before it can render its children" }` ) } } /** * Render the svg used to draw the connections * Positions will be updated when ResizeObserver is fired */ static renderChildConnections(rendered) { if (rendered) { const childrenContent = rendered.querySelectorAll(":scope > .tom-node-children > .tom-node > .tom-node-content") const content = rendered.querySelector(":scope > .tom-node-content") let connectionsSvg = rendered.querySelector(":scope > svg") if (connectionsSvg) { // remove extraneous connections if any while (connectionsSvg.children.length > childrenContent.length) { connectionsSvg.lastChild.remove() } } else { // create and insert svg the first time connectionsSvg = svg`` rendered.insertBefore(connectionsSvg, content) } } else { console.error(`renderChildConnections was called on a ${rendered} render. Can't draw connections`) } } /** * Center the Node content wrapper on the children first and last content wrapper. * This way the Node is centered on its direct children instead of being centered * on the entire subtree it holds. * * TODO * * @called via ResizeObserver */ static centerNodeOnChildren(rendered) { if (rendered) { const content = rendered.querySelector(":scope > .tom-node-content") const chidlrenContent = rendered.querySelectorAll(":scope > .tom-node-children > .tom-node > .tom-node-content") if (chidlrenContent.length > 0) { const [firstChildrenContent, lastChildrenContent] = [ chidlrenContent[0], chidlrenContent[chidlrenContent.length - 1] ] const contentRect = content.getBoundingClientRect() const firstRect = firstChildrenContent.getBoundingClientRect() const lastRect = lastChildrenContent.getBoundingClientRect() const totalWidth = lastRect.x + lastRect.width - firstRect.x const center = firstRect.x + totalWidth / 2 const contentCenter = contentRect.x + contentRect.width / 2 const offset = center - contentCenter content.style.setProperty("transform", offset ? `translateX(${offset}px)`: "") } } else { console.error(`centerNodeOnChildren was called on a ${rendered} render. Can't center the node on children`) } } /** * Position the current **rendered** child connections, including nodes that are * being removed and do not exist in the node children anymore * * TODO - we are still fighting against the tree being changed and this needs to be reworked * * @called via ResizeObserver */ static positionConnections(rendered) { if (rendered) { // Always re-render so we have the proper amount of connections TomNodeRenderer.renderChildConnections(rendered) const rootRect = rendered.getBoundingClientRect() const content = rendered.querySelector(":scope > .tom-node-content") if (content) { const contentRect = content.getBoundingClientRect() const childrenContent = rendered.querySelectorAll( ":scope > .tom-node-children > .tom-node > .tom-node-content" ) const svgElem = rendered.querySelector(":scope > svg") const connections = rendered.querySelectorAll(":scope > svg > line") // Always update svg size to the latest root rect size (so it's always matching) svgElem.setAttribute("viewBox", `0 0 ${Math.round(rootRect.width)} ${Math.round(rootRect.height)}`) // Update connections to their current positions // we are using a "memo" object to remember about the normal size of a Node // because when animating the new ones we can't know in advance const wrapper = content.querySelector(".wrapper") const wrapperRect = wrapper.getBoundingClientRect() const connectionHeight = parseInt(getComputedStyle(content).marginBottom) const marginTop = parseInt(getComputedStyle(wrapper).marginTop) const memo = { marginTop, width: wrapperRect.width // y: wrapperRect.y + wrapperRect.height + marginTop * 2 + wrapperRect.height / 2 + connectionHeight, // height: wrapperRect.height, } // console.log({memo}) childrenContent.forEach((child, i) => { const prevConnection = connections[i] const connection = prevConnection || svg`` connection.classList.toggle( "removing", child.parentNode.classList.contains("removing") ) const updatedConnection = TomNodeRenderer.updateConnectionPosition( child, connection, rootRect, contentRect, memo ) // Append the connection if it's a new one if (!prevConnection) { svgElem.append(updatedConnection) } requestAnimationFrame(() => { if (updatedConnection.isConnected) { // Maintain css variable for svg line animation const length = updatedConnection.getTotalLength() updatedConnection.style.setProperty("--length", `${length}`) } }) }) } if (rendered.getAnimations({subtree: true}).length) { if (window.requestIdleCallback) { window.requestIdleCallback(() => TomNodeRenderer.positionConnections(rendered)) } else { requestAnimationFrame(() => TomNodeRenderer.positionConnections(rendered)) } } } else { console.error( `positionConnections was called on a ${rendered} render. Can't center the node on children` ) } } /** * Update a given svg line connection to its new position * * @returns the updated svg line */ static updateConnectionPosition(child, connection, rootRect, contentRect, memo) { // Get the child to connect to and measurements we need const wrapper = child.querySelector(".wrapper") let marginTop = parseInt(getComputedStyle(wrapper).marginTop) // Compensate root rect position let childRect = wrapper.getBoundingClientRect() childRect = { x: childRect.x - rootRect.x, y: childRect.y - rootRect.y, width: childRect.width, height: childRect.height } // When animating new nodes, they don't know their final size yet, // so since we can only insert new nodes after existing ones, // we use this a cheap way to remember // if (memo.childRect?.y && childRect.y < memo.childRect.y) { // childRect.y = memo.childRect.y // } // if (memo.childRect?.width && childRect.width < memo.childRect.width) { // childRect.width = memo.childRect.width // } if (memo.marginTop && marginTop < memo.marginTop) { marginTop = memo.marginTop } memo.childRect = childRect memo.marginTop = marginTop // Prepare base coordinates for the connection line const contentEdgeY = contentRect.y + contentRect.height const baseLineCoords = { x1: contentRect.x + contentRect.width / 2 - rootRect.x, y1: contentEdgeY - rootRect.y - marginTop, x2: childRect.x + childRect.width / 2 , y2: childRect.y + childRect.height / 2 } if (childRect.x === 0 && childRect.y === 0) { // console.log(child, connection) // console.log(baseLineCoords) // console.warn("Oops, got 0") return connection } Object.entries(baseLineCoords).forEach( ([key, value]) => { if (isNaN(value)) { // TODO, see if it's still relevant console.log("baseLineCoords with NaN", key, value) } } ) // We clip the line to the parent and child bounding boxes, so it's naturally spaced // along the edges of the parent and children, while still pointing towards their center // to do that, we need a rect going from below the parent to the top of the child const belowParent = contentRect.y - rootRect.y + contentRect.height const clippingRect = { y: belowParent, // from below the parent x: contentRect.x - rootRect.x - window.innerWidth, // we make it extra wide so clipping is always width: contentRect.width + window.innerWidth * 2, // horizontal below parent, not distributed around height: (childRect.y - marginTop) - (belowParent) // down to the top of the child (single connection) } const nextLineCoords = TomNodeRenderer.clipLineToRect(baseLineCoords, clippingRect) Object.entries(nextLineCoords).forEach( ([key, value]) => { if (isNaN(value)) { console.log("nextLineCoords with NaN", key, value) } } ) // update new coordinates Object.entries(nextLineCoords).forEach( ([key, value]) => connection.setAttribute(key, value) ) return connection } /** * Clip given line coordinates to a given clipping rect using Liang-Barsky algorithm * * @returns the line coordinates, clipped or not */ static clipLineToRect(lineCoords, clippingRect) { const clipped = liangBarsky( lineCoords.x1, lineCoords.y1, lineCoords.x2, lineCoords.y2, clippingRect ) if (clipped) { const [x1, y1] = clipped[0] const [x2, y2] = clipped[1] return {x1, y1, x2, y2} } return lineCoords } /** * Reconcile two different nodes and animate the transition of the initial tree * to the new tree representation * * @param nodeA * @param nodeB */ static reconcile(nodeA, nodeB) { // We just replace the current node content nodeA.rendered.querySelector(".wrapper").textContent = nodeB.content // Recursively process the diff const processDiff = (diff) => { if (diff) { const diffs = [...diff.modified, ...diff.added, ...diff.removed] diffs.forEach( diffAction => { switch(diffAction.action) { case "added": TomNodeRenderer.reconcileInserted(diffAction) break; case "removed": TomNodeRenderer.reconcileRemoved(diffAction) break; case "modified": TomNodeRenderer.reconcileModified(diffAction) break; } processDiff(diffAction.childrenDiff) } ) } } // Start processing the diff processDiff(diffTrees(nodeA, nodeB)) TomNodeRenderer.positionConnections(nodeA.rendered) } /** * Animate the matching elements in a given TomNode, including nested matching elements * @param tomNode * @param selector - CSS selector to match elements with * @param keyframes - keyframes for the animation * @returns Animation[] */ static animateElements(tomNode, selector, keyframes) { const elems = [ ...Array.from(tomNode.rendered.querySelectorAll(selector)), tomNode.rendered ] return elems.map( t => t.animate(keyframes, { duration: parseFloat(transitionDuration) * 1.75 * 1000, easing: "ease-in-out", id: "reconciliation" }) ) } /** * Execute insertion transition for a given `inserted` reconciliation action * @param diffAction */ static reconcileInserted(diffAction) { const size = getComputedStyle(diffAction.addedTo.rendered).fontSize const keyframes = [{ boxShadow: options.includes("debug") ? "0 0 10px rgba(0, 192, 128, 0.25), 0 0 0 3px rgba(0, 192, 128, 0.25)" : "", fontSize: 0 }, { boxShadow: options.includes("debug") ? "0 0 10px rgba(0, 192, 128, 0), 0 0 0 3px rgba(0, 192, 128, 0)" : "", fontSize: `${size}` }] diffAction.node.render() const wrappers = Array.from(diffAction.node.rendered.querySelectorAll(".tom-node-children .tom-node")) wrappers.push(diffAction.node.rendered) wrappers.forEach(w => w.style.setProperty("font-size", "0")) diffAction.addedTo.rendered.querySelector(".tom-node-children").append(diffAction.node.rendered) const animations = TomNodeRenderer.animateElements(diffAction.node, ".tom-node-children .tom-node", keyframes) animations.forEach(animation => { animation.oncancel = animation.onfinish = (e) => { e.target.effect.target.style.setProperty("font-size", "") } }) TomNodeRenderer.positionConnections(diffAction.node.rendered) TomNodeRenderer.positionConnections(diffAction.addedTo.rendered) } /** * Execute modification transition for a given `modified` reconciliation action * @param diffAction */ static reconcileModified(diffAction) { // console.log(diffAction.node.content, diffAction.node.rendered) // console.log(diffAction.replacedBy.content, diffAction.replacedBy.rendered) diffAction.replacedBy.parentNode = diffAction.node.parentNode const original = diffAction.node.rendered.querySelector(".wrapper") const replacement = diffAction.replacedBy.render().querySelector(".wrapper") const clone = replacement.cloneNode(true) original.replaceWith(clone) clone.onclick = replacement.onclick diffAction.replacedBy.rendered = diffAction.node.rendered // TomNodeRenderer.positionConnections(diffAction.node.rendered) } /** * Execute removal transition for a given `removed` reconciliation action * @param diffAction */ static reconcileRemoved(diffAction) { const size = getComputedStyle(diffAction.node.rendered).fontSize const keyframes = [{ boxShadow: options.includes("debug") ? "0 0 10px rgba(237, 20, 121, 0.25), 0 0 0 3px rgba(237, 20, 121, 0.25)" : "", fontSize: `${size}` }, { boxShadow: options.includes("debug") ? "0 0 10px rgba(237, 20, 121, 0), 0 0 0 3px rgba(237, 20, 121, 0)" : "", fontSize: 0 }] const animations = TomNodeRenderer.animateElements( diffAction.node, ".tom-node-children .tom-node", keyframes ) diffAction.node.rendered.classList.add("removing") TomNodeRenderer.positionConnections(diffAction.removedFrom.rendered) animations.forEach(anim => { anim.effect.target?.classList.add("removing") anim.oncancel = anim.onfinish = () => { // diffAction.removedFrom.children = diffAction.removedFrom.children.filter( // c => c !== diffAction.node // ) anim.effect.target?.remove() } }) } }33:T488,In order to do that, what you need is basically a way of telling the difference between one description of a tree and another one. What we're specifically interested in our case are the three following operations: - we want to know when a node was modified - when a new node was inserted - and when we removed a node In our case, it's a quite trivial job, because we don't have to worry much about the details of the nodes we're moving, they're all pretty much the same. In the case of more complex tree structures, like an abstraction of a DOM tree, of course, you'd have to be way more granular and precise. You might also need to introduce the concept of **`keys`**, to be able to point at which nodes are the same between trees ([seems familiar?](https://reactjs.org/docs/lists-and-keys.html)). While we don't need it in this exploration, as soon as you want to support things like re-ordering sibling nodes, it will become quite helpful. It can also help with the performances of your diffing algorithm. We discuss a bit more about this in the closing thoughts.34:T55a,card( md`### Finding the difference between two trees In our case, we basically just check if a child existed at the same index in the two tree's children. Any node that only exist within a single tree is either an inserted or a removed node, depending on which tree it exists in. ${ details( html`Show me the example`, md`\`\`\`js /** * Recursively diff two simple trees, * Any exisiting node in tree A is either modified or removed * Any additional node found in tree B is considered added */ function diffTrees(treeA, treeB) { const modified = [] const added = [] const removed = [] const childrenA = treeA.children const childrenB = treeB.children // Check for modified and removed nodes in the first tree childrenA.forEach((childA, childIndex) => { const childB = childrenB[childIndex] if (childB) { modified.push({ action: "modified", node: childA, replacedBy: childB, childrenDiff: diffTrees(childA, childB) // recurse }) } else { removed.push({ action: "removed", node: childA, removedFrom: treeA }) } }) // The remaining children in the second tree are added ones return { modified, added: childrenB.slice(childrenA.length).map( addedChild => ({action: "added", node: addedChild, addedTo: treeA}) ), removed, } } \`\`\`` ) }`)35:T7b7,card( md`### Applying the diff to transition to the new tree - Any Modified node gets its content instantly replaced - Any node Removed from the previous tree get their font-size animated to 0 - Inserted nodes are new nodes, so we add them and animate their font-size to the desired size ${ details( html`Show me the example`, md`\`\`\`js /** * A simplified version of what we do is: */ function reconcile(nodeA, nodeB) { // Recursively process the diff const processDiff = (diff) => { const diffs = [...diff.modified, ...diff.added, ...diff.removed] diffs.forEach( diffAction => { switch(diffAction.action) { case "added": reconcileInserted(diffAction) break; case "removed": reconcileRemoved(diffAction) break; case "modified": reconcileModified(diffAction) break; } processDiff(diffAction.childrenDiff) } ) } // Start processing the diff processDiff(diffTrees(nodeA, nodeB)) } // Transition a modified node function reconcileModified(diffAction) { const original = diffAction.node.domNode.content const replacement = diffAction.replacedBy.domNode.content original.replaceWith(replacement) } // Transition an inserted node function reconcileInserted(diffAction) { const size = getComputedStyle(diffAction.addedTo.domNode).fontSize const keyframes = [{fontSize: 0}, {fontSize: size}] diffAction.addedTo.domNode .childrenDomNode .append( diffAction.node.domNode ) animateChildren(diffAction.node.domNode, keyframes) } // Transition a removed node function reconcileRemoved(diffAction) { const size = getComputedStyle(diffAction.node.domNode).fontSize const keyframes = [{fontSize: size}, {fontSize: 0}] animateChildren(diffAction.node.domNode, keyframes) } \`\`\`` )}`)36:T632,As we said previously, it's also quite likely that at some point you will need the concept of a **key** to be able to _identify the same node within two different representations of the same tree_. It would enable things like moving the nodes around and changing their order. Effectively adding one new operation to the diff set of possible operations. Now this **key** thing is probably something you heard about if you did any work using UI frameworks such as _React_, _Vue_, and many others. This is because in the end, one of the services they provide you with is managing the transitions between the current rendered tree, and the next one want to render. And to do this, as you most likely guessed it at this point, they do some form of reconciliation. Because DOM Nodes are much more complex than our very basic Tom Nodes and they can represent many different things like HTMLElements, TextNodes, and whatnot. Providing the framework with a **key**, which is just a form of identifier, allows you to tell it that a node in a given tree, is actually the same one as another node in another tree. The essence of that is that when you are, or the framework you use is, creating entirely new nodes – with different _identities_ – upon re-rendering the same component, you need a sure way to match them with the previously rendered ones. The other implication of using keys is that it gives you a very cheap way to test your nodes: instead of using a set of potentially complex heuristics, you can simply compare the keys for a match. This can certainly help with performances37:T446,function liangBarsky (x1, y1, x2, y2, domRect) { const xmin = domRect.x const xmax = domRect.x + domRect.width const ymin = domRect.y const ymax = domRect.y + domRect.height const dx = x2 - x1 const dy = y2 - y1 let t1 = 0 let t2 = 1 let p, q, r; // Loop through edges - left, right, bottom, top for(var edge = 0; edge < 4; edge++) { switch(edge) { case 0: p = -dx q = -(xmin - x1) break case 1: p = dx q = (xmax - x1) break case 2: p = -dy q = -(ymin - y1) break case 3: p = dy q = (ymax - y1) break } r = q / p if (p === 0 && q < 0) { return null // No intersection } else if(p < 0) { if (r > t2) { return null // No intersection } else if (r > t1) { t1 = r } } else if (p > 0) { if(r < t1) { return null // No intersection } else if (r < t2) { t2 = r } } } return [ [x1 + t1 * dx, y1 + t1 * dy], [x1 + t2 * dx, y1 + t2 * dy] ]; }38:T46f,{ return html` ${ [ [ `Intersection of a line with a partially overlapping clipping rectangle`, () => { const result = liangBarsky(0, 0, 10, 10, {x: 5, y: 5, width: 10, height: 10}) return JSON.stringify(result) === JSON.stringify([[5, 5], [10, 10]]) } ], [ `Intersection of a line with a fully overlapping clipping rectangle`, () => { const result = liangBarsky(0, 0, 20, 20, {x: 5, y: 5, width: 10, height: 10}) return JSON.stringify(result) === JSON.stringify([[5, 5], [15, 15]]) } ], [ `Intersection of a line with an non-overlapping clipping rectangle is null`, () => { const result = liangBarsky(0, 0, 4, 4, {x: 5, y: 5, width: 10, height: 10}) return result === null } ] ].map(t => html``) }

Test case	Pass
${t[0]}	${t[1]() ? "✅" : "❌"}

` }39:T409,class RandomTomFactory { static create( rootConstructor, tomConstructors, level = 0, maxChildren = presetMaxChildren, maxDepth = presetMaxDepth ) { const childCount = ~~(Math.random() * maxChildren) + (level < 1 ? ~~(Math.random() * 1) + 2 : 0) const children = RandomTomFactory.randomChildren(rootConstructor, tomConstructors, level, maxChildren, maxDepth) const constructor = tomConstructors[~~(Math.random() * tomConstructors.length)] const tom = level === 0 ? new tomConstructors[0](children) : new constructor(children) return tom } static randomChildren( rootConstructor, tomConstructors, level = 0, maxChildren = presetMaxChildren, maxDepth = presetMaxDepth ) { const childCount = Math.min(~~(Math.random() * maxChildren) + (level < 1 ? ~~(Math.random()) + 2 : 0), maxChildren) const children = level + 1 < maxDepth ? [...Array(childCount)].map(_ => RandomTomFactory.create(rootConstructor, tomConstructors, level + 1, maxChildren - 1)) : [] return children } }3a:Tabb,SpecializedToms = { class RootTom extends TomNode { constructor( children = [], ) { super(children) const faces = ["🌳", "🌲", "🌵", "🌴", "🪴", "🎄"] this.content = faces[~~(Math.random() * faces.length)] } render() { const rendered = super.render() const wrapper = rendered.querySelector(".wrapper") wrapper.onclick = () => { console.log("click") if ( rendered.getAnimations({subtree: true}).length === 0 ) { const newTomNode = RandomTomFactory.create(RootTom, [HumanTom, DogTom], this.depth) this.replaceWith( newTomNode ) } } return rendered } } class HumanTom extends TomNode { constructor( children = [], height, armLength, legLength, ) { super(children) const faces = ["😀", "😊", "😎", "🥳", "🤓", "🧐", "😂", "🤩", "🤠", "🥸"] this.content = faces[~~(Math.random() * faces.length)] } render() { const rendered = super.render() const wrapper = rendered.querySelector(".wrapper") wrapper.onclick = () => { console.log("click") const animations = rendered.getAnimations({subtree: true}).filter(a => a.id === "reconciliation") animations.forEach(animation => animation.effect.target.tagName.toLowerCase() !== "line" && animation.finish()) // if ( // rendered.getAnimations({subtree: true}).length === 0 // ) { const newTomNode = RandomTomFactory.create(RootTom, [HumanTom, DogTom], this.depth) this.replaceWith( newTomNode ) // } } return rendered } } class DogTom extends TomNode { constructor( children = [], wagsTail = false ) { super(children) const faces = ["🐕", "🦮", "🐩"] this.content = faces[~~(Math.random() * faces.length)] } render() { const rendered = super.render() const wrapper = rendered.querySelector(".wrapper") wrapper.onclick = () => { console.log("click") const animations = rendered.getAnimations({subtree: true}).filter(a => a.id === "reconciliation") animations.forEach(animation => animation.effect.target.tagName.toLowerCase() !== "line" && animation.finish()) // if ( // rendered.getAnimations({subtree: true}).length === 0 // ) { const newTomNode = RandomTomFactory.create(RootTom, [HumanTom, DogTom], this.depth) this.replaceWith( newTomNode ) // } } return rendered } } return {RootTom, HumanTom, DogTom} }3b:T51b,testToms = { let count = 1 class TestTom extends TomNode { constructor( children = [], height, armLength, legLength, ) { super(children) const faces = ["😀", "😊", "😎", "🥳", "🤓", "🧐", "😂", "🤩", "🤠", "🥸"] this.content = faces[~~(Math.random() * faces.length)] } render() { const rendered = super.render() const wrapper = rendered.querySelector(".wrapper") wrapper.onclick = () => { this.replaceWith((count % 2) === 0 ? testTom() : testTom2()) count++ } return rendered } } const testTom = () => { const childTom01 = new TestTom() const childTom02 = new TestTom() const testTom = new TestTom([childTom01, childTom02]) return testTom } const testTom2 = () => { const childTom1 = new TestTom() const childTom2b = new TestTom() const childTom2a = new TestTom() const childTom2 = new TestTom() const childTom3b = new TestTom() const childTom3a = new TestTom([childTom3b]) const childTom3 = new TestTom([childTom3a]) const childTom4 = new TestTom() const testTom2 = new TestTom([childTom1, childTom2, childTom3, childTom4]) return testTom2 } return {testTom: testTom(), testTom2: testTom2()} }3c:T848,{ return html` ${ [ [`maximum depth is never more than configured`, () => { let success = true for (let i = 0; i < 100; i++) { const randomTom = RandomTomFactory.create(SpecializedToms.RootTom, [SpecializedToms.HumanTom, SpecializedToms.DogTom]) const walk = (tom, depth) => { // console.log(tom.depth) depth = tom.depth > depth ? tom.depth : depth if (tom.children.length) { depth = tom.children.map( (t) => walk(t, depth) ).reduce( (l, v) => l < v? v : l, depth ) } return depth } const maxDepth = walk(randomTom, 0) if ( maxDepth >= presetMaxDepth ) { success = false } } return success }], [`maximum number of children is never more than configured`, () => { let success = true for (let i = 0; i < 100; i++) { const randomTom = RandomTomFactory.create(SpecializedToms.RootTom, [SpecializedToms.HumanTom, SpecializedToms.DogTom]) const walk = (tom, maxCount) => { maxCount = tom.children.length > maxCount ? tom.children.length : maxCount if (tom.children.length) { maxCount = tom.children.map( (t) => walk(t, maxCount) ).reduce( (l, v) => l < v ? v : l, maxCount ) } return maxCount } const maxChildren = walk(randomTom, 0) if ( maxChildren > presetMaxChildren) { success = false } } return success }], ].map(t => html``) }

Test case	Pass
${t[0]}	${t[1]() ? "✅" : "❌"}

` }3d:T46e,{ const nested6 = new TomNode() const nested5a = new TomNode([nested6]) const nested5b = new TomNode() const nested4 = new TomNode([nested5a, nested5b]) const nested3 = new TomNode([nested4]) const nested2 = new TomNode([nested3]) const nested1 = new TomNode([nested2]) const root = new TomNode([nested1]) return html` ${ [ [`root node depth is 0`, () => root.depth === 0], [`a level 1 node depth is 1`, () => nested1.depth === 1], [`a level 2 node depth is 2`, () => nested2.depth === 2], [`a level 3 node depth is 3`, () => nested3.depth === 3], [`a level 4 node depth is 4`, () => nested4.depth === 4], [`a level 5 node with sibling depth is 5`, () => nested5a.depth === 5], [`a sibling of a level 5 node depth is 5`, () => nested5b.depth === 5], [`a level 6 node nested in a node with siblings is 6`, () => nested6.depth === 6], ].map(t => html``) }

Test case	Pass
${t[0]}	${t[1]() ? "✅" : "❌"}

` }3e:T46c,3f:T10f5,40:[] 2d:{"id":"859634bd65e6d498","slug":"tom-in-the-dom-a-story-about-tree-structures-reconciliation","title":"Tom in the DOM, a story about tree structures reconciliation","thumbnail":"66f44c487d14c46b767e2900345d921710c12e9c58197f928473ede3fe6e2f91","access_level":"public","create_time":"$D2022-05-21T15:15:02.515Z","update_time":"$D2022-07-31T15:32:28.470Z","view_time":null,"first_public_time":"$D2022-07-31T15:14:52.939Z","has_unpublished_edits":null,"fork":false,"stars":33,"starred":false,"owner":{"type":"team","id":"56478bd83f2190f0","login":"daformat","name":"Mathieu Jouhet","avatar_url":"https://avatars-next.observableusercontent.com/c16e6bd08b4b833b3760138d4467214b19161a15acf138c3d1809c74485979ec","tier":"starter_2024"},"version":3437,"publish_version":3437,"role":null,"authored":false,"authors":[{"type":"individual","id":"e5f68da25a5a2366","login":"daformat","name":"Mathieu Jouhet","avatar_url":"https://avatars-next.observableusercontent.com/c16e6bd08b4b833b3760138d4467214b19161a15acf138c3d1809c74485979ec","tier":null}],"members":[{"type":"individual","id":"e5f68da25a5a2366","login":"daformat","name":"Mathieu Jouhet","avatar_url":"https://avatars-next.observableusercontent.com/c16e6bd08b4b833b3760138d4467214b19161a15acf138c3d1809c74485979ec","tier":null,"role":"editor"},{"type":"individual","id":"508a63413d5752c9","login":"lele-venturi","name":"Gabriele Venturi","avatar_url":"https://avatars-next.observableusercontent.com/2b8e0f352d8120b2d331a38188ac28218d724dd4fe3c73fe573baf637acc44ab","tier":null,"role":"viewer"},{"type":"individual","id":"9bda6a3ca0d47e44","login":"stefkors","name":"Stef Kors","avatar_url":"https://avatars-next.observableusercontent.com/8ef23d8abe5d6114fc4715206f8163e88feeb8498022ba2feb9d54417c5b61e8","tier":null,"role":"viewer"},{"type":"individual","id":"5067d9543499be52","login":"wilfried","name":"Wilfried De Kerchove de Denterghem","avatar_url":"https://avatars-next.observableusercontent.com/a19af0b4253312480b9c62dc38cf9ca7b429662bf3263c273e10a7e7fde26137","tier":null,"role":"viewer"}],"comments":[],"custom_thumbnail":true,"trashed":false,"lapsed":null,"subscribed":null,"forks":10,"collection":null,"type":"notebook","body":{"title":"Tom in the DOM, a story about tree structures reconciliation","cells":[{"id":0,"value":"# Tom in the DOM, a story about tree structures reconciliation","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":2455,"value":"This is not a discussion about whether VDOM is a good thing","pinned":false,"hidden":false,"mode":"html","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":2106,"value":"haveFun && md`## Meet Tom ${haveFun}`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2269,"value":"Tom is a _**Node**_, he lives in a _**tree structure**_, which is to say that any given Tom can hold other child Tom Nodes. All is good in Tom's life, but the world around, the tree structure, keeps changing. It can be hard for Tom to animate the changes.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":3000,"value":"In this notebook, we'll explore **tree reconciliation**, a rather quite common problem in modern web development, and see how we helped Tom live a smoother life along the way.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":2457,"value":"Click on Tom 👇","pinned":false,"hidden":false,"mode":"html","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":2618,"value":"viewof haveFun = {\n const render = html`\n

\n ${tom3a.render()}\n

\n `\n render.value = tom3a.content\n render.onclick = () => {\n render.value = tom3a.content\n render.dispatchEvent(new Event(\"input\"))\n }\n return render\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":3382,"value":"md`_**fig 0** • Clicking any node generates a new random subtree_`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":3033,"value":" ","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":2681,"value":"## The problem:
replacing an html tree with another one is trivial, transitioning one to the other is not","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":2209,"value":"$2f","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":3039,"value":"Click on Tom or its child nodes 👇","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":2398,"value":"","pinned":false,"hidden":false,"mode":"html","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":3278,"value":"md`_**fig 1** • Reacting to DOM updates after the fact only gets us so far_`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":3073,"value":" ","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":3057,"value":"card(\nmd`### Using a ResizeObserver\nIn order to listen the size changes of any html element we can use a ResizeObserver.\n${\ndetails(\n html`Show me the example`,\n md`\\`\\`\\`js\n// Keep memory of the last known width\nlet previousWidth\n\n// The observer callback when a node was resized\nfunction handleResizeNode(entry) {\n const nextWidth = entry.borderBoxSize[0].inlineSize\n if (previousWidth) {\n animateWidth(previousWidth, nextWidth)\n }\n previousWidth = nextWidth\n}\n\n// Initialize a resize observer\nconst resizeObserver = new ResizeObserver(\n entries => entries.forEach(\n entry => handleResizeNode(entry)\n )\n)\n\n// Observe the elements we're interested in\nconst tomNodeCollection = document.querySelectorAll(\".tom-node\")\ntomNodeCollection.forEach(tomNode => this.resizeObserver.observe(tomNode))\n\\`\\`\\``\n)\n}`)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":3067,"value":"card(md`### Animating with dynamic keyframes\nUsing the WebAnimation API is then pretty trivial:\n${details(html`Show me the example`, md`\\`\\`\\`js\n// use the WebAnimation API to transition from the previous width\n// to the next\nfunction animateWidth(element, from, to) {\n const currentAnimations = element.getAnimations()\n const isAnimating = currentAnimations.some(\n animation => animation.id === \"animate-width\"\n )\n if (isAnimating) {\n const keyframes = [\n { width: \\`\\${from}px\\` },\n { width: \\`\\${to}px\\`}\n ]\n const options = {\n id: \"animate-width\",\n duration: 200,\n easing: \"ease-in-out\",\n fill: \"none\"\n }\n element.animate(keyframes, options)\n }\n}\n\\`\\`\\``)}\n`)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":3075,"value":" ","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":1460,"value":"$30","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":2254,"value":" ","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":2684,"value":"## One solution is reconciliation","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":2101,"value":"What we want to do is to actually perform a transition from the original tree, with its current DOM representation, to the new tree and the resulting DOM we want to replace it with. This is called **reconciliation**.\n\nThis can be useful when you keep your own representation of the tree structure:\n- maybe your structure is very simple, but rendering it is costly\n- or maybe the nodes in your structures have different identities, but relate to the same DOM representation\n- it might also be that you want to use a declarative approach the describe changes across renders \n- maybe you just want to have fun animating the transition, and want to keep control over the browser relayouts because you implemented a tree rendered using flexbox ¯\\\\\\_(ツ)_/¯\n\nWhatever the reason, it might make more sense for you to transition the existing DOM to the new one.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":2469,"value":"Click on Tom 👇 again","pinned":false,"hidden":false,"mode":"html","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":69,"value":"viewof renderer = {\n const render = html`\n

\n ${tom.render()}\n

\n `\n render.value = 0\n render.onclick = () => {\n render.value++\n render.dispatchEvent(new Event(\"input\"))\n }\n return render\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":3244,"value":"md`_**fig 2** • Tree reconciliation allows us to animate the transition between states_`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2523,"value":"Isn't that so much more satisfying and organic looking?\n\nIf you're interested, you can look at the following two classes, which are the core of the demos in this notebook. Although beware, this is just a quick implementation, please don't think of this as remotely close to production ready code, or even a good way to implement reconciliation, the purpose of this is to give you the _keys_ (pun intended) to understand the general idea.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":5,"value":"$31","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":8,"value":"$32","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2419,"value":" ","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":1564,"value":"## Getting the difference between the two trees","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":2180,"value":"$33","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":2529,"value":"Click the first Tom 👇 or the Other Tom 👇 to update trees and the diff between each","pinned":false,"hidden":false,"mode":"html","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":1471,"value":"viewof demoDiff = {\n const render = html`\n

\n ${tom2a.render()}\n

\n ${tom2b.render()}\n

\n Modified node\n Inserted node\n Removed node\n

\n `\n return render\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":3233,"value":" ","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":3218,"value":"$34","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1499,"value":"currentDemoDiff = {\n demoDiff\n const diff = diffTrees(tom2a, tom2b)\n\n const removePreviousClasses = t => t.classList.remove(\"modified\", \"added\", \"removed\")\n tom2a.rendered.querySelectorAll(\".tom-node\").forEach(removePreviousClasses)\n tom2b.rendered.querySelectorAll(\".tom-node\").forEach(removePreviousClasses)\n\n const processDiff = (diff) => {\n if (diff) {\n const diffs = []\n diffs.push(...diff.modified, ...diff.added, ...diff.removed)\n diffs.forEach(\n diffAction => {\n diffAction.node.rendered.classList.add(diffAction.action)\n processDiff(diffAction.childrenDiff)\n }\n )\n }\n }\n processDiff(diff)\n \n return diff\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1497,"value":"/**\n * Recursively diff two simple trees,\n * Any exisiting node in tree A is either modified or removed\n * Any additional node found in tree B is considered added\n */\nfunction diffTrees(treeA, treeB) {\n const modified = []\n const added = []\n const removed = []\n const childrenA = treeA.children\n const childrenB = treeB.children\n \n // Check for modified and removed nodes in the first tree\n childrenA.forEach((childA, childIndex) => {\n const childB = childrenB[childIndex]\n if (childB) {\n modified.push({\n action: \"modified\", node: childA, replacedBy: childB,\n childrenDiff: diffTrees(childA, childB) // recurse\n })\n } else {\n removed.push({\n action: \"removed\", node: childA, removedFrom: treeA\n })\n }\n })\n \n // The remaining children in the second tree are added ones\n return {\n modified,\n added: childrenB.slice(childrenA.length).map(\n addedChild => ({action: \"added\", node: addedChild, addedTo: treeA})\n ),\n removed,\n }\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":3293,"value":" ","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":2579,"value":"Now that we get our diff, we can start acting on it. For each provided diff operation, we have to implement the way we want it to behave. Which in our case is, again, quite simple, we want to keep Tom's life simple, and this notebook focused","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":2599,"value":"$35","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":3252,"value":" ","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":2167,"value":"---","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":3300,"value":"# Closing thoughts","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":3302,"value":"There might be questions you have left...","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":2713,"value":"## Where are the keys?","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":2689,"value":"$36","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":3370,"value":" ","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":3372,"value":"## Why aren't we just straight updating the DOM?\nBecause the DOM is the byproduct of our own tree structure, and rendering this tree structure can be thought as a function of the state we hold and that describes our tree.\n\nThis enables declarative thinking. Remember that a declarative programming language is a language which enables you to express what you want done, and not explicitly how you want it done. Html and css, for instance, are declarative languages. So here, what we do is generate a new representation of our tree, and the reconciliation process takes care of updating the underlying DOM.\n\nIn our case, it makes sense to just generate a random tree without having to manipulate the existing one. The way our code behaves is now very close to the _mental model_ we have of it: clicking on a node generates a new random tree and effectively transitions the old one into the new one.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":2661,"value":" \n ","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":2663,"value":"## And now, what?\nNow, go get crazy, and appreciate the simple joy of a transitioning tree. Then the next time you work on any `html` document or `svg`, remember it's just like this tree. Sometimes you might want to transition it.\n\nOh by the way, in case you missed it, we are rendering these trees with... html and svg to draw the connections. Using trees to render trees, how crazy ¯\\\\\\_(ツ)_/¯\n\nLast but not least, since we discussed some much about trees in this notebook, consider planting one 🪴\n\n \n ","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":3317,"value":"md`\n## Want some more?\nLearn [how to round polygon corners using svg and javascript](https://observablehq.com/@daformat/rounding-polygon-corners)\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":3322,"value":"html`\n\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":3327,"value":" ","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":3295,"value":"---","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":2568,"value":"# Bonus","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":2570,"value":"_Because who doesn't like free stuff?_","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":2135,"value":"## Liang-Barsky algorithm\n\nOne trick we use to draw the connections is that we actually draw them to the _geometric center_ of Nodes, and then _clip them_ with a rectangle. This way, they always point at the center while still being distributed along the edges, without us doing the distribution. We use the [Liang-Barsky line clipping](https://en.wikipedia.org/wiki/Liang%E2%80%93Barsky_algorithm) algorithm to do the clipping. While this is not optimal for large trees, it's good enough for our purposes!\n\n#### Find the intersection of a line and an unrotated rectangle (axis-aligned)\nThis algorithm takes a line coordinates, and a DOMRect-ish object with at least the `x`, `y`, `width` and `height` properties. It uses the parametric equation of the line to find the clipped result\n\n_**Returns**_\n- `[[x1: number, y1: number], [x2: number, y2: number]]` the coordinates of the clipped portion of the line, if the two indeed have some overlap\n- `null` otherwise","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":898,"value":"$37","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2117,"value":"$38","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":3353,"value":" ","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":2169,"value":"---","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":2233,"value":"## The random Tom Factory","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":410,"value":"$39","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":12,"value":"$3a","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1307,"value":"viewof options = Inputs.checkbox([\"slow-motion\", \"debug\"])","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":728,"value":"viewof tomNodeSize = Inputs.range([16, 64], {step: 1, label: \"TomNode size\", value: 24})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":866,"value":"viewof tomNodeConnectionsHeight = Inputs.range([1, 2], {step: 0.01, label: \"Connections length\"})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":875,"value":"viewof tomNodeMarginH = Inputs.range([0, 1], {step: 0.01, label: \"TomNode margin H\"})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":873,"value":"viewof tomNodeMarginV = Inputs.range([0, 1], {step: 0.01, label: \"TomNode margin V\"})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":405,"value":"viewof presetMaxChildren = Inputs.range([1, 4], {step: 1, value: 4, label: \"Max children\"})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":430,"value":"viewof presetMaxDepth = Inputs.range([1, 6], {step: 1, value: 5, label: \"Max depth\"})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2433,"value":"### Main Tom and his children:","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":416,"value":"tom = {\n return RandomTomFactory.create(SpecializedToms.RootTom, [SpecializedToms.HumanTom, SpecializedToms.DogTom])\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2438,"value":"### Diff Toms:","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":494,"value":"tom2a = {\n return RandomTomFactory.create(\n SpecializedToms.RootTom, [SpecializedToms.HumanTom, SpecializedToms.DogTom], 0, 4, 3\n )\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1474,"value":"tom2b = {\n return RandomTomFactory.create(\n SpecializedToms.RootTom, [SpecializedToms.HumanTom, SpecializedToms.DogTom], 0, 4, 4\n )\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2621,"value":"### Final Toms","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":2625,"value":"tom3a = {\n return RandomTomFactory.create(\n SpecializedToms.RootTom, [SpecializedToms.HumanTom, SpecializedToms.DogTom], 0, 4, 5\n )\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2441,"value":"### Test random factory config","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":2736,"value":"$3b","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2295,"value":"$3c","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2443,"value":"`Test TomNode depth`","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":1247,"value":"$3d","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2216,"value":"## Misc","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":2014,"value":"viewof transitionDurationMs = Inputs.range([200, 3500], {step: 1, label: \"Transition duration\", value: options.includes(\"slow-motion\") ? 1500 : 200})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1882,"value":"transitionDuration = `${transitionDurationMs / 1000}s`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":3433,"value":"### Html helpers","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":3079,"value":"function details(summary, content, open = false, className) {\n return html`\n

${summary}

\n ${content}\n

\n `\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":3104,"value":"","pinned":false,"hidden":false,"mode":"html","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":2218,"value":"## Style\n```\nStyle is form,\nform follows function(s),\nindeed, that is a pun\n```","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":55,"value":"$3f","pinned":false,"hidden":false,"mode":"html","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"}],"files":"$W40","stdlib":"1","titling":"auto"}} 2e:"$2d:body"