Solved

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

Posted on 2007-04-01
6
344 Views
Last Modified: 2010-04-01
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
0
Comment
Question by:RTempleton
  • 2
6 Comments
 
LVL 16

Accepted Solution

by:
AlexNek earned 84 total points
ID: 18833139
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
 
LVL 45

Assisted Solution

by:Kdo
Kdo earned 83 total points
ID: 18835609
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
 
LVL 39

Assisted Solution

by:itsmeandnobodyelse
itsmeandnobodyelse earned 83 total points
ID: 18835963
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
 
LVL 16

Expert Comment

by:AlexNek
ID: 18837980
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

Featured Post

Enabling OSINT in Activity Based Intelligence

Activity based intelligence (ABI) requires access to all available sources of data. Recorded Future allows analysts to observe structured data on the open, deep, and dark web.

Join & Write a Comment

Suggested Solutions

Displaying an arrayList in a listView using the default adapter is rarely the best solution. To get full control of your display data, and to be able to refresh it after editing, requires the use of a custom adapter.
Although it can be difficult to imagine, someday your child will have a career of his or her own. He or she will likely start a family, buy a home and start having their own children. So, while being a kid is still extremely important, it’s also …
Viewers will learn how to properly install Eclipse with the necessary JDK, and will take a look at an introductory Java program. Download Eclipse installation zip file: Extract files from zip file: Download and install JDK 8: Open Eclipse and …
The viewer will learn additional member functions of the vector class. Specifically, the capacity and swap member functions will be introduced.

707 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

Need Help in Real-Time?

Connect with top rated Experts

13 Experts available now in Live!

Get 1:1 Help Now