The big-string Reference Manual

Table of Contents

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

The big-string Reference Manual

This is the big-string Reference Manual, generated automatically by Declt version 2.4 "Will Decker" on Wed Jun 20 10:48:44 2018 GMT+0.


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

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.

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

2 Systems

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


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

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

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

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 files   [Contents][Index]

3.1.1 big-string.asd

Location

big-string.asd

Systems

big-string (system)


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

3.1.2 big-string/package.lisp

Parent

big-string (system)

Location

package.lisp

Packages

big-string


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

3.1.3 big-string/big-string.lisp

Dependency

package.lisp (file)

Parent

big-string (system)

Location

big-string.lisp

Exported Definitions
Internal Definitions

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

4 Packages

Packages are listed by definition order.


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

4.1 big-string

Source

package.lisp (file)

Use List

common-lisp

Exported Definitions
Internal Definitions

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

5 Definitions

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


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

5.1 Exported definitions


Next: , Previous: , Up: Exported definitions   [Contents][Index]

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)


Previous: , Up: Exported definitions   [Contents][Index]

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)


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

5.2 Internal definitions


Next: , Previous: , Up: Internal definitions   [Contents][Index]

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)


Previous: , Up: Internal definitions   [Contents][Index]

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)


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

Appendix A Indexes


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

A.1 Concepts

Jump to:   B   F   L  
Index Entry  Section

B
big-string.asd: The big-string<dot>asd file
big-string/big-string.lisp: The big-string/big-string<dot>lisp file
big-string/package.lisp: The big-string/package<dot>lisp file

F
File, Lisp, big-string.asd: The big-string<dot>asd file
File, Lisp, big-string/big-string.lisp: The big-string/big-string<dot>lisp file
File, Lisp, big-string/package.lisp: The big-string/package<dot>lisp file

L
Lisp File, big-string.asd: The big-string<dot>asd file
Lisp File, big-string/big-string.lisp: The big-string/big-string<dot>lisp file
Lisp File, big-string/package.lisp: The big-string/package<dot>lisp file

Jump to:   B   F   L  

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

A.2 Functions

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

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

B
big-string-append: Exported functions
big-string-char: Exported functions
big-string-cumulative-lengths: Internal functions
big-string-length: Exported functions
big-string-p: Exported functions
big-string-strings: Internal functions
big-string-substring: Exported functions
big-string-tracked-length: Internal functions
binary-search: Internal functions

C
copy-big-string: Exported functions

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

M
make-big-string: Exported functions

S
string-of-big-string: Exported functions

Jump to:   (  
B   C   F   M   S  

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

A.3 Variables

Jump to:   C   S   T  
Index Entry  Section

C
cumulative-lengths: Exported structures

S
Slot, cumulative-lengths: Exported structures
Slot, strings: Exported structures
Slot, tracked-length: Exported structures
strings: Exported structures

T
tracked-length: Exported structures

Jump to:   C   S   T  

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

A.4 Data types

Jump to:   A   B   P   S   T  
Index Entry  Section

A
array-size: Internal types

B
big-string: The big-string system
big-string: The big-string package
big-string: Exported structures
big-string-size: Internal types

P
Package, big-string: The big-string package

S
Structure, big-string: Exported structures
System, big-string: The big-string system

T
Type, array-size: Internal types
Type, big-string-size: Internal types

Jump to:   A   B   P   S   T