The blog of dlaa.me

Yesterday at its Build conference, Microsoft released the Visual Studio Code editor which is a lightweight, cross-platform tool for building web and cloud applications. I've been using internal releases for a while and highly recommend trying it out!

One thing I didn't know about until yesterday was support for Tasks to automate common steps like build and testing. As the documentation shows, there's already knowledge of common build frameworks, including gulp for Node.js and io.js. But for simple Node projects I like to automate via npm's scripts because they're simple and make it easy to integrate with CI systems like Travis. So I whipped up a simple tasks.json for Code that handles build, test, and lint for typical npm configurations. I've included it below for anyone who's interested.

Note: Thanks to metadata, the build and test tasks are recognized as such by Code and easily run with the default hotkeys Ctrl+Shift+B and Ctrl+Shift+T.

Enjoy!

 

{
  "version": "0.1.0",
  "command": "npm",
  "isShellCommand": true,
  "suppressTaskName": true,
  "tasks": [
    {
      // Build task, Ctrl+Shift+B
      // "npm install --loglevel info"
      "taskName": "install",
      "isBuildCommand": true,
      "args": ["install", "--loglevel", "info"]
    },
    {
      // Test task, Ctrl+Shift+T
      // "npm test"
      "taskName": "test",
      "isTestCommand": true,
      "args": ["test"]
    },
    {
      // "npm run lint"
      "taskName": "lint",
      "args": ["run", "lint"]
    }
  ]
}

Updated 2015-05-02: Added --loglevel info to npm install for better progress reporting

Updated 2016-02-27: Added isShellCommand, suppressTaskName, and updated args to work with newer versions of VS Code

Sitting on a plane recently looking for a distraction, I recalled a programming challenge by James Michael Hare: Little Puzzlers-Is Tree a Binary Search Tree?. All I had to work with was a web browser, so I used JavaScript to come up with a solution. James subsequently blogged a recursive implementation in C# which is quite elegant. Wikipedia's Binary search tree page uses the same approach and C++ for its verification sample.

Because I did things a little differently, I thought I'd share - along with a few thoughts:

/**
 * Determines if a tree of {value, left, right} nodes is a binary search tree.
 * @param {Object} root Root of the tree to examine.
 * @returns {Boolean} True iff root is a binary search tree.
 */
function isBinarySearchTree(root) {
  var wrapper, node, stack = [{ node: root }];
  while (wrapper = stack.pop()) {
    if (node = wrapper.node) {
      if ((node.value <= wrapper.min) || (wrapper.max <= node.value)) {
        return false;
      }
      stack.push({ node: node.left, min: wrapper.min, max: node.value },
                 { node: node.right, min: node.value, max: wrapper.max });
    }
  }
  return true;
}

Notes:

• Tree nodes are assumed to have a numeric value and references to their left and right nodes (both possibly null).
  • I used the name value (vs. data) because it is slightly more specific.
• I decided on an iterative algorithm because it has two notable advantages over recursion:
  • In the worst case for a tree with N nodes, an iterative solution has bookkeeping for N/2 nodes (when starting to process the leaf nodes of a balanced tree assuming nodes were queued) whereas a recursive solution has bookkeeping for all N nodes (when processing the deepest node of a completely unbalanced tree).
    • Because there are two recursive calls, I don't think tail recursion can be counted on to fix the worst-case behavior.
  • The memory used for bookkeeping by an iterative solution comes from the heap which is generally much larger than the thread stack.
  • To be fair, neither advantage is likely to be significant in practice - but they make good discussion points during an interview. :)
• The iterative algorithm has a disadvantage:
  • Bookkeeping requires an additional object type (wrapper in the code above) which associates the relevant min and max bounds with pending node instances.
    • ... unless you avoid the wrapper by augmenting the node elements themselves.
      • ... which is quite easy in JavaScript thanks to its dynamic type system.
        • ... but still a violation of the separation of concerns principle.
    • The creation/destruction of wrapper objects creates additional memory pressure.
      • Although these objects are short-lived and therefore low-impact for typical garbage collection algorithms.
• I intended the code to be concise, so I made use of assignments in conditional expressions.
  • This is not a practice everyone believes in (myself included!), but it seemed acceptable here.
• The code uses a stack (vs. a queue) because stacks tend to be simpler than queues - especially when implemented with an array.
• I made use of the fact that comparing a number to undefined evaluates to false so I could avoid specifying explicit minimum/maximum values (as in the Wikipedia example) or making HasValue checks (as in James's example).
• If you have a different approach or a suggestion to simplify this one, please share!
  • And note: I'm interested in algorithmic changes, not tweaks like removing extra parenthesis. :)