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.