denistakeda · denistakeda · May 1, 2021 · May 5, 2021 · evxn · Jul 23, 2021
diff --git a/examples/todolist.ts b/examples/todolist.ts
@@ -1,9 +1,10 @@
-import { cell, deref, formula, FormulaCell, reset, swap } from '../src/Cell'
-import { button, div, input, renderList, span } from '../src/Dom'
+import { cell, deref, formula, FormulaCell, Value, reset, swap } from '../src/Cell'
+import { button, div, input, span } from '../src/Dom'
 import {
   className,
   classList,
   children,
+  children1,
   inputType,
   text,
   onClick,
@@ -55,7 +56,10 @@ export const todolist = () => {
   return div([
     className('todolist'),
     children([
-      div([className('list'), children(renderList(todoItem, TodoList.list()))]),
+      div([
+        className('list'),
+        children1(todoItem, TodoList.list()),
+      ]),
       div([
         children([
           input([inputType('text'), value(newItem), onChange((val) => reset(val, newItem))]),
@@ -66,10 +70,12 @@ export const todolist = () => {
   ])
 }
 
-const todoItem = (item: TodoList.TodoItem) =>
-  div([
+const todoItem = (val: Value<TodoList.TodoItem>) => {
+  const item = deref(val)
+  return div([
     className('todoitem'),
     classList({ checked: item.done }),
     onClick(() => TodoList.toggle(item.id)),
     children([input([inputType('checkbox'), checked(item.done)]), span([text(item.text)])]),
   ])
+}
diff --git a/src/Cell.ts b/src/Cell.ts
@@ -308,7 +308,7 @@ export const map = formula
  * Accepts a cell and creates a cell of tuple [newValue, oldValue]
  * initially oldValue is undefined
  */
-export function history<T>(cell: Cell<T>): FormulaCell<[T, T | undefined]> {
+export function history<T>(cell: Value<T>): FormulaCell<[T, T | undefined]> {
   let oldVal: T | undefined = undefined
   return formula((newVal) => {
     const result: [T, T | undefined] = [newVal, oldVal]

diff --git a/src/Graph.ts b/src/Graph.ts
@@ -0,0 +1,121 @@
+export interface DirectedEdge {
+    readonly from: number
+    readonly to: number
+    readonly weight: number
+}
+
+export interface EdgeWeightedDigraph {
+    v(): number
+    adj(v: number): DirectedEdge[]
+}
+
+export class MayersGraph<T> implements EdgeWeightedDigraph {
+    constructor(private readonly oldS: T[], private readonly newS: T[]) {
+
+    }
+
+    public v(): number {
+        return (this.oldS.length + 1) * (this.newS.length + 1)
+    }
+
+    // No need to store the adjacency list, we can generate it on the flight
+    public adj(v: number): DirectedEdge[] {
+        const [ newId, oldId ] = this.toCoord(v)
+
+        let result: DirectedEdge[] = []
+        if (oldId < this.oldS.length && newId < this.newS.length && this.oldS[oldId] === this.newS[newId]) {
+            result.push({
+                from: v,
+                to: (newId + 1) * (this.oldS.length + 1) + oldId + 1,
+                weight: 0,
+            })
+            return result
+        }
+        if (oldId < this.oldS.length)
+            result.push({ from: v, to: v + 1, weight: 1 })
+        if (newId < this.newS.length)
+            result.push({ from: v, to: v + this.oldS.length + 1, weight: 1 })
+        return result
+    }
+
+    public toCoord(v: number): [number, number] {
+        return [Math.floor(v / (this.oldS.length + 1)), v % (this.oldS.length + 1)]
+    }
+}
+
+
+export function topologicalOrder(g: EdgeWeightedDigraph, s: number): number[] {
+    const order: number[] = []
+    const marked: boolean[] = []
+    // TODO: use the explicit stack instead of recursion
+    const dfs = (g: EdgeWeightedDigraph, v: number) => {
+        marked[v] = true
+        for (let e of g.adj(v))
+            if (!marked[e.to])
+                dfs(g, e.to)
+
+        order.unshift(v)
+    }
+    dfs(g, s)
+    return order
+}
+
+// -- Shortest path --
+
+export function shortestPath(g: EdgeWeightedDigraph, s: number, d: number): DirectedEdge[] {
+    const edgeTo: DirectedEdge[] = []
+    const distTo: number[] = Array(g.v()).fill(Number.MAX_SAFE_INTEGER)
+
+    distTo[s] = 0
+    for (let v of topologicalOrder(g, s)) {
+        relax(g, v, edgeTo, distTo)
+    }
+    return pathTo(d, edgeTo)
+}
+
+function relax(g: EdgeWeightedDigraph, v: number, edgeTo: DirectedEdge[], distTo: number[]) {
+    for (let e of g.adj(v)) {
+        const w = e.to
+        if (distTo[w] > distTo[v] + e.weight) {
+            distTo[w] = distTo[v] + e.weight
+            edgeTo[w] = e
+        }
+    }
+}
+
+function pathTo(d: number, edgeTo: DirectedEdge[]): DirectedEdge[] {
+    const path: DirectedEdge[] = []
+    for (let e = edgeTo[d]; e !== undefined; e = edgeTo[e.from])
+        path.unshift(e)
+    return path
+}
+
+// --------------------
+
+// -- Mayer's algorithm --
+
+interface InsertAction<T> {
+    kind: 'insert',
+    value: T,
+}
+interface DeleteAction<T> {
+    kind: 'delete',
+    value: T,
+}
+interface SkipAction<T> {
+    kind: 'skip',
+    value: T,
+}
+type Action<T> =  InsertAction<T> | DeleteAction<T> | SkipAction<T>
+
+export function mayers<T>(oldArr: T[], newArr: T[]): Action<T>[] {
+    const g = new MayersGraph(oldArr, newArr)
+    const path = shortestPath(g, 0, g.v() - 1)
+    return path.map(edge => {
+        const [y1, x1] = g.toCoord(edge.from)
+        const [y2, x2] = g.toCoord(edge.to)
+        if (y2 > y1 && x2 > x1) return { kind: 'skip', value: newArr[y1]}
+        else if (y2 > y1) return { kind: 'insert', value: newArr[y1]}
+        else return { kind: 'delete', value: oldArr[x1] }
+    })
+}
diff --git a/src/Properties.ts b/src/Properties.ts
@@ -11,7 +11,8 @@
  *     ]),
  * ])
  */
-import { Value, isCell, history, formula } from './Cell'
+import { Value, isCell, history, formula, deref, destroy } from './Cell'
+import { mayers } from './Graph'
 
 /**
  * Property is just a mutable transformation over HTMLElement
@@ -128,30 +129,38 @@ export const onChange: (
   )
 
 export function children(chld: Value<Array<Value<Node>>>): Property<HTMLElement> {
-  return (element) => {
-    formula((chld) => {
-      // TODO: this property is not efficient
-      while (element.lastChild) {
-        element.removeChild(element.lastChild)
+  return element => {
+    for (let child of deref(chld)) {
+      element.appendChild(deref(child))
+    }
+  }
+}
+
+export function children1<T>(fn: (val: Value<T>) => Value<Node>, vals: Value<Array<Value<T>>>): Property<HTMLElement> {
+  return element => {
+    formula(([newList, oldList]) => {
+      if (!oldList) {
+        newList.forEach(val => element.appendChild(deref(fn(val))))
+        return
       }
-      for (let child of chld) {
-        if (isCell(child)) {
-          formula(([newChild, oldChild]: [Node, Node | undefined]) => {
-            if (!oldChild) {
-              formula((newChild) => element.appendChild(newChild), newChild)
-            } else {
-              formula(
-                (newChild, oldChild) => element.replaceChild(newChild, oldChild),
-                newChild,
-                oldChild
-              )
-            }
-          }, history(child))
-        } else {
-          element.appendChild(child)
+
+      let pos = 0
+      for (let action of mayers(oldList, newList)) {
+        switch (action.kind) {
+            case 'insert':
+              element.insertBefore(deref(fn(action.value)), element.childNodes[pos])
+              pos++
+              break
+            case 'delete':
+              element.removeChild(element.childNodes[pos])
+              destroy(action.value)
+              break
+            case 'skip':
+              pos++
+              break
         }
       }
-    }, chld)
+    }, history(vals))
  }
 }
 

diff --git a/test/Graph.test.ts b/test/Graph.test.ts
@@ -0,0 +1,57 @@
+import { MayersGraph, topologicalOrder, shortestPath, mayers } from '../src/Graph'
+
+const graph = new MayersGraph<String>('bac'.split(''), 'cbcb'.split(''))
+const smallGraph = new MayersGraph<String>(['a'], ['b'])
+
+describe('DoubleStringGraph', () => {
+    it('should calculate the graph size', () => {
+        expect(graph.v()).toBe(20)
+    })
+
+    it('should return the right adjacency lists', () => {
+        expect(graph.adj(0)).toEqual([
+            { from: 0, to: 1, weight: 1 },
+            { from: 0, to: 4, weight: 1 }
+        ])
+        expect(graph.adj(2)).toEqual([
+            { from: 2, to: 7, weight: 0 }
+        ])
+        expect(graph.adj(3)).toEqual([
+            { from: 3, to: 7, weight: 1 }
+        ])
+        expect(graph.adj(16)).toEqual([
+            { from: 16, to: 17, weight: 1 }
+        ])
+        expect(graph.adj(19)).toEqual([])
+    })
+})
+
+describe('topologicalOrder', () => {
+    it('should sort small graph in a topological order', () => {
+        expect(topologicalOrder(smallGraph, 0)).toEqual([0, 2, 1, 3])
+    })
+})
+
+describe('shortestPath', () => {
+    it('should provide a shortest path', ()=> {
+        expect(shortestPath(graph, 0, 19)).toEqual([
+            {from: 0, to: 4, weight: 1},
+            {from: 4, to: 9, weight: 0},
+            {from: 9, to: 10, weight: 1},
+            {from: 10, to: 15, weight: 0},
+            {from: 15, to: 19, weight: 1}
+        ])
+    })
+})
+
+describe('mayers', () => {
+    it('should return the list of mutations', () => {
+        expect(mayers('bac'.split(''), 'cbcb'.split(''))).toEqual([
+            {kind: "insert", value: "c"},
+            {kind: "skip", value: "b"},
+            {kind: "delete", value: "a"},
+            {kind: "skip", value: "c"},
+            {kind: "insert", value: "b"}
+        ])
+    })
+})