1// SPDX-License-Identifier: MIT OR MPL-2.0 OR LGPL-2.1-or-later OR GPL-2.0-or-later
2// Copyright 2010, SIL International, All rights reserved.
3
4#include <algorithm>
5#include <cmath>
6#include <limits>
7
8#include "inc/Intervals.h"
9#include "inc/Segment.h"
10#include "inc/Slot.h"
11#include "inc/debug.h"
12#include "inc/bits.h"
13
14using namespace graphite2;
15
16#include <cmath>
17
18inline
19Zones::Exclusion Zones::Exclusion::split_at(float p) {
20 Exclusion r(*this);
21 r.xm = x = p;
22 return r;
23}
24
25inline
26void Zones::Exclusion::left_trim(float p) {
27 x = p;
28}
29
30inline
31Zones::Exclusion & Zones::Exclusion::operator += (Exclusion const & rhs) {
32 c += rhs.c; sm += rhs.sm; smx += rhs.smx; open = false;
33 return *this;
34}
35
36inline
37uint8 Zones::Exclusion::outcode(float val) const {
38 float p = val;
39 //float d = std::numeric_limits<float>::epsilon();
40 float d = 0.;
41 return ((p - xm >= d) << 1) | (x - p > d);
42}
43
44void Zones::exclude_with_margins(float xmin, float xmax, int axis) {
45 remove(xmin, xmax);
46 weightedAxis(axis, xmin-_margin_len, xmin, 0, 0, _margin_weight, xmin-_margin_len, 0, 0, false);
47 weightedAxis(axis, xmax, xmax+_margin_len, 0, 0, _margin_weight, xmax+_margin_len, 0, 0, false);
48}
49
50namespace
51{
52
53inline
54bool separated(float a, float b) {
55 return a != b;
56 //int exp;
57 //float res = frexpf(fabs(a - b), &exp);
58 //return (*(unsigned int *)(&res) > 4);
59 //return std::fabs(a-b) > std::numeric_limits<float>::epsilon(); // std::epsilon may not work. but 0.5 fails exising 64 bit tests
60 //return std::fabs(a-b) > 0.5f;
61}
62
63}
64
65void Zones::insert(Exclusion e)
66{
67#if !defined GRAPHITE2_NTRACING
68 addDebug(&e);
69#endif
70 e.x = max(e.x, _pos);
71 e.xm = min(e.xm, _posm);
72 if (e.x >= e.xm) return;
73
74 for (iterator i = _exclusions.begin(), ie = _exclusions.end(); i != ie && e.x < e.xm; ++i)
75 {
76 const uint8 oca = e.outcode(i->x),
77 ocb = e.outcode(i->xm);
78 if ((oca & ocb) != 0) continue;
79
80 switch (oca ^ ocb) // What kind of overlap?
81 {
82 case 0: // e completely covers i
83 // split e at i.x into e1,e2
84 // split e2 at i.mx into e2,e3
85 // drop e1 ,i+e2, e=e3
86 *i += e;
87 e.left_trim(i->xm);
88 break;
89 case 1: // e overlaps on the rhs of i
90 // split i at e->x into i1,i2
91 // split e at i.mx into e1,e2
92 // trim i1, insert i2+e1, e=e2
93 if (!separated(i->xm, e.x)) break;
94 if (separated(i->x,e.x)) { i = _exclusions.insert(i,i->split_at(e.x)); ++i; }
95 *i += e;
96 e.left_trim(i->xm);
97 break;
98 case 2: // e overlaps on the lhs of i
99 // split e at i->x into e1,e2
100 // split i at e.mx into i1,i2
101 // drop e1, insert e2+i1, trim i2
102 if (!separated(e.xm, i->x)) return;
103 if (separated(e.xm, i->xm)) i = _exclusions.insert(i,i->split_at(e.xm));
104 *i += e;
105 return;
106 case 3: // i completely covers e
107 // split i at e.x into i1,i2
108 // split i2 at e.mx into i2,i3
109 // insert i1, insert e+i2
110 if (separated(e.xm, i->xm)) i = _exclusions.insert(i,i->split_at(e.xm));
111 i = _exclusions.insert(i, i->split_at(e.x));
112 *++i += e;
113 return;
114 }
115
116 ie = _exclusions.end();
117 }
118}
119
120
121void Zones::remove(float x, float xm)
122{
123#if !defined GRAPHITE2_NTRACING
124 removeDebug(x, xm);
125#endif
126 x = max(x, _pos);
127 xm = min(xm, _posm);
128 if (x >= xm) return;
129
130 for (iterator i = _exclusions.begin(), ie = _exclusions.end(); i != ie; ++i)
131 {
132 const uint8 oca = i->outcode(x),
133 ocb = i->outcode(xm);
134 if ((oca & ocb) != 0) continue;
135
136 switch (oca ^ ocb) // What kind of overlap?
137 {
138 case 0: // i completely covers e
139 if (separated(i->x, x)) { i = _exclusions.insert(i,i->split_at(x)); ++i; }
140 GR_FALLTHROUGH;
141 // no break
142 case 1: // i overlaps on the rhs of e
143 i->left_trim(xm);
144 return;
145 case 2: // i overlaps on the lhs of e
146 i->xm = x;
147 if (separated(i->x, i->xm)) break;
148 GR_FALLTHROUGH;
149 // no break
150 case 3: // e completely covers i
151 i = _exclusions.erase(i);
152 --i;
153 break;
154 }
155
156 ie = _exclusions.end();
157 }
158}
159
160
161Zones::const_iterator Zones::find_exclusion_under(float x) const
162{
163 size_t l = 0, h = _exclusions.size();
164
165 while (l < h)
166 {
167 size_t const p = (l+h) >> 1;
168 switch (_exclusions[p].outcode(x))
169 {
170 case 0 : return _exclusions.begin()+p;
171 case 1 : h = p; break;
172 case 2 :
173 case 3 : l = p+1; break;
174 }
175 }
176
177 return _exclusions.begin()+l;
178}
179
180
181float Zones::closest(float origin, float & cost) const
182{
183 float best_c = std::numeric_limits<float>::max(),
184 best_x = 0;
185
186 const const_iterator start = find_exclusion_under(origin);
187
188 // Forward scan looking for lowest cost
189 for (const_iterator i = start, ie = _exclusions.end(); i != ie; ++i)
190 if (i->track_cost(best_c, best_x, origin)) break;
191
192 // Backward scan looking for lowest cost
193 // We start from the exclusion to the immediate left of start since we've
194 // already tested start with the right most scan above.
195 for (const_iterator i = start-1, ie = _exclusions.begin()-1; i != ie; --i)
196 if (i->track_cost(best_c, best_x, origin)) break;
197
198 cost = (best_c == std::numeric_limits<float>::max() ? -1 : best_c);
199 return best_x;
200}
201
202
203// Cost and test position functions
204
205bool Zones::Exclusion::track_cost(float & best_cost, float & best_pos, float origin) const {
206 const float p = test_position(origin),
207 localc = cost(p - origin);
208 if (open && localc > best_cost) return true;
209
210 if (localc < best_cost)
211 {
212 best_cost = localc;
213 best_pos = p;
214 }
215 return false;
216}
217
218inline
219float Zones::Exclusion::cost(float p) const {
220 return (sm * p - 2 * smx) * p + c;
221}
222
223
224float Zones::Exclusion::test_position(float origin) const {
225 if (sm < 0)
226 {
227 // sigh, test both ends and perhaps the middle too!
228 float res = x;
229 float cl = cost(x);
230 if (x < origin && xm > origin)
231 {
232 float co = cost(origin);
233 if (co < cl)
234 {
235 cl = co;
236 res = origin;
237 }
238 }
239 float cr = cost(xm);
240 return cl > cr ? xm : res;
241 }
242 else
243 {
244 float zerox = smx / sm + origin;
245 if (zerox < x) return x;
246 else if (zerox > xm) return xm;
247 else return zerox;
248 }
249}
250
251
252#if !defined GRAPHITE2_NTRACING
253
254void Zones::jsonDbgOut(Segment *seg) const {
255
256 if (_dbg)
257 {
258 for (Zones::idebugs s = dbgs_begin(), e = dbgs_end(); s != e; ++s)
259 {
260 *_dbg << json::flat << json::array
261 << objectid(dslot(seg, (Slot *)(s->_env[0])))
262 << reinterpret_cast<ptrdiff_t>(s->_env[1]);
263 if (s->_isdel)
264 *_dbg << "remove" << Position(s->_excl.x, s->_excl.xm);
265 else
266 *_dbg << "exclude" << json::flat << json::array
267 << s->_excl.x << s->_excl.xm
268 << s->_excl.sm << s->_excl.smx << s->_excl.c
269 << json::close;
270 *_dbg << json::close;
271 }
272 }
273}
274
275#endif
276