2 releases

0.1.2 Sep 4, 2024
0.1.1 Aug 21, 2024
0.1.0 Aug 20, 2024
0.0.2 Aug 17, 2024
0.0.1 Jul 24, 2024

#1019 in Algorithms

Download history 107/week @ 2024-07-21 13/week @ 2024-07-28 1/week @ 2024-08-04 109/week @ 2024-08-11 341/week @ 2024-08-18 13/week @ 2024-08-25 168/week @ 2024-09-01 20/week @ 2024-09-08 16/week @ 2024-09-15

225 downloads per month

Apache-2.0

26KB
595 lines

GitHub Workflow Status crates.io

bubbletree

Bubble-tree: a dynamic tree structure for maintaining data bubbles of fully dynamic data w.r.t. compression factor.

Usage

The following example shows how to maintain data bubbles of fully dynamic data for a given compression factor:

use bubbletree::BubbleTree;

#[test]
pub fn example_usage() {
    // Configure the tree
    let fanout = 4;
    let compression_factor = 3;
    let mut tree = BubbleTree::new(fanout, compression_factor);

    // Insert points
    let a = tree.insert([0.0, 0.0]);
    let b = tree.insert([1.0, 1.0]);
    let c = tree.insert([2.0, 2.0]);
    let d = tree.insert([10.0, 10.0]);
    let e = tree.insert([11.0, 11.0]);
    let f = tree.insert([12.0, 12.0]);

    // Confirm that the tree should have 2 leaves:
    assert_eq!(tree.num_leaves, 2);

    // 6 points compressed into 2 groups (or data bubbles)
    // a, b, c should be in the same group
    assert!(tree.parent_of(a) == tree.parent_of(b));
    assert!(tree.parent_of(b) == tree.parent_of(c));
    assert_ne!(tree.parent_of(a), tree.parent_of(d));

    // d, e, f should be in the same group
    assert!(tree.parent_of(d) == tree.parent_of(e));
    assert!(tree.parent_of(e) == tree.parent_of(f));
}

License

This project is licensed under the Apache License, Version 2.0 - See the LICENSE.md file for details.

Dependencies

~1.5MB
~23K SLoC