Storing and Maintaining a TreeView in a file for random access and partial filling

I'm starting the design of a "Favorites" section to a plugin of mine.  Like a web browser, the favorite items can be organized in folders hierarchically and so forth.  The TreeView architecture and most of the GUI handling is already available and pretty straight forward.  But since memory is at a premium, I don't intend on fully structuring the Favorites hierarchy in memory but only showing the current displayed folders and visible items.  This means that access to the file (if that is recommended) that contains the full structure must be random and fast!

For illustration, this is what a full memory structure might contain:

folder
..folder
....item
....item
..folder
....item
....item
....folder
......item
folder
...

But I only want the current visiblie folders/items in memory at any time:

folder
..folder
..folder
....item
....item
....folder
folder

This needs to be able to handle tens of thousands of items (minimally) and thus the reason for the partial TreeView filling and the need for quick access within the file that contains the full tree.  I've done this partial listing successfully for a real folder hierarchy tree, but now the hierarchy will be virtual.

Internet Explorer uses a 'virtual' folder hierarchy on the filesystem.  Firefox uses XML (I think).  I'd rather not do this the IE way - unless it is highly recommended!

Systems: Windows, MacOSX (VC++ 6, VS 2005, CodeWarrior 9, XCode 2.4.1)
Language: C++
GUI and other support: Cinema 4D C++ SDK (R8.2-R10)

I'd appreciate any links, pointers, algorithms in regards to such a process.

Thank you very much,
Robert
RTempletonAsked:
Who is Participating?
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

AlexNekCommented:
It is a little bit stragne wish for a favorites structure becaus it can't be hunderts Mb.
You can clreate three nodes on disk too. Instead pointers use data offset in file.
0

Experts Exchange Solution brought to you by

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trial
Kent OlsenData Warehouse Architect / DBACommented:
Hello RTempleton,

I agree with Alex that this is a bit odd, but you've got your reasons so let's run with it.  :)

If your list contains a few hundred (or even a few thousand) items, you should probably abandon any plan to "page" the items in the TreeView yourself.  The lower level routines can do this a lot faster than you can.  Plus, the delay to the user will be less.  An application that forces a noticable delay to the user whenever a mouse button is pressed won't win too many quality points.  If you're TreeView is managing 1,000 items of approximately 200 bytes, the total structure size is only about 200K.  That's less than 1/3 the memory that was available on the old 16-bit DOS systems (640K).

If the list is large (in the megabytes range) Windows will transparently do its own paging of the data.  That is still faster than the application can do.  With the added benefit that as the user bounces around the list the recently accessed nodes are still in memory.

If the list is huge (10s of megabytes) you might consider mapping the file to memory with CreateFileMapping() so that you can quickly, and randomly, access the items within the file.  The nodes in the file would take on a linked list effect to allow you to quickly move through the nodes and build the current structure.

typedef struct
{
  int   ID;             // unique identifier given to this node.  Probably the ordinal within the file.
  int  Next;          // ID of the next item at this level
  int  Child;          // ID of the first child item to this node.
//  Your definitions
};

Given this data and structure (with record ID values):

  1,  My Name
  2,    Address
  3,    Phones
  4,      HomePhone
  5,      WorkPhone
  6,      CellPhone
  7,  YourName
  8,    Address
  9,    Phones
10,      HomePhone
11,      WorkPhone
12,      CellPhone

The data structures could look like this for ID, Next, and Child:

  1,   7,   2,  My Name
  2,   3,   0,  Address
  3,   0,   4,  Phones
  4,   5,   0,  HomePhone
  5,   6,   0,  WorkPhone
  6,   0,   0,  CellPhone
  7,   0,   8,  YourName
  8,   9,   0,  Address
  9,   0, 10,  Phones
10, 11,   0,  HomePhone
11, 12,   0,  WorkPhone
12,   0,   0,  CellPhone


This is the same technique that the TreeView uses to maintain the tree structure.  The only real benefit that can be derived from building it "on demand" is that you can split the time required to prebulid the entire list into smaller chunks that occur when a new node is selected.



Good Luck,
Kent
0
itsmeandnobodyelseCommented:
You might use a database rather than file. The table would have an indexed column to have direct access to each folder of the tree. (e. g. base0/base1/..../folder). The folder *path* easily could be built in the GUI. The item entries could be stored in a BLOB column (or CLOB if text only) what made it one db call to fetch the items. Note, if there is not enough memory to hold the maximum of items possible, you could put all items to a separate table and have a reference to the folder table:

Table:         FOLDER
Column 0:   FOLDERID  INT PRIMARY_KEY  
Column 1:   FOLDERPATH VARCHAR2 INDEXED

Table:         ITEM
Column 0:   FOLDERID  INT REFERENCE_KEY  
Column 1:   ITEMNAME VARCHAR2

You would fetch all data to a folder by

SELECT B.ITEMNAME FROM FOLDER A, ITEM B WHERE A.FOLDERPATH = 'base0/base1/.../folder' and A.FOLDERID = B.FOLDERID

You could fetch the data in portions so you don't need the memory to hold all data.

The last isn't as fast as the BLOB or CLOB solution but fast enough if we assume that you can show only 30 items to a time. If you want to have a fast scroll you could add an index number in the ITEM table to be able to access ranges of items.

For the DBMS you could use Berkeley DB which most likely is fastest (though you need two calls cause it doesn't provide joint selects) or any other RDBMS which was supported at the target platforms. When using ODBC access you could switch the RDBMS depending on the platform.

Regards, Alex
0
AlexNekCommented:
Database using is good idea too but I would like to use only one table, such as

parent_id
name

because we always need to get one level Items. First you get all items for parent 0 /root/, then for that node that must be expanded.
0
It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today
C++

From novice to tech pro — start learning today.

Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.