Utils for trees: Grid Snap and Navigation

example.js

let R         = require("./node_modules/ramda")
let treeUtils = require("./tree-utils")
let {inspect} = require("util")

show = x => inspect(x, {depth: null})
log  = console.log

///////////////////////////////////////////////////////////////////////////////

// We need some tree type to play with. Lets define one.
//
class Tree {
    constructor(name, x, y, ...children) {
        Object.assign(this, {name, coord: {x, y}, children})
    }

    // Default output of "inspect" is unreadable, to say the least.
    //
    [inspect.custom]() {
        let {name, coord: {x, y}, children, navigation = {}} = this
        return {
            name,
            coord: {x, y},
            navigation: {
                up:    navigation.up    === undefined? "-" : navigation.up.name,
                down:  navigation.down  === undefined? "-" : navigation.down.name,
                left:  navigation.left  === undefined? "-" : navigation.left.name,
                right: navigation.right === undefined? "-" : navigation.right.name,
            },
            children
        }
    }
}

let tree = (...args) => new Tree(...args)

// Mkay, lets define config for that type.
let config = {
    x:        R.lensPath(["coord", "x"]),
    y:        R.lensPath(["coord", "y"]),
    children: R.lensPath(["children"]),
    up:       R.lensPath(["navigation", "up"]),
    down:     R.lensPath(["navigation", "down"]),
    left:     R.lensPath(["navigation", "left"]),
    right:    R.lensPath(["navigation", "right"]),
}

// Now we can do things!
//
let {
    snap,             // snap nodes to the grid
    writeNavigation,  // write neighthbors into the node
    mapTree           // do "map" on the tree
} = treeUtils.using(config)

///////////////////////////////////////////////////////////////////////////////

let scheme = `
       qux    lol
foo    bar   [kek]  rolf
              burp
`

let node0 = tree("kek", 0.1, 0.2)

// All coordinates are taken from scheme above with slight offsets
let tree0 = tree("foo", -1.8,0.2,
    tree("bar", -0.9,0.2,
        tree("qux", -1.3,1.2)
    ),
    tree("lol", 0.2, 1.3,
        tree("burp", 0.2, -0.8),
        node0,
        tree("rolf", 1.1, -0.1)
    )
)

///////////////////////////////////////////////////////////////////////////////

// First, lets map(snap) over the whole tree to 1-unit grid.
//
let tree1 = mapTree(tree0, snap({x: 1, y: 1}))

// Then we write {up, left, right, down} navigation accelerators.
//
let tree2 = writeNavigation(tree1)

// Lets see what we got on all stages:
//
log(scheme)
log(show(tree0, {depth: null}))
log(show(tree1, {depth: null}))
log(show(tree2, {depth: null}))

tree-utils.js

/*
    Here we from config (pack of lenses) generate 3 functions.

    But wait, lets define what config is!

    > type Config = {
    >     x, y     : Lens<Tree, Number>,  // coordinates
    >     children : Lens<Tree, [Tree]>,  // child nodes
    >     up, ...  : Lens<Tree, Tree>,    // nodes in given direction
    > }

    I use lenses here, because I don't want to depend on concrete tree.
    If you are to use this, just provide this "Config" interface to your type.

    Lets go back to those 3 functions:

    - snap(Tree, {x: Number, y: Number}) : Tree

      Snaps 1 node to given grid. The "x" and "y" are the cell sizes for the grid.

    - writeNavigation(Tree) : Tree

      Writes nearest neighbors to each node of the tree, using "up", "down", "left" and "right" lenses.

    - mapTree(Tree, Node => Node) : Tree

      Applies a function to each node of the tree. Yeah, I can do that w/o
      any knowledge of what your tree is - just using the "children" lens.
*/

let R = require('./node_modules/ramda')

let patchFuckingRambda = action => (lens, value, source) =>
    Object.assign(
        Object.create(source.__proto__),
        action(lens, value, source)
    )

let Rset  = patchFuckingRambda(R.set)
let Rover = patchFuckingRambda(R.over)

module.exports.using = cfg => {
    let {x, y, children, up, down, left, right} = cfg

    // Snaps the coordinate.
    //
    let snapCoord = step => x => Math.round(x / step) * step

    // Since we have "children" lens, we can "map" the tree.
    //
    let mapTree = (tree, f) => {
        function aux(tree) {
            let descendants = R.view(children, tree).map(aux)
            return Rset(children, descendants, f(tree))
        }
        return aux(tree)
    }

    // Collect all nodes from the tree.
    //
    // Copies ALOT.
    //
    let allNodes = tree => {
        var acc = []
        mapTree(tree, node => acc.push(node))
        return acc
    }

    // Return a predicate succeeding only if its argument
    // is in given direction from given node.
    //
    // For instance, direction "up" is (-45 degree, 45 degree) from ray going up.
    // (Look onto your Wi-Fi symbol to see what "up" is)
    //
    let onlyDirection = (node, dir) => {
        let x0 = R.view(x, node)
            y0 = R.view(y, node)

        return otherNode => {
            let dx = R.view(x, otherNode) - x0
                dy = R.view(y, otherNode) - y0

                isVertical   = Math.abs(dy) >= Math.abs(dx)
                isHorisontal = Math.abs(dy) <= Math.abs(dx)

            return (
                // Current node should not be checked.
                //
                dx == 0 && dy == 0? false :

                dir == "up"?    isVertical   && dy > 0 :
                dir == "down"?  isVertical   && dy < 0 :
                dir == "left"?  isHorisontal && dx < 0 :
                dir == "right"? isHorisontal && dx > 0 :
                undefined
            )
        }
    }

    // Distance between 2 nodes.
    //
    let distanceTo = node => other => {
        let dx = R.view(x, node) - R.view(x, other)
            dy = R.view(y, node) - R.view(y, other)

        return Math.sqrt(dx * dx + dy * dy)
    }

    let by = f => (x, y) => f(x) - f(y)

    // Find node nearest to "node" in "tree" in given "dir"ection
    //
    let nearest = (nodeset, node, dir) =>
        nodeset
            .filter(onlyDirection(node, dir))
            .sort(by(distanceTo(node)))
            [0]

    let snap = grid => node =>
        Rover(x, snapCoord(grid.x),
        Rover(y, snapCoord(grid.y),
            node))

    let writeNavigation = (tree) => {
        let nodeset = allNodes(tree)
        return mapTree(tree, node =>
            Rset(left,  nearest(nodeset, node, "left"),
            Rset(right, nearest(nodeset, node, "right"),
            Rset(up,    nearest(nodeset, node, "up"),
            Rset(down,  nearest(nodeset, node, "down"),
                node)))))
    }

    return {mapTree, snap, writeNavigation}
}