Iterators

Iterators allow to traverse the tree.

Depth First

The DepthFirstIterator traverses the tree in a depth first manner. If no node is specified the tree is traversed from the root node.

m = meshsphere(1.0, 0.1)
tree = TwoNTree(vertices(m), 0.1)
println(collect(H2Trees.DepthFirstIterator(tree)))

[373, 391, 372, 392, 16, 55, 388, 15, 385, 57, 56, 14, 393, 61, 60, 390, 108, 107, 62, 395, 109, 19, 18, 17, 409, 394, 382, 59, 415, 58, 5, 4, 357, 358, 360, 403, 356, 364, 362, 363, 412, 368, 369, 361, 406, 400, 383, 106, 105, 3, 104, 401, 103, 376, 371, 370, 389, 26, 102, 404, 25, 24, 2, 208, 188, 187, 186, 139, 65, 66, 64, 68, 185, 67, 184, 183, 63, 125, 178, 9, 74, 8, 73, 205, 72, 190, 206, 189, 7, 153, 148, 177, 149, 147, 150, 146, 215, 181, 176, 145, 179, 182, 180, 71, 210, 70, 204, 138, 142, 211, 143, 137, 69, 140, 131, 198, 199, 130, 160, 152, 151, 133, 144, 132, 129, 6, 203, 128, 127, 209, 202, 201, 200, 124, 207, 126, 123, 122, 169, 168, 212, 214, 167, 134, 36, 193, 173, 196, 35, 195, 163, 174, 162, 158, 159, 157, 156, 161, 213, 216, 155, 154, 34, 166, 165, 164, 197, 33, 32, 31, 30, 172, 175, 29, 28, 171, 170, 194, 39, 38, 41, 42, 141, 192, 40, 191, 136, 135, 37, 27, 98, 398, 97, 407, 100, 101, 378, 99, 377, 367, 366, 96, 355, 354, 353, 359, 414, 352, 384, 410, 95, 408, 397, 94, 413, 411, 365, 405, 351, 375, 350, 379, 374, 349, 48, 47, 46, 54, 53, 347, 399, 52, 381, 402, 380, 348, 51, 50, 49, 45, 386, 44, 93, 387, 92, 396, 91, 13, 43, 12, 11, 10, 438, 90, 89, 494, 88, 491, 87, 86, 495, 434, 433, 85, 425, 492, 424, 503, 458, 457, 476, 477, 420, 505, 419, 418, 429, 493, 502, 498, 428, 456, 470, 455, 453, 454, 469, 452, 475, 483, 84, 417, 487, 83, 448, 449, 488, 447, 446, 445, 82, 471, 444, 443, 440, 78, 79, 499, 77, 497, 81, 80, 76, 75, 253, 316, 252, 307, 262, 320, 260, 259, 251, 304, 250, 249, 340, 264, 322, 230, 229, 246, 302, 245, 267, 266, 265, 228, 269, 274, 309, 282, 317, 268, 344, 289, 345, 343, 291, 290, 284, 283, 341, 292, 318, 237, 342, 236, 299, 240, 305, 313, 227, 226, 225, 254, 233, 303, 296, 232, 273, 293, 272, 312, 311, 331, 315, 314, 231, 224, 334, 239, 238, 330, 329, 328, 327, 223, 324, 308, 222, 221, 346, 333, 332, 248, 306, 247, 243, 261, 335, 325, 336, 242, 279, 280, 281, 339, 288, 278, 277, 276, 275, 285, 287, 286, 271, 270, 241, 298, 338, 297, 337, 235, 234, 323, 244, 263, 220, 219, 218, 295, 326, 294, 257, 310, 258, 319, 256, 301, 321, 300, 255, 217, 416, 121, 23, 439, 22, 442, 489, 441, 496, 120, 119, 21, 118, 508, 478, 490, 500, 117, 473, 468, 472, 465, 466, 467, 464, 482, 461, 463, 474, 460, 459, 507, 509, 437, 501, 481, 436, 116, 112, 113, 485, 435, 111, 115, 510, 114, 480, 479, 431, 484, 430, 110, 427, 506, 426, 504, 423, 432, 486, 422, 451, 462, 450, 421, 20, 1]

Parents Upward

The ParentUpwardsIterator is an iterator that iterates over all parent nodes of a given node in a tree until the root is reached. The last node is the node 0.

m = meshsphere(1.0, 0.1)
tree = TwoNTree(vertices(m), 0.1)
println(collect(H2Trees.ParentUpwardsIterator(tree, 373)))

[372, 14, 2, 1]

Children

The ChildIterator is an iterator over the children of a node in a tree.

m = meshsphere(1.0, 0.1)
tree = TwoNTree(vertices(m), 0.1)
println(collect(H2Trees.children(tree, H2Trees.root(tree))))

[2, 6, 27, 10, 75, 224, 217, 20]

Leaves

leaves returns an iterator over the leaf nodes in the tree, starting from the specified node. If no node is specified the tree is traversed from the root node.

m = meshsphere(1.0, 0.1)
tree = TwoNTree(vertices(m), 0.1)
println(collect(H2Trees.leaves(tree)))

[373, 391, 392, 16, 55, 388, 385, 57, 393, 61, 390, 108, 62, 395, 109, 19, 409, 394, 382, 59, 415, 5, 357, 358, 360, 403, 364, 362, 363, 412, 368, 369, 406, 400, 383, 106, 104, 401, 376, 371, 389, 26, 102, 404, 208, 188, 186, 139, 65, 66, 68, 185, 184, 125, 178, 9, 74, 73, 205, 190, 206, 153, 148, 177, 149, 150, 146, 215, 181, 176, 179, 182, 180, 71, 210, 204, 138, 142, 211, 143, 140, 131, 198, 199, 160, 152, 133, 144, 203, 128, 209, 202, 200, 124, 207, 126, 169, 168, 212, 214, 134, 36, 193, 173, 196, 195, 163, 174, 162, 158, 159, 156, 161, 213, 216, 155, 166, 165, 197, 33, 31, 30, 172, 175, 171, 194, 39, 41, 42, 141, 192, 191, 136, 98, 398, 407, 100, 101, 378, 377, 367, 355, 354, 353, 359, 414, 384, 410, 95, 408, 397, 413, 411, 365, 405, 351, 375, 379, 374, 349, 48, 54, 53, 347, 399, 381, 402, 348, 51, 45, 386, 93, 387, 396, 91, 13, 43, 438, 90, 89, 494, 491, 87, 495, 434, 425, 492, 503, 458, 476, 477, 420, 505, 429, 493, 502, 498, 456, 470, 455, 453, 454, 469, 475, 483, 84, 417, 487, 448, 449, 488, 447, 446, 471, 444, 440, 78, 79, 499, 497, 81, 253, 316, 307, 262, 320, 260, 251, 304, 340, 264, 322, 230, 246, 302, 267, 266, 269, 274, 309, 282, 317, 344, 289, 345, 343, 291, 290, 284, 341, 292, 318, 237, 342, 299, 240, 305, 313, 227, 254, 233, 303, 296, 273, 293, 312, 331, 315, 334, 239, 330, 329, 327, 223, 324, 308, 346, 333, 332, 248, 306, 243, 261, 335, 325, 336, 279, 280, 281, 339, 288, 278, 277, 275, 285, 287, 286, 271, 298, 338, 337, 235, 323, 244, 263, 220, 295, 326, 257, 310, 258, 319, 301, 321, 416, 121, 23, 439, 442, 489, 496, 120, 118, 508, 478, 490, 500, 473, 468, 472, 465, 466, 467, 482, 461, 463, 474, 460, 507, 509, 437, 501, 481, 112, 113, 485, 435, 115, 510, 480, 431, 484, 427, 506, 504, 423, 432, 486, 451, 462]

Level Iterator

LevelIterator return an iterator over the nodes at the specified level in the tree.

m = meshsphere(1.0, 0.1)
tree = TwoNTree(vertices(m), 0.1)
println(collect(H2Trees.LevelIterator(tree,2)))

[2, 6, 10, 20, 27, 75, 217, 224]

Same Level Nodes

[SameLevelIterator] returns an iterator over the nodes at the same level as node in the tree.

m = meshsphere(1.0, 0.1)
tree = TwoNTree(vertices(m), 0.1)
println(collect(H2Trees.SameLevelIterator(tree,3)))

[3, 7, 11, 14, 17, 21, 24, 28, 34, 37, 46, 49, 63, 69, 76, 82, 85, 96, 110, 116, 122, 129, 218, 221, 225, 228, 231, 241, 249, 255, 418, 421]

Near- and Far Nodes

The NearNodeIterator returns, in the Galerkin case, an iterator over the nodes in the tree that are at the same level as the specified node and are near to node. Two nodes are near if the function isnear(tree, nodea, nodeb) evaluates to true.

m = meshsphere(1.0, 0.1)
tree = TwoNTree(vertices(m), 0.1)
println("node 4 is at level ", H2Trees.level(tree, 4))
println("nodes near to node 4: ", collect(H2Trees.NearNodeIterator(tree, 4)))

node 4 is at level 4
nodes near to node 4: [4, 58, 105, 137, 352, 356, 361, 436]

In the Petrov-Galerkin case the NearNodeIterator returns an iterator over the nodes in the testtree that are at the same level as the specified node in the trialtree and are near to node. Two nodes are near if the function isnear(testtree, trialtree, testnode, trialnode) evaluates to true.

mx = meshsphere(1.0, 0.1)
my = meshsphere(2.0, 0.1)

testtree = TwoNTree(vertices(mx), 0.1)
trialtree = TwoNTree(vertices(my), 0.1)
println("trial node 4 is at level ", H2Trees.level(trialtree, 4))
println("nodes near to trial node 4: ", collect(H2Trees.NearNodeIterator(testtree, trialtree, 4)))

trial node 4 is at level 4
nodes near to trial node 4: [4, 15, 18, 25, 47, 50, 52, 56, 58, 60, 64, 67, 70, 94, 97, 99, 103, 105, 107, 111, 114, 117, 123, 127, 130, 132, 137, 145, 147, 151, 154, 167, 183, 187, 201, 242, 247, 256, 294, 300, 350, 352, 356, 361, 366, 370, 372, 380, 419, 422, 424, 426, 428, 430, 436, 445, 450, 457, 459, 464, 479]

The FarNodeIterator is defined accordingly.

Well Separated Nodes

The WellSeparatedIterator is used to identify which translations should occur and which should not. This determination is based on the concept of well-separated nodes.

The WellSeparatedIterator can be configured using either an isnear or an iswellseparated function.

The following example demonstrates the usage of the WellSeparatedIterator in the Galerkin-case

m = meshsphere(1.0, 0.1)
tree = KMeansTree(vertices(m), 4; minvalues=60)

# Using the WellSeparatedIterator with the default isnear() function
println("First iterator\t", collect(H2Trees.WellSeparatedIterator(tree, 3)))

# Creating a functor without specifying a tree first
functor = H2Trees.WellSeparatedIterator()
iterator = functor(tree)
println("Second iterator\t", collect(iterator(tree, 3)))

# Specifying a custom iswellseparated criterion
functor = H2Trees.WellSeparatedIterator(; iswellseparated=(tree) -> (tree, nodea, nodeb) -> iseven(nodea))
iterator = functor(tree)
println("Third iterator\t", collect(iterator(tree, 3)))

# Specifying a custom isnear criterion
functor = H2Trees.WellSeparatedIterator(; isnear=(tree) -> (tree, nodea, nodeb) -> iseven(nodea))
iterator = functor(tree)
println("Fourth iterator\t", collect(iterator(tree, 3)))

First iterator	[39, 50]
Second iterator	[39, 50]
Third iterator	[8, 18, 24, 34, 50, 60, 66, 76]
Fourth iterator	[3, 13, 45, 55]

When defining the isnear or iswellseparated criterion, it is necessary to provide a function that takes a tree as input and returns another function. This returned function is then used to evaluate the criterion.

At first glance, this may seem like an unnecessary layer of indirection. However, it actually provides a significant advantage: it enables precomputations that can be performed only once, when the criterion function is first created, rather than every time the iterator is called.

By allowing the initial function to perform any necessary precomputations and store the results, the returned function can then simply use these precomputed values to evaluate the criterion. This can significantly improve performance, especially when working with large trees or complex criteria.

For the Petrov-Galerkin case, we assume that translations occur from the trialtree to the testtree. This scenario can be demonstrated with the following example

mx = meshsphere(1.0, 0.1)
my = meshsphere(2.0, 0.1)

tree = TwoNTree(vertices(mx), vertices(my), 0.1)

# Using the WellSeparatedIterator with the default isnear() function
println("First iterator\t", collect(H2Trees.WellSeparatedIterator(tree, 4)))

# Creating a functor without specifying a tree first
functor = H2Trees.WellSeparatedIterator()
iterator = functor(tree)
println("Second iterator\t", collect(iterator(H2Trees.testtree(tree), H2Trees.trialtree(tree), 4)))

# Specifying a custom iswellseparated criterion
functor = H2Trees.WellSeparatedIterator(;
    iswellseparated=(tree) -> (testtree, trialtree, testnode, trialnode) -> iseven(testnode)
)
iterator = functor(tree)
println("Third iterator\t", collect(iterator(H2Trees.testtree(tree), H2Trees.trialtree(tree), 4)))

# Specifying a custom isnear criterion
functor = H2Trees.WellSeparatedIterator(;
    isnear=(tree) -> (testtree, trialtree, testnode, trialnode) -> iseven(testnode)
)
iterator = functor(tree)
println("Fourth iterator\t", collect(iterator(H2Trees.testtree(tree), H2Trees.trialtree(tree), 4)))

First iterator	[7, 11, 21, 28, 37, 76, 85, 218, 221, 228, 231, 249]
Second iterator	[7, 11, 21, 28, 37, 76, 85, 218, 221, 228, 231, 249]
Third iterator	[14, 24, 28, 34, 46, 76, 82, 96, 110, 116, 122, 218, 228, 418]
Fourth iterator	[3, 7, 11, 17, 21, 49, 63, 69, 129, 225, 231, 249, 421]

In general, it is more efficient to use functors instead of functions in this context.

Translating Nodes

The TranslatingNodesIterator is a wrapper for the WellSeparatedIterator.

Filtering Nodes

NodeFilterIterator returns an iterator over nodes at the same level as trialnode in trialtree, for which the function filter(testtree, trialtree, testnode, trialnode) return true. In the case of a tree with the trait isBlockTree, it is assumed that trialnode is belonging to the trialtree. For the Galerkin case, we have

m = meshsphere(1.0, 0.1)
tree = TwoNTree(vertices(m), 0.1)
println(collect(H2Trees.NodeFilterIterator(tree, 3, (tree, nodea, nodeb)-> iseven(nodea))))

[14, 24, 28, 34, 46, 76, 82, 96, 110, 116, 122, 218, 228, 418]

and for the Petrov-Galerkin case

mx = meshsphere(1.0, 0.1)
my = meshsphere(2.0, 0.1)

tree = TwoNTree(vertices(mx), vertices(my), 0.1)
testtree = H2Trees.testtree(tree)
trialtree = H2Trees.trialtree(tree)
println(collect(H2Trees.NodeFilterIterator(tree, 3, (testree, trialtree, testnode, trialnode)-> iseven(testnode))))

[2, 6, 10, 20, 224]

and

mx = meshsphere(1.0, 0.1)
my = meshsphere(2.0, 0.1)

tree = TwoNTree(vertices(mx), vertices(my), 0.1)
testtree = H2Trees.testtree(tree)
trialtree = H2Trees.trialtree(tree)
println(collect(H2Trees.NodeFilterIterator(testtree, trialtree, 3, (testree, trialtree, testnode, trialnode)-> iseven(testnode))))

[2, 6, 10, 20, 224]