How to make an Excel-Like Sort By A, Then By B in a TObjectList<> using multiple comparers

Question

I have just started to use generics, and I am currently having a problem doing sorting on multiple fields.

Case:
I have a PeopleList as a TObjectList<TPerson> and I want to be able to make an Excel-like sorting function, by selecting one sort-field at a time, but keeping the previous sorting as much as possible.

EDIT: It must be possible to change the field sort sequence at runtime. (Ie. in one scenario, the user wants the sort order A,B,C - in another scenario he wants B,A,C - in yet another A,C,D)

Lets say we have an unsorted list of people :

Lastname     Age
---------------------
Smith        26
Jones        26
Jones        24
Lincoln      34

Now if I sort by LastName :

Lastname ▲   Age
---------------------
Jones        26
Jones        24
Lincoln      34
Smith        26

Then if I sort by Age, I want this :

Lastname ▲   Age ▲
---------------------
Jones        24
Jones        26
Smith        26
Lincoln      34

In order to do this, I have made two Comparers - One TLastNameComparer and one TAgeComparer.

I now call

PeopleList.Sort(LastNameComparer)
PeopleList.Sort(AgeComparer)

Now my problem is that this does not produce the output I want, but

Lastname ?   Age ?
---------------------
Jones        24
Smith        26
Jones        26
Lincoln      34

where Smith,26 appears before Jones,26 instead. So it seems like it doesn't keep the previous sorting.

I know that I can make just one comparer that compares both LastName and Age - but the problem is, that I then have to make comparers for each combination of the fields present in TPerson.

Is it possible to do what I want using multiple TComparers or how can I accomplish what I want?

New Years Update

Just for reference to future visitors, this is (almost) the code I am using now.

First I made a base class TSortCriterion<T> and a TSortCriteriaComparer<T> in order to be able to use these in multiple classes in the future. I have changed the Criterion and the list to TObject and TObjectList respectively, as I found it easier if the objectlist automatically handles destruction of the Criterion.

  TSortCriterion<T> = Class(TObject)
    Ascending: Boolean;
    Comparer: IComparer<T>;
  end;

  TSortCriteriaComparer<T> = Class(TComparer<T>)
  Private
    SortCriteria : TObjectList<TSortCriterion<T>>;
  Public
    Constructor Create;
    Destructor Destroy; Override;
    Function Compare(Const Right,Left : T):Integer; Override;
    Procedure ClearCriteria; Virtual;
    Procedure AddCriterion(NewCriterion : TSortCriterion<T>); Virtual;
  End;

implementation

{ TSortCriteriaComparer<T> }

procedure TSortCriteriaComparer<T>.AddCriterion(NewCriterion: TSortCriterion<T>);
begin
  SortCriteria.Add(NewCriterion);
end;

procedure TSortCriteriaComparer<T>.ClearCriteria;
begin
  SortCriteria.Clear;
end;

function TSortCriteriaComparer<T>.Compare(Const Right, Left: T): Integer;
var
  Criterion: TSortCriterion<T>;
begin
  for Criterion in SortCriteria do begin
    Result := Criterion.Comparer.Compare(Right, Left);
    if not Criterion.Ascending then
      Result := -Result;
    if Result <> 0 then
      Exit;
  end;
end;

constructor TSortCriteriaComparer<T>.Create;
begin
  inherited;
  SortCriteria := TObjectList<TSortCriterion<T>>.Create(True);
end;

destructor TSortCriteriaComparer<T>.Destroy;
begin
  SortCriteria.Free;
  inherited;
end;

Finally, in order to use the sort criteria : (this is just for the sake of the example, as the logic of creating the sort order really depends on the application) :

Procedure TForm1.SortList;
Var
  PersonComparer : TSortCriteriaComparer<TPerson>; 
  Criterion : TSortCriterion<TPerson>;
Begin
  PersonComparer := TSortCriteriaComparer<TPerson>.Create;
  Try
    Criterion:=TSortCriterion<TPerson>.Create;
    Criterion.Ascending:=True;
    Criterion.Comparer:=TPersonAgeComparer.Create
    PersonComparer.AddCriterion(Criterion);
    Criterion:=TSortCriterion<TPerson>.Create;
    Criterion.Ascending:=True;
    Criterion.Comparer:=TPersonLastNameComparer.Create
    PersonComparer.AddCriterion(Criterion);
    PeopleList.Sort(PersonComparer);
    // Do something with the ordered list of people.
  Finally
    PersonComparer.Free;  
  End;  
End;

Sectary

See this somewhat similar question, should give you some ideas. – Midyear

Answer 1

Put your sort criteria in a list that includes the direction to sort and the function to use to compare items. A record like this could help:

type
  TSortCriterion<T> = record
    Ascending: Boolean;
    Comparer: IComparer<T>;
  end;

As the user configures the desired ordering, populate the list with instances of that record.

var
  SortCriteria: TList<TSortCriterion>;

The Comparer member will refer to the functions you've already written for comparing based on name and age. Now write a single comparison function that refers to that list. Something like this:

function Compare(const A, B: TPerson): Integer;
var
  Criterion: TSortCriterion<TPerson>;
begin
  for Criterion in SortCriteria do begin
    Result := Criterion.Comparer.Compare(A, B);
    if not Criterion.Ascending then
      Result := -Result;
    if Result <> 0 then
      Exit;
  end;
end;

Pappy

+1 This is a nice exposition and I like the touch of including the ascending/descending in a nicely encapsulated record. – Discretion

@Rob: This is exactly what i needed, and as David mentions, a nice touch with the ascending/descending feature. Thanks for your time helping. – Sectary

Answer 2

Your problem is that you are performing two separate sorts. You need to perform a single sort and use what is known as a lexical ordering. You need to use a comparer that compares the primary field and then, only if the primary key compares equal, goes on to compare the secondary key. Like this:

Result := CompareStr(Left.Name, Right.Name);
if Result=0 then
  Result := Left.Age-Right.Age;

This approach can be extended to cater for an arbitrary number of keys.

---

In your update to the question you add the requirement that the key precedence will be determined at runtime. You can do this with a comparison function like this:

function TMyClass.Comparison(const Left, Right: TPerson): Integer;
var
  i: Integer;
begin
  for i := low(FSortField) to high(FSortField) do begin
    Result := CompareField(Left, Right, FSortField[i]);
    if Result<>0 then begin
      exit;
    end;
  end;
end;

Here FSortField is an array containing identifiers for the fields, in descending order of precendence. So FSortField[0] identifies the primary key, FSortField[1] identifies the secondary key and so on. The CompareField function compares the field identified by its third parameter.

So the CompareField function might be like this:

function CompareField(const Left, Right: TPerson; Field: TField): Integer;
begin
  case Field of
  fldName:
    Result := CompareStr(Left.Name, Right.Name);
  fldAge:
    Result := Left.Age-Right.Age;
  //etc.
  end;
end;

Discretion

Thanks for your quick answer David. The problem is that i want the user to be able to change the sort order at runtime, and by using this approach, i have to create a comparer for each combination of fields e.g, if the user at some time wants to sort first by Age and then LastName, and in another scenario he wants to sort by LastName, then Age - then i need two comparers that does this. Imagine how many comparers i need if it also should be possible to sort by FirstName, PhoneNo, ShoeSize etc. with any combination of field sorting sequence. – Sectary

@Techno You only need one comparer and a bit of indirection. See my update. – Discretion

That was the hint i needed, and Robs nicely polished version just makes it perfect. Thanks for your time helping. – Sectary

Answer 3

If you have a stable sorting algorithm, then you can apply each comparer in reverse order, and the result will be a list sorted in the order you desire. Delphi's list classes use quick sort, which is not a stable sort. You'd need to apply your own sorting routine instead of the built-in ones.

Pappy

Does (any) Delphi come with stable sorting algorithms (whether Delphi's list classes use them or not)? – Faceoff

@marjan no stable sort in any Delphi I ever encountered – Discretion

@david Thanks. Pity. Sorting in reverse order of sort criteria is a nice simple solution... – Faceoff

@marjan stable sort is not hard to implement but using a single comparer is more efficient – Discretion