search recursively without using a recursive iterator

[cmccaig]

im writing a program for school that needs to search through a directory and find files of a certain type. if it meets up with a folder i need to search inside it and so on for all other folders found inside.
i was thinking of a function to pass the path into but if it meets up with a folder inside i cannot call a function that im already inside.
im not allowed to use boost::filesystem::recursive_directory_iterator
and anything from boost filesystem has to be from version 3

i dont need actual code examples just need a hint to wrap my head around the idea

[WaltP]

You don't need boost for recursion. Just call function traversing the directory while traversing the directory.

Your compiler will probably have filesystem commands to walk through a directory
( findfirst() and findnext() type of functions). Check your compiler documentation.

[Taywin]

You could try depth first search (DFS) and store every file/folder found in a queue. If the element which is popped from the queue is a directory, go inside the directory and push all files/directories listed inside the directory into the queue. If it is a file, check whether or not it matches the type you are looking for. Hope this help.

[vijayan121]

Class basic_directory_iterator is an important component of the library. It provides an input iterator over the contents of a directory, with the value type being class basic_path. Typedefs directory_iterator and wdirectory_iterator are provided to cover the most common use cases.

The following function, given a directory path and a file name, recursively searches the directory and its sub-directories for the file name, returning a bool, and if successful, the path to the file that was found. The code below is extracted from a real program, slightly modified for clarity:

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->status()) )
        {
          if ( find_file( itr->path(), file_name, path_found ) ) return true;
        }
        else if ( itr->leaf() == file_name ) // see below
        {
          path_found = itr->path();
          return true;
        }
      }
      return false;
    }

The expression itr->path().leaf() == file_name, in the line commented // see below, calls the leaf() function on the path returned by calling the path() function of the directory_entry object pointed to by the iterator. leaf() returns a string which is a copy of the last (closest to the leaf, farthest from the root) file or directory name in the path object.

In addition to leaf(), several other function names use the tree/root/branch/leaf metaphor.

Notice that find_file() does not do explicit error checking, such as verifying that the dir_path argument really represents a directory. Boost.Filesystem functions throw exceptions if they do not complete successfully, so there is enough implicit error checking that this application doesn't need to supply additional error checking code unless desired. Several Boost.Filesystem functions have non-throwing versions, to ease use cases where exceptions would not be appropriate.

Note: Recursive directory iteration was added as a convenience function after the above tutorial code was written, so nowadays you don't have to actually code the recursion yourself.

- From Boost.Filesystem library 1.35 Two-minute tutorial http://www.boost.org/doc/libs/1_35_0/libs/filesystem/doc/index.htm

[cmccaig]

#define BOOST_FILESYSTEM_VERSION 3
#define BOOST_FILESYSTEM_NO_DEPRECATED

#include <iostream>
#include <string>
#include <vector>
#include <boost/filesystem.hpp>
namespace fs = boost::filesystem;
using namespace std;

int main(int argc, char* argv[])
{
	fs::path fullPath(".");
	if(argc > 1)
		fullPath = fs::path(argv[1]);

	if(!fs::exists(fullPath))
		cout << "\nNot found: " << fullPath << endl;

	vector<fs::path> v_path;
	vector<string> v_selection;
	v_selection.push_back(".docx");
	v_selection.push_back(".xlxs");
	v_selection.push_back(".sln");
	v_selection.push_back(".txt");


	cout << " 0: Microsoft Word 2007\n 1: Microsoft Excel\n 2: Visual Studio 2010\n 3: Notepad" << endl;
	int userSelection;
	cout << "Enter your Choice: ";
	cin >> userSelection;

	fs::directory_iterator endIt;


	for(fs::directory_iterator dirIt(fullPath); dirIt != endIt; ++dirIt)
	{
		try
		{
			if(fs::is_directory(*dirIt))
			{
				for(fs::directory_iterator rdirIt(dirIt->path()); rdirIt != endIt; ++rdirIt)
				{
					
				}
			}else if(dirIt->path().extension() == v_selection[userSelection])
			{
				v_path.push_back(dirIt->path());
			}else
			{
				continue;
			}
		}
		catch( const std::exception& ex)
		{}
	}
}

this is what i have so far... you can see where i attempt to do the recursion, but you can also see what problems this method will bring

[cmccaig]

bump....

[Taywin]

The way you did is not recursion but iteration. OK, let me try to write a psuedo code for it...

/*
fs <- the root file directory
fList <- a list of file found which is initiated to empty
ftype <- a file type/extension a user is looking for
fsRecursive(fs, fList, ftype)
  files <- get a list of files inside fs
  for each files as f
    if f matches the ftype  // <-- somewhat base case, but not quite because you are collecting
      push f onto fList     //     all the file matches
    else if f is a directory
      fsRecursive(f, fList, ftype)  // <-- recursive part
  return
*/

The psuedo above would be different if you want to just print out the result or you want it to return a list instead of passing in an array of the fList.