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