stylewarning / big-string Goto Github PK

                              BIG-STRING
                              ==========

                           By Robert Smith


INTRODUCTION & USAGE
--------------------

BIG-STRING is a library for working with big strings. Despite the
name, BIG-STRING is also useful for general collections of strings. It
is very much like Java's StringBuilder class. Care has been taken to
make most operations linear in time at worst.

The usual trick to concatenate many strings together in (probably)
linear time is to use WITH-OUTPUT-TO-STRING:

CL-USER> (let ((strings '("this " "is " "a " "collection " "of " "strings.")))
           (with-output-to-string (*standard-output*)
             (dolist (string strings)
               (princ string))))
"this is a collection of strings."

Depending on how WITH-OUTPUT-TO-STRING is implemented, this might not
be linear, and could be inefficient (the standard makes no complexity
guarantee).

BIG-STRING encapsulates this idea in a data structure:

BIG-STRING> (let* ((strings '("this " "is " "a " "collection " "of " "strings."))
                   (bs (make-big-string)))
              (dolist (string strings bs)
                (big-string-append bs string)))
#<BIG-STRING of 32 characters {10074D6AD3}>

We can convert this into a string in guaranteed linear time:

BIG-STRING> (string-of-big-string *)
"this is a collection of strings."

It is possble to do an analogous operation by creating a new string
stream using MAKE-STRING-OUTPUT-STRING, writing to the resulting
stream, and the obtaining the string using GET-OUTPUT-STREAM-STRING.

In a sense, we are building a string lazily. But more interestingly,
we can operate on it as if itself was a string.

BIG-STRING> (list (big-string-length **)
                  (big-string-char ** 10)
                  (big-string-substring ** 8 20))
(32 #\c "a collection")


LIMITATIONS
-----------

Right now, a few operations are slightly inefficient. Also, some more
string-like functions should be implemented.

The implementation right now takes about twice the time than SBCL
takes with string streams. However, with some type tweaking,
BIG-STRING goes at the same speed or faster, with about half the
memory.