Merge pull request #278 from petgraph/unionfind-perf
Improve performance of UnionFind's find_mut
diff --git a/src/unionfind.rs b/src/unionfind.rs
index bbc9a06..986d60d 100644
--- a/src/unionfind.rs
+++ b/src/unionfind.rs
@@ -33,6 +33,13 @@
xs.get_unchecked(index)
}
+#[inline]
+unsafe fn get_unchecked_mut<K>(xs: &mut [K], index: usize) -> &mut K
+{
+ debug_assert!(index < xs.len());
+ xs.get_unchecked_mut(index)
+}
+
impl<K> UnionFind<K>
where K: IndexType
{
@@ -79,17 +86,16 @@
}
}
- unsafe fn find_mut_recursive(&mut self, x: K) -> K
+ unsafe fn find_mut_recursive(&mut self, mut x: K) -> K
{
- let xparent = *get_unchecked(&self.parent, x.index());
- if xparent != x {
- let xrep = self.find_mut_recursive(xparent);
- let xparent = self.parent.get_unchecked_mut(x.index());
- *xparent = xrep;
- *xparent
- } else {
- xparent
+ let mut parent = *get_unchecked(&self.parent, x.index());
+ while parent != x {
+ let grandparent = *get_unchecked(&self.parent, parent.index());
+ *get_unchecked_mut(&mut self.parent, x.index()) = grandparent;
+ x = parent;
+ parent = grandparent;
}
+ x
}
/// Returns `true` if the given elements belong to the same set, and returns
