I previously wrote in general about data structures in LotusScript. Now I want to talk about one specific “classic” data structure, the queue. The strict version of this is like a pipeline where you put things in one end, and you pull them out the other end in the same order they went in. It’s a good way to keep track of work that needs doing.
As with everything in LotusScript, as regards the datatype of the contents, you either have to write a generic class that can contain any type of data, or if you want type checking, specific classes for each content datatype you want to support. There’s no concept of an Interface like in Java, that you can just declare to the type you want.
The Queue class shown below can contain either primitives or objects — the caller needs to keep track of what type of data it’s putting in. The properties and methods are:
- Sub New(defaultval): the argument is the value to return for the Get method if the queue is empty. E.g. if the contents are objects it might be Nothing so you can always safely use the Set statement with the result.
- Sub Put(value): Add a value to the end of the queue.
- Function Get as Variant: Remove a value from the front of the queue and return it. If the queue is empty return the default value specified in the constructor.
- IsEmpty as Boolean: reports TRUE if the queue contains no values.
If you find this website helpful and want to give back, may I suggest buying, reading, and reviewing one of my excellent books? More are coming soon!
If you want email whenever there’s a new post, you can subscribe to the email list, which is 100% private and used only to send you information about stuff on this site.
The implementation of this class uses a simple linked list. A helper class, QueueNode, contains the value that was queued, and a pointer to the next-oldest item. The most recently queued item has a Next pointer to Nothing — the null-pointer keyword in LotusScript.
In the above example, there are three elements in the queue, the oldest being the value 5, then 17, then 8. When we “get” a value from the list, it comes from the node pointed to by the top pointer of the Queue object — Get returns the value 5. The top pointer then follows the Next pointer of that node to find the new top node, 17. The QueueNode containing 5 is discarded.
To “put” a value in the list, the class creates a new QueueNode to contain it. The end pointer of queue is set to point to it, and so is the next pointer of the previous youngest node, 8.
All the links in this linked list are one-way. Recalling how reference counting works, what happens if you delete the Queue object? There was only one pointer to the QueueNode containing 5, and it’s just been deleted, so the reference counter of QueueNode 5 drops to zero. That makes the garbage cleaner delete that node. The 5 node contained the only pointer to the 17 node, so next the 17 node is deleted, and finally the 8 node, since both pointers that were pointing to it have been deleted. We can see this will end up with all the data going away. It’s like a piece of knitting unraveling because there was one loose end.
Suppose we’d had a ring rather than a chain, though? Suppose our implementation had the newest QueueNode pointing to the oldest as its Next value? 8 loops back around to point to 5 in this example. When the Queue object is deleted, the QueueNodes still each have something pointing to them. But there are no pointers to the QueueNodes from anywhere else. You can’t get at them, but also they don’t automatically get garbage-collected.
Since we don’t have a cycle of links, in this case it doesn’t appear necessary to take any special action to free memory. But I added a Delete method to the class to forcibly delete them anyway — just to be safe.
Incidentally, if your queue contains objects rather than number values as in this case, would you want to delete those objects also? Like if it was a queue of NotesDatabases to be processed — should you delete the NotesDatabase objects also?
Probably not. Remember the script may have other variables with links to those same objects, and Deleting them deletes that object everywhere. Maybe some other code was still using those objects. Here we must depend on the reference counter doing its job, or the caller explicitly deleting objects as needed.
%REM Class Queue By Andre Guirard Description: A strict queue of objects or primitives, implemented with a linked list. Constructor: New Queue(defaultval) where defaultval is the value to return to a Get call if the queue is empty. %END REMClass Queue Private z_top As QueueNode Private z_end As QueueNode Private z_defval As Variant Sub New(defaultval) If IsObject(defaultval) Then Set z_defval = defaultval Else z_defval = defaultval End Sub
%REM Sub Put Description: Add a value to the queue %END REMSub Put(value) Dim aNode As New QueueNode(value) If z_end Is Nothing Then Set z_end = aNode
' first node is both top and bottom of list.Set z_top = aNode Else
' append to end node, and this is the new end.Set z_end.Next = aNode Set z_end = aNode End If End Sub
%REM Function Get Description: Return the oldest value in the queue, removing it also. %END REMFunction Get As Variant If z_top Is Nothing Then If IsObject(z_defval) Then Set me.get = z_defval Else me.get = z_defval ElseIf IsObject(z_top.value) Then Set me.get = z_top.value Else me.get = z_top.value End If Dim aNode As QueueNode Set aNode = z_top Set z_top = z_top.Next Delete aNode
' if this was the last node this also deletes z_end since they're the same object.End Function Public Property Get IsEmpty As Boolean me.IsEmpty = (z_top Is Nothing) End Property Sub Delete Dim aNode As QueueNode While Not z_top Is Nothing Set aNode = z_top Set z_top = z_top.Next Delete aNode Wend End Sub End Class
%REM Class QueueNode Constructor: New QueueNode(value) %END REMPrivate Class QueueNode Public value As Variant Public Next As QueueNode Sub New(value) If IsObject(value) Then Set me.value = value Else me.value = value End Sub End Class
How would we use the above class to track work that needs doing? As an example, here’s a function that takes a filepath and matching criteria, and recursively finds all the files that match the wildcard syntax given. You could do this with actual recursion — when it finds a folder name the function could call itself to process that folder. But you run the risk with recursion of hitting a limit — of stack size, for instance. It’s often better to avoid recursion and write a “flat” function that keeps track of what needs doing using data structures.
The Dir$ function in LotusScript isn’t recursive — it returns the contents of a specified path. So the strategy of this function is to scan the folder for subfolders and put each subfolder in the queue for later processing. The main loop of the function pulls a folder name from the queue and processes that folder. This processing includes looking for subfolders and queueing those also. The outer loop continues until the queue is empty.
This code is also an example of the use of a List datatype to manage a searchable list of strings. The Dir$ function doesn’t have an option to return only folders. You can ask for only files, or for files and folders mixed together. If you want a list of only folders, you have to ask for the list of everything, then ask for the list of files, and subtract the files from the list of everything, leaving folders. A tactic I like in cases like this is to use a List as a collection of strings — I don’t care about the values, just the keys. I called Dir$ once asking for only files, and added each filename as a key value in a list of Booleans.
Later, I asked Dir$ for all files and folders. For each name it returns, I use IsElement to see whether the name is a key value in my list of filenames. If not, it must be a folder — so I add it to the work queue.
Note: this code uses names defined in the lsconst script library.
%REM Function FileSearch Description: Recursively search a given folder for files who name match a set of patterns. Works on any OS. Arguments: baseDir: the folder you want to search. May optionally have a directory delimiter at the end, e.g. "C:\foo" or "C:\foo\". Should work on any OS. patterns: a string delimited with "|" listing the second operands for a LIKE operator to match against the filename, case insensitive. E.g. "*.dat|ac[0-5]*.cab" to find all ".DAT" files and all ".CAB" files whose names begin "ac" followed by digit 0 to 5. Returns: array of strings containing full filepaths of all matching files, or if no matches found, array containing one blank element. %END REMFunction FileSearch(ByVal baseDir$, ByVal patterns$) As Variant Dim delim$, afile$, results$, adir$, patternarr Dim workq As New Queue("") Dim files List As Boolean
' find what path delimiter the caller prefers.If basedir Like "/*" then delim = "/"
' linux style pathElseIf basedir Like "\*" Or basedir Like "[A-Z]:\*" Then delim = "\"
' windows style pathElse Error 20030, "FileSearch needs an absolute filepath." End If patternarr = Split(LCase(patterns), "|")
' internally we want all filepaths to end with the folder separatorIf baseDir Like "*[!\/]" Then baseDir = baseDir & delim workq.put basedir
' while there are directories in the queue, process the first directory.Do Until workq.IsEmpty adir = workq.Get Erase files afile = Dir$(aDir & "*", Attr_hidden + Attr_system)
' all files but not directories.Do Until afile = "" files(afile) = True
' remember the names of the filesIf IsLikeAnyOf(LCase(aFile), patternarr) Then results = results & NEWLINE & adir & afile End If afile = Dir$ Loop
' now find the names of each subfolder.afile = Dir$(aDir, Attr_directory + attr_hidden) ' this will include files also Do Until afile = "" If afile <> "." And afile <> ".." Then If Not IsElement(files(afile)) Then
' this is a folder. Add it to work queue for processing on later iteration.workq.put adir & afile & delim End If End If afile = Dir$ Loop Loop FileSearch = Split(Mid$(results, 2), NEWLINE) End Function
%REM Function IsLikeAnyOf Description: Match a string against an array of patterns using the LIKE operator, returning TRUE if it matches any of them. %END REMFunction IsLikeAnyOf(a$, patterns) As Boolean ForAll aPattern In patterns If a Like aPattern Then IsLikeAnyOf = True Exit Function End If End ForAll End Function
Here’s sample code to call this function:
Sub Initialize Dim matches, pattern$, basepath$ pattern = "*.ns6|*.lss" basepath = "C:\notes" matches = FileSearch(basepath, pattern) MsgBox "Matches for " & pattern & " in " & basepath & ":" & NEWLINE & NEWLINE & Join(matches, NEWLINE), 0, "" End Sub
It’s good to think about the consequences of using different data structures in terms of the order in which work gets done. In this case, folders are processed in the order they are added to the queue. Think about the consequence of this for a sample folder structure:
As you scan folder “foods” you’ll add folders “meat” and “vegetables” to the queue for later. Next pass, you’ll process the “meat” folder and add to the queue its subfolder, “fish”. But you’re not going to process the “fish” subfolder right away because it’s at the end of the queue — “vegetables” will be processed first.
Let’s say each of these folders contains some matching files. The matches are reported in the order that the folders were processed, so that would be:
For this task, if you care about the order of the returned results, this probably isn’t what you want. You’d prefer all the files in a given folder to be grouped together with the files from its subfolders, so those last two should be switched.
Exercise for the reader: what data structure could be used instead of a queue to track the work and give the result in the desired order?
For VoltScript we’ve been working on various enhancements, using LotusScript as a base. Some are core language enhancements, some are LSXs and some are helper classes. Proper Collection and Map classes were an area we identified early on as one of our targets. We scoped it out after the Factory Tour in September, and we’ve had something working for a few weeks. One of the innovative approaches we took was to make the Collection class as generic Collection, Queue and Stack. I decided to try your use case against it, and I think the solution works quite nicely. I’ve blogged about it here https://paulswithers.github.io/blog/2022/12/13/directories-challenge.
Your other problem, with Dir() not being recursive, is one that coincidentally bit me a couple of weeks ago. We already have a first pass on an alternative approach, we’ll see how it works in internal use-cases (we have a number!).