Find the total number of emails in a folder (with all of the subfolders)

Question

The Folder struct definition below is given:

type Folder struct { 
    ID int
    emailCount int
    childFolderIDs []int
}

Description of the fields are:

• Id : folder id
• emailCount : number of emails in the folder
• childFolderIDS : if the folder has subfolders, this list contains folder IDS of the subfolders.

I am trying to write a function:

• Function is taking two parameters:
  • First parameter is a list of all folders in the email application

      var folders = []Folder{  
            Folder{1, 30, []int{2, 4}},  
            Folder{2, 10, []int{3}},  
            Folder{4, 60, []int{}},  
            Folder{3, 20, []int{}},  
      }  
    

  • Second parameter is folder id of a folder
• Function will return a total number of emails with ID=Folder Id and all of its children recursively.

For example:

If the second parameter is:

• four, then the function should return 60 (there is no subfolder)

• two, then the function should return 30

My code is below:

      package main

      import "fmt"

      type Folder struct {
          ID int
          emailCount int
          childFolderIDs []int
      }

      func InsertIntoMap(data_arr []Folder) map[int]Folder {
          var retval = make(map[int]Folder)
          var child_folders []int
          for _, elem := range data_arr {
            child_folders = elem.childFolderIDs
            var folder Folder 
            folder.ID = elem.ID
            folder.emailCount = elem.emailCount
            folder.childFolderIDs = child_folders
            retval[elem.ID] = folder
          }    

          return retval
      }

    func GetTotalEmailCount(p_map map[int]Folder, folder_id int) int {
          total := 0
          var child_folders []int
          child_folders = p_map[folder_id].childFolderIDs
          total = total + p_map[folder_id].emailCount

          if len(child_folders) == 0{
            return total
          }else{
            for e := range child_folders {
              return total + GetTotalEmailCount(p_map, child_folders[e])
              }          
          }

          return total
    }

      func main() {

        var folders = []Folder{
          Folder{1, 30, []int{2, 4}},
          Folder{2, 10, []int{3}},
          Folder{4, 60, []int{}},
          Folder{3, 20, []int{}},
      }

      var m = InsertIntoMap(folders)

      fmt.Println(GetTotalEmailCount(m,1))  // result is 60
      fmt.Println(GetTotalEmailCount(m,2))  // result is 30
      fmt.Println(GetTotalEmailCount(m,3))  // result is 20
      fmt.Println(GetTotalEmailCount(m,4))  // result is 60

      }
```

Answer 1

First, your code doesn't give correnct answers; for (m, 1) the answer should be 120 (30 in ./1, +10 in ./1/2, +20 in ./1/2/3, +60 in ./1/4; you never count more than a single entry in the sub-folder slice).

Also, you should run go fmt (or goimports) on your code (perhaps you did and that was lost when posting). Also, adding a Go Playground link to your original code in posts is helpful.

You mention that you wanted to create a function taking two parameters, the first being []Folder but your code instead converts the slice into a map and uses that as the first argument. Which did you intend? When you have a function or functions that are answering questions based on an argument you could consider making a method. For example, perhaps something like:

type Folders []Folder
// or
type Folders struct {
    list []Folder
    byID map[int]Folder
}

func (f Folders) EMailCount(folder int) int {
    // code that uses f and folder as arguments
}

You use snake_case for some of your identifiers and camelCase for others; idiomatic Go code uses camelCase for all identifiers.

In your InsertIntoMap function:

• When you make the map you know how many entries you expect so you should include that number to make as a size hint (e.g. make(map[int]Folder, len(data))). If the size is large this avoids the having to dynamically re-size the map as you add entries.
• You name the map retval, I'd instead name it based on what contains (a map of folders by ID) rather than it happens to be the return value. I'd call it just m or byID.
• Within the loop you effectively copy the element elem to the variable folder. You can do this with just folder := elem but at that point the entire loop body can just be rewritten as retval[elem.ID] = elem.

In your GetTotalEmailCount function:

• Normally in Go instead of:

  var foo []int
  foo = something[bar].foo
  

  you'll just see:

  foo := something[bar].foo
  

  not only is it shorter but it can make future code changes easier. In the latter if the field foo changes type you don't need to edit the type of the variable foo to match. (By the way, shorter isn't always better. Clarity is more important than conciseness).

• Idiomatic Go code tends avoid indenting code by using early returns (see https://github.com/golang/go/wiki/CodeReviewComments#indent-error-flow). You return if len(…) == 0 so you should just drop the else clause and remove the indent (golint will suggest this). E.g, instead of:

  if someCondition {
      return something
  } else {
      // other code
      //     possibly with more conditional/loop indenting
  }
  

  it would be:

  if someCondition {
      return something
  }
  
  // other code
  //     possibly with more conditional/loop indenting
  

• In this specific case, you don't even need the conditional since for range loops don't do anything on empty/nil slices the following return total line is sufficient.

• It's in this for loop your your bug exists. On the first iteration you stop looping and return the total of this folder and it's first child without iterating to the next child.

  return total + GetTotalEmailCount(p_map, child_folders[e])
  

  should be:

  total += GetTotalEmailCount(p_map, child_folders[e])
  

Without changing the basic structure of your code, all the above gives something like this (Go Playground):

package main

import "fmt"

type Folder struct {
    ID             int
    emailCount     int
    childFolderIDs []int
}

func InsertIntoMap(data []Folder) map[int]Folder {
    m := make(map[int]Folder, len(data))
    for _, e := range data {
        m[e.ID] = e
    }
    return m
}

func GetTotalEmailCount(m map[int]Folder, folder int) int {
    children := m[folder].childFolderIDs
    total := m[folder].emailCount

    for e := range children {
        // BUG: doesn't detect infinite loops
        total += GetTotalEmailCount(m, children[e])
    }

    return total
}

func main() {
    var folders = []Folder{
        Folder{1, 30, []int{2, 4}},
        Folder{2, 10, []int{3}},
        Folder{4, 60, []int{}},
        Folder{3, 20, []int{}},
    }

    var m = InsertIntoMap(folders)
    fmt.Println(GetTotalEmailCount(m, 1)) // result is 120, 30+10+20+60
    fmt.Println(GetTotalEmailCount(m, 2)) // result is 30
    fmt.Println(GetTotalEmailCount(m, 3)) // result is 20
    fmt.Println(GetTotalEmailCount(m, 4)) // result is 60
}