Running a no-dependencies Node module in Java

Sometimes you do something just because you wonder if you can. Today’s example is a prime example of that.

I wonder if it’s possible to run a no-dependencies Node module in Java, without running Project Avatar? The answer, of course, is yes, it is.

For my no-dependencies Node module, I picked semver.js – there’s a pretty well defined external interface there, and all it’s really doing in String manipulation, so there’s no external dependencies to worry about.

Before I go further, a caveat: I actually did this example in Groovy, mostly to save the extra typing necessary in Java, but the example shouldn’t require any knowledge of Groovy, and it should all work with only minor modifications in pure Java (JDK 8, since I’m using nashorn’s engine, but there’s no reason something similar shouldn’t work with Rhino as well).

If you like, you can run the example just by downloading the git repository and typing

gradlew

at the command line (provided that node and npm are already installed and in your path – if not, installing node is easy).

If you’ve never used JavaScript from within Java, it’s pretty easy.

ScriptEngineManager manager = new ScriptEngineManager();
ScriptEngine engine = manager.getEngineByName("nashorn");
Invocable inv = (Invocable) engine;

Get a manager, use it to obtain an engine, and (optionally) cast it to an Invocable instance.

With the engine, you can conveniently say

engine.eval("javascript code to run")

while with the invocable, you can say:

inv.invokeMethod(contextObject,"methodname",[param1,param2])

which is far more convenient if you don’t want to continuously do .toString and string concatenation.

So, with those two basic methods, let’s run a node module. First, we’ll need to set up an exports object, which node modules expect to exist.

engine.eval('exports = {}')

Then load and evaluate the server code:

File semverjs = new File('./node_modules/semver/semver.js')
engine.eval(semverjs.text);

Set the exports object to be the same as a server object, so our JS code will look a little more natural, and grab that object to use as the context object for invokeMethod (engine.get(varname) will fetch the JS object from Nashorn, and let you use it in Java):

engine.eval('semver = exports')
def semver = engine.get('semver')

With that setup, we can do a simple eval:

println engine.eval('semver.clean("1.2.3")')

or a simple invokeMethod:

println inv.invokeMethod(semver,"clean", "1.2.3");

A somewhat more complex invokeMethod (passing multiple arguments as an array, I needed to say “as Object[]” in Groovy to do an inline cast to an array of Objects):

println inv.invokeMethod(semver,"lt",['1.2.3','4.5.6'] as Object[])

but when we pass in an array as one of the parameters, it all goes sideways:

println inv.invokeMethod(semver, 'maxSatisfying',
                [['1.2.3','1.3.0'] as Object[],'~1',true] as Object[])

will return

TypeError: [Ljava.lang.Object;@c667f46 has no such function "filter" in  at line number 912

So, that’s not good. What’s going on? When you call invokeMethod with the array of parameters, Nashorn will place each of them as it receives them into the list of parameters on the JavaScript function. But for whatever reason, the Nashorn dev team decided that they would not convert Java arrays automatically into JavaScript arrays during this process – and when ‘semver.maxSatisfying’ tries to manipulate the first parameter as if it was a JavaScript array, it fails. And I can not find a public Java API in Nashorn to do the conversion. But I can find the JavaScript Nashorn function Java.from, which does that conversion.

There are two ways around this for this use case. I’m not especially fond of either.

First, you can install a shim, so that instead of calling the function which expects the JavaScript array, call the shim, which will do the conversion from Java to JavaScript.

def shim =
'''
semver.maxSatisfyingHack = maxSatisfyingHack;
function maxSatisfyingHack(rversions, range, loose) {
  var versions = Java.from(rversions)
  return maxSatisfying(versions,range,loose);
}
'''           
engine.eval(shim)
println inv.invokeMethod(semver, 'maxSatisfyingHack', [['1.2.3','1.3.0'],'~1',true] as Object[])

That works, but now you’re modifying the underlying JS, which isn’t too nice.

Alternately, you can use the underlying JS Java object, and call the from method on it using invokeMethod.

println inv.invokeMethod(semver, 'maxSatisfying', 
    [inv.invokeMethod(engine.get('Java'),'from',['1.2.3','1.3.0']),'~1',true] as Object[])

The downside of this method is that you’re using invokeMethod twice for each invoke, which is going to be a bit expensive.

Essentially, a node module without dependencies is nothing more than straight JavaScript with some conventions, so it’s not surprising that integration is possible. At some point, I’ll try integrating modules with dependencies – that should be much more involved.

Learning JavaScript

In the last couple weeks, I’ve had three different people ask “What’s the best way to learn JavaScript?”.

As all engineers know, if you do something more than twice you immediately want to automate it, so here’s a quick description of how I think the best way to learn JavaScript is.

First, get Crockford’s book: JavaScript: The Good Parts.

I think of it as filling the same place for JavaScript as the K&R book does for C – a baseline where you should start, as well as a clear, concise description of the language with only minimal degressions.

Next, I’d encourage you to read it, cover to cover… Then read it again. It’s good enough that I don’t think you’ll mind.

To try out your skills, you’ll probably want a command line interpreter that reads JavaScript. You could always use the “jrunscript” program that comes with Java – but I think an even better choice would be to pull up the console in Chrome, and start typing. Better still would be to create a small program on disk, and include it in a simple HTML web page, then use the Chrome console to add and subtract behaviors that way.

Once you understand why [1,2,13].sort() returns [1,13,2], you’re ready to move on…

Next, you’ll probably want to use JavaScript with HTML, on a web page. I strongly recommend you get Flanagan’s JavaScript: The Definitive Guide. At 1100 pages, it’s big. Real, real big. Don’t worry, you don’t have to read it right away – it’s just a great reference when you get stuck. It really can’t be beat for describing all the different JavaScript functions you can operate on in the DOM. There are other, free resources (notably at Microsoft and Mozilla) which do much the same thing, but nothing beats this monster of a manual for answering most of your questions.

But instead of going head-first into DOM API programming, I recommend that you instead also check out some of the wealth of libraries out there. Two in particular stand out: jQuery and underscore.

jQuery has tons of books out there, and I don’t have a favorite (I did read a few) – but before you get one, I’d recommend checking out the API Docs. They’re small, and the API is pretty well focused. There’s also a Learning Center, where they’ve gathered all the best information for getting started.

The underscore.js docs are so small, I think any book would be superfluous. Don’t worry if you don’t understand what most of the functions are for when you first look over them – it’ll (mostly) become obvious once you’ve used JavaScript to write a few simple programs. Just try to make yourself familiar with most of what it does, so you know that there’s a better way than writing hacky code yourself.

Master class stuff is mostly even more a matter of opinion than beginner work, but I rather like Addy Osmani’s Learning JavaScript Design Patterns, which is either available for free, or for purchase (and if you like it, do purchase a copy, to encourage that sort of behavior).

Similarly, both John Resig and Stoyan Stefanov are legends in the JavaScript community, and everyone thinks highly of their books (though I’m somewhat ashamed to say I haven’t cleared my schedule to do more than skim them).

That should be more than enough to get you started. I’d love to hear any suggestions anyone may have to improve this article.

Bootstrap for Responsive Design

This post is part of a series examining the Modern Web. Currently, I’m trying to assess pain points in creating a Single Page application, and to do that, I’ve created a simple application which does inventory management. You can find the (somewhat sloppy) code on Github, if you want to follow along.

After my previous post looking at the Model layer, today we’ll examine how to handle responsive design using Bootstrap. (Please forgive the hokey formatting in this post, WordPress Markdown support is still pretty badly broken.)

I just need to say it: using Bootstrap is a treat, and I’m utterly in love. Can you love a UI framework? Apparently so.

Consider the process of making a menu that will appear at the top of your page. You want it to look nice, both on mobile devices as well as the desktop. Let’s also make it “stick” to the top of the page, even when you scroll.

To do that, you take a nav tag, and decorate it with a few CSS classes:

<nav class="navbar navbar-default navbar-static-top" role="navigation">

The part that you want to display when collapsed goes into a separate header:

<div class="navbar-header">
    <button type="button" class="navbar-toggle" 
      data-toggle="collapse" data-target="#navbar-collapse">
        <span class="sr-only">Toggle navigation</span>
        <span class="icon-bar"></span>
        <span class="icon-bar"></span>
        <span class="icon-bar"></span>
    </button>
    <a class="navbar-brand" href="#home">JQ Product</a>
</div>

The three spans with class="icon-bar" are there to show a classic “three lines” icon when the menu is collapsed. Now, when the navigation menu is too small horizontally to display everything, only the three lines icon and your branding link are displayed.

After that, just list all the links you want to see in the navbar, as a list:

<div class="collapse navbar-collapse" id="navbar-collapse">
    <ul class="nav navbar-nav">
        <li>
            <a href="#products&page=1">Product</a>
        </li>
        <li>
            <a href="#categories&page=1">Category</a>
        </li>
    </ul>

(Note that since this div collapses, I’ve added the appropriate CSS classes. Uncollapsed, this will all appear horizontally, collapsed, this all appears vertically. It’s a nice effect on a phone.)

There’s even facilities to to add search forms, as well as to right justify elements of your menu:

        <form class="navbar-form navbar-right" role="search">
            <div class="form-group">
                <input id="searchinput" type="text" 
                    class="form-control" placeholder="Search">
            </div>
            <span id="search-nav-btn-holder">
                <div id="search-nav-btn" class="btn-group">
                    <button type="button" 
                       class="btn btn-default dropdown-toggle" 
                       data-toggle="dropdown">
                        Search
                        <span class="caret"></span>
                    </button>
                    <ul class="dropdown-menu" role="menu">
                        <li>
                            <a class="search-btn" 
                              href="#products&search=">
                                Search Products
                              </a>
                        </li>
                        <li>
                            <a class="search-btn" 
                              href="#categories&search=">
                                Search Categories
                              </a>
                        </li>
                    </ul>
                </div>
            </span>
        </form>
    </div>
</nav>

This last bit of code you see above sets up a form in the menu bar for search, pulls it all the way to the right, and adds a drop down selection button, using the dropdown-menu on a ul tag. All declaratively. Annotating an a tag with class="search-btn" even gives a nice rounded button which distinguishes search buttons from other types of buttons on the page.

As I said in the intro, I’m quite smitten with Bootstrap, and I could probably go on and on about what it does, but if this example looks interesting to you, check out their documentation on what components it offers, it’s quite good. Their whole website is a nice example of use as well, and view source is very instructive.

Next up, we’ll deal with some of the harder parts of creating your own Thin Server app – specifically, view management.

Thin Server the Hard Way (Model layer)

This post is part of a series examining the Modern Web. Currently, I’m trying to assess pain points in creating a Single Page application, and to do that, I’ve created a simple application which does inventory management. You can find the (somewhat sloppy) code on Github, if you want to follow along.

After my previous post looking at routing, today we’ll examine how to handle the model layer of our single page app.

Architecture

The first step on something like this is to decide on an initial architecture. QEDServer has a fairly simple REST API for fetching and updating records in the database – the only mildly tricky part is to format and pass it parameters. So a fairly lightweight wrapper around the jQuery AJAX API is probably all that’s required. Let’s model what how it’d be used, in this case for fetching a page of results containing the names of Categories for our products:

        qedModel.getCategories({
            page: currentPage,
            search: search,
            error: onFetchError,
            success: onFetchSuccess,
            complete: onFetchAlways
        });

Implementation

The REST API we’re using already has a paging facility (you pass it a URL param of ?page=number) as well as search (passing a URL param of ?q=searchterm), so the JavaScript API wrapper we need to develop only needs to smartly handle parameter building for the URL, which is a pretty simple task. We’ll also want to have success, error and complete callbacks, which are handled by the jQuery AJAX API already. So, the finished code is really pretty simple:

        getCategories: function getCategories(params) {
            var error = params.error || null;
            var success = params.success || null;
            var complete = params.complete || null;
            var page = params.page || 1;
            var search = params.search;
            var endpoint = '/categories.json?';
            if (!!search) {
                endpoint = endpoint + '&q=' + search;
            }
            endpoint = endpoint + '&page=' + page;
            $.ajax({
                type: 'GET',
                url: endpoint,
                success: success,
                error: error,
                complete: complete,
                dataType: 'json'
            });
        }

A thin wrapper around the AJAX API, which simply builds a URL and returns the results in the supplied callbacks.

Much like building a front controller, this was trivially easy, but it didn’t have to be – there’s other features we could add in here, the most important of which are cacheing and pagination. Rather than always using the server to handle pagination and fetching values from the server every time, it would be far, far better to prefetch large chunks of data from the server, and let the client model layer handle the caching. But because of the design of the QEDServer REST API, which only allows fetching of 10 records at a time, that would have been counter productive in this case. And cacheing server data on the client opens up the problem of currency – making sure that the client data and server data are in sync. This implementation mostly just hand-waves that away.

Pain Points

In my simple implementation, there really were no pain points, but as I mentioned, I’d hope that any client side Model layer would handle cacheing and pagination as well as offer some hints on how to implement data synchronization.

So, with the Model and Front Controller out of the way, it’s time to move into the View Layer, which presented far more problems. But first, we’ll detour into what capabilities Bootstrap provides.

Thin Server the Hard Way (Routing)

This post is part of a series examining the Modern Web. Currently, I’m trying to assess pain points in creating a Single Page application, and to do that, I’ve created a simple application which does inventory management. You can find the (somewhat sloppy) code up on github, if you want to follow along.

Previously, I covered the basic architecture. Today I’d like to examine how to handle routing via a front controller. As I’ve mentioned before, this proved to be one of the easier tasks.

As background, recall that the anchor is the last portion of every URL, and is set off from it via the # character, which is also called a hash (or octothorpe, if you’re a serious geek). All of our href values will just have these anchor tags, such as href="#home". When a user clicks on that link, we want to rerender the page to make it look to the user like they’ve gone to a new place – but without having to roundtrip to the server to get all of the new HTML. Possibly, we may not have to go to the server at all, if we’ve cached values. This will give the user a much snappier experience, and is pretty much how most modern web sites work nowadays (though some also use the newish history.pushState function, which lets you avoid all this anchor stuff on compatible browsers).

The pattern to follow here is a simple one: For any action which you want the user to be able to bookmark, use an anchored URL. For any action which is inappropriate to bookmark (such as deleting a record), use a click handler.

First, we create a module (jqcontroller) which will handle all the routing. Inside it, we’ll create a hardcoded routing table, which will associate names with the route to take:

// routing table
var routingTable = {
    home: jqproduct.displayHome,
    products: jqproduct.displayProductsPage,
    categories: jqproduct.displayCategoriesPage,
    productAdd: jqproduct.displayProductAddPage,
    defaultPage: jqproduct.displayHome
},
defaultPage = jqproduct.displayHome;

So, when we receive a URL that looks like #home, we’ll call the function jqproduct.displayHome.

We also need to create an onhashchange handler:

function hashChangeHanderSetup() {
    // when the hash changes, go through the router
    $(window).on('hashchange', function router() {
        jqcontroller.route(location.hash);
    });
}

Here, we’re using jQuery to add a new handler on the window object. When the URL’s hash changes, call the jqcontroller.route function, passing in the new hash value.

Of course, we have to call that setup message during initialization for it to work. While we’re at it, let’s allow for routing to an initial location, so that when users bookmark the location, navigating back to it functions correctly:

initializeModule: function initializeModule() {
    hashChangeHanderSetup();
    // initial route
    jqcontroller.route(location.hash);
}

The actual router code called by these functions couldn’t really be much simpler, though it’s complicated by one additional requirement – we also want the hash to contain parameters, so that if you search, for instance, by product name, the hash may look like #products&search=Time – we’ll need to strip that out, and so we’ve created an additional utility method to do that called getPage:

route: function route(url) {
    try {
        var page = pub.getPage();
        var hash = url.split('#')[1];
        if (!!hash) {
            location.hash = hash;
        }
        if (!page || !routingTable[page]) {
            defaultPage();
        } else {
            routingTable[page]();
        }
    } catch (error) {
        // in production, this could write to console, 
        // or do something else useful with error reporting
        window.alert(error);
    }
}

Here, the meat of the code is simply calling routingTable[page](), which means “look up the value of page in the routing table, and execute that as a function”.

So, that’s it in a nutshell. As I mentioned, there’s additional code to handle parameter passing in a hash, but otherwise, there’s not much else.

As pain points go, this isn’t so bad. It’d be nice to have all this code encapsulated in a reusable library, but doing it myself wouldn’t be a terribly difficult task. Of more concern is that there isn’t any support in my code for history.pushState() and related APIs. Though as I mentioned, there needs to be server side support for that as well.

So, any MV* framework would need to support such a simple front controller pattern, as well as (optional) pushState. But since that’s a rather low bar, I don’t expect that to be an issue.

Next up, I’ll talk about implementing the Model layer, which was another fairly easy task.

Thin Server the Hard Way (Basic Architecture)

As I mentioned in my previous post, I’m looking to create a basic Thin Server Architecture without any particular framework, mostly to see what the pain points are. Knowing what problems these MV* frameworks are trying to solve is going to be critical in further evaluation.

So, with that as the goal, I created a simple Thin Server front end around the REST endpoints provided by QEDServer.

I’ve set up a Github repository to hold all the Thin Server clients I’m writing, and made this project a subdirectory in the repo. To use this subdirectory, download QEDServer, clone the Github repo, and symlink QEDServer public directory to point to the subdirectory. I do recommend you try this out if you’re going to read further, since it’ll show clearly what kinds of nifty responsive layout options you get from Bootstrap, if nothing else.

The app is really just two monolithic blocks – a rather large HTML file, and a very large JavaScript file. There are also two other files – a load indicator gif (generated from a lovely website devoted to that purpose), as well as a tiny css file to augment the base Bootstrap setup.

As a side note before we go any further, I do feel the need to mention that I’m not particularly proud of this code – it served it’s purpose, and it’s mostly bug free, but as I continued on, I started a number of refactorings which I never quite finished. For that reason, I almost didn’t release it – but in the end, I decided it was worthwhile as a launch point for a discussion.

So, on the to code.

HTML file

The HTML file (about 250 lines) can be thought of being divided into about 4 separate sections. I’ll outline them in summary, and then go into detail in a later post. For added maintainability, I went with an Unobtrusive JavaScript approach, meaning that there’s no JavaScript in the HTML at all, just script tags which act on the HTML once loaded.

Header info

The header info contains the loading information for all the base JavaScript and CSS. Since I wanted to keep this simple, I just used CDN loaded versions of all the libraries. Note that some additional shims are required to get things running for IE8, but that’s not something I was interested in testing out – like most people, I can’t wait for that browser to die in a fire.

Nav bar

This section contains the Navigation and branding that’s used throughout the application. The markup is pretty simple, and really shows off what kinds of things that Bootstrap can do. That’s the topic for a whole separate post.

Swappable Divs

Underneath the navigation section are all the different “pages” which will be visible to our users. Since only one will be visible at any given time, I opted to place all of them in separate divs, and then switch between them via hide/show. This is a very performant way to do things, but has two drawbacks – you take a hit on initial load, and for large apps, it will become utterly unwieldy.

Cloning area

Similarly, I have a separate cloning area for sections of HTML code which I’ll be copying and placing into the app, completely wrapped in a hidden div. Again, this is a simple, fairly performant way to do things, at a cost in initial load and maintainability.

JavaScript file

At almost 800 lines, this ended up being a pretty big lump of code. I opted to use the module pattern (with import and export) to organize things. I further divided up the code into several modules, to do a proper division of responsibilities – and since it was going to be evaluating MV* frameworks, it seemed to make sense to use a similar structure.

View layer

The first module just controls the view layer (in conjunction with the HTML, meaning that that doesn’t fit properly into an MVC pattern). A variety of functions handle displaying the different pages via show/hide on the divs in the page, as well as event handlers, an alert messaging system, and other action functions for adding and deleting products. I refactored this code a number of times (and actually stopped in the middle of my last refactoring), but never really got the kind of cleanliness that I wanted. In particular, I really wanted to separate out the binding between the rendered HTML and the functions that acted on it that I felt would be necessary for maintainable code. Of the three layers I tackled, this one was the one that left me the most dissatisfied.

Front Controller / Router

By using onhashchange as a listener for the routing code, it was pretty easy to come up with a basic routing mechanism. With the exception of some annoying boilerplate that I had to write for parameter handling, this proved to be some of the easiest code to write for the whole app. While complexity would grow linearly with the complexity of the app, it doesn’t look like this is really something that other MV* frameworks are going to address – but maybe they’ll surprise me. It would be nice to have something that handled history.pushState automatically, but since QEDServer doesn’t really handle that, I didn’t take a stab at it.

Model layer

A thin ajax layer across the REST interface of QEDServer was, like the router code, rather easy to write (once jQuery’s excellent ajax support was added in). Since it’s only a thin layer, it does expose the underlying data structure of the REST server to the View layer, but you could just as easily change it to massage the returned data to any desired format, in the event that the returned data changed it’s structure. While there was a tiny bit of boilerplate, this doesn’t seem to be that big a deal. Adding in CORS support looks easy, but I didn’t try it, since QEDServer didn’t support it. Like the router code, this looks like complexity will grow linearly with the complexity of the REST API being modeled, and it’s not clear how a framework could really improve on things. Again, I’m hoping somebody will surprise and delight me by proving me wrong.

Initialization and utility methods

The end blocks contain a variety of utility and initialization methods. There was a fair bit of code in here that really felt like reinventing the wheel, and in the end, I even wrote a really primitive templating solution – I’ve no doubt that this is tackled in any number of other places (and more recent efforts have certainly proved that out).

Pain points

I was more than a little surprised by what I found. The two bits I thought would be hard, routing and Ajax retrieval from REST, were handled pretty easily, while the part I thought I knew how to do, view manipulation, proved to be a pretty tough nut to crack.

• Templating is a pretty large need.
  • Balancing initial load time with performant changes
  • Better code organization for large applications
• A simple setup for routing would be convenient, but not especially critical
• Removing some boilerplate for REST endpoint wrapping would be a nice-to-have
• View state management looks to be critical.
  • Binding both data values and entire views to HTML tags
  • Binding event handlers
  • Managing view transitions and lifecycle

I’ve already ported this application to the first MV* framework that I looked it, Backbone, but it’s probably worthwhile going through a few more items on this first effort first before diving in. Look for that next.

Thin Server the Hard Way (Getting Set Up)

After the diversion I just had with Java 8, time to get back to describing some features of the Modern Web.

There are any number of MV* client side frameworks out there. I’ve already mentioned TodoMVC, where you can find an extensive list, as well as sample code for each.

But before you evaluate tools, it always pays to know what pain points you’re trying to solve. So, with that in mind, I decided my first task would be to do a Thin Server application the hard way, using only jQuery to manipulate the DOM and handle the data.

Now, I didn’t want to not learn anything new during this exercise, so to keep in interesting, I added in one new dependency, Bootstrap.

So, here’s the recipe list I started with to develop the application:

Tools in Use

• Brackets, which I wanted to evaluate as an IDE
• QEDServer, which provides default REST endpoints, as well as a public directory to serve files
• jQuery, because why on earth would you use the built in DOM APIs if you didn’t have to?
• Bootstrap, to make the site look pretty

So, not quite starting at the bare metal, but close enough.

jQuery

I’m not going to go over jQuery at all in describing my solution. Even though it was the first time I used it for writing anything more than a few lines, I think it’s pretty likely that anyone reading this will almost certainly know it. And if you don’t… There are any number of books out there on it, but before you invest in a book, just check out the API Documentation. It’s a small API, and quite restrained in what it’s trying to accomplish. Essentially, it’s for DOM manipulation, AJAX requests, and handful of utility functions to make those two functions easier. If you already know much about the browser DOM, it’ll take you a weekend to get up to speed. If you don’t know the browser DOM… then that’s the problem you need to solve, not learning jQuery.

Bootstrap

There are a number of “website boilerplate” projects out there. Besides Bootstrap, Foundation and HTML5 Boilerplate seem to be the most popular – but here’s a list of 10, if you’re interested.

I picked Bootstrap simply because it’s the most popular one right now, and they handle a bunch of things out of the box that I thought would be quite tricky for me to do on my own.

Bootstrap provides you with a set of CSS and JavaScript libraries that you can use as a starting point for your pages, and by default, their look and feel is both clean and modern. Additionally, adding simple effects (like collapsing navigation bars, popups, and closable alert boxes), can be done almost entirely declaratively. Like jQuery, I found it to be incredibly simple to use, and rock solid – I only found one bug during the process, and that was certainly because I was doing something that was an unexpected use of the product.

Also, because it’s the most popular framework, I was able to find lots of information on the web about various setup questions, including the fix for the bug I found.

Bootstrap’s only requirement was that jQuery be included in the same page, so that also worked out pretty well for me.

Conclusions

I’d certainly recommend both libraries as something that a beginner should start out with – they’re both self contained and easy to learn.

Next up, I’ll out line the architecture that I used to create my first Thin Server application

Java 8 features recap

Just a quick post to recap the series of posts I just did on using Java 8 to handle some sample interview questions.

To learn the Java 8 API’s, I relied on Cay Horstman‘s just released book, Java SE 8 for the Really Impatient, and I can’t recommend it enough. It’s quite good.

The topics I covered were:

• Finding all the Palindromes in English using Streams
• Combining Sorted Lists, again using Streams
• Getting the largest sum of a sublist, this time using Streams, Futures, Completable Futures, parallel processing, etc.
• Getting Bacon Numbers Parts 1, 2, 3, 4 – using Streams, parallel processing, method expressions, Map.merge

See the individual posts for more.

Bacon Numbers with Java 8, part 4

This fourth part of the series of posts on getting a Bacon Number with Java 8 will probably be a bit of an anticlimax. As a reminder, we’re covering:

Given a large hash table whose keys are movie names and whose values 
are a list of actors in those movies, write a function to determine 
the Bacon Number of a particular actor.

We created sample data with Stream.generate, we also created a micro benchmark with functional interfaces, to measure how we were doing. And last post, we modified the data to be easier to search.

As the last step, we actually need to search that modified data. Since we only want to find the closest relationship, a Breadth First Search is certainly the way to go.

Set<Integer> visited = new HashSet<>();
Integer result = null;
Set<Integer> degreelist = actors.get(firstactor);
if (degreelist == null || actors.get(secondactor) == null) {   //short circuit
    result = -1;
} else {
    int degree = 1;
    while (result == null) {
        if (degreelist.contains(secondactor)) {
            result = degree;
            break;
        }
        degree++;
        if (degree > DEEPESTSEARCH) {
            result = DEEPESTSEARCH;
            break;
        }
        visited.addAll(degreelist);
        Set<Integer> nextDegreelist = new HashSet<>();
        degreelist.stream().forEach((i) -> {
            nextDegreelist.addAll(actors.get(i));
        });
        nextDegreelist.removeAll(visited);
        if (nextDegreelist.isEmpty()) {
            result = -1;
            break;
        }
        degreelist = nextDegreelist;
    }
}

Assuming we’re starting with a Map called actors, and two ints for the first and second actors to find. Create a Set of all visited actors (starting at the first one), and then just start iterating through each level, looking for the second one. When we find it, we’re done. Note that I use a forEach on the Stream from each degree to build the Set that I search. But we can do better:

        Set<Integer> visited = new HashSet<>();
        Integer result = null;
        Set<Integer> degreelist = actors.get(firstactor);
        if (degreelist == null || actors.get(secondactor) == null) {   //short circuit
            result = -1;
        } else {
            int degree = 1;
            while (result == null) {
                if (degreelist.contains(secondactor)) {
                    result = degree;
                    break;
                }
                degree++;
                if (degree > DEEPESTSEARCH) {
                    result = DEEPESTSEARCH;
                    break;
                }
                visited.addAll(degreelist);
                Set<Integer> nextDegreelist = degreelist.parallelStream().unordered()
                        .flatMap((i) -> actors.get(i).stream())
                        .collect(Collectors.toSet());
                nextDegreelist.removeAll(visited);
                if (nextDegreelist.isEmpty()) {
                    result = -1;
                    break;
                }
                degreelist = nextDegreelist;
            }
        }

Here, I build the Set I’m going to search through using a unordered parallelStream. I collapse the results of that Stream using flatMap into a Stream of Integers, then collect it at the end into a Set. All this is much more efficient, and results in a clock time savings of about 50% on an 8 core machine.

A word about what map and flatMap do, since I haven’t mentioned flatMap before: map will take a result on your Stream, and map it to a different value, applying the function you supply to each element of the Stream. Similarly, flatMap does the same thing, but it’s built to work with Streams as the returned object, and will unpack them from a Stream of Streams (of some Class) into a single continuous Stream of the Class. So this mapping function is taking a Stream of Integers, using them to look up a Set of Integers, and then unpacking that into individual Integers that it then returns as a Stream. All in one concise function.

At the end of that flatMap process, I bundle that Stream back up into a Set via the call to collect, and that’s what’s used for the next search.

And there you have it: We’ve not just found the Bacon Number as specified, we’ve enabled discovering any relationship degree at all.

All the source code for this and the previous 3 posts can be found in the gist. I’d love to know what you thought.

Bacon Numbers with Java 8, part 3

Continuing the work of my previous post, we’re examining the following question:

Given a large hash table whose keys are movie names and whose values 
are a list of actors in those movies, write a function to determine 
the Bacon Number of a particular actor.

We created sample data with Stream.generate, we also created a micro benchmark with functional interfaces, to measure how we were doing. Now, let’s massage the data to get it into a form we can easily search.

As I mentioned in the first post, the main problem here is that the form of the data is completely inappropriate for the kind of search we wish to perform.

Movie 1 --
  -- Actor 1
  -- Actor 2
Movie 2 --
  -- Actor 2
  -- Actor 3

Far better would be to associate the actors with each other, so we could readily relate them.

Actor 1 --
  -- Actor 2
  -- Actor 3
Actor 2 -- 
  -- Actor 1
  -- Actor 3
Actor 3 --
  -- Actor 2

Performing this transformation is a relatively simple task.

Map<Integer, Set<Integer>> actorRelations = new HashMap<>();
// get all the list of actors for each movie
for (List<Integer> movie : set) {
    // for each actor in a movie
    for (Integer actor : movie) {
        // get the list of actors
        Set<Integer> coactors = new HashSet(movie);
        // remove self
        coactors.remove(actor);
        // add to the list of relations
        actorRelations.merge(actor, coactors,
            (existing, update) -> {
                existing.addAll(update);
                    return existing;
        });
    }
}

We’re going to create a Map, with the id of the actor as a key, and containing a Set of all the actors they have shared a movie with. Nothing new or interesting here, except one thing – the Map.merge method, which takes three parameters. The first is the key to operate on, the second, the value we wish to place into the Map. The third is a Function interface, called if the value is already set, and passed the existing value along with the new one. In our case, we wish to merge the two Sets, and we do so in the usual way.

We can do much the same thing with a Stream implementation, and I think it’s rather easier to read:

Map<Integer, Set<Integer>> actorRelations = new HashMap<>();
set.stream().forEach((movie) -> {
        movie.stream().forEach((actor) -> {
            Set<Integer> coactors = new HashSet(movie);
            coactors.remove(actor);
            actorRelations.merge(actor, coactors,
                    (existing, update) -> {
                        existing.addAll(update);
                        return existing;});
        });
    });

This operates slightly faster than the previous implementation, but only by a little.

To go through this — take the Set that contains the movies, and create a Stream. For each element in the Stream (and remember, that element is a List), create another Stream. For each element on that Stream, create a Set of all actors in that film (self excluded) and add that to the Map of relationships, merging if necessary.

Of course, one of the best things that you get when using Stream is the ability to change it to parallel processing with only a couple of extra method calls:

Map<Integer, Set<Integer>> actorRelations = new ConcurrentHashMap<>();
set.parallelStream().unordered().forEach((movie) -> {
    movie.stream().forEach((actor) -> {
        Set<Integer> coactors = new HashSet(movie);
        coactors.remove(actor);
        actorRelations.merge(actor, coactors,
            (existing, update) -> {
                existing.addAll(update);
                return existing;
            });
    });
});

This is the same as above, with two changes – instead of a HashMap, use a ConcurrentHashMap, and just add .parrallel().unsorted() to the Stream code. With that simple change, the clock time for this drops by over half (on an 8 core machine).

Next up, we’ll finish working on this problem by actually running the search.