fritzthecat-blog: The State Pattern in Multiple Selection

We all know Design Patterns.

AbstractFactory, FactoryMethod, Composition, Adapter, Singleton, Visitor, Iterator, Observer, Command, FlyWeight, Proxy, Memento, State, ....

We have read about them, looked at their UML diagrams, and tried to understand the examples. But, after all, people rarely use them, because they like to solve problems by their "home-grown" super-fast hacking techniques :-) We are different! Aren't we :-?

Design Patterns are not an easy topic. You need the book always on your side. They are subtle. You think you understand it, but you can't find any application for it. Or you apply it, but find that it has become different from what is in the book. Sometimes you find out the real motivation for a design pattern in a situation where you did not expect it. For example, did you know that Visitor can be used to avoid the instanceof code smell? Or that FactoryMethod is an important part of every really reusable object-oriented framework?

Here and now I would like to present a small example of the State Pattern, which can reduce implementation complexity drastically, and avoid unconsidered situations to hit you.
I will build this in Java.

Multiple Selection

Let's look at multiple selection in a UI container like list, table or tree. You might know that such containers sometimes accept clicks in combination with key-presses. When you click an item, and you Shift-click another item, all items between these two will be selected. When you then Ctrl-click an item in between, this item will be deselected, leaving all others selected.

How does this work? Somewhere the first clicked item seems to have been remembered, and when a Shift-click follows, the range between the clicks gets selected. With Ctrl-clicks you can selectively add or remove items. You might also notice that any Ctrl-click, like any first click, marks the item that is used for a subsequent Shift-click bulk selection. I would like to call that item selection anchor in the following.

States and Events

The State Pattern exists to implement finite automatons, which you can visualize by UML state diagrams.

Why would we want a state machine here? Because we have a stateful object (selected items, selection anchor), and events that can change the state of that object (click, Shift-click, Ctrl-click). And there might be unexpected complex situations, f.i. what happens when several items are selected, and a Ctrl-click arrives, followed by a Shift-click? We would like a concept that leaves no holes for unconsidered situations.

I design the multi-selection automaton by thinking about possible states and events. Events might trigger a transition from one state to another. In case of multiple selection I find as

states NoneSelected
OneOrMoreSelected

and events click
shiftClick
ctrlClick

To cover all possible combinations of states and events, I draw a table with states as column headers and events as row headers.

	NoneSelected	OneOrMoreSelected
click
shiftClick
ctrlClick

For simplicity I ignore the existence of Shift-Ctrl-click and assume that Shift dominates, thus any Shift-Ctrl-click will be interpreted as Shift-click.

Transitions

What is missing here are the actions to be executed when an event arrives, and the follower state after that action. I write this into the empty cells.

	NoneSelected	OneOrMoreSelected
click	single-select the clicked item, set clicked item as anchor	single-select the clicked item, set clicked item as anchor
shiftClick	single-select the clicked item, set clicked item as anchor	multi-select the range between clicked item and anchor item
ctrlClick	single-select the clicked item, set clicked item as anchor	add the clicked item to selection when it is deselected, else remove it from selection, set clicked item as anchor

And I assign follower states:

	NoneSelected	OneOrMoreSelected
click	OneOrMoreSelected	OneOrMoreSelected
shiftClick	OneOrMoreSelected	OneOrMoreSelected
ctrlClick	OneOrMoreSelected	when none selected after action, NoneSelected, else OneOrMoreSelected

This now reads like

When a click arrives in state NoneSelected, the clicked item will be the only one selected, and it will be the new anchor. Follower state is OneOrMoreSelected.

When a Shift-click arrives in state NoneSelected, ...

It is plain to see that a lot of state/event transitions (table cells) do the same: 1/1, 1/2, 1/3 and 2/1 do the same, and have the same follower state. I would like to reuse transition implementations, and this will be done using inheritance.

State Pattern in Java

I model the states as classes, and the events as methods in these classes. Because all states must accept all events, I design an abstract super-class for all states, containing all event methods. And I give it a Context that wraps the selection and the anchor. That context will perform the work that the state machine decides to do.

abstract class State
{
  public final Context context;
 
  protected State(Context context) {
    this.context = context;
  }
 
  public abstract State click();
  public abstract State shiftClick();
  public abstract State ctrlClick();
}

I derive all states from that abstraction. I implement actions in event methods, and return follower states. Anticipating that an application will be able to construct an adequate state instance, mediate the pending event to it, and draw the follower state from it.

public class NoneSelectedState extends State
{
  public NoneSelectedState(Context context) {
    super(context);
  }
 
  @Override
  public State click() {
    context.setSelected(context.newItem);
    return new OneOrMoreSelectedState(new Context(context.table, context.newItem));
  }
 
  @Override
  public State shiftClick() {
    return click();
  }
 
  @Override
  public State ctrlClick() {
    return click();
  }
}

This was the first column of above table, and ....

public class OneOrMoreSelectedState extends NoneSelectedState // inherit click() handling
{
  public OneOrMoreSelectedState(Context context) {
    super(context);
  }
 
  @Override
  public State shiftClick() {
    final Object [] itemsBetween = context.itemsBetween(context.anchorItem, context.newItem);
    context.setSelected(itemsBetween);
    final Context newContext = new Context(context.table, context.anchorItem); // anchor stays the same
    return new OneOrMoreSelectedState(newContext);
  }
 
  @Override
  public State ctrlClick() {
    if (context.isSelected(context.newItem))
      context.removeSelected(context.newItem);
    else
      context.addSelected(context.newItem);
  
    final Context newContext = new Context(context.table, context.newItem); // anchor changes
    return context.size() > 0
        ? new OneOrMoreSelectedState(newContext)
        : new NoneSelectedState(newContext);
  }
}

... this was the second column of above table.

The NoneSelectedState reuses its own click() implementation for shiftClick() and ctrlClick().
The OneOrMoreSelectedState extends NoneSelectedState to inherit the click() event.

That's all, the State Pattern is ready to be used!

Now what is essential with state machines is that you should not expect them to be already existing any time you need them. Best is to have a factory or facade that can construct any state instance from some environmental information. I do this here with a static data-less utility method.

Mind that here is the place where Shift-click overrules Ctrl-Shift-click!

/**
 * Facade class for multi-selection.
 * Any selection holder must provide unique item-ids
 */
public final class MultiSelectUtil
{
  /**
   * Select items according to given event information.
   * @param clickedItemId the id of the currently clicked item.
   * @param shiftKeyDown true when "Shift" key was down on click.
   * @param ctrlKeyDown true when "Control" key was down on click.
   * @param selectionHolder where the selected items exist and should be set.
   * @param anchorItemIdProvider the object providing the anchor item-id.
   */
  public static void transition(
        Object clickedItemId,
        boolean shiftKeyDown,
        boolean ctrlKeyDown,
        SelectionHolder selectionHolder,
        AnchorItemIdHolder anchorItemIdProvider)
  {
    final Context context = new Context(
        selectionHolder,
        anchorItemIdProvider.getAnchorItemId(),
        clickedItemId);
   
    final State transition = (context.size() > 0)
        ? new OneOrMoreSelectedState(context)
        : new NoneSelectedState(context);
  
    final State followerState;
    if (shiftKeyDown)
      followerState = transition.shiftClick();
    else if (ctrlKeyDown)
      followerState = transition.ctrlClick();
    else
      followerState = transition.click();

    anchorItemIdProvider.setAnchorItemId(followerState.context.anchorItem);
  }
 
  private MultiSelectUtil() {} // do not instantiate
}

That was the state machine, and an example facade for it.
Everything is modelled quite cleanly here, but where is the real selection work done?

States Work on Context

The Context implementation does the real work.
As with automaton states, you should not expect the context to always be there when you need it, so it should be easily constructable from some environment. Actually the Context implemented here is meant to be used temporarily only, for instance during a HTTP request.

I wrapped the real UI selection list behind Java-interfaces, to get the chance to write a unit test for my multiple selection. The class(es) behind these interfaces hold the actual state that survives the HTTP request (selection, anchor). It may be useful that the class implementing SelectionHolder also implements AnchorItemHolder.

/**
 * Responsibilities of the list-widget.
 */
public interface SelectionHolder
{
  /** @return all unique ids of items in this list, in top-down order of visual appearance. */
  Collection<?> getItemIds();
 
  /** @return the unique ids of selected items in this list (order does not matter). */
  Collection<?> getSelection();
 
  /** @param newSelection the unique ids to be set as selected items in this list. */
  void setSelection(Collection<?> newSelection);
}

/**
 * Implementers hold the state of the selection,
 * i.e. the latest clicked item when no Shift key was pressed.
 * This is needed to select a range of items when a Shift-click follows.
 */
public interface AnchorItemIdHolder
{
  /** @return the current anchor item id. */
  Object getAnchorItemId();
 
  /** @param anchorItemId the new anchor item id to set. */
  void setAnchorItemId(Object anchorItemId);
}

Mind that interfaces always must be well-documented. If you do not use JavaDoc, consider using it on interfaces :-)

And here is the real work, done on abstracted selection- and anchor-providers.
The package-visible constructor is for the states to construct a follower-state context.
The public constructor is for any facade (for example MultiSelectUtil).

Mind that the context exposes its member fields as package-visible, to be used by the states to construct follower state contexts. This does not violate encapsulation, because all fields are final.

The responsibilty of the follwing Context is to talk to the SelectionHolder (list Widget), and to provide implementations the states will need to call. For Ctrl-click add and remove is needed, for Shift-click itemsBetween and setSelection is needed. Finally it exposes the anchor item for some caller that needs how to store this.

public class Context
{
  final SelectionHolder table;
  final Object anchorItem;
  final Object newItem;
  
  public Context(SelectionHolder table, Object anchorItem, Object newItem) {
    this.table = table;
    this.anchorItem = anchorItem;
    this.newItem = newItem;
  }

  Context(SelectionHolder table, Object anchorItem) {
    this(table, anchorItem, null);
  }

  /** @return true when given item is currently selected. */
  public boolean isSelected(Object item) {
    return getMultipleSelection().contains(item);
  }

  /** @return the number of selected items. */
  public int size() {
    return getMultipleSelection().size();
  }
  
  /** Clears current selection and set given one. */
  public void setSelected(Object ... items) {
    setMultipleSelection(buildSelection(items));
  }
  
  /** Adds given items to current selection. */
  public void addSelected(Object ... items) {
    final Collection<?> selection = getMultipleSelection();
    final Set<Object> newSelection = buildSelection(items);
    newSelection.addAll(selection);
    setMultipleSelection(newSelection);
  }
  
  /** Removes given items from current selection. */
  public void removeSelected(Object ... items) {
    final Collection<?> selection = getMultipleSelection();
    final Set<Object> newSelection = buildSelection(selection.toArray());
    for (Object item : items)
      newSelection.remove(item);
    setMultipleSelection(newSelection);
  }
  
  /** @return all items between item1 and item2. */
  public Object [] itemsBetween(Object item1, Object item2) {
    final Set<Object> itemsBetween = buildSelection();
    Object startItem = null;
    
    for (Object itemId : table.getItemIds())  {
      if (startItem == null && itemsBetween.size() <= 0)
        if (itemId.equals(item1) || itemId.equals(item2))
          startItem = itemId;
      
      if (startItem != null)
        itemsBetween.add(itemId);
      
      if (startItem != null && (itemId.equals(startItem) == false || item1.equals(item2)))
        if (itemId.equals(item1) || itemId.equals(item2))
          startItem = null;
    }
    
    return itemsBetween.toArray();
  }
  
  
  private Set<Object> buildSelection(Object ... items) {
    final Set<Object> selection = new HashSet<Object>();
    for (Object item : items)
      selection.add(item);
    return selection;
  }
  
  private Collection<?> getMultipleSelection() {
    final Collection<?> selection = table.getSelection();
    return (selection == null) ? buildSelection() : selection;  // avoid null return
  }
  
  private void setMultipleSelection(Collection<?> newSelection) {
    table.setSelection(newSelection);
  }
}

Test to Prove Concept

The unit test for this might make clear how it is used. It provides a mock list Widget (TestSelectionHolder) that implements SelectionHolder and AnchorItemHolder together, exposing an integer item list from 1 to 7. It performs certain click sequences, and asserts what is expected to be selected after.

public class MultiSelectUtilTest extends TestCase
{
  private static class TestSelectionHolder implements
    AnchorItemIdHolder,
    SelectionHolder
  {
    private Collection<?> itemIds = Arrays.asList(new Integer [] {
        Integer.valueOf(1),
        Integer.valueOf(2),
        Integer.valueOf(3),
        Integer.valueOf(4),
        Integer.valueOf(5),
        Integer.valueOf(6),
        Integer.valueOf(7),
      });
    
    private Collection<Object> selection = new HashSet<Object>();
    
    private Object anchorItemId;
    
    @Override
    public Collection<?> getItemIds() {
      return itemIds;
    }
    @Override
    public Collection<?> getSelection() {
      return selection;
    }
    @Override
    public void setSelection(Collection<?> newSelection) {
      selection.clear();
      selection.addAll(newSelection);
    }
    @Override
    public Object getAnchorItemId() {
      return anchorItemId;
    }
    @Override
    public void setAnchorItemId(Object anchorItemId) {
      this.anchorItemId = anchorItemId;
    }
  }
  
  public void testAutomaton()  {
    final TestSelectionHolder table = new TestSelectionHolder();
    assertEquals(0, table.getSelection().size());
    
    // click on "3"
    MultiSelectUtil.transition(Integer.valueOf(3), false, false, table, table);
    assertEquals(1, table.getSelection().size());
    assertEquals(Integer.valueOf(3), table.getSelection().iterator().next());
    
    // Shift-click on "5" to select "3", "4", and "5"
    MultiSelectUtil.transition(Integer.valueOf(5), true, false, table, table);
    assertEquals(3, table.getSelection().size());
    assertTrue(table.getSelection().contains(Integer.valueOf(3)));
    assertTrue(table.getSelection().contains(Integer.valueOf(4)));
    assertTrue(table.getSelection().contains(Integer.valueOf(5)));
    
    // Ctrl-click on "4" to remove it from selection
    MultiSelectUtil.transition(Integer.valueOf(4), false, true, table, table);
    assertEquals(2, table.getSelection().size());
    assertTrue(table.getSelection().contains(Integer.valueOf(3)));
    assertTrue(table.getSelection().contains(Integer.valueOf(5)));
    
    // Shift-click on "2" to select "2", "3", and "4",
    // because anchor has been set to "4" by preceding Ctrl-click
    MultiSelectUtil.transition(Integer.valueOf(2), true, false, table, table);
    assertEquals(3, table.getSelection().size());
    assertTrue(table.getSelection().contains(Integer.valueOf(2)));
    assertTrue(table.getSelection().contains(Integer.valueOf(3)));
    assertTrue(table.getSelection().contains(Integer.valueOf(4)));
    
    // simple click on "1" should select only "1"
    MultiSelectUtil.transition(Integer.valueOf(1), false, false, table, table);
    assertEquals(1, table.getSelection().size());
    assertTrue(table.getSelection().contains(Integer.valueOf(1)));
    
    // Ctrl-click on "7" should select "1" and "7"
    MultiSelectUtil.transition(Integer.valueOf(7), false, true, table, table);
    assertEquals(2, table.getSelection().size());
    assertTrue(table.getSelection().contains(Integer.valueOf(1)));
    assertTrue(table.getSelection().contains(Integer.valueOf(7)));
  }
}

Thanks to the clearness of the State Pattern the unit test was green immediately. Copy & paste all code and try it yourself!

The State Pattern concentrates on decisions under certain circumstances. It decides what to do, but the work should be done by the Context, to keep the automaton clean and clear (state machines tend to grow in course of time).

The construction of states, and further usage of their follower states, mostly depends on where and how the automaton is used. Best is to have it abstracted from everything by interfaces.

fritzthecat-blog

Blog-Archiv

Mittwoch, 26. November 2014

The State Pattern in Multiple Selection