The big-string Reference Manual

Table of Contents

The big-string Reference Manual

This is the big-string Reference Manual, generated automatically by Declt version 3.0 "Montgomery Scott" on Mon Apr 19 14:11:17 2021 GMT+0.

1 Introduction

                              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)))
#

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.

2 Systems

The main system appears first, followed by any subsystem dependency.

2.1 big-string

Author

Robert Smith <quad@symbo1ics.com>

License

BSD 3-clause (see LICENSE)

Description

Big strings, similar to Java’s StringBuilder.

Source

big-string.asd (file)

Components

• package.lisp (file)
• big-string.lisp (file)

3 Files

Files are sorted by type and then listed depth-first from the systems components trees.

3.1 Lisp

3.1.1 big-string.asd

Location

big-string.asd

Systems

big-string (system)

3.1.2 big-string/package.lisp

Parent

big-string (system)

Location

package.lisp

Packages

big-string

3.1.3 big-string/big-string.lisp

Dependency

package.lisp (file)

Parent

big-string (system)

Location

big-string.lisp

Exported Definitions

• big-string (structure)
• big-string-append (function)
• big-string-char (function)
• big-string-length (function)
• big-string-p (function)
• big-string-substring (function)
• copy-big-string (function)
• make-big-string (function)
• string-of-big-string (function)

Internal Definitions

• array-size (type)
• big-string-cumulative-lengths (function)
• (setf big-string-cumulative-lengths) (function)
• big-string-size (type)
• big-string-strings (function)
• (setf big-string-strings) (function)
• big-string-tracked-length (function)
• (setf big-string-tracked-length) (function)
• binary-search (function)

4 Packages

Packages are listed by definition order.

4.1 big-string

Source

package.lisp (file)

Use List

common-lisp

Exported Definitions

• big-string (structure)
• big-string-append (function)
• big-string-char (function)
• big-string-length (function)
• big-string-p (function)
• big-string-substring (function)
• copy-big-string (function)
• make-big-string (function)
• string-of-big-string (function)

Internal Definitions

• array-size (type)
• big-string-cumulative-lengths (function)
• (setf big-string-cumulative-lengths) (function)
• big-string-size (type)
• big-string-strings (function)
• (setf big-string-strings) (function)
• big-string-tracked-length (function)
• (setf big-string-tracked-length) (function)
• binary-search (function)

5 Definitions

Definitions are sorted by export status, category, package, and then by lexicographic order.

5.1 Exported definitions

5.1.1 Functions

Function: big-string-append BS STRING

Destructively append the string STRING to the big string BS.

Time complexity: O(1) [amortized]

Package

big-string

Source

big-string.lisp (file)

Function: big-string-char BS N

Find the Nth char in the big string BS.

Time complexity: O(log n)

Package

big-string

Source

big-string.lisp (file)

Function: big-string-length BS

Return the total length of the big string BS.

Time complexity: O(1)

Package

big-string

Source

big-string.lisp (file)

Function: big-string-p OBJECT

Package

big-string

Source

big-string.lisp (file)

Function: big-string-substring BS START &optional END

Compute the substring from the big string BS from the index START to before the index END.

Time complexity: with n = end - start, O(n log n)

Package

big-string

Source

big-string.lisp (file)

Function: copy-big-string INSTANCE

Package

big-string

Source

big-string.lisp (file)

Function: make-big-string ()

Package

big-string

Source

big-string.lisp (file)

Function: string-of-big-string BS

Build a string from the big string BS.

Time complexity: O(size(bs))

Package

big-string

Source

big-string.lisp (file)

5.1.2 Structures

Structure: big-string ()

Package

big-string

Source

big-string.lisp (file)

Direct superclasses

structure-object (structure)

Direct methods

print-object (method)

Direct slots

Slot: tracked-length

Type

big-string::big-string-size

Initform

0

Readers

big-string-tracked-length (function)

Writers

(setf big-string-tracked-length) (function)

Slot: cumulative-lengths

Type

(and (vector big-string::big-string-size) (not simple-array))

Initform

(make-array 10 :element-type (quote big-string::big-string-size) :initial-element 0 :adjustable t :fill-pointer 0)

Readers

big-string-cumulative-lengths (function)

Writers

(setf big-string-cumulative-lengths) (function)

Slot: strings

Type

(and (vector simple-string) (not simple-array))

Initform

(make-array 10 :element-type (quote simple-string) :initial-element "" :adjustable t :fill-pointer 0)

Readers

big-string-strings (function)

Writers

(setf big-string-strings) (function)

5.2 Internal definitions

5.2.1 Functions

Function: big-string-cumulative-lengths INSTANCE

Function: (setf big-string-cumulative-lengths) VALUE INSTANCE

Package

big-string

Source

big-string.lisp (file)

Function: big-string-strings INSTANCE

Function: (setf big-string-strings) VALUE INSTANCE

Package

big-string

Source

big-string.lisp (file)

Function: big-string-tracked-length INSTANCE

Function: (setf big-string-tracked-length) VALUE INSTANCE

Package

big-string

Source

big-string.lisp (file)

Function: binary-search N ARRAY

Find the least value in the array ARRAY greater than N. Return NIL if N is negative or no such number is found.

Package

big-string

Source

big-string.lisp (file)

5.2.2 Types

Type: array-size ()

Possible size of an array.

Package

big-string

Source

big-string.lisp (file)

Type: big-string-size ()

Possible size of a big string.

Package

big-string

Source

big-string.lisp (file)

Appendix A Indexes

A.1 Concepts

A.2 Functions

A.3 Variables

A.4 Data types