idtree 0.2.0

ID-Tree dynamic connectivity data structure
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

// bridge.rs

/// Bridge between C++ and Rust for the DNDTree implementation.
#[cxx::bridge]
pub mod ffi {
    unsafe extern "C++" {
        include!("dndtree_wrapper.h");

        /// Opaque handle to the C++ CPPDNDTree wrapper class.
        type CPPDNDTree;

        /// Constructs a new CPPDNDTree from a flattened adjacency list representation.
        ///
        /// # Arguments
        /// * `n` - The number of nodes in the graph.
        /// * `degrees` - A slice containing the degree of each node.
        /// * `flat_neighbors` - A flattened list of neighbors for all nodes.
        /// * `use_union_find` - Whether to enable DSU-based connectivity optimizations.
        fn new_cpp_dndtree_from_flat_adj(
            n: i32,
            degrees: &[i32],
            flat_neighbors: &[i32],
            use_union_find: bool,
        ) -> UniquePtr<CPPDNDTree>;

        /// Inserts an edge into the tree and updates the dynamic connectivity state.
        fn insert_edge(&self, u: i32, v: i32) -> i32;

        /// Deletes an edge from the tree and searches for a replacement edge.
        fn delete_edge(&self, u: i32, v: i32) -> i32;

        /// Returns true if nodes u and v are currently connected in the forest.
        fn query(&self, u: i32, v: i32) -> bool;

        /// Returns the DSU root for a given node. Returns -1 if DSU is disabled.
        fn get_dsu_root(&self, u: i32) -> i32;

        /// Returns the current parent of node u in the tree structure.
        fn get_tree_parent(&self, u: i32) -> i32;

        /// Returns the size of the subtree rooted at node u.
        fn get_subtree_size(&self, u: i32) -> i32;

        /// Toggles the global C++ trace output for debugging internal logic state.
        fn set_cpp_trace(enable: bool);
    }
}