Sorting two lists in step?

[giomach 1]

I'd be grateful for your thoughts on the easiest way to program this.

 

I have two TStringLists, which correspond item-by-item. I intend to use Find on the first list, and extract the corresponding item from the second list.  So far it works well.

 

Now I want to speed up the Find by having the first list sorted.  But this will change the order of items on the first list, and the result of the Find will not fetch the right item from the second list.

 

Is there a component which can hold both lists, and sort them both, using one of them as the sort key, so that they stay in step?

 

It seems a simple problem, but I haven't found a simple answer.  TStringGrid seems appearance-oriented, with a header row, and sorting is not straightforward.  Or TStringList's AddObject might be possible, but it is difficult to find a relevant example program. Or define my own descendant of TList? (I'd need an example of that). Or adapt a textbook quicksort algorithm to include handling the second list?

 

[David Heffernan 2345]

Create an array of integers 0 to N-1, sort that leaving the raw lists unchanged. Whenever you want to refer to an item in either list, instead of list use list[arr] 

[programmerdelphi2k 237]

would be that?

• "ITEMS" is a TStrings/TStringList - then ... 

implementation

{$R *.dfm}

procedure TForm1.FormCreate(Sender: TObject);
begin
  LMyItemsString := ['Item01', 'Item02', 'Item03', 'Item04', 'Item05', 'Item06', 'Item07', 'Item08', 'Item09', 'Item10'];
  //
  ListBox1.Items.AddStrings(LMyItemsString);
  ListBox2.Items.AddStrings(LMyItemsString);
end;

function MyAlreadyUsed(Arr: TArray<integer>; Value: integer): boolean;
begin
  result := false;
  //
  for var V in Arr do
    if (V = Value) then
      exit(true);
end;

procedure MyNewOrderList(ASrcArray: TArray<string>; var ATrgArray: TArray<string>);
var
  LPositionAlreadyUsed: TArray<integer>;
  LTotalItems         : integer;
  LRandomPosition     : integer;
begin
  randomize;
  //
  LTotalItems := length(ASrcArray);
  //
  for var i: integer := 0 to (LTotalItems - 1) do
    begin
      LRandomPosition := random(LTotalItems);
      //
      if (length(LPositionAlreadyUsed) > 1) then
        while MyAlreadyUsed(LPositionAlreadyUsed, LRandomPosition) do
          begin
            LRandomPosition := random(LTotalItems);
          end;
      //
      LPositionAlreadyUsed := LPositionAlreadyUsed + [LRandomPosition];
      // new order...
      ATrgArray := ATrgArray + [ASrcArray[LRandomPosition]];
    end;
end;

procedure TForm1.Btn_DeOrder_itClick(Sender: TObject);
var
  LMyItemsStringOutOfOrder: TArray<string>;
begin
  ListBox2.Sorted := false;
  //
  MyNewOrderList(LMyItemsString, LMyItemsStringOutOfOrder);
  //
  ListBox2.Items.Clear;
  ListBox2.Items.AddStrings(LMyItemsStringOutOfOrder);
  //
  ListBox1.SetFocus;
end;

procedure TForm1.Btn_Order_itClick(Sender: TObject);
begin
  ListBox2.Sorted := true;
  ListBox1.SetFocus;
end;

procedure TForm1.ListBox1Click(Sender: TObject);
var
  i: integer;
begin
  i := ListBox1.ItemIndex;
  if (i > -1) then
    begin
      if ListBox1.Items[i] = ListBox2.Items[i] then
        ListBox2.ItemIndex := i
      else
        ListBox2.ItemIndex := -1; // de-Select
    end;
end;

end.

 

 

 

 

Edited May 8, 2023 by programmerdelphi2k

[Attila Kovacs 629]

54 minutes ago, programmerdelphi2k said:

would be that?

•  

no, it's like 

 

'C' -> Pear

'A' -> Apple

'B' -> Banana

 

 

[programmerdelphi2k 237]

then... just needs:

Quote

  YourItemOnListBox2 := ListBox2.Items.IndexOf(ListBox1.Items[ i ]) ;

 

Edited May 8, 2023 by programmerdelphi2k

[Attila Kovacs 629]

3 minutes ago, programmerdelphi2k said:

then... just needs:

Quote

no, but it's already answered. creating an index array and sorting that.

 

[Remy Lebeau 1393]

6 hours ago, giomach said:

I have two TStringLists, which correspond item-by-item. I intend to use Find on the first list, and extract the corresponding item from the second list.  So far it works well.

Why are you using two TStringLists, and not a single TStringList that holds 'name=value' pairs?  Or, at least a TList that holds TPair<String, Integer>?

6 hours ago, giomach said:

Now I want to speed up the Find by having the first list sorted.  But this will change the order of items on the first list, and the result of the Find will not fetch the right item from the second list.

If you insist on using TStringList, then I would store the indexes of the 2nd list in the Objects[] property of the 1st list.  That way, no matter how the 1st list is sorted, the indexes will still match up.

[programmerdelphi2k 237]

@giomach

EDITED: now it's working...  (see code abode and add this 2 buttons)

• now, just translate for your propose

 

type
  TMyHackLB = class(TListBox);

procedure TForm1.ListBox1Click(Sender: TObject);
var
  i: integer;
  x: integer;
  n: nativeint;
begin
  i := ListBox1.ItemIndex;
  if (i > -1) then
    begin
      n := TMyHackLB(ListBox1).GetItemData(i);
      //
      if (n - 1) >= 0 then
        ListBox2.ItemIndex := (n - 1);  // -1 because ...  // TObject( x + 1 ) to avoid 0 = nil
      //
      { if (ListBox1.Items[i] = ListBox2.Items[i]) then
        ListBox2.ItemIndex := i
        else
        ListBox2.ItemIndex := -1; // de-Select }
    end;
end;

procedure TForm1.Btn_LB1_NewOrderClick(Sender: TObject);
var
  LMyItemsStringOutOfOrder: TArray<string>;
  LObj                    : TObject;
  LTotalItems             : integer;
  LIndexLB2               : integer;
begin
  // new order...
  MyNewOrderList(ListBox2.Items.ToStringArray, LMyItemsStringOutOfOrder);
  // LMyItemsStringOutOfOrder := ListBox2.Items.ToStringArray;
  //
  LTotalItems := length(LMyItemsStringOutOfOrder);
  ListBox1.Items.Clear;
  //
  for var z: integer := 0 to (LTotalItems - 1) do
    begin
      LIndexLB2 := ListBox2.Items.IndexOf(LMyItemsStringOutOfOrder[z]);
      LObj      := TObject(LIndexLB2 + 1);  // TObject( 0 ) = nil
      //
      ListBox1.Items.AddObject(LMyItemsStringOutOfOrder[z], LObj);
    end;
end;

procedure TForm1.BtnUpdateObjectsInListBox1Click(Sender: TObject);
var
  LMyItemsStringOutOfOrder: TArray<string>;
  //
  LIndexLB1: integer;
  LIndexLB2: integer;
  LText    : string;
  LObj     : TObject;
begin
  //
  // new order for test...
  MyNewOrderList(LMyItemsString, LMyItemsStringOutOfOrder);
  // LMyItemsStringOutOfOrder := ListBox2.Items.ToStringArray;
  //
  ListBox2.Items.Clear;
  ListBox2.Items.AddStrings(LMyItemsStringOutOfOrder);
  //
  for var z: integer := 0 to high(LMyItemsStringOutOfOrder) do
    begin
      // find new "ItemIndex" to update "Objects" in ListBox1
      LText     := LMyItemsStringOutOfOrder[z];
      LIndexLB1 := ListBox1.Items.IndexOf(LText);
      LIndexLB2 := ListBox2.Items.IndexOf(LText);
      //
      if (LIndexLB1 > -1) then
        begin
          LObj                              := TObject(LIndexLB2 + 1); // TObject( 0 ) = nil
          ListBox1.Items.Objects[LIndexLB1] := LObj;
        end;
    end;
end;

end.

 

Edited May 9, 2023 by programmerdelphi2k

[Fr0sT.Brutal 900]

options:

1. borrow sort procedure from Classes and rework it to sort both lists

2. store references to 2nd list in the 1st list somehow (indexes or pointers to the strings)

3. change container - keep everything in a single TList<TStrPairRec> or a dictionary which is exactly meant to locate item2 by the value of item1

[Uwe Raabe 2057]

I wonder why still no one suggested using a TDictionary<string,string> instead.

var dict: TDictionary<string,string>.Create;

dict.Add('C', 'Pear');
dict.Add('A', 'Apple');
dict.Add('B', 'Banana');

// lookup shortname (A, B or C)
var fullName := dict[shortname];

 

[Attila Kovacs 629]

was not defined tht list A contains unique keys 🙂

Edited May 10, 2023 by Attila Kovacs

[Sherlock 663]

23 minutes ago, Attila Kovacs said:

was not defined tht list A contains unique keys

It sort of was:

On 5/8/2023 at 6:50 PM, giomach said:

I have two TStringLists, which correspond item-by-item. I intend to use Find on the first list, and extract the corresponding item from the second list.  So far it works well.

So the TDictionary approach is sound.

[Attila Kovacs 629]

no it wasn't

[Uwe Raabe 2057]

Well, using Find on a TStringList with duplicates to get an index into a corresponding TStringList seems like a less optimal approach.

[Sherlock 663]

33 minutes ago, Attila Kovacs said:

no it wasn't

OK, but it should be clear, that for every "C" you will always get a "Pear". Which leads to data hygiene and no use for doubles.

[Attila Kovacs 629]

16 minutes ago, Sherlock said:

OK, but it should be clear, that for every "C" you will always get a "Pear". Which leads to data hygiene and no use for doubles.

In a stringlists, it is highly plausible that lines are not unique. Why would you argue about the opposite? 😉

 

Edited May 10, 2023 by Attila Kovacs

[Sherlock 663]

Agrred. But with two StringLists whose Items correspond Item by Item there is clearly no room for interpretation. But, lets let the TE clarify... @giomach has either been overwhelmed by the answers or is carefully formulating a response right now.

[giomach 1]

12 minutes ago, Sherlock said:

But, lets let the TE clarify... @giomach has either been overwhelmed by the answers or is carefully formulating a response right now.

Right on both counts, Sherlock!

 

While digesting all those very welcome suggestions, meantime I apologize for not making myself clearer and for confusing Find with IndexOf.

For clarification, the list I want to sort will have no duplicates.

 

At present, with no sorting, both lists are built sequentially by ADDing corresponding items, and later I have something like this:
            list1, list2: TStringList;
            s1, s2: string;
            ...
            s2 := list2 [ list1.IndexOf (s1) ]
which works very well, but is slow.

 

If I make list1 SORTED, the code above is much faster, but the answers are wrong, because the order of items in list1 has been changed by the sorting whereas list2 is the same as before.  To get the benefit of speeding up, I want to re-order list2 to match the way list1 was reordered by the sorting.

 

Taking up the idea of an index array (or list), the following might work, and slowness here wouldn't matter so much:
           Copy list1 to list1a
           list1.Sort          // will ensure the collation order is compatible with TStringList.IndexOf
           Construct an index by comparing list1 and list1a
           Copy list2 to list2a
           Clear list2 and rebuild it sequentially using list2a and the index.
           
But I need to examine the other proposals before doing anything else.

 

[Uwe Raabe 2057]

What you describe just screams for a TDictionary. Is there anything hindering you to use the built-in implementation?

[Stefan Glienke 2002]

You could (ab)use the objects part of the first stringlist entries as index of the entry in the second stringlist 😏

 

To be more serious - while the dictionary is a fair approach it leads to duplicated data which can make updating data more complex.

To find a good solution it might be worth it to explain a bit more about the data and the use case itself. You also mentioned a TStringGrid for UI which I personally find a terrible component.

Edited May 10, 2023 by Stefan Glienke

[Uwe Raabe 2057]

18 minutes ago, Stefan Glienke said:

You could (ab)use the objects part of the first stringlist entries as index of the entry in the second stringlist

I'm glad that nobody suggested a solution involving an SQL server, yet.

[Lajos Juhász 293]

3 minutes ago, Uwe Raabe said:

I'm glad that nobody suggested a solution involving an SQL server, yet.

For this task the only proper solution can be done using webserver and python that would enable the application to work fast.

[Attila Kovacs 629]

14 minutes ago, Uwe Raabe said:

I'm glad that nobody suggested a solution involving an SQL server, yet.

Maybe his next step would be to insert it into the db. We don't know 😛

[giomach 1]

I'm (slowly) working through the suggestions.

 

1. Use a name=value pair in TStringList

 

My version of Delphi (XE) doesn't seem to have this. (BTW, where can you find out when a Delphi feature - such as IndexOfName - was first introduced?)
But anyway there could be no time saving in using IndexOfName to look up a list which has been sorted on the whole string, and I don't see a way to sort on Name only.

 

2. Use TStringList.AddObject to hold (the index of?) the associated string

 

This technique seems to be frowned on but I tried it anyway.
I have also seen mention of a problem if the string exceeds the size of a pointer, so perhaps I must use the integer index rather than the actual string.
But tests seem to indicate that TStringList.SaveToFile saves only the strings, not the attached objects.  I'd like confirmation of that before moving to the next suggestion.  If it's true, it's not useful for me, as the setting up of the lists and their consultation are in different programs.
 

3. Use a TPair in TList

 

This is promising because (in contrast to no 1) both TList.Sort and TList.BinarySearch seem to support a custom comparison (in which I would use only the first element of the pair).

It is next on my list.

 

TDictionary, of which I have high hopes, will be next after that.

 

 

[Stefan Glienke 2002]

1 hour ago, giomach said:

I have also seen mention of a problem if the string exceeds the size of a pointer, so perhaps I must use the integer index rather than the actual string.

Wait what? Well first of a string is basically a pointer so you could store that inside of the pointer - nobody is talking about storing the string content into a pointer - you could only ever store 2 or 4 Unicode characters in there. So yes, of course, it's about storing the string index into the pointer.