linnet/half_edge/nodestore/
bitvec_find.rs

1use bitvec::vec::BitVec;
2
3use crate::{
4    half_edge::{
5        involution::Hedge,
6        nodestore::{BitVecNeighborIter, NodeStorage, NodeStorageOps, NodeStorageVec},
7        NodeIndex,
8    },
9    tree::{parent_pointer::PPNode, Forest, RootData, RootId},
10    union_find::{SetIndex, UFNode, UnionFind},
11};
12
13#[derive(Debug, Clone, PartialEq, Eq, Hash)]
14#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
15#[cfg_attr(feature = "bincode", derive(bincode::Encode, bincode::Decode))]
16pub struct HedgeNodeStore<V> {
17    data: V,
18    #[cfg_attr(feature = "bincode", bincode(with_serde))]
19    node: BitVec,
20}
21
22#[derive(Debug, Clone, PartialEq, Eq)]
23#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
24#[cfg_attr(feature = "bincode", derive(bincode::Encode, bincode::Decode))]
25pub struct UnionFindNodeStore<V> {
26    pub nodes: UnionFind<HedgeNodeStore<V>>,
27}
28
29impl<V> From<NodeStorageVec<V>> for UnionFindNodeStore<V> {
30    fn from(vecnodes: NodeStorageVec<V>) -> Self {
31        let node_data: Vec<_> = vecnodes
32            .node_data
33            .into_iter()
34            .zip(vecnodes.nodes)
35            .map(|(v, h)| HedgeNodeStore { data: v, node: h })
36            .collect();
37
38        let hairs: Vec<_> = node_data.iter().map(|a| a.node.clone()).collect();
39
40        UnionFindNodeStore {
41            nodes: UnionFind::from_bitvec_partition(node_data.into_iter().zip(hairs).collect())
42                .unwrap(),
43        }
44    }
45}
46
47impl SetIndex {
48    pub fn node_ref(&self) -> &NodeIndex {
49        unsafe { std::mem::transmute(self) }
50    }
51}
52
53impl<V> NodeStorage for UnionFindNodeStore<V> {
54    type Storage<N> = UnionFindNodeStore<N>;
55    type NodeData = V;
56    type Neighbors = BitVec;
57    type NeighborsIter<'a>
58        = BitVecNeighborIter<'a>
59    where
60        Self: 'a;
61}
62
63impl<V> UnionFindNodeStore<V> {
64    fn root_hedge(&self, node: NodeIndex) -> Hedge {
65        self.nodes[&SetIndex(node.0)].root_pointer
66    }
67}
68
69impl<V> NodeStorageOps for UnionFindNodeStore<V> {
70    type OpStorage<A> = Self::Storage<A>;
71    type Base = BitVec;
72
73    fn swap(&mut self, _a: Hedge, _b: Hedge) {
74        todo!()
75    }
76
77    fn delete<S: crate::half_edge::subgraph::SubGraph<Base = Self::Base>>(
78        &mut self,
79        _subgraph: &S,
80    ) {
81        todo!()
82    }
83
84    fn extract<S: crate::half_edge::subgraph::SubGraph<Base = Self::Base>, V2>(
85        &mut self,
86        _subgraph: &S,
87        _spit_node: impl FnMut(&Self::NodeData) -> V2,
88        _owned_node: impl FnMut(Self::NodeData) -> V2,
89    ) -> Self::OpStorage<V2> {
90        todo!()
91    }
92
93    fn get_neighbor_iterator(&self, node_id: NodeIndex) -> Self::NeighborsIter<'_> {
94        (&self.nodes[SetIndex(node_id.0)].node).into()
95    }
96
97    fn hedge_len(&self) -> usize {
98        self.nodes.n_elements()
99    }
100
101    fn identify_nodes(
102        &mut self,
103        nodes: &[NodeIndex],
104        node_data_merge: Self::NodeData,
105    ) -> NodeIndex {
106        let hedges = nodes
107            .iter()
108            .map(|n| self.root_hedge(*n))
109            .collect::<Vec<_>>();
110
111        let n_init_root = hedges[0];
112        for n in hedges.iter().skip(1) {
113            self.nodes.union(n_init_root, *n, |a, _| a);
114        }
115        self.nodes.replace_set_data_of(n_init_root, |mut a| {
116            a.data = node_data_merge;
117            a
118        });
119        NodeIndex(self.nodes.find_data_index(n_init_root).0)
120    }
121
122    fn to_forest<U, H>(
123        &self,
124        map_data: impl Fn(&Self::NodeData) -> U,
125    ) -> crate::tree::Forest<U, crate::tree::parent_pointer::ParentPointerStore<H>> {
126        Forest {
127            roots: self
128                .nodes
129                .set_data
130                .iter()
131                .map(|a| RootData {
132                    root_id: a.root_pointer.into(),
133                    data: map_data(&a.data.as_ref().unwrap().data),
134                })
135                .collect(),
136            nodes: self
137                .nodes
138                .nodes
139                .iter()
140                .map(|a| {
141                    let ad = a.get();
142                    let n = match &ad {
143                        UFNode::Child(c) => PPNode::dataless_child((*c).into()),
144                        UFNode::Root { set_data_idx, .. } => {
145                            PPNode::dataless_root(RootId(set_data_idx.0))
146                        }
147                    };
148
149                    a.set(ad);
150
151                    n
152                })
153                .collect(),
154        }
155    }
156
157    fn node_len(&self) -> usize {
158        self.nodes.n_sets()
159    }
160
161    fn check_and_set_nodes(&mut self) -> Result<(), crate::half_edge::HedgeGraphError> {
162        Ok(())
163    }
164
165    fn map_data_ref_graph<'a, E, V2>(
166        &'a self,
167        graph: &'a crate::half_edge::HedgeGraph<E, Self::NodeData, Self>,
168        mut node_map: impl FnMut(
169            &'a crate::half_edge::HedgeGraph<E, Self::NodeData, Self>,
170            Self::NeighborsIter<'a>,
171            &'a Self::NodeData,
172        ) -> V2,
173    ) -> Self::OpStorage<V2> {
174        UnionFindNodeStore {
175            nodes: self.nodes.map_set_data_ref(|n| HedgeNodeStore {
176                data: node_map(graph, (&n.node).into(), &n.data),
177                node: n.node.clone(),
178            }),
179        }
180    }
181
182    fn map_data_ref_mut_graph<'a, V2>(
183        &'a mut self,
184        mut node_map: impl FnMut(Self::NeighborsIter<'a>, &'a mut Self::NodeData) -> V2,
185    ) -> Self::OpStorage<V2> {
186        UnionFindNodeStore {
187            nodes: self.nodes.map_set_data_ref_mut(|n| HedgeNodeStore {
188                data: node_map((&n.node).into(), &mut n.data),
189                node: n.node.clone(),
190            }),
191        }
192    }
193
194    fn map_data_ref_graph_result<'a, E, V2, Er>(
195        &'a self,
196        graph: &'a crate::half_edge::HedgeGraph<E, Self::NodeData, Self>,
197        mut node_map: impl FnMut(
198            &'a crate::half_edge::HedgeGraph<E, Self::NodeData, Self>,
199            Self::NeighborsIter<'a>,
200            &'a Self::NodeData,
201        ) -> Result<V2, Er>,
202    ) -> Result<Self::OpStorage<V2>, Er> {
203        Ok(UnionFindNodeStore {
204            nodes: self.nodes.map_set_data_ref_result(|n| {
205                match node_map(graph, (&n.node).into(), &n.data) {
206                    Ok(data) => Ok(HedgeNodeStore {
207                        data,
208                        node: n.node.clone(),
209                    }),
210                    Err(err) => Err(err),
211                }
212            })?,
213        })
214    }
215
216    fn iter_nodes(
217        &self,
218    ) -> impl Iterator<Item = (Self::NeighborsIter<'_>, NodeIndex, &Self::NodeData)> {
219        self.nodes
220            .iter_set_data()
221            .map(|(i, d)| ((&d.node).into(), NodeIndex(i.0), &d.data))
222    }
223    fn iter_nodes_mut(
224        &mut self,
225    ) -> impl Iterator<Item = (Self::NeighborsIter<'_>, NodeIndex, &mut Self::NodeData)> {
226        self.nodes
227            .iter_set_data_mut()
228            .map(|(i, d)| ((&d.node).into(), NodeIndex(i.0), &mut d.data))
229    }
230
231    fn node_id_ref(&self, hedge: crate::half_edge::involution::Hedge) -> NodeIndex {
232        NodeIndex(self.nodes.find_data_index(hedge).0)
233    }
234
235    fn get_node_data_mut(&mut self, node_id: NodeIndex) -> &mut Self::NodeData {
236        &mut self.nodes[SetIndex(node_id.0)].data
237    }
238
239    fn iter_node_id(&self) -> impl Iterator<Item = NodeIndex> {
240        self.nodes.iter_set_data().map(|(i, _)| NodeIndex(i.0))
241    }
242
243    fn get_node_data(&self, node_id: NodeIndex) -> &Self::NodeData {
244        &self.nodes[SetIndex(node_id.0)].data
245    }
246
247    fn map_data_graph<'a, V2>(
248        self,
249        involution: &'a crate::half_edge::involution::Involution<
250            crate::half_edge::involution::EdgeIndex,
251        >,
252        mut f: impl FnMut(
253            &'a crate::half_edge::involution::Involution<crate::half_edge::involution::EdgeIndex>,
254            NodeIndex,
255            Self::NodeData,
256        ) -> V2,
257    ) -> Self::OpStorage<V2> {
258        UnionFindNodeStore {
259            nodes: self.nodes.map_set_data(|i, n| HedgeNodeStore {
260                data: f(involution, NodeIndex(i.0), n.data),
261                node: n.node.clone(),
262            }),
263        }
264    }
265
266    fn extend(mut self, other: Self) -> Self {
267        self.nodes.extend(other.nodes);
268        self
269    }
270
271    fn extend_mut(&mut self, other: Self) {
272        self.nodes.extend(other.nodes);
273    }
274
275    fn iter(&self) -> impl Iterator<Item = (NodeIndex, &Self::NodeData)> {
276        self.nodes
277            .iter_set_data()
278            .map(|(i, d)| (NodeIndex(i.0), &d.data))
279    }
280
281    fn build<
282        I: IntoIterator<Item = crate::half_edge::builder::HedgeNodeBuilder<Self::NodeData>>,
283    >(
284        nodes: I,
285        n_hedges: usize,
286    ) -> Self {
287        NodeStorageVec::build(nodes, n_hedges).into()
288    }
289
290    fn drain(self) -> impl Iterator<Item = (NodeIndex, Self::NodeData)> {
291        self.nodes
292            .drain_set_data()
293            .map(|(s, d)| (NodeIndex(s.0), d.data))
294    }
295
296    fn random(sources: &[Self::Neighbors], sinks: &[Self::Neighbors]) -> Self
297    where
298        Self::NodeData: Default,
299    {
300        NodeStorageVec::random(sources, sinks).into()
301    }
302
303    fn add_dangling_edge(
304        mut self,
305        source: NodeIndex,
306    ) -> Result<Self, crate::half_edge::HedgeGraphError> {
307        let setid = SetIndex(source.0);
308        let _ = self.nodes.add_child(setid);
309        self.nodes.iter_set_data_mut().for_each(|(s, n)| {
310            if s == setid {
311                n.node.push(true);
312            } else {
313                n.node.push(false);
314            }
315        });
316        Ok(self)
317    }
318}
linnet/half_edge/nodestore/bitvec_find.rs

linnet/half_edge/nodestore/
bitvec_find.rs
