Run, Forest, run!

run-forest-run.js

// API:
// ===
//   helpers:
//   -------
//     var write       = function (what)
//     var writeln     = function (what)
//     var write_spine = function (spine)

//   tree constructors:
//   -----------------
//     var node  = function (name, payload, children)
//     var clone = function (node)
//     var leaf  = function (name, payload)

//   render:
//   ------
//     var previewWithSpine = function (tree, start, append, end)

//   modification helpers:
//   --------------------
//     var invalidate     = function(node)
//     var invalidateDeep = function(node)

//   create:
//   ------
//     var createFromSpine = function (path, tree, create)

//   read:
//   ----
//     var zoomAt = function(path, tree, lens)

//   update:
//   ------
//     var modifyAt = function (path, tree, willCascade, extract)

//   delete:
//   ------
//     var removeById = function (array, name)

//   test implementation:
//   -------------------    
//     var rect   = function (x, y, w, h)
//     var start  = function (spine)
//     var append = function (accum, child)
//     var end    = function (spine, accum)
    
//     var willCascade = function(oldRect, newRect)



var write   = function (what) { process.stdout.write(what) }
var writeln = function (what) { write(what + "\n") }

var s       = JSON.stringify


// Take an array of nodes (spine is a path back to root)
//  and print their names.

var write_spine = function(spine) {
    var names = spine.map(function(x) { 
        return x.id 
    })

    writeln(JSON.stringify(names))
}

Object.prototype.to_s = function() { return s(this) }

// Get last element from array.

Array.prototype.last = function() {
    if (this.length)
        return this[this.length - 1]
};


// Fold an array using some binary operation.

// Undefined for empty arrays,
// the single element for single-element array,
// all elements "summed" by `add` otherwise.

Array.prototype.fold = function(add) {
    switch (this.length) {
        case 1:
            return this[0]

        default:
            var accum = this.last()

            for (var i = this.length - 2; i >= 0; i--) {
                accum = add(this[i], accum)
            }

            return accum
    }
}

// Smart ctor for tree.

var node = function (name, payload, children) {
    return {
        id:       name,
        payload:  payload,
        preview:  undefined,
        version:  1,
        children: children,
    }
}


// Smart shallow-copy-ctor for tree.

// Warning, it returns half-fabricated node:
//   the `preview` & `children` aren't set!

var clone = function(node) {
    return {
        id:       node.id,
        payload:  node.payload,
        version:  node.version + 1,
    }
}

// Smart-ctor for end-branch with no children

var leaf = function (name, payload) {
    return node(name, payload, [])   
}

// Main rendering driver.
//
// It will traverse a tree down from a root, looking for invalid[ated] nodes
//  and will rebuild absent previews for that nodes.
//
// It creates a new tree, the old tree remain untouched.
// It is not recommended to modify any parameters 
//  inside the function passed into.
//
// It requires:
//   - a tree;
//   - a draw:
//        function to transform a pair (spine, child.previews array)
//        into a new preview for the node
//
// The "spine" is the array of nodes, touched by the path, in the order
//  of proximity from the root.
//
// Typical spine is [root, root-child, ..., node-parent, node].
//
// You can get current node from a spine using a .last() method.

var previewWithSpine = function(tree, draw) {

    var spine = []
    var walk  = function(tree) {

        if (tree.preview === undefined) {

            spine.push(tree)
 
            var new_node  = clone(tree)
            var accum     = []

            new_node.children = tree.children.map(function(child) {
                var new_child = walk(child)

                accum.push(new_child.preview)

                return new_child
            })

            new_node.preview = draw(spine, accum)

            spine.pop()

            return new_node
        }

        return tree
    }

    return walk(tree)
}

// It will create a shallow copy of the tree node w/o preview,
//  making it a valid target for `previewWithSpine`

var invalidate = function(node) {
    var new_node = clone(node)

    new_node.preview  = undefined
    new_node.children = node.children

    return new_node
}

// It will create a deep copy of the tree node w/o previews down the branches,
//  making it a valid target for `previewWithSpine`

var invalidateDeep = function(node) {
    var new_node = invalidate(node)

    new_node.children = node.children.map(invalidateDeep)

    return new_node
}

// special case, to prevent double version imcrement

var invalidateDeep1 = function(node) {
    var new_node = invalidate(node)

    new_node.version -= 1

    new_node.children = node.children.map(invalidateDeep)

    return new_node
}

// this function will traverse a tree along the path, invalidating
// nodes & invoking an action on the spine, current already invalidated node
// and the current step

var traverse = function(path, tree, action) {

    var spine = []
    var walk  = function(step, tree) {

        if (tree.id == path[step]) {

            var new_tree = invalidate(tree)

            spine.push(tree)

            new_tree.children = tree.children.map(function (child) {
                return walk(step + 1, child)
            })

            new_tree = action(spine, new_tree, step)

            spine.pop(tree)

            return new_tree
        }

        return tree
    }

    return walk(0, tree)

}

// It will modify a node found in a "tree" on a "path", using "extract".
// The "extract" will receive an "spine" - ancestors node array.
//
// The "willCascade" function is used to determine if the node invalidation
//  causes its children to invalidate.
//
// Spines are explained above in the comment for the `previewWithSpine`.
//
// P.S.: this function, if does any changes at all, changes version of the root
//  node, which one could be used as global version (couldn't be decremented).

var modifyAt = function(path, tree, willCascade, extract) {

    return traverse(path, tree, function(spine, tree, step) {

        if (step == path.length - 1) {

            var payload = extract(spine)

            if (willCascade(tree.payload, payload))
                tree = invalidateDeep1(tree)

            tree.payload = payload

        }

        return tree
    })

}

// It builds a spine from a path in a tree & passes it to "lens".

var zoomAt = function(path, tree, lens) {

    var spine = []
    var walk  = function(step, tree) {

        if (path[step] == tree.id) {

            spine.push(tree)

            if (step == path.length - 1) {

                return lens(spine)

            } else {

                var children = tree.children

                for (var i = 0; i < children.length; i++) {
                    var focus = walk(step + 1, children[i])

                    if (focus)
                        return focus
                }

            }

            spine.pop()

        }

    }

    return walk(0, tree)

}

// It will create a node on a path, assimung path.pop() exists in tree.
// "Create" parameter is a function receiving the spine & name for node

var createFromSpine = function (path, tree, create) {
    
    var name = path.last()

    path.pop()

    return traverse(path, tree, function (spine, tree, step) {

        if (step == path.length - 1) {
            new_node = create(spine, name)

            tree.children.push(new_node)
        }

        return tree
    })

}

var removeById = function (array, name) {
    for (var i = 0; i < array.length; i++) {
        if (array[i].id == name) {
            array.splice(i, 1)
            break
        }
    }
}

// This function will remove subtree on the path, assuming it exists.
//
// It is impossible to remove the root.

var remove = function(path, tree) {

    var victim = path.last()

    path.pop()

    return traverse(path, tree, function (_, tree, step) {
        
        if (step == path.length - 1) {
            removeById(tree.children, victim)
        }

        return tree

    })

}

////////////////////////////////////
// testing area
////////////////////////////////////

var rect = function (x, y, w, h) {
    return {x: x, y: y, w: w, h: h}
}

var tree = node('a', rect(10, 10, 20, 20), [
    leaf('b', rect(5, 0, 20, 20)),
    node('c', rect(0, 5, 20, 20), [
        leaf('d', rect(5, 0, 20, 20)),
        leaf('e', rect(0, 5, 20, 20))
    ]),
    node('f', rect(0, 50, 20, 20), [
        leaf('g', rect(5, 0, 20, 20)),
        leaf('h', rect(0, 5, 20, 20))
    ]),
    leaf('i', rect(-5, 0, 20, 20))
])

// This function creates simplified tree from a normal one.

var draw = function(spine, accum) {

    // retrieve current node
    var node = spine.last()

    // we are transforming a spine into pair {x, y} here
    var pair = spine.

        // firstly, reduce array of nodes to array of pivot points
        // retriving latter from their payloads
        map(function(node) {
            return {
                x: node.payload.x,
                y: node.payload.y
            }
        }).

        // then fold the array of point by adding their coordinates
        // itno one point
        fold(function(parent, current) {
            return {
                x: parent.x + current.x,
                y: parent.y + current.y,
            }
        })

    // making the result value
    var it = {
        // we put a version after the name
        id:    node.id + "-" + node.version,
        value: s(pair), 
    }

    // if any children exist, put them inside, too
    if (accum.length)
        it.items = accum

    return it
}

// This function checks if a rectangle was moved.

var willCascade = function(oldRect, newRect) {
    return oldRect.x != newRect.x || oldRect.y != newRect.y
}

// We are drawing the tree using our mock implementation here.

var tree1 = previewWithSpine(tree, draw)

// We are moving a node at path "a c" in the tree1 (with its children).

var tree2 = modifyAt(["a", "c"], tree1, willCascade, function(spine) {

    // get the payload of current node
    var top = spine.last().payload

    // return a new rect, located far far away
    return {
        x: top.x + 1000,
        y: top.y + 1000,
        w: top.w,
        h: top.h,
    }
})

// Here we redraw changed nodes.

var tree3 = previewWithSpine(tree2, draw)

// Here is the result of redrawing.

zoomAt(["a", "c"], tree3, function (spine) {
    return spine.last()
})