The ROPE type is the preferred way of representing immutable sequences of characters, and has proven to be very successful. This package provides the analogous data type where the base types are of type REF ANY. The fundamental operations on objects of this type are concatenation, substring extraction, and fetching the values by index. Additional operations are provided for more efficient sequential creation and scanning of the objects.

The client interface is called Rosary.mesa, and the basic data type is ROSARY. The Segment type is used to refer to part of a ROSARY without doing the extra work associated with substring extraction.

The Rosary implementation provides a print procedure to the Cedar system, so that when you print a value of type ROSARY in the interpreter or with PutF, it will be displayed in the form

The basic operations are Size, Fetch, FromItem, Substr, and Concat. These are analogous to their counterparts in Rope.

Cat is a convenience for concatenating multiple ROSARYs together.

CatSegments provides a way of concatenating up to three segments to obtain a new ROSARY.

FromProc is analogous to Rope.FromProc.

FromProcProc is a more convoluted way of creating a ROSARY, but is often applicable where FromProc is not. It uses a double callback mechanism, where the client passes in a procedure p; the package calls p back, handing it a procedure q, and then p calls q once for each item. If this seems confusing, don't be discouraged, because it is. The implementation of FromList may make it all clear:

Map is analogous to Rope.Map, and MapRuns may be used where it is expected that repeated items will occur frequently. MapRuns does not promise to collapse adjacent runs for you, merely to take advantage of any encoded runs that occur in the data structure. FetchRun may be used to obtain a single, uncollapsed run.

FetchBuffer may be used to get a buffer-full of consecutive entries out of a ROSARY; this is especially useful when more than one ROSARY are being traversed in parallel, where Map is unusable. For example:

FromList and ToList are conversion procedures between the types ROSARY and LIST OF REF.

FromObject provides a way of creating a ROSARY with a non-standard implementation. To do this, the client provides a procedure for mapping the runs of the rosary object, along with the size and any data it needs. The client may also provide a substr procedure for implementing the substring operation; if this is omitted, a default one will be provided. As an example, consider the following lazy-reverse routine:

The underlying representation of a ROSARY is a binary tree. The implementation tries to create trees that are not too high, so that excessive stack space is not used when traversing them. Unlike the ROPE representation, there is no substr node; this is done to guarantee that a ROSARY points only to the REFs that it contains. Thus the Substr operation needs to pick apart the subtrees it should contain, and glue them together with concat nodes. All of this work is actually done in CatSegments; Concat is lazier and only rebalances when necessary to keep the maximum height from being exceeded.

There is a compact representation provided for adjacent elements that are all equal, so ROSARYs that tend to have lots of runs will be more compact.

Neglecting the run encodings, a ROSARY takes between 2 and 3 times as much storage as the equivalent LIST OF REF, not counting the storage for the elements. The time to create a ROSARY using FromProcProc is roughly twice the time to create a LIST OF REF using CONS (when the elements are already allocated). The traversal time using Map is about 8 times slower than running through a list, neglecting the time spent processing each element. The random access time is, of course, much faster, growing as the height of the ROSARY rather than as its size.