The Design of Software (CLOSED)

A public forum for discussing the design of software, from the user interface to the code architecture. Now closed.

The "Design of Software" discussion group has been merged with the main Joel on Software discussion group.

The archives will remain online indefinitely.

tree data & containers

I am trying to represent a tree-like data structure inside a container (STL). The tree-like data structure is just a file system on a PC.

The STL containers are flat, however, this data by its nature is not.. folders can have files and folders, so they are nodes, while files are just leaves.

I am having a lot of difficulty with this because I am also trying to populate a treeview control with all this data. In a way I am trying to recreate the Windows Explorer. Don't ask!  :)

I need each node to know what it is so if I right-click on it, I can get a pop-up window relevant to that node (directory or file).

STL containers are made for homogeneous data. I can't create a file-type and dir-type and store them both in the same container. If I have 2 containers -one for files, one for directories, then I have difficulty populating the treeview control without the treeview knowing what "type" of data each item is holding.

If I create a common base class "CNode" and extend it as "CFile" and "CDirectory" to store in a single container, then I get polymorphism headaches since each of these derived nodes have specific features that the other doesn't (used to build the pop-up window), and I get into the "type-id" hell.

Can you give me some pointers? What I am doing wrong here?
IDEs do this kinda thing all the time with their "project view"s. I never knew it was this difficult!  :)

I'd appreciate any and every hint!
Thank you

p.s. I apologize for the cross-post. I didn't mean to.
Saturday, February 18, 2006

I'm assuming that only the structure is of importance here. Well a file is a file, and a directory is a "special" file that contains files.

    struct File
        string name;
        shared_ptr< list<File> > pContents;

    bool IsDir(const File &p_File)
        return bool(p_File.pContents); // false if pContents is null.

What are the specific features you are talking about? Is there any reason they absolutely must be members of the class File, or could they be got with things like,

Saturday, February 18, 2006
I don't see a way around having a variant type here. Directory trees have this dual nature and the differences are dramatic, they can't be really smoothed over by the usual abstraction tricks.
son of parnas
Saturday, February 18, 2006
The only thing I found was the Visitor pattern. I know that the number of Visitors I have to right might blow up in number, but at least I can keep the Nodes clean and store them in a single container structure.

If anyone has any other ideas, I am all ears!
Saturday, February 18, 2006

Comes as an activex or vcl.

This is one of the reasons I like delphi/c++ builder, components like this make life much easier without reinventing the wheel everytime I need to do something....

Sunday, February 19, 2006
you are given an excellent library which implements different containers vectors, stacks, sets, hash_maps
and you do not how to implement a Tree ADT???
Take any good textbook on algorithms like Sedgewick "Algorithms in C++" and you will find many exaxmples how to implement trees (different kind of trees) using different containers.
As far as I understand you need a tree
such that your application would be able
1 traverse it efficiently
2 find an element in the directory by its name or regular expression which match it.
3 it is possible that there are many (thousands???) files in the one directory
I would implement tree using hashmap (file name -> pointer to the file element) as a container of child notes
Is you file system truly tree? Do you have links?
Do you need to search files efficiently or only traverse trees?
Andrei Lopatenko Send private email
Tuesday, February 21, 2006
I believe there are plenty implementations of tree ADT  using STL
just try to find them.
Andrei Lopatenko Send private email
Tuesday, February 21, 2006
This is an almost canonical case of inheritance: you have a collection of objects with a few similarities and many differences, in this case nodes in a file system. You create an abstract base class:

  class fs_node
    string name;

then you subclass the abstract base class for your concrete node types (files and directories):

  class fs_file: fs_node
    int length;

  class fs_dir: fs_node
    vector<fs_node> children;

I have, of course, left out all sorts of C++ niceties (constructors and destructors, for example) in the interest of brevety, but I hope you get the general idea.

While it may seem like files and directories are entirely dissimilar beasts, it is only because you thinking about the problem from with a tightly constrained model (things-that-live-in-a-filesystem). In fact, files and directories share all sorts of common properties and behaviors:

  1) they both have names and parent directories (which
      is just another way of saying that they both live
      in a filesystem).
  2) they both have 'lengths' (for a directory the
      number of child-nodes in the directory could
      be considered its length).
  3) they can both be created, renamed and deleted.
  4) they can both be 'opened' and 'read' (reading a
      directory returns the name of each successive
      child node).

So there is clearly a lot of room for both common behavior (implemented in the base class) and overloaded behavior (with an abstract method in the base class and concrete implementations in the sub-classes).
Jeff Dutky Send private email
Tuesday, February 21, 2006
IIRC when I reimplemented TreeView I did it with an abstract type, like:

interface ITreeItem
  virtual string getText() = 0;
  virtual ICON getIcon() = 0;
  virtual void onPopup() = 0;

A TreeNode then looks something like this:

class TreeNode
  ITreeItem m_item;
  list<TreeNode> m_children;

You then create application-specific classes derived from ITreeItem, e.g. FileTreeItem and DirectoryTreeItem.
Christopher Wells Send private email
Wednesday, February 22, 2006

This topic is archived. No further replies will be accepted.

Other recent topics Other recent topics
Powered by FogBugz