Image source

Comment Trees and Recursion with RxJava

Recently I’ve been working on a Hacker News client as a way to brush up on some Android technologies and to have a canvas to work on some app design. The first screen I built would display the top stories on Hacker News. The second would be a detail screen with the content of a story, and more importantly comments from the community.

It turns out comments are logically stored in n-ary trees in order to accommodate n-comments, each with any combination of n-deep child comments. Once we have our data structured properly, we can display the comments with some good old-fashioned preorder tree traversing.

Assuming in this iteration we only intend to fetch and display these comments, on the presentation side we simply need a list of items to display. Reducing the dataset to a list, we need some indicator of how much to indent them, so the user understands which parent comment a child comment is replying to.

Constructing our tree

Assume we have the following API:

@GET("item/{id}.json")
Item getItem(@Path("id") long id);

We can recursively fetch our comments and construct our tree:

void fetchChildren(Item item) {
  if (!item.hasChildren()) return;

  List<Item> children = new ArrayList<>(item.childIds.size());
  for (Long childId : item.childIds) {
    Item child = api.getItem(childId);
    children.add(child);
    fetchChildren(child);
  }

  item.children = children;
}

Creating a list to display

Once we have our tree handy, we use recursion to traverse a comment tree to get a simple list to display:

List<Item> preorderTraversal(List<Item> list, Item item) {
  list.add(item);

  if (item.hasChildren()) {
    for (Item child : item.children) {
      child.indent = item.indent + 1;
      preorderTraversal(list, child);
    }
  }

  return list;
}

Great, this works. Diving into some of the popularly used Android libraries today, I wondered what this would look like with RxJava.

Recursive calls with RxJava

Let’s redo our API call with Observables:

@GET("item/{id}.json")
Observable<Item> getItem(@Path("id") long id);

Now we construct our tree…and produce a list to display at the same time?

public Observable<Item> getComments(final Item parentItem) {
  if (parentItem.hasKids()) {
    return Observable.merge(
      Observable.just(parentItem),
      Observable.fromArray(parentItem.getKids())
        .flatMap(ids -> getItems(ids))
        .flatMap(item -> {
          item.indent = parentItem.indent + 1;
          return getComments(item);
        })
    );
  } else {
    return Observable.just(parentItem);
  }
}

Wow, that’s so much more concise. Here we’re able to both fetch comments and combine them into a stream with the order we want to display them with, all in one go. You can see the preorder traversal part of this with the order of parameters in the Observable.merge() call — parent, then the recursive call on its children. From here we can call this method, subscribe to the observable returned, and populate comments as they’re fetched.

Really enjoying RxJava so far and thinking about things in streams. Looking forward to discovering other cool ways to apply it to new and existing code.