• Home
  • Features
  • Pricing
  • Docs
  • Announcements
  • Sign In

NREL / SolTrace / 20283049329

16 Dec 2025 09:19PM UTC coverage: 88.351% (-0.8%) from 89.184%
20283049329

Pull #91

github

web-flow
Merge d2f36f095 into a73a760a4
Pull Request #91: Implement multi-threading in NativeRunner

366 of 468 new or added lines in 11 files covered. (78.21%)

34 existing lines in 6 files now uncovered.

6007 of 6799 relevant lines covered (88.35%)

7475791.74 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

78.82
/coretrace/simulation_runner/native_runner/treemesh.cpp
1

2
/*******************************************************************************************************
3
 *  Copyright 2018 Alliance for Sustainable Energy, LLC
4
 *
5
 *  NOTICE: This software was developed at least in part by Alliance for Sustainable Energy, LLC
6
 *  ("Alliance") under Contract No. DE-AC36-08GO28308 with the U.S. Department of Energy and the U.S.
7
 *  The Government retains for itself and others acting on its behalf a nonexclusive, paid-up,
8
 *  irrevocable worldwide license in the software to reproduce, prepare derivative works, distribute
9
 *  copies to the public, perform publicly and display publicly, and to permit others to do so.
10
 *
11
 *  Redistribution and use in source and binary forms, with or without modification, are permitted
12
 *  provided that the following conditions are met:
13
 *
14
 *  1. Redistributions of source code must retain the above copyright notice, the above government
15
 *  rights notice, this list of conditions and the following disclaimer.
16
 *
17
 *  2. Redistributions in binary form must reproduce the above copyright notice, the above government
18
 *  rights notice, this list of conditions and the following disclaimer in the documentation and/or
19
 *  other materials provided with the distribution.
20
 *
21
 *  3. The entire corresponding source code of any redistribution, with or without modification, by a
22
 *  research entity, including but not limited to any contracting manager/operator of a United States
23
 *  National Laboratory, any institution of higher learning, and any non-profit organization, must be
24
 *  made publicly available under this license for as long as the redistribution is made available by
25
 *  the research entity.
26
 *
27
 *  4. Redistribution of this software, without modification, must refer to the software by the same
28
 *  designation. Redistribution of a modified version of this software (i) may not refer to the modified
29
 *  version by the same designation, or by any confusingly similar designation, and (ii) must refer to
30
 *  the underlying software originally provided by Alliance as "SolTrace". Except to comply with the
31
 *  foregoing, the term "SolTrace", or any confusingly similar designation may not be used to refer to
32
 *  any modified version of this software or any modified version of the underlying software originally
33
 *  provided by Alliance without the prior written consent of Alliance.
34
 *
35
 *  5. The name of the copyright holder, contributors, the United States Government, the United States
36
 *  Department of Energy, or any of their employees may not be used to endorse or promote products
37
 *  derived from this software without specific prior written permission.
38
 *
39
 *  THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR
40
 *  IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND
41
 *  FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER,
42
 *  CONTRIBUTORS, UNITED STATES GOVERNMENT OR UNITED STATES DEPARTMENT OF ENERGY, NOR ANY OF THEIR
43
 *  EMPLOYEES, BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
44
 *  DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
45
 *  DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER
46
 *  IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF
47
 *  THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
48
 *******************************************************************************************************/
49

50
#include "treemesh.hpp"
51

52
#include <algorithm>
53
#include <cmath>
54
#include <cstdio>
55
#include <limits>
56
#include <set>
57
#include <string>
58
#include <unordered_map>
59

60
namespace SolTrace::NativeRunner {
61

62
//-------------------------------------------------------------------------------------------------
63

64
inline bool binary_add(const std::string &key, std::string &modkey, int val[2])
76,720✔
65
{
66
    /*
67
    key is:
68
    "x0-y0-x1-y1-x2-y2..."
69
    without the dashes
70

71
    val is:
72
    <adder in x (-1,0,1)>,<adder in y>
73

74
    modkey is the sum of key and val
75

76
    Binary addition. The summed number will necessarily be of the same length as the value provided because of
77
    the resolution requirements for the binary tree.
78

79
    If this is adapted for some other purpose, the summed number should probably be shifted so that there's
80
    room for extra leading digits.
81
    */
82

83
    int lx = 0;
76,720✔
84
    int ly = 0;
76,720✔
85
    for (int i = 0; i < key.size(); i += 2)
613,168✔
86
    {
87
        if (key.at(i) == 'x')
536,448✔
UNCOV
88
            break;
×
89
        lx++;
536,448✔
90
    }
91
    for (int i = 1; i < key.size(); i += 2)
536,560✔
92
    {
93
        if (key.at(i) == 'x')
536,448✔
94
            break;
76,608✔
95
        ly++;
459,840✔
96
    }
97

98
    modkey = key; // copy
76,720✔
99

100
    // deal with x
101
    int xadd = val[0];
76,720✔
102
    int c = 0;
76,720✔
103
    bool first = true;
76,720✔
104
    for (int i = 2 * (lx - 1); i > -1; i -= 2)
133,024✔
105
    {
106
        int n = (int)(key.at(i) == '1');
133,024✔
107
        if (first)
133,024✔
108
            n += xadd;
76,720✔
109
        else
110
            n += c;
56,304✔
111
        first = false;
133,024✔
112

113
        if (n > 1)
133,024✔
114
        {
115
            modkey.at(i) = '0';
28,206✔
116
            c = 1;
28,206✔
117
        }
118
        else if (n < 0)
104,818✔
119
        {
120
            modkey.at(i) = '1';
28,242✔
121
            c = -1;
28,242✔
122
        }
123
        else
124
        {
125
            modkey.at(i) = n == 0 ? '0' : '1'; // 0 or 1
76,576✔
126
            c = 0;
76,576✔
127
            break;
76,576✔
128
        }
129

130
        if (i == 0 && c != 0)
56,448✔
131
        {
132
            // out of bounds
133
            return false;
144✔
134
        }
135
    }
136

137
    // deal with y
138
    int yadd = val[1];
76,576✔
139
    c = 0;
76,576✔
140
    first = true;
76,576✔
141
    for (int i = 2 * (ly - 1) + 1; i > 0; i -= 2)
131,840✔
142
    {
143
        int n = (int)(key.at(i) == '1');
131,638✔
144
        if (first)
131,638✔
145
            n += yadd;
76,576✔
146
        else
147
            n += c;
55,062✔
148
        first = false;
131,638✔
149

150
        if (n > 1)
131,638✔
151
        {
152
            modkey.at(i) = '0';
27,458✔
153
            c = 1;
27,458✔
154
        }
155
        else if (n < 0)
104,180✔
156
        {
157
            modkey.at(i) = '1';
27,806✔
158
            c = -1;
27,806✔
159
        }
160
        else
161
        {
162
            modkey[i] = n == 0 ? '0' : '1'; // 0 or 1
76,374✔
163
            c = 0;
76,374✔
164
            break;
76,374✔
165
        }
166

167
        if (i == 0 && c != 0)
55,264✔
168
        {
169
            // out of bounds
170
            return false;
×
171
        }
172
    }
173

174
    return true;
76,576✔
175
}
176

177
st_tree_node::st_tree_node()
36,342✔
178
{
179
    // Initialize
180
    m0 = m1 = 0;
36,342✔
181
    terminal = false;
36,342✔
182
}
36,342✔
183

184
void st_tree_node::setup(st_tree_node *child0)
9,576✔
185
{
186
    // Set both children equal to specified node. Used for 'x' keys.
187
    terminal = false;
9,576✔
188
    m0 = child0;
9,576✔
189
    m1 = m0;
9,576✔
190
}
9,576✔
191
void st_tree_node::setup(st_tree_node *child0, st_tree_node *child1)
26,718✔
192
{
193
    // Set children nodes equal to node pointer values (as applicable). For ptrs to 0, don't set.
194
    terminal = false;
26,718✔
195
    if (child0 != 0)
26,718✔
196
        m0 = child0;
13,356✔
197
    if (child1 != 0)
26,718✔
198
        m1 = child1;
13,362✔
199
}
26,718✔
200
void st_tree_node::setup(void *Data)
16,176✔
201
{
202
    // Set node as terminal and add data
203
    terminal = true;
16,176✔
204
    if (Data != 0) // Don't try to add a null value
16,176✔
205
        data.push_back(Data);
12,586✔
206
}
16,176✔
207
bool st_tree_node::is_terminal()
258,096✔
208
{
209
    return terminal;
258,096✔
210
}
211
std::vector<void *> *st_tree_node::get_array()
453,224✔
212
{
213
    return &data;
453,224✔
214
}
215
st_tree_node *st_tree_node::m_proc(std::string &key, int index)
6,005,937✔
216
{
217
    /*
218
    ** Recursive **
219

220
    Process 'key' string at current index. Traverses tree structure. If no node is found at the specified index,
221
    return 0.
222

223
    */
224

225
    char c;
226
    try
227
    {
228
        c = key.at(index);
6,005,937✔
229
    }
230
    catch (...)
317,214✔
231
    {
232
        return this;
317,214✔
233
    }
317,214✔
234
    if (terminal)
5,688,723✔
235
        return this;
75,232✔
236
    switch (c)
5,613,491✔
237
    {
238
    case 't':
×
239
        return this;
×
240
    case 'x':
2,838,505✔
241
    case '0':
242
        if (m0 != 0)
2,838,505✔
243
            return m0->m_proc(key, index + 1);
2,794,830✔
244
        else
245
            return 0;
43,675✔
246
    case '1':
2,774,986✔
247
        if (m1 != 0)
2,774,986✔
248
            return m1->m_proc(key, index + 1);
2,732,460✔
249
        else
250
            return 0;
42,526✔
251
    }
252

253
    return 0;
×
254
}
255
std::vector<st_tree_node *> st_tree_node::m_get_children()
×
256
{
257
    std::vector<st_tree_node *> kids;
×
258
    if (!terminal)
×
259
    {
260
        if (m0 == m1)
×
261
        {
262
            kids.push_back(m0);
×
263
            std::vector<st_tree_node *> m0kids = m0->m_get_children();
×
264
            for (unsigned int i = 0; i < m0kids.size(); i++)
×
265
                kids.push_back(m0kids.at(i));
×
266
        }
×
267
        else
268
        {
269
            kids.push_back(m0);
×
270
            kids.push_back(m1);
×
271
            std::vector<st_tree_node *> m0kids = m0->m_get_children();
×
272
            std::vector<st_tree_node *> m1kids = m1->m_get_children();
×
273
            for (unsigned int i = 0; i < m0kids.size(); i++)
×
274
                kids.push_back(m0kids.at(i));
×
275
            for (unsigned int i = 0; i < m1kids.size(); i++)
×
276
                kids.push_back(m1kids.at(i));
×
277
        }
×
278
    }
279
    return kids;
×
280
}
×
281
std::vector<void *> st_tree_node::get_child_data()
×
282
{
283
    if (terminal)
×
284
    {
285
        return data;
×
286
    }
287
    else
288
    {
289
        if (m0 == m1)
×
290
        {
291
            return m0->get_child_data();
×
292
        }
293
        else
294
        {
295
            std::vector<void *> m0dat, m1dat, alldat;
×
296
            m0dat = m0->get_child_data();
×
297
            m1dat = m1->get_child_data();
×
298
            for (unsigned int i = 0; i < m0dat.size(); i++)
×
299
                alldat.push_back(m0dat.at(i));
×
300
            for (unsigned int i = 0; i < m1dat.size(); i++)
×
301
                alldat.push_back(m1dat.at(i));
×
302
            return alldat;
×
303
        }
×
304
    }
305
}
306

307
st_tree_node *st_tree_node::get_child_node(bool upper)
408,858✔
308
{
309
    return upper ? m1 : m0;
408,858✔
310
}
311

312
std::string st_tree_node::get_address()
113,014✔
313
{
314
    return address;
113,014✔
315
}
316

317
void st_tree_node::set_address(const std::string &addr)
36,294✔
318
{
319
    address = addr;
36,294✔
320
}
36,294✔
321

322
//-------------------------------------------------------------------------------------------------
323
void st_opt_element::set_range(double xrlo, double xrhi, double yrlo, double yrhi)
4✔
324
{
325
    xr[0] = xrlo;
4✔
326
    xr[1] = xrhi;
4✔
327
    yr[0] = yrlo;
4✔
328
    yr[1] = yrhi;
4✔
329
}
4✔
330

331
void st_opt_element::set_range(double *xri, double *yri)
36,294✔
332
{
333
    for (int i = 0; i < 2; i++)
108,882✔
334
    {
335
        xr[i] = xri[i];
72,588✔
336
        yr[i] = yri[i];
72,588✔
337
    }
338
}
36,294✔
339

340
st_opt_element *st_opt_element::process(std::string &key, int index)
478,647✔
341
{
342
    return (st_opt_element *)m_proc(key, index);
478,647✔
343
}
344

345
std::vector<st_opt_element *> st_opt_element::get_children()
×
346
{
347
    std::vector<st_opt_element *> children;
×
348
    std::vector<st_tree_node *> m_children = m_get_children();
×
349
    for (auto it = m_children.begin(); it != m_children.end(); it++)
×
350
        children.push_back((st_opt_element *)*it);
×
351
    return children;
×
352
}
×
353

354
double *st_opt_element::get_yr() { return yr; }
481,094✔
355
double *st_opt_element::get_xr() { return xr; }
481,094✔
356

357
void st_opt_element::add_neighbor(void *ptr)
×
358
{
359
    neighbors.push_back(ptr);
×
360
}
×
361

362
std::vector<void *> *st_opt_element::get_neighbor_data()
434,748✔
363
{
364
    return &neighbors;
434,748✔
365
}
366

367
//-------------------------------------------------------------------------------------------------
368
st_hash_tree::st_hash_tree()
48✔
369
{
370
    log2inv = 1. / log(2.);
48✔
371
}
48✔
372

373
bool st_hash_tree::create_mesh(KDLayoutData &data)
4✔
374
{
375
    /*
376
    Create a mesh of the heliostat field according to the performance surface
377
    provided by the 'integrals' class.
378
    */
379
    Data = data;
4✔
380

381
    // Calculate min and max recursion levels based on user zone size limitations
382
    double dextx = (Data.xlim[1] - Data.xlim[0]);
4✔
383
    nx_req = (int)floor(log(dextx / Data.min_unit_dx) * log2inv);
4✔
384
    nx_req = nx_req < 1 ? 1 : nx_req;
4✔
385
    double dexty = (Data.ylim[1] - Data.ylim[0]);
4✔
386
    ny_req = (int)floor(log(dexty / Data.min_unit_dy) * log2inv);
4✔
387
    ny_req = ny_req < 1 ? 1 : ny_req;
4✔
388

389
    // estimate the maximum number of nodes and reserve memory
390
    int nmaxdivx = (int)pow(2., nx_req);            // maximum number of zones x
4✔
391
    int nmaxdivy = (int)pow(2., ny_req);            // max y
4✔
392
    int nmaxterm = nmaxdivx * nmaxdivy;             // total max number of zones
4✔
393
    int maxreclevel = std::max(nmaxdivx, nmaxdivy); // worst case max recursion level
4✔
394
    int nmaxnodes = 0;
4✔
395
    for (int i = 0; i < maxreclevel; i++)
266✔
396
        nmaxnodes += nmaxterm / (int)pow(2., i); // Add each level in the node tree
262✔
397

398
    // Try reserving the number of required nodes, catch any memory error
399
    try
400
    {
401
        nodes.reserve(nmaxnodes * 2); // include a 100% buffer
4✔
402
    }
403
    catch (...)
×
404
    {
405
        // Memory error
406
        return false;
×
407
    }
×
408

409
    // set up the head node's range. This doesn't actually create the tree yet.
410
    head_node.set_range(Data.xlim[0], Data.xlim[1], Data.ylim[0], Data.ylim[1]);
4✔
411

412
    return true;
4✔
413
}
414

415
std::string st_hash_tree::pos_to_binary_base(double x, double y)
418,247✔
416
{
417
    double res = fmin(Data.min_unit_dx, Data.min_unit_dy);
418,247✔
418
    return pos_to_binary(x, y, res);
418,247✔
419
}
420

421
void st_hash_tree::reset()
×
422
{
423
    Data.min_unit_dx =
×
424
        Data.min_unit_dy =
×
425
            Data.xlim[0] = Data.xlim[1] = Data.ylim[0] = Data.ylim[1] =
×
426
                std::numeric_limits<double>::quiet_NaN();
×
427

428
    head_node = st_opt_element();
×
429
    nodes.clear();
×
430
    nx_req = -1;
×
431
    ny_req = -1;
×
432
}
×
433

434
void st_hash_tree::get_terminal_data(std::vector<std::vector<void *> *> &retdata)
×
435
{
436

437
    for (auto it = nodes.begin(); it != nodes.end(); it++)
×
438
    {
439
        if (!it->is_terminal())
×
440
            continue;
×
441
        retdata.push_back(it->get_array());
×
442
    }
443
}
×
444
void st_hash_tree::get_terminal_nodes(std::vector<st_opt_element *> &tnodes)
4✔
445
{
446

447
    tnodes.clear();
4✔
448

449
    for (int i = 0; i < (int)nodes.size(); i++)
31,940✔
450
    {
451
        if (nodes.at(i).is_terminal())
31,936✔
452
            tnodes.push_back(&nodes.at(i));
9,590✔
453
    }
454

455
    return;
4✔
456
}
457

458
std::vector<st_opt_element> *st_hash_tree::get_all_nodes()
×
459
{
460
    return &nodes;
×
461
}
462

463
void st_hash_tree::add_neighborhood_data()
4✔
464
{
465
    /*
466
    Collect the data elements that surround addresses that already contain elements. If the neighboring elements
467
    of the same resolution are empty (no data), then create empty zones and flag as needing to be processed.
468
    */
469

470
    std::vector<st_opt_element *> tnodes;
4✔
471
    std::unordered_map<std::string, std::set<st_opt_element *>> empty_nb_map;
4✔
472

473
    get_terminal_nodes(tnodes);
4✔
474
    for (int k = 0; k < tnodes.size(); k++)
9,594✔
475
    {
476
        st_opt_element *node = tnodes.at(k);
9,590✔
477
        int add[2];
478

479
        for (int i = -1; i < 2; i++)
38,360✔
480
        {
481
            for (int j = -1; j < 2; j++)
115,080✔
482
            {
483
                if (i == 0 && j == 0)
86,310✔
484
                    continue; // omit self zone
9,590✔
485

486
                // do binary addition to find the specified neighboring zone
487
                add[0] = i;
76,720✔
488
                add[1] = j;
76,720✔
489

490
                std::string nzone;
76,720✔
491

492
                if (binary_add(node->get_address(), nzone, add))
76,720✔
493
                {
494
                    st_opt_element *el = head_node.process(nzone, 0);
76,576✔
495
                    if (el != 0)
76,576✔
496
                    {
497
                        std::vector<void *> *dat = el->get_array();
58,206✔
498
                        if (dat != 0)
58,206✔
499
                        {
500
                            for (int k = 0; k < dat->size(); k++)
137,510✔
501
                                node->get_neighbor_data()->push_back(dat->at(k));
79,304✔
502
                        }
503
                    }
504
                    else
505
                    {
506
                        empty_nb_map[nzone].insert(node);
18,370✔
507
                    }
508
                }
509
            }
76,720✔
510
        }
511
    }
512

513
    // Go back and add empty neighbors that were identified
514
    for (auto mp = empty_nb_map.begin(); mp != empty_nb_map.end(); mp++)
3,594✔
515
    {
516
        double x, y;
517
        // get center of zone
518
        binary_to_pos(mp->first, &x, &y);
3,590✔
519
        // get an appropriate element size to add
520
        double *xr = (*mp->second.begin())->get_xr();
3,590✔
521
        double *yr = (*mp->second.begin())->get_yr();
3,590✔
522
        double rmin[2];
523
        rmin[0] = (xr[1] - xr[0]) * 0.55; // make the "object" smaller than the previous zone size but larger than half the zone size
3,590✔
524
        rmin[1] = (yr[1] - yr[0]) * 0.55;
3,590✔
525
        // Add the element (actually just create the empty terminal zone)
526
        add_object(0, x, y, rmin);
3,590✔
527

528
        // now add neighbors directly to the new terminal zone
529
        st_opt_element *newnode = &nodes.back();
3,590✔
530
        for (auto nit = mp->second.begin(); nit != mp->second.end(); nit++)
21,960✔
531
        {
532
            for (int j = 0; j < (*nit)->get_array()->size(); j++)
39,574✔
533
                newnode->get_neighbor_data()->push_back((*nit)->get_array()->at(j));
21,204✔
534
        }
535
    }
536
}
4✔
537

538
bool st_hash_tree::get_all_data_at_loc(std::vector<void *> &data,
402,071✔
539
                                       double locx, double locy)
540
{
541
    std::string bin = pos_to_binary_base(locx, locy);
402,071✔
542

543
    data.clear();
402,071✔
544

545
    st_opt_element *z = head_node.process(bin, 0);
402,071✔
546
    if (z != 0)
402,071✔
547
    {
548
        std::vector<void *> *zd = z->get_array();
334,240✔
549
        if (zd != 0)
334,240✔
550
            for (int i = 0; i < zd->size(); i++)
665,690✔
551
                data.push_back(zd->at(i));
331,450✔
552

553
        zd = z->get_neighbor_data();
334,240✔
554
        if (zd != 0)
334,240✔
555
            for (int i = 0; i < zd->size(); i++)
2,797,308✔
556
                data.push_back(zd->at(i));
2,463,068✔
557

558
        if (!data.empty())
334,240✔
559
            return true;
334,240✔
560
    }
561

562
    return false;
67,831✔
563
}
402,071✔
564

565
void st_hash_tree::create_node(st_opt_element &node, int index, std::string &binary, void *object, double *dprojected)
238,752✔
566
{
567
    /*
568
    node        |   pointer to parent node
569
    index       |   current character location in the string 'binary'
570
    binary      |   string of characters indicating the path to follow to create a new node
571
    object      |   pointer to the object that is to be added to the new node
572
    dprojected  |   2-value array: 1st value is span in azimuthal direction, 2nd value spans zenith direction
573
    */
574

575
    // evaluate the derivatives at the center of the element.
576
    double
577
        xr0 = node.get_xr()[0],
238,752✔
578
        xr1 = node.get_xr()[1],
238,752✔
579
        yr0 = node.get_yr()[0],
238,752✔
580
        yr1 = node.get_yr()[1],
238,752✔
581
        C0 = (xr0 + xr1) * 0.5,
238,752✔
582
        C1 = (yr0 + yr1) * 0.5;
238,752✔
583
    double dpx, dpy;
584
    if (dprojected == 0)
238,752✔
585
    {
586
        dpx = 0.;
188,546✔
587
        dpy = 0.;
188,546✔
588
    }
589
    else
590
    {
591
        dpx = dprojected[0];
50,206✔
592
        dpy = dprojected[1];
50,206✔
593
    }
594

595
    bool x_direction = (double)(index / 2) == ((double)index / 2.);
238,752✔
596

597
    int x_rec_level, y_rec_level;
598

599
    if (x_direction)
238,752✔
600
    {
601
        x_rec_level = index / 2;
125,672✔
602
        y_rec_level = x_rec_level - 1;
125,672✔
603
    }
604
    else
605
    {
606
        x_rec_level = y_rec_level = (index - 1) / 2;
113,080✔
607
    }
608

609
    // check to see if we're at the end of the string
610
    if (index > binary.size() - 1)
238,752✔
611
    {
612
        // Add the object to the data vector and return
613
        node.setup(object);
12,592✔
614
        return;
12,592✔
615
    }
616

617
    // check to see if this node is terminal. If so, add the data here rather than continuing branching.
618
    if (node.is_terminal())
226,160✔
619
    {
UNCOV
620
        node.setup(object);
×
UNCOV
621
        return;
×
622
    }
623

624
    // which direction split is indicated?
625
    bool split_pos = binary.at(index) == '1';
226,160✔
626

627
    if (x_direction)
226,160✔
628
    {
629
        if (x_rec_level < nx_req && dpx < (C0 - xr0))
113,080✔
630
        {
631

632
            // does a node already exist in the proposed split direction?
633
            if (node.get_child_node(split_pos) == 0)
113,080✔
634
            {
635
                // we can split in the x direction
636
                nodes.push_back(st_opt_element());
17,738✔
637
                st_opt_element *m = &nodes.back();
17,738✔
638
                m->set_address(node.get_address() + binary.at(index));
17,738✔
639

640
                if (split_pos) // upper
17,738✔
641
                {
642
                    double xr[] = {C0, xr1};
8,862✔
643
                    double yr[] = {yr0, yr1};
8,862✔
644
                    m->set_range(xr, yr);
8,862✔
645
                    node.setup(0, m);
8,862✔
646

647
                    create_node(*m, index + 1, binary, object, dprojected);
8,862✔
648
                    return;
8,862✔
649
                }
650
                else // lower
651
                {
652
                    double xr[] = {xr0, C0};
8,876✔
653
                    double yr[] = {yr0, yr1};
8,876✔
654
                    m->set_range(xr, yr);
8,876✔
655
                    node.setup(m, 0);
8,876✔
656

657
                    create_node(*m, index + 1, binary, object, dprojected);
8,876✔
658
                    return;
8,876✔
659
                }
660
            }
661
            else
662
            {
663
                // a node already exists, so just follow along without adding a new node in its place
664
                create_node(*(st_opt_element *)(node.get_child_node(split_pos)), index + 1, binary, object, dprojected);
95,342✔
665
                return;
95,342✔
666
            }
667
        }
668
        else
669
        {
670
            // no more splits allowed in the x direction
671
            // check if more y splits are allowed
UNCOV
672
            if (y_rec_level < ny_req && dpy < (C1 - yr0))
×
673
            {
UNCOV
674
                if (node.get_child_node(split_pos) == 0)
×
675
                {
UNCOV
676
                    nodes.push_back(st_opt_element());
×
UNCOV
677
                    st_opt_element *m = &nodes.back();
×
678

UNCOV
679
                    double xr[] = {xr0, xr1};
×
UNCOV
680
                    double yr[] = {yr0, yr1};
×
681

UNCOV
682
                    m->set_range(xr, yr);
×
UNCOV
683
                    m->set_address(node.get_address() + "x");
×
UNCOV
684
                    node.setup(m);
×
685

UNCOV
686
                    create_node(*m, index + 1, binary, object, dprojected);
×
UNCOV
687
                    return;
×
688
                }
689
                else
690
                {
UNCOV
691
                    create_node(*(st_opt_element *)(node.get_child_node(split_pos)), index + 1, binary, object, dprojected);
×
UNCOV
692
                    return;
×
693
                }
694
            }
695
            else
696
            {
697
                // no more y splits are allowed either, so add the object and return
UNCOV
698
                node.setup(object);
×
UNCOV
699
                return;
×
700
            }
701
        }
702
    }
703
    else // Y direction
704
    {
705
        if (y_rec_level < ny_req && dpy < (C1 - yr0))
113,080✔
706
        {
707

708
            // does a node already exist in the proposed split direction?
709
            if (node.get_child_node(split_pos) == 0)
96,932✔
710
            {
711
                // we can split in the y direction
712
                nodes.push_back(st_opt_element());
8,980✔
713
                st_opt_element *m = &nodes.back();
8,980✔
714
                m->set_address(node.get_address() + binary.at(index));
8,980✔
715

716
                if (split_pos) // upper
8,980✔
717
                {
718
                    double xr[] = {xr0, xr1};
4,500✔
719
                    double yr[] = {C1, yr1};
4,500✔
720
                    m->set_range(xr, yr);
4,500✔
721
                    node.setup(0, m);
4,500✔
722

723
                    create_node(*m, index + 1, binary, object, dprojected);
4,500✔
724
                    return;
4,500✔
725
                }
726
                else // lower
727
                {
728
                    double xr[] = {xr0, xr1};
4,480✔
729
                    double yr[] = {yr0, C1};
4,480✔
730
                    m->set_range(xr, yr);
4,480✔
731
                    node.setup(m, 0);
4,480✔
732

733
                    create_node(*m, index + 1, binary, object, dprojected);
4,480✔
734
                    return;
4,480✔
735
                }
736
            }
737
            else
738
            {
739
                // a node already exists, so just follow along without adding a new node in its place
740
                create_node(*(st_opt_element *)(node.get_child_node(split_pos)), index + 1, binary, object, dprojected);
87,952✔
741
                return;
87,952✔
742
            }
743
        }
744
        else
745
        {
746
            // no more splits allowed in the y direction
747
            // check if more y splits are allowed
748
            if (x_rec_level < nx_req && dpx < (C0 - xr0))
16,148✔
749
            {
750
                if (node.get_child_node(split_pos) == 0)
12,564✔
751
                {
752
                    nodes.push_back(st_opt_element());
9,576✔
753
                    st_opt_element *m = &nodes.back();
9,576✔
754

755
                    double xr[] = {xr0, xr1};
9,576✔
756
                    double yr[] = {yr0, yr1};
9,576✔
757

758
                    m->set_range(xr, yr);
9,576✔
759
                    m->set_address(node.get_address() + "x");
9,576✔
760
                    node.setup(m);
9,576✔
761

762
                    create_node(*m, index + 1, binary, object, dprojected);
9,576✔
763
                    return;
9,576✔
764
                }
765
                else
766
                {
767
                    create_node(*(st_opt_element *)(node.get_child_node(split_pos)), index + 1, binary, object, dprojected);
2,988✔
768
                    return;
2,988✔
769
                }
770
            }
771
            else
772
            {
773
                // no more x splits are allowed either, so add the object and return
774
                node.setup(object);
3,584✔
775
                return;
3,584✔
776
            }
777
        }
778
    }
779
}
780

781
std::string st_hash_tree::pos_to_binary(double x, double y, double res)
418,247✔
782
{
783
    /*
784
    Convert an x-y position into a binary tag
785
    */
786

787
    std::string tag;
418,247✔
788

789
    bool x_mode = true; // start with radius
418,247✔
790

791
    double
792
        y0 = Data.ylim[0],
418,247✔
793
        y1 = Data.ylim[1],
418,247✔
794
        x0 = Data.xlim[0],
418,247✔
795
        x1 = Data.xlim[1];
418,247✔
796

797
    int nc = std::max(nx_req, ny_req) * 2;
418,247✔
798

799
    for (int i = 0; i < nc; i++)
5,673,163✔
800
    {
801
        if (x_mode)
5,254,916✔
802
        {
803
            double cx = (x0 + x1) * 0.5;
2,627,458✔
804
            if (x > cx)
2,627,458✔
805
            {
806
                x0 = cx;
1,314,311✔
807
                tag.append("1");
1,314,311✔
808
            }
809
            else
810
            {
811
                x1 = cx;
1,313,147✔
812
                tag.append("0");
1,313,147✔
813
            }
814
        }
815
        else
816
        {
817
            double cy = (y0 + y1) * 0.5;
2,627,458✔
818
            if (y > cy)
2,627,458✔
819
            {
820
                y0 = cy;
1,309,814✔
821
                tag.append("1");
1,309,814✔
822
            }
823
            else
824
            {
825
                y1 = cy;
1,317,644✔
826
                tag.append("0");
1,317,644✔
827
            }
828
        }
829
        x_mode = !x_mode;
5,254,916✔
830
    }
831
    return tag;
418,247✔
832
}
×
833

834
void st_hash_tree::binary_to_pos(const std::string &binary, double *x, double *y)
3,590✔
835
{
836
    /*
837
    Returns double[2] of x,y position of center of zone described by binary.
838
    */
839
    bool x_mode = true; // start with radius
3,590✔
840

841
    double
842
        y0 = Data.ylim[0],
3,590✔
843
        y1 = Data.ylim[1],
3,590✔
844
        x0 = Data.xlim[0],
3,590✔
845
        x1 = Data.xlim[1];
3,590✔
846

847
    *x = (x0 + x1) / 2.;
3,590✔
848
    *y = (y0 + y1) / 2.;
3,590✔
849

850
    for (int i = 0; i < binary.size(); i++)
53,790✔
851
    {
852
        if (x_mode)
50,200✔
853
        {
854
            switch (binary.at(i))
25,100✔
855
            {
856
            case '0':
12,508✔
857
                x1 = *x;
12,508✔
858
                *x = (x1 + x0) / 2.;
12,508✔
859
                break;
12,508✔
860
            case '1':
12,592✔
861
                x0 = *x;
12,592✔
862
                *x = (x1 + x0) / 2.;
12,592✔
863
                break;
12,592✔
UNCOV
864
            case 'x':
×
UNCOV
865
                break;
×
866
            }
867
        }
868
        else
869
        {
870
            switch (binary.at(i))
25,100✔
871
            {
872
            case '0':
10,502✔
873
                y1 = *y;
10,502✔
874
                *y = (y1 + y0) / 2.;
10,502✔
875
                break;
10,502✔
876
            case '1':
11,014✔
877
                y0 = *y;
11,014✔
878
                *y = (y1 + y0) / 2.;
11,014✔
879
                break;
11,014✔
880
            case 'x':
3,584✔
881
                break;
3,584✔
882
            }
883
        }
884

885
        x_mode = !x_mode;
50,200✔
886
    }
887

888
    return;
3,590✔
889
}
890

891
void st_hash_tree::add_object(void *object, double locx, double locy, double *objsize)
16,176✔
892
{
893
    std::string tag = pos_to_binary_base(locx, locy);
16,176✔
894
    create_node(head_node, 0, tag, object, objsize);
16,176✔
895
}
16,176✔
896

897
} // namespace SolTrace::NativeRunner
STATUS · Troubleshooting · Open an Issue · Sales · Support · CAREERS · ENTERPRISE · START FREE · SCHEDULE DEMO
ANNOUNCEMENTS · TWITTER · TOS & SLA · Supported CI Services · What's a CI service? · Automated Testing

© 2026 Coveralls, Inc