How to sort glazed TreeList

This is my first article, so don't be too critical, I just wanted to share some ideas on a problem, which took me couple of days to solve.

We are using glazed list together with nattable in our project. Usually, there is a TreeList (and TreeList based data provider) behind the table, which is created based on sorted list. It is done to be able to represent the tree structure inside the table. More over, nodes of this tree can be of different types. Sometimes data provider is changed to data provider, which uses usual sorted list - when filtering is applied.

Client wants to sort by to different types of nodes in tree on one column. This requirement forced us to change default sorting mechanism of nattable. It wasn't a rocket science, though it was a bit challenging. Basically, it was necessary to pass down to the ComparatorChooser and SortingState additional parameter (SortTarget), which indicates which type of nodes should be sorted:

public PlanningTableSortingColumn(final TableFormat<? super T> tableFormat, final int column, final SortTarget sortTarget) {
	this.column = column;
	this.sortTarget = sortTarget;

	if (tableFormat instanceof PlanningTableColumnFormat) {
		final PlanningTableColumnFormat<? super T> planningTableColumnFormat = (PlanningTableColumnFormat<? super T>) tableFormat;
		planningTableColumnFormat.setSortTarget(sortTarget);
		final Comparator<T> columnComparator = (Comparator<T>) planningTableColumnFormat.getColumnComparator(column);
		if (columnComparator != null) {
			comparators.add(new PlanningTableColumnComparatorDelegate<T>(tableFormat, column, columnComparator, sortTarget));
		}
	} else {
		comparators.add(new TableColumnComparator(tableFormat, column));
	}
}

The comparator for each column was also changed. Initially it was  usual TableColumnComparator, which takes as a parameter custom comparator, which is responsible for sorting of column values. But due to the fact, that it was necessary to sort by two different types of objects in tree we could not use TableColumComparator.

The main responsibility of PlanningTableColumnComparatorDelegate is to find out, if two object are suitable to be sorted and then delegate responsibilities down to TableColumnComparator, which will afterwards call our custom comparator with proper column values. PlanningTableColumnComparatorDelegate uses following simple algorithm to determine, if two objects can be sorted:

1. Objects are of the same type
2. Sort target is suitable to sort current objects
3. Objects have the same parent
4. If at least one of the conditions is not fulfilled, return 0.

Another custom thing, which had to be implemented is CellPainter. Default SortableHeaderTextPainter was extended to be able to draw "sorting triangle" on both sides of the sorted header cell.

When everything (comparators, models, layers etc.) was changed to support custom sorting it kind of started working, but the happiness was short. It was working when data provider was the one with SortedList. When we changed it to use TreeList, no sorting happened.

To make it working with TreeList, first of all, I had to switch of the comparator, which was initially  implemented for TreeLis#Format. The reason is that it overrides sorting, which was performed on SortedList. After returning null for TreeList.Format#getComparator(int)sorting seemed to start working again, but with one exception - for sorting by one type it's child elements were duplicated:

No sorting applied:

Type1-el1
   Type2-el1
      Type3-el1
      Type3-el2
   Type2-el2

Sorting by Type2 elements
Type1-el1
   Type2-el1
   Type2-el2
   Type2-el2
      Type3-el1
      Type3-el2

Reversed sorting:
Type1-el1
   Type2-el2
   Type2-el1
   Type2-el2
      Type3-el1
      Type3-el2

 Sorting by nodes of Typ3 was working fine.

After some time of debugging I found out, that elements are not actually duplicated. The reason of such behavior was that sorting mechanism was properly moving those nodes, which should be actually moved, but its children was not moved together with parent. They were left on their initial places and (probably) due to TreeList could not find their parents there, where they should be, it added those by itself.

I spent some time trying to move parents together with children in my comparators, but without any luck.

Apparently, initial sorting mechanism had to be adjusted to be able to move parents together with their children. The sorting is performed in ColumnComparatoChooser#rebuildComparator(), when selected comparator is set into SortedList. RebuilComparator method had to be overrided in the way so, that we don't call setComparator on SortedList, but sort it by our self.

I can say, that it is probably, not the best way to do it, cause some other problems occur - like you need to clear SortedList first and then put there your own "sorted list", which causes some magical things to happen inside SortList and TreeList. Also, you need to be able to restore state of the list, when no sorting is applied (when restoring state you need to consider, that list might be changed) and so on and so on (I will mention one more problem later). But despite all this facts I came up with following implementation for rebuildComparator method.

protected void rebuildComparator() {
	final Comparator<T> rebuiltComparator = sortingState.buildComparator();
	SortTarget sortTarget = null;
	final boolean isTypeFilterApplied = SortingUtils.isTypeFilterApplied(sortedList);

	// update comparator with current sorting conditions
        ....

	// select the new comparator
	sortedList.getReadWriteLock().writeLock().lock();
	try {
		sortedListComparator = rebuiltComparator;
		final BasicEventList<T> tmpSortedList;
		if (rebuiltComparator != null) {
			tmpSortedList = SortingUtils.sort(rebuiltComparator, sortedList, sortTarget, isTypeFilterApplied);
			sortedList.clear();
			sortedList.addAll(tmpSortedList);
		} else {
			// restore initial state, when no sorting is applied
			final List<PlanningTableNode> currentState = planningTableContentProvider.getPlanningTableBodyLayerStack()
				       .getCurrentBodyListDataProvider().getList();
			// copy is needed, since further clear clears also currentState list
			final EventList<T> currentStateCopy = (EventList<T>) GlazedLists.eventList(currentState);
			if (currentState.size() > 0) {
				tmpSortedList = SortingUtils.sort(new BENameComparator<T>(), currentStateCopy, SortTarget.AT, isTypeFilterApplied);
				sortedList.clear();
				sortedList.addAll(tmpSortedList);
			}
		}
	} finally {
		sortedList.getReadWriteLock().writeLock().unlock();
	}
}

The main idea is to have tmpSortedList already sorted in a proper way and then just update SortedList with already sorted elements.

Now everything seems to be working...or almost everything.

When type filter is applied, then there are elements of only one type in the list and also data provider is changed from one, that uses TreeList to another, which uses SortedList (there is no tree structure anymore in the table). Sorting is also working in this case, but when filter is cleared and initial tree is restored (data provider is changed back to tree data provider) then again, some elements are duplicated. I haven't yet investigated it deeply, and can not say right now, what is actual reason of such behavior. May be, this is a topic for another article...

 Any feedback is greatly appreciated.

AlexG.