Extending Java Template Driven Comparator

Recently I introduced a comparator that can sort after a given template list. In this article I want to show how you can extend a base comparator to cover a bigger set of sortable elements without repeating the base sort order.

For comfortably editing a template sort order and mixing new elements into it, I will introduce a custom list called MergeList. This class allows to add elements relatively to a given anchor element.

Example Application

The use case covered here is sorting menu items. The base item list contains just "Cut", "Copy" and "Paste", the extension merges "Open", "Clear", "Insert" and "Delete" into it in a way that demonstrates the capacities of the MergeList API.

Following application shows how you can programmatically extend a base sort order without repeating it, by referring to existing list elements when adding new ones. This makes the implementation stable and independent from changes in the base sort order. A runtime-exception would be thrown when an anchor item is no more in the base list, but if you keep all items in constants and remove the according constant when an item is no more used, the compiler will detect such a problem.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59

import java.util.*; public class Main { public static final String CUT = "Cut"; public static final String COPY = "Copy"; public static final String PASTE = "Paste"; public static final String INSERT = "Insert"; public static final String DELETE = "Delete"; public static final String CLEAR = "Clear"; public static final String OPEN = "Open"; public static class BaseComparator extends TemplateDrivenComparator<String> { private final List<String> sorted = List.of( CUT, COPY, PASTE); @Override protected List<String> template() { return sorted; } }; public static class ExtendingComparator extends BaseComparator { private final List<String> sorted = MergeList.of(super.template()) .before(CUT).add(INSERT) .after(CUT).add(DELETE) .after(PASTE).addAll(List.of(CLEAR, OPEN)); @Override protected List<String> template() { return sorted; } }; public static void main(String[] args) { final List<String> sequence = new ArrayList<>(); sequence.add(OPEN); sequence.add(COPY); sequence.add(PASTE); sequence.add(CUT); sequence.add(INSERT); sequence.add(DELETE); sequence.add(CLEAR); System.out.println(sequence); final Comparator<String> comparator = new ExtendingComparator(); Collections.sort(sequence, comparator); System.out.println(sequence); } }

Output of this application is:

[Open, Copy, Paste, Cut, Insert, Delete, Clear]
[Insert, Cut, Delete, Copy, Paste, Clear, Open]

On top of the example class, from line 5 to 12, there are constants describing menu items. They are used in both comparators and the application main() on line 43. To see source code of the here used TemplateDrivenComparator please refer to my recent article.

The base comparator starts on line 14, the extended comparator on line 28. If I would use BaseComparator, then "Insert", "Delete", "Clear" and "Open" would be appended to the end of the item list in a random order. But if I use ExtendingComparator, the order as built from line 31 to 34 would show up, as to be seen in the output above.

Item merging happens on line 31. First, the template() list of items gets fetched from super-class. The MergeList.of() call creates a new list that can be edited comfortably (source code see next chapter).
I tell the new list to add "Insert" before "Cut" on line 32.
On line 33 I tell it to add "Delete" after "Cut".
The expression on line 34 adds "Clear" and "Open" after "Paste".

Why don't I simply use addAll() for appending "Clear" and "Open" to end? Because I want "Clear" and "Open" always being after "Paste", not necessarily at end of list. The base list (containing "Paste") may change in future in a way that "Paste" is followed by other items.
→ We should always be as explicit as possible!

Line 44 to 57 perform the use case. A list of menu items is built in a chaotic order, and printed to stdout. On line 54 the comparator is constructed, on line 56 it is applied to the list that is printed on line 57.

Merge List

Here is the source code for the MergeList used in example above. It features an intuitive API that lets you add before or after a given anchor item, adding either a single item or a list of new items.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73

import java.util.*; /** * A List that can be edited comfortably. */ public class MergeList<T> extends ArrayList<T> { /** Builds an editable MergeList from given List. */ public static <E> MergeList<E> of(List<E> elements) { final MergeList<E> result = new MergeList<>(); result.addAll(elements); return result; } /** * @param anchor required, the element at the insertion position. * @return inserter that will insert before given anchor. */ public Inserter before(T anchor) { return new Inserter(anchor, true); } /** * @param anchor required, the element at the insertion position. * @return inserter that will insert after given anchor. */ public Inserter after(T anchor) { return new Inserter(anchor, false); } public class Inserter { private final T anchor; private final boolean before; private Inserter(T anchor, boolean before) { this.anchor = Objects.requireNonNull(anchor); this.before = before; } public MergeList<T> add(T element) { return addAt(element, anchor, before); } public MergeList<T> addAll(List<T> elements) { return addAllAt(elements, anchor, before); } } private MergeList<T> addAt(T element, T anchor, boolean before) { final int index = assertAnchorIndex(anchor); super.add(before ? index : index + 1, element); return this; } private MergeList<T> addAllAt(List<T> elements, T anchor, boolean before) { final int index = assertAnchorIndex(anchor); super.addAll(before ? index : index + 1, elements); return this; } private int assertAnchorIndex(T anchor) { if (anchor == null) throw new IllegalArgumentException("Anchor can not be null!"); final int index = indexOf(anchor); if (index < 0) throw new IndexOutOfBoundsException("Index not found: "+anchor); return index; } }

This list extends the Java ArrayList and adds facilities to add items at specific positions.

A static factory for such lists is implemented on line 9.

Line 19 exposes a method that lets refer to an anchor item for subsequently adding items before it. Line 27 is the same but for subsequently adding after an anchor item. Calling these methods you get back an Inserter, that means the list is not altered yet.

The Inserter on line 32 does the list modification. It exposes just addAt() and addAllAt() methods, that means I must insert something when I receive an Inserter. Afterwards I get back the MergeList and can continue referring to other anchor items.

As the Inserter is a non-static inner class, it can call private methods of the MergeList instance. The real work is done in addAt() on line 51 and addAllAt() on line 57. The assertAnchorIndex() method on line 65 makes sure that a given anchor exists. It throws an exception when not, else it returns its index.

Resume

I hope I could give hints how to reuse sort orders of template lists. This is a frequent problem to be found in many applications.

You don't want to implement a sort algorithm, you want to implement a comparator and use Collections.sort(list, comparator), because that is much easier than re-inventing the wheel. The Java runtime library will provide the fastest available sort algorithm behind Collections.sort().