Struct datafrog::Variable

source · 
pub struct Variable<Tuple: Ord> {
    pub stable: Rc<RefCell<Vec<Relation<Tuple>>>>,
    pub recent: Rc<RefCell<Relation<Tuple>>>,
    /* private fields */
}
Expand description

An monotonically increasing set of Tuples.

There are three stages in the lifecycle of a tuple:

  1. A tuple is added to self.to_add, but is not yet visible externally.
  2. Newly added tuples are then promoted to self.recent for one iteration.
  3. After one iteration, recent tuples are moved to self.tuples for posterity.

Each time self.changed() is called, the recent relation is folded into tuples, and the to_add relations are merged, potentially deduplicated against tuples, and then made recent. This way, across calls to changed() all added tuples are in recent at least once and eventually all are in tuples.

A Variable may optionally be instructed not to de-duplicate its tuples, for reasons of performance. Such a variable cannot be relied on to terminate iterative computation, and it is important that any cycle of derivations have at least one de-duplicating variable on it.

Fields§

§stable: Rc<RefCell<Vec<Relation<Tuple>>>>

A list of relations whose union are the accepted tuples.

§recent: Rc<RefCell<Relation<Tuple>>>

A list of recent tuples, still to be processed.

Implementations§

Adds tuples that result from joining input1 and input2 – each of the inputs must be a set of (Key, Value) tuples. Both input1 and input2 must have the same type of key (K) but they can have distinct value types (V1 and V2 respectively). The logic closure will be invoked for each key that appears in both inputs; it is also given the two values, and from those it should construct the resulting value.

Note that input1 must be a variable, but input2 can be a relation or a variable. Therefore, you cannot join two relations with this method. This is not because the result would be wrong, but because it would be inefficient: the result from such a join cannot vary across iterations (as relations are fixed), so you should prefer to invoke insert on a relation created by Relation::from_join instead.

Examples

This example starts a collection with the pairs (x, x+1) and (x+1, x) for x in 0 .. 10. It then adds pairs (y, z) for which (x, y) and (x, z) are present. Because the initial pairs are symmetric, this should result in all pairs (x, y) for x and y in 0 .. 11.

use datafrog::{Iteration, Relation};

let mut iteration = Iteration::new();
let variable = iteration.variable::<(usize, usize)>("source");
variable.extend((0 .. 10).map(|x| (x, x + 1)));
variable.extend((0 .. 10).map(|x| (x + 1, x)));

while iteration.changed() {
    variable.from_join(&variable, &variable, |&key, &val1, &val2| (val1, val2));
}

let result = variable.complete();
assert_eq!(result.len(), 121);

Adds tuples from input1 whose key is not present in input2.

Note that input1 must be a variable: if you have a relation instead, you can use Relation::from_antijoin and then Variable::insert. Note that the result will not vary during the iteration.

Examples

This example starts a collection with the pairs (x, x+1) for x in 0 .. 10. It then adds any pairs (x+1,x) for which x is not a multiple of three. That excludes four pairs (for 0, 3, 6, and 9) which should leave us with 16 total pairs.

use datafrog::{Iteration, Relation};

let mut iteration = Iteration::new();
let variable = iteration.variable::<(usize, usize)>("source");
variable.extend((0 .. 10).map(|x| (x, x + 1)));

let relation: Relation<_> = (0 .. 10).filter(|x| x % 3 == 0).collect();

while iteration.changed() {
    variable.from_antijoin(&variable, &relation, |&key, &val| (val, key));
}

let result = variable.complete();
assert_eq!(result.len(), 16);

Adds tuples that result from mapping input.

Examples

This example starts a collection with the pairs (x, x) for x in 0 .. 10. It then repeatedly adds any pairs (x, z) for (x, y) in the collection, where z is the Collatz step for y: it is y/2 if y is even, and 3*y + 1 if y is odd. This produces all of the pairs (x, y) where x visits y as part of its Collatz journey.

use datafrog::{Iteration, Relation};

let mut iteration = Iteration::new();
let variable = iteration.variable::<(usize, usize)>("source");
variable.extend((0 .. 10).map(|x| (x, x)));

while iteration.changed() {
    variable.from_map(&variable, |&(key, val)|
        if val % 2 == 0 {
            (key, val/2)
        }
        else {
            (key, 3*val + 1)
        });
}

let result = variable.complete();
assert_eq!(result.len(), 74);

Adds tuples that result from combining source with the relations given in leapers. This operation is very flexible and can be used to do a combination of joins and anti-joins. The main limitation is that the things being combined must consist of one dynamic variable (source) and then several fixed relations (leapers).

The idea is as follows:

  • You will be inserting new tuples that result from joining (and anti-joining) some dynamic variable source of source tuples (SourceTuple) with some set of values (of type Val).
  • You provide these values by combining source with a set of leapers leapers, each of which is derived from a fixed relation. The leapers should be either a single leaper (of suitable type) or else a tuple of leapers. You can create a leaper in one of two ways:
    • Extension: In this case, you have a relation of type (K, Val) for some type K. You provide a closure that maps from SourceTuple to the key K. If you use relation.extend_with, then any Val values the relation provides will be added to the set of values; if you use extend_anti, then the Val values will be removed.
    • Filtering: In this case, you have a relation of type K for some type K and you provide a closure that maps from SourceTuple to the key K. Filters don’t provide values but they remove source tuples.
  • Finally, you get a callback logic that accepts each (SourceTuple, Val) that was successfully joined (and not filtered) and which maps to the type of this variable.

Inserts a relation into the variable.

This is most commonly used to load initial values into a variable. it is not obvious that it should be commonly used otherwise, but it should not be harmful.

Extend the variable with values from the iterator.

This is most commonly used to load initial values into a variable. it is not obvious that it should be commonly used otherwise, but it should not be harmful.

Consumes the variable and returns a relation.

This method removes the ability for the variable to develop, and flattens all internal tuples down to one relation. The method asserts that iteration has completed, in that self.recent and self.to_add should both be empty.

Trait Implementations§

Returns a copy of the value. Read more
Performs copy-assignment from source. Read more
If we are on iteration N of the loop, these are the tuples added on iteration N-1. (For a Relation, this is always an empty slice.) Read more
If we are on iteration N of the loop, these are the tuples added on iteration N - 2 or before. (For a Relation, this is just self.) Read more
Get the set of recent tuples.
Get the set of stable tuples.

Auto Trait Implementations§

Blanket Implementations§

Gets the TypeId of self. Read more
Immutably borrows from an owned value. Read more
Mutably borrows from an owned value. Read more

Returns the argument unchanged.

Calls U::from(self).

That is, this conversion is whatever the implementation of From<T> for U chooses to do.

The resulting type after obtaining ownership.
Creates owned data from borrowed data, usually by cloning. Read more
Uses borrowed data to replace owned data, usually by cloning. Read more
The type returned in the event of a conversion error.
Performs the conversion.
The type returned in the event of a conversion error.
Performs the conversion.