rust: translation of missingancestors
This is as direct as possible a translation of the ancestor.missingancestors
Python class in pure Rust. The goal for this changeset is to make it easy
to compare with the Python version.
We also add to Python tests the cases that helped us develop and debug
this implementation.
Some possible optimizations are marked along the way as TODO comments
Differential Revision: https://phab.mercurial-scm.org/D5416
% removeancestorsfrom(), example 1
remaining (sorted): [5, 6, 8, 9]
% removeancestorsfrom(), example 2
remaining (sorted): [11, 12, 13, 14]
% removeancestorsfrom(), example 3
remaining (sorted): [3, 5]
% missingancestors(), example 1
return [3, 7, 11]
% missingancestors(), example 2
return [5, 10]
% missingancestors(), example 3
return [3, 6, 9, 11]
% removeancestorsfrom(), bigger graph
Ok
% lazy ancestor set for [], stoprev = 0, inclusive = False
membership: []
iteration: []
% lazy ancestor set for [11, 13], stoprev = 0, inclusive = False
membership: [7, 8, 3, 4, 1, 0]
iteration: [8, 7, 4, 3, 2, 1, 0]
% lazy ancestor set for [1, 3], stoprev = 0, inclusive = False
membership: [1, 0]
iteration: [1, 0]
% lazy ancestor set for [11, 13], stoprev = 0, inclusive = True
membership: [11, 13, 7, 8, 3, 4, 1, 0]
iteration: [13, 11, 8, 7, 4, 3, 2, 1, 0]
% lazy ancestor set for [11, 13], stoprev = 6, inclusive = False
membership: [7, 8]
iteration: [8, 7]
% lazy ancestor set for [11, 13], stoprev = 6, inclusive = True
membership: [11, 13, 7, 8]
iteration: [13, 11, 8, 7]
% lazy ancestor set for [11, 13], stoprev = 11, inclusive = True
membership: [11, 13]
iteration: [13, 11]
% lazy ancestor set for [11, 13], stoprev = 12, inclusive = True
membership: [13]
iteration: [13]
% lazy ancestor set for [10, 1], stoprev = 0, inclusive = True
membership: [2, 10, 4, 5, 0, 1]
iteration: [10, 5, 4, 2, 1, 0]