The big-string Reference Manual

Next: , Previous: , Up: (dir)   [Contents][Index]

The big-string Reference Manual

This is the big-string Reference Manual, generated automatically by Declt version 4.0 beta 2 "William Riker" on Thu Sep 15 03:20:07 2022 GMT+0.

Table of Contents


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.


Previous: , Up: Systems   [Contents][Index]

2.1 big-string

Big strings, similar to Java’s StringBuilder.

Author

Robert Smith <quad@symbo1ics.com>

License

BSD 3-clause (see LICENSE)

Source

big-string.asd.

Child Components

3 Files

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


Previous: , Up: Files   [Contents][Index]

3.1 Lisp


Next: , Previous: , Up: Lisp   [Contents][Index]

3.1.1 big-string/big-string.asd

Source

big-string.asd.

Parent Component

big-string (system).

ASDF Systems

big-string.


3.1.2 big-string/package.lisp

Source

big-string.asd.

Parent Component

big-string (system).

Packages

big-string.


3.1.3 big-string/big-string.lisp

Dependency

package.lisp (file).

Source

big-string.asd.

Parent Component

big-string (system).

Public Interface
Internals

4 Packages

Packages are listed by definition order.


Previous: , Up: Packages   [Contents][Index]

4.1 big-string

Source

package.lisp.

Use List

common-lisp.

Public Interface
Internals

5 Definitions

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


Next: , Previous: , Up: Definitions   [Contents][Index]

5.1 Public Interface


5.1.1 Ordinary 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.

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.

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.

Function: big-string-p (object)
Package

big-string.

Source

big-string.lisp.

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.

Function: copy-big-string (instance)
Package

big-string.

Source

big-string.lisp.

Function: make-big-string ()
Package

big-string.

Source

big-string.lisp.

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.


5.1.2 Standalone methods

Method: print-object ((object big-string) stream)
Source

big-string.lisp.


5.1.3 Structures

Structure: big-string
Package

big-string.

Source

big-string.lisp.

Direct superclasses

structure-object.

Direct methods

print-object.

Direct slots
Slot: tracked-length
Type

big-string::big-string-size

Initform

0

Readers

big-string-tracked-length.

Writers

(setf big-string-tracked-length).

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.

Writers

(setf big-string-cumulative-lengths).

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.

Writers

(setf big-string-strings).


5.2 Internals


Next: , Previous: , Up: Internals   [Contents][Index]

5.2.1 Ordinary functions

Reader: big-string-cumulative-lengths (instance)
Writer: (setf big-string-cumulative-lengths) (instance)
Package

big-string.

Source

big-string.lisp.

Target Slot

cumulative-lengths.

Reader: big-string-strings (instance)
Writer: (setf big-string-strings) (instance)
Package

big-string.

Source

big-string.lisp.

Target Slot

strings.

Reader: big-string-tracked-length (instance)
Writer: (setf big-string-tracked-length) (instance)
Package

big-string.

Source

big-string.lisp.

Target Slot

tracked-length.

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.


5.2.2 Types

Type: array-size ()

Possible size of an array.

Package

big-string.

Source

big-string.lisp.

Type: big-string-size ()

Possible size of a big string.

Package

big-string.

Source

big-string.lisp.


Appendix A Indexes


Next: , Previous: , Up: Indexes   [Contents][Index]

A.1 Concepts


Next: , Previous: , Up: Indexes   [Contents][Index]

A.2 Functions

Jump to:   (  
B   C   F   M   P   S  
Index Entry  Section

(
(setf big-string-cumulative-lengths): Private ordinary functions
(setf big-string-strings): Private ordinary functions
(setf big-string-tracked-length): Private ordinary functions

B
big-string-append: Public ordinary functions
big-string-char: Public ordinary functions
big-string-cumulative-lengths: Private ordinary functions
big-string-length: Public ordinary functions
big-string-p: Public ordinary functions
big-string-strings: Private ordinary functions
big-string-substring: Public ordinary functions
big-string-tracked-length: Private ordinary functions
binary-search: Private ordinary functions

C
copy-big-string: Public ordinary functions

F
Function, (setf big-string-cumulative-lengths): Private ordinary functions
Function, (setf big-string-strings): Private ordinary functions
Function, (setf big-string-tracked-length): Private ordinary functions
Function, big-string-append: Public ordinary functions
Function, big-string-char: Public ordinary functions
Function, big-string-cumulative-lengths: Private ordinary functions
Function, big-string-length: Public ordinary functions
Function, big-string-p: Public ordinary functions
Function, big-string-strings: Private ordinary functions
Function, big-string-substring: Public ordinary functions
Function, big-string-tracked-length: Private ordinary functions
Function, binary-search: Private ordinary functions
Function, copy-big-string: Public ordinary functions
Function, make-big-string: Public ordinary functions
Function, string-of-big-string: Public ordinary functions

M
make-big-string: Public ordinary functions
Method, print-object: Public standalone methods

P
print-object: Public standalone methods

S
string-of-big-string: Public ordinary functions

Jump to:   (  
B   C   F   M   P   S