Solved

tree-list structure

Posted on 2011-03-19
30
400 Views
Last Modified: 2012-06-27
Hi all,
 Now i can get all name of directory and its subdirectories. I want to build a tree to maintain the hierraachy .please advise what kind of tree I need to build. tks.
0
Comment
Question by:BeginToLearn
  • 15
  • 8
  • 3
  • +2
30 Comments
 
LVL 45

Expert Comment

by:Kdo
ID: 35173334
Hi Begin,

You want an N-node tree, not a binary tree.  That is, every node contains the names of all of the files in the directory and all of the (1st level) subdirectories.  Each subdirectory is a pointer to a node that describes the directory.

typtedef struct {
  char **FileNames;
  char **DirNames;
} node_t;

Keep all of the files in one list, and all of the directories in the other list.


Kent
0
 

Author Comment

by:BeginToLearn
ID: 35173753
Let me think about this tree
0
 
LVL 37

Expert Comment

by:TommySzalapski
ID: 35173785
I think you need it set up more like this (since you put this in the C++ zone, I assume that's what you are using):

struct DirectoryNode
{
  DirectoryNode* mChildren;
  char* mName;
  bool isFolder;
};

Then the root node contains the entire hierarchy and you of course set mChildren to 0 for all files and empty folders.
0
 
LVL 32

Expert Comment

by:phoffric
ID: 35173822
Assuming that you are concerned about only folder structure, I was toying with this idea.
#include <vector>
#include <iostream>
using namespace std;

struct dirNode;
typedef vector < dirNode* > Subfolders;

class dirNode 
{
public:
   dirNode(string dname)
      : directoryName(dname), pChildren(Subfolders()) {}
   bool addChild(string dirname); // return false if folder already exists; else true
private:
   string directoryName; 
   Subfolders pChildren;
};

int main() {
   Subfolders emptySubfolders(2); // assume 2 subfolders yet to come
   dirNode root_node(".");
   bool alreadyExists = root_node.addChild("project");
}

Open in new window

0
 

Author Comment

by:BeginToLearn
ID: 35173954
Tks.i gonna read all comments when I get home.
0
 
LVL 32

Accepted Solution

by:
phoffric earned 500 total points
ID: 35173975
I'm now thinking that an implied tree just using a multimap may prove easier to implement.

Assuming relative paths, the first element inserted is the current folder, "."
Under it, suppose there are 3 folders, "project0", "project1", "project2"
project0 has 4 folders, "Prj0 SubPrj0", "Prj0 SubPrj1", ..., "Prj0 SubPrj3"
and so on.

Useful functions for reviewing hierarchy are
find - we certainly need to find the root, "."
    http://www.cplusplus.com/reference/stl/multimap/find/

equal_range - to find all the folders from the parent
    http://www.cplusplus.com/reference/stl/multimap/equal_range/

The code already shows insert in action:
     http://www.cplusplus.com/reference/stl/multimap/insert/

General multimap reference:
    http://www.cplusplus.com/reference/stl/multimap/
#include <map>
#include <string>
using namespace std;

typedef multimap<string, string> dirNode; // parent/child dir names
typedef pair<string,string> pair_str;

int main() {
   dirNode tree;
   tree.insert(pair_str(".",""));
   tree.insert(pair_str(".", "project0"));
   tree.insert(pair_str(".", "project1"));
   tree.insert(pair_str(".", "project2"));
   tree.insert(pair_str("project0", "Prj0 SubPrj0"));
   tree.insert(pair_str("project0", "Prj0 SubPrj1"));
   tree.insert(pair_str("project0", "Prj0 SubPrj2"));
   tree.insert(pair_str("project0", "Prj0 SubPrj3"));
   tree.insert(pair_str("project1", "Prj1 SubPrj0"));
   tree.insert(pair_str("project1", "Prj1 SubPrj1"));
   tree.insert(pair_str("project1", "Prj1 SubPrj2"));
   tree.insert(pair_str("Prj0 SubPrj3", "Prj0 SubPrj3 ExtraCredit0"));
}

Open in new window

0
 

Author Comment

by:BeginToLearn
ID: 35174066
3 hrs later I will be home to try those mwthods.tks.
0
 
LVL 32

Expert Comment

by:phoffric
ID: 35174097
If you have confidence that you can extract the tree structure from the multimap, then to convey this structure to another system to rebuild that structure, then the message could simply be a a set of these paired strings. The order in which you send these pairs will not matter, as long as the order within the pair does not change. The first string in the pair is the key (in this case the parent folder name of the second string).

There are char values that are not permitted to be in a folder name. Pick one of those to be the delimiter (preferably a printable one).

BTW, I recommend that you use string rather than char * wherever possible
0
 

Author Comment

by:BeginToLearn
ID: 35174138
I like string bc compiler can rake care many operations easily
0
 

Author Comment

by:BeginToLearn
ID: 35174424
i am reading all comments now :)
0
 

Author Comment

by:BeginToLearn
ID: 35174724
I can see multimap is kind of easy to build. However, I want to think in advanced the next step and other possible issue I may face .I just want to find some approach that is easy to implement.
 Because I have all file name list already, I only concern about folder structure. I think I need two steps :
    + from the folder structure, create all folder
    + transfer all files from file list.

>>> If you have confidence that you can extract the tree structure from the multimap
 do u mean we must build tree?
0
 

Author Comment

by:BeginToLearn
ID: 35174746
just pop up idea.  if we build a tree, can we combine with vector?  
0
 
LVL 32

Expert Comment

by:phoffric
ID: 35175042
>> if we build a tree, can we combine with vector?
Yes, many ways to build the tree and to unravel it. You can go that way if desired.

Not only is the multimap easy to build on the client side and rebuild on the server side. Once you have a MM (either including a "/" for absolute paths, or a "." for relative paths, but never having both), then using recursion, you should find it very easy to rebuild the directory tree structure.
0
 
LVL 32

Expert Comment

by:phoffric
ID: 35175098
>> If you have confidence that you can extract the tree structure from the multimap
>> >> do u mean we must build tree?
   On the remote side, you receive a string with {parent, child} string pairs.

    You could build your tree just from this string of pairs, but I think just reinserting the pairs into a MM is trivial, and then you have the find and equal_range functions that you do not have to write. Your message, of course, should start off with the length of the string.

  If you wish to generalize so that the string is either absolute or relative paths, you could include the string "a" or "r" to distinguish between the two cases. This is explicit. Or, implicitly, you can just find "." or "/" to determine which mode you are in.

   BTW - using the network to host functions and vice-versa to handle binary integers is very easy to add.
0
 

Author Comment

by:BeginToLearn
ID: 35175648
I think I would go with multimap because I can reuse the "list_all_files" function.
0
Highfive + Dolby Voice = No More Audio Complaints!

Poor audio quality is one of the top reasons people don’t use video conferencing. Get the crispest, clearest audio powered by Dolby Voice in every meeting. Highfive and Dolby Voice deliver the best video conferencing and audio experience for every meeting and every room.

 

Author Comment

by:BeginToLearn
ID: 35176918
From my observation, I think i can reuse "list_all_files" for directory. It work based on hierarchy of folder via recursion. So after we have mmap , we can just follow the sequence and create all necessary folders before  sending files.

How do you think?
0
 
LVL 32

Expert Comment

by:phoffric
ID: 35176999
Yes, when you find a folder, then before you recurse into it, you have the parent, and that forms the pair of {parent, child}.

As long as you know the parent/child relation to form the pair, then it is easy to write two strings into an MM (and, of course, no matter which scheme you use, you obviously need to know the parent/child relationship).
0
 

Author Comment

by:BeginToLearn
ID: 35177435
I gonna implement it tonight
0
 

Author Comment

by:BeginToLearn
ID: 35178945
I just finish directory hierarchy map. I think it works. Please take a look. tks.
test.c
0
 
LVL 45

Expert Comment

by:Kdo
ID: 35180290
Hi Begin,

Good morning.  :)

That looks like it will work just fine.  I'd have written it a bit differently so that you only had to scan the directory catalogs once, but let's not argue with success.

Now that you have the directories and files listed, what's your next step?


Kent
0
 
LVL 32

Expert Comment

by:sarabande
ID: 35180969
a multimap with complete paths for parent directory contains a lot of redundant information.

an alternative could be a self-written filetree class which is drafted in the following:

class filetree_object
{
   filetree_folder * parent;
   std::string name;
public:
   filetree_object(filetree_folder * p, const std::string & n) : parent(p), name(n) { }

   std::string getname() { return name; }
   virtual bool isfolder() = 0; 
   
};  

class filetree_file : public filetree_object
{
public:
   filetree_file(filetree_folder * p, const std::string & n) : filetree_object(p, n) { }
   virtual bool isfolder() { return false; }

};

class filetree_folder : public filetree_object
{
   std::vector<filetree_object *> children;
public:
   filetree_folder(filetree_folder * p, const std::string & n) : filetree_object(p, n) {}
   virtual ~filetree_folder() 
   {
      std::vector<filetree_object *>::iterator i;
      for (i = children.begin(); i != children.end(); i++)
         delete *i;
   }
   virtual bool isfolder() { return true; }
   filetree_folder & addfolder(const std::string & fn)
   {
       children.push_back(new filetree_folder(this, fn));
       return *((filetree_folder*)children.back());
   }
   filetree_file & addfile(const std::string & fn)
   {
       children.push_back(new filetree_file(this, fn));
       return *((filetree_file*)children.back());
   }
};

class filetree
{
   filetree_folder root;
public:
   filetree(const std::string & rn) : root(NULL, rn) {}
   filetree_folder & getroot() { return root; }
};

Open in new window



the above has only rudimentary functionality yet. but it would not be very difficult to add functions like getpath() or iterator and necessary operators.

Sara
0
 
LVL 32

Expert Comment

by:phoffric
ID: 35181815
I ran your test program to produce both the <LIST> and the MultiMap. Looks complete.

Since list_all_dirs also does the work of list_all_files, it appears that you can eliminate the list_all_files function.

One concern - the <LIST> produced by list_all_dirs includes folder names. Isn't that going to cause a problem? Shouldn't your file list only include filenames and exclude folder names? If that becomes a problem for you, then when copying files to the remote system, then on the remote system, you could check whether the "file" is actually a folder, and if it is, just throw away that <LIST> entry.

Did you want to recreate the tree structure on a remote system using absolute or relative paths? In either case, your directory tree message could include the CWD path, and then the subsequent parent/child string pairs could exclude that CWD.

In general when copying a tree structure over to a remote system, there are practical issues to deal with. What if a folder already exists. And when you transfer files over, what if a filename already exists? For your assignment, possibly you can eliminate some of the practical considerations, and just assume that the tree at or below the CWD is non-existent.
0
 

Author Comment

by:BeginToLearn
ID: 35181989
basically, before sending files from server to client, i will send the MultiMap first to create all folders. then starting to send files from <List>.
 From starting stage, I assume those folders and files don't exist. If folders exist, just ignore. If files exist, i will check the different and send the only difference. maybe using diff...

 So can we leave this question a while. Let me open a new question regarding to " receiving" because right now the code is unstable. tks.    
0
 
LVL 32

Expert Comment

by:phoffric
ID: 35182024
Do you want to review the message being sent before trying to receive it?
0
 

Author Comment

by:BeginToLearn
ID: 35182035
yeah. i am openning new question about it now :)
0
 
LVL 32

Expert Comment

by:sarabande
ID: 35182203
i wouldn't send the multimap from server to client.

instead send the full relative (relative to root folder) path of each file. then on the receiver side you easily can parse the path and create empty subfolders if necessary.

you also should see that a vector with full path strings of each file would serve same as a multimap does for your purposes.

Sara

0
 

Author Comment

by:BeginToLearn
ID: 35182313
i just thought about this. because each system has different "current directory". So I will need to modify the string such as replace "current directory "of client by "." and substitute "." by "current directory" in client. But leave this for a while because the biggest issue is in receiving question. I will get back to this after fixing the main issue. tks a lot.
0
 
LVL 45

Expert Comment

by:Kdo
ID: 35182441
Hi Begin,

That depends on what you're trying to do.

If you want to copy a directory as is, into the same location on the target, you can take either approach.

If you want the flexibility to copy the folder from the source system anywhere on the target system, you'll need to send the entire path.

You might want to copy

  c:\windows

to

  c:\temp\windows

If you send the entire path you can do that (minus the files that are locked).  But you can not copy an entire folder over c:windows.



Kent
0
 
LVL 32

Expert Comment

by:sarabande
ID: 35183497
with root folder i didn't meant root of a linux system, but top folder of the files to copy.

so the paths always would be relative and not absolute.

Sara
0
 

Author Comment

by:BeginToLearn
ID: 35217377
The main reason favor for multiplemap is i forgot that list_all_files can keep hierarchy folder. So using vector like Sara mention is an alternative solution if i have time. This is the first time i ever used Multiplemap. At least I have a backup solution now:). let me close this question.
0

Featured Post

Highfive + Dolby Voice = No More Audio Complaints!

Poor audio quality is one of the top reasons people don’t use video conferencing. Get the crispest, clearest audio powered by Dolby Voice in every meeting. Highfive and Dolby Voice deliver the best video conferencing and audio experience for every meeting and every room.

Join & Write a Comment

Suggested Solutions

This article will show you some of the more useful Standard Template Library (STL) algorithms through the use of working examples.  You will learn about how these algorithms fit into the STL architecture, how they work with STL containers, and why t…
This article shows you how to optimize memory allocations in C++ using placement new. Applicable especially to usecases dealing with creation of large number of objects. A brief on problem: Lets take example problem for simplicity: - I have a G…
The viewer will learn additional member functions of the vector class. Specifically, the capacity and swap member functions will be introduced.
The viewer will be introduced to the member functions push_back and pop_back of the vector class. The video will teach the difference between the two as well as how to use each one along with its functionality.

743 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

12 Experts available now in Live!

Get 1:1 Help Now