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

NREL / SolTrace / 20378883693

19 Dec 2025 06:23PM UTC coverage: 89.332% (+0.1%) from 89.184%
20378883693

Pull #94

github

web-flow
Merge 5886fcdf4 into a73a760a4
Pull Request #94: Round robin validation tests

6029 of 6749 relevant lines covered (89.33%)

34032352.27 hits per line

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

82.9
/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])
25,042,032✔
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;
25,042,032✔
84
    int ly = 0;
25,042,032✔
85
    for (int i = 0; i < key.size(); i += 2)
254,692,784✔
86
    {
87
        if (key.at(i) == 'x')
243,988,592✔
88
            break;
14,337,840✔
89
        lx++;
229,650,752✔
90
    }
91
    for (int i = 1; i < key.size(); i += 2)
263,827,952✔
92
    {
93
        if (key.at(i) == 'x')
245,961,904✔
94
            break;
7,175,984✔
95
        ly++;
238,785,920✔
96
    }
97

98
    modkey = key; // copy
25,042,032✔
99

100
    // deal with x
101
    int xadd = val[0];
25,042,032✔
102
    int c = 0;
25,042,032✔
103
    bool first = true;
25,042,032✔
104
    for (int i = 2 * (lx - 1); i > -1; i -= 2)
43,594,884✔
105
    {
106
        int n = (int)(key.at(i) == '1');
43,594,884✔
107
        if (first)
43,594,884✔
108
            n += xadd;
25,042,032✔
109
        else
110
            n += c;
18,552,852✔
111
        first = false;
43,594,884✔
112

113
        if (n > 1)
43,594,884✔
114
        {
115
            modkey.at(i) = '0';
9,294,708✔
116
            c = 1;
9,294,708✔
117
        }
118
        else if (n < 0)
34,300,176✔
119
        {
120
            modkey.at(i) = '1';
9,274,062✔
121
            c = -1;
9,274,062✔
122
        }
123
        else
124
        {
125
            modkey.at(i) = n == 0 ? '0' : '1'; // 0 or 1
25,026,114✔
126
            c = 0;
25,026,114✔
127
            break;
25,026,114✔
128
        }
129

130
        if (i == 0 && c != 0)
18,568,770✔
131
        {
132
            // out of bounds
133
            return false;
15,918✔
134
        }
135
    }
136

137
    // deal with y
138
    int yadd = val[1];
25,026,114✔
139
    c = 0;
25,026,114✔
140
    first = true;
25,026,114✔
141
    for (int i = 2 * (ly - 1) + 1; i > 0; i -= 2)
43,594,266✔
142
    {
143
        int n = (int)(key.at(i) == '1');
43,591,368✔
144
        if (first)
43,591,368✔
145
            n += yadd;
25,026,114✔
146
        else
147
            n += c;
18,565,254✔
148
        first = false;
43,591,368✔
149

150
        if (n > 1)
43,591,368✔
151
        {
152
            modkey.at(i) = '0';
9,250,808✔
153
            c = 1;
9,250,808✔
154
        }
155
        else if (n < 0)
34,340,560✔
156
        {
157
            modkey.at(i) = '1';
9,317,344✔
158
            c = -1;
9,317,344✔
159
        }
160
        else
161
        {
162
            modkey[i] = n == 0 ? '0' : '1'; // 0 or 1
25,023,216✔
163
            c = 0;
25,023,216✔
164
            break;
25,023,216✔
165
        }
166

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

174
    return true;
25,026,114✔
175
}
176

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

184
void st_tree_node::setup(st_tree_node *child0)
2,786,032✔
185
{
186
    // Set both children equal to specified node. Used for 'x' keys.
187
    terminal = false;
2,786,032✔
188
    m0 = child0;
2,786,032✔
189
    m1 = m0;
2,786,032✔
190
}
2,786,032✔
191
void st_tree_node::setup(st_tree_node *child0, st_tree_node *child1)
11,095,088✔
192
{
193
    // Set children nodes equal to node pointer values (as applicable). For ptrs to 0, don't set.
194
    terminal = false;
11,095,088✔
195
    if (child0 != 0)
11,095,088✔
196
        m0 = child0;
5,552,246✔
197
    if (child1 != 0)
11,095,088✔
198
        m1 = child1;
5,542,842✔
199
}
11,095,088✔
200
void st_tree_node::setup(void *Data)
12,972,970✔
201
{
202
    // Set node as terminal and add data
203
    terminal = true;
12,972,970✔
204
    if (Data != 0) // Don't try to add a null value
12,972,970✔
205
        data.push_back(Data);
10,845,381✔
206
}
12,972,970✔
207
bool st_tree_node::is_terminal()
274,767,902✔
208
{
209
    return terminal;
274,767,902✔
210
}
211
std::vector<void *> *st_tree_node::get_array()
119,125,828✔
212
{
213
    return &data;
119,125,828✔
214
}
215
st_tree_node *st_tree_node::m_proc(std::string &key, int index)
1,902,886,670✔
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
        if (index <= key.length() - 1)
1,902,886,670✔
229
            c = key.at(index);
1,845,097,887✔
230
        else 
231
            return this;
57,788,783✔
232
    }
233
    catch (...)
×
234
    {
235
        return this;
×
236
    }
×
237
    if (terminal)
1,845,097,887✔
238
        return this;
20,112,175✔
239
    switch (c)
1,824,985,712✔
240
    {
241
    case 't':
×
242
        return this;
×
243
    case 'x':
919,331,066✔
244
    case '0':
245
        if (m0 != 0)
919,331,066✔
246
            return m0->m_proc(key, index + 1);
902,634,216✔
247
        else
248
            return 0;
16,696,850✔
249
    case '1':
905,654,646✔
250
        if (m1 != 0)
905,654,646✔
251
            return m1->m_proc(key, index + 1);
889,337,878✔
252
        else
253
            return 0;
16,316,768✔
254
    }
255

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

310
st_tree_node *st_tree_node::get_child_node(bool upper)
501,982,526✔
311
{
312
    return upper ? m1 : m0;
501,982,526✔
313
}
314

315
std::string st_tree_node::get_address()
38,923,152✔
316
{
317
    return address;
38,923,152✔
318
}
319

320
void st_tree_node::set_address(const std::string &addr)
13,881,120✔
321
{
322
    address = addr;
13,881,120✔
323
}
13,881,120✔
324

325
//-------------------------------------------------------------------------------------------------
326
void st_opt_element::set_range(double xrlo, double xrhi, double yrlo, double yrhi)
61✔
327
{
328
    xr[0] = xrlo;
61✔
329
    xr[1] = xrhi;
61✔
330
    yr[0] = yrlo;
61✔
331
    yr[1] = yrhi;
61✔
332
}
61✔
333

334
void st_opt_element::set_range(double *xri, double *yri)
13,881,120✔
335
{
336
    for (int i = 0; i < 2; i++)
41,643,360✔
337
    {
338
        xr[i] = xri[i];
27,762,240✔
339
        yr[i] = yri[i];
27,762,240✔
340
    }
341
}
13,881,120✔
342

343
st_opt_element *st_opt_element::process(std::string &key, int index)
110,914,576✔
344
{
345
    return (st_opt_element *)m_proc(key, index);
110,914,576✔
346
}
347

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

357
double *st_opt_element::get_yr() { return yr; }
543,937,175✔
358
double *st_opt_element::get_xr() { return xr; }
543,937,175✔
359

360
void st_opt_element::add_neighbor(void *ptr)
×
361
{
362
    neighbors.push_back(ptr);
×
363
}
×
364

365
std::vector<void *> *st_opt_element::get_neighbor_data()
145,298,101✔
366
{
367
    return &neighbors;
145,298,101✔
368
}
369

370
//-------------------------------------------------------------------------------------------------
371
st_hash_tree::st_hash_tree()
120✔
372
{
373
    log2inv = 1. / log(2.);
120✔
374
}
120✔
375

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

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

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

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

412
    // set up the head node's range. This doesn't actually create the tree yet.
413
    head_node.set_range(Data.xlim[0], Data.xlim[1], Data.ylim[0], Data.ylim[1]);
61✔
414

415
    return true;
61✔
416
}
417

418
std::string st_hash_tree::pos_to_binary_base(double x, double y)
98,861,432✔
419
{
420
    double res = fmin(Data.min_unit_dx, Data.min_unit_dy);
98,861,432✔
421
    return pos_to_binary(x, y, res);
98,861,432✔
422
}
423

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

431
    head_node = st_opt_element();
×
432
    nodes.clear();
×
433
    nx_req = -1;
×
434
    ny_req = -1;
×
435
}
×
436

437
void st_hash_tree::get_terminal_data(std::vector<std::vector<void *> *> &retdata)
×
438
{
439

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

450
    tnodes.clear();
61✔
451

452
    for (int i = 0; i < (int)nodes.size(); i++)
9,921,141✔
453
    {
454
        if (nodes.at(i).is_terminal())
9,921,080✔
455
            tnodes.push_back(&nodes.at(i));
3,130,254✔
456
    }
457

458
    return;
61✔
459
}
460

461
std::vector<st_opt_element> *st_hash_tree::get_all_nodes()
×
462
{
463
    return &nodes;
×
464
}
465

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

473
    std::vector<st_opt_element *> tnodes;
61✔
474
    std::unordered_map<std::string, std::set<st_opt_element *>> empty_nb_map;
61✔
475

476
    get_terminal_nodes(tnodes);
61✔
477
    for (int k = 0; k < tnodes.size(); k++)
3,130,315✔
478
    {
479
        st_opt_element *node = tnodes.at(k);
3,130,254✔
480
        int add[2];
481

482
        for (int i = -1; i < 2; i++)
12,521,016✔
483
        {
484
            for (int j = -1; j < 2; j++)
37,563,048✔
485
            {
486
                if (i == 0 && j == 0)
28,172,286✔
487
                    continue; // omit self zone
3,130,254✔
488

489
                // do binary addition to find the specified neighboring zone
490
                add[0] = i;
25,042,032✔
491
                add[1] = j;
25,042,032✔
492

493
                std::string nzone;
25,042,032✔
494

495
                if (binary_add(node->get_address(), nzone, add))
25,042,032✔
496
                {
497
                    st_opt_element *el = head_node.process(nzone, 0);
25,026,114✔
498
                    if (el != 0)
25,026,114✔
499
                    {
500
                        std::vector<void *> *dat = el->get_array();
19,080,668✔
501
                        if (dat != 0)
19,080,668✔
502
                        {
503
                            for (int k = 0; k < dat->size(); k++)
87,918,767✔
504
                                node->get_neighbor_data()->push_back(dat->at(k));
68,838,099✔
505
                        }
506
                    }
507
                    else
508
                    {
509
                        empty_nb_map[nzone].insert(node);
5,945,446✔
510
                    }
511
                }
512
            }
25,042,032✔
513
        }
514
    }
515

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

531
        // now add neighbors directly to the new terminal zone
532
        st_opt_element *newnode = &nodes.back();
2,127,589✔
533
        for (auto nit = mp->second.begin(); nit != mp->second.end(); nit++)
8,073,035✔
534
        {
535
            for (int j = 0; j < (*nit)->get_array()->size(); j++)
23,585,158✔
536
                newnode->get_neighbor_data()->push_back((*nit)->get_array()->at(j));
17,639,712✔
537
        }
538
    }
539
}
61✔
540

541
bool st_hash_tree::get_all_data_at_loc(std::vector<void *> &data,
85,888,462✔
542
                                       double locx, double locy)
543
{
544
    std::string bin = pos_to_binary_base(locx, locy);
85,888,462✔
545

546
    data.clear();
85,888,462✔
547

548
    st_opt_element *z = head_node.process(bin, 0);
85,888,462✔
549
    if (z != 0)
85,888,462✔
550
    {
551
        std::vector<void *> *zd = z->get_array();
58,820,290✔
552
        if (zd != 0)
58,820,290✔
553
            for (int i = 0; i < zd->size(); i++)
175,246,160✔
554
                data.push_back(zd->at(i));
116,425,870✔
555

556
        zd = z->get_neighbor_data();
58,820,290✔
557
        if (zd != 0)
58,820,290✔
558
            for (int i = 0; i < zd->size(); i++)
917,585,539✔
559
                data.push_back(zd->at(i));
858,765,249✔
560

561
        if (!data.empty())
58,820,290✔
562
            return true;
58,808,922✔
563
    }
564

565
    return false;
27,079,540✔
566
}
85,888,462✔
567

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

578
    // evaluate the derivatives at the center of the element.
579
    double
580
        xr0 = node.get_xr()[0],
270,904,793✔
581
        xr1 = node.get_xr()[1],
270,904,793✔
582
        yr0 = node.get_yr()[0],
270,904,793✔
583
        yr1 = node.get_yr()[1],
270,904,793✔
584
        C0 = (xr0 + xr1) * 0.5,
270,904,793✔
585
        C1 = (yr0 + yr1) * 0.5;
270,904,793✔
586
    double dpx, dpy;
587
    if (dprojected == 0)
270,904,793✔
588
    {
589
        dpx = 0.;
113,375,951✔
590
        dpy = 0.;
113,375,951✔
591
    }
592
    else
593
    {
594
        dpx = dprojected[0];
157,528,842✔
595
        dpy = dprojected[1];
157,528,842✔
596
    }
597

598
    bool x_direction = (double)(index / 2) == ((double)index / 2.);
270,904,793✔
599

600
    int x_rec_level, y_rec_level;
601

602
    if (x_direction)
270,904,793✔
603
    {
604
        x_rec_level = index / 2;
140,017,918✔
605
        y_rec_level = x_rec_level - 1;
140,017,918✔
606
    }
607
    else
608
    {
609
        x_rec_level = y_rec_level = (index - 1) / 2;
130,886,875✔
610
    }
611

612
    // check to see if we're at the end of the string
613
    if (index > binary.size() - 1)
270,904,793✔
614
    {
615
        // Add the object to the data vector and return
616
        node.setup(object);
6,057,971✔
617
        return;
6,057,971✔
618
    }
619

620
    // check to see if this node is terminal. If so, add the data here rather than continuing branching.
621
    if (node.is_terminal())
264,846,822✔
622
    {
623
        node.setup(object);
3,991,168✔
624
        return;
3,991,168✔
625
    }
626

627
    // which direction split is indicated?
628
    bool split_pos = binary.at(index) == '1';
260,855,654✔
629

630
    if (x_direction)
260,855,654✔
631
    {
632
        if (x_rec_level < nx_req && dpx < (C0 - xr0))
132,030,294✔
633
        {
634

635
            // does a node already exist in the proposed split direction?
636
            if (node.get_child_node(split_pos) == 0)
120,211,447✔
637
            {
638
                // we can split in the x direction
639
                nodes.push_back(st_opt_element());
4,333,422✔
640
                st_opt_element *m = &nodes.back();
4,333,422✔
641
                m->set_address(node.get_address() + binary.at(index));
4,333,422✔
642

643
                if (split_pos) // upper
4,333,422✔
644
                {
645
                    double xr[] = {C0, xr1};
2,166,414✔
646
                    double yr[] = {yr0, yr1};
2,166,414✔
647
                    m->set_range(xr, yr);
2,166,414✔
648
                    node.setup(0, m);
2,166,414✔
649

650
                    create_node(*m, index + 1, binary, object, dprojected);
2,166,414✔
651
                    return;
2,166,414✔
652
                }
653
                else // lower
654
                {
655
                    double xr[] = {xr0, C0};
2,167,008✔
656
                    double yr[] = {yr0, yr1};
2,167,008✔
657
                    m->set_range(xr, yr);
2,167,008✔
658
                    node.setup(m, 0);
2,167,008✔
659

660
                    create_node(*m, index + 1, binary, object, dprojected);
2,167,008✔
661
                    return;
2,167,008✔
662
                }
663
            }
664
            else
665
            {
666
                // a node already exists, so just follow along without adding a new node in its place
667
                create_node(*(st_opt_element *)(node.get_child_node(split_pos)), index + 1, binary, object, dprojected);
115,878,025✔
668
                return;
115,878,025✔
669
            }
670
        }
671
        else
672
        {
673
            // no more splits allowed in the x direction
674
            // check if more y splits are allowed
675
            if (y_rec_level < ny_req && dpy < (C1 - yr0))
11,818,847✔
676
            {
677
                if (node.get_child_node(split_pos) == 0)
10,675,428✔
678
                {
679
                    nodes.push_back(st_opt_element());
1,889,034✔
680
                    st_opt_element *m = &nodes.back();
1,889,034✔
681

682
                    double xr[] = {xr0, xr1};
1,889,034✔
683
                    double yr[] = {yr0, yr1};
1,889,034✔
684

685
                    m->set_range(xr, yr);
1,889,034✔
686
                    m->set_address(node.get_address() + "x");
1,889,034✔
687
                    node.setup(m);
1,889,034✔
688

689
                    create_node(*m, index + 1, binary, object, dprojected);
1,889,034✔
690
                    return;
1,889,034✔
691
                }
692
                else
693
                {
694
                    create_node(*(st_opt_element *)(node.get_child_node(split_pos)), index + 1, binary, object, dprojected);
8,786,394✔
695
                    return;
8,786,394✔
696
                }
697
            }
698
            else
699
            {
700
                // no more y splits are allowed either, so add the object and return
701
                node.setup(object);
1,143,419✔
702
                return;
1,143,419✔
703
            }
704
        }
705
    }
706
    else // Y direction
707
    {
708
        if (y_rec_level < ny_req && dpy < (C1 - yr0))
128,825,360✔
709
        {
710

711
            // does a node already exist in the proposed split direction?
712
            if (node.get_child_node(split_pos) == 0)
124,367,211✔
713
            {
714
                // we can split in the y direction
715
                nodes.push_back(st_opt_element());
6,761,666✔
716
                st_opt_element *m = &nodes.back();
6,761,666✔
717
                m->set_address(node.get_address() + binary.at(index));
6,761,666✔
718

719
                if (split_pos) // upper
6,761,666✔
720
                {
721
                    double xr[] = {xr0, xr1};
3,376,428✔
722
                    double yr[] = {C1, yr1};
3,376,428✔
723
                    m->set_range(xr, yr);
3,376,428✔
724
                    node.setup(0, m);
3,376,428✔
725

726
                    create_node(*m, index + 1, binary, object, dprojected);
3,376,428✔
727
                    return;
3,376,428✔
728
                }
729
                else // lower
730
                {
731
                    double xr[] = {xr0, xr1};
3,385,238✔
732
                    double yr[] = {yr0, C1};
3,385,238✔
733
                    m->set_range(xr, yr);
3,385,238✔
734
                    node.setup(m, 0);
3,385,238✔
735

736
                    create_node(*m, index + 1, binary, object, dprojected);
3,385,238✔
737
                    return;
3,385,238✔
738
                }
739
            }
740
            else
741
            {
742
                // a node already exists, so just follow along without adding a new node in its place
743
                create_node(*(st_opt_element *)(node.get_child_node(split_pos)), index + 1, binary, object, dprojected);
117,605,545✔
744
                return;
117,605,545✔
745
            }
746
        }
747
        else
748
        {
749
            // no more splits allowed in the y direction
750
            // check if more y splits are allowed
751
            if (x_rec_level < nx_req && dpx < (C0 - xr0))
4,458,149✔
752
            {
753
                if (node.get_child_node(split_pos) == 0)
2,677,737✔
754
                {
755
                    nodes.push_back(st_opt_element());
896,998✔
756
                    st_opt_element *m = &nodes.back();
896,998✔
757

758
                    double xr[] = {xr0, xr1};
896,998✔
759
                    double yr[] = {yr0, yr1};
896,998✔
760

761
                    m->set_range(xr, yr);
896,998✔
762
                    m->set_address(node.get_address() + "x");
896,998✔
763
                    node.setup(m);
896,998✔
764

765
                    create_node(*m, index + 1, binary, object, dprojected);
896,998✔
766
                    return;
896,998✔
767
                }
768
                else
769
                {
770
                    create_node(*(st_opt_element *)(node.get_child_node(split_pos)), index + 1, binary, object, dprojected);
1,780,739✔
771
                    return;
1,780,739✔
772
                }
773
            }
774
            else
775
            {
776
                // no more x splits are allowed either, so add the object and return
777
                node.setup(object);
1,780,412✔
778
                return;
1,780,412✔
779
            }
780
        }
781
    }
782
}
783

784
std::string st_hash_tree::pos_to_binary(double x, double y, double res)
98,861,432✔
785
{
786
    /*
787
    Convert an x-y position into a binary tag
788
    */
789

790
    std::string tag;
98,861,432✔
791

792
    bool x_mode = true; // start with radius
98,861,432✔
793

794
    double
795
        y0 = Data.ylim[0],
98,861,432✔
796
        y1 = Data.ylim[1],
98,861,432✔
797
        x0 = Data.xlim[0],
98,861,432✔
798
        x1 = Data.xlim[1];
98,861,432✔
799

800
    int nc = std::max(nx_req, ny_req) * 2;
98,861,432✔
801

802
    for (int i = 0; i < nc; i++)
1,929,072,604✔
803
    {
804
        if (x_mode)
1,830,211,172✔
805
        {
806
            double cx = (x0 + x1) * 0.5;
915,105,586✔
807
            if (x > cx)
915,105,586✔
808
            {
809
                x0 = cx;
456,709,668✔
810
                tag.append("1");
456,709,668✔
811
            }
812
            else
813
            {
814
                x1 = cx;
458,395,918✔
815
                tag.append("0");
458,395,918✔
816
            }
817
        }
818
        else
819
        {
820
            double cy = (y0 + y1) * 0.5;
915,105,586✔
821
            if (y > cy)
915,105,586✔
822
            {
823
                y0 = cy;
461,059,888✔
824
                tag.append("1");
461,059,888✔
825
            }
826
            else
827
            {
828
                y1 = cy;
454,045,698✔
829
                tag.append("0");
454,045,698✔
830
            }
831
        }
832
        x_mode = !x_mode;
1,830,211,172✔
833
    }
834
    return tag;
98,861,432✔
835
}
×
836

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

844
    double
845
        y0 = Data.ylim[0],
2,127,589✔
846
        y1 = Data.ylim[1],
2,127,589✔
847
        x0 = Data.xlim[0],
2,127,589✔
848
        x1 = Data.xlim[1];
2,127,589✔
849

850
    *x = (x0 + x1) / 2.;
2,127,589✔
851
    *y = (y0 + y1) / 2.;
2,127,589✔
852

853
    for (int i = 0; i < binary.size(); i++)
44,478,403✔
854
    {
855
        if (x_mode)
42,350,814✔
856
        {
857
            switch (binary.at(i))
21,223,106✔
858
            {
859
            case '0':
9,893,762✔
860
                x1 = *x;
9,893,762✔
861
                *x = (x1 + x0) / 2.;
9,893,762✔
862
                break;
9,893,762✔
863
            case '1':
9,917,308✔
864
                x0 = *x;
9,917,308✔
865
                *x = (x1 + x0) / 2.;
9,917,308✔
866
                break;
9,917,308✔
867
            case 'x':
1,412,036✔
868
                break;
1,412,036✔
869
            }
870
        }
871
        else
872
        {
873
            switch (binary.at(i))
21,127,708✔
874
            {
875
            case '0':
9,762,624✔
876
                y1 = *y;
9,762,624✔
877
                *y = (y1 + y0) / 2.;
9,762,624✔
878
                break;
9,762,624✔
879
            case '1':
10,147,415✔
880
                y0 = *y;
10,147,415✔
881
                *y = (y1 + y0) / 2.;
10,147,415✔
882
                break;
10,147,415✔
883
            case 'x':
1,217,669✔
884
                break;
1,217,669✔
885
            }
886
        }
887

888
        x_mode = !x_mode;
42,350,814✔
889
    }
890

891
    return;
2,127,589✔
892
}
893

894
void st_hash_tree::add_object(void *object, double locx, double locy, double *objsize)
12,972,970✔
895
{
896
    std::string tag = pos_to_binary_base(locx, locy);
12,972,970✔
897
    create_node(head_node, 0, tag, object, objsize);
12,972,970✔
898
}
12,972,970✔
899

900
} // 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