CL-Containers User's Guide

Introduction

Common Lisp ships with a set of powerful built in data structures including the venerable list, full featured arrays, and hash-tables. The Common Lisp Container Library enhances and builds on these structures in two ways:

By adding containers that are not available in native Lisp (for example: binary search trees, red-black trees, sparse arrays and so on).
By standardizing the container interface so that they are simpler to use and so that changing design decisions becomes significantly easier.

The containers in can be divided into three storage types: Ordered, Unordered and Associative.

Ordered containers store things in (some) order. The order may be based on how items were inserted into the container or it may depend on an explicit sorting.
Unordered containers also store things and share much of Ordered containers interface. However, the items in an Unordered container do not maintain any particular arrangement.
Associative containers store items associated with some index or key. The key may be simple (for example, a one-dimensional array indexed by an integer) or complex (for example, a nested hash table indexed by color, size and object class).

The way containers store their contents provides another view in 's design: containers may store their contents directly (think of a list) or they may wrap each element within some data-structure -- a node -- that helps the container keep track of what is going on (think of a binary tree). We'll see many examples of both styles below.

There are many other mixins that combine to produce generic container behavior. For example, a bounded-container-mixin starts at some fixed size and cannot grow beyond it whereas a keyed-container-mixin provide a key function that is used by other container functions (e.g., sort-container) to modify their behavior.

Terminology

Containers store elements. Sometimes the elements are wrapped in nodes. We can insert, delete, search-for, find, iterate, and collect both elements and nodes from a container. We can also look at the size of a container, see it is empty (with emptyp) and empty it (with empty!). Ordered containers also let us find the first, last and nth element (or node) and they may let us sort or reverse the contents as a whole. Associative containers provide the ability to look at keys and elements (or, sometimes, values). We can collect and iterate either one of these or both simultaneously. Finally, certain specialized container classes provide synonyms for their usual operations. For example, you can still pop and push into a stack-container.

Using a container

Creating and inspecting

Containers can be created with or make-container. The latter is exactly the same as the former unless dynamic-classes is also loaded. In this case, make-container can take a list of superclasses and will find or create a container class to match.

Creates a new container of type class using the additional arguments (args).

Though specific container classes add to this list, every container shares a set of common operations:

Returns the number of items currently in the container.

Removes all items from the container and returns nil.

Empty a queue of all contents.

Returns t if there are no items in the container.

Container nodes (i.e., instances of type container-node-mixin) also share a set of operations:

General use: adding, deleting, finding

Adding

Deleting

Getting

No documentation found

Returns the nth element in the container's 'natural' order.

Returns the item specified by the indexes.

Specialized

These operations are essentially synonyms for the generic container methods. They are included to make working with queues and stacks feel more natural.

Some and Every

Returns the first item in the container for which predicate holds. Predicate should be a function of one argument for iteratable containers and a function of two arguments for associative containers.

Returns true if every item in the container satisfies the predicate. Predicate should be a function of one argument for iteratable containers and a function of two arguments for associative containers.

Counting, Collecting, and Canvasing

Once you have a container, it is very common to want to map some function over its contents or to want to collect its contents for some other purpose. The following functions support these desires.

Applies function to each node in the container. If the container doesn't have nodes, then this is equivalent to iterate-elements.

Returns a possibly filtered and possibly transformed list of the nodes in a container. If the container uses nodes, then the items are the nodes. If not, collect-nodes is equivalent to collect-elements.

Returns a possibly filtered and possibly transformed list of the elements in a container. If the container uses nodes, then the elements are the things 'in' the nodes. Warning: it is possible for the result to share structure with the original container.

Collects the keys of a container into a list.

The filter and transform arguments should be nil or functions of one argument. If filter is non-nil, then the list returned will contain only keys that return true. If transform is non-nil, then it will be applied to each key that passes the filter.

If the list begins with an atom, then it is treated as a property list; otherwise, it is treated as an associative-list.

Iterate over the keys and values of the container and return a list of the ones that pass the filter function transformed by the transform function.

Finding and Searching

Find item in container using the container's test method for comparisons. The test method must take two parameters. The first will be the item being searched for; the second will be an item in the container. If the container has a key (keyed-container-mixin), then the test is performed on the item and the key of each element in the container. Find-item returns nil if the item is not found and it returns the element in the container if it is.

Find node containing thing in container using the container's test method for comparisons. The test method must take two parameters. The first will be the item being searched for; the second will be an item in the container. If the container has a key (keyed-container-mixin), then the test is performed on the item and the key of each element in the container. Find-item returns nil if the thing is not found and it returns the node in the container if it is. Find-node is the same as find-element for containers that do not use nodes.

For now, compare find-item.

Miscellaneous

Container taxonomy

package-container abstract-tree-container rooted-tree-container quad-tree binary-search-tree splay-tree red-black-tree vector-container-mixin many-ordered-child-node basic-vector-container vector-container heap-container k-best-heap-container flexible-vector-container bounded-vector-container uses-contents-mixin abstract-bag/set-container set-container bag-container stack-container alist-container array-container-abstract array-container contents-as-hashtable-mixin union-find-container bag/set-container keyed-bag/set-container associative-container keyed-associative-container simple-associative-container sparse-array-container contents-as-array-mixin contents-as-sequence-mixin contents-as-list-mixin many-unordered-child-node list-container sorted-list-container non-associative-container-mixin cl-graph:graph-container cl-graph:dot-graph ordered-container-mixin dlist-container sorted-dlist-container abstract-stack abstract-queue ring-buffer basic-queue priority-queue-on-container classified-container-mixin sorted-container-mixin unordered-container-mixin searchable-container-mixin iteratable-container-mixin forward-iterator delimited-iterator line-iterator word-iterator basic-stream-iterator file-form-iterator file-line-iterator file-iterator basic-generator arithmetic-sequence-generator finite-arithmetic-sequence-generator array-iterator list-iterator hash-table-iterator many-child-node stable-associative-container key-value-iteratable-container-mixin findable-container-mixin container-uses-nodes-mixin basic-initial-contents-mixin initial-contents-key-value-mixin associative-container-mixin biassociative-container-mixin initial-contents-mixin initial-element-mixin indexed-container-mixin bounded-container-mixin typed-container-mixin keyed-container-mixin)

basic-iterator> # # # # # # # # # # # # # # # )

Iterators

CL-Containers includes a set of classes to implement forward iterators and simple generators (where the latter is a sort of infinite instance of the former).

To iterate, you create an iterator on a container and then move forward until the iterator is exhausted.

Creating an iterator

Tell Lisp that you are done with this iterator. Further calls to current-element, etc. will have unspecified behavior and may cause an error.

Using an iterator