Delphi: Store multiple Sortings of TObjectList

Question

I have a bunch of TCoordinates which are stored in a TObjectList. To find a Coordinate faster the List must be sorted. The problem is that iam alternating searching for x and y. Is there a build in way to store the outcome of the sorting, so i dont need to sort the list again and again.

unit uStackoverflowQuestion;

interface

uses
  System.Generics.Collections, System.Generics.defaults;

type
  TCoordinate = class(Tobject)
    public
      x: Integer;
      y: Integer;
  end;

  TMultipleSortedList = class(TObjectlist<TCoordinate>)
    public
      // StoredSortingByX: List;
      // StoredSortingByY: List;
      procedure SortAndStoreByX;
      procedure SortAndStoreByY;
  end;

implementation

procedure TMultipleSortedList.SortAndStoreByX;
begin
  // TODO -cMM: TMultipleSortedList.SortAndStoreByX default body inserted
end;

procedure TMultipleSortedList.SortAndStoreByY;
begin
  // TODO -cMM: TMultipleSortedList.SortAndStoreByY default body inserted
end;

end.

To find a coordinate faster you may consider dictionary. Or R-Tree if you're going to work with geographical coordinates. — Victoria

David Heffernan David Heffernan · Accepted Answer · 2017-07-19T09:38:40

Create an index map to represent the two different orders. This is simply a dynamic array of integer.

type
  TListOrder = TArray<Integer>;

When you wish to read an item using that order you do so like this:

function GetItem(Index: Integer; const Order: TListOrder): TItem;
begin
  Result := List[Order[Index]];
end;

The key point here is that we don't modify the content of List ever. We regard that as unordered. Instead, we hold the order separate to the container. That allows us to have multiple such orders.

The next question is how to create an order. First of all populate the order with all the valid indices:

var
  i: Integer;
  Order: TListOrder;
....
SetLength(Order, List.Count);
for i := 0 to List.Count-1 do
  Order[i] := i;

Now you can sort the order like so:

TArray.Sort<Integer>(Order, Comparer);

Finally, what to use as the comparer. This is where the magic happens.

var
  Comparer: IComparer<Integer>;
....
Comparer := 
  function(const Left, Right: Integer): Integer
  var
    LeftItem, RightItem: TItem;
  begin
    LeftItem := GetItem(Left, Order);
    RightItem := GetItem(Right, Order);
    Result := ...; // your compare logic goes here
  end;

And that's it.

Delphi: Store multiple Sortings of TObjectList

2 Answers