1use crate::{bit_indexed_array::*, flag::*, result::*, traits::*};
2use super::{lnode::{self, *}, mnode::*, snode::{self, *}};
3use alloc::{boxed::Box, borrow::Cow, fmt::Debug, sync::Arc, vec::Vec};
4use core::ptr;
5
6#[derive(Debug)]
7pub(crate) struct CNode <H: Hashword, F: Flagword<H>, K: Key, V: Value, M: 'static> {
8 nodes: Arc<dyn BitIndexedArray::<F, MNode<H, F, K, V, M>, usize>>,
9}
10
11impl <H: Hashword, F: Flagword<H>, K: Key, V: Value, M: HasherBv<H, K>> CNode<H, F, K, V, M> {
12 #[must_use]
13 pub(super) fn new(nodes: Box<dyn BitIndexedArray::<F, MNode<H, F, K, V, M>, usize> + 'static>) -> Self {
14 Self { nodes: nodes.into() }
15 }
16
17 #[must_use]
18 pub(super) fn size(&self) -> usize {
19 *self.nodes.extra()
20 }
21
22 pub(super) fn find<'a, L: Key>(&'a self, key: &L, flag: Option<Flag<H, F>>) -> FindResult<'a, K, V> where K: PartialEq<L>, <F as core::convert::TryFrom<<H as core::ops::BitAnd>::Output>>::Error: core::fmt::Debug {
23 match self.nodes.at(flag.as_ref().unwrap().flag.clone()) {
24 Ok(node) => match node {
25 MNode::C(cnode) => cnode.find(key, flag.unwrap().next()),
26 MNode::L(lnode) => lnode.find(key),
27 MNode::S(snode) => snode.find(key),
28 },
29 Err(_) => FindResult::NotFound
30 }
31 }
32
33 pub(super) fn remove<'a, L: Key>(&'a self, key: &L, flag: Option<Flag<H, F>>) -> RemoveResult<'a, H, F, K, V, M> where K: PartialEq<L>, M: HasherBv<H, L>, <F as core::convert::TryFrom<<H as core::ops::BitAnd>::Output>>::Error: core::fmt::Debug {
34 match self.nodes.at(flag.as_ref().unwrap().flag.clone()) {
35 Ok(node) => match node.remove(key, flag.as_ref().unwrap().next()) {
36 RemoveResult::NotFound => RemoveResult::NotFound,
37 RemoveResult::RemovedC(node, key, value) => {
38 if node.size() == 0 {
39 panic!()
40 }
41 RemoveResult::RemovedC(Self::new(self.nodes.updated(flag.unwrap().flag, Cow::Owned(MNode::C(node)), Cow::Owned(self.size() - 1)).unwrap()), key, value)
42 },
43 RemoveResult::RemovedL(node, key, value) => {
44 RemoveResult::RemovedC(Self::new(self.nodes.updated(flag.unwrap().flag, Cow::Owned(MNode::L(node)), Cow::Owned(self.size() - 1)).unwrap()), key, value)
45 },
46 RemoveResult::RemovedS(node, key, value) => {
47 RemoveResult::RemovedC(Self::new(self.nodes.updated(flag.unwrap().flag, Cow::Owned(MNode::S(node)), Cow::Owned(self.size() - 1)).unwrap()), key, value)
48 },
49 RemoveResult::RemovedZ(key, value) => {
50 if self.size() == 1 {
51 RemoveResult::RemovedZ(key, value)
52 }
53 else {
54 RemoveResult::RemovedC(Self::new(self.nodes.removed(flag.unwrap().flag, Cow::Owned(self.size() - 1)).unwrap()), key, value)
55 }
56 },
57 },
58 Err(_) => RemoveResult::NotFound
59 }
60 }
61
62 pub(super) fn visit<Op: Clone>(&self, op: Op) where Op: Fn(&K, &V) {
63 for node in self.nodes.as_ref() {
64 match node {
65 MNode::C(cnode) => cnode.visit(op.clone()),
66 MNode::L(lnode) => lnode.visit(op.clone()),
67 MNode::S(snode) => snode.visit(op.clone()),
68 }
69 }
70 }
71
72}
73
74impl <H: Hashword, F: Flagword<H>, K: Key, V: Value, M: HasherBv<H, K>> CNode<H, F, K, V, M> {
75 pub(super) fn insert<'a, L: Key + Into<K>, W: Into<V>>(&'a self, key: L, value: W, flag: Option<Flag<H, F>>, replace: bool) -> CNodeInsertResult<'a, H, F, K, V, M>
76 where
77 K: HashLike<L>,
78 K: PartialEq<L>,
79 M: HasherBv<H, L>,
80 <F as core::convert::TryFrom<<H as core::ops::BitAnd>::Output>>::Error: core::fmt::Debug
81 {
82 match self.nodes.at(flag.as_ref().unwrap().flag.clone()) {
83 Ok(node) => match node {
84 MNode::C(cnode) => match cnode.insert(key, value, flag.as_ref().unwrap().next(), replace) {
85 CNodeInsertResult::Found(key, value) => CNodeInsertResult::Found(key, value),
86 CNodeInsertResult::InsertedC(cnode2, key, value, prev) => {
87 let size = self.size() + cnode2.size() - cnode.size();
88 CNodeInsertResult::InsertedC(Self::new(self.nodes.updated(flag.unwrap().flag, Cow::Owned(MNode::C(cnode2)), Cow::Owned(size)).unwrap()), key, value, prev)
89 },
90 },
91 MNode::L(lnode) => match lnode::insert(&lnode, key, value, flag.as_ref().unwrap().next(), replace) {
92 LNodeInsertResult::Found(key, value) => CNodeInsertResult::Found(key, value),
93 LNodeInsertResult::InsertedC(cnode, key, value, prev) => CNodeInsertResult::InsertedC(Self::new(self.nodes.updated(flag.unwrap().flag, Cow::Owned(MNode::C(cnode)), Cow::Owned(self.size() + 1)).unwrap()), key, value, prev),
94 LNodeInsertResult::InsertedL(lnode2, key, value, prev) => {
95 let size = self.size() + lnode2.size() - lnode.size();
96 CNodeInsertResult::InsertedC(Self::new(self.nodes.updated(flag.unwrap().flag, Cow::Owned(MNode::L(lnode2)), Cow::Owned(size)).unwrap()), key, value, prev)
97 },
98 },
99 MNode::S(snode) => match snode::insert(&snode, key, value, flag.as_ref().unwrap().next(), replace) {
100 InsertResult::Found(key, value) => CNodeInsertResult::Found(key, value),
101 InsertResult::InsertedC(cnode, key, value, prev) => CNodeInsertResult::InsertedC(Self::new(self.nodes.updated(flag.unwrap().flag, Cow::Owned(MNode::C(cnode)), Cow::Owned(self.size() + 1)).unwrap()), key, value, prev),
102 InsertResult::InsertedL(lnode, key, value, prev) => CNodeInsertResult::InsertedC(Self::new(self.nodes.updated(flag.unwrap().flag, Cow::Owned(MNode::L(lnode)), Cow::Owned(self.size() + 1)).unwrap()), key, value, prev),
103 InsertResult::InsertedS(snode, key, value, prev) => CNodeInsertResult::InsertedC(Self::new(self.nodes.updated(flag.unwrap().flag, Cow::Owned(MNode::S(snode)), Cow::Owned(self.size())).unwrap()), key, value, prev),
104 },
105 },
106 Err(_) => {
107 let snode = SNode::new(key.into(), value.into());
108 let key: *const K = snode.key();
109 let value: *const V = snode.value();
110 CNodeInsertResult::InsertedC(Self::new(self.nodes.inserted(flag.unwrap().flag, Cow::Owned(MNode::S(snode)), Cow::Owned(self.size() + 1)).unwrap()), key, value, None)
111 }
112 }
113 }
114}
115
116pub(super) fn transform<H: Hashword, F: Flagword<H>, K: Key, V: Value, M: HasherBv<H, K>, ReduceT, ReduceOp, Op>(this: &CNode<H, F, K, V, M>, reduce_op: ReduceOp, op: Op) -> MNodeTransformResult<H, F, K, V, M, ReduceT>
117where
118 ReduceT: Default,
119 ReduceOp: Fn(&ReduceT, &ReduceT) -> ReduceT + Clone,
120 Op: Fn(&K, &V) -> MapTransformResult<V, ReduceT> + Clone,
121 <F as core::convert::TryFrom<<H as core::ops::BitAnd>::Output>>::Error: core::fmt::Debug
122{
123 let mut size = 0;
124 let mut bits_t = F::default();
125 let mut values_t = Vec::default();
126 let mut reduced = ReduceT::default();
127 let mut changed = false;
128
129 for index in 0..<F>::max_ones() {
130 if let Ok(node) = this.nodes.at_bit_index(index) {
131 match node.transform(reduce_op.clone(), op.clone()) {
132 MNodeTransformResult::Unchanged(r) => {
133 size += node.size();
134 bits_t = bits_t.bit_insert(<F>::nth_bit(index).unwrap()).unwrap();
135 values_t.push(node.clone());
136 reduced = reduce_op(&reduced, &r);
137 },
138 MNodeTransformResult::C(cnode, r) => {
139 size += cnode.size();
140 bits_t = bits_t.bit_insert(<F>::nth_bit(index).unwrap()).unwrap();
141 values_t.push(MNode::C(cnode));
142 reduced = reduce_op(&reduced, &r);
143 changed = true;
144 },
145 MNodeTransformResult::L(lnode, r) => {
146 size += lnode.size();
147 bits_t = bits_t.bit_insert(<F>::nth_bit(index).unwrap()).unwrap();
148 values_t.push(MNode::L(lnode));
149 reduced = reduce_op(&reduced, &r);
150 changed = true;
151 },
152 MNodeTransformResult::S(snode, r) => {
153 size += 1;
154 bits_t = bits_t.bit_insert(<F>::nth_bit(index).unwrap()).unwrap();
155 values_t.push(MNode::S(snode));
156 reduced = reduce_op(&reduced, &r);
157 changed = true;
158 },
159 MNodeTransformResult::Removed(r) => {
160 reduced = reduce_op(&reduced, &r);
161 changed = true;
162 },
163 }
164 }
165 }
166
167 if changed {
168 match values_t.len() {
169 0 => MNodeTransformResult::Removed(reduced),
170 1 => match values_t.pop().unwrap() {
171 MNode::C(cnode) => MNodeTransformResult::C(CNode::new(new_bit_indexed_array(bits_t, BitIndexedArrayVec::new(&[MNode::C(cnode)]), size).unwrap()), reduced),
172 MNode::L(lnode) => MNodeTransformResult::L(lnode, reduced),
173 MNode::S(snode) => MNodeTransformResult::S(snode, reduced),
174 },
175 _ => MNodeTransformResult::C(CNode::new(new_bit_indexed_array(bits_t, BitIndexedArrayVec::new(&values_t), size).unwrap()), reduced),
176 }
177 }
178 else {
179 MNodeTransformResult::Unchanged(reduced)
180 }
181}
182
183
184pub(super) unsafe fn transmute<H: Hashword, F: Flagword<H>, K: Key, V: Value, S: Key, X: Value, M: HasherBv<H, K>, ReduceT, ReduceOp, Op>(this: &CNode<H, F, K, V, M>, reduce_op: ReduceOp, op: Op) -> MNodeTransmuteResult<H, F, S, X, M, ReduceT>
185where
186 ReduceT: Default,
187 ReduceOp: Fn(&ReduceT, &ReduceT) -> ReduceT + Clone,
188 Op: Fn(&K, &V) -> MapTransmuteResult<S, X, ReduceT> + Clone,
189 K: HashLike<S>,
190 K: PartialEq<S>,
191 M: HasherBv<H, S>,
192 <F as core::convert::TryFrom<<H as core::ops::BitAnd>::Output>>::Error: core::fmt::Debug
193{
194 let mut size = 0;
195 let mut bits_t = F::default();
196 let mut values_t = Vec::default();
197 let mut reduced = ReduceT::default();
198
199 for index in 0..<F>::max_ones() {
200 if let Ok(node) = this.nodes.at_bit_index(index) {
201 match node.transmute(reduce_op.clone(), op.clone()) {
202 MNodeTransmuteResult::C(cnode, r) => {
203 size += cnode.size();
204 bits_t = bits_t.bit_insert(<F>::nth_bit(index).unwrap()).unwrap();
205 values_t.push(MNode::C(cnode));
206 reduced = reduce_op(&reduced, &r);
207 },
208 MNodeTransmuteResult::L(lnode, r) => {
209 size += lnode.size();
210 bits_t = bits_t.bit_insert(<F>::nth_bit(index).unwrap()).unwrap();
211 values_t.push(MNode::L(lnode));
212 reduced = reduce_op(&reduced, &r);
213 },
214 MNodeTransmuteResult::S(snode, r) => {
215 size += 1;
216 bits_t = bits_t.bit_insert(<F>::nth_bit(index).unwrap()).unwrap();
217 values_t.push(MNode::S(snode));
218 reduced = reduce_op(&reduced, &r);
219 },
220 MNodeTransmuteResult::Removed(r) => {
221 reduced = reduce_op(&reduced, &r);
222 },
223 }
224 }
225 }
226
227 assert_eq!(values_t.len(), bits_t.count_ones_t());
228
229 match values_t.len() {
230 0 => MNodeTransmuteResult::Removed(reduced),
231 1 => match values_t.pop().unwrap() {
232 MNode::C(cnode) => MNodeTransmuteResult::C(CNode::new(new_bit_indexed_array(bits_t, BitIndexedArrayVec::new(&[MNode::C(cnode)]), size).unwrap()), reduced),
233 MNode::L(lnode) => MNodeTransmuteResult::L(lnode, reduced),
234 MNode::S(snode) => MNodeTransmuteResult::S(snode, reduced),
235 },
236 _ => MNodeTransmuteResult::C(CNode::new(new_bit_indexed_array(bits_t, BitIndexedArrayVec::new(&values_t), size).unwrap()), reduced),
237 }
238}
239
240pub(crate) fn transform_with_transformed<H: Hashword, F: Flagword<H>, K: Key, V: Value, M: HasherBv<H, K>, ReduceT, ReduceOp, BothOp, LeftOp, RightOp>(this: &CNode<H, F, K, V, M>, right: &MNode<H, F, K, V, M>, reduce_op: ReduceOp, both_op: BothOp, left_op: LeftOp, right_op: RightOp, depth: usize) -> MNodeJointTransformResult<H, F, K, V, M, ReduceT>
241where
242 ReduceT: Default,
243 ReduceOp: Fn(&ReduceT, &ReduceT) -> ReduceT + Clone,
244 BothOp: Fn(&K, &V, &K, &V) -> MapJointTransformResult<V, ReduceT> + Clone,
245 LeftOp: Fn(&K, &V) -> MapTransformResult<V, ReduceT> + Clone,
246 RightOp: Fn(&K, &V) -> MapTransformResult<V, ReduceT> + Clone,
247 <F as core::convert::TryFrom<<H as core::ops::BitAnd>::Output>>::Error: core::fmt::Debug
248{
249 match right {
250 MNode::C(cnode) => transform_with_transformed_cnode(this, cnode, reduce_op, both_op, left_op, right_op, depth),
251 MNode::L(lnode) => transform_with_transformed_lnode(this, lnode, reduce_op, both_op, left_op, right_op, depth),
252 MNode::S(snode) => transform_with_transformed_snode(this, snode, reduce_op, both_op, left_op, right_op, depth),
253 }
254}
255
256pub(crate) unsafe fn transform_with_transmuted<H: Hashword, F: Flagword<H>, K: Key, V: Value, L: Key, W: Value, M: HasherBv<H, K>, ReduceT, ReduceOp, BothOp, LeftOp, RightOp>(this: &CNode<H, F, K, V, M>, right: &MNode<H, F, L, W, M>, reduce_op: ReduceOp, both_op: BothOp, left_op: LeftOp, right_op: RightOp, depth: usize) -> MNodeTransformResult<H, F, K, V, M, ReduceT>
257where
258 ReduceT: Default,
259 ReduceOp: Fn(&ReduceT, &ReduceT) -> ReduceT + Clone,
260 BothOp: Fn(&K, &V, &L, &W) -> MapTransformResult<V, ReduceT> + Clone,
261 LeftOp: Fn(&K, &V) -> MapTransformResult<V, ReduceT> + Clone,
262 RightOp: Fn(&L, &W) -> MapTransmuteResult<K, V, ReduceT> + Clone,
263 K: HashLike<L>,
264 K: PartialEq<L>,
265 L: HashLike<K>,
266 L: PartialEq<K>,
267 M: HasherBv<H, L>,
268 <F as core::convert::TryFrom<<H as core::ops::BitAnd>::Output>>::Error: core::fmt::Debug
269{
270 match right {
271 MNode::C(cnode) => transform_with_transmuted_cnode(this, cnode, reduce_op, both_op, left_op, right_op, depth),
272 MNode::L(lnode) => transform_with_transmuted_lnode(this, lnode, reduce_op, both_op, left_op, right_op, depth),
273 MNode::S(snode) => transform_with_transmuted_snode(this, snode, reduce_op, both_op, left_op, right_op, depth),
274 }
275}
276
277pub(crate) unsafe fn transmute_with_transformed<H: Hashword, F: Flagword<H>, K: Key, V: Value, L: Key, W: Value, M: HasherBv<H, K>, ReduceT, ReduceOp, BothOp, LeftOp, RightOp>(this: &CNode<H, F, K, V, M>, right: &MNode<H, F, L, W, M>, reduce_op: ReduceOp, both_op: BothOp, left_op: LeftOp, right_op: RightOp, depth: usize) -> MNodeTransformResult<H, F, L, W, M, ReduceT>
278where
279 ReduceT: Default,
280 ReduceOp: Fn(&ReduceT, &ReduceT) -> ReduceT + Clone,
281 BothOp: Fn(&K, &V, &L, &W) -> MapTransformResult<W, ReduceT> + Clone,
282 LeftOp: Fn(&K, &V) -> MapTransmuteResult<L, W, ReduceT> + Clone,
283 RightOp: Fn(&L, &W) -> MapTransformResult<W, ReduceT> + Clone,
284 K: HashLike<L>,
285 K: PartialEq<L>,
286 L: HashLike<K>,
287 L: PartialEq<K>,
288 M: HasherBv<H, L>,
289 <F as core::convert::TryFrom<<H as core::ops::BitAnd>::Output>>::Error: core::fmt::Debug
290{
291 match right {
292 MNode::C(cnode) => transmute_with_transformed_cnode(this, cnode, reduce_op, both_op, left_op, right_op, depth),
293 MNode::L(lnode) => transmute_with_transformed_lnode(this, lnode, reduce_op, both_op, left_op, right_op, depth),
294 MNode::S(snode) => transmute_with_transformed_snode(this, snode, reduce_op, both_op, left_op, right_op, depth),
295 }
296}
297
298pub(crate) unsafe fn transmute_with_transmuted<H: Hashword, F: Flagword<H>, K: Key, V: Value, L: Key, W: Value, S: Key, X: Value, M: HasherBv<H, K>, ReduceT, ReduceOp, BothOp, LeftOp, RightOp>(this: &CNode<H, F, K, V, M>, right: &MNode<H, F, L, W, M>, reduce_op: ReduceOp, both_op: BothOp, left_op: LeftOp, right_op: RightOp, depth: usize) -> MNodeTransmuteResult<H, F, S, X, M, ReduceT>
299where
300 ReduceT: Default,
301 ReduceOp: Fn(&ReduceT, &ReduceT) -> ReduceT + Clone,
302 BothOp: Fn(&K, &V, &L, &W) -> MapTransmuteResult<S, X, ReduceT> + Clone,
303 LeftOp: Fn(&K, &V) -> MapTransmuteResult<S, X, ReduceT> + Clone,
304 RightOp: Fn(&L, &W) -> MapTransmuteResult<S, X, ReduceT> + Clone,
305 K: HashLike<L>,
306 K: PartialEq<L>,
307 K: HashLike<S>,
308 K: PartialEq<S>,
309 L: HashLike<K>,
310 L: PartialEq<K>,
311 L: HashLike<S>,
312 L: PartialEq<S>,
313 M: HasherBv<H, L>,
314 M: HasherBv<H, S>,
315 <F as core::convert::TryFrom<<H as core::ops::BitAnd>::Output>>::Error: core::fmt::Debug
316{
317 match right {
318 MNode::C(cnode) => transmute_with_transmuted_cnode(this, cnode, reduce_op, both_op, left_op, right_op, depth),
319 MNode::L(lnode) => transmute_with_transmuted_lnode(this, lnode, reduce_op, both_op, left_op, right_op, depth),
320 MNode::S(snode) => transmute_with_transmuted_snode(this, snode, reduce_op, both_op, left_op, right_op, depth),
321 }
322}
323
324pub(crate) fn transform_with_transformed_cnode<H: Hashword, F: Flagword<H>, K: Key, V: Value, M: HasherBv<H, K>, ReduceT, ReduceOp, BothOp, LeftOp, RightOp>(this: &CNode<H, F, K, V, M>, right: &CNode<H, F, K, V, M>, reduce_op: ReduceOp, both_op: BothOp, left_op: LeftOp, right_op: RightOp, depth: usize) -> MNodeJointTransformResult<H, F, K, V, M, ReduceT>
325where
326 ReduceT: Default,
327 ReduceOp: Fn(&ReduceT, &ReduceT) -> ReduceT + Clone,
328 BothOp: Fn(&K, &V, &K, &V) -> MapJointTransformResult<V, ReduceT> + Clone,
329 LeftOp: Fn(&K, &V) -> MapTransformResult<V, ReduceT> + Clone,
330 RightOp: Fn(&K, &V) -> MapTransformResult<V, ReduceT> + Clone,
331 <F as core::convert::TryFrom<<H as core::ops::BitAnd>::Output>>::Error: core::fmt::Debug
332{
333 let mut size = 0;
334 let mut bits_t = F::default();
335 let mut values_t = Vec::default();
336 let mut reduced = ReduceT::default();
337 let mut unchangedl = true;
338 let mut unchangedr = true;
339
340 for index in 0..<F>::max_ones() {
341 let mut left = None;
342 let mut right_node = None;
343
344 let transform_result = if let Ok(node) = this.nodes.at_bit_index(index) {
345 left = Some(node);
346 if let Ok(right) = right.nodes.at_bit_index(index) {
347 right_node = Some(right);
348 node.transform_with_transformed(right, reduce_op.clone(), both_op.clone(), left_op.clone(), right_op.clone(), depth + 1)
349 }
350 else {
351 match node.transform(reduce_op.clone(), left_op.clone()) {
352 MNodeTransformResult::Unchanged(reduced) => MNodeJointTransformResult::UnchangedL(reduced),
353 MNodeTransformResult::C(cnode, reduced) => MNodeJointTransformResult::C(cnode, reduced),
354 MNodeTransformResult::L(lnode, reduced) => MNodeJointTransformResult::L(lnode, reduced),
355 MNodeTransformResult::S(snode, reduced) => MNodeJointTransformResult::S(snode, reduced),
356 MNodeTransformResult::Removed(reduced) => MNodeJointTransformResult::Removed(reduced),
357 }
358 }
359 }
360 else if let Ok(right) = right.nodes.at_bit_index(index) {
361 right_node = Some(right);
362 match right.transform(reduce_op.clone(), right_op.clone()) {
363 MNodeTransformResult::Unchanged(reduced) => MNodeJointTransformResult::UnchangedR(reduced),
364 MNodeTransformResult::C(cnode, reduced) => MNodeJointTransformResult::C(cnode, reduced),
365 MNodeTransformResult::L(lnode, reduced) => MNodeJointTransformResult::L(lnode, reduced),
366 MNodeTransformResult::S(snode, reduced) => MNodeJointTransformResult::S(snode, reduced),
367 MNodeTransformResult::Removed(reduced) => MNodeJointTransformResult::Removed(reduced),
368 }
369 }
370 else {
371 continue;
372 };
373
374 match transform_result {
375 MNodeJointTransformResult::UnchangedLR(r) => {
376 size += left.unwrap().size();
377 bits_t = bits_t.bit_insert(<F>::nth_bit(index).unwrap()).unwrap();
378 values_t.push(left.unwrap().clone());
379 reduced = reduce_op(&reduced, &r);
380 },
381 MNodeJointTransformResult::UnchangedL(r) => {
382 size += left.unwrap().size();
383 bits_t = bits_t.bit_insert(<F>::nth_bit(index).unwrap()).unwrap();
384 values_t.push(left.unwrap().clone());
385 reduced = reduce_op(&reduced, &r);
386 unchangedr = false;
387 },
388 MNodeJointTransformResult::UnchangedR(r) => {
389 size += right_node.unwrap().size();
390 bits_t = bits_t.bit_insert(<F>::nth_bit(index).unwrap()).unwrap();
391 values_t.push(right_node.unwrap().clone());
392 reduced = reduce_op(&reduced, &r);
393 unchangedl = false;
394 },
395 MNodeJointTransformResult::C(cnode, r) => {
396 size += cnode.size();
397 bits_t = bits_t.bit_insert(<F>::nth_bit(index).unwrap()).unwrap();
398 values_t.push(MNode::C(cnode));
399 reduced = reduce_op(&reduced, &r);
400 unchangedl = false;
401 unchangedr = false;
402 },
403 MNodeJointTransformResult::L(lnode, r) => {
404 size += lnode.size();
405 bits_t = bits_t.bit_insert(<F>::nth_bit(index).unwrap()).unwrap();
406 values_t.push(MNode::L(lnode));
407 reduced = reduce_op(&reduced, &r);
408 unchangedl = false;
409 unchangedr = false;
410 },
411 MNodeJointTransformResult::S(snode, r) => {
412 size += 1;
413 bits_t = bits_t.bit_insert(<F>::nth_bit(index).unwrap()).unwrap();
414 values_t.push(MNode::S(snode));
415 reduced = reduce_op(&reduced, &r);
416 unchangedl = false;
417 unchangedr = false;
418 },
419 MNodeJointTransformResult::Removed(r) => {
420 reduced = reduce_op(&reduced, &r);
421 unchangedl = false;
422 unchangedr = false;
423 },
424 }
425 }
426
427 if unchangedl {
428 if unchangedr {
429 MNodeJointTransformResult::UnchangedLR(reduced)
430 }
431 else {
432 MNodeJointTransformResult::UnchangedL(reduced)
433 }
434 }
435 else if unchangedr {
436 MNodeJointTransformResult::UnchangedR(reduced)
437 }
438 else {
439 match values_t.len() {
440 0 => MNodeJointTransformResult::Removed(reduced),
441 1 => match values_t.pop().unwrap() {
442 MNode::C(_cnode) => MNodeJointTransformResult::C(CNode::new(new_bit_indexed_array(bits_t, BitIndexedArrayVec::new(&values_t), size).unwrap()), reduced),
443 MNode::L(lnode) => MNodeJointTransformResult::L(lnode, reduced),
444 MNode::S(snode) => MNodeJointTransformResult::S(snode, reduced),
445 },
446 _ => MNodeJointTransformResult::C(CNode::new(new_bit_indexed_array(bits_t, BitIndexedArrayVec::new(&values_t), size).unwrap()), reduced),
447 }
448 }
449}
450
451pub(crate) unsafe fn transform_with_transmuted_cnode<H: Hashword, F: Flagword<H>, K: Key, V: Value, L: Key, W: Value, M: HasherBv<H, K>, ReduceT, ReduceOp, BothOp, LeftOp, RightOp>(this: &CNode<H, F, K, V, M>, right: &CNode<H, F, L, W, M>, reduce_op: ReduceOp, both_op: BothOp, left_op: LeftOp, right_op: RightOp, depth: usize) -> MNodeTransformResult<H, F, K, V, M, ReduceT>
452where
453 ReduceT: Default,
454 ReduceOp: Fn(&ReduceT, &ReduceT) -> ReduceT + Clone,
455 BothOp: Fn(&K, &V, &L, &W) -> MapTransformResult<V, ReduceT> + Clone,
456 LeftOp: Fn(&K, &V) -> MapTransformResult<V, ReduceT> + Clone,
457 RightOp: Fn(&L, &W) -> MapTransmuteResult<K, V, ReduceT> + Clone,
458 K: HashLike<L>,
459 K: PartialEq<L>,
460 L: HashLike<K>,
461 L: PartialEq<K>,
462 M: HasherBv<H, L>,
463 <F as core::convert::TryFrom<<H as core::ops::BitAnd>::Output>>::Error: core::fmt::Debug
464{
465 let mut size = 0;
466 let mut bits_t = F::default();
467 let mut values_t = Vec::default();
468 let mut reduced = ReduceT::default();
469 let mut unchangedl = true;
470
471 for index in 0..<F>::max_ones() {
472 let mut left = None;
473
474 let transform_result = if let Ok(node) = this.nodes.at_bit_index(index) {
475 left = Some(node);
476 if let Ok(right) = right.nodes.at_bit_index(index) {
477 node.transform_with_transmuted(right, reduce_op.clone(), both_op.clone(), left_op.clone(), right_op.clone(), depth + 1)
478 }
479 else {
480 node.transform(reduce_op.clone(), left_op.clone())
481 }
482 }
483 else if let Ok(right) = right.nodes.at_bit_index(index) {
484 right.transmute(reduce_op.clone(), right_op.clone()).into()
485 }
486 else {
487 continue;
488 };
489
490 match transform_result {
491 MNodeTransformResult::Unchanged(r) => {
492 size += left.unwrap().size();
493 bits_t = bits_t.bit_insert(<F>::nth_bit(index).unwrap()).unwrap();
494 values_t.push(left.unwrap().clone());
495 reduced = reduce_op(&reduced, &r);
496 },
497 MNodeTransformResult::C(cnode, r) => {
498 size += cnode.size();
499 bits_t = bits_t.bit_insert(<F>::nth_bit(index).unwrap()).unwrap();
500 values_t.push(MNode::C(cnode));
501 reduced = reduce_op(&reduced, &r);
502 unchangedl = false;
503 },
504 MNodeTransformResult::L(lnode, r) => {
505 size += lnode.size();
506 bits_t = bits_t.bit_insert(<F>::nth_bit(index).unwrap()).unwrap();
507 values_t.push(MNode::L(lnode));
508 reduced = reduce_op(&reduced, &r);
509 unchangedl = false;
510 },
511 MNodeTransformResult::S(snode, r) => {
512 size += 1;
513 bits_t = bits_t.bit_insert(<F>::nth_bit(index).unwrap()).unwrap();
514 values_t.push(MNode::S(snode));
515 reduced = reduce_op(&reduced, &r);
516 unchangedl = false;
517 },
518 MNodeTransformResult::Removed(r) => {
519 reduced = reduce_op(&reduced, &r);
520 unchangedl = false;
521 },
522 }
523 }
524
525 if unchangedl {
526 MNodeTransformResult::Unchanged(reduced)
527 }
528 else {
529 match values_t.len() {
530 0 => MNodeTransformResult::Removed(reduced),
531 1 => match values_t.pop().unwrap() {
532 MNode::C(_cnode) => MNodeTransformResult::C(CNode::new(new_bit_indexed_array(bits_t, BitIndexedArrayVec::new(&values_t), size).unwrap()), reduced),
533 MNode::L(lnode) => MNodeTransformResult::L(lnode, reduced),
534 MNode::S(snode) => MNodeTransformResult::S(snode, reduced),
535 },
536 _ => MNodeTransformResult::C(CNode::new(new_bit_indexed_array(bits_t, BitIndexedArrayVec::new(&values_t), size).unwrap()), reduced),
537 }
538 }
539}
540
541pub(crate) unsafe fn transmute_with_transformed_cnode<H: Hashword, F: Flagword<H>, K: Key, V: Value, L: Key, W: Value, M: HasherBv<H, K>, ReduceT, ReduceOp, BothOp, LeftOp, RightOp>(this: &CNode<H, F, K, V, M>, right: &CNode<H, F, L, W, M>, reduce_op: ReduceOp, both_op: BothOp, left_op: LeftOp, right_op: RightOp, depth: usize) -> MNodeTransformResult<H, F, L, W, M, ReduceT>
542where
543 ReduceT: Default,
544 ReduceOp: Fn(&ReduceT, &ReduceT) -> ReduceT + Clone,
545 BothOp: Fn(&K, &V, &L, &W) -> MapTransformResult<W, ReduceT> + Clone,
546 LeftOp: Fn(&K, &V) -> MapTransmuteResult<L, W, ReduceT> + Clone,
547 RightOp: Fn(&L, &W) -> MapTransformResult<W, ReduceT> + Clone,
548 K: HashLike<L>,
549 K: PartialEq<L>,
550 L: HashLike<K>,
551 L: PartialEq<K>,
552 M: HasherBv<H, L>,
553 <F as core::convert::TryFrom<<H as core::ops::BitAnd>::Output>>::Error: core::fmt::Debug
554{
555 let mut size = 0;
556 let mut bits_t = F::default();
557 let mut values_t = Vec::default();
558 let mut reduced = ReduceT::default();
559 let mut unchangedr = true;
560
561 for index in 0..<F>::max_ones() {
562 let mut right_node = None;
563
564 let transform_result = if let Ok(node) = this.nodes.at_bit_index(index) {
565 if let Ok(right) = right.nodes.at_bit_index(index) {
566 right_node = Some(right);
567 node.transmute_with_transformed(right, reduce_op.clone(), both_op.clone(), left_op.clone(), right_op.clone(), depth + 1)
568 }
569 else {
570 node.transmute(reduce_op.clone(), left_op.clone()).into()
571 }
572 }
573 else if let Ok(right) = right.nodes.at_bit_index(index) {
574 right_node = Some(right);
575 right.transform(reduce_op.clone(), right_op.clone())
576 }
577 else {
578 continue;
579 };
580
581 match transform_result {
582 MNodeTransformResult::Unchanged(r) => {
583 size += right_node.unwrap().size();
584 bits_t = bits_t.bit_insert(<F>::nth_bit(index).unwrap()).unwrap();
585 values_t.push(right_node.unwrap().clone());
586 reduced = reduce_op(&reduced, &r);
587 },
588 MNodeTransformResult::C(cnode, r) => {
589 size += cnode.size();
590 bits_t = bits_t.bit_insert(<F>::nth_bit(index).unwrap()).unwrap();
591 values_t.push(MNode::C(cnode));
592 reduced = reduce_op(&reduced, &r);
593 unchangedr = false;
594 },
595 MNodeTransformResult::L(lnode, r) => {
596 size += lnode.size();
597 bits_t = bits_t.bit_insert(<F>::nth_bit(index).unwrap()).unwrap();
598 values_t.push(MNode::L(lnode));
599 reduced = reduce_op(&reduced, &r);
600 unchangedr = false;
601 },
602 MNodeTransformResult::S(snode, r) => {
603 size += 1;
604 bits_t = bits_t.bit_insert(<F>::nth_bit(index).unwrap()).unwrap();
605 values_t.push(MNode::S(snode));
606 reduced = reduce_op(&reduced, &r);
607 unchangedr = false;
608 },
609 MNodeTransformResult::Removed(r) => {
610 reduced = reduce_op(&reduced, &r);
611 unchangedr = false;
612 },
613 }
614 }
615
616 if unchangedr {
617 MNodeTransformResult::Unchanged(reduced)
618 }
619 else {
620 match values_t.len() {
621 0 => MNodeTransformResult::Removed(reduced),
622 1 => match values_t.pop().unwrap() {
623 MNode::C(_cnode) => MNodeTransformResult::C(CNode::new(new_bit_indexed_array(bits_t, BitIndexedArrayVec::new(&values_t), size).unwrap()), reduced),
624 MNode::L(lnode) => MNodeTransformResult::L(lnode, reduced),
625 MNode::S(snode) => MNodeTransformResult::S(snode, reduced),
626 },
627 _ => MNodeTransformResult::C(CNode::new(new_bit_indexed_array(bits_t, BitIndexedArrayVec::new(&values_t), size).unwrap()), reduced),
628 }
629 }
630}
631
632pub(crate) unsafe fn transmute_with_transmuted_cnode<H: Hashword, F: Flagword<H>, K: Key, V: Value, L: Key, S: Key, W: Value, X: Value, M: HasherBv<H, K>, ReduceT, ReduceOp, BothOp, LeftOp, RightOp>(this: &CNode<H, F, K, V, M>, right: &CNode<H, F, L, W, M>, reduce_op: ReduceOp, both_op: BothOp, left_op: LeftOp, right_op: RightOp, depth: usize) -> MNodeTransmuteResult<H, F, S, X, M, ReduceT>
633where
634 ReduceT: Default,
635 ReduceOp: Fn(&ReduceT, &ReduceT) -> ReduceT + Clone,
636 BothOp: Fn(&K, &V, &L, &W) -> MapTransmuteResult<S, X, ReduceT> + Clone,
637 LeftOp: Fn(&K, &V) -> MapTransmuteResult<S, X, ReduceT> + Clone,
638 RightOp: Fn(&L, &W) -> MapTransmuteResult<S, X, ReduceT> + Clone,
639 K: HashLike<L>,
640 K: PartialEq<L>,
641 K: HashLike<S>,
642 K: PartialEq<S>,
643 L: HashLike<K>,
644 L: PartialEq<K>,
645 L: HashLike<S>,
646 L: PartialEq<S>,
647 M: HasherBv<H, L>,
648 M: HasherBv<H, S>,
649 <F as core::convert::TryFrom<<H as core::ops::BitAnd>::Output>>::Error: core::fmt::Debug
650{
651 let mut size = 0;
652 let mut bits_t = F::default();
653 let mut values_t = Vec::default();
654 let mut reduced = ReduceT::default();
655
656 for index in 0..<F>::max_ones() {
657 let transmute_result = if let Ok(node) = this.nodes.at_bit_index(index) {
658 if let Ok(right) = right.nodes.at_bit_index(index) {
659 node.transmute_with_transmuted(right, reduce_op.clone(), both_op.clone(), left_op.clone(), right_op.clone(), depth + 1)
660 }
661 else {
662 node.transmute(reduce_op.clone(), left_op.clone())
663 }
664 }
665 else if let Ok(right) = right.nodes.at_bit_index(index) {
666 right.transmute(reduce_op.clone(), right_op.clone())
667 }
668 else {
669 continue;
670 };
671
672 match transmute_result {
673 MNodeTransmuteResult::C(cnode, r) => {
674 size += cnode.size();
675 bits_t = bits_t.bit_insert(<F>::nth_bit(index).unwrap()).unwrap();
676 values_t.push(MNode::C(cnode));
677 reduced = reduce_op(&reduced, &r);
678 },
679 MNodeTransmuteResult::L(lnode, r) => {
680 size += lnode.size();
681 bits_t = bits_t.bit_insert(<F>::nth_bit(index).unwrap()).unwrap();
682 values_t.push(MNode::L(lnode));
683 reduced = reduce_op(&reduced, &r);
684 },
685 MNodeTransmuteResult::S(snode, r) => {
686 size += 1;
687 bits_t = bits_t.bit_insert(<F>::nth_bit(index).unwrap()).unwrap();
688 values_t.push(MNode::S(snode));
689 reduced = reduce_op(&reduced, &r);
690 },
691 MNodeTransmuteResult::Removed(r) => {
692 reduced = reduce_op(&reduced, &r);
693 },
694 }
695 }
696
697 match values_t.len() {
698 0 => MNodeTransmuteResult::Removed(reduced),
699 1 => match values_t.pop().unwrap() {
700 MNode::C(_cnode) => MNodeTransmuteResult::C(CNode::new(new_bit_indexed_array(bits_t, BitIndexedArrayVec::new(&values_t), size).unwrap()), reduced),
701 MNode::L(lnode) => MNodeTransmuteResult::L(lnode, reduced),
702 MNode::S(snode) => MNodeTransmuteResult::S(snode, reduced),
703 },
704 _ => MNodeTransmuteResult::C(CNode::new(new_bit_indexed_array(bits_t, BitIndexedArrayVec::new(&values_t), size).unwrap()), reduced),
705 }
706}
707
708pub(crate) fn transform_with_transformed_lnode<H: Hashword, F: Flagword<H>, K: Key, V: Value, M: HasherBv<H, K>, ReduceT, ReduceOp, BothOp, LeftOp, RightOp>(this: &CNode<H, F, K, V, M>, right: &Arc<LNode<K, V>>, reduce_op: ReduceOp, both_op: BothOp, left_op: LeftOp, right_op: RightOp, depth: usize) -> MNodeJointTransformResult<H, F, K, V, M, ReduceT>
709where
710 ReduceT: Default,
711 ReduceOp: Fn(&ReduceT, &ReduceT) -> ReduceT + Clone,
712 BothOp: Fn(&K, &V, &K, &V) -> MapJointTransformResult<V, ReduceT> + Clone,
713 LeftOp: Fn(&K, &V) -> MapTransformResult<V, ReduceT> + Clone,
714 RightOp: Fn(&K, &V) -> MapTransformResult<V, ReduceT> + Clone,
715 <F as core::convert::TryFrom<<H as core::ops::BitAnd>::Output>>::Error: core::fmt::Debug
716{
717 let flag = Flag::<H, F>::new_at_depth(M::default().hash(right.key()), depth).unwrap().flag();
718
719 let mut size = 0;
720 let mut bits_t = F::default();
721 let mut values_t = Vec::default();
722 let mut reduced = ReduceT::default();
723 let mut unchangedl = true;
724 let mut unchangedr = true;
725
726 for index in 0..<F>::max_ones() {
727 let mut left = None;
728
729 let transform_result = if let Ok(node) = this.nodes.at_bit_index(index) {
730 left = Some(node);
731 if flag == F::nth_bit(index).unwrap() {
732 node.transform_with_transformed_lnode(right, reduce_op.clone(), both_op.clone(), left_op.clone(), right_op.clone(), depth + 1)
733 }
734 else {
735 match node.transform(reduce_op.clone(), left_op.clone()) {
736 MNodeTransformResult::Unchanged(reduced) => MNodeJointTransformResult::UnchangedL(reduced),
737 MNodeTransformResult::C(cnode, reduced) => MNodeJointTransformResult::C(cnode, reduced),
738 MNodeTransformResult::L(lnode, reduced) => MNodeJointTransformResult::L(lnode, reduced),
739 MNodeTransformResult::S(snode, reduced) => MNodeJointTransformResult::S(snode, reduced),
740 MNodeTransformResult::Removed(reduced) => MNodeJointTransformResult::Removed(reduced),
741 }
742 }
743 }
744 else if flag == F::nth_bit(index).unwrap() {
745 match lnode::transform(right, reduce_op.clone(), right_op.clone()) {
746 LNodeTransformResult::Unchanged(reduced) => MNodeJointTransformResult::UnchangedR(reduced),
747 LNodeTransformResult::L(lnode, reduced) => MNodeJointTransformResult::L(lnode, reduced),
748 LNodeTransformResult::S(snode, reduced) => MNodeJointTransformResult::S(snode, reduced),
749 LNodeTransformResult::Removed(reduced) => MNodeJointTransformResult::Removed(reduced),
750 }
751 }
752 else {
753 continue;
754 };
755
756 match transform_result {
757 MNodeJointTransformResult::UnchangedLR(r) => {
758 size += left.unwrap().size();
759 bits_t = bits_t.bit_insert(<F>::nth_bit(index).unwrap()).unwrap();
760 values_t.push(left.unwrap().clone());
761 reduced = reduce_op(&reduced, &r);
762 },
763 MNodeJointTransformResult::UnchangedL(r) => {
764 size += left.unwrap().size();
765 bits_t = bits_t.bit_insert(<F>::nth_bit(index).unwrap()).unwrap();
766 values_t.push(left.unwrap().clone());
767 reduced = reduce_op(&reduced, &r);
768 unchangedr = false;
769 },
770 MNodeJointTransformResult::UnchangedR(r) => {
771 size += right.size();
772 bits_t = bits_t.bit_insert(<F>::nth_bit(index).unwrap()).unwrap();
773 values_t.push(MNode::L(right.clone()));
774 reduced = reduce_op(&reduced, &r);
775 unchangedl = false;
776 },
777 MNodeJointTransformResult::C(cnode, r) => {
778 size += cnode.size();
779 bits_t = bits_t.bit_insert(<F>::nth_bit(index).unwrap()).unwrap();
780 values_t.push(MNode::C(cnode));
781 reduced = reduce_op(&reduced, &r);
782 unchangedl = false;
783 unchangedr = false;
784 },
785 MNodeJointTransformResult::L(lnode, r) => {
786 size += lnode.size();
787 bits_t = bits_t.bit_insert(<F>::nth_bit(index).unwrap()).unwrap();
788 values_t.push(MNode::L(lnode));
789 reduced = reduce_op(&reduced, &r);
790 unchangedl = false;
791 unchangedr = false;
792 },
793 MNodeJointTransformResult::S(snode, r) => {
794 size += 1;
795 bits_t = bits_t.bit_insert(<F>::nth_bit(index).unwrap()).unwrap();
796 values_t.push(MNode::S(snode));
797 reduced = reduce_op(&reduced, &r);
798 unchangedl = false;
799 unchangedr = false;
800 },
801 MNodeJointTransformResult::Removed(r) => {
802 reduced = reduce_op(&reduced, &r);
803 unchangedl = false;
804 unchangedr = false;
805 },
806 }
807 }
808
809 if unchangedl {
810 if unchangedr {
811 MNodeJointTransformResult::UnchangedLR(reduced)
812 }
813 else {
814 MNodeJointTransformResult::UnchangedL(reduced)
815 }
816 }
817 else if unchangedr {
818 MNodeJointTransformResult::UnchangedR(reduced)
819 }
820 else {
821 match values_t.len() {
822 0 => MNodeJointTransformResult::Removed(reduced),
823 1 => match values_t.pop().unwrap() {
824 MNode::C(_cnode) => MNodeJointTransformResult::C(CNode::new(new_bit_indexed_array(bits_t, BitIndexedArrayVec::new(&values_t), size).unwrap()), reduced),
825 MNode::L(lnode) => MNodeJointTransformResult::L(lnode, reduced),
826 MNode::S(snode) => MNodeJointTransformResult::S(snode, reduced),
827 },
828 _ => MNodeJointTransformResult::C(CNode::new(new_bit_indexed_array(bits_t, BitIndexedArrayVec::new(&values_t), size).unwrap()), reduced),
829 }
830 }
831}
832
833pub(crate) unsafe fn transform_with_transmuted_lnode<H: Hashword, F: Flagword<H>, K: Key, V: Value, L: Key, W: Value, M: HasherBv<H, K>, ReduceT, ReduceOp, BothOp, LeftOp, RightOp>(this: &CNode<H, F, K, V, M>, right: &Arc<LNode<L, W>>, reduce_op: ReduceOp, both_op: BothOp, left_op: LeftOp, right_op: RightOp, depth: usize) -> MNodeTransformResult<H, F, K, V, M, ReduceT>
834where
835 ReduceT: Default,
836 ReduceOp: Fn(&ReduceT, &ReduceT) -> ReduceT + Clone,
837 BothOp: Fn(&K, &V, &L, &W) -> MapTransformResult<V, ReduceT> + Clone,
838 LeftOp: Fn(&K, &V) -> MapTransformResult<V, ReduceT> + Clone,
839 RightOp: Fn(&L, &W) -> MapTransmuteResult<K, V, ReduceT> + Clone,
840 K: HashLike<L>,
841 K: PartialEq<L>,
842 L: HashLike<K>,
843 L: PartialEq<K>,
844 M: HasherBv<H, L>,
845 <F as core::convert::TryFrom<<H as core::ops::BitAnd>::Output>>::Error: core::fmt::Debug
846{
847 let flag = Flag::<H, F>::new_at_depth(M::default().hash(right.key()), depth).unwrap().flag();
848
849 let mut size = 0;
850 let mut bits_t = F::default();
851 let mut values_t = Vec::default();
852 let mut reduced = ReduceT::default();
853 let mut unchangedl = true;
854
855 for index in 0..<F>::max_ones() {
856 let mut left = None;
857
858 let transform_result = if let Ok(node) = this.nodes.at_bit_index(index) {
859 left = Some(node);
860 if flag == F::nth_bit(index).unwrap() {
861 node.transform_with_transmuted_lnode(right, reduce_op.clone(), both_op.clone(), left_op.clone(), right_op.clone(), depth + 1)
862 }
863 else {
864 node.transform(reduce_op.clone(), left_op.clone())
865 }
866 }
867 else if flag == F::nth_bit(index).unwrap() {
868 lnode::transmute(right, reduce_op.clone(), right_op.clone()).into()
869 }
870 else {
871 continue;
872 };
873
874 match transform_result {
875 MNodeTransformResult::Unchanged(r) => {
876 size += left.unwrap().size();
877 bits_t = bits_t.bit_insert(<F>::nth_bit(index).unwrap()).unwrap();
878 values_t.push(left.unwrap().clone());
879 reduced = reduce_op(&reduced, &r);
880 unchangedl = false;
881 },
882 MNodeTransformResult::C(cnode, r) => {
883 size += cnode.size();
884 bits_t = bits_t.bit_insert(<F>::nth_bit(index).unwrap()).unwrap();
885 values_t.push(MNode::C(cnode));
886 reduced = reduce_op(&reduced, &r);
887 unchangedl = false;
888 },
889 MNodeTransformResult::L(lnode, r) => {
890 size += lnode.size();
891 bits_t = bits_t.bit_insert(<F>::nth_bit(index).unwrap()).unwrap();
892 values_t.push(MNode::L(lnode));
893 reduced = reduce_op(&reduced, &r);
894 unchangedl = false;
895 },
896 MNodeTransformResult::S(snode, r) => {
897 size += 1;
898 bits_t = bits_t.bit_insert(<F>::nth_bit(index).unwrap()).unwrap();
899 values_t.push(MNode::S(snode));
900 reduced = reduce_op(&reduced, &r);
901 unchangedl = false;
902 },
903 MNodeTransformResult::Removed(r) => {
904 reduced = reduce_op(&reduced, &r);
905 unchangedl = false;
906 },
907 }
908 }
909
910 if unchangedl {
911 MNodeTransformResult::Unchanged(reduced)
912 }
913 else {
914 match values_t.len() {
915 0 => MNodeTransformResult::Removed(reduced),
916 1 => match values_t.pop().unwrap() {
917 MNode::C(_cnode) => MNodeTransformResult::C(CNode::new(new_bit_indexed_array(bits_t, BitIndexedArrayVec::new(&values_t), size).unwrap()), reduced),
918 MNode::L(lnode) => MNodeTransformResult::L(lnode, reduced),
919 MNode::S(snode) => MNodeTransformResult::S(snode, reduced),
920 },
921 _ => MNodeTransformResult::C(CNode::new(new_bit_indexed_array(bits_t, BitIndexedArrayVec::new(&values_t), size).unwrap()), reduced),
922 }
923 }
924}
925
926pub(crate) unsafe fn transmute_with_transformed_lnode<H: Hashword, F: Flagword<H>, K: Key, V: Value, L: Key, W: Value, M: HasherBv<H, K>, ReduceT, ReduceOp, BothOp, LeftOp, RightOp>(this: &CNode<H, F, K, V, M>, right: &Arc<LNode<L, W>>, reduce_op: ReduceOp, both_op: BothOp, left_op: LeftOp, right_op: RightOp, depth: usize) -> MNodeTransformResult<H, F, L, W, M, ReduceT>
927where
928 ReduceT: Default,
929 ReduceOp: Fn(&ReduceT, &ReduceT) -> ReduceT + Clone,
930 BothOp: Fn(&K, &V, &L, &W) -> MapTransformResult<W, ReduceT> + Clone,
931 LeftOp: Fn(&K, &V) -> MapTransmuteResult<L, W, ReduceT> + Clone,
932 RightOp: Fn(&L, &W) -> MapTransformResult<W, ReduceT> + Clone,
933 K: HashLike<L>,
934 K: PartialEq<L>,
935 L: HashLike<K>,
936 L: PartialEq<K>,
937 M: HasherBv<H, L>,
938 <F as core::convert::TryFrom<<H as core::ops::BitAnd>::Output>>::Error: core::fmt::Debug
939{
940 let flag = Flag::<H, F>::new_at_depth(M::default().hash(right.key()), depth).unwrap().flag();
941
942 let mut size = 0;
943 let mut bits_t = F::default();
944 let mut values_t = Vec::default();
945 let mut reduced = ReduceT::default();
946 let mut unchangedr = true;
947
948 for index in 0..<F>::max_ones() {
949 let transform_result = if let Ok(node) = this.nodes.at_bit_index(index) {
950 if flag == F::nth_bit(index).unwrap() {
951 node.transmute_with_transformed_lnode(right, reduce_op.clone(), both_op.clone(), left_op.clone(), right_op.clone(), depth + 1)
952 }
953 else {
954 node.transmute(reduce_op.clone(), left_op.clone()).into()
955 }
956 }
957 else if flag == F::nth_bit(index).unwrap() {
958 lnode::transform(right, reduce_op.clone(), right_op.clone()).into()
959 }
960 else {
961 continue;
962 };
963
964 match transform_result {
965 MNodeTransformResult::Unchanged(r) => {
966 size += right.size();
967 bits_t = bits_t.bit_insert(<F>::nth_bit(index).unwrap()).unwrap();
968 values_t.push(MNode::L(right.clone()));
969 reduced = reduce_op(&reduced, &r);
970 unchangedr = false;
971 },
972 MNodeTransformResult::C(cnode, r) => {
973 size += cnode.size();
974 bits_t = bits_t.bit_insert(<F>::nth_bit(index).unwrap()).unwrap();
975 values_t.push(MNode::C(cnode));
976 reduced = reduce_op(&reduced, &r);
977 unchangedr = false;
978 },
979 MNodeTransformResult::L(lnode, r) => {
980 size += lnode.size();
981 bits_t = bits_t.bit_insert(<F>::nth_bit(index).unwrap()).unwrap();
982 values_t.push(MNode::L(lnode));
983 reduced = reduce_op(&reduced, &r);
984 unchangedr = false;
985 },
986 MNodeTransformResult::S(snode, r) => {
987 size += 1;
988 bits_t = bits_t.bit_insert(<F>::nth_bit(index).unwrap()).unwrap();
989 values_t.push(MNode::S(snode));
990 reduced = reduce_op(&reduced, &r);
991 unchangedr = false;
992 },
993 MNodeTransformResult::Removed(r) => {
994 reduced = reduce_op(&reduced, &r);
995 unchangedr = false;
996 },
997 }
998 }
999
1000 if unchangedr {
1001 MNodeTransformResult::Unchanged(reduced)
1002 }
1003 else {
1004 match values_t.len() {
1005 0 => MNodeTransformResult::Removed(reduced),
1006 1 => match values_t.pop().unwrap() {
1007 MNode::C(_cnode) => MNodeTransformResult::C(CNode::new(new_bit_indexed_array(bits_t, BitIndexedArrayVec::new(&values_t), size).unwrap()), reduced),
1008 MNode::L(lnode) => MNodeTransformResult::L(lnode, reduced),
1009 MNode::S(snode) => MNodeTransformResult::S(snode, reduced),
1010 },
1011 _ => MNodeTransformResult::C(CNode::new(new_bit_indexed_array(bits_t, BitIndexedArrayVec::new(&values_t), size).unwrap()), reduced),
1012 }
1013 }
1014}
1015
1016pub(crate) unsafe fn transmute_with_transmuted_lnode<H: Hashword, F: Flagword<H>, K: Key, V: Value, L: Key, S: Key, W: Value, X: Value, M: HasherBv<H, K>, ReduceT, ReduceOp, BothOp, LeftOp, RightOp>(this: &CNode<H, F, K, V, M>, right: &Arc<LNode<L, W>>, reduce_op: ReduceOp, both_op: BothOp, left_op: LeftOp, right_op: RightOp, depth: usize) -> MNodeTransmuteResult<H, F, S, X, M, ReduceT>
1017where
1018 ReduceT: Default,
1019 ReduceOp: Fn(&ReduceT, &ReduceT) -> ReduceT + Clone,
1020 BothOp: Fn(&K, &V, &L, &W) -> MapTransmuteResult<S, X, ReduceT> + Clone,
1021 LeftOp: Fn(&K, &V) -> MapTransmuteResult<S, X, ReduceT> + Clone,
1022 RightOp: Fn(&L, &W) -> MapTransmuteResult<S, X, ReduceT> + Clone,
1023 K: HashLike<L>,
1024 K: PartialEq<L>,
1025 K: HashLike<S>,
1026 K: PartialEq<S>,
1027 L: HashLike<K>,
1028 L: PartialEq<K>,
1029 L: HashLike<S>,
1030 L: PartialEq<S>,
1031 M: HasherBv<H, L>,
1032 M: HasherBv<H, S>,
1033 <F as core::convert::TryFrom<<H as core::ops::BitAnd>::Output>>::Error: core::fmt::Debug
1034{
1035 let flag = Flag::<H, F>::new_at_depth(M::default().hash(right.key()), depth).unwrap().flag();
1036
1037 let mut size = 0;
1038 let mut bits_t = F::default();
1039 let mut values_t = Vec::default();
1040 let mut reduced = ReduceT::default();
1041
1042 for index in 0..<F>::max_ones() {
1043 let transmute_result = if let Ok(node) = this.nodes.at_bit_index(index) {
1044 if flag == F::nth_bit(index).unwrap() {
1045 node.transmute_with_transmuted_lnode(right, reduce_op.clone(), both_op.clone(), left_op.clone(), right_op.clone(), depth + 1)
1046 }
1047 else {
1048 node.transmute(reduce_op.clone(), left_op.clone())
1049 }
1050 }
1051 else if flag == F::nth_bit(index).unwrap() {
1052 lnode::transmute(right, reduce_op.clone(), right_op.clone()).into()
1053 }
1054 else {
1055 continue;
1056 };
1057
1058 match transmute_result {
1059 MNodeTransmuteResult::C(cnode, r) => {
1060 size += cnode.size();
1061 bits_t = bits_t.bit_insert(<F>::nth_bit(index).unwrap()).unwrap();
1062 values_t.push(MNode::C(cnode));
1063 reduced = reduce_op(&reduced, &r);
1064 },
1065 MNodeTransmuteResult::L(lnode, r) => {
1066 size += lnode.size();
1067 bits_t = bits_t.bit_insert(<F>::nth_bit(index).unwrap()).unwrap();
1068 values_t.push(MNode::L(lnode));
1069 reduced = reduce_op(&reduced, &r);
1070 },
1071 MNodeTransmuteResult::S(snode, r) => {
1072 size += 1;
1073 bits_t = bits_t.bit_insert(<F>::nth_bit(index).unwrap()).unwrap();
1074 values_t.push(MNode::S(snode));
1075 reduced = reduce_op(&reduced, &r);
1076 },
1077 MNodeTransmuteResult::Removed(r) => {
1078 reduced = reduce_op(&reduced, &r);
1079 },
1080 }
1081 }
1082
1083 match values_t.len() {
1084 0 => MNodeTransmuteResult::Removed(reduced),
1085 1 => match values_t.pop().unwrap() {
1086 MNode::C(_cnode) => MNodeTransmuteResult::C(CNode::new(new_bit_indexed_array(bits_t, BitIndexedArrayVec::new(&values_t), size).unwrap()), reduced),
1087 MNode::L(lnode) => MNodeTransmuteResult::L(lnode, reduced),
1088 MNode::S(snode) => MNodeTransmuteResult::S(snode, reduced),
1089 },
1090 _ => MNodeTransmuteResult::C(CNode::new(new_bit_indexed_array(bits_t, BitIndexedArrayVec::new(&values_t), size).unwrap()), reduced),
1091 }
1092}
1093
1094pub(crate) fn transform_with_transformed_snode<H: Hashword, F: Flagword<H>, K: Key, V: Value, M: HasherBv<H, K>, ReduceT, ReduceOp, BothOp, LeftOp, RightOp>(this: &CNode<H, F, K, V, M>, right: &Arc<SNode<K, V>>, reduce_op: ReduceOp, both_op: BothOp, left_op: LeftOp, right_op: RightOp, depth: usize) -> MNodeJointTransformResult<H, F, K, V, M, ReduceT>
1095where
1096 ReduceT: Default,
1097 ReduceOp: Fn(&ReduceT, &ReduceT) -> ReduceT + Clone,
1098 BothOp: Fn(&K, &V, &K, &V) -> MapJointTransformResult<V, ReduceT> + Clone,
1099 LeftOp: Fn(&K, &V) -> MapTransformResult<V, ReduceT> + Clone,
1100 RightOp: Fn(&K, &V) -> MapTransformResult<V, ReduceT> + Clone,
1101 <F as core::convert::TryFrom<<H as core::ops::BitAnd>::Output>>::Error: core::fmt::Debug
1102{
1103 let flag = Flag::<H, F>::new_at_depth(M::default().hash(right.key()), depth).unwrap().flag();
1104
1105 let mut size = 0;
1106 let mut bits_t = F::default();
1107 let mut values_t = Vec::default();
1108 let mut reduced = ReduceT::default();
1109 let mut unchangedl = true;
1110 let mut unchangedr = true;
1111
1112 for index in 0..<F>::max_ones() {
1113 let mut left = None;
1114
1115 let transform_result = if let Ok(node) = this.nodes.at_bit_index(index) {
1116 left = Some(node);
1117 if flag == F::nth_bit(index).unwrap() {
1118 node.transform_with_transformed_snode(right, reduce_op.clone(), both_op.clone(), left_op.clone(), right_op.clone(), depth + 1)
1119 }
1120 else {
1121 match node.transform(reduce_op.clone(), left_op.clone()) {
1122 MNodeTransformResult::Unchanged(reduced) => MNodeJointTransformResult::UnchangedL(reduced),
1123 MNodeTransformResult::C(cnode, reduced) => MNodeJointTransformResult::C(cnode, reduced),
1124 MNodeTransformResult::L(lnode, reduced) => MNodeJointTransformResult::L(lnode, reduced),
1125 MNodeTransformResult::S(snode, reduced) => MNodeJointTransformResult::S(snode, reduced),
1126 MNodeTransformResult::Removed(reduced) => MNodeJointTransformResult::Removed(reduced),
1127 }
1128 }
1129 }
1130 else if flag == F::nth_bit(index).unwrap() {
1131 match snode::transform(right, right_op.clone()) {
1132 SNodeTransformResult::Unchanged(reduced) => MNodeJointTransformResult::UnchangedR(reduced),
1133 SNodeTransformResult::S(snode, reduced) => MNodeJointTransformResult::S(snode, reduced),
1134 SNodeTransformResult::Removed(reduced) => MNodeJointTransformResult::Removed(reduced),
1135 }
1136 }
1137 else {
1138 continue;
1139 };
1140
1141 match transform_result {
1142 MNodeJointTransformResult::UnchangedLR(r) => {
1143 size += left.unwrap().size();
1144 bits_t = bits_t.bit_insert(<F>::nth_bit(index).unwrap()).unwrap();
1145 values_t.push(left.unwrap().clone());
1146 reduced = reduce_op(&reduced, &r);
1147 },
1148 MNodeJointTransformResult::UnchangedL(r) => {
1149 size += left.unwrap().size();
1150 bits_t = bits_t.bit_insert(<F>::nth_bit(index).unwrap()).unwrap();
1151 values_t.push(left.unwrap().clone());
1152 reduced = reduce_op(&reduced, &r);
1153 unchangedr = false;
1154 },
1155 MNodeJointTransformResult::UnchangedR(r) => {
1156 size += 1;
1157 bits_t = bits_t.bit_insert(<F>::nth_bit(index).unwrap()).unwrap();
1158 values_t.push(MNode::S(right.clone()));
1159 reduced = reduce_op(&reduced, &r);
1160 unchangedl = false;
1161 },
1162 MNodeJointTransformResult::C(cnode, r) => {
1163 size += cnode.size();
1164 bits_t = bits_t.bit_insert(<F>::nth_bit(index).unwrap()).unwrap();
1165 values_t.push(MNode::C(cnode));
1166 reduced = reduce_op(&reduced, &r);
1167 unchangedl = false;
1168 unchangedr = false;
1169 },
1170 MNodeJointTransformResult::L(lnode, r) => {
1171 size += lnode.size();
1172 bits_t = bits_t.bit_insert(<F>::nth_bit(index).unwrap()).unwrap();
1173 values_t.push(MNode::L(lnode));
1174 reduced = reduce_op(&reduced, &r);
1175 unchangedl = false;
1176 unchangedr = false;
1177 },
1178 MNodeJointTransformResult::S(snode, r) => {
1179 size += 1;
1180 bits_t = bits_t.bit_insert(<F>::nth_bit(index).unwrap()).unwrap();
1181 values_t.push(MNode::S(snode));
1182 reduced = reduce_op(&reduced, &r);
1183 unchangedl = false;
1184 unchangedr = false;
1185 },
1186 MNodeJointTransformResult::Removed(r) => {
1187 reduced = reduce_op(&reduced, &r);
1188 unchangedl = false;
1189 unchangedr = false;
1190 },
1191 }
1192 }
1193
1194 if unchangedl {
1195 if unchangedr {
1196 MNodeJointTransformResult::UnchangedLR(reduced)
1197 }
1198 else {
1199 MNodeJointTransformResult::UnchangedL(reduced)
1200 }
1201 }
1202 else if unchangedr {
1203 MNodeJointTransformResult::UnchangedR(reduced)
1204 }
1205 else {
1206 match values_t.len() {
1207 0 => MNodeJointTransformResult::Removed(reduced),
1208 1 => match values_t.pop().unwrap() {
1209 MNode::C(_cnode) => MNodeJointTransformResult::C(CNode::new(new_bit_indexed_array(bits_t, BitIndexedArrayVec::new(&values_t), size).unwrap()), reduced),
1210 MNode::L(lnode) => MNodeJointTransformResult::L(lnode, reduced),
1211 MNode::S(snode) => MNodeJointTransformResult::S(snode, reduced),
1212 },
1213 _ => MNodeJointTransformResult::C(CNode::new(new_bit_indexed_array(bits_t, BitIndexedArrayVec::new(&values_t), size).unwrap()), reduced),
1214 }
1215 }
1216}
1217
1218pub(crate) unsafe fn transform_with_transmuted_snode<H: Hashword, F: Flagword<H>, K: Key, V: Value, L: Key, W: Value, M: HasherBv<H, K>, ReduceT, ReduceOp, BothOp, LeftOp, RightOp>(this: &CNode<H, F, K, V, M>, right: &Arc<SNode<L, W>>, reduce_op: ReduceOp, both_op: BothOp, left_op: LeftOp, right_op: RightOp, depth: usize) -> MNodeTransformResult<H, F, K, V, M, ReduceT>
1219where
1220 ReduceT: Default,
1221 ReduceOp: Fn(&ReduceT, &ReduceT) -> ReduceT + Clone,
1222 BothOp: Fn(&K, &V, &L, &W) -> MapTransformResult<V, ReduceT> + Clone,
1223 LeftOp: Fn(&K, &V) -> MapTransformResult<V, ReduceT> + Clone,
1224 RightOp: Fn(&L, &W) -> MapTransmuteResult<K, V, ReduceT> + Clone,
1225 K: HashLike<L>,
1226 K: PartialEq<L>,
1227 L: HashLike<K>,
1228 L: PartialEq<K>,
1229 M: HasherBv<H, L>,
1230 <F as core::convert::TryFrom<<H as core::ops::BitAnd>::Output>>::Error: core::fmt::Debug
1231{
1232 let flag = Flag::<H, F>::new_at_depth(M::default().hash(right.key()), depth).unwrap().flag();
1233
1234 let mut size = 0;
1235 let mut bits_t = F::default();
1236 let mut values_t = Vec::default();
1237 let mut reduced = ReduceT::default();
1238 let mut unchangedl = true;
1239
1240 for index in 0..<F>::max_ones() {
1241 let mut left = None;
1242
1243 let transform_result = if let Ok(node) = this.nodes.at_bit_index(index) {
1244 left = Some(node);
1245 if flag == F::nth_bit(index).unwrap() {
1246 node.transform_with_transmuted_snode(right, reduce_op.clone(), both_op.clone(), left_op.clone(), right_op.clone(), depth + 1)
1247 }
1248 else {
1249 node.transform(reduce_op.clone(), left_op.clone())
1250 }
1251 }
1252 else if flag == F::nth_bit(index).unwrap() {
1253 snode::transmute(right, right_op.clone()).into()
1254 }
1255 else {
1256 continue;
1257 };
1258
1259 match transform_result {
1260 MNodeTransformResult::Unchanged(r) => {
1261 size += left.unwrap().size();
1262 bits_t = bits_t.bit_insert(<F>::nth_bit(index).unwrap()).unwrap();
1263 values_t.push(left.unwrap().clone());
1264 reduced = reduce_op(&reduced, &r);
1265 },
1266 MNodeTransformResult::C(cnode, r) => {
1267 size += cnode.size();
1268 bits_t = bits_t.bit_insert(<F>::nth_bit(index).unwrap()).unwrap();
1269 values_t.push(MNode::C(cnode));
1270 reduced = reduce_op(&reduced, &r);
1271 unchangedl = false;
1272 },
1273 MNodeTransformResult::L(lnode, r) => {
1274 size += lnode.size();
1275 bits_t = bits_t.bit_insert(<F>::nth_bit(index).unwrap()).unwrap();
1276 values_t.push(MNode::L(lnode));
1277 reduced = reduce_op(&reduced, &r);
1278 unchangedl = false;
1279 },
1280 MNodeTransformResult::S(snode, r) => {
1281 size += 1;
1282 bits_t = bits_t.bit_insert(<F>::nth_bit(index).unwrap()).unwrap();
1283 values_t.push(MNode::S(snode));
1284 reduced = reduce_op(&reduced, &r);
1285 unchangedl = false;
1286 },
1287 MNodeTransformResult::Removed(r) => {
1288 reduced = reduce_op(&reduced, &r);
1289 unchangedl = false;
1290 },
1291 }
1292 }
1293
1294 if unchangedl {
1295 MNodeTransformResult::Unchanged(reduced)
1296 }
1297 else {
1298 match values_t.len() {
1299 0 => MNodeTransformResult::Removed(reduced),
1300 1 => match values_t.pop().unwrap() {
1301 MNode::C(_cnode) => MNodeTransformResult::C(CNode::new(new_bit_indexed_array(bits_t, BitIndexedArrayVec::new(&values_t), size).unwrap()), reduced),
1302 MNode::L(lnode) => MNodeTransformResult::L(lnode, reduced),
1303 MNode::S(snode) => MNodeTransformResult::S(snode, reduced),
1304 },
1305 _ => MNodeTransformResult::C(CNode::new(new_bit_indexed_array(bits_t, BitIndexedArrayVec::new(&values_t), size).unwrap()), reduced),
1306 }
1307 }
1308}
1309
1310pub(crate) unsafe fn transmute_with_transformed_snode<H: Hashword, F: Flagword<H>, K: Key, V: Value, L: Key, W: Value, M: HasherBv<H, K>, ReduceT, ReduceOp, BothOp, LeftOp, RightOp>(this: &CNode<H, F, K, V, M>, right: &Arc<SNode<L, W>>, reduce_op: ReduceOp, both_op: BothOp, left_op: LeftOp, right_op: RightOp, depth: usize) -> MNodeTransformResult<H, F, L, W, M, ReduceT>
1311where
1312 ReduceT: Default,
1313 ReduceOp: Fn(&ReduceT, &ReduceT) -> ReduceT + Clone,
1314 BothOp: Fn(&K, &V, &L, &W) -> MapTransformResult<W, ReduceT> + Clone,
1315 LeftOp: Fn(&K, &V) -> MapTransmuteResult<L, W, ReduceT> + Clone,
1316 RightOp: Fn(&L, &W) -> MapTransformResult<W, ReduceT> + Clone,
1317 K: HashLike<L>,
1318 K: PartialEq<L>,
1319 L: HashLike<K>,
1320 L: PartialEq<K>,
1321 M: HasherBv<H, L>,
1322 <F as core::convert::TryFrom<<H as core::ops::BitAnd>::Output>>::Error: core::fmt::Debug
1323{
1324 let flag = Flag::<H, F>::new_at_depth(M::default().hash(right.key()), depth).unwrap().flag();
1325
1326 let mut size = 0;
1327 let mut bits_t = F::default();
1328 let mut values_t = Vec::default();
1329 let mut reduced = ReduceT::default();
1330 let mut unchangedr = true;
1331
1332 for index in 0..<F>::max_ones() {
1333 let transform_result = if let Ok(node) = this.nodes.at_bit_index(index) {
1334 if flag == F::nth_bit(index).unwrap() {
1335 node.transmute_with_transformed_snode(right, reduce_op.clone(), both_op.clone(), left_op.clone(), right_op.clone(), depth + 1)
1336 }
1337 else {
1338 node.transmute(reduce_op.clone(), left_op.clone()).into()
1339 }
1340 }
1341 else if flag == F::nth_bit(index).unwrap() {
1342 snode::transform(right, right_op.clone()).into()
1343 }
1344 else {
1345 continue;
1346 };
1347
1348 match transform_result {
1349 MNodeTransformResult::Unchanged(r) => {
1350 size += 1;
1351 bits_t = bits_t.bit_insert(<F>::nth_bit(index).unwrap()).unwrap();
1352 values_t.push(MNode::S(right.clone()));
1353 reduced = reduce_op(&reduced, &r);
1354 },
1355 MNodeTransformResult::C(cnode, r) => {
1356 size += cnode.size();
1357 bits_t = bits_t.bit_insert(<F>::nth_bit(index).unwrap()).unwrap();
1358 values_t.push(MNode::C(cnode));
1359 reduced = reduce_op(&reduced, &r);
1360 unchangedr = false;
1361 },
1362 MNodeTransformResult::L(lnode, r) => {
1363 size += lnode.size();
1364 bits_t = bits_t.bit_insert(<F>::nth_bit(index).unwrap()).unwrap();
1365 values_t.push(MNode::L(lnode));
1366 reduced = reduce_op(&reduced, &r);
1367 unchangedr = false;
1368 },
1369 MNodeTransformResult::S(snode, r) => {
1370 size += 1;
1371 bits_t = bits_t.bit_insert(<F>::nth_bit(index).unwrap()).unwrap();
1372 values_t.push(MNode::S(snode));
1373 reduced = reduce_op(&reduced, &r);
1374 unchangedr = false;
1375 },
1376 MNodeTransformResult::Removed(r) => {
1377 reduced = reduce_op(&reduced, &r);
1378 unchangedr = false;
1379 },
1380 }
1381 }
1382
1383 if unchangedr {
1384 MNodeTransformResult::Unchanged(reduced)
1385 }
1386 else {
1387 match values_t.len() {
1388 0 => MNodeTransformResult::Removed(reduced),
1389 1 => match values_t.pop().unwrap() {
1390 MNode::C(_cnode) => MNodeTransformResult::C(CNode::new(new_bit_indexed_array(bits_t, BitIndexedArrayVec::new(&values_t), size).unwrap()), reduced),
1391 MNode::L(lnode) => MNodeTransformResult::L(lnode, reduced),
1392 MNode::S(snode) => MNodeTransformResult::S(snode, reduced),
1393 },
1394 _ => MNodeTransformResult::C(CNode::new(new_bit_indexed_array(bits_t, BitIndexedArrayVec::new(&values_t), size).unwrap()), reduced),
1395 }
1396 }
1397}
1398
1399pub(crate) unsafe fn transmute_with_transmuted_snode<H: Hashword, F: Flagword<H>, K: Key, V: Value, L: Key, W: Value, S: Key, X: Value, M: HasherBv<H, K>, ReduceT, ReduceOp, BothOp, LeftOp, RightOp>(this: &CNode<H, F, K, V, M>, right: &Arc<SNode<L, W>>, reduce_op: ReduceOp, both_op: BothOp, left_op: LeftOp, right_op: RightOp, depth: usize) -> MNodeTransmuteResult<H, F, S, X, M, ReduceT>
1400where
1401 ReduceT: Default,
1402 ReduceOp: Fn(&ReduceT, &ReduceT) -> ReduceT + Clone,
1403 BothOp: Fn(&K, &V, &L, &W) -> MapTransmuteResult<S, X, ReduceT> + Clone,
1404 LeftOp: Fn(&K, &V) -> MapTransmuteResult<S, X, ReduceT> + Clone,
1405 RightOp: Fn(&L, &W) -> MapTransmuteResult<S, X, ReduceT> + Clone,
1406 K: HashLike<L>,
1407 K: PartialEq<L>,
1408 K: HashLike<S>,
1409 K: PartialEq<S>,
1410 L: HashLike<K>,
1411 L: PartialEq<K>,
1412 L: HashLike<S>,
1413 L: PartialEq<S>,
1414 M: HasherBv<H, L>,
1415 M: HasherBv<H, S>,
1416 <F as core::convert::TryFrom<<H as core::ops::BitAnd>::Output>>::Error: core::fmt::Debug
1417{
1418 let flag = Flag::<H, F>::new_at_depth(M::default().hash(right.key()), depth).unwrap().flag();
1419
1420 let mut size = 0;
1421 let mut bits_t = F::default();
1422 let mut values_t = Vec::default();
1423 let mut reduced = ReduceT::default();
1424
1425 for index in 0..<F>::max_ones() {
1426 let transmute_result = if let Ok(node) = this.nodes.at_bit_index(index) {
1427 if flag == F::nth_bit(index).unwrap() {
1428 node.transmute_with_transmuted_snode(right, reduce_op.clone(), both_op.clone(), left_op.clone(), right_op.clone(), depth + 1)
1429 }
1430 else {
1431 node.transmute(reduce_op.clone(), left_op.clone())
1432 }
1433 }
1434 else if flag == F::nth_bit(index).unwrap() {
1435 snode::transmute(right, right_op.clone()).into()
1436 }
1437 else {
1438 continue;
1439 };
1440
1441 match transmute_result {
1442 MNodeTransmuteResult::C(cnode, r) => {
1443 size += cnode.size();
1444 bits_t = bits_t.bit_insert(<F>::nth_bit(index).unwrap()).unwrap();
1445 values_t.push(MNode::C(cnode));
1446 reduced = reduce_op(&reduced, &r);
1447 },
1448 MNodeTransmuteResult::L(lnode, r) => {
1449 size += lnode.size();
1450 bits_t = bits_t.bit_insert(<F>::nth_bit(index).unwrap()).unwrap();
1451 values_t.push(MNode::L(lnode));
1452 reduced = reduce_op(&reduced, &r);
1453 },
1454 MNodeTransmuteResult::S(snode, r) => {
1455 size += 1;
1456 bits_t = bits_t.bit_insert(<F>::nth_bit(index).unwrap()).unwrap();
1457 values_t.push(MNode::S(snode));
1458 reduced = reduce_op(&reduced, &r);
1459 },
1460 MNodeTransmuteResult::Removed(r) => {
1461 reduced = reduce_op(&reduced, &r);
1462 },
1463 }
1464 }
1465
1466 match values_t.len() {
1467 0 => MNodeTransmuteResult::Removed(reduced),
1468 1 => match values_t.pop().unwrap() {
1469 MNode::C(_cnode) => MNodeTransmuteResult::C(CNode::new(new_bit_indexed_array(bits_t, BitIndexedArrayVec::new(&values_t), size).unwrap()), reduced),
1470 MNode::L(lnode) => MNodeTransmuteResult::L(lnode, reduced),
1471 MNode::S(snode) => MNodeTransmuteResult::S(snode, reduced),
1472 },
1473 _ => MNodeTransmuteResult::C(CNode::new(new_bit_indexed_array(bits_t, BitIndexedArrayVec::new(&values_t), size).unwrap()), reduced),
1474 }
1475}
1476
1477#[must_use]
1478pub(super) fn lift_to_cnode_and_insert<H: Hashword, F: Flagword<H>, K: Key, V: Value, M: HasherBv<H, K>>(this: MNode<H, F, K, V, M>, this_flag: Flag<H, F>, right: MNode<H, F, K, V, M>, right_flag: Flag<H, F>) -> CNode<H, F, K, V, M> where <F as core::convert::TryFrom<<H as core::ops::BitAnd>::Output>>::Error: core::fmt::Debug {
1479 let size = this.size() + right.size();
1480 if this_flag.flag() == right_flag.flag() {
1481 CNode::new(new_bit_indexed_array(this_flag.flag(), BitIndexedArrayVec::new(&[MNode::C(lift_to_cnode_and_insert(this, this_flag.next().unwrap(), right, right_flag.next().unwrap()))]), size).unwrap())
1482 }
1483 else {
1484 let flags = this_flag.flag().bit_insert(right_flag.flag()).unwrap();
1485 let values = if flags.bit_index(this_flag.flag).unwrap() == 0 {
1486 vec!(this, right)
1487 } else {
1488 vec!(right, this)
1489 };
1490 CNode::new(new_bit_indexed_array(flags, BitIndexedArrayVec::new(&values), size).unwrap())
1491 }
1492}
1493
1494impl <H: Hashword, F: Flagword<H>, K: Key, V: Value, M: 'static> Clone for CNode<H, F, K, V, M> {
1495 fn clone(&self) -> Self {
1496 Self {
1497 nodes: self.nodes.clone()
1498 }
1499 }
1500}
1501
1502impl <H: Hashword, F: Flagword<H>, K: Key, V: Value, M: HasherBv<H, K>> Default for CNode<H, F, K, V, M> {
1503 fn default() -> Self {
1504 CNode::new(default_bit_indexed_array())
1505 }
1506}
1507
1508impl <H: Hashword, F: Flagword<H>, K: Key, V: Value, M: HasherBv<H, K>> Eq for CNode<H, F, K, V, M> {}
1509
1510impl <H: Hashword, F: Flagword<H>, K: Key, V: Value, M: HasherBv<H, K>> PartialEq for CNode<H, F, K, V, M> {
1511 fn eq(&self, other: &Self) -> bool {
1512 ptr::eq(Arc::as_ptr(&self.nodes) as *const u8, Arc::as_ptr(&other.nodes) as *const u8)
1513 }
1514}
1515
1516impl <H: Hashword, F: Flagword<H>, K: Key, V: Value, M: HasherBv<H, K>> From<CNode<H, F, K, V, M>> for MNode<H, F, K, V, M> {
1517 fn from(other: CNode<H, F, K, V, M>) -> Self {
1518 MNode::C(other)
1519 }
1520}