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.

Jelene

@Jelene Could you tell us more about the data you are wishing to store. How big is it? How does it change during your process lifetime? Do you need random access? What are the performance constraints? At the moment I feel your question is too general to offer meaningful advice. – Paul

@Jelene Random access means you need an array. – Paul

@David a TList<your type> would be more suitable IMHO, but arrays are fine as well. – Hufuf

@dorin TList is an array – Paul

@David yes, it's an array of pointers, BUT it's easier to play with :-) that's my point. – Hufuf

@Dorin, TList<your type> is an array of <your type>. It's an array of pointers only if <your type> is an pointer :) – Locris

@Jelene I get your point. I think I have got it all along. What did you mean when you said that you wanted random access? Could you elaborate on that. Technically random access means O(1) access which usually implies an array. Do you really mean that? – Paul

@David By saying random access I meant ability to do fast lookups based on selected index (key column). Sorry for misunderstanding. – Jelene

@Linas, what's an "index" in a tree? You might want to elaborate a bit on exactly what you're trying to do. If the "key column" is something uniquely linked to the data, look into a HashTable (the TDictionary from Generics.Collection), it's supposed to provide O(1) access, so it's a good match for your "random access" requirement. – Locris

@Cosmin I know what TDictionary is capable of and You are right, it is probably the best solution for making an index. – Jelene

@Linas, TDictionary is a nice modern probabilistic data structure, but it has nothing to do with "hierarchy" and if the indexes are sequential it's slow compared to an array. I'd like to contribute an answer but I still don't understand exactly what you want to do: Where does your data come from? What kind of operations do you need, and the biggest one, do you really need O(1) random access? My imagination is probably failing me, but I can't think of an algorithm where you need a tree structure AND you need random access to any node. – Locris

@Cosmin Random access is not an issue. Don't get me wrong, I do not desperately need O(1) random access. Besides, it's not very difficult to implement that if I ever need it. – Jelene

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.

Jelene

good that you have worked it out but I would comment that a significant reason for you not getting an answer that satisfied you was that your question was somewhat vague. – Paul

@David Maybe you are right but the solution was not easy to implement. Maybe because of that complexity it was not easy for me to describe my problem. – Jelene

probably just trying to explain it here helped you understand the problem better! It often works that way. – Paul

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!!

Hufuf

this doesn't address the issue of hierarchy – Paul

@David Heffernan depending on his "actual" needs he can make compromises, if he needs to create maybe a million nodes, using objects will eat a lot of memory(now it all goes down to target system of course), however records will eat less, ANYHU you're more than welcome to come with a good answer :-P – Hufuf

@Dorin I said nothing about objects. For what it's worth I think that records are fine. That said, objects don't use any more memory - TObject has no member fields. My point is that the question is about the hierarchy, not how to store the information in a node. – Paul

I've mentioned in my question that records are quite good solution but using records doesn't address some issues as David said. – Jelene

@David come on man, don't get so defensive :) but regarding "That said, objects don't use any more memory" -- why would anyone use objects without fields? same applies to records, but if you add one integer field in a object and one integer field in a record, you will see the difference when you look at .InstanceSize, now that being said, multiply by number of items(and subitems) and you get a lot of memory wasted + the create and free process which will take quite a few CPU cycles(again if there are many items). – Hufuf

@Jelene you still haven't provided too much details regarding your end goal, i.e. how many items do you expect to show, WHY do you need to sub class, remember that you could also use helper methods on records or maybe, just maybe, objects is what you need to get the job done clean and fast. – Hufuf

@Dorin Why would you use objects rather than records? Inheritance, polymorphism, ability to implement interfaces. InstanceSize for the TObject subclass with a single integer is 12 bytes. So, yes it costs to use objects, but that cost is often insignificant. – Paul

@Dorin He didn't say anything about subclassing. He wants advice on a data structure that lives in parallel to the tree view. But you are right that the question is lacking the details that would make it possible to answer well. – Paul

@David no he didn't say anything regarding sub class, I assumed that that's the end goal, having nodes with special methods, fields, etc. since a tag is "data-structures" I also assume he might have a database that he didn't mention... – Hufuf

@Dorin: Don't want to be nit-picking but "data-structures" has nothing at all to do with a "database" – Camail

@Smasher well correct me if I'm wrong, but the purpose of a database is to hold "data" -- which can be anything from byte values to integer to strings to blobs(raw data), for example in one particular project I save the user preferences into the database -- no matter from where a user logs in, he will ALWAYS have his preferences restored from previous session. I "assumed" that he has something to do with database, for example for all tables in my database I have a class called (T + table name) which is a child of a class that can perform various tasks on database. What am I missing? – Hufuf

It's just that the implication a tag is "data-structures" -> he might have a database does not make sense to me. (+1 for the answer by the way which is certainly helpful) – Camail

well come to think of it now, it doesn't really make too much sense..., maybe because I've been dealing only with database related apps. I have a trigger that says: database in the back of my head, "assuming" does make an ass at least of me right now :-P – Hufuf

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;

Bluh

Interesting solution but I'm not a big fan of TXMLDocument because of it's external dependencies. – Jelene

XML is still a great structure for a tree so if you do not like TXMLDocument you can use something else to access and modify the XML data structure. – Bluh

I don't even want to imagine the slowness of this solution. – Naga