LotusScript Data Structures Basics

There’s a bit of intro here that most of your Notes Buccaneers won’t need, so skip ahead to the LotusScript specific stuff.

What are these data structures of which you speak?

In computer science, the term “data structure” refers to a way of organizing data into an arrangement you can navigate in specific ways, depending on the needs of your application.

At its most basic, you have a record, with pairs of names and values associated with those names.

An array is a simple data structure. It’s a generally fixed-size collection of similar elements you can navigate by a numeric index.

An associative array, represented by the List datatype in LotusScript, is another data structure which you can navigate either by key values, or by iterating through it in some order. Behind the scenes, the efficient implementation of an associative arrays involves hash values, internal lists, and the like, the details of which are hidden from you in this case.

Another useful data structure is the queue, whose behavior is described as “first in, first out.” You “put” records in at one end, and when you “get” a record, you get the oldest one, simultaneously removing it from the queue. When I was growing up on a farm, we had a cattle queue for branding, medicating and so on. It was too narrow for the cattle to pass each other, so they got their treatment in the same order we put them in the other end.

Then there’s the stack, which resembles the spring-loaded stacks of plates at a buffet. They’re loaded from the top, and you can only take from the top (unless you’re a savage who cheats and slips one out from further down).

Speaking of cheating, all the basic data structures can of course be modified, elaborated on. You can have a queue with a cutting in line feature so high-priority items are processed sooner. You can have a stack that lets you peek at the top value and (like a savage) save it for later and pull out the second value instead. Whatever your application requires. But the basic data structures are your starting point. So let’s talk about how to implement them in LotusScript.

How does this relate to LotusScript?

There are LotusScript implementations of the basic data structures in the LotusScript Gold Collection project on openntf.org. You can just take those and use them. But as noted above, often you need to modify the “classic” data structures for your specific requirements, or even create entirely new, specialized stuff. So I want to discuss the basic principles.

Let’s start with records. There are two main ways to represent record information in LotusScript: as a Type or as a Class. Either lets you define a group of named variables which travel together. I rarely use types. A class is generally better — more flexible, easier to pass around as parameters and include in data structures, and also contains the logic to manage the data it stores, making that logic easy to find and maintain.

Classes are the LotusScript implementation of object-oriented design. When I say “object” I’m referring to one instance of a class. The class can be thought of as the datatype of a record, and the object is a variable of that type.

Reference counter

Objects are never copied, unless you create a method to explicitly copy them. There’s one instance of the object and you store and pass around pointers to it. So any given object might be referenced from various places — let’s say it’s in an array, and you iterate through the array assigning each object into a temporary variable.

Function DocGroupSummary(zydocs() As NotesDocument) As String
	Dim i%, doc As NotesDocument
	For i = LBound(zydocs) To UBound(zydocs)
		Set doc = zydocs(i)
		' do stuff with doc
	Next
End Function

I’m using the built-in class NotesDocument here. The variable doc contains a pointer to a document object floating around out there in memory. The array zydocs contains a pointer to that same document in one of its elements. If you change the contents of the object referred to by doc — say you assign an item value — you’re also changing the document stored in zydocs, because both these values point to the same object.

Why is this important when working with data structures? LotusScript stores a “reference counter” in each object keeping track of how many variables have pointers to that object. When you assign doc to point to an object, that object’s counter is incremented. When you change doc to point to the next document in the array, the previous object’s counter is decremented. When the counter drops to zero, there’s no longer any variable containing a pointer to that object — it’s orphaned. So LotusScript deletes it, freeing that memory.

Ideally, this should just work. But the reference counting mechanism isn’t perfect. In particular, it can’t detect loops of objects that point to each other — or objects that point to themselves, for that matter. If you aren’t aware of how reference counting works and accounting for it, you can easily leave inaccessible islands of objects that can’t be deallocated because they all have something pointing to them.

They’ll eventually be freed when the script execution finishes, but meanwhile if you’re processing a lot of data during a single execution, they can accumulate and use up all your memory, preventing your script from completing successfully.

That’s why, when you have a data structure that involves links between objects, it”s best to have a Delete method defined in the class to navigate the structure and explicitly delete all the data when the containing object is deleted. You can see an example of this in the ObjectListLite class in LotusScript Gold Collection.

Remember: when you use Delete on an object, or the last pointer to it goes away, the object itself is deleted, but if it contains pointers to other objects, like a bunch of linked list nodes, those will only be automatically deleted if they aren’t pointing to each other.

Document caching

The NotesDocument object is a special in that it remains “cached” in memory in circumstances where other objects would be garbage collected. This is intended to improve performance, but it can also cause problems. Say the document contains unsaved changes. You might think that exiting the subroutine that contains the NotesDocument object without having saved those changes is enough to get rid of them. But the cached document might be retrieved again, with the unsaved changes still in it, which you might then save without realizing it in the process of saving other item changes that you do want. Or you might have originally retrieved it from one view collection, so the cached document’s ParentView property could be pointing to the wrong view when you later retrieve it from a different view.

Point is, if in doubt explicitly delete NotesDocument objects when you’re done with them. For this use the Delete statement:

Delete doc ' clears the variable and also removes the cache.

Merely reassigning the variable is not effective.

Set doc = Nothing ' Decrements reference counter but doesn't erase cache.

Typed Collections

Some languages have the ability to define a generic data structure class and then create instances associated with a particular type of contained object — for instance Java contains a built-in Queue<Typename> “Interface”, so if you want a queue whose members are strings, you can write:

import java.util.*;
...
Queue<String> strque = new LinkedList<>();

and the members of the queue are limited to the string type — or whatever type you specified inside the angle brackets.

LotusScript doesn’t have a corresponding feature. The best we can do is use Variant datatypes for the contained data, and the caller must then exercise discipline to make sure it’s using a consistent datatype for the contents. Alternately, you can write type-specific versions of your data structure classes, e.g. QueueOfString, but you have to separately write each one. You can use inheritance to reuse most of the code, but it’s a little complicated to do that in a way the compiler can check as opposed to just throwing runtime type mismatch errors.

Where to find prewritten versions of “classic” data structures

The LotusScript Gold Collection contains some of them, but check back here. I plan to publish implementations of some common ones. Also check the comments — there are probably existing ones I don’t know about, but maybe others do.