Level order tree traversal with ExamineDirectory()

Share your advanced PureBasic knowledge/code with the community.
Mistrel
Addict
Addict
Posts: 3415
Joined: Sat Jun 30, 2007 8:04 pm

Level order tree traversal with ExamineDirectory()

Post by Mistrel »

I don't recall ever doing this before in PureBasic so it was a fun little excersize. I needed to walk a directory tree and while recursion is always simpler to implement, I prefer a stack-based approach.

This example program will output the all directories recursively starting from the directory where the executable is run. If you don't provide an alternative, the default location is your operating system's temp directory.

A summary on how breadth-first (level order) traversal works can be found here:
https://www.cs.bu.edu/teaching/c/tree/breadth-first/

Code: Select all

CompilerIf #PB_Compiler_OS=#PB_OS_Windows
  #PS$="\"
CompilerElse
  #PS$="/"
CompilerEndIf

Structure DirectoryStack
  Id.i
  PathName.s
EndStructure

ExaminePath.s=RTrim(GetPathPart(ProgramFilename()),#PS$)

NewList Stack.DirectoryStack()

Directory=ExamineDirectory(#PB_Any,ExaminePath.s,"*.*")

If Not Directory
  End
EndIf

AddElement(Stack())
Stack()\Id=Directory
Stack()\PathName=ExaminePath.s

While ListSize(Stack())>0
  NextPath=Stack()\Id
  CurrentPath.s=Stack()\PathName.s
  
  While NextDirectoryEntry(NextPath)
    EntryName.s=DirectoryEntryName(NextPath)
    
    If EntryName.s="." Or EntryName.s=".."
      Continue
    EndIf
    
    If DirectoryEntryType(NextPath)=#PB_DirectoryEntry_Directory
      ChangeCurrentElement(Stack(),LastElement(Stack()))
      
      Directory=ExamineDirectory(#PB_Any,CurrentPath.s+#PS$+EntryName.s,"*.*")
      
      If Directory
        AddElement(Stack())
        Stack()\Id=Directory
        Stack()\PathName.s=CurrentPath.s+#PS$+EntryName.s
      EndIf

      ;/ Debug
      Debug CurrentPath.s+#PS$+EntryName.s
      
      ChangeCurrentElement(Stack(),FirstElement(Stack()))
    EndIf
  Wend
  
  FinishDirectory(NextPath)
  DeleteElement(Stack())
  ChangeCurrentElement(Stack(),FirstElement(Stack()))
Wend
Last edited by Mistrel on Mon Jul 09, 2018 11:56 pm, edited 4 times in total.
User avatar
Kwai chang caine
Always Here
Always Here
Posts: 5342
Joined: Sun Nov 05, 2006 11:42 pm
Location: Lyon - France

Re: Breadth-first tree traversal with ExamineDirectory()

Post by Kwai chang caine »

Thanks for sharing 8)
ImageThe happiness is a road...
Not a destination
davido
Addict
Addict
Posts: 1890
Joined: Fri Nov 09, 2012 11:04 pm
Location: Uttoxeter, UK

Re: Breadth-first tree traversal with ExamineDirectory()

Post by davido »

@Mistrel,

I am using PureBasic 5.70b1.
It wouldn't run because #PS is already defined as an integer.

I just changed #PS to #PS$ as PureBasic 5.70 already defines #PS$ to the OS path delimiter character.
It then worked perfectly.

Useful. Interesting, too.
Thank you for sharing.
DE AA EB
Mistrel
Addict
Addict
Posts: 3415
Joined: Sat Jun 30, 2007 8:04 pm

Re: Breadth-first tree traversal with ExamineDirectory()

Post by Mistrel »

Fixed to use the correct constant #PS$ and added a check for a failed call to ExamineDirectory() which may occur with insufficient permissions.
Mistrel
Addict
Addict
Posts: 3415
Joined: Sat Jun 30, 2007 8:04 pm

Re: Level order tree traversal with ExamineDirectory()

Post by Mistrel »

There are several other forms of tree transverse such as inorder, preorder, and postorder.

If anyone is feeling up to it, I would encourage you to try to solve the traversal with one of these alternative methods as an excersize:

https://www.geeksforgeeks.org/tree-trav ... postorder/
Post Reply