What data structure is best suited for VirtualStringTree?

Question

I guess everyone who had ever used Delphi's VirtualStringTree will agree that it is a great control. It is a "virtual" control (your data must be held somewhere else) so I was thinking what data structure is the best suited for such a task? IMO that data structure must support hierarchy, it must be fast and easily expandable. The easiest implementation would be using a record and that's what most of the documentation which can be found is suggesting. But what if you need to do some fast lookups, calculate totals, etc? What data structure you are using together with VirtualStringTree?

EDIT1: I'm using Delphi 2010.

OK, I'll try to give some more details about my requirements. Data size can be very variable, from 1 to thousands of items. Each item can hold multiple string, integer values. I need random access, my data can change many times during the application lifetime. Good performance is very desirable. I also need data saving and reloading.

EDIT2: Got 1 answer so I'll try to comment my opinion. Thanks, Dorin for your answer but I don't think your structure is very convenient. 1) It doesn't deal with hierarchy. 2) Having separate TStringList's or TList's for each node is not very effective IMO. With this implementation I can only lookup the current node's data, but can't effectively search in the whole tree.

I think this data structure must be like a tree. It must have nodes with ability to add children. Then I just could get node's data in OnInitNode event, check if my node has some children, set ivsHasChildren flag if so, then in OnInitChildren event set correct children count. Later in OnGetText event I could just fetch needed data from my node structure and set it to CellText based on the Column index. My idea is to have a separate data structure and do all the needed operations with it without a need to use VirtualStringTree. Hope someone got my point :).

EDIT3: I've found quite interesting JclTrees unit which at first sight could be used to achieve what I'm looking for. It belongs to JCL library. Lack of decent documentation makes it hard to quickly investigate it's functionality. I'll probably look deeper into it when I have some more time.

Answer 1

OK, because given answers didn't solved my issues I've written my own tree data structure which imitates TVirtualStringTree and handles all the problems I mentioned in my question. Now I can optionally use only my data structure and all the changes in it will automatically update the VirtualStringTree. I think I will upload source code somewhere later and post the link here. Thanks for all the answers.

EDIT: I've uploaded source to the Google code: svTrees. There is a little demo that shows how it works.

Answer 2

You haven't specified your Delphi version, so:

I suggest using records(I'm not sure in which version of Delphi they added methods for records, I moved from D7 to D2010) so you can have something like:

type
  TMyRecordWithMethods = record
    function GetMeAResult: Integer;
    procedure DoSomething(const AInParam: Integer; var AOutParam: Integer);
  end;

if your version of Delphi does not support records with methods and you really need methods for nodes, then you will have to use objects to accomplish this, also have a look at generics.

Since you will only need to hold a few thousand items, I suggest using generics(no need to reinvent the wheel IMHO) i.e.

uses ..., Generics.Collections;

type
  TMyNode = class(TObject)// you can leave this out if you like
    MyIntList: TList<Integer>; // you can do lookups, you have to implement your own saving/loading methods
    MyStringList: TStringList or TList<string>; // you can do lookups in both cases, use TStringList for save/load of data
  end;

Now I assume that you would like to store all items from the virtual tree and load them later, you can do this by defining your own file structure, i.e.

type
  TMyFileHeader = record
    CountItems: Integer; // number of items in the tree
    ...
  end;

const
  szMyFileHeader = SizeOf(TMyFileHeader);

type
  TMyItemEntry = record
    CountInt: Integer; // number of integer values
    ...
  end;

const
  szMyItemEntry = SizeOf(TMyItemEntry);

now you will need to implement the load and save, I suggest saving and loading using TFileStream -- very straightforward,

pseudo code, sorry not time for partial code :-\

a) saving the content:

• save the number of items in a TMyFileHeader variable and write it to file

• for each item in the tree, save the integer list, save the string list

b) loading the content:

• read file header -- so that you know how many items you need to read from the file

• do a for Index := 0 to Count -1 read the item from the file

Note: that you can save the string list from each item directly to the current position in the file stream, however it would be wise to save it directly by using:

FileStream.WriteBuffer(PChar(AStringList.Text)^, Length(AStringList.Text) * SizeOf(Char));

I hope this helps, the actual implementation of the code is up to you, have fun!!

Answer 3

You can use a TXMLDocument.

If you want more control over what you put in there I would suggest that you create a xsd describing the structure you want and use the XML Data Binding Wizard to generate Delphi code that you can use.

This schema

<?xml version="1.0" encoding="UTF-8" standalone="yes"?>
<xs:schema xmlns:xs="http://www.w3.org/2001/XMLSchema" elementFormDefault="qualified">
    <xs:complexType name="itemType">
        <xs:sequence>
            <xs:element name="id" type="xs:int"/>
            <xs:element name="name" type="xs:string"/>
            <xs:element name="itemlist" type="itemlistType" minOccurs="0"/>
        </xs:sequence>
    </xs:complexType>
    <xs:complexType name="itemlistType">
        <xs:sequence>
            <xs:element name="item" type="itemType" minOccurs="0" maxOccurs="unbounded"/>
        </xs:sequence>
    </xs:complexType>
    <xs:element name="root">
        <xs:complexType>
            <xs:sequence>
                <xs:element name="itemlist" type="itemlistType"/>
            </xs:sequence>
        </xs:complexType>
    </xs:element>
</xs:schema>

will give you these interfaces to work with in delphi

  IXMLRoot = interface(IXMLNode)
    ['{16C6C960-58B7-400C-9E46-7ACC7BEF276F}']
    { Property Accessors }
    function Get_Itemlist: IXMLItemlistType;
    { Methods & Properties }
    property Itemlist: IXMLItemlistType read Get_Itemlist;
  end;

{ IXMLItemlistType }

  IXMLItemlistType = interface(IXMLNodeCollection)
    ['{59F80BAC-887E-48DF-8288-95276BF9DCE7}']
    { Property Accessors }
    function Get_Item(Index: Integer): IXMLItemType;
    { Methods & Properties }
    function Add: IXMLItemType;
    function Insert(const Index: Integer): IXMLItemType;
    property Item[Index: Integer]: IXMLItemType read Get_Item; default;
  end;

{ IXMLItemType }

  IXMLItemType = interface(IXMLNode)
    ['{1218DD35-C3EF-40E6-831A-1A4AA0782C36}']
    { Property Accessors }
    function Get_Id: Integer;
    function Get_Name: WideString;
    function Get_Itemlist: IXMLItemlistType;
    procedure Set_Id(Value: Integer);
    procedure Set_Name(Value: WideString);
    { Methods & Properties }
    property Id: Integer read Get_Id write Set_Id;
    property Name: WideString read Get_Name write Set_Name;
    property Itemlist: IXMLItemlistType read Get_Itemlist;
  end;