Struct esl01_dag::IdDag

pub struct IdDag<Store> { /* fields omitted */ }

Structure to store a DAG of integers, with indexes to speed up ancestry queries.

A segment is defined as (level: int, low: int, high: int, parents: [int]) on a topo-sorted integer DAG. It covers all integers in low..=high range, and must satisfy:

• high is the only head in the sub DAG covered by the segment.
• parents do not have entries within low..=high range.
• If level is 0, for any integer x in low+1..=high range, x's parents must be x - 1.

See slides/201904-segmented-changelog/segmented-changelog.pdf for pretty graphs about how segments help with ancestry queries.

IdDag is often used together with [IdMap] to allow customized names on vertexes. The [NameDag] type provides an easy-to-use interface to keep IdDag and [IdMap] in sync.

Methods

impl IdDag<IndexedLogStore>

pub fn open(path: impl AsRef<Path>) -> Result<Self>

Open IdDag at the given directory. Create it on demand.

pub fn prepare_filesystem_sync(&self) -> Result<SyncableIdDag<IndexedLogStore>>

Return a [SyncableIdDag] instance that provides race-free filesytem read and write access by taking an exclusive lock.

The [SyncableIdDag] instance provides a sync method that actually writes changes to disk.

Block if another instance is taking the lock.

pub fn set_new_segment_size(&mut self, size: usize)

Set the maximum size of a new high-level segment.

This does not affect existing segments.

This might help performance a bit for certain rare types of DAGs. The default value is Usually good enough.

impl IdDag<InProcessStore>

pub fn new_in_process() -> Self

Instantiate an IdDag that stores all it's data in process. Useful for scenarios that do not require data persistance.

impl<Store: IdDagStore> IdDag<Store>

pub fn next_free_id(&self, level: Level, group: Group) -> Result<Id>

Return the next unused id for segments of the specified level.

Useful for building segments incrementally.

impl<Store: IdDagStore> IdDag<Store>

pub fn build_segments_volatile<F>(
    &mut self,
    high: Id,
    get_parents: &F
) -> Result<usize> where
    F: Fn(Id) -> Result<Vec<Id>>, 

Make sure the IdDag contains the given id (and all ids smaller than high) by building up segments on demand.

get_parents describes the DAG. Its input and output are Ids.

This is often used together with crate::idmap::IdMap.

Content inserted by this function will not be written to disk. For example, IdDag::prepare_filesystem_sync will drop them.

impl<Store: IdDagStore> IdDag<Store>

pub fn reload(&mut self) -> Result<()>

Reload from the source of truth. Discard pending changes.

impl<Store: IdDagStore> IdDag<Store>

pub fn all(&self) -> Result<SpanSet>

Return a SpanSet that covers all ids stored in this IdDag.

pub fn ancestors(&self, set: impl Into<SpanSet>) -> Result<SpanSet>

Calculate all ancestors reachable from any id from the given set.

union(ancestors(i) for i in set)

pub fn parents(&self, set: impl Into<SpanSet>) -> Result<SpanSet>

Calculate parents of the given set.

Note: SpanSet does not preserve order. Use IdDag::parent_ids if order is needed.

pub fn parent_ids(&self, id: Id) -> Result<Vec<Id>>

Get parents of a single id. Preserve the order.

pub fn first_ancestor_nth(&self, id: Id, n: u64) -> Result<Id>

Calculate the n-th first ancestor. If n is 0, return id unchanged. If n is 1, return the first parent of id.

pub fn to_first_ancestor_nth(
    &self,
    id: Id,
    constraint: FirstAncestorConstraint
) -> Result<Option<(Id, u64)>>

Convert an id to x~n form with the given constraint.

Return None if the conversion can not be done with the constraints.

pub fn heads(&self, set: impl Into<SpanSet>) -> Result<SpanSet>

Calculate heads of the given set.

pub fn children(&self, set: impl Into<SpanSet>) -> Result<SpanSet>

Calculate children of the given set.

pub fn roots(&self, set: impl Into<SpanSet>) -> Result<SpanSet>

Calculate roots of the given set.

pub fn gca_one(&self, set: impl Into<SpanSet>) -> Result<Option<Id>>

Calculate one "greatest common ancestor" of the given set.

If there are no common ancestors, return None. If there are multiple greatest common ancestors, pick one arbitrarily. Use gca_all to get all of them.

pub fn gca_all(&self, set: impl Into<SpanSet>) -> Result<SpanSet>

Calculate all "greatest common ancestor"s of the given set. gca_one is faster if an arbitrary answer is ok.

pub fn common_ancestors(&self, set: impl Into<SpanSet>) -> Result<SpanSet>

Calculate all common ancestors of the given set.

intersect(ancestors(i) for i in set)

pub fn is_ancestor(&self, ancestor_id: Id, descendant_id: Id) -> Result<bool>

Test if ancestor_id is an ancestor of descendant_id.

pub fn heads_ancestors(&self, set: impl Into<SpanSet>) -> Result<SpanSet>

Calculate "heads" of the ancestors of the given SpanSet. That is, Find Y, which is the smallest subset of set X, where ancestors(Y) is ancestors(X).

This is faster than calculating heads(ancestors(set)).

This is different from heads. In case set contains X and Y, and Y is an ancestor of X, but not the immediate ancestor, heads will include Y while this function won't.

pub fn range(
    &self,
    roots: impl Into<SpanSet>,
    heads: impl Into<SpanSet>
) -> Result<SpanSet>

Calculate the "dag range" - ids reachable from both sides.

intersect(ancestors(heads), descendants(roots))

pub fn descendants(&self, set: impl Into<SpanSet>) -> Result<SpanSet>

Calculate the descendants of the given set.

Logically equivalent to range(set, all()).

impl<Store: IdDagStore> IdDag<Store>

pub fn write_sparse_idmap(
    &self,
    full_idmap: &dyn IdMapLike,
    sparse_idmap: &mut IdMap
) -> Result<()>

Copy a subset of "Universal" mapping from full_idmap to sparse_idmap. See IdDag::universal.

Trait Implementations

impl<Store: IdDagStore> Debug for IdDag<Store>

fn fmt(&self, f: &mut Formatter) -> Result

Formats the value using the given formatter.