merkle_log/treeid.rs
1use crate::{maybestd::iter, util::Either};
2
3/// Unique identifiers for binary tree nodes. Reproduced from [flat-tree].
4///
5/// [flat-tree]: https://docs.rs/flat-tree
6#[derive(Clone, Copy, Debug, Hash, Eq, Ord, PartialEq, PartialOrd)]
7#[repr(transparent)]
8#[cfg_attr(
9 feature = "borsh",
10 derive(borsh::BorshDeserialize, borsh::BorshSerialize)
11)]
12#[cfg_attr(feature = "serde", derive(serde::Deserialize, serde::Serialize))]
13#[cfg_attr(feature = "serde", serde(transparent))]
14pub struct TreeID(u64);
15
16impl TreeID {
17 /// The highest root [`TreeID`] of a full [`MerkleLog`].
18 pub const ROOT: Self = Self(Self::MAX_LEAF_INDEX);
19
20 /// The [`TreeID`] of the very first leaf.
21 pub const MIN_LEAF: Self = Self::leaf(0);
22
23 /// The [`TreeID`] of the very last leaf.
24 pub const MAX_LEAF: Self = Self::leaf(Self::MAX_LEAF_INDEX);
25
26 /// a log longer than this wouldn't have a valid TreeID
27 #[doc(hidden)]
28 pub const MAX_LEN: u64 = Self::MAX_LEAF_INDEX + 1;
29
30 /// The maximum index of a leaf's [`TreeID`].
31 #[doc(hidden)]
32 pub const MAX_LEAF_INDEX: u64 = u64::MAX >> 1;
33
34 /// The maximum sort index of a [`TreeID`].
35 #[doc(hidden)]
36 pub const MAX_SORT_INDEX: u64 = u64::MAX - 1;
37
38 /// The maximum height of a [`TreeID`].
39 ///
40 /// we need 1 more bit than the id's size to represent all ids, so cap
41 /// the height to one less bit
42 #[doc(hidden)]
43 pub const MAX_HEIGHT: u8 = (u64::BITS - 1) as u8;
44
45 /// Returns a node's unique id within the tree, given its height and index.
46 ///
47 /// ## Examples
48 /// ```rust
49 /// use merkle_log::TreeID;
50 ///
51 /// assert_eq!(TreeID::new(0, 0), TreeID::from(0));
52 /// assert_eq!(TreeID::new(0, 1), TreeID::from(2));
53 /// assert_eq!(TreeID::new(0, 2), TreeID::from(4));
54 /// assert_eq!(TreeID::new(1, 0), TreeID::from(1));
55 /// assert_eq!(TreeID::new(1, 1), TreeID::from(5));
56 /// assert_eq!(TreeID::new(1, 2), TreeID::from(9));
57 /// assert_eq!(TreeID::new(1, 3), TreeID::from(13));
58 /// assert_eq!(TreeID::new(2, 0), TreeID::from(3));
59 /// assert_eq!(TreeID::new(2, 1), TreeID::from(11));
60 /// assert_eq!(TreeID::new(2, 2), TreeID::from(19));
61 /// assert_eq!(TreeID::new(3, 0), TreeID::from(7));
62 /// assert_eq!(TreeID::new(3, 1), TreeID::from(23));
63 /// ```
64 #[inline]
65 pub const fn new(height: u8, index: u64) -> Self {
66 debug_assert!(height <= Self::MAX_HEIGHT);
67 debug_assert!(index <= (Self::MAX_LEAF_INDEX >> height));
68 if height == Self::MAX_HEIGHT {
69 Self::ROOT
70 } else {
71 Self((index << (height + 1)) | ((1 << height) - 1))
72 }
73 }
74
75 /// Returns the first node's unique id at a given height.
76 /// ## Examples
77 /// ```rust
78 /// use merkle_log::TreeID;
79 ///
80 /// assert_eq!(TreeID::first(0), TreeID::from(0));
81 /// assert_eq!(TreeID::first(1), TreeID::from(1));
82 /// assert_eq!(TreeID::first(2), TreeID::from(3));
83 /// // test roots
84 /// assert_eq!(TreeID::first(62), TreeID::ROOT.left().unwrap());
85 /// assert_eq!(TreeID::first(TreeID::MAX_HEIGHT), TreeID::ROOT);
86 /// ```
87 #[inline]
88 pub const fn first(height: u8) -> Self {
89 Self::new(height, 0)
90 }
91
92 /// Returns the last node's unique id at a given height.
93 /// ## Examples
94 /// ```rust
95 /// use merkle_log::TreeID;
96 ///
97 /// assert_eq!(TreeID::last(0), TreeID::MAX_LEAF);
98 /// assert_eq!(TreeID::last(1), TreeID::MAX_LEAF.parent());
99 /// assert_eq!(TreeID::last(2), TreeID::MAX_LEAF.parent().parent());
100 /// // test roots
101 /// assert_eq!(TreeID::last(62), TreeID::ROOT.right().unwrap());
102 /// assert_eq!(TreeID::last(TreeID::MAX_HEIGHT), TreeID::ROOT);
103 /// ```
104 #[inline]
105 pub const fn last(height: u8) -> Self {
106 Self::new(height, Self::MAX_LEAF_INDEX >> height)
107 }
108
109 /// Returns a leaf node's unique id at a given index.
110 /// ## Examples
111 /// ```rust
112 /// use merkle_log::TreeID;
113 ///
114 /// assert_eq!(TreeID::leaf(0), TreeID::from(0));
115 /// assert_eq!(TreeID::leaf(1), TreeID::from(2));
116 /// assert_eq!(TreeID::leaf(2), TreeID::from(4));
117 /// assert_eq!(TreeID::leaf(3), TreeID::from(6));
118 /// ```
119 #[inline]
120 pub const fn leaf(index: u64) -> Self {
121 Self::new(0, index)
122 }
123
124 /// Determines if the id represents a leaf node.
125 ///
126 /// ## Examples
127 /// ```rust
128 /// use merkle_log::TreeID;
129 ///
130 /// assert_eq!(TreeID::from(0).is_leaf(), true);
131 /// assert_eq!(TreeID::from(1).is_leaf(), false);
132 /// assert_eq!(TreeID::from(2).is_leaf(), true);
133 /// assert_eq!(TreeID::from(3).is_leaf(), false);
134 /// ```
135 #[inline]
136 pub const fn is_leaf(&self) -> bool {
137 (self.0 & 1) == 0
138 }
139
140 /// Determines if the id represents a left node of its parent.
141 ///
142 /// ## Examples
143 /// ```rust
144 /// use merkle_log::TreeID;
145 ///
146 /// assert_eq!(TreeID::from(0).is_left(), true);
147 /// assert_eq!(TreeID::from(1).is_left(), true);
148 /// assert_eq!(TreeID::from(2).is_left(), false);
149 /// assert_eq!(TreeID::from(3).is_left(), true);
150 /// assert_eq!(TreeID::from(4).is_left(), true);
151 /// assert_eq!(TreeID::from(5).is_left(), false);
152 /// assert_eq!(TreeID::from(6).is_left(), false);
153 /// // test root
154 /// assert_eq!(TreeID::ROOT.is_left(), true);
155 /// ```
156 #[inline]
157 pub const fn is_left(&self) -> bool {
158 (self.index() & 1) == 0
159 }
160
161 /// Determines if the id represents a right node of its parent.
162 ///
163 /// ## Examples
164 /// ```rust
165 /// use merkle_log::TreeID;
166 ///
167 /// assert_eq!(TreeID::from(0).is_right(), false);
168 /// assert_eq!(TreeID::from(1).is_right(), false);
169 /// assert_eq!(TreeID::from(2).is_right(), true);
170 /// assert_eq!(TreeID::from(3).is_right(), false);
171 /// assert_eq!(TreeID::from(4).is_right(), false);
172 /// assert_eq!(TreeID::from(5).is_right(), true);
173 /// assert_eq!(TreeID::from(6).is_right(), true);
174 /// // test root
175 /// assert_eq!(TreeID::ROOT.is_right(), false);
176 /// ```
177 #[inline]
178 pub const fn is_right(&self) -> bool {
179 !self.is_left()
180 }
181
182 /// Determines if the id represents a left node of its parent.
183 ///
184 /// ## Examples
185 /// ```rust
186 /// use merkle_log::TreeID;
187 ///
188 /// assert_eq!(TreeID::from(0).is_left_of(&TreeID::from(0)), false);
189 /// assert_eq!(TreeID::from(0).is_left_of(&TreeID::from(1)), true);
190 /// assert_eq!(TreeID::from(2).is_left_of(&TreeID::from(1)), false);
191 /// assert_eq!(TreeID::from(1).is_left_of(&TreeID::from(2)), true);
192 /// ```
193 #[inline]
194 pub const fn is_left_of(&self, other: &Self) -> bool {
195 self.lt(other)
196 }
197
198 /// Determines if the id represents a right node of its parent.
199 ///
200 /// ## Examples
201 /// ```rust
202 /// use merkle_log::TreeID;
203 ///
204 /// assert_eq!(TreeID::from(0).is_right_of(&TreeID::from(0)), false);
205 /// assert_eq!(TreeID::from(0).is_right_of(&TreeID::from(1)), false);
206 /// assert_eq!(TreeID::from(2).is_right_of(&TreeID::from(1)), true);
207 /// assert_eq!(TreeID::from(1).is_right_of(&TreeID::from(2)), false);
208 /// ```
209 #[inline]
210 pub const fn is_right_of(&self, other: &Self) -> bool {
211 other.lt(self)
212 }
213
214 /// Determines if the id is the first among nodes of the same height.
215 /// ## Examples
216 /// ```rust
217 /// use merkle_log::TreeID;
218 ///
219 /// assert_eq!(TreeID::from(0).is_first(), true);
220 /// assert_eq!(TreeID::from(1).is_first(), true);
221 /// assert_eq!(TreeID::from(2).is_first(), false);
222 /// assert_eq!(TreeID::from(3).is_first(), true);
223 /// assert_eq!(TreeID::from(4).is_first(), false);
224 /// assert_eq!(TreeID::from(5).is_first(), false);
225 /// assert_eq!(TreeID::from(6).is_first(), false);
226 /// assert_eq!(TreeID::from(7).is_first(), true);
227 /// // test root
228 /// assert_eq!(TreeID::ROOT.is_first(), true);
229 /// ```
230 #[inline]
231 pub const fn is_first(self) -> bool {
232 self.index() == 0
233 }
234
235 /// Determines if the id is the last among nodes of the same height.
236 /// ## Examples
237 /// ```rust
238 /// use merkle_log::TreeID;
239 ///
240 /// assert_eq!(TreeID::MAX_LEAF.is_last(), true);
241 /// assert_eq!(TreeID::MAX_LEAF.parent().is_last(), true);
242 /// assert_eq!(TreeID::MAX_LEAF.sibling().is_last(), false);
243 /// assert_eq!(TreeID::MAX_LEAF.parent().sibling().is_last(), false);
244 /// // test root
245 /// assert_eq!(TreeID::ROOT.is_last(), true);
246 /// ```
247 #[inline]
248 pub const fn is_last(self) -> bool {
249 self.index() == (Self::MAX_LEAF_INDEX >> self.height())
250 }
251
252 /// Returns a node's index among nodes of the same height.
253 ///
254 /// ## Examples
255 /// ```rust
256 /// use merkle_log::TreeID;
257 ///
258 /// assert_eq!(TreeID::from(0).index(), 0);
259 /// assert_eq!(TreeID::from(1).index(), 0);
260 /// assert_eq!(TreeID::from(2).index(), 1);
261 /// assert_eq!(TreeID::from(3).index(), 0);
262 /// assert_eq!(TreeID::from(4).index(), 2);
263 /// assert_eq!(TreeID::from(5).index(), 1);
264 /// assert_eq!(TreeID::from(6).index(), 3);
265 /// assert_eq!(TreeID::from(7).index(), 0);
266 /// assert_eq!(TreeID::from(8).index(), 4);
267 /// assert_eq!(TreeID::from(9).index(), 2);
268 /// assert_eq!(TreeID::from(10).index(), 5);
269 /// // test root
270 /// assert_eq!(TreeID::ROOT.index(), 0);
271 /// ```
272 #[inline]
273 pub const fn index(&self) -> u64 {
274 if self.is_root() {
275 0
276 } else {
277 self.0 >> (self.height() + 1)
278 }
279 }
280
281 /// Returns a node's height in the tree.
282 ///
283 /// ## Examples
284 /// ```rust
285 /// use merkle_log::TreeID;
286 ///
287 /// assert_eq!(TreeID::from(0).height(), 0);
288 /// assert_eq!(TreeID::from(1).height(), 1);
289 /// assert_eq!(TreeID::from(2).height(), 0);
290 /// assert_eq!(TreeID::from(3).height(), 2);
291 /// assert_eq!(TreeID::from(4).height(), 0);
292 /// // test root
293 /// assert_eq!(TreeID::ROOT.height(), TreeID::MAX_HEIGHT);
294 /// ```
295 #[inline]
296 pub const fn height(&self) -> u8 {
297 (!self.0).trailing_zeros() as u8
298 }
299
300 /// Returns the total number of nodes the node spans.
301 ///
302 /// ## Examples
303 /// ```rust
304 /// use merkle_log::TreeID;
305 ///
306 /// assert_eq!(TreeID::from(0).size(), 1);
307 /// assert_eq!(TreeID::from(2).size(), 1);
308 /// assert_eq!(TreeID::from(1).size(), 3);
309 /// assert_eq!(TreeID::from(3).size(), 7);
310 /// assert_eq!(TreeID::from(7).size(), 15);
311 /// // test root
312 /// assert_eq!(TreeID::ROOT.size(), u64::MAX);
313 /// ```
314 #[inline]
315 pub const fn size(&self) -> u64 {
316 !((u64::MAX - 1) << self.height())
317 }
318
319 /// Returns the number of leaf nodes the node spans.
320 ///
321 /// ## Examples
322 /// ```rust
323 /// use merkle_log::TreeID;
324 ///
325 /// assert_eq!(TreeID::from(0).num_leaves(), 0);
326 /// assert_eq!(TreeID::from(2).num_leaves(), 0);
327 /// assert_eq!(TreeID::from(1).num_leaves(), 2);
328 /// assert_eq!(TreeID::from(5).num_leaves(), 2);
329 /// assert_eq!(TreeID::from(3).num_leaves(), 4);
330 /// assert_eq!(TreeID::from(7).num_leaves(), 8);
331 /// // test root
332 /// assert_eq!(TreeID::ROOT.num_leaves(), TreeID::MAX_LEAF.index() + 1);
333 /// ```
334 #[inline]
335 pub const fn num_leaves(&self) -> u64 {
336 if self.is_leaf() {
337 0
338 } else {
339 2u64 << (self.height() - 1)
340 }
341 }
342
343 /// Returns the left- and right-most node ids in the tree the node spans.
344 ///
345 /// ## Examples
346 /// ```rust
347 /// use merkle_log::TreeID;
348 ///
349 /// assert_eq!(TreeID::from(0).span(), (TreeID::from(0), TreeID::from(0)));
350 /// assert_eq!(TreeID::from(2).span(), (TreeID::from(2), TreeID::from(2)));
351 /// assert_eq!(TreeID::from(1).span(), (TreeID::from(0), TreeID::from(2)));
352 /// assert_eq!(TreeID::from(3).span(), (TreeID::from(0), TreeID::from(6)));
353 /// assert_eq!(TreeID::from(23).span(), (TreeID::from(16), TreeID::from(30)));
354 /// assert_eq!(TreeID::from(27).span(), (TreeID::from(24), TreeID::from(30)));
355 /// // test root
356 /// assert_eq!(TreeID::ROOT.span(), (TreeID::MIN_LEAF, TreeID::MAX_LEAF));
357 /// ```
358 #[inline]
359 pub const fn span(&self) -> (Self, Self) {
360 if self.is_leaf() {
361 (*self, *self)
362 } else {
363 let idx = self.index();
364 let num_leaves = self.num_leaves();
365 (
366 Self::leaf(idx * num_leaves),
367 Self::leaf((idx + 1) * num_leaves - 1),
368 )
369 }
370 }
371
372 /// Determines if the id's tree spans (i.e. contains) another id.
373 ///
374 /// ## Examples
375 /// ```rust
376 /// use merkle_log::TreeID;
377 ///
378 /// assert_eq!(TreeID::from(0).spans(&TreeID::from(0)), true);
379 /// assert_eq!(TreeID::from(0).spans(&TreeID::from(1)), false);
380 /// assert_eq!(TreeID::from(0).spans(&TreeID::from(2)), false);
381 /// assert_eq!(TreeID::from(1).spans(&TreeID::from(0)), true);
382 /// assert_eq!(TreeID::from(1).spans(&TreeID::from(1)), true);
383 /// assert_eq!(TreeID::from(1).spans(&TreeID::from(2)), true);
384 /// assert_eq!(TreeID::from(3).spans(&TreeID::from(1)), true);
385 /// assert_eq!(TreeID::from(3).spans(&TreeID::from(5)), true);
386 /// assert_eq!(TreeID::from(3).spans(&TreeID::from(7)), false);
387 /// // test root
388 /// assert_eq!(TreeID::ROOT.spans(&TreeID::MIN_LEAF), true);
389 /// assert_eq!(TreeID::ROOT.spans(&TreeID::MAX_LEAF), true);
390 /// ```
391 #[inline]
392 pub const fn spans(&self, other: &Self) -> bool {
393 let (ref left, ref right) = self.span();
394 left.lte(other) && other.lte(right)
395 }
396
397 /// Returns the lowest root id of a [`MerkleLog`] that contains this node.
398 ///
399 /// ## Examples
400 /// ```rust
401 /// use merkle_log::TreeID;
402 ///
403 /// assert_eq!(TreeID::from(0).root_id(), TreeID::from(0));
404 /// assert_eq!(TreeID::from(1).root_id(), TreeID::from(1));
405 /// assert_eq!(TreeID::from(2).root_id(), TreeID::from(1));
406 /// assert_eq!(TreeID::from(3).root_id(), TreeID::from(3));
407 /// assert_eq!(TreeID::from(4).root_id(), TreeID::from(3));
408 /// assert_eq!(TreeID::from(5).root_id(), TreeID::from(3));
409 /// assert_eq!(TreeID::from(6).root_id(), TreeID::from(3));
410 /// assert_eq!(TreeID::from(7).root_id(), TreeID::from(7));
411 /// assert_eq!(TreeID::from(8).root_id(), TreeID::from(7));
412 /// assert_eq!(TreeID::from(9).root_id(), TreeID::from(7));
413 /// // test root
414 /// assert_eq!(TreeID::ROOT.root_id(), TreeID::ROOT);
415 /// ```
416 #[inline]
417 pub const fn root_id(&self) -> Self {
418 let (_, right) = self.span();
419 Self::first(Self::root_height(right.index() + 1))
420 }
421
422 /// Returns a node's sort index, i.e. the index in a list sorted by when the
423 /// node completes a subtree and becomes immutable.
424 ///
425 /// ## Examples
426 /// ```rust
427 /// use merkle_log::TreeID;
428 ///
429 /// assert_eq!(TreeID::from(0).sort_index(), 0);
430 /// assert_eq!(TreeID::from(2).sort_index(), 1);
431 /// assert_eq!(TreeID::from(1).sort_index(), 2);
432 /// assert_eq!(TreeID::from(4).sort_index(), 3);
433 /// assert_eq!(TreeID::from(6).sort_index(), 4);
434 /// assert_eq!(TreeID::from(5).sort_index(), 5);
435 /// assert_eq!(TreeID::from(3).sort_index(), 6);
436 /// assert_eq!(TreeID::from(8).sort_index(), 7);
437 /// assert_eq!(TreeID::from(10).sort_index(), 8);
438 /// assert_eq!(TreeID::from(9).sort_index(), 9);
439 /// assert_eq!(TreeID::from(12).sort_index(), 10);
440 /// assert_eq!(TreeID::from(14).sort_index(), 11);
441 /// assert_eq!(TreeID::from(13).sort_index(), 12);
442 /// assert_eq!(TreeID::from(11).sort_index(), 13);
443 /// assert_eq!(TreeID::from(7).sort_index(), 14);
444 /// // check final nodes
445 /// assert_eq!(TreeID::MAX_LEAF.sort_index(), TreeID::MAX_SORT_INDEX - TreeID::MAX_HEIGHT as u64);
446 /// assert_eq!(TreeID::ROOT.sort_index(), TreeID::MAX_SORT_INDEX);
447 /// ```
448 #[inline]
449 pub const fn sort_index(&self) -> u64 {
450 if self.is_min_leaf() {
451 return 0;
452 } else if self.is_a_root() {
453 return self.size() - 1;
454 }
455
456 match (self.is_leaf(), self.is_left()) {
457 (true, true) => self.subroots_size() - 1,
458 (true, false) => 1 + self.sibling().sort_index(),
459 _ => {
460 let (_, right) = self.span();
461 self.height() as u64 + right.sort_index()
462 }
463 }
464 }
465
466 // /// Returns a node's sort index, i.e. the index in a list sorted by when the
467 // /// node completes a subtree and becomes immutable.
468 // ///
469 // /// ## Examples
470 // /// ```rust
471 // /// use merkle_log::TreeID;
472 // ///
473 // /// assert_eq!(TreeID::from_sort_index(0), TreeID::from(0));
474 // /// assert_eq!(TreeID::from_sort_index(1), TreeID::from(2));
475 // /// assert_eq!(TreeID::from_sort_index(2), TreeID::from(1));
476 // /// assert_eq!(TreeID::from_sort_index(3), TreeID::from(4));
477 // /// assert_eq!(TreeID::from_sort_index(4), TreeID::from(6));
478 // /// assert_eq!(TreeID::from_sort_index(5), TreeID::from(5));
479 // /// assert_eq!(TreeID::from_sort_index(6), TreeID::from(3));
480 // /// assert_eq!(TreeID::from_sort_index(7), TreeID::from(8));
481 // /// assert_eq!(TreeID::from_sort_index(8), TreeID::from(10));
482 // /// assert_eq!(TreeID::from_sort_index(9), TreeID::from(9));
483 // /// assert_eq!(TreeID::from_sort_index(10), TreeID::from(12));
484 // /// assert_eq!(TreeID::from_sort_index(11), TreeID::from(14));
485 // /// assert_eq!(TreeID::from_sort_index(12), TreeID::from(13));
486 // /// assert_eq!(TreeID::from_sort_index(13), TreeID::from(11));
487 // /// assert_eq!(TreeID::from_sort_index(14), TreeID::from(7));
488 // /// // check last leaf
489 // /// // assert_eq!(TreeID::MAX_LEAF.sort_index(), u64::MAX);
490 // /// ```
491 // #[inline]
492 // pub const fn from_sort_index(index: u64) -> Self {
493 // if index == 0 {
494 // return Self::MIN_LEAF;
495 // } else if (index + 2).is_power_of_two() {
496 // return Self::first(Self::num_balanced_leaves(index).trailing_zeros() as u8);
497 // }
498 //
499 // let len = index + 1;
500 // //
501 // unimplemented!()
502 // }
503 //
504 // #[inline]
505 // pub fn sort_iter() -> impl Iterator<Item = Self> {
506 // (0..u64::MAX).map(TreeID::from_sort_index)
507 // }
508
509 /// Returns the sibling id of a node.
510 ///
511 /// ## Examples
512 /// ```rust
513 /// use merkle_log::TreeID;
514 ///
515 /// assert_eq!(TreeID::from(0).sibling(), TreeID::from(2));
516 /// assert_eq!(TreeID::from(2).sibling(), TreeID::from(0));
517 /// assert_eq!(TreeID::from(1).sibling(), TreeID::from(5));
518 /// assert_eq!(TreeID::from(5).sibling(), TreeID::from(1));
519 /// // test root
520 /// // assert_eq!(TreeID::ROOT.sibling(), TreeID::ROOT);
521 /// ```
522 #[inline]
523 pub const fn sibling(&self) -> Self {
524 Self::new(self.height(), self.index() ^ 1)
525 }
526
527 /// Returns the parent id of a node.
528 ///
529 /// ## Examples
530 /// ```rust
531 /// use merkle_log::TreeID;
532 ///
533 /// assert_eq!(TreeID::from(0).parent(), TreeID::from(1));
534 /// assert_eq!(TreeID::from(1).parent(), TreeID::from(3));
535 /// assert_eq!(TreeID::from(2).parent(), TreeID::from(1));
536 /// assert_eq!(TreeID::from(3).parent(), TreeID::from(7));
537 /// assert_eq!(TreeID::from(4).parent(), TreeID::from(5));
538 /// assert_eq!(TreeID::from(5).parent(), TreeID::from(3));
539 /// assert_eq!(TreeID::from(6).parent(), TreeID::from(5));
540 /// assert_eq!(TreeID::from(7).parent(), TreeID::from(15));
541 /// assert_eq!(TreeID::from(8).parent(), TreeID::from(9));
542 /// // test root
543 /// // assert_eq!(TreeID::ROOT.sibling(), TreeID::ROOT);
544 /// ```
545 #[inline]
546 pub const fn parent(&self) -> Self {
547 Self::new(self.height() + 1, self.index() >> 1)
548 }
549
550 /// Given a node, returns its parent's sibling's id.
551 ///
552 /// ## Examples
553 /// ```rust
554 /// use merkle_log::TreeID;
555 ///
556 /// assert_eq!(TreeID::from(0).uncle(), TreeID::from(5));
557 /// assert_eq!(TreeID::from(2).uncle(), TreeID::from(5));
558 /// assert_eq!(TreeID::from(1).uncle(), TreeID::from(11));
559 /// assert_eq!(TreeID::from(5).uncle(), TreeID::from(11));
560 /// assert_eq!(TreeID::from(9).uncle(), TreeID::from(3));
561 /// // test root
562 /// // assert_eq!(TreeID::ROOT.sibling(), TreeID::ROOT);
563 /// ```
564 #[inline]
565 pub const fn uncle(&self) -> Self {
566 Self::new(self.height() + 1, self.parent().index() ^ 1)
567 }
568
569 /// Returns the id of the node's left child.
570 ///
571 /// ## Examples
572 /// ```rust
573 /// use merkle_log::TreeID;
574 ///
575 /// assert_eq!(TreeID::from(0).left(), None);
576 /// assert_eq!(TreeID::from(1).left(), Some(TreeID::from(0)));
577 /// assert_eq!(TreeID::from(3).left(), Some(TreeID::from(1)));
578 /// ```
579 #[inline]
580 pub const fn left(&self) -> Option<Self> {
581 if self.is_leaf() {
582 None
583 } else {
584 Some(Self::new(self.height() - 1, self.index() << 1))
585 }
586 }
587
588 /// Returns the id of the node's right child.
589 ///
590 /// ## Examples
591 /// ```rust
592 /// use merkle_log::TreeID;
593 ///
594 /// assert_eq!(TreeID::from(0).right(), None);
595 /// assert_eq!(TreeID::from(1).right(), Some(TreeID::from(2)));
596 /// assert_eq!(TreeID::from(3).right(), Some(TreeID::from(5)));
597 /// ```
598 #[inline]
599 pub const fn right(&self) -> Option<Self> {
600 if self.is_leaf() {
601 None
602 } else {
603 Some(Self::new(self.height() - 1, (self.index() << 1) + 1))
604 }
605 }
606
607 /// Given the id of a node in a balanced tree, produce the ids of nodes
608 /// required for a traditional merkle tree proof, excluding the (sub)root.
609 ///
610 /// ## Examples
611 /// ```rust
612 /// use std::collections::BTreeSet;
613 /// use merkle_log::*;
614 ///
615 /// assert_eq!(TreeID::from(0).proving_ids(0).collect::<Vec<_>>(), &[]);
616 /// assert_eq!(TreeID::from(0).proving_ids(1).collect::<Vec<_>>(), &[TreeID::from(2)]);
617 /// assert_eq!(TreeID::from(0).proving_ids(2).collect::<Vec<_>>(), &[TreeID::from(2), TreeID::from(5)]);
618 /// ```
619 #[inline]
620 pub fn proving_ids(&self, to_height: u8) -> impl Iterator<Item = Self> {
621 debug_assert!(to_height <= Self::MAX_HEIGHT);
622 (0..(to_height - self.height())).scan(*self, |current_id, _| {
623 let sibling = current_id.sibling();
624 *current_id = current_id.parent();
625 Some(sibling)
626 })
627 }
628
629 /// The ids whose values are required to append the next entry to the log,
630 /// sorted left to right.
631 ///
632 /// ## Examples
633 /// ```rust
634 /// use merkle_log::*;
635 ///
636 /// assert_eq!(TreeID::appending_ids(1).collect::<Vec<_>>(), &[]);
637 /// assert_eq!(TreeID::appending_ids(2).collect::<Vec<_>>(), &[TreeID::from(0)]);
638 /// assert_eq!(TreeID::appending_ids(3).collect::<Vec<_>>(), &[TreeID::from(1)]);
639 /// assert_eq!(TreeID::appending_ids(4).collect::<Vec<_>>(), &[TreeID::from(1), TreeID::from(4)]);
640 /// assert_eq!(TreeID::appending_ids(5).collect::<Vec<_>>(), &[TreeID::from(3)]);
641 /// assert_eq!(TreeID::appending_ids(6).collect::<Vec<_>>(), &[TreeID::from(3), TreeID::from(8)]);
642 /// assert_eq!(TreeID::appending_ids(7).collect::<Vec<_>>(), &[TreeID::from(3), TreeID::from(9)]);
643 /// assert_eq!(TreeID::appending_ids(8).collect::<Vec<_>>(), &[TreeID::from(3), TreeID::from(9), TreeID::from(12)]);
644 /// assert_eq!(TreeID::appending_ids(9).collect::<Vec<_>>(), &[TreeID::from(7)]);
645 /// assert_eq!(TreeID::appending_ids(10).collect::<Vec<_>>(), &[TreeID::from(7), TreeID::from(16)]);
646 /// ```
647 #[inline]
648 pub fn appending_ids(new_len: u64) -> impl Iterator<Item = Self> {
649 Self::subroot_ids(new_len - 1)
650 }
651
652 /// The root ids of the highest complete subtrees within a log whose length
653 /// is `len`, sorted left to right.
654 ///
655 /// ## Examples
656 /// ```rust
657 /// use merkle_log::*;
658 ///
659 /// assert_eq!(TreeID::subroot_ids(0).collect::<Vec<_>>(), &[]);
660 /// assert_eq!(TreeID::subroot_ids(1).collect::<Vec<_>>(), &[TreeID::from(0)]);
661 /// assert_eq!(TreeID::subroot_ids(2).collect::<Vec<_>>(), &[TreeID::from(1)]);
662 /// assert_eq!(TreeID::subroot_ids(3).collect::<Vec<_>>(), &[TreeID::from(1), TreeID::from(4)]);
663 /// assert_eq!(TreeID::subroot_ids(4).collect::<Vec<_>>(), &[TreeID::from(3)]);
664 /// assert_eq!(TreeID::subroot_ids(5).collect::<Vec<_>>(), &[TreeID::from(3), TreeID::from(8)]);
665 /// assert_eq!(TreeID::subroot_ids(6).collect::<Vec<_>>(), &[TreeID::from(3), TreeID::from(9)]);
666 /// assert_eq!(TreeID::subroot_ids(7).collect::<Vec<_>>(), &[TreeID::from(3), TreeID::from(9), TreeID::from(12)]);
667 /// assert_eq!(TreeID::subroot_ids(8).collect::<Vec<_>>(), &[TreeID::from(7)]);
668 /// assert_eq!(TreeID::subroot_ids(9).collect::<Vec<_>>(), &[TreeID::from(7), TreeID::from(16)]);
669 /// assert_eq!(TreeID::subroot_ids(10).collect::<Vec<_>>(), &[TreeID::from(7), TreeID::from(17)]);
670 /// // test root
671 /// // assert_eq!(TreeID::subroot_ids(TreeID::MAX_LEN).count() as u64, 0u64);
672 /// ```
673 #[inline]
674 pub fn subroot_ids(len: u64) -> impl Iterator<Item = Self> {
675 debug_assert!(
676 len <= Self::MAX_LEN,
677 "cannot obtain subroots for logs greater than {}",
678 Self::MAX_LEN
679 );
680
681 if len == 0 {
682 return Either::Left(Either::Left(iter::empty()));
683 } else if len.is_power_of_two() {
684 let root = Self::first(Self::root_height(len));
685 return Either::Left(Either::Right(iter::once(root)));
686 }
687
688 Either::Right(
689 iter::successors(Some(Self::num_balanced_leaves(len)), move |num_leaves| {
690 (num_leaves < &len)
691 .then(|| num_leaves + Self::num_balanced_leaves(len - num_leaves))
692 })
693 .scan(None, move |prev_id: &mut Option<TreeID>, num_leaves| {
694 let height = num_leaves.trailing_zeros() as u8;
695 let next_id = match prev_id {
696 None => Self::first(height),
697 Some(_) if height == 0 => Self::leaf(len - 1),
698 Some(prev_id) => {
699 let index = ((prev_id.index() + 1) << (prev_id.height() - height)) as u64;
700 Self::new(height, index)
701 }
702 };
703 prev_id.replace(next_id);
704 Some(next_id)
705 }),
706 )
707 }
708
709 #[inline]
710 pub(crate) const fn root_height(len: u64) -> u8 {
711 len.next_power_of_two().trailing_zeros() as u8
712 }
713
714 #[inline]
715 const fn num_balanced_leaves(len: u64) -> u64 {
716 prev_power_of_two(len)
717 }
718
719 #[inline]
720 const fn subroots_size(&self) -> u64 {
721 debug_assert!(self.is_leaf());
722 let len = self.index() + 1;
723
724 let mut num_leaves = 0u64;
725 let mut size = 0u64;
726 while num_leaves < len {
727 let subtree_len = Self::num_balanced_leaves(len - num_leaves);
728 num_leaves += subtree_len;
729 size += (subtree_len << 1) - 1;
730 }
731 size
732 }
733}
734
735impl TreeID {
736 #[inline]
737 const fn is_min_leaf(&self) -> bool {
738 self.is(&Self::MIN_LEAF)
739 }
740
741 #[inline]
742 const fn is_root(&self) -> bool {
743 self.is(&Self::ROOT)
744 }
745
746 #[inline(always)]
747 const fn is_a_root(&self) -> bool {
748 self.is_first()
749 }
750
751 #[inline(always)]
752 const fn is(&self, other: &Self) -> bool {
753 self.0 == other.0
754 }
755
756 #[inline]
757 const fn lte(&self, other: &Self) -> bool {
758 other.0.checked_sub(self.0).is_some()
759 }
760
761 #[inline]
762 const fn lt(&self, other: &Self) -> bool {
763 match other.0.checked_sub(self.0) {
764 None | Some(0) => false,
765 _ => true,
766 }
767 }
768}
769
770#[inline]
771const fn prev_power_of_two(n: u64) -> u64 {
772 let n = n >> 1;
773 if n.is_power_of_two() {
774 (n << 1).next_power_of_two()
775 } else {
776 n.next_power_of_two()
777 }
778}
779
780impl From<u64> for TreeID {
781 fn from(id: u64) -> Self {
782 Self(id)
783 }
784}
785
786// macro_rules! derive_eq {
787// ($type:ty) => {
788// impl PartialEq<$type> for TreeID {
789// fn eq(&self, other: &$type) -> bool {
790// self.0 == *other as u64
791// }
792// }
793// };
794// }
795
796// derive_eq!(usize);
797// derive_eq!(u8);
798// derive_eq!(u16);
799// derive_eq!(u32);
800// derive_eq!(u64);