How to avoid dynamic_cast/static_cast

[exterminator]

Visitor solution is okay but it does not look better than having members isDir() and isFile() in that these functions would be making 1 virtual call while the visitor solution makes 2. Good that it hides the keywords "*_cast" but I don't think it is well suited here.

For composite pattern, I looked at it the first time and tried pulling out some code that can help achieve the search functionality but it too required knowledge if a FSObject is a folder or not. Here is what I roughly got (incomplete but then I don't feel like completing it):

#include <iostream>
#include <string>
#include <vector>

class IFSObject
{
	public:
		virtual const std::vector<IFSObject*>& GetChildren() const = 0;
		virtual const std::string& GetName() const = 0
		virtual IFSObject& Clone() = 0;
		//other interfaces
		virtual ~IFSObject(){}
};

class File : public IFSObject
{
	public:
		File(const std::string& name_) : name(name_){}
		const std::vector<IFSObject*>& GetChildren() const{
			return std::vector<IFSObject*>();
		}
		const std::string& GetName() const{
			return name;
		}
		IFSObject& Clone(){
			return *(new File(name));
		}
	private:
		std::string name;
}

class Folder : public IFSObject
{
	public:
		Folder(const std::string& name_) : name(name_){}
		const std::vector<IFSObject*>& GetChildren() const{
			return children;
		}
		void Add(const IFSObject& something){
			/*Should keep IFSObject ownership*/
			children.push_back(&(something.Clone()));
		}
		void Remove(const IFSObject& something){
			/*Add remove logic*/
		}
		IFSObject& Clone(){
			return *(new Folder(name));
		}
		~Folder(){
			/*Add children cleanup logic*/
		}
	private:
		std::string name;
		std::vector<IFSObject*> children; /*may use shared_ptr<T>*/
}

class Link : public IFSObject
{
	/*add implementations with extensions*/
}

IFSObject* search(const std::string& name, const Folder& folder)
{
	//would need to know the actual type
	//Why??
	//Because there can be empty folders and links which will not be files.
}

int main()
{
	//create a filesystem
	Folder folder;
	//fill folder with various components
	IFSObject* fsobject_ptr = search("somefile", folder);
	return 0;
}

Or else, I might not have understood composite pattern well. But the thing is the moment a differentiation is necessary (which I think is), the composite pattern becomes a wrong choice.

Having a variant type might not help as well. Type information seems necessary. A virtual call is necessary.

There is one advantage with composite pattern though - the virtual call to know the type would be only necessary in the worst cases, i.e. when a directory does not have files and the cases when the FSObject may be a link. For the rest of the iteration one can go without knowing what FSObject* actually points to. That is a choice you can make.

I also had a quick look at boost::filesystem library where I though they might be having some different solution when finding files in a filesystem. But, alas, they don't have any such mechanism either. They also need to know the "type" information. They use a function named "is_directory". Take a look at the following code:

bool find_file( const path & dir_path,     // in this directory,
                const std::string & file_name, // search for this name,
                path & path_found )        // placing path here if found
{
	if ( !exists( dir_path ) ) 
		return false;
	directory_iterator end_itr; // default construction yields past-the-end
	for ( directory_iterator itr( dir_path ); itr != end_itr; ++itr )
  	{
    		if ( is_directory( *itr ) )
    		{
      			if ( find_file( *itr, file_name, path_found ) ) return true;
    		}
    		else if ( itr->leaf() == file_name ) // see below
    		{
      			path_found = *itr;
		      	return true;
    		}
  	}
  	return false;
}

So as to conclude my thoughts on this now, there are 2 options: go ahead with what you have already (something as in OP) or use composite pattern with type checking in worst cases. That can be reduced even further with one thing that I am not very sure of - but atleast in *nix and windows doing ls -altr or dir, I always see 2 entries (directories . and ..) may be paths to previous directory and current working directory. This may be a case worth considering whatever you are modelling (I think that is not actually a FS).

Hope it helps a little bit.

[wildfrog]

I also had a quick look at boost::filesystem library where I though they might be having some different solution when finding files in a filesystem. But, alas, they don't have any such mechanism either. They also need to know the "type" information. They use a function named "is_directory".

Somehow I don't find the Boost find_file example suitable for comparison (with the OP). They're only working with the type path, which can represent a path to 'anything' (a file, directory, link etc.). More interestingly a single Boost path instance can at one time represent a file, then later change and represent a directory.

- petter

[exterminator]

Somehow I don't find the Boost find_file example suitable for comparison (with the OP). They're only working with the type path, which can represent a path to 'anything' (a file, directory, link etc.). More interestingly a single Boost path instance can at one time represent a file, then later change and represent a directory.

Yeah, it is not exactly the same, but I found it quite analogous. path can be path to anything, FSObject* can point to anything.

[wildfrog]

Yeah, it is not exactly the same, but I found it quite analogous. path can be path to anything, FSObject* can point to anything.

You're right, but a path* will always point to a path and there is never a need for any casting. I would compare it to file/directory attributes. You don't specialize the File class and make a ReadOnlyFile or HiddenAndReadOnlyFile class, instead you add a functions like bool isReadOnly() or int getAttributes() to the File class.

- petter

[exterminator]

You're right, but a path* will always point to a path and there is never a need for any casting.

.. and that path string will either end up with a directory or a file. And to recursively get into a directory, a check for is_directory is used. There isn't a need of casting because is_directory tells about what path is, if it is a directory path it makes the recursive call else gets to the leaf which would be a file. That is what OP's isFile(), isFolder calls would do without casting. Surely there is a difference as these are dynamic calls but the things being achieved is similar and that is differentiation between files or folders.

I would compare it to file/directory attributes. You don't specialize the File class and make a ReadOnlyFile or HiddenAndReadOnlyFile class, instead you add a functions like bool isReadOnly() or int getAttributes() to the File class.

Well, there can be different approaches. Why can one not derive File to make ROFile/HAROFile/etc? That would cause a very different File class definition with conversions available depending upon user actions. But having member functions like isReadOnly/getAttributes can also be an approach. This can be another discussion on its own.

By the way, I am not quite sure if I understand where you are heading. The example given by me was not the determining point on which my thoughts were based.

[treuss]

Actually by specification, sibling nodes can be presented in any order within an XML document. If you have a document where the ordering of nodes is required, then it is non-conformant!

This is OT, but you must be kidding. I'm not reading into the XML standard, but if you look at the XML Schema standard, you will see that there are two elements for describing the structure of an XML document: <xs:sequence> and <xs:all>. The former one defines that the order of the child elements matter, the latter one defines that it does not matter. So why would the W3C define an element to specify a document structure that is not according to the standard.

[screetch]

docbook is an xml file, order is important....no kidding, order is important, try to change chapters order ^_^

[treuss]

The overhead isn't bad: it's a double-dispatch technique, resulting in two virtual function calls. This is usually not an issue.

Just as a follow-up: I implemented the visitor pattern into my program and did a quick performance test of the old vs. the visitor implementation. The result is that the visitor solution requires roughly 4% more CPU time for traversing a large data structure. So it's not a big issue, but it is measurable and to save 5% again on other places will be quite difficult. However, it will probably be less than 4% if the search condition will actually do some check as opposed to just returning false as it did for the test.

[jfaust]

Just as a follow-up: I implemented the visitor pattern into my program and did a quick performance test of the old vs. the visitor implementation. The result is that the visitor solution requires roughly 4% more CPU time for traversing a large data structure. So it's not a big issue, but it is measurable and to save 5% again on other places will be quite difficult. However, it will probably be less than 4% if the search condition will actually do some check as opposed to just returning false as it did for the test.

Intersting. You must be calling this a lot. I'm assuming that you are profiling on a release build, not a debug build, and running outside the debugger.

Just out of curiousity, what are the actual runtimes. Are we talking milliseconds or seconds here?

Jeff

[treuss]

Intersting. You must be calling this a lot.

Well, I was just curious, if the difference is measurable.

I'm assuming that you are profiling on a release build, not a debug build, and running outside the debugger.

The code is optimized with g++ -O3 -funroll-loops -march=athlon-xp -ftracer, which usually gave me the best results.

Just out of curiousity, what are the actual runtimes. Are we talking milliseconds or seconds here?

Depends on how much data you want to process . My test was traversing a data structure consisting of 180138 "folders" and 600552 "files" 100 times and the time it took on my Athlon XP 25000 was 7.77 vs 8.07 seconds. So for most people and most applications the difference would be insignificant.