Returns true iff r is empty. O(1).
Returns the number of key/value pairs in r. O(1).
Returns an arbitrary key/value pair of r. Specifically, on a nonempty
relation, returns three values: an arbitrary key, an arbitrary value associated with that key, and
true; on an empty relation, returns nil, nil, and false. O(1).
Constructs inverse. Returns the inverse of r, that is, a relation with the same pairs as r except that keys and values are swapped. The returned relation is of the same implementation as r, and its key and value comparison functions are swapped. Amortized O(1).
Returns true iff r contains a pair whose key is x and whose value is y. O(log n).
Returns true iff r has any pair whose key is x. O(log n).
Constructs inverse. Returns true iff r has any pair whose value is y. Amortized O(log n).
Returns the set of values to which r maps key x. If r has no pairs with key x, simply returns an empty set. The returned set is of the same implementation (WB or CHAMP) as r, and its comparison function is the value comparison function of r. O(log n).
The use of setf with lookup on a binary relation is not recommended, as the semantics
don’t make sense; (setf (lookup r x) y) simply adds the pair <x,
y> to r.
Constructs inverse. Returns the set of keys that r maps to value y. If r has no pairs with value y, simply returns an empty set. The returned set is of the same implementation (WB or CHAMP) as r, and its comparison function is the key comparison function of r. Amortized O(log n).
Returns the domain of r, that is, the set of keys it maps to at least one value. O(n).
Constructs inverse. Returns the range of r, that is, the set of values to which at least one key is mapped. Amortized O(n).
Returns a relation, of the same type and organization as r, that contains all pairs of r and also maps key x to value y. If r already contained that mapping, returns r itself. O(log n).
Returns a relation, of the same type and organization as r, that contains all pairs of r except the one mapping key x to value y. If r already did not contain that mapping, returns r itself. O(log n).
Returns a relation, of the same type and organization is r1, that contains all pairs that are in either r1 or r2. Implements left preference: for any pair of equal objects in the two relations, the result contains the instance that was in s1. If either r1 or r2 has had its inverse constructed, the result does also. O(n).
Returns a relation, of the same type and organization is r1, that contains all pairs that are in both r1 and r2. Implements left preference: for any pair of equal objects in the two relations, the result contains the instance that was in r1. If either r1 or r2 has had its inverse constructed, the result does also. O(n).
Here c1 and c2 designate columns of r1 and r2 respectively, as 0 for the domain and 1 for the range. Computes and returns the equijoin of r1 column c1 with r2 column c2. This is a 2-relation in which each pair of pairs of the two relations that have equal values in the specified columns become one pair in the result, with the other column of the r1 pair being its domain value and the other column in the r2 pair its range value. O(n).
Returns a 2-relation containing those pairs of r for which the key is mapped to more than one value. O(n).
(The use case for this operation is when you expect the relation to be a function, or nearly so;
perhaps you plan to convert it to a map. If r is a
function already, conflicts returns an empty relation; otherwise, it tells you which keys map
to non-unique values — the idea is that these are conflicts that will need to be resolved
somehow.)
For each key/value pair of rel, binds x to the key and y to the value and executes
body. When done, returns value if supplied, otherwise nil.
(If you want to execute the body only once for each key, write:
(do-map (x y-set (convert 'map-to-sets rel)) ...)
y-set will be bound to the set of values for the current key.)
Returns a stateful iterator over the 2-relation r. The :get
operation returns three values: if there is another key/value pair remaining, returns it as two
values and a true third value, else two nil values and false. Creating an iterator takes
O(log n) time; the :get operation is amortized O(1).
Returns a functional iterator over the 2-relation r. The
:first operation returns three values: if the iterator is not empty, returns the first
key/value pair as two values and a true third value, else two nil values and false. Creating
an iterator takes O(log n) time; the :first operation is O(1), and :rest is
amortized O(1).