bempp_octree::morton

Struct MortonKey

Source
pub struct MortonKey { /* private fields */ }
Expand description

A morton key

This is a distinct type to distinguish from u64 numbers.

Implementations§

Source§

impl MortonKey

Source

pub fn upper_bound() -> Self

A key that is not valid or well formed but guaranteed to be larger than any valid key.

This is useful when a guaranteed upper bound is needed.

Source

pub fn invalid_key() -> Self

Create an invalid key.

Source

pub fn is_valid(&self) -> bool

Check if key is valid.

A key is not valid if its highest bit is 1.

Examples found in repository?
examples/mpi_complete_tree_debug.rs (line 56)
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
pub fn main() {
    // Initialise MPI
    let universe = mpi::initialize().unwrap();

    // Get the world communicator
    let comm = universe.world();

    // Initialise a seeded Rng.
    let mut rng = ChaCha8Rng::seed_from_u64(comm.rank() as u64);

    // Create `npoints` per rank.
    let npoints = 10000;

    // Generate random points.

    let mut points = generate_random_points(npoints, &mut rng, &comm);
    // Make sure that the points live on the unit sphere.
    for point in points.iter_mut() {
        let len = point.coords()[0] * point.coords()[0]
            + point.coords()[1] * point.coords()[1]
            + point.coords()[2] * point.coords()[2];
        let len = len.sqrt();
        point.coords_mut()[0] /= len;
        point.coords_mut()[1] /= len;
        point.coords_mut()[2] /= len;
    }

    let tree = Octree::new(&points, 15, 50, &comm);

    // We now check that each node of the tree has all its neighbors available.

    let leaf_tree = tree.leaf_keys();
    let all_keys = tree.all_keys();

    assert!(is_complete_linear_and_balanced(leaf_tree, &comm));
    for &key in leaf_tree {
        // We only check interior keys. Leaf keys may not have a neighbor
        // on the same level.
        let mut parent = key.parent();
        while parent.level() > 0 {
            // Check that the key itself is there.
            assert!(all_keys.contains_key(&key));
            // Check that all its neighbours are there.
            for neighbor in parent.neighbours().iter().filter(|&key| key.is_valid()) {
                assert!(all_keys.contains_key(neighbor));
            }
            parent = parent.parent();
            // Check that the parent is there.
            assert!(all_keys.contains_key(&parent));
        }
    }

    // At the end check that the root of the tree is also contained.
    assert!(all_keys.contains_key(&MortonKey::root()));

    // Count the number of ghosts on each rank
    // Count the number of global keys on each rank.

    // Assert that all ghosts are from a different rank and count them.

    let nghosts = all_keys
        .iter()
        .filter_map(|(_, &value)| {
            if let KeyType::Ghost(rank) = value {
                assert!(rank != comm.size() as usize);
                Some(rank)
            } else {
                None
            }
        })
        .count();

    if comm.size() == 1 {
        assert_eq!(nghosts, 0);
    } else {
        assert!(nghosts > 0);
    }

    let nglobal = all_keys
        .iter()
        .filter(|(_, &value)| matches!(value, KeyType::Global))
        .count();

    // Assert that all globals across all ranks have the same count.

    let nglobals = gather_to_all(std::slice::from_ref(&nglobal), &comm);

    assert_eq!(nglobals.iter().unique().count(), 1);

    // Check that the points are associated with the correct leaf keys.
    let mut npoints = 0;
    let leaf_point_map = tree.leaf_keys_to_local_point_indices();

    for (key, point_indices) in leaf_point_map {
        for &index in point_indices {
            assert!(key.is_ancestor(tree.point_keys()[index]));
        }
        npoints += point_indices.len();
    }

    // Make sure that the number of points and point keys lines up
    // with the points stored for each leaf key.
    assert_eq!(npoints, tree.points().len());
    assert_eq!(npoints, tree.point_keys().len());

    // Check the neighbour relationships.

    let all_neighbours = tree.neighbour_map();
    let all_keys = tree.all_keys();

    for (key, key_type) in all_keys {
        // Ghost keys should not be in the neighbour map.
        match key_type {
            KeyType::Ghost(_) => assert!(!all_neighbours.contains_key(key)),
            _ => {
                // If it is not a ghost the key should be in the neighbour map.
                assert!(all_neighbours.contains_key(key));
            }
        }
    }

    if comm.rank() == 0 {
        println!("No errors were found in setting up tree.");
    }
}
Source

pub fn root() -> MortonKey

Create a root key.

A root key simply has the value 0.

Examples found in repository?
examples/mpi_complete_tree_debug.rs (line 66)
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
pub fn main() {
    // Initialise MPI
    let universe = mpi::initialize().unwrap();

    // Get the world communicator
    let comm = universe.world();

    // Initialise a seeded Rng.
    let mut rng = ChaCha8Rng::seed_from_u64(comm.rank() as u64);

    // Create `npoints` per rank.
    let npoints = 10000;

    // Generate random points.

    let mut points = generate_random_points(npoints, &mut rng, &comm);
    // Make sure that the points live on the unit sphere.
    for point in points.iter_mut() {
        let len = point.coords()[0] * point.coords()[0]
            + point.coords()[1] * point.coords()[1]
            + point.coords()[2] * point.coords()[2];
        let len = len.sqrt();
        point.coords_mut()[0] /= len;
        point.coords_mut()[1] /= len;
        point.coords_mut()[2] /= len;
    }

    let tree = Octree::new(&points, 15, 50, &comm);

    // We now check that each node of the tree has all its neighbors available.

    let leaf_tree = tree.leaf_keys();
    let all_keys = tree.all_keys();

    assert!(is_complete_linear_and_balanced(leaf_tree, &comm));
    for &key in leaf_tree {
        // We only check interior keys. Leaf keys may not have a neighbor
        // on the same level.
        let mut parent = key.parent();
        while parent.level() > 0 {
            // Check that the key itself is there.
            assert!(all_keys.contains_key(&key));
            // Check that all its neighbours are there.
            for neighbor in parent.neighbours().iter().filter(|&key| key.is_valid()) {
                assert!(all_keys.contains_key(neighbor));
            }
            parent = parent.parent();
            // Check that the parent is there.
            assert!(all_keys.contains_key(&parent));
        }
    }

    // At the end check that the root of the tree is also contained.
    assert!(all_keys.contains_key(&MortonKey::root()));

    // Count the number of ghosts on each rank
    // Count the number of global keys on each rank.

    // Assert that all ghosts are from a different rank and count them.

    let nghosts = all_keys
        .iter()
        .filter_map(|(_, &value)| {
            if let KeyType::Ghost(rank) = value {
                assert!(rank != comm.size() as usize);
                Some(rank)
            } else {
                None
            }
        })
        .count();

    if comm.size() == 1 {
        assert_eq!(nghosts, 0);
    } else {
        assert!(nghosts > 0);
    }

    let nglobal = all_keys
        .iter()
        .filter(|(_, &value)| matches!(value, KeyType::Global))
        .count();

    // Assert that all globals across all ranks have the same count.

    let nglobals = gather_to_all(std::slice::from_ref(&nglobal), &comm);

    assert_eq!(nglobals.iter().unique().count(), 1);

    // Check that the points are associated with the correct leaf keys.
    let mut npoints = 0;
    let leaf_point_map = tree.leaf_keys_to_local_point_indices();

    for (key, point_indices) in leaf_point_map {
        for &index in point_indices {
            assert!(key.is_ancestor(tree.point_keys()[index]));
        }
        npoints += point_indices.len();
    }

    // Make sure that the number of points and point keys lines up
    // with the points stored for each leaf key.
    assert_eq!(npoints, tree.points().len());
    assert_eq!(npoints, tree.point_keys().len());

    // Check the neighbour relationships.

    let all_neighbours = tree.neighbour_map();
    let all_keys = tree.all_keys();

    for (key, key_type) in all_keys {
        // Ghost keys should not be in the neighbour map.
        match key_type {
            KeyType::Ghost(_) => assert!(!all_neighbours.contains_key(key)),
            _ => {
                // If it is not a ghost the key should be in the neighbour map.
                assert!(all_neighbours.contains_key(key));
            }
        }
    }

    if comm.rank() == 0 {
        println!("No errors were found in setting up tree.");
    }
}
Source

pub fn deepest_first() -> Self

Return the first deepest key.

This is the first key on the deepest level.

Source

pub fn deepest_last() -> Self

Return the last deepest key.

This is the last key on the deepest level.

Source

pub fn physical_box(&self, bounding_box: &PhysicalBox) -> PhysicalBox

Return the associated physical box.

Given the physical boundix bos of the octree this method returns the physical box associated with the key.

Source

pub fn key_in_direction(&self, direction: [i64; 3]) -> MortonKey

Return key in a given direction.

Returns an invalid key if there is no valid key in that direction.

Source

pub fn is_well_formed(&self) -> bool

A key is ill-formed if it has non-zero bits and positions that should be zero by the given level.

Source

pub fn from_physical_point( point: Point, bounding_box: &PhysicalBox, level: usize, ) -> Self

Map a physical point within a bounding box to a Morton key on a given level.

It is assumed that points are strictly contained within the bounding box.

Source

pub fn from_index_and_level(index: [usize; 3], level: usize) -> MortonKey

Create a new key by providing the [x, y, z] index and a level.

This is the preferred way to create a new Morton key.

Source

pub fn level(&self) -> usize

Return the level of a key.

Examples found in repository?
examples/mpi_complete_tree_debug.rs (line 52)
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
pub fn main() {
    // Initialise MPI
    let universe = mpi::initialize().unwrap();

    // Get the world communicator
    let comm = universe.world();

    // Initialise a seeded Rng.
    let mut rng = ChaCha8Rng::seed_from_u64(comm.rank() as u64);

    // Create `npoints` per rank.
    let npoints = 10000;

    // Generate random points.

    let mut points = generate_random_points(npoints, &mut rng, &comm);
    // Make sure that the points live on the unit sphere.
    for point in points.iter_mut() {
        let len = point.coords()[0] * point.coords()[0]
            + point.coords()[1] * point.coords()[1]
            + point.coords()[2] * point.coords()[2];
        let len = len.sqrt();
        point.coords_mut()[0] /= len;
        point.coords_mut()[1] /= len;
        point.coords_mut()[2] /= len;
    }

    let tree = Octree::new(&points, 15, 50, &comm);

    // We now check that each node of the tree has all its neighbors available.

    let leaf_tree = tree.leaf_keys();
    let all_keys = tree.all_keys();

    assert!(is_complete_linear_and_balanced(leaf_tree, &comm));
    for &key in leaf_tree {
        // We only check interior keys. Leaf keys may not have a neighbor
        // on the same level.
        let mut parent = key.parent();
        while parent.level() > 0 {
            // Check that the key itself is there.
            assert!(all_keys.contains_key(&key));
            // Check that all its neighbours are there.
            for neighbor in parent.neighbours().iter().filter(|&key| key.is_valid()) {
                assert!(all_keys.contains_key(neighbor));
            }
            parent = parent.parent();
            // Check that the parent is there.
            assert!(all_keys.contains_key(&parent));
        }
    }

    // At the end check that the root of the tree is also contained.
    assert!(all_keys.contains_key(&MortonKey::root()));

    // Count the number of ghosts on each rank
    // Count the number of global keys on each rank.

    // Assert that all ghosts are from a different rank and count them.

    let nghosts = all_keys
        .iter()
        .filter_map(|(_, &value)| {
            if let KeyType::Ghost(rank) = value {
                assert!(rank != comm.size() as usize);
                Some(rank)
            } else {
                None
            }
        })
        .count();

    if comm.size() == 1 {
        assert_eq!(nghosts, 0);
    } else {
        assert!(nghosts > 0);
    }

    let nglobal = all_keys
        .iter()
        .filter(|(_, &value)| matches!(value, KeyType::Global))
        .count();

    // Assert that all globals across all ranks have the same count.

    let nglobals = gather_to_all(std::slice::from_ref(&nglobal), &comm);

    assert_eq!(nglobals.iter().unique().count(), 1);

    // Check that the points are associated with the correct leaf keys.
    let mut npoints = 0;
    let leaf_point_map = tree.leaf_keys_to_local_point_indices();

    for (key, point_indices) in leaf_point_map {
        for &index in point_indices {
            assert!(key.is_ancestor(tree.point_keys()[index]));
        }
        npoints += point_indices.len();
    }

    // Make sure that the number of points and point keys lines up
    // with the points stored for each leaf key.
    assert_eq!(npoints, tree.points().len());
    assert_eq!(npoints, tree.point_keys().len());

    // Check the neighbour relationships.

    let all_neighbours = tree.neighbour_map();
    let all_keys = tree.all_keys();

    for (key, key_type) in all_keys {
        // Ghost keys should not be in the neighbour map.
        match key_type {
            KeyType::Ghost(_) => assert!(!all_neighbours.contains_key(key)),
            _ => {
                // If it is not a ghost the key should be in the neighbour map.
                assert!(all_neighbours.contains_key(key));
            }
        }
    }

    if comm.rank() == 0 {
        println!("No errors were found in setting up tree.");
    }
}
Source

pub fn decode(&self) -> (usize, [usize; 3])

Decode a key and return a tuple of the form (level, [x, y, z]), where the latter is the index vector.

Source

pub fn parent(&self) -> Self

Return the parent of a key.

Examples found in repository?
examples/mpi_complete_tree_debug.rs (line 51)
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
pub fn main() {
    // Initialise MPI
    let universe = mpi::initialize().unwrap();

    // Get the world communicator
    let comm = universe.world();

    // Initialise a seeded Rng.
    let mut rng = ChaCha8Rng::seed_from_u64(comm.rank() as u64);

    // Create `npoints` per rank.
    let npoints = 10000;

    // Generate random points.

    let mut points = generate_random_points(npoints, &mut rng, &comm);
    // Make sure that the points live on the unit sphere.
    for point in points.iter_mut() {
        let len = point.coords()[0] * point.coords()[0]
            + point.coords()[1] * point.coords()[1]
            + point.coords()[2] * point.coords()[2];
        let len = len.sqrt();
        point.coords_mut()[0] /= len;
        point.coords_mut()[1] /= len;
        point.coords_mut()[2] /= len;
    }

    let tree = Octree::new(&points, 15, 50, &comm);

    // We now check that each node of the tree has all its neighbors available.

    let leaf_tree = tree.leaf_keys();
    let all_keys = tree.all_keys();

    assert!(is_complete_linear_and_balanced(leaf_tree, &comm));
    for &key in leaf_tree {
        // We only check interior keys. Leaf keys may not have a neighbor
        // on the same level.
        let mut parent = key.parent();
        while parent.level() > 0 {
            // Check that the key itself is there.
            assert!(all_keys.contains_key(&key));
            // Check that all its neighbours are there.
            for neighbor in parent.neighbours().iter().filter(|&key| key.is_valid()) {
                assert!(all_keys.contains_key(neighbor));
            }
            parent = parent.parent();
            // Check that the parent is there.
            assert!(all_keys.contains_key(&parent));
        }
    }

    // At the end check that the root of the tree is also contained.
    assert!(all_keys.contains_key(&MortonKey::root()));

    // Count the number of ghosts on each rank
    // Count the number of global keys on each rank.

    // Assert that all ghosts are from a different rank and count them.

    let nghosts = all_keys
        .iter()
        .filter_map(|(_, &value)| {
            if let KeyType::Ghost(rank) = value {
                assert!(rank != comm.size() as usize);
                Some(rank)
            } else {
                None
            }
        })
        .count();

    if comm.size() == 1 {
        assert_eq!(nghosts, 0);
    } else {
        assert!(nghosts > 0);
    }

    let nglobal = all_keys
        .iter()
        .filter(|(_, &value)| matches!(value, KeyType::Global))
        .count();

    // Assert that all globals across all ranks have the same count.

    let nglobals = gather_to_all(std::slice::from_ref(&nglobal), &comm);

    assert_eq!(nglobals.iter().unique().count(), 1);

    // Check that the points are associated with the correct leaf keys.
    let mut npoints = 0;
    let leaf_point_map = tree.leaf_keys_to_local_point_indices();

    for (key, point_indices) in leaf_point_map {
        for &index in point_indices {
            assert!(key.is_ancestor(tree.point_keys()[index]));
        }
        npoints += point_indices.len();
    }

    // Make sure that the number of points and point keys lines up
    // with the points stored for each leaf key.
    assert_eq!(npoints, tree.points().len());
    assert_eq!(npoints, tree.point_keys().len());

    // Check the neighbour relationships.

    let all_neighbours = tree.neighbour_map();
    let all_keys = tree.all_keys();

    for (key, key_type) in all_keys {
        // Ghost keys should not be in the neighbour map.
        match key_type {
            KeyType::Ghost(_) => assert!(!all_neighbours.contains_key(key)),
            _ => {
                // If it is not a ghost the key should be in the neighbour map.
                assert!(all_neighbours.contains_key(key));
            }
        }
    }

    if comm.rank() == 0 {
        println!("No errors were found in setting up tree.");
    }
}
Source

pub fn ancestor_at_level(&self, level: usize) -> Option<Self>

Return ancestor of key on specified level

Return None if level > self.level(). Return the key itself if level == self.level().

Source

pub fn is_ancestor(&self, other: MortonKey) -> bool

Check if key is ancestor of other. If keys are identical also returns true.

Examples found in repository?
examples/mpi_complete_tree_debug.rs (line 108)
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
pub fn main() {
    // Initialise MPI
    let universe = mpi::initialize().unwrap();

    // Get the world communicator
    let comm = universe.world();

    // Initialise a seeded Rng.
    let mut rng = ChaCha8Rng::seed_from_u64(comm.rank() as u64);

    // Create `npoints` per rank.
    let npoints = 10000;

    // Generate random points.

    let mut points = generate_random_points(npoints, &mut rng, &comm);
    // Make sure that the points live on the unit sphere.
    for point in points.iter_mut() {
        let len = point.coords()[0] * point.coords()[0]
            + point.coords()[1] * point.coords()[1]
            + point.coords()[2] * point.coords()[2];
        let len = len.sqrt();
        point.coords_mut()[0] /= len;
        point.coords_mut()[1] /= len;
        point.coords_mut()[2] /= len;
    }

    let tree = Octree::new(&points, 15, 50, &comm);

    // We now check that each node of the tree has all its neighbors available.

    let leaf_tree = tree.leaf_keys();
    let all_keys = tree.all_keys();

    assert!(is_complete_linear_and_balanced(leaf_tree, &comm));
    for &key in leaf_tree {
        // We only check interior keys. Leaf keys may not have a neighbor
        // on the same level.
        let mut parent = key.parent();
        while parent.level() > 0 {
            // Check that the key itself is there.
            assert!(all_keys.contains_key(&key));
            // Check that all its neighbours are there.
            for neighbor in parent.neighbours().iter().filter(|&key| key.is_valid()) {
                assert!(all_keys.contains_key(neighbor));
            }
            parent = parent.parent();
            // Check that the parent is there.
            assert!(all_keys.contains_key(&parent));
        }
    }

    // At the end check that the root of the tree is also contained.
    assert!(all_keys.contains_key(&MortonKey::root()));

    // Count the number of ghosts on each rank
    // Count the number of global keys on each rank.

    // Assert that all ghosts are from a different rank and count them.

    let nghosts = all_keys
        .iter()
        .filter_map(|(_, &value)| {
            if let KeyType::Ghost(rank) = value {
                assert!(rank != comm.size() as usize);
                Some(rank)
            } else {
                None
            }
        })
        .count();

    if comm.size() == 1 {
        assert_eq!(nghosts, 0);
    } else {
        assert!(nghosts > 0);
    }

    let nglobal = all_keys
        .iter()
        .filter(|(_, &value)| matches!(value, KeyType::Global))
        .count();

    // Assert that all globals across all ranks have the same count.

    let nglobals = gather_to_all(std::slice::from_ref(&nglobal), &comm);

    assert_eq!(nglobals.iter().unique().count(), 1);

    // Check that the points are associated with the correct leaf keys.
    let mut npoints = 0;
    let leaf_point_map = tree.leaf_keys_to_local_point_indices();

    for (key, point_indices) in leaf_point_map {
        for &index in point_indices {
            assert!(key.is_ancestor(tree.point_keys()[index]));
        }
        npoints += point_indices.len();
    }

    // Make sure that the number of points and point keys lines up
    // with the points stored for each leaf key.
    assert_eq!(npoints, tree.points().len());
    assert_eq!(npoints, tree.point_keys().len());

    // Check the neighbour relationships.

    let all_neighbours = tree.neighbour_map();
    let all_keys = tree.all_keys();

    for (key, key_type) in all_keys {
        // Ghost keys should not be in the neighbour map.
        match key_type {
            KeyType::Ghost(_) => assert!(!all_neighbours.contains_key(key)),
            _ => {
                // If it is not a ghost the key should be in the neighbour map.
                assert!(all_neighbours.contains_key(key));
            }
        }
    }

    if comm.rank() == 0 {
        println!("No errors were found in setting up tree.");
    }
}
Source

pub fn finest_common_ancestor(&self, other: MortonKey) -> MortonKey

Return the finest common ancestor of two keys.

If the keys are identical return the key itself.

Source

pub fn is_root(&self) -> bool

Return true if key is equal to the root key.

Source

pub fn children(&self) -> [MortonKey; 8]

Return the 8 children of a key.

Source

pub fn siblings(&self) -> [MortonKey; 8]

Return the 8 siblings of a key.

The key itself is part of the siblings.

Source

pub fn neighbours(&self) -> [MortonKey; 26]

Return the neighbours of a key.

The key itself is not part of the neighbours. If along a certain direction there is no neighbour then an invalid key is stored.

Examples found in repository?
examples/mpi_complete_tree_debug.rs (line 56)
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
pub fn main() {
    // Initialise MPI
    let universe = mpi::initialize().unwrap();

    // Get the world communicator
    let comm = universe.world();

    // Initialise a seeded Rng.
    let mut rng = ChaCha8Rng::seed_from_u64(comm.rank() as u64);

    // Create `npoints` per rank.
    let npoints = 10000;

    // Generate random points.

    let mut points = generate_random_points(npoints, &mut rng, &comm);
    // Make sure that the points live on the unit sphere.
    for point in points.iter_mut() {
        let len = point.coords()[0] * point.coords()[0]
            + point.coords()[1] * point.coords()[1]
            + point.coords()[2] * point.coords()[2];
        let len = len.sqrt();
        point.coords_mut()[0] /= len;
        point.coords_mut()[1] /= len;
        point.coords_mut()[2] /= len;
    }

    let tree = Octree::new(&points, 15, 50, &comm);

    // We now check that each node of the tree has all its neighbors available.

    let leaf_tree = tree.leaf_keys();
    let all_keys = tree.all_keys();

    assert!(is_complete_linear_and_balanced(leaf_tree, &comm));
    for &key in leaf_tree {
        // We only check interior keys. Leaf keys may not have a neighbor
        // on the same level.
        let mut parent = key.parent();
        while parent.level() > 0 {
            // Check that the key itself is there.
            assert!(all_keys.contains_key(&key));
            // Check that all its neighbours are there.
            for neighbor in parent.neighbours().iter().filter(|&key| key.is_valid()) {
                assert!(all_keys.contains_key(neighbor));
            }
            parent = parent.parent();
            // Check that the parent is there.
            assert!(all_keys.contains_key(&parent));
        }
    }

    // At the end check that the root of the tree is also contained.
    assert!(all_keys.contains_key(&MortonKey::root()));

    // Count the number of ghosts on each rank
    // Count the number of global keys on each rank.

    // Assert that all ghosts are from a different rank and count them.

    let nghosts = all_keys
        .iter()
        .filter_map(|(_, &value)| {
            if let KeyType::Ghost(rank) = value {
                assert!(rank != comm.size() as usize);
                Some(rank)
            } else {
                None
            }
        })
        .count();

    if comm.size() == 1 {
        assert_eq!(nghosts, 0);
    } else {
        assert!(nghosts > 0);
    }

    let nglobal = all_keys
        .iter()
        .filter(|(_, &value)| matches!(value, KeyType::Global))
        .count();

    // Assert that all globals across all ranks have the same count.

    let nglobals = gather_to_all(std::slice::from_ref(&nglobal), &comm);

    assert_eq!(nglobals.iter().unique().count(), 1);

    // Check that the points are associated with the correct leaf keys.
    let mut npoints = 0;
    let leaf_point_map = tree.leaf_keys_to_local_point_indices();

    for (key, point_indices) in leaf_point_map {
        for &index in point_indices {
            assert!(key.is_ancestor(tree.point_keys()[index]));
        }
        npoints += point_indices.len();
    }

    // Make sure that the number of points and point keys lines up
    // with the points stored for each leaf key.
    assert_eq!(npoints, tree.points().len());
    assert_eq!(npoints, tree.point_keys().len());

    // Check the neighbour relationships.

    let all_neighbours = tree.neighbour_map();
    let all_keys = tree.all_keys();

    for (key, key_type) in all_keys {
        // Ghost keys should not be in the neighbour map.
        match key_type {
            KeyType::Ghost(_) => assert!(!all_neighbours.contains_key(key)),
            _ => {
                // If it is not a ghost the key should be in the neighbour map.
                assert!(all_neighbours.contains_key(key));
            }
        }
    }

    if comm.rank() == 0 {
        println!("No errors were found in setting up tree.");
    }
}
Source

pub fn child_index(&self) -> usize

Return the index of the key as a child of the parent, i.e. 0, 1, …, 7.

Source

pub fn finest_outer_descendent(&self) -> MortonKey

Return the finest descendent that is opposite to the joint corner with the siblings.

Source

pub fn next_non_descendent_key(&self) -> Option<MortonKey>

Return the next possible Morton key on the deepest level that is not a descendent of the current key.

If the key is already the last possible key then return None.

Source

pub fn linearize(keys: &[MortonKey]) -> Vec<MortonKey>

Linearize by sorting and removing overlaps.

Source

pub fn fill_between_keys(&self, key2: MortonKey) -> Vec<MortonKey>

Fill the region between two keys with a minimal number of keys.

Source

pub fn complete_tree(keys: &[MortonKey]) -> Vec<MortonKey>

Complete a tree ensuring that the given keys are part of the leafs.

The given keys must not overlap.

Source

pub fn get_interior_keys(keys: &[MortonKey]) -> HashSet<MortonKey>

Get all interior keys for an Octree represented by a list of Morton keys

Adds the root at level 0 if the root is not a leaf if the octree. If keys only contains the root of the tree then the returned set is empty.

Source

pub fn get_interior_and_leaf_keys(keys: &[MortonKey]) -> HashSet<MortonKey>

Return interior and leaf keys.

Source

pub fn is_complete_linear_octree(keys: &[MortonKey]) -> bool

Check if a list of Morton keys represent a complete linear tree.

Source

pub fn balance(keys: &[MortonKey], root: MortonKey) -> Vec<MortonKey>

Balance a list of Morton keys with respect to a root key.

Source

pub fn is_complete_linear_and_balanced(keys: &[MortonKey]) -> bool

Returns true if an Octree is linear, complete, and, balanced.

Trait Implementations§

Source§

impl Clone for MortonKey

Source§

fn clone(&self) -> MortonKey

Returns a copy of the value. Read more
1.0.0 · Source§

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source. Read more
Source§

impl Debug for MortonKey

Source§

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter. Read more
Source§

impl Default for MortonKey

Source§

fn default() -> Self

Returns the “default value” for a type. Read more
Source§

impl Display for MortonKey

Source§

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter. Read more
Source§

impl Equivalence for MortonKey

Source§

type Out = DatatypeRef<'static>

The type of the equivalent MPI datatype (e.g. SystemDatatype or UserDatatype)
Source§

fn equivalent_datatype() -> Self::Out

The MPI datatype that is equivalent to this Rust type
Source§

impl Hash for MortonKey

Source§

fn hash<__H: Hasher>(&self, state: &mut __H)

Feeds this value into the given Hasher. Read more
1.3.0 · Source§

fn hash_slice<H>(data: &[Self], state: &mut H)
where H: Hasher, Self: Sized,

Feeds a slice of this type into the given Hasher. Read more
Source§

impl Ord for MortonKey

Source§

fn cmp(&self, other: &MortonKey) -> Ordering

This method returns an Ordering between self and other. Read more
1.21.0 · Source§

fn max(self, other: Self) -> Self
where Self: Sized,

Compares and returns the maximum of two values. Read more
1.21.0 · Source§

fn min(self, other: Self) -> Self
where Self: Sized,

Compares and returns the minimum of two values. Read more
1.50.0 · Source§

fn clamp(self, min: Self, max: Self) -> Self
where Self: Sized,

Restrict a value to a certain interval. Read more
Source§

impl PartialEq for MortonKey

Source§

fn eq(&self, other: &MortonKey) -> bool

Tests for self and other values to be equal, and is used by ==.
1.0.0 · Source§

fn ne(&self, other: &Rhs) -> bool

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.
Source§

impl PartialOrd for MortonKey

Source§

fn partial_cmp(&self, other: &MortonKey) -> Option<Ordering>

This method returns an ordering between self and other values if one exists. Read more
1.0.0 · Source§

fn lt(&self, other: &Rhs) -> bool

Tests less than (for self and other) and is used by the < operator. Read more
1.0.0 · Source§

fn le(&self, other: &Rhs) -> bool

Tests less than or equal to (for self and other) and is used by the <= operator. Read more
1.0.0 · Source§

fn gt(&self, other: &Rhs) -> bool

Tests greater than (for self and other) and is used by the > operator. Read more
1.0.0 · Source§

fn ge(&self, other: &Rhs) -> bool

Tests greater than or equal to (for self and other) and is used by the >= operator. Read more
Source§

impl Copy for MortonKey

Source§

impl Eq for MortonKey

Source§

impl StructuralPartialEq for MortonKey

Auto Trait Implementations§

Blanket Implementations§

Source§

impl<T> Any for T
where T: 'static + ?Sized,

Source§

fn type_id(&self) -> TypeId

Gets the TypeId of self. Read more
§

impl<Src, Scheme> ApproxFrom<Src, Scheme> for Src
where Scheme: ApproxScheme,

§

type Err = NoError

The error type produced by a failed conversion.
§

fn approx_from(src: Src) -> Result<Src, <Src as ApproxFrom<Src, Scheme>>::Err>

Convert the given value into an approximately equivalent representation.
§

impl<Dst, Src, Scheme> ApproxInto<Dst, Scheme> for Src
where Dst: ApproxFrom<Src, Scheme>, Scheme: ApproxScheme,

§

type Err = <Dst as ApproxFrom<Src, Scheme>>::Err

The error type produced by a failed conversion.
§

fn approx_into(self) -> Result<Dst, <Src as ApproxInto<Dst, Scheme>>::Err>

Convert the subject into an approximately equivalent representation.
§

impl<T> AsDatatype for T
where T: Equivalence,

§

type Out = <T as Equivalence>::Out

The type of the associated MPI datatype (e.g. SystemDatatype or UserDatatype)
§

fn as_datatype(&self) -> <T as AsDatatype>::Out

The associated MPI datatype
Source§

impl<T> Borrow<T> for T
where T: ?Sized,

Source§

fn borrow(&self) -> &T

Immutably borrows from an owned value. Read more
Source§

impl<T> BorrowMut<T> for T
where T: ?Sized,

Source§

fn borrow_mut(&mut self) -> &mut T

Mutably borrows from an owned value. Read more
Source§

impl<T> CloneToUninit for T
where T: Clone,

Source§

unsafe fn clone_to_uninit(&self, dst: *mut T)

🔬This is a nightly-only experimental API. (clone_to_uninit)
Performs copy-assignment from self to dst. Read more
§

impl<T> Collection for T
where T: Equivalence,

§

fn count(&self) -> i32

How many things are in this collection.
§

impl<T, Dst> ConvAsUtil<Dst> for T

§

fn approx(self) -> Result<Dst, Self::Err>
where Self: Sized + ApproxInto<Dst>,

Approximate the subject with the default scheme.
§

fn approx_by<Scheme>(self) -> Result<Dst, Self::Err>
where Self: Sized + ApproxInto<Dst, Scheme>, Scheme: ApproxScheme,

Approximate the subject with a specific scheme.
§

impl<T> ConvUtil for T

§

fn approx_as<Dst>(self) -> Result<Dst, Self::Err>
where Self: Sized + ApproxInto<Dst>,

Approximate the subject to a given type with the default scheme.
§

fn approx_as_by<Dst, Scheme>(self) -> Result<Dst, Self::Err>
where Self: Sized + ApproxInto<Dst, Scheme>, Scheme: ApproxScheme,

Approximate the subject to a given type with a specific scheme.
§

fn into_as<Dst>(self) -> Dst
where Self: Sized + Into<Dst>,

Convert the subject to a given type.
§

fn try_as<Dst>(self) -> Result<Dst, Self::Err>
where Self: Sized + TryInto<Dst>,

Attempt to convert the subject to a given type.
§

fn value_as<Dst>(self) -> Result<Dst, Self::Err>
where Self: Sized + ValueInto<Dst>,

Attempt a value conversion of the subject to a given type.
Source§

impl<T> From<T> for T

Source§

fn from(t: T) -> T

Returns the argument unchanged.

Source§

impl<T, U> Into<U> for T
where U: From<T>,

Source§

fn into(self) -> U

Calls U::from(self).

That is, this conversion is whatever the implementation of From<T> for U chooses to do.

Source§

impl<T> IntoEither for T

Source§

fn into_either(self, into_left: bool) -> Either<Self, Self>

Converts self into a Left variant of Either<Self, Self> if into_left is true. Converts self into a Right variant of Either<Self, Self> otherwise. Read more
Source§

fn into_either_with<F>(self, into_left: F) -> Either<Self, Self>
where F: FnOnce(&Self) -> bool,

Converts self into a Left variant of Either<Self, Self> if into_left(&self) returns true. Converts self into a Right variant of Either<Self, Self> otherwise. Read more
§

impl<T> Pointer for T
where T: Equivalence,

§

fn pointer(&self) -> *const c_void

A pointer to the starting address in memory
§

impl<T> PointerMut for T
where T: Equivalence,

§

fn pointer_mut(&mut self) -> *mut c_void

A mutable pointer to the starting address in memory
Source§

impl<T> ToOwned for T
where T: Clone,

Source§

type Owned = T

The resulting type after obtaining ownership.
Source§

fn to_owned(&self) -> T

Creates owned data from borrowed data, usually by cloning. Read more
Source§

fn clone_into(&self, target: &mut T)

Uses borrowed data to replace owned data, usually by cloning. Read more
Source§

impl<T> ToString for T
where T: Display + ?Sized,

Source§

default fn to_string(&self) -> String

Converts the given value to a String. Read more
§

impl<Src> TryFrom<Src> for Src

§

type Err = NoError

The error type produced by a failed conversion.
§

fn try_from(src: Src) -> Result<Src, <Src as TryFrom<Src>>::Err>

Convert the given value into the subject type.
Source§

impl<T, U> TryFrom<U> for T
where U: Into<T>,

Source§

type Error = Infallible

The type returned in the event of a conversion error.
Source§

fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>

Performs the conversion.
§

impl<Src, Dst> TryInto<Dst> for Src
where Dst: TryFrom<Src>,

§

type Err = <Dst as TryFrom<Src>>::Err

The error type produced by a failed conversion.
§

fn try_into(self) -> Result<Dst, <Src as TryInto<Dst>>::Err>

Convert the subject into the destination type.
Source§

impl<T, U> TryInto<U> for T
where U: TryFrom<T>,

Source§

type Error = <U as TryFrom<T>>::Error

The type returned in the event of a conversion error.
Source§

fn try_into(self) -> Result<U, <U as TryFrom<T>>::Error>

Performs the conversion.
§

impl<V, T> VZip<V> for T
where V: MultiLane<T>,

§

fn vzip(self) -> V

§

impl<Src> ValueFrom<Src> for Src

§

type Err = NoError

The error type produced by a failed conversion.
§

fn value_from(src: Src) -> Result<Src, <Src as ValueFrom<Src>>::Err>

Convert the given value into an exactly equivalent representation.
§

impl<Src, Dst> ValueInto<Dst> for Src
where Dst: ValueFrom<Src>,

§

type Err = <Dst as ValueFrom<Src>>::Err

The error type produced by a failed conversion.
§

fn value_into(self) -> Result<Dst, <Src as ValueInto<Dst>>::Err>

Convert the subject into an exactly equivalent representation.
§

impl<T> Buffer for T
where T: Equivalence,

§

impl<T> BufferMut for T
where T: Equivalence,