Returns true iff b is empty. O(1).
Returns an empty bag of the same type and organization as c.
Returns the total multiplicity of the elements of b. O(1).
Returns the number of unique elements in b; that is, the size of a set containing its elements. O(1).
Returns an arbitrary element of b, with its multiplicity. Specifically, on
a nonempty bag, returns three values: an arbitrary element, its multiplicity, and true; on an empty
set, returns nil, nil, and false. O(1).
Returns true iff x is an element of b, with multiplicity of at least mult. O(log n).
If b contains x, returns two values, its multiplicity and the element found; else 0 and
nil. O(log n). (The lookup method is provided as a convenience; because it is
provided, you can also use the @ macro.)
Convenience method. If s contains x, returns two values, 1 and the instance found; else
0 and nil. O(log n). (Note that multiplicity returns an integer first value on
both bags and sets, but lookup on a set returns a boolean.)
Returns a bag, of the same class and organization as b, that contains mult more repetitions of x. That is, if x was not an element of b, the result contains it with multiplicity mult; if it was an element, the result contains it with its multiplicity in b plus mult.
A modify macro that expands to with. If place b holds
a bag, updates it so the bag now contains mult more repetitions of x.
Returns a bag, of the same class and organization as b, that contains mult fewer repetitions of x, but not fewer than zero. That is, if b contains x with multiplicity less than or equal to mult, the result does not contain x; if greater, the result contains x with it multiplicity in b minus mult.
A modify macro that expands to less. If place b
(which must be setf-able) holds a bag, updates it so the bag now contains mult fewer
repetitions of x (but not fewer than zero).
If b contains x, returns the index of x within the ordering of b; otherwise
nil. This ordering ignores multiplicities, counting each element once. O(log n).
Returns, as two values the element at index idx within the ordering of b, and its
multiplicity. (On a wb-bag, this is the same as at-rank.) idx must be in [0
.. size(s)); otherwise, signals an error of type simple-type-error. O(log n).
Returns a bag of the same type and organization as b1, that contains all elements that are in either b1 or b2, with the multiplicity of each equal to its maximum multiplicity in the two bags. A set can be supplied for one of the bags; its elements are treated as having multiplicity 1. Implements left preference: for any pair of equal objects in the two bags or sets, the result contains the instance that was in b1. Normally O(n).
Returns a bag of the same type and organization as b1, that contains all elements that are in either b1 or b2, with the multiplicity of each equal to the sum of its multiplicities in the two bags. A set can be supplied for one of the bags; its elements are treated as having multiplicity 1. Implements left preference: for any pair of equal objects in the two bags or sets, the result contains the instance that was in b1. Normally O(n).
Returns a bag of the same type and organization as b1, that contains all elements that are in both b1 and b2, with the multiplicity of each equal to its minimum multiplicity in the two bags. A set can be supplied for one of the bags; its elements are treated as having multiplicity 1, and the result will be returned as a set. Implements left preference: for any pair of equal objects in the two bags or sets, the result contains the instance that was in b1. Normally O(n).
Returns a bag of the same type and organization as b1, that contains all elements that are in both b1 and b2, with the multiplicity of each equal to the product of its multiplicities in the two bags. A set can be supplied for one of the bags; its elements are treated as having multiplicity 1. Implements left preference: for any pair of equal objects in the two bags or sets, the result contains the instance that was in b1. Normally O(n).
Returns a bag of the same type and organization as b1, that contains all elements that are in b1 with greater multiplicity than they occur in b2 with; the multiplicity of each is that in b1 minus that in b2. A set can be supplied for one of the bags; its elements are treated as having multiplicity 1, and if b1 is a set, the result will be returned as a set. Normally O(n).
Returns true iff every element of b1 is also in b2, with its multiplicity in b1 being greater than or equal to that in b2. Normally O(n).
Returns true iff every element of b1 is also in b2, with its multiplicity in b1 being greater than or equal to that in b2, and b1 is smaller (in total multiplicity) than b2. Normally O(n).
Returns true iff b1 and b2 have no elements in common. Normally O(n).
For each element of bag, binds x to it and executes body repeatedly, as many
times as the element’s multiplicity. When done, returns value if supplied, otherwise
nil.
For each element of bag, binds x to it and n to its multiplicity, and executes
body once. When done, returns value if supplied, otherwise nil.
Returns a stateful iterator over the bag b. Creating an iterator
takes O(log n) time; the :get operation is amortized O(1).
If pairs? is false, the :get operation returns two values: if there is another element
repetition remaining, returns it and true; else nil and false. Yields each element a number
of times equal to its multiplicity;
If pairs? is true, the :get operation returns three values: if there is another element
remaining, returns it and its multiplicity as two values and a true third value, else nil,
zero, and false.
Returns a functional iterator over the bag b. Creating an
iterator takes O(log n) time; the :first operation is O(1), and :rest is amortized
O(1).
If pairs? is false, the :first operation returns two values: if the iterator is not
empty, the first element and true; else nil and false. Yields each element a number of times
equal to its multiplicity;
If pairs? is true, the :first operation returns three values: if the iterator is not
empty, returns the first element and its multiplicity as two values and a true third value, else
nil, zero, and false.
Returns a new bag, of the same type and organization as b, containing only those elements that satisfy pred, with the same multiplicity as they have in b. 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 new bag, of the same type and organization as b, containing only those pairs that satisfy pred. That is, pred is called with each element and its multipilcity as two arguments; if it returns true, the result will contain the element, with the same multipilcity. pred must be a function or an fbound symbol. 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 bag containing the values of fn applied to all the elements of b. Since the result is a bag, its elements will not necessarily correspond one-to-one to those of b; it will impose its own ordering, and will have fewer distinct elements than b if fn returns the same value on two or more elements of b. The multiplicity of each element of the result will be the sum of the multiplicities of the elements of b that fn mapped to it.
The result will be of the same type as b. compare-fn-name, if supplied, will control its organization; otherwise, that will also be the same as for b. 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 b
(which must be setf-able) holds a bag, updates it so the place now contains the image of the
bag under fn.
If pairs? is false, calls fn repeatedly with two arguments, a state variable and the next element repetition of b, storing the result of each call back into the state variable, and finally returning that result. In this mode, calls fn on each element a number of times equal to the element’s multiplicity.
If pairs? is true, calls fn repeatedly with three arguments, a state variable, the next element of b, and the multiplicity of that element, storing the result of each call back into the state variable, and finally returning that result. In this mode, calls fn on each element once.
If initial-value is supplied, it is used as the initial value of the state variable.
Otherwise: if b 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.)
Scans linearly through b to find an element that matches item according to key and
test. For each (unique) element of b, 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.
Normally O(n), but as a special case, if test is equal?, key is not supplied,
and the bag’s comparison function is compare, this does an O(log n) lookup.
Scans linearly through b to find an element 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.
Scans linearly through b to find an element 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.
Scans linearly through b, accumulating the total multiplicity of elements that match
item according to key and test. For each element of b, key is called
on it, and then test is called on item and the result; if it returns true, the element’s
multiplicity is added. Returns the total. key and test must be functions or fbound
symbols. key defaults to the identity function; test defaults to equal?, not
eql.
Normally O(n), but as a special case, if test is equal?, key is not supplied,
and the bag’s comparison function is compare, this does an O(log n) lookup.
Scans linearly through b to accumulate the total multiplicity of elements for which the result of calling key on them satisfies pred. Returns the total. pred and key must be functions or fbound symbols. key defaults to the identity function.
Scans linearly through b to accumulate the total multiplicity of elements for which the result of calling key on them does not satisfy pred. Returns the total. pred and key must be functions or fbound symbols. key defaults to the identity function.