Data Structures

Data structures are the bones of most good program implementations. Using proper data structures, allows you to manipulate your application state, with ease. Adding pieces together, sorting a set, filtering, searching... they're all just operations on your structures, and some structures are better for some operations than others. Being able to transform your data structures to other data structures can be a big help in getting the simplest implementation of what you need into your text editor (this is stuff that your IDE can't do for you, yet).

While this discussion transcends programming languages, I'm going to focus on data structures in JavaScript. This means arrays and objects (string keyed hash maps), for the most part. There are more structures coming with ES6 and ES7, but availability without polyfills is still pretty sparse. Also, we can get a lot with just these two basic structures.

Designing Data Structures

The first step to good programming is always thinking. If we're being honest, I'd say that programming is at least 80% critical thinking. After you have some experience and are fluent in a language, getting the program running is beyond simple. Deciding how to maintain and manipulate the application state is the part of programming that requires thought and creativity.

I'm going to be using a vehicle filtering application as an example (mostly because I did some stuff around this, recently). This application assumes a few things, I'll try to explain as we come across them.

So, let's think about the elements of this application. All of the actual filtering is done on the back end. We have an event handler attached to each checkbox to submit the form every time an of them are changed. We'll call a function later to do that, without defining it, so we can focus on the topic, at hand. We're only concerned with maintaining the state of the filters.

The Model

I usually do this part with pencil and paper, erasing and scratching out often. I've done that work for you, but just know, you don't usually just land on the right structure on your first pass.

All of our filters are check boxes. We also maintain counts of how many vehicles will be resulting when each box is checked, as well as keeping a reference to the element.

CheckboxFilter = {
  name: <string>,
  checked: <boolean>,
  vehicleCount: <number>,
  element: <Node>
}

Then we have the filters in groups by category (think year, make, model, color, etc...). So, that model ends up looking like this:

FilterGroup = {
  name: <string>,
  filters: [<CheckboxFilter>],
  element: <Node>
}

We'll then encapsulate these groups in an object, to keep everything together and easily findable.

FilterState = {
  name <string>: <FilterGroup>
}

Using Arrays

Our check boxes need to maintain a certain order, so they should be an array, everything else is an object. There are some other reasons to store data in an array. Sorting and reversing (granted, both operations having to do with order), mapping, reducing, and filtering are all very fast and have built-in functions in arrays.

Using Objects

Object are great for searching, I mean, they are really just string keyed hashmaps, right? They are also great for holding disparate information about the state of an object, of course.

Getting it Running

In order to get this running, I'd build some constructors for those objects, though you really could do all this with object and array literals.

function CheckboxFilter(init) {
  this.name = init && init.name || "";
  this.checked = init && init.checked || false;
  this.count = init && init.count || 0;
  this.countElement = init && init.countElement || null;
  this.element = init && init.element || null;
}

function FilterGroup(init) {
  this.name = init && init.name || "";
  this.filters = init && init.filters || [];
  this.element = init && init.element || null;
}

Notice that I defined a default for each property that I intend to use. The only properties that still aren't properly useable are the element references (because of null).

With our constructors, we'll want to build our initial state, either from a state object that was passed down with our document or from our DOM. Then we'll need to update our object model when people interact with our user interface, as well as when our form posts return an updated state. Finally, we'll need to update the user interface when our application state changes.

Building the Model

I'm building my initial state object from the DOM. So a lot of this code will be dependent on the HTML structure of our document. Therefore, we'll want to make sure this is separate from our constructor and response parsing code, as that will be a lot more stable.

Our HTML structure looks something like this:

<section class="filters">
  <ul class="filter-group">
    <li class="filter">
      <label id="year_2016">
        <input type="checkbox" name="year" value="2016">
        2016
        <span class="count">25</span>
      </label>
    </li>
    <li class="filter">
      <label id="year_2015">
        <input type="checkbox" name="year" value="2015">
        2015
        <span class="count">35</span>
      </label>
    </li>
    <li class="filter">
      <label id="year_2014">
        <input type="checkbox" name="year" value="2014">
        2014
        <span class="count">27</span>
      </label>
    </li>
  </ul>
  <ul class="filter-group">
    <li class="filter">
      <label id="make_chevrolet">
        <input type="checkbox" name="make" value="chevrolet">
        Chevrolet
        <span class="count">33</span>
      </label>
    </li>
    <li class="filter">
      <label id="make_dodge">
        <input type="checkbox" name="make" value="dodge">
        Dodge
        <span class="count">30</span>
      </label>
    </li>
    <li class="filter">
      <label id="make_ford">
        <input type="checkbox" name="make" value="ford">
        Ford
        <span class="count">24</span>
      </label>
    </li>
  </ul>
</section>

So, our data structure setup might look like:

function buildFilters(root) {
  return Array.from(root.querySelectorAll("input")).reduce(stateBuilder, {});
}

function stateBuilder(state, node) {
  var groupName = node.getAttribute("name");
  var group = state[groupName];

  if (!group) {
    group = state[groupName] = new FilterGroup({
      name: groupName,
      filters: [],
      element: node.closest(".filter-group")
    });
  }

  var countElement = node.parentNode.querySelector(".count");
  var checkboxModel = new CheckboxFilter({
    name: node.getAttribute("value"),
    checked: node.checked,
    count: parseInt(countElement.textContent, 10),
    countElement: countElement,
    element: node
  });

  node.addEventListener("change", function() {
    checkboxModel.checked = node.checked;
    submitForm();
  });

  group.filters.push(checkboxModel);

  return state;
}

Transforming the Data Structure

There are times when the easiest way to make the data do what you want means transforming your data structure. It is generally, pretty simple and quick to transform your data structure to a form that allows you to do precisely what you intend.

Updating the User Interface

We need to update the user interface when we get a response from the server (each checkbox change event fires a post request on the form). We're going to assume the response is an updated model in JSON format.

So, the first thing we need to do when we get the new model is to check if any of our existing filters were changed or removed. We're going to be changing our arrays to objects (since things could be in a different order, then they were originally).

// This function will be used with reduce to turn the filter arrays
// into objects. This, combined with the first 3 lines of our
// checkChanges method, is all we need to convert all of the filter
// arrays in our response to objects.
function objify(filterObj, filter) {
  filterObj[filter.name] = filter;
  return filterObj;
}

state.checkChanges = function checkChanges(updated) {
  for (var group in updated) {
    updated[group].keyed = updated[group].filters.reduce(objify, {});
  });

  // Here, we are changing the state object into an array of keys, so
  // we can easily iterate over it.
  Object.keys(this).forEach(function(groupName) {
    var filters = this[groupName].filters;
    var updGroup = updated[groupName];

    this[groupName].filters = filters.filter(function(filter) {
      var updFilter = updGroup[filter.name];

      // If we can't find the filter in the group, delete the filter
      // element and return false, filtering this element from the
      // array.
      if (!updFilter) { 
        deleteElement(filter.element);
        if (this[groupName].keyed) {
          delete this[groupName].keyed[filter.name];
        }
        return false;
      }

      // Update the other filter props, as needed.
      if (updFilter.checked !== filter.checked) {
        filter.checked = updFilter.checked;
        filter.element.checked = updFilter.checked;
      }

      if (updFilter.count !== filter.count) {
        filter.count = updFilter.count;
        filter.countElement.textContent = updFilter.count;
      }

      return true;
    });
  });
};

I left out the element deletion function, as it doesn't really add much to this discussion.

Adding and Rearranging the Filters

Now that we've resolved any discrepancies with existing filter properties, we need to ensure we are including any filters that were added with the response, as well as make sure everything is still in the right order.

Now, we don't often change the list of filters, so we'll generate our object just in time, if we find differences in order or find that we're missing some filters.

state.checkOrder = function(updated) {
  Object.keys(this).forEach(function(groupName) {
    var filters = this[groupName].filters;
    var updGroup = updated[groupName];
    var group = this[groupName];

    updGroup.filters.forEach(function(filter, i) {
      if (i >= filters.length || filter.name !== filters[i].name) {
        // Something is out of place
        // Create the object if it doesn't already exist.
        if (!this[groupName].keyed) {
          this[groupName].keyed = filters.reduce(objify, {});
        }

        var name = filter.name;
        var keyed = this[groupName].keyed;
        if (!keyed[name]) {
          filter.element = createElement(filter);
          keyed[name] = filter;
        } else {
          filter = filters.splice(filters.indexOf(keyed[name]), 1);
        }

        var next = i < filters.length ? filters[i] : null;
        insertElement(filter, next);
      }
  });
};

You'll notice I left out the mundane element creation and insertion. As above, it doesn't add much.

Simpler and Faster

While, everybody may not think so, I find this approach to be very graceful, even surgical. My implemented solution was somewhat more complex than this (probably because you understand the problem better on iterations). Even so, it was orders of magnitude simpler than the previous code. I'm sure the previous implementation could have been much simpler, as well, and maybe that would have negated any speed improvements I gained, but I doubt it. Most of the performance hits were based on the paints, not on actual JavaScript performance.

While I'd like to share some performance improvement numbers, I don't really have them any longer. I may add them to the story later, if I get the inclination. However, the numbers don't even tell the biggest part of the story. The perceived performance increase was more than the numbers appeared to support... but, it felt so much faster and smoother. Almost native, even.

@phillipwills #DataStructures #JavaScript

Discuss on Hacker News

Published