Returns true iff the seq is empty. O(1).
Returns the number of elements in the map. O(1).
Returns true iff s is a char seq, i.e., it contains only characters and is not empty.
If idx is an integer in [0 .. size(s)], returns two values: the element at that
position, and true. Otherwise, returns the seq’s default and false; if
the seq has no default, signals an error of type seq-bounds-error. O(log n).
For seqs, at-index is synonymous with lookup.
setf Expander: setf lookup (seq) s idx v ¶Invoked as (setf (lookup s idx) v). Updates the place s (which must
be setf-able) to have v at idx. Equivalent to (setf s (with s
idx v)), except that subexpressions within s are evaluated only once.
You can also write (setf (@ s idx) v). See The @ Macro.
If the seq has a default, returns it and a true second value; otherwise, returns nil and
false. O(1).
Returns a new seq that has all the pairs of s, but whose default is new-default. O(1).
setf Expander: default s new-default ¶(setf (default s) new-default) is equivalent to (setf s (with-default
s new-default)), except that subexpressions within s are evaluated only once.
Returns a new seq that has all the pairs of s, but has no default. O(1).
(clear-default s) is equivalent to (setf s (without-default s)),
except that subexpressions within s are evaluated only once.
If s is nonempty, returns its first element, that is, the one at index 0, and a true second
value. Otherwise, returns the seq’s default and false; if the seq has
no default, signals an error of type empty-seq-error. O(1).
Returns a new seq of size one greater than that of s, with x inserted at index 0. O(log n), but with a relatively small constant factor, since it usually doesn’t require walking the tree.
A modify macro that expands to with-first. Assuming place
s (which must be setf-able) holds a seq, updates s by inserting x at index
0.
If s is nonempty, returns a new seq of size one less than that of s, with the element at
index 0 removed. Otherwise, returns the seq’s default and false; if
the seq has no default, signals an error of type empty-seq-error. O(log n), but with a
relatively small constant factor, since it usually doesn’t require walking the tree.
A quasi-mutating macro. if place s (which must be
setf-able) holds a nonempty seq, returns its first element after updating s by removing
that element. If s holds an empty seq, returns the seq’s default; if the seq has no default, signals an error of type empty-seq-error.
If s is nonempty, returns its last element, that is, the one at index size(s) - 1, and a
true second value. Otherwise, returns the seq’s default and false; if
the seq has no default, signals an error of type empty-seq-error. O(1). See first and last.
Returns a new seq of size one greater than that of s, with x inserted after the last element (i.e., at index size(s)). O(log n), but with a relatively small constant factor, since it usually doesn’t require walking the tree.
A modify macro that expands to with-last. Assuming place
s (which must be setf-able) holds a seq, updates s by inserting x after the
last element.
If s is nonempty, returns a new seq of size one less than that of s, with the element at
index 0 removed. Otherwise, returns the seq’s default and false; if
the seq has no default, signals an error of type empty-seq-error. O(log n), but with a
relatively small constant factor, since it usually doesn’t require walking the tree.
A quasi-mutating macro. if place s (which must be
setf-able) holds a nonempty seq, returns its last element after updating s by removing
that element. If s holds an empty seq, returns the seq’s default; if the seq has no default, signals an error of type empty-seq-error.
If idx is in [0 .. size(s)), returns a new seq which contains x at position
idx. If idx is -1, equivalent to (with-first s x); if idx is
size(s), equivalent to (with-last s x).
If idx < -1 or > size(s), and s has a default, inserts as many repetitions of the
default as needed to reach idx, then inserts x. That is, if idx < -1, inserts
x followed by (-1 - idx) repetitions of the default at the beginning; if idx >
size(s), inserts (idx - size(s)) repetitions of the default followed by x at
the end. If s has no default, signals an error of type seq-bounds-error.
O(log n).
If idx is in [0 .. size(s)), returns a new seq with the element at position idx removed. Otherwise, returns s.
O(log n)
If idx is in [0 .. size(s)), returns a new seq which contains x inserted just
before position idx. If idx is 0, equivalent to (with-first s x);
if idx is size(s), equivalent to (with-last s x).
If idx < 0 or > size(s), and s has a default, inserts as many repetitions of the
default as needed to reach idx, then inserts x. That is, if idx < 0, inserts
x followed by (-idx) repetitions of the default at the beginning; if idx >
size(s), inserts (idx - size(s)) repetitions of the default followed by x at
the end. If s has no default, signals an error of type seq-bounds-error.
O(log n).
(For most of FSet’s existence, this has been called insert, but I recently decided that name
is too suggestive of mutation, and have deprecated it in favor of inserted.)
Returns the subsequence of s on the interval [start .. end). end defaults to size(s). Out-of-bounds values for start and end are silently adjusted to the nearest correct bound.
O(log n).
The first argument must be a seq, but the remainder can be any type that can be converted to a seq. Returns the concatenation of the arguments in the order given.
O(log n) on two seqs; if conversions are required, they will generally take O(n) time.
If idx is in [0 .. size(s)), returns a new seq which contains the elements of
subseq inserted just before position idx. If idx is 0, equivalent to
(concat subseq s); if idx is size(s), equivalent to (concat
s subseq).
If idx < 0 or > size(s), and s has a default, inserts as many repetitions of the
default as needed to reach idx, then splices in subseq. That is, if idx < 0,
inserts the elements of subseq followed by (-idx) repetitions of the default at the
beginning; if idx > size(s), inserts (idx - size(s)) repetitions of the
default followed by the elements of subseq at the end. If s has no default, signals an
error of type seq-bounds-error.
O(log n).
(For most of FSet’s existence, this has been called splice, but I recently decided that name
is too suggestive of mutation, and have deprecated it in favor of spliced.)
Returns the reversal of the seq. O(n).
Returns a seq of the same size as s, with the elements sorted by pred, which must be a
function of two arguments that implements a
strict weak ordering (of
which a total ordering is a special case). If pred, invoked on A and B, returns true, that
means that A is to appear before B in the result. There may be pairs A and B such that pred
returns false on both (A, B) and (B, A) (this is the meaning of “weak ordering”); such pairs are
called “incomparable”. sort does not guarantee to maintain the ordering of incomparable
elements; stable-sort keeps them in the same order, relative to one another that they were
in in s.
If key is supplied, it is invoked on each element and the resulting value passed to pred in its place.
These functions have the same interface as cl:sort and cl:stable-sort, so that you can
shadow those names with them (see Operations on CL Types). Therefore pred can’t be a
function like compare that uses the FSet comparison function protocol, returning one of
:less, :equal, :greater, or :unequal; you’ll need to wrap such a
function to use it, e.g.:
(sort s (lambda (x y) (eq (compare x y) ':less)))
O(n log n), assuming pred and key are O(1).
Returns a set of the valid indices of s, that is, the integers in [0 .. size(s)). O(n).
Returns true iff idx is an integer in [0 .. size(s)].
Returns true iff s contains x at any index. The comparison is done with equal?.
O(n) (requires a linear search). (Use whichever name you prefer.)
Returns the elements of s, as a set. O(n log n).
(Deprecated. I recommend using a conversion instead,
e.g. (convert 'set s), as this gives you a way to specify the type and organization of the
set if you wish to.)
For each element of seq, possibly restricted by start and end, and in reverse
order if from-end? is true, binds var to it and executes body. If index is
supplied, it names a variable that will be bound at each iteration to the index of the current
element of seq. When done, returns value if supplied, else nil.
Returns a stateful iterator over the seq s, possibly restricted by
start and end, and in reverse order if from-end? is true. The :get
operation returns two values: if there is another element remaining, returns it and a true second
value, else nil and false. Creating an iterator takes O(log n) time; the :get
operation is amortized O(1).
Returns a functional iterator over the seq, possibly restricted by
start and end, and in reverse order if from-end? is true. The :first
operation returns two values: if the iterator is not empty, returns the first element and a true
second value, else nil and false. Creating an iterator takes O(log n) time; the
:first operation is O(1), and :rest is amortized O(1).
Returns a new seq containing only those elements of s that satisfy pred, in the same order in which they appear in s. pred must be a function, an fbound symbol, or a boolean-valued map. O(n ⋅ tc(pred)) + O(r log r), where tc(pred) is the time complexity of pred and r is the size of the result.
Equivalent to (values (filter pred s) (filter (complement pred) s)) when pred is a
function. Returns two values: first, a new seq containing only those elements of s that
satisfy pred; second, a seq containing only those elements that do not satisfy
pred. In both results, the relative order is the same as in s. pred must be a
function, an fbound symbol, or a boolean-valued map. O(n ⋅ tc(pred)) + O(r log
r), where tc(pred) is the time complexity of pred and r is the size of the
result.
Returns a seq containing the values of fn applied to each element of s, in order. fn must be a function, an fbound symbol, or a map. O(n ⋅ tc(fn)) + O(r log r), where tc(fn) is the time complexity of fn and r is the size of the result.
A modify macro that expands to image. If place s
(which must be setf-able) holds a seq, updates it so the place now contains the image of the
seq under fn.
Iterates over [start .. end), where start defaults to 0 and end defaults to
size(s); if from-end is true, the iteration is in reverse order. Calls fn
repeatedly with two arguments, a state variable and the element of s at the next index,
storing the result of each call back into the state variable, and finally returning that result. If
initial-value is supplied, it is used as the initial value of the state variable. Otherwise:
if s is nonempty, the initial value is the first element; if s is empty, the result of
reduce is obtained by calling fn with no arguments. In all cases, if key is
provided, it is called on each element and the result used in place of the element. (Time
complexity depends on the behavior of fn.)
Iterates over [start .. end), where start defaults to 0 and end defaults to
size(s); if from-end is true, the iteration is in reverse order. Scans linearly through
elements of s at those indices to find one that matches item according to key and
test. For each element of s, key, a function that defaults to the identity
function, is called on it, and then test is called on item and the result; if it returns
true, find returns the element. If no match is found, find returns nil.
test defaults to equal?, not eql.
Iterates over [start .. end), where start defaults to 0 and end defaults to
size(s); if from-end is true, the iteration is in reverse order. Scans linearly through
elements of s at those indices to find one for which the result of calling key on it
satisfies pred. key and pred must be functions or fbound symbols. key
defaults to the identity function. Returns the element found, or nil if none.
Iterates over [start .. end), where start defaults to 0 and end defaults to
size(s); if from-end is true, the iteration is in reverse order. Scans linearly through
elements of s at those indices to find one for which the result of calling key on it
does not satisfy pred. key and pred must be functions or fbound symbols.
key defaults to the identity function. Returns the element found, or nil if none.
Iterates over [start .. end), where start defaults to 0 and end defaults to
size(s); if from-end is true, the iteration is in reverse order. Scans linearly through
elements of s at those indices, counting the number that match item according to
key and test. For each such element, key is called on it, and then test is
called on item and the result; if it returns true, the element is counted. Returns the count.
key and test must be functions or fbound symbols. key defaults to the identity
function; test defaults to equal?, not eql.
Iterates over [start .. end), where start defaults to 0 and end defaults to size(s); if from-end is true, the iteration is in reverse order. Scans linearly through the elements of s at those indices to count the number for which the result of calling key on them satisfies pred. Returns the count. pred and key must be functions or fbound symbols. key defaults to the identity function.
Iterates over [start .. end), where start defaults to 0 and end defaults to size(s); if from-end is true, the iteration is in reverse order. Scans linearly through the elements of s at those indices to count the number for which the result of calling key on them does not satisfy pred. Returns the count. pred and key must be functions or fbound symbols. key defaults to the identity function.
Iterates over [start .. end), where start defaults to 0 and end defaults to
size(s); if from-end is true, the iteration is in reverse order. Scans linearly through
the elements of s at those indices to find one that matches item according to key
and test. For each element of s, key, a function that defaults to the identity
function, is called on it, and then test is called on item and the result; if it returns
true, position returns the index of the element. If no match is found, position
returns nil. test defaults to equal?, not eql.
Iterates over [start .. end), where start defaults to 0 and end defaults to
size(s); if from-end is true, the iteration is in reverse order. Scans linearly through
the elements of s at those indices to find one for which the result of calling key on it
satisfies pred. key and pred must be functions or fbound symbols. key
defaults to the identity function. Returns the index of the element found, or nil if none.
Iterates over [start .. end), where start defaults to 0 and end defaults to
size(s); if from-end is true, the iteration is in reverse order. Scans linearly through
the elements of s to find one for which the result of calling key on it does not satisfy
pred. key and pred must be functions or fbound symbols. key defaults to
the identity function. Returns the index of the element found, or nil if none.
Iterates over [start .. end), where start defaults to 0 and end defaults to
size(s); if from-end is true, the iteration is in reverse order. Scans linearly through
elements of s at those indices, removing any that match item according to key and
test; if count is provided, stops after removing that many elements. For each such
element, key is called on it, and then test is called on item and the result; if
it returns true, the element is removed. Returns the updated seq. key and test must be
functions or fbound symbols. key defaults to the identity function; test defaults to
equal?, not eql.
Iterates over [start .. end), where start defaults to 0 and end defaults to size(s); if from-end is true, the iteration is in reverse order. Scans linearly through the elements of s at those indices, removing any for which the result of calling key on them satisfies pred; if count is provided, stops after removing that many elements. Returns the updated seq. pred and key must be functions or fbound symbols. key defaults to the identity function.
Iterates over [start .. end), where start defaults to 0 and end defaults to size(s); if from-end is true, the iteration is in reverse order. Scans linearly through the elements of s at those indices, removing any for which the result of calling key on them does not satisfy pred; if count is provided, stops after removing that many elements. Returns the updated seq. pred and key must be functions or fbound symbols. key defaults to the identity function.
Iterates over [start .. end), where start defaults to 0 and end defaults to
size(s); if from-end is true, the iteration is in reverse order. Scans linearly through
elements of s at those indices, substituting with newitem any that match olditem
according to key and test; if count is provided, stops after substituting that
many elements. For each such element, key is called on it, and then test is called on
olditem and the result; if it returns true, the element is substituted. Returns the updated
seq. key and test must be functions or fbound symbols. key defaults to the
identity function; test defaults to equal?, not eql.
Iterates over [start .. end), where start defaults to 0 and end defaults to size(s); if from-end is true, the iteration is in reverse order. Scans linearly through the elements of s at those indices, substituting with newitem any for which the result of calling key on them satisfies pred; if count is provided, stops after substituting that many elements. Returns the updated seq. pred and key must be functions or fbound symbols. key defaults to the identity function.
Iterates over [start .. end), where start defaults to 0 and end defaults to size(s); if from-end is true, the iteration is in reverse order. Scans linearly through the elements of s at those indices, substituting with newitem any for which the result of calling key on them does not satisfy pred; if count is provided, stops after substituting that many elements. Returns the updated seq. pred and key must be functions or fbound symbols. key defaults to the identity function.
Searches the interval of seq2 bounded by start2 and end2 for a subsequence
matching the interval of seq1 between start1 and end1. One of seq1 and
seq2 must be a seq for this method to be callled (otherwise, the compatibility method will be called), but the other can be anything that can be
converted to a seq. Elements are compared using test,
which defaults to equal?. Returns the index of the leftmost occurrence, unless
from-end is true, in which case it returns the index of the leftmost element of the rightmost
occurrence.
Scans in parallel the interval of seq1 between start1 and end1 and the interval of seq2 between start2 and end2, comparing corresponding elements, and returning the absolute index within seq1 of the first mismatch (unequal pair). One of seq1 and seq2 must be a seq for this method to be callled (otherwise, the compatibility method will be called), but the other can be anything that can be converted to a seq. If from-end is true, the comparison starts at the right ends of the intervals rather than the left ends.