Mercurial > hg
annotate rust/hg-core/src/dagops.rs @ 41717:9060af281be7
rust: itering less on MissingAncestors.bases for max()
Instead of iterating on the whole `self.bases` each time to find
its max, we keep the latter in a separate member attribute and
keep it up to date in `add_bases()`
On a perfdiscovery done on PyPy, with repos prepared with
`contrib/discovery-helper.sh 50 100`, this gives a slight
improvement (around 0.5% on wall time, but 10% on CPU)
before:
! wall 0.172801 comb 0.180000 user 0.180000 sys 0.000000 (median of 541)
after:
! wall 0.171798 comb 0.160000 user 0.160000 sys 0.000000 (median of 551)
(perf command run time upped because of bigger variability during this test).
Differential Revision: https://phab.mercurial-scm.org/D5945
author | Georges Racinet <georges.racinet@octobus.net> |
---|---|
date | Mon, 04 Feb 2019 19:46:57 +0100 |
parents | 47881d2a9d99 |
children | 3bdb21bbf791 |
rev | line source |
---|---|
41242
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
1 // dagops.rs |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
2 // |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
3 // Copyright 2019 Georges Racinet <georges.racinet@octobus.net> |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
4 // |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
5 // This software may be used and distributed according to the terms of the |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
6 // GNU General Public License version 2 or any later version. |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
7 |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
8 //! Miscellaneous DAG operations |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
9 //! |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
10 //! # Terminology |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
11 //! - By *relative heads* of a collection of revision numbers (`Revision`), |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
12 //! we mean those revisions that have no children among the collection. |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
13 //! - Similarly *relative roots* of a collection of `Revision`, we mean |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
14 //! those whose parents, if any, don't belong to the collection. |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
15 use super::{Graph, GraphError, Revision, NULL_REVISION}; |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
16 use std::collections::HashSet; |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
17 |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
18 fn remove_parents( |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
19 graph: &impl Graph, |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
20 rev: Revision, |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
21 set: &mut HashSet<Revision>, |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
22 ) -> Result<(), GraphError> { |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
23 for parent in graph.parents(rev)?.iter() { |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
24 if *parent != NULL_REVISION { |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
25 set.remove(parent); |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
26 } |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
27 } |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
28 Ok(()) |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
29 } |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
30 |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
31 /// Relative heads out of some revisions, passed as an iterator. |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
32 /// |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
33 /// These heads are defined as those revisions that have no children |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
34 /// among those emitted by the iterator. |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
35 /// |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
36 /// # Performance notes |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
37 /// Internally, this clones the iterator, and builds a `HashSet` out of it. |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
38 /// |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
39 /// This function takes an `Iterator` instead of `impl IntoIterator` to |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
40 /// guarantee that cloning the iterator doesn't result in cloning the full |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
41 /// construct it comes from. |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
42 pub fn heads<'a>( |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
43 graph: &impl Graph, |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
44 iter_revs: impl Clone + Iterator<Item = &'a Revision>, |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
45 ) -> Result<HashSet<Revision>, GraphError> { |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
46 let mut heads: HashSet<Revision> = iter_revs.clone().cloned().collect(); |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
47 heads.remove(&NULL_REVISION); |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
48 for rev in iter_revs { |
41717
9060af281be7
rust: itering less on MissingAncestors.bases for max()
Georges Racinet <georges.racinet@octobus.net>
parents:
41242
diff
changeset
|
49 if *rev != NULL_REVISION { |
9060af281be7
rust: itering less on MissingAncestors.bases for max()
Georges Racinet <georges.racinet@octobus.net>
parents:
41242
diff
changeset
|
50 remove_parents(graph, *rev, &mut heads)?; |
9060af281be7
rust: itering less on MissingAncestors.bases for max()
Georges Racinet <georges.racinet@octobus.net>
parents:
41242
diff
changeset
|
51 } |
41242
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
52 } |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
53 Ok(heads) |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
54 } |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
55 |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
56 /// Retain in `revs` only its relative heads. |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
57 /// |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
58 /// This is an in-place operation, so that control of the incoming |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
59 /// set is left to the caller. |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
60 /// - a direct Python binding would probably need to build its own `HashSet` |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
61 /// from an incoming iterable, even if its sole purpose is to extract the |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
62 /// heads. |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
63 /// - a Rust caller can decide whether cloning beforehand is appropriate |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
64 /// |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
65 /// # Performance notes |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
66 /// Internally, this function will store a full copy of `revs` in a `Vec`. |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
67 pub fn retain_heads( |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
68 graph: &impl Graph, |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
69 revs: &mut HashSet<Revision>, |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
70 ) -> Result<(), GraphError> { |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
71 revs.remove(&NULL_REVISION); |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
72 // we need to construct an iterable copy of revs to avoid itering while |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
73 // mutating |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
74 let as_vec: Vec<Revision> = revs.iter().cloned().collect(); |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
75 for rev in as_vec { |
41717
9060af281be7
rust: itering less on MissingAncestors.bases for max()
Georges Racinet <georges.racinet@octobus.net>
parents:
41242
diff
changeset
|
76 if rev != NULL_REVISION { |
9060af281be7
rust: itering less on MissingAncestors.bases for max()
Georges Racinet <georges.racinet@octobus.net>
parents:
41242
diff
changeset
|
77 remove_parents(graph, rev, revs)?; |
9060af281be7
rust: itering less on MissingAncestors.bases for max()
Georges Racinet <georges.racinet@octobus.net>
parents:
41242
diff
changeset
|
78 } |
41242
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
79 } |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
80 Ok(()) |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
81 } |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
82 |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
83 #[cfg(test)] |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
84 mod tests { |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
85 |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
86 use super::*; |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
87 use crate::testing::SampleGraph; |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
88 |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
89 /// Apply `retain_heads()` to the given slice and return as a sorted `Vec` |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
90 fn retain_heads_sorted( |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
91 graph: &impl Graph, |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
92 revs: &[Revision], |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
93 ) -> Result<Vec<Revision>, GraphError> { |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
94 let mut revs: HashSet<Revision> = revs.iter().cloned().collect(); |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
95 retain_heads(graph, &mut revs)?; |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
96 let mut as_vec: Vec<Revision> = revs.iter().cloned().collect(); |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
97 as_vec.sort(); |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
98 Ok(as_vec) |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
99 } |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
100 |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
101 #[test] |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
102 fn test_retain_heads() -> Result<(), GraphError> { |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
103 assert_eq!(retain_heads_sorted(&SampleGraph, &[4, 5, 6])?, vec![5, 6]); |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
104 assert_eq!( |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
105 retain_heads_sorted(&SampleGraph, &[4, 1, 6, 12, 0])?, |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
106 vec![1, 6, 12] |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
107 ); |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
108 assert_eq!( |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
109 retain_heads_sorted(&SampleGraph, &[1, 2, 3, 4, 5, 6, 7, 8, 9])?, |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
110 vec![3, 5, 8, 9] |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
111 ); |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
112 Ok(()) |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
113 } |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
114 |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
115 /// Apply `heads()` to the given slice and return as a sorted `Vec` |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
116 fn heads_sorted( |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
117 graph: &impl Graph, |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
118 revs: &[Revision], |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
119 ) -> Result<Vec<Revision>, GraphError> { |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
120 let heads = heads(graph, revs.iter())?; |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
121 let mut as_vec: Vec<Revision> = heads.iter().cloned().collect(); |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
122 as_vec.sort(); |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
123 Ok(as_vec) |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
124 } |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
125 |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
126 #[test] |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
127 fn test_heads() -> Result<(), GraphError> { |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
128 assert_eq!(heads_sorted(&SampleGraph, &[4, 5, 6])?, vec![5, 6]); |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
129 assert_eq!( |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
130 heads_sorted(&SampleGraph, &[4, 1, 6, 12, 0])?, |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
131 vec![1, 6, 12] |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
132 ); |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
133 assert_eq!( |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
134 heads_sorted(&SampleGraph, &[1, 2, 3, 4, 5, 6, 7, 8, 9])?, |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
135 vec![3, 5, 8, 9] |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
136 ); |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
137 Ok(()) |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
138 } |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
139 |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
140 } |