// DTree.h

#if _MSC_VER >= 1000
#pragma once
#endif // _MSC_VER >= 1000

#ifndef DTreeh
#define DTreeh

#include "TreeList.h"
#include "FileDetails.h"

/* Directory Searching Made Easy
These classes allow you to iterate Files and Directories
 (optionally having a specified extension)
 in a specified Directory.

There are two classes CDtree and CQDTree.
CDTree sorts the Directory Tree so that Directories come before Files and all items are in name order alphabetically (case insensitive).
CQDTree is a Quick (unsorted) version.
I use Windows NT which gives sorted output (case sensitive) using CQDTree, but Win98 returns the Files in Disk Order.

CDTree uses an AVL Binary Tree for the sorting which should be the fastest method.
Sorting is very fast but I still wanted to offer the simpler class.
I tested the sort speed using a powerful workstation with RAM disk to ignore disk access times.
The sorting took a third of the time of the rest of the process (So if the Directory scan is going to take 3 minutes using the unsorted CQDTree class, it will take four minutes using the sorted CDTree class).

To deal with each File or Directory in a given Directory:

#include "DTree.h"
main() {
  CDTree DTree;
  if(DTree.GetList("V:\\Programming\\C++\\TestApps\\DirectoryTester","*.cpp")) {
    CString S;
    while(DTree.GetNext(S)) {
      bool Directory=DTree.IsDirectory();
      //Deal with it here...
} } }

The order of the search is as you would see the results in a fully expanded tree representation, top to bottom.
There is an IsLast() function to tell you if this is the last File Object in the current Directory.

You can 'recursively' deal with each File or Directory from a given Path.
The algorithm is efficient, doesn't use recursion and provides extra information (such as whether the File you're currently dealing with is the last File Object in this Directory).
To do this you call the CDTree::FromPath method or use the appropriate constructor (as shown below).
This Method will call three event handlers that you design in a Behaviour Class derived from CDTreeBehaviour.
 OnDIR  is called when a Directory is found. Return true to process that Directory.
 OnFile is called when a File is found.
 OnUp   is called when the search goes up a level.
You need to create this small class to describe the behaviour that you want to be performed on each event; here I've created CDTreeViewer as an example.
The example produces a full Directory tree listing:

+-dir1
| +-dir11
| | \-fName11
| \-dir12
|   +-fName.txt
|   \-fName12
\-dir2
  +-dir21
  | +-fName.txt
  | \-fName21
  +-dir22
  | +-Copy of fName22
  | +-fName.txt
  | \-fName22
  +-fName.txt
  \-fName2

#include "DTree.h"
#include "ioStream.h"  // For cout
#include <direct.h>    // For mkdir
#include <conio.h>     // For getch

class CDTreeViewer: public CDTreeBehaviour {
  bool Done[MAX_PATH];
public:
  CDTreeViewer(const CString& Path) {
    CString S;
    DWORD Length=GetFullPathName(Path,0,0,0); //Make relative paths absolute:
    GetFullPathName(Path, Length, S.GetBufferSetLength(Length), 0);
    S.ReleaseBuffer();
    cout << (const char*)(S) << endl;

    memset(Done, false, MAX_PATH);
    CDTree(Path, *this); //For the faster, unsorted version, use: CQDTree(Path, *this);
  }
private:
  void OnFile(CDTreeBase& DTreeBase) {
    for(int i=0; i<DTreeBase.GetDepth(); ++i) cout << (Done[i] ? "  " : "| ");
    cout << (DTreeBase.IsLast() ? '\\' : '+') << '-' << (const char*)(DTreeBase.GetName()) << endl;
    if(DTreeBase.IsLast()) Done[DTreeBase.GetDepth()]=true;
  }
  bool OnDIR (CDTreeBase& DTreeBase) {OnFile(DTreeBase); return true;}
  void OnUp  (CDTreeBase& DTreeBase) {Done[DTreeBase.GetDepth()]=false;}
};

main() {
  mkdir("Test"                                                );
  mkdir("Test\\dir1"                                          );
  mkdir("Test\\dir1\\dir11"                                   );
  CFile("Test\\dir1\\fName11"               ,CFile::modeCreate);
  mkdir("Test\\dir1\\dir12"                                   );
  CFile("Test\\dir1\\dir12\\fName.txt"      ,CFile::modeCreate);
  CFile("Test\\dir1\\dir12\\fName12"        ,CFile::modeCreate);
  mkdir("Test\\dir2"                                          );
  mkdir("Test\\dir2\\dir21"                                   );
  CFile("Test\\dir2\\dir21\\fName.txt"      ,CFile::modeCreate);
  CFile("Test\\dir2\\dir21\\fName21"        ,CFile::modeCreate);
  mkdir("Test\\dir2\\dir22"                                   );
  CFile("Test\\dir2\\dir22\\Copy of fName22",CFile::modeCreate);
  CFile("Test\\dir2\\dir22\\fName.txt"      ,CFile::modeCreate);
  CFile("Test\\dir2\\dir22\\fName22"        ,CFile::modeCreate);
  CFile("Test\\dir2\\fName.txt"             ,CFile::modeCreate);
  CFile("Test\\dir2\\fName22"               ,CFile::modeCreate);

  CDTreeViewer DTV("Test");
  getch();
}

The following code saves a Directory tree to a text file in a compact manner:
The top line is the start path.
Lines starting with a dot '.' specify a Directory name.
Lines starting with anything other than a dot are files within the last specified Directory.
Lines containing two dots mean "go up a Directory".

class CDTreeSaver: public CDTreeBehaviour {
public:
  CDTreeCat(const CString& Path) : pFile(0), pAr(0) {
    pFile=new CFile;
    if(!pFile->Open("C:\\S.TXT",CFile::modeCreate|CFile::modeWrite)) return;
    pAr=new CArchive(pFile,CArchive::store);
    pAr->WriteString(Path+"\r\n");
    CDTree(Path, *this);
  }
  virtual ~CDTreeCat() {try{delete pAr; delete pFile;}catch(...){ASSERT(0);}}
private:
  CFile* pFile;
  CArchive* pAr;
  void OnFile(CDTreeBase& DTreeBase) {pAr->WriteString(    DTreeBase.GetName()+"\r\n");}
  bool OnDIR (CDTreeBase& DTreeBase) {pAr->WriteString('.'+DTreeBase.GetName()+"\r\n"); return true;}
  void OnUp  (CDTreeBase& DTreeBase) {pAr->WriteString("..\r\n");}
};
*/

class CDTreeBase;
class CDTreeBehaviour {
public:
  virtual bool OnDIR (CDTreeBase& DTreeBase)=0; // return false to ignore files in this Directory
  virtual void OnFile(CDTreeBase& DTreeBase)=0;
  virtual void OnUp  (CDTreeBase& DTreeBase)=0;
};

//>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> CDTreeBase <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<

class CDTreeBase {
  friend class CQDTree;
  friend class  CDTree;
protected:
  CString Path;
  CString CurrentDirectoryName; // Only valid during ForAll(...)
  CString Name;
  CString Type;
  bool    First; //true if this is the first item in the Directory
  char WasFirst; // ==1 if this is the last item in the Directory was the first (used to delay the First flag in GetNext(CString S)
  bool    Last;  //true if this is the last item in the Directory (used for Tree representations)
  int     Depth;
  bool    Abort; //Used by ForAll

  bool GetList(WIN32_FIND_DATA& FindFileData, HANDLE& hFind, const CString& _Path, const CString& _Type="*") {
    Clear();
    Path=CLocalPath::FormatPath(_Path, false);
    Type=_Type;
    if((hFind=FindFirstFile(Path+'\\'+Type, &FindFileData))==INVALID_HANDLE_VALUE) return false; //Finds Files . & .. !!!
    while(FindFileData.cFileName[0]=='.' && (FindFileData.cFileName[1]==0 || (FindFileData.cFileName[1]=='.' &&  FindFileData.cFileName[2]==0))) {
      if(!FindNextFile(hFind, &FindFileData)) {
        Clear();
        return false;
    } }
    return true;
  }

  virtual void Clear()  {First=WasFirst=Last=false; Name.Empty();}
  virtual void Load()   =0;
  virtual void SetLast()=0;
  virtual void Find(const CString& Me, CString& File)=0; //After Up go to entry after "Me".

public:
  virtual ~CDTreeBase() {}
  virtual const CFileDetails* GetFileDetails() const =0;
  virtual void       SetName      ()       =0;
  virtual CString    GetShortName () const =0;
  virtual CString    GetExtension () const =0;
  virtual DWORD      GetAttributes() const =0;
  virtual CTime      GetCreated   () const =0;
  virtual CTime      GetAccessed  () const =0;
  virtual CTime      GetModified  () const =0;
  virtual __int64    GetSize      () const =0;

  virtual bool IsValid     () const =0;
  virtual bool IsEmpty     () const =0;

  virtual bool IsReadOnly  () const =0;
  virtual bool IsHidden    () const =0;
  virtual bool IsSystem    () const =0;
  virtual bool IsDirectory () const =0;
  virtual bool IsArchive   () const =0;
  virtual bool IsEncrypted () const =0;
  virtual bool IsNormal    () const =0;
  virtual bool IsTemporary () const =0;
  virtual bool IsSparse    () const =0;
  virtual bool IsReparse   () const =0;
  virtual bool IsCompressed() const =0;
  virtual bool IsOffLine   () const =0;
  virtual bool IsIndexed   () const =0;

  int     GetDepth    () const {return Depth;}
  bool    IsFirst     () const {return First;}
  bool    IsLast      () const {return Last ;}
  CString GetPath     () const {return Path ;}
  CString GetName     () const {return Name ;}
  CString GetPathName () const {return Path+'\\'+GetName();} //Use this to display the path to the user.
  CString GetShortPath() const { //Use this to give to File Functions because some fail with long file names if they contain characters such as !&% etc.
    CString ShortPath;
    DWORD Length=GetShortPathName(GetPath(),0,0);
    GetShortPathName(GetPath(), ShortPath.GetBufferSetLength(Length), Length);
    ShortPath.ReleaseBuffer();
    return ShortPath+'\\'+GetShortName();
  }

  virtual bool GetList(const CString& _Path, const CString& _Type="*")=0;

  bool GetNext(CString& S) { //Since this must be called to get the first Name we need to delay the First Flag.
    if(WasFirst==1) {++WasFirst; First=false;}
    if(!GetNext()) return false;
    if(WasFirst==0) {++WasFirst; First=true ;}
    S=GetName();
    return true;
  }
  bool GetNext() {
    if(!IsValid()) return false;
    if(IsFirst()) First=false;
    else if(IsLast()) {
      Clear();
      return false;
    }else Load();
    SetName();
    SetLast();
    return true;
  }

//>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> Directory 'Recursion' <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<

  void Stop() {Abort=true;}

  CString GetCurrentDirectoryName() const {return CurrentDirectoryName;} // The Name, not the Path, of the Current Directory.

  bool ForAll(CString StartPath, CDTreeBehaviour& Behaviour) { // Uses StartPath parameter as a temporary variable.
    Abort=false;
    CString File;
    Path=StartPath=CLocalPath::FormatPath(StartPath, false);
    Depth=0;
    int i=Path.ReverseFind('\\')+1;
    CurrentDirectoryName=(i ? Path.Mid(i) : Path); // If we're at the root of a Drive use that as the CurrentDirectoryName
    for(;;) {
      GetList(Path); // If it fails (empty Directory), fall through to go up a Directory
      for(;;) {
        while(GetNext(File)) {
          if(Abort) return false;
          if(IsDirectory()) { // Go down a Directory:
            if(Behaviour.OnDIR(*this)) { // At this point CurrentDirectoryName, Path and Depth are of the Directory where you are, and Name is of the Directory you're going into.
              Path+='\\'+File;
              CurrentDirectoryName=File;
              ++Depth;
              break; // Do this Directory's Files
            }
            continue; // Ignore this Directory
          }
          Behaviour.OnFile(*this); // At this point GetName() is of the File, and GetPath(), GetCurrentDirectoryName() and GetDepth() are of the Directory that the file is in.
        }
        if(!Name.IsEmpty()) break; // Go down a Directory
     // We've finished this Directory, so try to go up a Directory:
        i=Path.ReverseFind('\\')+1;
        Name=(i ? Path.Mid (i  ) : Path); // If we're at the root of a Drive use that as the Name
        bool Finished=(!Path.CompareNoCase(StartPath));
        Path=(i ? Path.Left(i-1) : Path); // If we're at the root of a Drive use that as the Path
        Behaviour.OnUp(*this); // At this point Path is where you are, and CurrentDirectoryName, Name and Depth are of the Directory you've just finished scanning.
        if(Finished) return true;
        ASSERT(i && !CurrentDirectoryName.IsEmpty()); // Can't go up any more Directories
        if(GetList(Path)) Find(CurrentDirectoryName, File); // Find CurrentDirectoryName and continue
        i=Path.ReverseFind('\\')+1;
        CurrentDirectoryName=(i ? Path.Mid(i) : Path); // If we're at the root of a Drive use that as the CurrentDirectoryName
        --Depth;
  } } }
};

//>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> CQDTree <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<

class CQDTree : public CDTreeBase {
protected:
  CFileDetails    File;
  WIN32_FIND_DATA FindFileData;
  HANDLE          hFind;
public:
  CQDTree() : hFind(INVALID_HANDLE_VALUE) {}
  CQDTree(const CString& Path, const CString& Type="*", int _Depth=0) : hFind(INVALID_HANDLE_VALUE) {Depth=_Depth; GetList(Path,Type);}
  CQDTree(const CString& StartPath, CDTreeBehaviour& Behaviour) {ForAll(StartPath, Behaviour);}
  virtual ~CQDTree() {try{Close();}catch(...){ASSERT(0);}}

  const CFileDetails* GetFileDetails() const {return IsValid() ? &File :0;}
  void                SetName       ()       {Name = File.GetName      ();}
  CString             GetShortName  () const {return File.GetShortName ();}
  CString             GetExtension  () const {return File.GetExtension ();}
  DWORD               GetAttributes () const {return File.GetAttributes();}
  CTime               GetCreated    () const {return File.GetCreated   ();}
  CTime               GetAccessed   () const {return File.GetAccessed  ();}
  CTime               GetModified   () const {return File.GetModified  ();}
  __int64             GetSize       () const {return File.GetSize      ();}

  bool IsValid     () const {return !File.GetName().IsEmpty();}
  bool IsEmpty     () const {return (hFind==INVALID_HANDLE_VALUE) && !Last;}

  bool IsReadOnly  () const {return File.IsReadOnly  ();}
  bool IsHidden    () const {return File.IsHidden    ();}
  bool IsSystem    () const {return File.IsSystem    ();}
  bool IsDirectory () const {return File.IsDirectory ();}
  bool IsArchive   () const {return File.IsArchive   ();}
  bool IsEncrypted () const {return File.IsEncrypted ();}
  bool IsNormal    () const {return File.IsNormal    ();}
  bool IsTemporary () const {return File.IsTemporary ();}
  bool IsSparse    () const {return File.IsSparse    ();}
  bool IsReparse   () const {return File.IsReparse   ();}
  bool IsCompressed() const {return File.IsCompressed();}
  bool IsOffLine   () const {return File.IsOffLine   ();}
  bool IsIndexed   () const {return File.IsIndexed   ();}

  bool GetList(const CString& _Path, const CString& _Type="*") {
    if(!CDTreeBase::GetList(FindFileData,hFind, _Path,_Type)) return false;
    File.Set(FindFileData);
    Last=!FindNextFile(hFind, &FindFileData);
    if(Last) Close(); //Close the handle as soon as possible
    return First=true;
  }

protected:
  void Clear() {
    CDTreeBase::Clear();
    File.Clear();
    Close();
  }
  void Close() {
    if(hFind!=INVALID_HANDLE_VALUE) {
      FindClose(hFind);
      hFind=INVALID_HANDLE_VALUE;
  } }
  void Load() {
    if(!IsEmpty()) {
      File.Set(FindFileData);
      Last=!FindNextFile(hFind, &FindFileData);
      if(Last) Close(); //Close the handle as soon as possible
  } }
  void SetLast() {}
  void Find(const CString& Me, CString& File) {while(GetNext(File) && !(IsDirectory() && (File==Me)));}
};

//>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> CDTree <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<

class CDTree : public CDTreeBase {
private:
  CTreeList        <CFileDetails> TreeList;
  CTreeListIterator<CFileDetails> it;
  CTreeListIterator<CFileDetails> LastNode;

public:
  CDTree() {First=Last=0; Depth=0;}
  CDTree(const CString& Path, const CString& Type="*") {GetList(Path,Type);}
  CDTree(const CString& StartPath, CDTreeBehaviour& Behaviour) {ForAll(StartPath, Behaviour);}
  virtual ~CDTree() {}

  const CFileDetails* GetFileDetails       () const {return it ? it.GetData() :  0;}
  void       SetName      ()       {Name = it ? it.GetData()->GetName      () : "";}
  CString    GetShortName () const {return it ? it.GetData()->GetShortName () : "";}
  CString    GetExtension () const {return it ? it.GetData()->GetExtension () : "";}
  DWORD      GetAttributes() const {return it ? it.GetData()->GetAttributes() :  0;}
  CTime      GetCreated   () const {return it ? it.GetData()->GetCreated   () :  0;}
  CTime      GetAccessed  () const {return it ? it.GetData()->GetAccessed  () :  0;}
  CTime      GetModified  () const {return it ? it.GetData()->GetModified  () :  0;}
  __int64    GetSize      () const {return it ? it.GetData()->GetSize      () :  0;}
  DWORD      GetCount     () const {return it ? TreeList.GetNodeCount      () :  0;}

  bool IsValid     () const {return it;}
  bool IsEmpty     () const {return TreeList.IsEmpty();}

  bool IsReadOnly  () const {return it ? it.GetData()->IsReadOnly  () : false;}
  bool IsHidden    () const {return it ? it.GetData()->IsHidden    () : false;}
  bool IsSystem    () const {return it ? it.GetData()->IsSystem    () : false;}
  bool IsDirectory () const {return it ? it.GetData()->IsDirectory () : false;}
  bool IsArchive   () const {return it ? it.GetData()->IsArchive   () : false;}
  bool IsEncrypted () const {return it ? it.GetData()->IsEncrypted () : false;}
  bool IsNormal    () const {return it ? it.GetData()->IsNormal    () : false;}
  bool IsTemporary () const {return it ? it.GetData()->IsTemporary () : false;}
  bool IsSparse    () const {return it ? it.GetData()->IsSparse    () : false;}
  bool IsReparse   () const {return it ? it.GetData()->IsReparse   () : false;}
  bool IsCompressed() const {return it ? it.GetData()->IsCompressed() : false;}
  bool IsOffLine   () const {return it ? it.GetData()->IsOffLine   () : false;}
  bool IsIndexed   () const {return it ? it.GetData()->IsIndexed   () : false;}

  bool GetList(const CString& _Path, const CString& _Type="*") {
    WIN32_FIND_DATA FindFileData;
    HANDLE hFind;
    if(!CDTreeBase::GetList(FindFileData,hFind, _Path,_Type)) {
      if(hFind!=INVALID_HANDLE_VALUE) FindClose(hFind);
      return false;
    }
    do TreeList.Insert(new CFileDetails(FindFileData)); while(FindNextFile(hFind, &FindFileData));
    FindClose(hFind);
    if(TreeList.GetDepth()>7) TreeList.Morph2List(); //Spend the time now; we just did a disk operation (slow) anyway. This will make the rest or the iteration faster for large numbers of files.
    it.Set(TreeList);
    LastNode.Set(TreeList);
    LastNode.End(); //Again, for speed, store the Last Node so we don't have to find it all the time.
    return First=true;
  }
  CTreeListIterator<CFileDetails> GetIterator() {return CTreeListIterator<CFileDetails>(TreeList);}

private:
  void Clear()   {CDTreeBase::Clear(); TreeList.Empty(); it.Set(TreeList);}
  void Load()    {it.Next();}
  void SetLast() {Last=(it==LastNode);}
  void Find(const CString& Me, CString& File) {it.Find(CFileDetails(Me)); GetNext(File);}
};

/*>>>>>>>>>>>>>>>>>>>>>> Directory Tree Serialization <<<<<<<<<<<<<<<<<<<<<<<<<

CDTreeSaver and CDTreeLoader Serialize the File and folder information of a Directory Tree

CDTreeSaver Usage:
  CDTreeSaver DTreeSaver("C:\Windows", "Local.Tree");
  if(!DTreeSaver.IsValid()) return "Couldn't create Local.Tree";

Three BYTE Tokens are used:
0 = End Of File.
1 = A CFileDetails Object follows.
2 = Go Up a Directory.
The Tree is written like a fully expanded Windows Explorer Tree from the top downwards.
The top File Object is written (preceded by a '1' BYTE Token).
If that File Object was a Directory, the next File Object to be written would be the directories first Child.
When the Directories children have all been saved an "Up" Token: (BYTE)2, is written.
When all File Objects have been written a "EOF" Token: (BYTE)0, is written,
*/
class CDTreeSaver : public CDTreeBehaviour {
  bool SavedOK;
  CFile*    pFile;
  CArchive* pAr;
  void OnFile(CDTreeBase& DTreeBase) {*pAr << (BYTE)1 << *DTreeBase.GetFileDetails();}
  bool OnDIR (CDTreeBase& DTreeBase) {OnFile(DTreeBase); return true;}
  void OnUp  (CDTreeBase& /*DTreeBase*/) {*pAr << (BYTE)2;}
public:
  CDTreeSaver(const CString& Root, const CString& FilePath) : pFile(0),pAr(0), SavedOK(false) {
    try{
      pFile=new CFile;
      if(!pFile
      || !pFile->Open(FilePath, CFile::modeWrite|CFile::modeCreate|CFile::shareDenyNone)) return;
      pAr=new CArchive(pFile, CArchive::store);
      if(!pAr) return;
      CDTree(Root, *this);
      *pAr << (BYTE)0;
      SavedOK=true;
    }catch(...) {}
    delete pAr;
    pAr=0;
    delete pFile;
    pFile=0;
  }
  bool IsValid() const {return SavedOK;}
  virtual ~CDTreeSaver() {
    try{
      delete pAr;
      delete pFile;
    }catch(...){ASSERT(0);}
  }
};
//To load a File saved by CDTreeSaver, derive a class from CTreeLoader and implement OnLoadTreeFOs(...)
class CDTreeLoader {
protected:
  CDTreeLoader() {}
  virtual ~CDTreeLoader() {}

  virtual void OnLoadTreeFileDetails(CFileDetails& File, const CString& Path) =0; //Override to use Load(...)

  bool LoadTreeFileDetails(CArchive& ar) {
    CString CurrentPath;
    BYTE b;
    CFileDetails File;
    for(;;) {
      ar >> b;
      switch(b) {
       default: return false;
        case 0: return true; // File Loaded OK
        case 1: { // Got a File Object next:
          ar >> File;
          OnLoadTreeFileDetails(File, CurrentPath);
          if(File.IsDirectory()) CurrentPath+=File.GetName()+'\\';
          continue;
        }
        case 2: { // Go Up a Directory
          CurrentPath.TrimRight('\\');
          int i=CurrentPath.ReverseFind('\\');
          if(i!=-1) CurrentPath=CurrentPath.Left(i)+'\\'; // If we're at the root of a Drive use that as the Path
          else CurrentPath.Empty();
          continue;
  } } } }
};

#endif //ndef DTreeh