MultiselectJS Tutorial

The multi-selection task is to identify a subset of a collection of elements. To abstract over what these elements are (DOM elements, characters in text, polygons drawn on a canvas, and so forth), we assume that each element is uniquely identified by some index. Indices can be of any type that can be compared for equality with ===, such as numbers, object references, or strings.

The selection state of elements is modeled as a mapping from indices to booleans, where true indicates that an element is selected, false that it is not. We call such a mapping a selection mapping. User’s selection actions, such as clicking the mouse on an element, dragging a ``rubber band’’ around elements, or pressing an arrow key with the shift modifier key held down translate to one or more selection operations that modify the selection mapping.

Each selection operation is associated with a selection domain that determines the set of indices that the operation affects, and a selection function that determines whether the indices will be selected, deselected, or toggled. The user indicates the selection domain through specifying a selection path, a sequence of points in some suitable coordinate space. This selection space could be, for example, the mouse locations in a window or pairs of row and column indices in a grid of elements. The first point of a selection path arises from a click or a command-click¹ and the subsequent points from shift-clicks (or mouse moves, when rubber band selecting). The first point is called the anchor and the last the active end of the path. In the case of a one-element path, the active end coincides with the anchor. The selection domain specified by the current selection path is the active selection domain.

Figure 1 shows concrete instances of the above concepts. The selectable elements are rectangles of arbitrary size, they are placed in arbitrary locations, and they can overlap. We make the following observations:

• The selected elements are items 2, 4, 5, and 6, and hence the selection mapping maps the indices 2, 4, 5, and 6 to true, and all other indices to false.
• The element 4 has been selected with a prior selection command. To select the elements 2, 5, and 6, the user has clicked the location marked with a red circle, and then dragged the mouse (rubber band selection) through several other locations (small blue dots). The last, and current, mouse location is marked with a blue circle.
• The selection space is the space of mouse coordinates. The sequence of points indicated by the blue dots therefore constitute the selection path.
• In most selection contexts, the anchor and active end are the only points that matter in determining the selection domain. Here, the anchor and active end serve as the opposite corners of a rectangle—all elements that overlap with this rectangle (shown in blue) belong to the active selection domain.

How the selection path determines the selection domain varies from one context to another. This variation is captured by the selection geometry. Concretely, a selection geometry in MultiselectJS is an object that defines the functions:

• m2v(point) that converts mouse coordinates to selection space coordinates;
• selectionDomain(path, J) that maps a selection path to a selection domain (the J parameter is to enable optimizations to be explained later);
• extendPath(path, point) that defines how a new point is added to the selection path;
• filter(pred) that computes a selection domain as the set of indices that satisfy the predicate pred;
• step(direction, point) that defines how arrow keys should impact the current keyboard cursor location; and
• defaultCursor(direction) that defines default cursor locations for when keyboard cursor has not yet been established.

The library has default definitions for each of the selection geometry’s functions, and often it suffices to implement only a subset of them. For example, in the selection geometry of Figure 1, the default definitions for m2v (identity function) and extendPath (add point as the new anchor) can be used. If the example does not support keyboard selection, step and defaultCursor need not be defined. If it does not support selection by a predicate, filter need not be defined. The only function that must be defined is selectionDomain; it computes the indices of the elements that overlap with the rectangle indicated by the anchor and active end.

Figure 2 shows a snapshot from a selection context that has a different selection geometry. In this geometry the selection space coincides with the set of element indices: the m2v function maps all mouse positions that fall within an element’s extents to the index of that element. In this context, elements are considered to be ordered, so the selectionDomain function maps a selection path to the range of indices between (inclusive) the path’s anchor and active end. The anchor is marked with a red dashed frame and the active end with blue. Here, the user has clicked first somewhere on Item 5 and then shift-clicked somewhere on Item 2. As a result, all elements between these two items are marked selected.

Another aspect that varies from one selection context to another is if and how the anchor and the active end, and more generally the selection path, are visualized. MultiselectJS leaves these questions to the client, but makes the data needed for those visualizations readily available (see Section 3.7).

Click, command-click, and shift-click are the basic selection tools that most applications support. Different applications assign slightly different meanings to these operations. The key bindings may vary as well (e.g., Windows’ ctrl-click corresponds to OS X’s command-click). These three commands are the basic building blocks of MultiselectJS, in terms of which most other (keyboard and rubber band selection) commands are defined. In a nutshell, the three selection commands work as follows:

• Click deselects all selected elements. The clicked point becomes the anchor and the sole element of the selection path. The new active selection domain is computed from this selection path; the elements in this domain are selected. The selection function is set to select, so that subsequent shift-click operations will select, rather than deselect, elements.
• The clicked point becomes the anchor and the sole element of the selection path. The new active selection domain is computed from this selection path. If the anchor is on an already selected element, the selection function is set to deselect, otherwise to select. The elements of the active selection domain are either selected or deselected according to the selection function.
• Shift-click extends the current selection path with a new point. It computes a new selection domain that corresponds to this selection path. The new selection domain replaces the current active selection domain.

MultiselectJS does not insist on particular key bindings for any of the selection operations, but the naming of the functions in its public API reflects our recommendations.

To use MultiselectJS on a page is a matter of importing it as a script. There are no dependencies; we import jQuery because we use it in this tutorial.

<script type="text/javascript" src="../../dist/multiselect.js"></script>
<script type="text/javascript" src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.3/jquery.min.js"></script>

In this example, the selectable elements are HTML table cells. We give the cells the selectable class attribute so that they are easily accessible. The animal_list span is a placeholder for where the selected animal names will be shown when the show_animals button is clicked.

    <table id="selectable_area">
      <tr><td class="selectable">pig</td>
      <td class="selectable">cow</td>             
      <td class="selectable">goat</td>
      <td class="selectable">horse</td>
      <td class="selectable">sheep</td>
      <td class="selectable">chicken</td>
      <td class="selectable">duck</td>
      <td class="selectable">turkey</td>
      <td class="selectable">ostrich</td>
      <td class="selectable">mule</td>
      </tr>
    </table>

    <br>
    <button id="show_animals">Show selected animals</button> <span id="animal_list"></span>

Next, we access the above HTML elements from JavaScript code:

var selectableArea = document.getElementById("selectable_area");
var selectables = selectableArea.getElementsByClassName("selectable");

The selectableArea object is the target of the mouse events. The selectables objects is the collection of the selectable elements; it is an “array-like” object, indexed with integers.

The following CSS code defines the visual appearance of selectable elements in both their unselected and selected states. The .selected class is turned on when an element is selected and off when deselected.

  <style>
    .selectable { outline:1px solid; padding:10px; cursor:default; }
    .selected { background-color: khaki; }
  </style>

To display the current selection state, MultiselectJS invokes a callback function after every selection command (unless the library recognizes that a command had no effect), passing it the current selection mapping. We use the refresh(s) function below as the callback; it iterates over all selectable elements and toggles the selected class attribute according to each element’s selection status:

  function refresh(s) {
    for(var i=0; i<selectables.length; ++i) { 
      selectables[i].classList.toggle('selected', s(i));
    };
  }

The library can also be configured to track changes, in which case the argument to the callback would be a Map² of changed elements. This mechanism is explained in Section 3.2.

The OrderedGeometry class³ defines the selection geometry for our example. The _elements member is a reference to the collection of the selectable elements.

var OrderedGeometry = function (elements) {
  this._elements = elements;
}
OrderedGeometry.prototype = Object.create(multiselect.DefaultGeometry.prototype);

OrderedGeometry inherits from DefaultGeometry to get the default implementations of the selection geometry methods. The superclass’ constructor is not called since the base class has no state. OrderedGeometry defines two methods: m2v and selectionDomain.

The selection space coordinates are the indices of the selectable elements, integers between 0 and this._elements.length - 1. The m2v function finds the element on which the mouse coordinate mp falls on and returns the element’s index.

  OrderedGeometry.prototype.m2v = function(mp) {
    for (var i=0; i<this._elements.length; ++i) {
      if (pointInRectangle(mp, this._elements[i].getBoundingClientRect())) return i;
    }
  }

The helper function pointInRectangle checks whether a point is inside a rectangle.

  function pointInRectangle(mp, r) {
    return mp.x >= r.left && mp.x <= r.right && 
           mp.y >= r.top  && mp.y <= r.bottom;
  }

The selectionDomain function is simple—it constructs a new Map object with makeEmptyMap, extracts the anchor and active end from the selection path, and sets all indices between them to true. The selectionDomain function may be called with an empty path, which is handled by checking whether path.length === 0.

  OrderedGeometry.prototype.selectionDomain = function(path) {
    var J = multiselect.makeEmptyMap();
    if (path.length === 0) return J;
    var a = multiselect.anchor(path);
    var b = multiselect.activeEnd(path);
    for (var i=Math.min(a, b); i<=Math.max(a, b); ++i) J.set(i, true);
    return J;
  }

The SelectionState class maintains all the state of the selection, including the current selection mapping, selection path, and undo and redo stacks. It defines methods for the various selection commands (click, cmdClick, shiftClick, etc.). The SelectionState constructor’s parameters are a selection geometry, the refresh callback, a boolean that turns change tracking on or off, and the maximum number of undo states. The last two can be omitted if their defaults (false and 10, respectively) are suitable.

  var geometry = new OrderedGeometry(selectables);
  var selection = new multiselect.SelectionState(geometry, refresh, false, 10);

The event handler for the mouse down event recognizes clicks, command-clicks, and shift-clicks, and invokes the corresponding library functions. Detecting modifier keys is somewhat messy. MultiselectJS provides a function modifierKeys(evt) that translates the event data to constants that indicate shift, command/ctrl, and option/alt modifiers. These constants are NONE, SHIFT, CMD, SHIFT_CMD, OPT, and SHIFT_OPT. The client can certainly define its own functions to distinguish between different mouse events if the one provided is not adequate.

In this simple example, it suffices to define and register a handler for the mousedown event:

  function mousedownHandler(evt) {
    evt.preventDefault();
    evt.stopPropagation();

    var vp = selection.geometry().m2v({ x: evt.clientX, y: evt.clientY });

    switch (multiselect.modifierKeys(evt)) {
    case multiselect.NONE: selection.click(vp); break;
    case multiselect.CMD: selection.cmdClick(vp); break;
    case multiselect.SHIFT: selection.shiftClick(vp); break;
    }
  };

  selectableArea.addEventListener('mousedown', mousedownHandler, false);

We draw attention to the simplicity of invoking MultiselectJS’s services: the selection geometry’s m2v function transforms the mouse position into a selection space coordinate, which is then passed to either the click, cmdClick, or shiftClick method.

The first example is complete except for the handler for the ``Show selected animals’’ button that displays a list of the selected elements. The selection.selected() call returns the indices of the selected elements as a Set.

  function showAnimals() {
    var s = "";
    selection.selected().forEach(function(v) { 
      s = s + selectables[v].textContent + " "; 
    });
    document.getElementById("animal_list").textContent = s; 
  }
  document.getElementById("show_animals").addEventListener("click", showAnimals);

Another means to inspect the current selection state, not used here, is the isSelected(i) method that returns true if the element i is selected and false otherwise.

The selectable area is a div. The tabIndex attribute is defined so that the element can acquire the keyboard focus.

<div id="selectable_area2" tabIndex="0"></div>

In this example, the selectable elements are generated by JavaScript code:

  var selectableArea2 = document.getElementById("selectable_area2");
  for (var i = 0; i<400; ++i) {
    var e = document.createElement("span");
    e.setAttribute("class", "selectable2");
    e.textContent = i;
    selectableArea2.appendChild(e);
  }

  var selectables2 = selectableArea2.getElementsByClassName("selectable2");

We again use CSS and classes to visualize the selection state. The selectable2 class indicates a selectable element and the selected2 class an element that is currently selected. The style definitions are as follows:

  <style>
    #selectable_area2 { border:1px solid black; cursor:default; }
    .selectable2 { outline:1px solid; padding:1px 4px 1px 4px; 
                   margin:2px; display:inline-block; }
    .selected2 { background-color: khaki; }
  </style>

As discussed above, every method of the SelectionState class that may change the selection state invokes the refresh callback. This example uses tracking of changes so that the refresh callback function only needs to iterate over the changed elements, instead of all selectable elements. We use a refresh function that toggles a class in further examples as well, and thus write a factory function that can generate a refresh-callback for any set of DOM elements.

function mkRefresh (elements, cls) {
  return (function (changed) {
    changed.forEach(function (value, i) { 
      $(elements[i]).toggleClass(cls, value); 
    });
  });
}

The refresh function for this current example is:

var refresh2 = mkRefresh(selectables2, 'selected2');

With tracking of changes on, the argument to the refresh callback is a Map object. Its keys are the indices of the elements that were changed and its values are either true or false, each indicating whether an element is selected or not.

The selection geometry again stores a reference to the collection of the selectable elements. It also stores a reference to a DOM object surrounding the selectable elements. We use mouse coordinates that are relative to this parent object’s location on the page.

var RowwiseGeometry = function (parent, elements) {
  this._parent = parent;
  this._elements = elements;
}
RowwiseGeometry.prototype = Object.create(multiselect.DefaultGeometry.prototype);

Coordinates in the selection space can indicate either an element index or a point ``in-between’’. We choose to represent a coordinate as an object that has two members, index and point. The in-between coordinate values are recognized by index that has the value null. The m2v method thus maps a mouse location mp, which is relative to parent, to a coordinate object whose point member is mp and whose index member is either null or the index of one of the elements.

  RowwiseGeometry.prototype.m2v = function(mp) {
    for (var i=0; i<this._elements.length; ++i) {
      var r = getOffsetRectangle(this._parent, this._elements[i]);
      if (pointInRectangle(mp, r)) return { index: i, point: mp };        
    }
    return { index: null, point: mp };
  }

The utility function getOffsetRectangle(a, b) function computes the bounding box of b in coordinates relative to the top-left corner of the bounding box of a:

  function topLeftCorner(r) { return { x: r.left, y: r.top }; }
    
  function offsetRectangle(p, r) {
    return {
      left: r.left - p.x, top: r.top - p.y, 
      right: r.right - p.x, bottom: r.bottom - p.y 
    };
  }

  function getOffsetRectangle(parent, elem) {
    return offsetRectangle(topLeftCorner(parent.getBoundingClientRect()),
                           elem.getBoundingClientRect());
  }

As mentioned above, the user can select either a range or a rectangular area of elements. Which mechanism is used depends on from where a selection command starts: if the anchor is on an element, a range is selected; if the anchor is in-between elements, a rectangular area is selected. The selectionDomain function thus first inspects the anchor’s index to determine the kind of coordinate the anchor is, and then interprets the anchor and the active end either as the endpoints of a range or as the corners of a rectangle. Again, the case that path is empty must be handled.

  RowwiseGeometry.prototype.selectionDomain = function(path) {
    var J = multiselect.makeEmptyMap();
    if (path.length === 0) return J;

    var a = multiselect.anchor(path);
    var b = multiselect.activeEnd(path);

    if (a.index !== null) { // path defines a range
      for (var i=Math.min(a.index, b.index); i<=Math.max(a.index, b.index); ++i) 
        J.set(i, true);
    } else {                // path defines a rectangle
      var r1 = { left:   Math.min(a.point.x, b.point.x),
                 right:  Math.max(a.point.x, b.point.x),
                 top:    Math.min(a.point.y, b.point.y),
                 bottom: Math.max(a.point.y, b.point.y) };
      for (var i = 0; i < this._elements.length; ++i) {
        var r2 = getOffsetRectangle(this._parent, this._elements[i]);
        if (rectangleIntersect(r1, r2)) J.set(i, true);
      }
    }

    return J;
  }

The rectangeIntersect helper function is as follows:

  function rectangleIntersect(r1, r2) {
    return r1.left <= r2.right  && r1.right  >= r2.left && 
           r1.top  <= r2.bottom && r1.bottom >= r2.top;
  }

This selection geometry also overrides the extendPath(path, p) method. The click, cmdClick, and shiftClick methods call extendPath to add a selection space point to the current selection path. Prior to pushing the new point to the path array, this extendPath implementation performs two tasks. First, only the first and last point of the selection path (anchor and active end) are of importance in this geometry. Therefore, if the path already has two elements, the previous active end is discarded.⁴ Second, if the anchor is on an element, we insist that the active end is also on an element: trying to extend the path with an in-between point has no effect in this case.

  RowwiseGeometry.prototype.extendPath = function(path, p) {
    if (path.length > 0 &&
        multiselect.anchor(path).index !== null && p.index === null) return null;
    if (path.length == 2) path.pop();
    path.push(p); 
  }

By returning null when the selection path is not changed, the extendPath function informs the library that the selection domain does not have to be recalculated.

The SelectionState object is created as in the first example. This time, however, we set tracking to true since we defined the refresh2 callback to expect a map of the changed elements as its parameter.

  var geometry2 = new RowwiseGeometry(selectableArea2, selectables2);
  var selection2 = new multiselect.SelectionState(geometry2, refresh2, true);

Setting up mouse events for the current example is a bit more involved because supporting rubber band selection requires handlers also for the mousemove and mouseup events. Furthermore, in addition to the selection status of the elements, this example visualizes the anchor, active end, and the rubber band, which adds a few function calls to the handlers.

The interplay between the handlers of different mouse events can be designed in many ways—the code below should be considered as one possible arrangement. The handler for the mousedown event in the selectable area (parent) is registered at all times. After a command that it recognizes, this handler registers the handlers for the mousemove and mouseup events. These are recognized within the entire document, as the mouse can wander outside of the selectable area. The handler for the mouseup event de-registers itself and the mousemove handler.

function setupMouseEvents (parent, canvas, selection) {

  function mousedownHandler(evt) {

    var mousePos = selection.geometry().m2v(offsetMousePos(parent, evt));
    switch (multiselect.modifierKeys(evt)) {
    case multiselect.NONE: selection.click(mousePos); break;
    case multiselect.CMD: selection.cmdClick(mousePos); break;
    case multiselect.SHIFT: selection.shiftClick(mousePos); break;
    default: return;
    }    

    selection.geometry().drawIndicators(selection, canvas, true, true, false);
    document.addEventListener('mousemove', mousemoveHandler, false);
    document.addEventListener('mouseup', mouseupHandler, false);
    evt.preventDefault();
    evt.stopPropagation();
  };

  function mousemoveHandler (evt) {
    evt.preventDefault();
    evt.stopPropagation();
    var mousePos = selection.geometry().m2v(offsetMousePos(parent, evt));
    selection.shiftClick(mousePos);
    selection.geometry().drawIndicators(selection, canvas, true, true, true);
  };

  function mouseupHandler (evt) {
    document.removeEventListener('mousemove', mousemoveHandler, false);
    document.removeEventListener('mouseup', mouseupHandler, false);
    selection.geometry().drawIndicators(selection, canvas, true, true, false);
  };

  parent.addEventListener('mousedown', mousedownHandler, false);
}

There are three further noteworthy issues in the code above.

1. A mouse move during rubber band selection is semantically equivalent to a shift-click. The mousemoveHandler thus acquires a selection space coordinate and passes it to the shiftClick method.
2. The calls to drawIndicators function are what display the anchor, the active end, and the rubber band indicators. These markers are drawn on a HTML5 canvas element that overlaps the selectable area. The three boolean arguments specify which of the three indicators (in the order anchor, active end, rubber band) should be shown; true means to show, false to hide. In this example we make drawIndicators a method of the geometry object. This is because we reuse the setupMouseEvents function in a later example that uses a different selection geometry. A different geometry usually means a different visualization, so it is convenient that the geometry object brings along this visualization function.
3. Even though the mouse events are a bit more complex than in the first example, MultiselectJS’s selection services are obtained by the same simple calls to the three different click methods.

We remark that a common feature in multi-selection contexts is drag-and-drop of selected elements. The above event handlers do not recognize the start of a drag-and-drop event.

A few tasks remain. First, the mouse setup code uses the helper function offsetMousePos to translate an event’s mouse coordinates to coordinates relative to another DOM element (parent). Its implementation is as follows:

  function offsetMousePos(parent, evt) { 
    var p = topLeftCorner(parent.getClientRects()[0]);
    return { x: evt.clientX - p.x, y: evt.clientY - p.y }; 
  }

Second, the event handlers must be activated:

  var canvas2 = createCanvas(selectableArea2);
  setupMouseEvents(selectableArea2, canvas2, selection2);

Section 3.7 shows the implementations of the createCanvas and drawIndicators functions.

Various keyboard commands can accomplish the same selection tasks as clicks—the selection space point associated with a keyboard command is the value of the keyboard cursor. The keyboard cursor is often the same as the active end; a click, command-click, and shift-click set the cursor to and the active end to the clicked point. The cursor can, however, deviate from the active end. For example, the arrow keys, unmodified, move the keyboard cursor but do not change the selection path. Further, the keyboard cursor can be defined even if the selection path is empty, e.g., after an undo command.

Selection geometry’s step(dir, point) method determines how arrow keys move the keyboard cursor. The dir parameter is one of constants UP, DOWN, LEFT, RIGHT. In this example, step only moves the cursor if it is on an element. When moving to a new element, the point member of the cursor object is set to the center point of the moved-to element.

  RowwiseGeometry.prototype.step = function (dir, p) {
    if (p.index === null) return p; // p is an "in-between" point, no change
    var ind = null;
    switch (dir) {
    case multiselect.LEFT:  ind = Math.max(p.index - 1, 0); break;
    case multiselect.RIGHT: ind = Math.min(p.index + 1, this._elements.length-1); break;
    case multiselect.UP: 
      ind = findClosestP.call(this, this._parent, this._elements, p.index, isAbove); 
      break;
    case multiselect.DOWN: 
      ind = findClosestP.call(this, this._parent, this._elements, p.index, 
                                    function (a, b) { return isAbove(b, a); }); 
      break; 
    default: return p;
    }
    return { index: ind, point: centerPoint(getOffsetRectangle(this._parent, this._elements[ind])) };
  }

Moving left and right is simple: decrement or increment the cursor’s index. Moving up or down is more complex. There are several sensible choices for what the next element above and the next element below could mean, even the notions of above and below are ambiguous. Here we consider one element to be above another if the former’s center point is above the top edge of the latter. The next element above of some element i is the closest, in distance between center points, of all elements that are above i. The next element below is defined analogously. The findClosestP(parent, elements, i, pred) helper function performs these determinations, finding the closest element to i that satisfies pred:

  function centerPoint (r) { return { x: (r.left + r.right)/2, 
                                      y: (r.top + r.bottom)/2 }; }

  function distance (p1, p2) {
    var dx = p1.x - p2.x;
    var dy = p1.y - p2.y;
    return Math.sqrt(dx * dx + dy * dy);
  }

  function isAbove(r1, r2) { return centerPoint(r2).y < r1.top; }

  function findClosestP(parent, elements, j, pred) {
    var r = getOffsetRectangle(parent, elements[j]);
    var candidateIndex = null; 
    var candidateDistance = Number.MAX_VALUE;

    for (var i=0; i<elements.length; ++i) {
      var rc = getOffsetRectangle(parent, elements[i]);
      if (pred(r, rc) && distance(centerPoint(r), centerPoint(rc)) < candidateDistance) {
        candidateIndex = i; 
        candidateDistance = distance(centerPoint(r), centerPoint(rc));
      }
    }
    if (candidateIndex === null) return j; else return candidateIndex;
  }

With the step function defined, setting up the keyboard events is straightforward: the event handler for keydown recognizes the key combination of a command, invokes the desired SelectionState’s method, and calls the function that draws the indicators. To avoid conflicts, we bind the handler to parent, which is the selectable area. In this way the bindings are only in effect when parent has the focus. A new mousedown handler is added to give parent the focus when anything within it is clicked.

  function setupKeyboardEvents(parent, canvas, selection) {

    parent.addEventListener('keydown', keydownHandler, false);
    parent.addEventListener('mousedown', function() { parent.focus(); }, false);

    function keydownHandler(evt) {
      var handled = false; 
      var mk = multiselect.modifierKeys(evt);
      switch (evt.which) {          
      case 37: handled = callArrow(mk, multiselect.LEFT); break;
      case 38: handled = callArrow(mk, multiselect.UP); break;             
      case 39: handled = callArrow(mk, multiselect.RIGHT); break;
      case 40: handled = callArrow(mk, multiselect.DOWN); break;
      case 32: handled = callSpace(mk); break;
      case 90: handled = callUndoRedo(mk); break;
      default: return; // exit this handler for unrecognized keys
      }
      if (!handled) return; // they key+modifier combination was not recognized

      selection.geometry().drawIndicators(selection, canvas, true, true, false);
      evt.preventDefault(); 
      evt.stopPropagation();
    }  
  
    function callUndoRedo (mk) {
      switch (mk) {
      case multiselect.OPT: selection.undo(); break;
      case multiselect.SHIFT_OPT: selection.redo(); break;
      default: return false;
      }      
      return true;
    }

    function callArrow (mk, dir) {
      switch (mk) {
      case multiselect.NONE: selection.arrow(dir); break;
      case multiselect.CMD: selection.cmdArrow(dir); break;
      case multiselect.SHIFT: selection.shiftArrow(dir); break;
      default: return false;
      }
      return true;
    }
  
    function callSpace (mk) {
      switch (mk) {
      case multiselect.NONE: selection.space(); break;
      case multiselect.CMD: selection.cmdSpace(); break;
      case multiselect.SHIFT: selection.shiftSpace(); break;
      default: return false;      
      }
      return true;
    }
  }

The main switch statement recognizes the arrow keys, space, and the character z (for undo and redo), and delegates to different helper functions. The helper functions inspect the modifiers and dispatch to the appropriate SelectionState method, or return false if the key binding is not recognized.

A call to setupKeyboardEvents registers the keyboard event handler:

setupKeyboardEvents(selectableArea2, canvas2, selection2);

To complete the keyboard selection functionality, we override the defaultCursor method so that the keyboard cursor has sensible defaults when nothing has yet been selected: the arrow right and arrow down keys start from the first element, the arrow left and arrow up keys from the last.

  RowwiseGeometry.prototype.defaultCursor = function (dir) {
    var ind;
    switch (dir) {
    case multiselect.RIGHT: 
    case multiselect.DOWN: ind = 0; break;
    case multiselect.LEFT: 
    case multiselect.UP: ind = this._elements.length - 1; break;
    default: return undefined;
    }
    return { index: ind, point: centerPoint(getOffsetRectangle(this._parent, this._elements[ind])) };
  }

Sometimes it is useful to show where the anchor, active end, and keyboard cursor reside. Many expect to see a rectangular rubber band when selecting via dragging. In “lasso” selection, it is particularly important to have a visual indicator of the selected area. To display such indicators is outside of MultiselectJS. To help in the task, however, SelectionState has the methods selectionPath() and cursor() that return the current selection path and cursor, respectively. The former returns an array of points and the latter a single point. These points are selection space coordinates and thus something akin to an inverse of the m2v transformation is necessary prior to their use in visualization. The desired visualization, however, is likely not a single point, but instead perhaps a frame over the selected element. Since the details of the “inverse” transformation varies from one selection context to another, its definition is left to the client.

In this example the visual indicators are drawn on a canvas that is placed on top of the selectable area. So that the canvas tracks the selectable area at all times, the canvas’ size and position are recalculated whenever the window object is resized.

function createCanvas (parent) {

  var canvas = document.createElement("canvas");
  canvas.style.position = 'absolute';
  parent.insertBefore(canvas, parent.firstChild);

  $(window).resize(resizeCanvas); 
  resizeCanvas();

  return canvas;

  function resizeCanvas() {
    var rect = parent.getBoundingClientRect();
    canvas.width = rect.right - rect.left;
    canvas.height = rect.bottom - rect.top;    
  }
}

The drawIndicators function is defined as a method of the geometry2 object. The function first clears all indicators, then draws some or all of anchor, cursor, and rubber band based on the drawAnchor, drawCursor, and drawRubber flags. The tests for undefined points are to safeguard for the case where there is no anchor (the selection path is empty) or no cursor.

The anchor is drawn as a circle if it is an in-between point (a point whose index is null) and as a rectangle if it is on an element. The cursor is not drawn at all for in-between points.

  geometry2.drawIndicators = function (selection, canvas, drawAnchor, drawCursor, drawRubber) {
    var ctx = canvas.getContext('2d');
    ctx.clearRect(0, 0, canvas.width, canvas.height);
    if (drawAnchor) { 
      ctx.strokeStyle = 'DarkRed';
      var p = multiselect.anchor(selection.selectionPath());
      if (p !== undefined) {
        if (p.index === null) { // in-between point, draw a circle
          ctx.beginPath();
          ctx.arc(p.point.x, p.point.y, 4, 0, Math.PI*2, true); 
          ctx.stroke();
        } else { // point on an element, draw a frame
          var r = getOffsetRectangle(canvas, selection.geometry()._elements[p.index]);
          ctx.strokeRect(r.left, r.top, r.right-r.left, r.bottom-r.top);
        }
      }
    }
    if (drawCursor) { 
      ctx.strokeStyle = 'blue';
      var p = selection.cursor();
      if (p !== undefined && p.index !== null) { 
        var r = getOffsetRectangle(canvas, selection.geometry()._elements[p.index]);
        ctx.strokeRect(r.left, r.top, r.right-r.left, r.bottom-r.top);
      }
    }
    if (drawRubber) { 
      ctx.strokeStyle = 'green';
      var p1 = multiselect.anchor(selection.selectionPath());
      if (p1 !== undefined && p1.index === null) {
        var p2 = multiselect.activeEnd(selection.selectionPath());
        ctx.strokeRect(Math.min(p1.point.x, p2.point.x),
                       Math.min(p1.point.y, p2.point.y),
                       Math.abs(p1.point.x-p2.point.x),
                       Math.abs(p1.point.y-p2.point.y));
      }
    }
  }

The second example is complete.

The selectable elements are again generated by JavaScript. The code that populates the fish array is in fish.js.

  var selectableArea3 = $("#selectable_area3")[0];
  for (var i = 0; i<fish.length; ++i) {
    $(selectableArea3).append("<span class='selectable2'>" + fish[i] + "</span> ");
  }
  var selectables3 = $(".selectable2", selectableArea3);

The styles selectable2 and selected2 are reused from the previous example, so we only style the selectable area:

<style> 
  #selectable_area3 { border:1px solid black; cursor:default; } 
</style>

The snake geometry again stores the DOM object of the selectable area (parent) and the collection of the selectable elements (elements). The third member k is explained below.

var SnakeGeometry = function (parent, elements) {
  this._parent = parent;
  this._elements = elements;
  this._k = 0;
}
SnakeGeometry.prototype = Object.create(multiselect.DefaultGeometry.prototype);

The snake geometry can use the default definitions of m2v (identity) and extendPath (pushes a new point to the array that represents the selection path). The selectionDomain function is more complex. It iterates over all line segments defined by two adjacent points on the selection path, and for each line segment finds the elements that the line segment intersects with, and adds them to the selection domain. This is quite a bit of work, and thus the function implements an optimization. When it is finished computing a selection domain, it stores the last index of the selection path in this._k. When shiftClick (which is called repeatedly during rubber band selection) makes a call to selectionDomain, the call includes the previously calculated selection domain (J) as the second parameter. It then suffices to iterate the line segments on the path from the index k onward. That J is undefined acts as a signal that a new active set has been created and that any cached values (here _k) should be reset.

  SnakeGeometry.prototype.selectionDomain = function(path, J) {  
    if (J === undefined) { J = multiselect.makeEmptyMap(); this._k = 0; } 
    var prev = this._k;
    for (var i = this._k; i < path.length; ++i) {
      for (var j = 0; j < this._elements.length; ++j) {
        if (lineRectIntersect(path[i], path[prev],
                              getOffsetRectangle(this._parent, this._elements[j]))) J.set(j, true);
      }
      prev = i;
    }
    this._k = Math.max(0, path.length - 1);

    return J;
  }

A few helper functions are needed. The lineRectIntersect function determines if a line intersects with a rectangle, mkRectangle constructs a rectangle from two points:

function lineRectIntersect(p1, p2, r) {
  if (!rectangleIntersect(mkRectangle(p1, p2), r)) return false; // if bounding boxes do not overlap, cannot intersect
  if (pointEquals(p1, p2)) return pointInRectangle(p1, r);
  var p = {};
  if (lineIntersect(p1, p2, { x: r.left, y: r.top }, { x: r.left, y: r.bottom }, p) === 1) return true;
  if (lineIntersect(p1, p2, { x: r.left, y: r.top }, { x: r.right, y: r.top }, p) === 1) return true;
  if (lineIntersect(p1, p2, { x: r.right, y: r.bottom }, { x: r.right, y: r.top }, p) === 1) return true;
  if (lineIntersect(p1, p2, { x: r.right, y: r.bottom }, { x: r.left, y: r.bottom }, p) === 1) return true;
  return pointInRectangle(p1, r) || pointInRectangle(p2, r);
}

function mkRectangle(p1, p2) {
  return { 
    left: Math.min(p1.x, p2.x),
    top: Math.min(p1.y, p2.y),
    right: Math.max(p1.x, p2.x),
    bottom: Math.max(p1.y, p2.y)
  };        
}

function pointEquals(p1, p2) { return p1.x === p2.x && p1.y === p2.y; }

The lineIntersect function is more involved. The code is a bit long, so we show it at the very end of this document in Section 4.6.

This example allows selecting elements by specifying a predicate. For this, we must override the filter method. It takes a predicate p and returns a Map of all indices for which the predicate is true.

Constructing the selection state object is as before. We again create the refresh callback function with the mkRefresh factory function, and we set track changes to true.

var geometry3 = new SnakeGeometry(selectableArea3, selectables3);
var selection3 = new multiselect.SelectionState(geometry3, mkRefresh(selectables3, 'selected2'), true);

Drawing the various indicators is done as before. We again setup a canvas over the selectable area, and add the drawIndicators method to the selection geometry object. The anchor and cursor are drawn as small circles, the rubber band indicator as the line segments of the selection path.

  geometry3.drawIndicators = function (selection, canvas, drawAnchor, drawCursor, drawRubber) {
    var ctx = canvas.getContext('2d');
    ctx.clearRect(0, 0, canvas.width, canvas.height);
    if (drawAnchor) { 
      ctx.strokeStyle = 'DarkRed';
      var p = multiselect.anchor(selection.selectionPath());
      if (p !== undefined) {
        ctx.beginPath();
        ctx.arc(p.x, p.y, 4, 0, Math.PI*2, true); 
        ctx.stroke();
      }
    }
    if (drawCursor) { 
      ctx.strokeStyle = 'blue';
      var p = selection.cursor();
      if (p !== undefined) { 
        ctx.beginPath();
        ctx.arc(p.x, p.y, 4, 0, Math.PI*2, true); 
        ctx.stroke();
      }
    }
    if (drawRubber) { 
      ctx.strokeStyle = 'green';
      var path = selection.selectionPath();
      if (path.length > 0) {
        ctx.moveTo(path[0].x, path[0].y);
        for (var i = 1; i < path.length; ++i) ctx.lineTo(path[i].x, path[i].y);
        ctx.stroke();
      }
    }
  }

This example reuses the createCanvas, setupMouseEvents, and setupKeyboardEvents functions from before for setting up the mouse and keyboard events.

  var canvas3 = createCanvas(selectableArea3);
  setupMouseEvents(selectableArea3, canvas3, selection3);
  setupKeyboardEvents(selectableArea3, canvas3, selection3);

The Filter textbox also listens to keyboard events. When its contents change, a new predicate is built and the SelectionState object’s filter method is invoked. The predicate is true for some element if the contents of the textbox is a substring of that element’s string value. To be able to commit the result of filtering as an undoable state, we bind the Commit button’s click to the commit method.

  var filter3 = $("#filter3")[0];

  $(filter3).keyup(function () {    
    var str = $(filter3).val(); 
    selection3.filter(function(i){ return str !== "" && fish[i].indexOf(str)>-1; });
  });
  $("#commit_filter3").click(function(){ selection3.commit(); });

This function is adapted from Prasad Mukesh’s C-code Intersection of Line Segments, ACM Transaction of Graphics’ Graphics Gems II, p. 7–9, code: p. 473–476, xlines.c.

  /* PORTED FROM:

   * lines_intersect:  AUTHOR: Mukesh Prasad
   *
   *   This function computes whether two line segments,
   *   respectively joining the input points (x1,y1) -- (x2,y2)
   *   and the input points (x3,y3) -- (x4,y4) intersect.
   *   If the lines intersect, the output variables x, y are
   *   set to coordinates of the point of intersection.
   *
   *   All values are in integers.  The returned value is rounded
   *   to the nearest integer point.
   *
   *   If non-integral grid points are relevant, the function
   *   can easily be transformed by substituting floating point
   *   calculations instead of integer calculations.
   *
   *   Entry
   *        x1, y1,  x2, y2   Coordinates of endpoints of one segment.
   *        x3, y3,  x4, y4   Coordinates of endpoints of other segment.
   *
   *   Exit
   *        x, y              Coordinates of intersection point.
   *
   *   The value returned by the function is one of:
   *
   *        DONT_INTERSECT    0
   *        DO_INTERSECT      1
   *        COLLINEAR         2
   *
   * Error conditions:
   *
   *     Depending upon the possible ranges, and particularly on 16-bit
   *     computers, care should be taken to protect from overflow.
   *
   *     In the following code, 'long' values have been used for this
   *     purpose, instead of 'int'.
   *
   */

  function sameSigns(a, b) { return a >= 0 && b >= 0 || a < 0 && b < 0; }

  function lineIntersect( p1,   /* First line segment */
                          p2,
                          p3,   /* Second line segment */
                          p4,
                          p5    /* Output value:
                                 * point of intersection */
                        )
  {
    const DONT_INTERSECT = 0;
    const DO_INTERSECT = 1;
    const COLLINEAR = 2;

    var a1, a2, b1, b2, c1, c2; /* Coefficients of line eqns. */
    var r1, r2, r3, r4;         /* 'Sign' values */
    var denom, offset, num;     /* Intermediate values */

    /* Compute a1, b1, c1, where line joining points 1 and 2
     * is "a1 x  +  b1 y  +  c1  =  0".
     */

    a1 = p2.y - p1.y;
    b1 = p1.x - p2.x;
    c1 = p2.x * p1.y - p1.x * p2.y;

    /* Compute r3 and r4.
     */
    r3 = a1 * p3.x + b1 * p3.y + c1;
    r4 = a1 * p4.x + b1 * p4.y + c1;

    /* Check signs of r3 and r4.  If both point 3 and point 4 lie on
     * same side of line 1, the line segments do not intersect.
     */
    if ( r3 != 0 &&
         r4 != 0 &&
         sameSigns( r3, r4 ))
      return ( DONT_INTERSECT );

    /* Compute a2, b2, c2 */
    a2 = p4.y - p3.y;
    b2 = p3.x - p4.x;
    c2 = p4.x * p3.y - p3.x * p4.y;

    /* Compute r1 and r2 */
    r1 = a2 * p1.x + b2 * p1.y + c2;
    r2 = a2 * p2.x + b2 * p2.y + c2;

    /* Check signs of r1 and r2.  If both point 1 and point 2 lie
     * on same side of second line segment, the line segments do
     * not intersect.
     */
    if ( r1 !== 0 &&
         r2 !== 0 &&
         sameSigns( r1, r2 ))
      return ( DONT_INTERSECT );

    /* Line segments intersect: compute intersection point. 
     */

    denom = a1 * b2 - a2 * b1;
    if ( denom === 0 )
      return ( COLLINEAR );
    // offset = denom < 0 ? - denom / 2 : denom / 2;

    // /* The denom/2 is to get rounding instead of truncating.  It
    //  * is added or subtracted to the numerator, depending upon the
    //  * sign of the numerator.
    //  */

    // The calculations for p5 are commented out; 
    // we just need to know if lines intersect or not

    // num = b1 * c2 - b2 * c1;
    // p5.x = ( num < 0 ? num - offset : num + offset ) / denom;

    // num = a2 * c1 - a1 * c2;
    // p5.y = ( num < 0 ? num - offset : num + offset ) / denom;

    return DO_INTERSECT;
  }