LotusScript Queue data structure

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.

Specification

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.

Implementation notes

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.

Delete Method

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.

Code

%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 REM
Class 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 REM
	Sub 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 REM
	Function 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 REM
Private 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

Example code

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 REM
Function 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 path
	ElseIf basedir Like "\*" Or basedir Like "[A-Z]:\*" Then
		delim = "\" ' windows style path
	Else
		Error 20030, "FileSearch needs an absolute filepath."
	End If
	
	patternarr = Split(LCase(patterns), "|")
	' internally we want all filepaths to end with the folder separator
	If 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 files
			If 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 REM
Function 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

Final thoughts

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:

• /foods
• /foods/meat
• /foods/vegetables
• /foods/meat/fish

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?