(Reverse?) Tree Enumeration

Question

I'm working on this app to gather some file/folder usage data. The goal is to have my object know the size of its files and children folders; at every point in the tree.

My problem is; after getting the directory structure into my objects, I'm perplexed at how to get the subtotals in there.

Could I actually add the totals in when creating the trees? Or do I have to step through the tree in reverse (which seems especially confusing...)

I'm a novice with no computer science education; I'm sure the answer would be out there if I knew the right terminology to Google.

My classes are currnetly a bit of a mess, they've still got some half formed ideas there...

Imports System.IO
Public Class Form1
    Public Class mrFURDirectory
        Public Property Name As String
        Public Property FileSize As Long = 0
        Public Property FileCount As Long = 0
        Public Property DirSize As Long = 0
        Public Property DirCount As Long = 0
        Public Property Parent As mrFURDirectory
        Public Property Children As New List(Of mrFURDirectory)
        Public Property PercentOfParent As Short = 0
        Public Property DirChecked As Boolean = False

        Public Sub New(ByVal Name As String)
            Me.Name = Name
        End Sub
    End Class

    Public Class mrBaseFURDirectory
        Inherits mrFURDirectory
        Property RootPath As String

        Sub New(ByVal Name As String, ByVal RootPath As String)
            MyBase.New(Name = Name)
            Me.RootPath = RootPath
        End Sub

    End Class

    Dim BaseDirectory As New mrBaseFURDirectory("A:\", "a:\") 'RAM disk full files/folders

    Private Sub Form1_Load(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles MyBase.Load

        'setup IO
        Dim IOBaseDirectory As IO.DirectoryInfo
        IOBaseDirectory = New IO.DirectoryInfo(BaseDirectory.RootPath)

        'go get 'em tiger!
        GatherChildDirectoryStats(IOBaseDirectory, BaseDirectory)

        MsgBox("Done.")
    End Sub

    Public Sub GatherChildDirectoryStats(ByVal IODirectory As IO.DirectoryInfo, ByVal FURDirectory As mrFURDirectory)

        'get the file count and total size of files in this directory
        For Each aFile As IO.FileInfo In IODirectory.GetFiles
            FURDirectory.FileSize += aFile.Length
            FURDirectory.FileCount += 1
        Next

        For Each Directory As IO.DirectoryInfo In IODirectory.GetDirectories
            'DirCount likely redundant..
            FURDirectory.DirCount += 1

            'if we're in here, we need another child, make one
            Dim NewChildDir As mrFURDirectory
            'attach it to the parent
            FURDirectory.Children.Add(New mrFURDirectory(Directory.Name))
            'reference the child
            NewChildDir = FURDirectory.Children(FURDirectory.Children.Count - 1)
            'tell the child who the parent is
            NewChildDir.Parent = FURDirectory

            'recurse into sub again
            GatherChildDirectoryStats(Directory, NewChildDir)
        Next

    End Sub

Answer 1

After adding up all the file sizes in each node you are calling the subnodes to do the same. After this call returns add this:

'recurse into sub again
GatherChildDirectoryStats(Directory, NewChildDir)

'add child sums to this node    
FURDirectory.DirSize += NewChildDir.FileSize + NewChildDir.DirSize

So the last node sums up its files, returns and the sums are added to the n-1 node etc. Recursion rocks!

Answer 2

You can do it as you go along. All you need to do is having processed a child directory then add the stats into the current directory.

The other option is to put a property on the mrFURDirectory object that will go and get all the relevant stats. This property will look at the stats on the current mrFURDirectory and then loop through all the children using their relevant stat property and adding it in. Of course the children will look up recursively, etc.

Assuming this is a static snapshot you can store these results in somethign nullable so once you have worked it out once you can skip the calculations the second time around. I suspect this is along the lines of what you were thinking when you talked about stepping through the tree in reverse but it is a much more obvious and intuitive way of doing it.

In this case the latter method is much the same as the former method except that you are being lazier about it. The first method (adding a child directories stats as it is processed) will be doign much the same thing except as you go along rather than at the end.

Answer 3

You are almost there: the size of a directory is the sum of the sizes of the files (this you have) PLUS the sum of the sizes of the subdirectories.

So right after you finish adding a subdirectory, you can get it's total size and add that to the total size of the currect directory.