IBM®
Skip to main content
    Country/region select      Terms of use
 
 
   
     Home      Products      Services & solutions      Support & downloads      My account     

developerWorks  >  Lotus  >  Forums & community  >  Best Practice Makes Perfect

Best Practice Makes Perfect

A collaboration with Domino developers about how to do it and how to get it right in Domino

Bob Balaban recently posted about recursion and how to program so that it is not needed. The main problem is that the size of the LotusScript stack is limited, and bad things happen if you exceed it. This is generally not a problem if you're not using recursion, because the stack only goes as deep as you have explicitly designed it to go.

I agree that it's better to try for an iterative implementation in many cases. I just thought Bob's example was rather long and complex, and I happened to have a simpler one that makes the point more clearly, and is useful. The problem was to write a function like the Mkdir command, but that would work even if the containing directory didn't already exist. So for instance, you would use the call:

MakeDir "C:\movies\stars\carmen-miranda\pics"

If you do this with the built-in Mkdir function, it will fail if the containing folder (C:\movies\stars\carmen-miranda) doesn't already exist. I wanted it to be able to create the whole series of folders, if necessary.

The simplest way to find out whether the containing folder is already there, is to try a Mkdir of the whole path and trap the error that happens if it is not so. Yes, you could parse out the filepath and explicitly check for the existence of the parent and whether it's a directory, but why do all that work when the Mkdir command will do it for you? So here's a recursive and iterative implementation of the task using that technique:

Recursive MakeDirR Iterative MakeDir
Sub MakeDirR(Byval strWhere$)
      On Error 76 Goto parentDoesNotExist

      Mkdir strWhere

      Exit Sub

parentDoesNotExist:
' or other problem, but let's assume that for now.
      On Error 76 Goto fullpatherr

      Dim fname$, fpath$

     
SplitFilepath strWhere, fpath, fname
      MakeDirR fpath

      Mkdir strWhere

      Exit Sub
End Sub
Sub MakeDir(Byval strWhere$)    
       On Error 76 Goto parentDoesNotExist

       Dim stack$

       Const NL = {

}

       Do

               Mkdir strWhere

               On Error Goto 0
' first success, stop trapping errors; avoid infinite loop.
               strWhere = Strleft(stack, NL)
' "pop" a path for next iteration
               stack = Mid$(stack, Len(strWhere)+2)

failed:

       Loop Until strWhere = ""

       Exit Sub

       
parentDoesNotExist:

       ' This error code can indicate other problems, but assume missing parent.

       ' If not, we get a different error (75) later when trying to create the parent.

       Dim fpath$, fname$

       
SplitFilepath strWhere, fpath, fname
       If fpath = "" Then Error 76, "Invalid path: '" & strWhere & "'"

       stack = strWhere & NL & stack
' "push" onto stack to retry later.
       strWhere = fpath
' try a path one step shorter.
       Resume failed

End Sub
Code shared by both approaches:
Sub SplitFilepath(Byval fullpath$, dirpath$, filename$)
       Const DELIMS = {/\:}

       While Instr(DELIMS, Right$(fullPath, 1))
' discard final delimiter character...
               fullpath = Left$(fullpath, Len(fullpath)-1)

       Wend

       Dim candidate$, i%

       filename = Strtoken(fullpath, Left$(DELIMS, 1), -1)

       For i = 2 To Len(DELIMS)

               candidate = Strtoken(fullpath, Mid$(DELIMS, i, 1), -1)

               If Len(candidate) < Len(filename) Then

                       filename = candidate

               End If

       Next

       Dim fplen%

       fplen = Len(fullpath)-Len(filename)
       If fplen > 0 Then fplen = fplen - 1
       dirpath = Left$(fullpath, fplen)

End Sub


Look at the recursive routine, MakeDirR, first. The role of the stack here is to keep track of the remaining work to be done, and where in the middle of a suspended task we were (on which line). This routine tries to create a folder, and if this fails, tries to create the parent folder, and if that fails, tries to create its parent folder, and so on until either the create succeeds, or there's an error that's not consistent with a missing parent folder. Then it backtracks to create the folders that it put off creating earlier (this time not trapping errors, to avoid infinite recursion). The variable strWhere has a different value at each level of the stack, and that's how we remember what folder we were trying to create at that level.

Converting any recursive implementation to iterative, requires a replacement for the role of the stack in tracking work to be done. In Bob's example, he uses a Queue class. This is a good way to do it, and it's nice to have such a class in your personal library (I have a version that's not specific to DOM nodes). But it doesn't need to be that complex; in many cases an array or string can be used to stuff everything you want to keep track of. The nice thing about a string or a "redimmed" array, is that it doesn't take up a lot of room on the stack -- just a few bytes -- but you can store lots of data in it. This is also true of an object variable.

In my example, I use a string (stack) to keep a list of the directories I must try to create. This technique depends on the existence of a delimiter character (newline in this case) that will not appear in the data. Each time creation of a folder fails, the failed path is added to the beginning of stack, and the last part of the path is dropped. Again, once successful in creating a folder, it turns off error trapping to avoid an infinite loop. This is the same sequence of operations as the recursive function, but without the stack, we have to add logic to explicitly store and retrieve information and to control position in the code. This makes the iterative implementation a little longer, as usual (though in this case some of the extra length is caused by better comments).

So the iterative implementation has a little more code, and lacks the elegant simplicity of recursion, but is safer (and often more efficient). In this case, the chance of overrunning the stack limit is probably fairly small, since a path won't have so very many levels of folder names. We'd probably be just fine with the recursive approach, unless we're already pushing the limit before we call this routine. So, do what you think best -- but I'm putting the iterative version in my library.

Andre Guirard | 11 April 2008 05:12:00 AM ET | Home, Plymouth, MN, USA | Comments (9)

Search this blog 

Disclaimer 

    About IBM Privacy Contact