Solved

Sorting TCollection (via it's private TList)

Posted on 2002-05-14
6
1,853 Views
Last Modified: 2012-05-04
We have a large collection stored in a TCollection descendant for which I am implementing a sort.

A solution is to :

- copy the TCollection to a TObjectList
- call the TObjectList's sort (the algorithm is a really quick Quicksort)
- cycle through the TObjectList and reset the TCollectionItem.Index property for each item

This works but it is still a little sluggish for large collections, the big overhead being setting the index which does a Move.

However TCollection actually uses a TList itself but _unfortunately it's private_. We tried copying the VCL code for TCollection, opened access to the List and called the sort directly and it works lightening fast!

We don't know a way to have a TCollection descendant access the private TList without creating a new class in the VCL source unit. Does a hack exist?

Has anyone come up with a solution for sorting a TCollection that does not involve adding to the VCL source or setting the Items Index?

I would appreciate any suggestions,

Thanks, Tom

Delphi 6 UP2
0
Comment
Question by:tomcorcoran
6 Comments
 
LVL 6

Expert Comment

by:swift99
ID: 7010084
To me it looks like you will end up doing exactly what you did - creating your clone of the Borland code base and  either exposing the FList or creating a sort method that in turn invokes FList.Sort.

Hacks are always a dangerous thing - I'm in the process of attempting to upgrade about 250,000 lines of code from a hacked D3 VCL base to a standard D6 code base.

We have another 500,000 or so lines that two other gentlemen are responsible for upgrading.  It's a real pain - you don't want to go there.
0
 
LVL 9

Accepted Solution

by:
ITugay earned 400 total points
ID: 7010420
Hi tomcorcoran,

it is possible, but it can be differ for different Delphi versions.

e.g D5 TCollection declaration:

  TCollection = class(TPersistent)
  private
    FItemClass: TCollectionItemClass;
    FItems: TList;
....

you can see that FItems located bellow FItemClass. So, hack code to access FItems:

function GetCollectionList(C: TCollection): TList;
var
  M: TMethod;
  L: TList absolute M;
  P: Pointer;
begin
  // offset of FItemClass
  P := @C.ItemClass;
  // add size of FItemClass
  inc(Integer(P), SizeOf(TCollectionItemClass));
  // now P point to FItems
  M := TMethod(P^);
  Result := L;
end;


now an example:

  L := TCollection.Create(TCollectionItem);
  L.Add;
  L.Add;
  L.Add;
  GetCollectionList(L).Clear;
  Caption := IntToStr(L.Count);

------
Igor.
   
PS: Can be a problem regarding TCollectionItem.Index. It stored inside an item and will not be changed after sorting.
0
 
LVL 45

Expert Comment

by:aikimark
ID: 7011314
idea 1:
1. Pull the list into an array of type TObject
2. do a Quicksort on the array (your code)
3. rebuild your list

==============================================
on what criteria (object property) are basing your sort comparisons?

==============================================
idea 2:
1. build an array of the criteria and (double-)linked pointer data.
2. sort the array
3. "move" the the list items directly to their correct (sorted) location in the list, if they aren't already in the correct location in the list.  You only need to update the pointers.
0
Live: Real-Time Solutions, Start Here

Receive instant 1:1 support from technology experts, using our real-time conversation and whiteboard interface. Your first 5 minutes are always free.

 

Author Comment

by:tomcorcoran
ID: 7012329
Thanks guys. Got a possibility today by adding a TObjectList member to the collection and adding (integer) mappers for both the collection and the list to the collectionitem object. Ugly but a possibility.

Igor, that is exactly what I was hoping for :-) _But_ your PS of the index not being set is worrying. I will look at it tomorrow.

The sorting of the collection is done via a ListView where they can click on a number of columns for ascending / descending order. How can you rebuild a TCollection with the same TCollectionItems? There would be too much design overhead in idea 2 if I understand it correctly we would prefer not to change from using a TCollection. The tough part every time is the TCollectonItem.Index.

As the access to the collection is through the ListView the fact the index from that won't be talking with the correct index in the Collection means trouble :-) I will investigate tomorrow.

Thanks for the mails. Tom.

0
 
LVL 45

Expert Comment

by:aikimark
ID: 7013429
Tom,

Does this other solution create an "index" to the list?
0
 

Author Comment

by:tomcorcoran
ID: 7014410
Can I give an A++ :-)

You beauty, what a sick hack!!!!!!

On a test list of 1 million items it sorted in 15 seconds! It our real world situtation it would not be this fast as we use RTTI to get the column clicked on...

Anyway, we were concerned about 16,000 items which with the old optimised insertion sort was taking up to a minute, now it's a second odd.

I can't thank you enough!

Experts-exchamge rules :-)

Cheers, Tom.
0

Featured Post

Gigs: Get Your Project Delivered by an Expert

Select from freelancers specializing in everything from database administration to programming, who have proven themselves as experts in their field. Hire the best, collaborate easily, pay securely and get projects done right.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Suggested Solutions

Title # Comments Views Activity
Delphi - replicating a form 8 72
Run video youtube webbrowse 10 61
Reconfigure Delphi Install? 2 51
Find and Replace Stream with 0s 8 62
This article explains how to create forms/units independent of other forms/units object names in a delphi project. Have you ever created a form for user input in a Delphi project and then had the need to have that same form in a other Delphi proj…
Introduction I have seen many questions in this Delphi topic area where queries in threads are needed or suggested. I know bumped into a similar need. This article will address some of the concepts when dealing with a multithreaded delphi database…
Along with being a a promotional video for my three-day Annielytics Dashboard Seminor, this Micro Tutorial is an intro to Google Analytics API data.
Finds all prime numbers in a range requested and places them in a public primes() array. I've demostrated a template size of 30 (2 * 3 * 5) but larger templates can be built such 210  (2 * 3 * 5 * 7) or 2310  (2 * 3 * 5 * 7 * 11). The larger templa…

785 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question